Nice Prefixes

2020年1月17日 1082点热度 0人点赞 0条评论

Nice Prefixes

时间: 1ms        内存:128M

描述:

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 count(S, k) to be the number of occurrences of the symbol k in S. For example, count(bbcac, b) = 2 and 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, |count(P, k1) - count(P, k2)| <= 2. For example, bbcac has nice prefixes, but abbbc does not because 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.

输入:

The input is a single line containing the two integers L and K, separated by spaces, with 1 <= L <= 1018 and 1 <= K <= 50.

输出:

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

示例输入:

4 2

示例输出:

12

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论