Hide

# Nice Prefixes

Consider strings formed from characters from an alphabet of size $K$. For example, if $K = 4$, our alphabet might be ${a,b,c,d}$, and an example string is $bbcac$.

For a string $S$, define $\mathrm{count}(S, k)$ to be the number of occurrences of the symbol $k$ in $S$. For example, $\mathrm{count}(bbcac, b) = 2$ and $\mathrm{count}(bbcac, a) = 1$.

A prefix of a string $S$ is any string obtained from $S$ by deleting some (possibly none) of the trailing characters of $S$. For example, the prefixes of $acb$ are the empty string, $a$, $ac$, and $acb$.

A string $S$ has “nice prefixes” if for every prefix $P$ of $S$ and for every two characters $k1$ and $k2$ in the alphabet, $|\mathrm{count}(P, k1) - \mathrm{count}(P, k2)| <= 2$. For example, $bbcac$ has nice prefixes, but $abbbc$ does not because $\mathrm{count}(abbb, b) = 3$ and $count(abbb, c) = 0$.

Count the number of strings of length $L$ on an alphabet of size $K$ that have nice prefixes. This number can be large, so print its remainder when divided by 1000000007.

## Input

The input is a single line containing the two integers $L$ and $K$, separated by spaces, with $1 \leq L \leq 10^{18}$ and $1 \leq K \leq 50$.

## Output

Output a single line containing the number of strings of length $L$ on an alphabet of size $K$ that have nice prefixes, modulo 1000000007.

Sample Input 1 Sample Output 1
4 2

12

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 8.3hard
Statistics Show