← 返回题目列表

AtCoder · pakencamp_2024_day1_n

N. 去学校

中文机器翻译题面 查看原题

配点 : 600 点

問題文

素数 P 和正整数 给出了 H,W 。存在以下问题 请求解 K=1,2,\ldots ,W 。

巴肯王国的形状像棋盘,从南方开始。 编号为 0,1, \ldots H 并编号 H+1 东西向和自西向西的道路 0,1, \ldots W 并编号 W+1 有一条南北走向的路。

以降、 i 东西向主干道 j 南北主干道交叉口处 写为 (i,j) 。

荧光笔你的房子是 位于 (0,0) 学校位于 (H,W) 的东部或北部 1 我反复向前走一个街区去上学。你不能向南或向西。

不过,因为阳光明媚, K 你不能连续向东走超过一个街区。

查找满足条件的学校路线数量。然而,答案可能非常大。 请打印除以 P 后的余数。

制約

  • 1 \leq H,W \leq 10^{6}
  • 10^{8} \leq P \leq 10^{9}
  • P 是质数
  • 所有输入均为整数 仅当

小課題

  1. ( 200 点 ) H,W \leq 2000
  2. ( 400 点)没有额外的限制。 打印

入力

输入将以以下形式从标准输入给出。

H W P

出力

W 行。 i 在线 有关第 K=i 的答案。


入力例 1

8 5 998244353

出力例 1

126
882
1206
1278
1287

入力例 2

289 17 998244353

出力例 2

185944034
575259088
157522078
750432611
294726854
977803727
513648158
653193164
809039201
300639291
136301002
621883169
824367261
6666205
18818655
18902465
18902755