#P18541. Periodic Sequence

Periodic Sequence

Periodic Sequence

这是关于小青鱼的朋友 Kevin 的另一个故事。

Kevin 是国际凸多边形竞赛(ICPC,International Convex Polygon Championship)的总裁判长。他提出了一道几何题,却因缺乏计算几何经验,无法为测试数据生成正确的凸多边形,于是转而研究字符串问题。

本题中的字符串均由小写英文字母组成。对于字符串 S=S0S1…S∣S∣−1S=S_0S_1\ldots S_{|S|-1},∣S∣|S| 表示长度,SiS_i 表示第 i+1i+1 个字符。例如,字符串 xiaoqingyu 的长度为 1010,并且 S0=xS_0=\texttt{x}、S1=iS_1=\texttt{i}、S9=uS_9=\texttt{u}。

若对所有 0≤i<∣S∣0\le i<|S| 都有

Si=Ti mod ∣T∣,S_i=T_{i\bmod |T|},

则称字符串 TT 是字符串 SS 的一个周期。例如,ccpc 是 ccpcccpc 和 ccpccc 的周期,而 cpc 不是 ccpc 的周期。这里不要求 ∣T∣≤∣S∣|T|\le|S|,请直接依照上述定义判断。

Kevin 称字符串序列 [S1,S2,…,Sk][S_1,S_2,\ldots,S_k] 是周期序列,当且仅当:

  • 对任意 1≤i<j≤k1\le i<j\le k,均有 Si≠SjS_i\ne S_j;
  • 对任意 1≤i<k1\le i<k,SiS_i 是 Si+1S_{i+1} 的周期。

给定整数 nn,考虑所有满足每个字符串长度不超过 nn 的周期序列。设其中最长序列的长度为 f(n)f(n)。

小青鱼认为只计算一个 f(n)f(n) 太简单了,因此他想知道 f(1),f(2),…,f(N)f(1),f(2),\ldots,f(N)。答案可能很大,请对输入中给定的素数 MM 取模。

输入格式

一行包含两个整数 N,MN,M,满足:

  • 1≤N≤2×1051\le N\le2\times10^5;
  • 5×108≤M≤1.01×1095\times10^8\le M\le1.01\times10^9;
  • 保证 MM 是素数。

输出格式

输出一行 NN 个整数,依次为 f(1),f(2),…,f(N)f(1),f(2),\ldots,f(N) 对 MM 取模后的结果。

样例

输入:

5 1000000007

输出:

1 3 6 11 19

样例说明

有 f(1)=1f(1)=1、f(2)=3f(2)=3、f(3)=6f(3)=6。

  • n=1n=1 时,一个最长序列为 [a];
  • n=2n=2 时,一个最长序列为 [ab, a, aa];
  • n=3n=3 时,一个最长序列为 [abc, ab, aba, a, aaa, aa]。