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 翻译