Counting Spanning Trees of a k‑Order Wheel

In this problem, CluCalska wants to count the number of spanning trees of a k‑order wheel with \(n+1\) vertices. The graph is defined as follows:

• Vertex \(0\) is the center.
• Vertices \(1,2,\dots,n\) form a cycle. That is, for \(1 \le i < n\) there is an edge connecting \(i\) and \(i+1\), and an additional edge connects vertex \(n\) and vertex \(1\).
• For every \(1 \le i \le \frac{n}{k}\) (it is guaranteed that \(n\) is divisible by \(k\)), an extra edge (called a spoke) is added between vertex \(0\) and vertex \(i\,k\).

Your task is to compute the number of spanning trees of this graph modulo \(10^9+7\). The answer is guaranteed to be computed correctly if you use the Matrix‑Tree Theorem. In this problem one may show that if we remove the \(0^{th}\) row and column from the Laplacian matrix of the graph, the determinant of the resulting \(n\times n\) matrix equals the number of spanning trees.

The Laplacian matrix \(L\) of the graph is defined as follows. For vertices \(1\) through \(n\):

• For each vertex \(i\), the diagonal entry is \[ L_{ii} = \text{deg}(i) = 2 + \begin{cases}1,&\text{if } i\equiv 0\; (\bmod\; k)\\0,&\text{otherwise} \end{cases} \] because every vertex on the cycle has degree 2 and those vertices that are multiples of \(k\) have an extra incident spoke edge.
• For each edge in the cycle, if vertices \(i\) and \(j\) are adjacent (with indices taken modulo \(n\), i.e. vertex \(1\) is adjacent to vertex \(n\) as well as vertex \(2\)), then \(L_{ij} = -1\).
• All other off‐diagonal entries are 0.

Thus, given input \(n\) and \(k\) (with \(n\bmod k=0\)), you have to form the \(n \times n\) matrix \(M\) defined by:

[ M_{ii} = 2 + \begin{cases}1,&\text{if } i\equiv 0; (\bmod; k)\0,&\text{otherwise} \end{cases}, \quad M_{i,j} = \begin{cases}-1,&\text{if } j=i-1 \text{ or } j=i+1 \text{ (cyclic indices)}\0,&\text{otherwise.} \end{cases} ]

Your answer is the determinant of \(M\) modulo \(10^9+7\).

Input Format: The input consists of a single line containing two integers \(n\) and \(k\). It is guaranteed that \(n\bmod k=0\).

Output Format: Output a single integer – the number of spanning trees modulo \(10^9+7\).

inputFormat

The input is given in one line containing two space‑separated integers \(n\) and \(k\), where \(n\) is the number of cycle vertices (the graph has \(n+1\) vertices in total) and \(k\) is the order of the wheel (\(n\) is divisible by \(k\)).

outputFormat

Output a single integer, the number of spanning trees of the given graph modulo \(10^9+7\).

sample

4 2

12