AT_s8pc_3_g フィボナッチ数の総和

[problemUrl]: https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_g 次のような数列があります。 - $ a_1=a_2=1 $, $ a_{k+2}=a_{k+1}+a_k\ (k\ \ge\ 1) $ E869120は, この数列を使って次のように数列 $ d_1,\ d_2,\ d_3,\ \dots\ ,\ d_n $ を定義することにしました。 - $ d_{1,\ j}\ =\ a_j $ - $ d_{i,\ j}\ =\ \sum_{k\ =\ 1}^j\ d_{i\ -\ 1,\ k}\ (i\ \ge\ 2) $ 整数 $ n,\ m $ が与えられます。そのとき, $ d_{n,\ m} $ の値を求めてください。 ただし, 答えが非常に大きくなることがあるので, $ 998,244,353 $ で割った余りを求めてください。 あなたはこの問題が解けますか??? 問題文担当者：square1001

N/A

N/A

### 制約 - $ 1\ \le\ n\ \le\ 200,000 $ - $ 1\ \le\ m\ \le\ 10^{18} $ ### 小課題 小課題1 \[ $ 100 $ 点 \] - $ 1\ \le\ n,\ m\ \le\ 3,000 $ を満たす。 小課題2 \[ $ 170 $ 点 \] - $ 1\ \le\ m\ \le\ 200,000 $ を満たす。 小課題3 \[ $ 230 $ 点 \] - $ 1\ \le\ n\ \le\ 3 $ を満たす。 小課題4 \[ $ 420 $ 点 \] - $ 1\ \le\ n\ \le\ 1000 $ を満たす。 小課題5 \[ $ 480 $ 点 \] - 追加の制約はない。 ### Sample Explanation 1 以下のような数列になっています。 $ d_{i,\ 1} $ $ d_{i,\ 2} $ $ d_{i,\ 3} $ $ d_{i,\ 4} $ $ d_{i,\ 5} $ $ d_{i,\ 6} $ $ d_{i,\ 7} $ $ d_1 $ 1 1 2 3 5 8 13 $ d_2 $ 1 2 4 7 12 20 33 $ d_3 $ 1 3 7 14 26 46 79 $ d_4 $ 1 4 11 25 51 97 176 よって, $ d_{4,\ 7}\ =\ 176 $ となり, これが答えとなります。 ### Sample Explanation 3 $ d_{16,\ 30}\ =\ 1,193,004,294,685 $ なので, これを $ 998,244,353 $ で割った余りは $ 102,292,850 $ です。