Nice Prefixes

<p> Consider strings formed from characters from an alphabet of size <i>K</i>. For example, if <i>K = 4</i>, our alphabet might be <i>{a,b,c,d}</i>, and an example string is <i>bbcac</i>. </p> <p> For a string <i>S</i>, define <i>count(S, k)</i> to be the number of occurrences of the symbol <i>k</i> in <i>S</i>. For example, <i>count(bbcac, b) = 2</i> and <i>count(bbcac, a) = 1</i>. </p> <p> A prefix of a string <i>S</i> is any string obtained from <i>S</i> by deleting some (possibly none) of the trailing characters of <i>S</i>. For example, the prefixes of <i>acb</i> are the empty string, <i>a</i>, <i>ac</i>, and <i>acb</i>. </p> <p> A string <i>S</i> has "nice prefixes" if for every prefix <i>P</i> of <i>S</i> and for every two characters <i>k1</i> and <i>k2</i> in the alphabet, <i>|count(P, k1) - count(P, k2)| &lt;= 2</i>. For example, <i>bbcac</i> has nice prefixes, but <i>abbbc</i> does not because <i>count(abbb, b) = 3</i> and <i>count(abbb, c) = 0</i>. </p> <p> Count the number of strings of length <i>L</i> on an alphabet of size <i>K</i> that have nice prefixes. This number can be large, so print its remainder when divided by 1000000007. </p>

<p> The input is a single line containing the two integers <i>L</i> and <i>K</i>, separated by spaces, with 1 &lt;= <i>L</i> &lt;= 10¹⁸ and 1 &lt;= <i>K</i> &lt;= 50. </p>

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