题目描述

次のような数列があります。

• $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\ \quad\ m$

• 1行目には, 整数 $n,\ m$ が空白区切りで与えられる。

输出格式

• $d_{n,\ m}$ を $998,244,353$ で割った余りを求めなさい。

题目大意

意思就是输入两个数n和m
创造一个二维矩阵d[][] (这个矩阵可能很大)

第一行是斐波那契数列

1 1 2 3 5 8 13....

第n行的d[j][i]，加上d[j-1][i+1]得d[j][i+1] (每行首个数都为1)
样例1:
输入:

4 7

输出:

176

二维矩阵:

1 1 2 3 5 8 13...
1 2 4 7 12 20 33...//1+1=2,2+2=4,4+3=7,7+5=12...
1 3 7 14 26 46 79...//1+2=3,3+4=7,7+7=14,14+12=26...
1 4 11 25 51 97 [176](d[4][7])...
.....
.....

因为数可能很大 所以 要求输出d[n][m]上的数mod 998,244,353

$n\le2\times10^5,m\le10^{18}。$

感谢@ВОЛШЕБНИК 提供的翻译

4 7

176

12 20

174174144

16 30

102292850

提示

制約

• $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$ です。