Counting Good Numbers

We are given two positive integers N and K. Consider an integer A (written in base K with exactly N digits – leading zeros are allowed) to be a good number if and only if for every integer i with 1 ≤ i ≤ N-1 the following inequality holds:

\[ \frac{A}{K^i} - \left\lfloor \frac{A}{K^i} \right\rfloor > \frac{A}{K^N} \]

In other words, if we write A in base K as \[ A = a_{N-1} K^{N-1} + a_{N-2} K^{N-2} + \cdots + a_0\, , \] then note that \(\frac{A}{K^N}\) is the number represented by the digits \(0.a_{N-1}a_{N-2}\cdots a_0\) in base K and for any i with \(1 \le i \le N-1\) the fractional part of \(\frac{A}{K^i}\) is given by \[ \left\{ \frac{A}{K^i} \right\} = \frac{a_{i-1} K^{i-1} + a_{i-2} K^{i-2} + \cdots + a_0}{K^i} \,. \] The condition requires that for every such i we have \[ \frac{a_{i-1} K^{i-1} + a_{i-2} K^{i-2} + \cdots + a_0}{K^i} > \frac{A}{K^N}\,. \]

Your task is to compute the number of good numbers modulo \(10^9+7\). Note that A is taken from the range \([1, K^N)\) (when written with N digits in base K). For example, when \(N=2\), a number A = a_1 K + a_0 is good if and only if \[ a_0 \times K > a_1 \times K + a_0 \quad \Longleftrightarrow \quad a_1 < \frac{(K-1)a_0}{K}\,. \]

inputFormat

The input consists of two space‐separated integers N and K.

outputFormat

Output a single integer: the number of good numbers modulo \(10^9+7\).

sample

2 10

45