TopCoder

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

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

55.9% (38/68)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144