Coloring the Circular Regions

B has a circular ring divided into n regions. He wants to color these regions using m colors (colors are numbered from 0 to m − 1). However, he does not want any consecutive m regions (taken cyclically) to use all m colors exactly once (i.e. form a permutation of the m colors). In other words, for every contiguous block of m regions along the ring, the set of colors in that block should not be equal to \(\{0,1,\dots,m-1\}\).

Moreover, two colorings are considered essentially the same if one can be rotated to obtain the other. (Note that if they need to be reflected (flipped) to match, they are considered different.)

For example, when \(n=4\) and \(m=4\):

• The colorings [1,2,3,4] and [3,4,1,2] are essentially the same (by rotation).
• [1,2,3,4] and [4,3,2,1] are essentially different.
• [1,2,1,2] and [2,1,2,1] are essentially the same.

Your task is to compute the number of essentially different valid colorings, modulo \(10^9+7\).

Note: For any contiguous block of \(m\) regions (the block is taken cyclically on the ring), the following must hold: \[ \text{if } X \text{ is the multiset of colors in the block, then } |X|< m. \]

inputFormat

The input consists of a single line with two integers n and m (\(1 \le n, m \le \text{small}\)); they denote the number of regions and the number of colors respectively.

outputFormat

Output a single integer – the number of essentially different valid colorings modulo \(10^9+7\).

sample

4 4

64