Niuniu likes traveling. Now he will travel on a special graph.
Given k and n, The
directed graph contains n vertices, which are numbered from 0 to n - 1.
For the vertex i, and for 1 <= j <= k, there is a directed edge from vertex i to vertex ((i + j) % n).
We want to know the number of (directed) cycles, that pass each directed edge exactly once.
As the answer might be very large, you only need to output the answer mod 1000000007.