#P18541. Periodic Sequence
Periodic Sequence
Periodic Sequence
这是关于小青鱼的朋友 Kevin 的另一个故事。
Kevin 是国际凸多边形竞赛(ICPC,International Convex Polygon Championship)的总裁判长。他提出了一道几何题,却因缺乏计算几何经验,无法为测试数据生成正确的凸多边形,于是转而研究字符串问题。
本题中的字符串均由小写英文字母组成。对于字符串 , 表示长度, 表示第 个字符。例如,字符串 xiaoqingyu 的长度为 ,并且 、、。
若对所有 都有
则称字符串 是字符串 的一个周期。例如,ccpc 是 ccpcccpc 和 ccpccc 的周期,而 cpc 不是 ccpc 的周期。这里不要求 ,请直接依照上述定义判断。
Kevin 称字符串序列 是周期序列,当且仅当:
- 对任意 ,均有 ;
- 对任意 , 是 的周期。
给定整数 ,考虑所有满足每个字符串长度不超过 的周期序列。设其中最长序列的长度为 。
小青鱼认为只计算一个 太简单了,因此他想知道 。答案可能很大,请对输入中给定的素数 取模。
输入格式
一行包含两个整数 ,满足:
- ;
- ;
- 保证 是素数。
输出格式
输出一行 个整数,依次为 对 取模后的结果。
样例
输入:
5 1000000007
输出:
1 3 6 11 19
样例说明
有 、、。
- 时,一个最长序列为
[a]; - 时,一个最长序列为
[ab, a, aa]; - 时,一个最长序列为
[abc, ab, aba, a, aaa, aa]。