問題一覧 > 通常問題

No.1039 Do It on Project Euler

レベル : / AI推定難易度 : 2525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : testestest / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 3937 / 自分の提出
問題文最終更新日: 2020-04-24 18:50:59
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 245 (順位表) の他の問題:

Story

yuki created the following problem.

You are given a sequence a of length N.
Answer Q queries of the following two types.
・1 x y  Change $a_x$ to $y$ ($0 \leq x < N,\ \ 0\leq y < M$)
・2 x y  Output $a_x + a_{x+1} + ... + a_y \pmod M$ ($0\leq x \leq y < N$)

Do you know the Binary Indexed Tree? yuki does.
This problem can be solved using a Binary Indexed Tree.

yuki likes Binary Indexed Trees.
By the way, a pair of a set and a binary operation satisfying certain nice conditions is called an abelian group.
(For the precise definition, see Wikipedia: Abelian group)
It is known that, in general, a Binary Indexed Tree can carry the structure of an abelian group.
That is, if the set $\{0,...,M-1\}$ forms an abelian group under a binary operation ★, then the second query of the above problem can be replaced with

・2 x y  Output $a_x ★ a_{x+1} ★ ... ★ a_y$
and the problem can still be solved with a Binary Indexed Tree.

Problem Statement

How many binary operations on the set $\{0,...,M-1\}$ form an abelian group? Answer $\bmod 10^9+7$.

Input

$M$

$1\leq M < 10^6$

Output

Output the number of binary operations on $\{0,...,M-1\}$ that form an abelian group, $\bmod 10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
3
Output
3

The following 3 operations exist.
$x ★ y = x+y \pmod 3$

★0 1 2 
0012
1120
2201

$x ★ y = x+y+1 \pmod 3$
★0 1 2 
0120
1201
2012

$x ★ y = x+y +2\pmod 3$
★0 1 2 
0201
1012
2120

Sample 2
Input
4
Output
16

Besides operations such as $x ★ y = x+y+k \pmod 4$ and $x ★ y = x \ \mbox{XOR}\ y\ \mbox{XOR} \ k\ (0\leq k < 4)$, mysterious operations like the following also satisfy the condition.

★0 1 2 3 
03201
12310
20123
31032

This mysterious operation can be computed, for example, in python as follows.
pow(2,pow(3,x,5)+pow(3,y,5)+1,5)%4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。