좋은 접두사

크기가 $K$인 알파벳으로 이루어진 문자열을 생각하자. 예를 들어 $K = 4$이면 알파벳은 $\{a, b, c, d\}$일 수 있고, 그런 문자열의 예로 $bbcac$가 있다.

문자열 $S$에 대해 $\mathrm{count}(S, k)$를 $S$에서 기호 $k$가 나타나는 횟수라고 정의한다. 예를 들어 $\mathrm{count}(bbcac, b) = 2$이고 $\mathrm{count}(bbcac, a) = 1$이다.

문자열 $S$의 접두사는 $S$의 뒤쪽 문자들을 $0$개 이상 지워서 얻는 문자열이다. 예를 들어 $acb$의 접두사는 빈 문자열, $a$, $ac$, $acb$이다.

문자열 $S$가 좋은 접두사를 가진다는 것은, $S$의 모든 접두사 $P$와 알파벳의 임의의 두 기호 $k_1$, $k_2$에 대해 $|\mathrm{count}(P, k_1) - \mathrm{count}(P, k_2)| \le 2$가 성립함을 뜻한다. 예를 들어 $bbcac$는 좋은 접두사를 가지지만, $abbbc$는 그렇지 않다. $\mathrm{count}(abbb, b) = 3$이고 $\mathrm{count}(abbb, c) = 0$이기 때문이다.

크기가 $K$인 알파벳 위에서 길이가 $L$이며 좋은 접두사를 가지는 문자열의 개수를 구하여라. 이 수가 클 수 있으므로 $1000000007$로 나눈 나머지를 출력한다.

한 줄에 두 정수 $L$과 $K$가 공백으로 구분되어 주어진다. $1 \le L \le 10^{18}$, $1 \le K \le 50$이다.

크기가 $K$인 알파벳 위에서 길이가 $L$이며 좋은 접두사를 가지는 문자열의 개수를 $1000000007$로 나눈 나머지를 한 줄에 출력한다.