若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1221: Nice Prefixes

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,106

题目描述

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

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist