63. 惠惠的おっぱい魔法

Problem Description

惠惠想讓自己胸部變大，從 $Lv. 0$ 上升到 $Lv. 1$ 需要花費 1 單位魔法；從 $Lv. x-1$ 上升到 $Lv. x$ 需要花費

$E(x) = (x!)^{2}$

單位的魔法。她想一口氣從 $Lv. 0$ 上升到 $Lv. N$ ，但是一次從 $i$ 上升到 $j$ 的代價是所有經過的 $E(i+1) … E(j)$ 的乘積，這個花費十分巨大，但經過維茲的藥水加持，惠惠可以挑選一個小於 $10^6$ 的質數 $P$ ， 使總花費中除了 $P$ 以外的質因數全部消失 (從花費中被除掉) 。請問剩下的花費為多少？請輸出花費會是P的幾次方。 (由於答案遠超過C++ int範圍，請將答案mod $(10^{9} + 7)$再輸出。)

Input Format

輸入只有一行，其中有兩個數字 $N$ 和 $P$ ，其意義如題目敘述。

Input Constraints

Testcase #1~5 ( score: 30 )

• $ 1 < N \leq 10^9$
• $ \max(2, \frac{N}{10^6}) \leq P \leq \min(10^6, N) $

Testcase #6~10 ( score: 70 )

• $ 1 < N \leq 10^{18}$
• $ 1 < P \leq \min(10^6, N) $

對所有測資，$P$ 保證是質數。

Output format

輸出一個數字：累乘 $E(1)$ 到 $E(N)$ 後將 $P$ 以外的質因數都除盡，剩下為 $P^x$ 。輸出此 $x$ mod $(10^{9} + 7)$ 。

Sample IO

Sample In 1

18026 9013

Sample Out 1

18030

Sample In 2

12 3

Sample Out 2

52

Sample In 3

10 2

Sample Out 3

76

Sample Explonasion

選下面的都是邪教

Hint

題目要求的 $x$ 等同於整個乘積能被 $P$ 整除幾次。

Judge Setting

run-time limit: 1000 ms
memory limit: 256000000 byte
測資數量: 10