Problem Description

Given parameters \( N \) and \( K \). A number \( A \) is called a good number if and only if for any \( i \in \{ 1, 2, \cdots, N-1 \} \), it satisfies: \( \dfrac{A}{K^i} - \left\lfloor \dfrac{A}{K^i} \right\rfloor > \dfrac{A}{K^N} \).

Find the number of good numbers modulo \( 10^9+7 \).

Input Format

A single line containing two positive integers \( N \) and \( K \).

Output Format

A single line, the number of good numbers modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

10 10

Sample Output #1

999989991

Sample Input #2

6 2

Sample Output #2

9

Notes

• For \( 20\% \) of the data, \( K^N \leq 5 \times 10^4 \).
• For \( 60\% \) of the data, \( N, K \leq 10^6 \).
• For \( 100\% \) of the data, \( 1 \leq N, K \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分