AT_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}$ 的值。 由于答案可能非常大，请输出 $d_{n, m}$ 除以 $998,244,353$ 的余数。 你能解决这个问题吗？ 出题人：square1001

输入从标准输入按以下格式给出。 > $n\quad m$ - 第 1 行包含用空格分隔的两个整数 $n, m$。

- 输出 $d_{n, m}$ 除以 $998,244,353$ 的余数。

## 限制条件 - $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 分\] - 无额外限制 ## 样例解释 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$，这就是答案。 ## 样例解释 3 $d_{16, 30} = 1,193,004,294,685$，所以它除以 $998,244,353$ 的余数是 $102,292,850$。 由 ChatGPT 4.1 翻译