AT_pakencamp_2024_day1_n Go to School

素数 $ P $ および正整数 $ H,W $ が与えられます。以下の問題を $ K=1,2,\ldots ,W $ について解いてください。 > 碁盤の目状のパ研王国には南から順に $ 0,1, \ldots H $ と番号が付いた $ H+1 $ 本の東西方向の道路と、西から順に $ 0,1, \ldots W $ と番号が付いた $ W+1 $ 本の南北方向の道路があります。 > > 以降、 $ i $ 本目の東西方向の道路と $ j $ 本目の南北方向の道路の交わる交差点を $ (i,j) $ と表記します。 > > highlighter君の家は $ (0,0) $ にあり、 $ (H,W) $ にある学校まで東、または北に $ 1 $ 区画分進むことを繰り返して通学します。南や西に進むことはできません。 > > しかし、太陽が眩しいため、 $ K $ 区画分より多く連続して東に進むことはできません。 > > 条件を満たす通学路の個数を求めてください。ただし答えは非常に大きくなり得るので $ P $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ P $

$ W $ 行出力せよ。 $ i $ 行目には $ K=i $ の場合の答えを出力せよ。

### 小課題 1. ( $ 200 $ 点 ) $ H,W \leq 2000 $ 2. ( $ 400 $ 点 ) 追加の制約はない。 ### Constraints - $ 1 \leq H,W \leq 10^{6} $ - $ 10^{8} \leq P \leq 10^{9} $ - $ P $ は素数 - 入力は全て整数