Nice Prefixes

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

For a string $S$, let $\mathrm{count}(S, k)$ be the number of times the symbol $k$ occurs 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 by deleting zero or more 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 every two alphabet symbols $k_1$ and $k_2$, $|\mathrm{count}(P, k_1) - \mathrm{count}(P, k_2)| \le 2$. For example, $bbcac$ has nice prefixes, but $abbbc$ does not, because $\mathrm{count}(abbb, b) = 3$ and $\mathrm{count}(abbb, c) = 0$.

Count the number of strings of length $L$ over an alphabet of size $K$ that have nice prefixes. This number can be large, so print it modulo $1000000007$.

A single line with two integers $L$ and $K$ separated by a space, where $1 \le L \le 10^{18}$ and $1 \le K \le 50$.

Print a single line with the number of length-$L$ strings over an alphabet of size $K$ that have nice prefixes, taken modulo $1000000007$.