TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

53.2% (41/77)

Description

你,もも,是個考古學家。
這次你去到了亞特蘭提斯,
走著走著你發現了一個地穴。
地穴被一個大石碑擋住,
上面沾滿了灰塵,
你輕拍了石碑。
「密碼鎖!!?」你驚呼了一聲。
你向來不太會解密碼鎖,
所以你拿出了筆電,
開始計算答案到底是多少,
你發現答案可能太大,
仔細的看了一下石碑上面
「如果你發現你無法將你的答案用密碼鎖表達,請試著mod 1000000007」。

密碼鎖的下方寫著:
給定$n,k$求滿足下列的組合數
1. $1 \leq x,f(x)\leq n$
2. $ x,f(x) $ 屬於正整數
3. $IF f(x) = f(y) 則x=y$
4. $f_{2}(x)=f(f_{1}(x))=f(f(x))$;亦即$f_{a}(x)=f(f_{a-1}(x))$
5. $f_{k}(x)=x$
6. $f(x) \ne x$
7. 令$x$帶入$f$回到$x$最短的長度為$l$,則$1 \leq x \leq n$都需要具有相同的$l$
舉個例子$n=4, k=2$時
f(1)=2 f(2)=1 f(3)=4 f(4)=3
是一個滿足的解
對於所有$1 \leq x \leq n$都有滿足$f_{2}(x)=x$

Input Format

本題有多筆測資,
請讀到EOF。

$n, k \leq 1000000$

Output Format

Sample Input

4 2
9 3

Sample Output

3
2240

Hints

n=4 k=2
f(1)=2 f(2)=1 f(3)=4 f(4)=3
f(1)=3 f(2)=4 f(3)=1 f(4)=2
f(1)=4 f(2)=3 f(3)=2 f(4)=1
共三組解

Problem Source

Tocknicsu

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10