Problem Description

There is a sequence defined as follows:

• $ a_1=a_2=1 $, $a_{k+2}=a_{k+1}+a_k\ (k\ \ge\ 1)$

E869120 decided to define a sequence $d_1,\ d_2,\ d_3,\ \dots\ ,\ d_n$ using this sequence as follows:
- $d_{1,\ j}\ =\ a_j$
- $d_{i,\ j}\ =\ \sum_{k\ =\ 1}^j\ d_{i\ -\ 1,\ k}\ (i\ \ge\ 2)$

Given integers $n,\ m$, find the value of $d_{n,\ m}$. Since the answer can be very large, find it modulo $ 998,244,353 $.

Can you solve this problem???
Problem author: square1001

Input Format

The input is given from the standard input in the following format:

$n\ \quad\ m$

• The first line contains two integers $n,\ m$ separated by a space.

Output Format

• Find $d_{n,\ m}$ modulo $ 998,244,353 $.

Sample Input and Output

Sample Input #1

4 7

Sample Output #1

176

Sample Input #2

12 20

Sample Output #2

174174144

Sample Input #3

16 30

Sample Output #3

102292850

Notes/Hints

Constraints

• $1\ \le\ n\ \le\ 200,000$
• $1\ \le\ m\ \le\ 10^{18}$

Subtasks

Subtask 1 \[ $ 100 $ points \]

• $1\ \le\ n,\ m\ \le\ 3,000$

Subtask 2 \[ $ 170 $ points \]
- $1\ \le\ m\ \le\ 200,000$

Subtask 3 \[ $ 230 $ points \]
- $1\ \le\ n\ \le\ 3$

Subtask 4 \[ $ 420 $ points \]
- $1\ \le\ n\ \le\ 1000$

Subtask 5 \[ $ 480 $ points \]
- No additional constraints.

Sample Explanation 1

The sequence is as follows:

$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

Thus, $d_{4,\ 7}\ =\ 176$, which is the answer.

Sample Explanation 3

Since $d_{16,\ 30}\ =\ 1,193,004,294,685$, the remainder when divided by $ 998,244,353 $ is $ 102,292,850 $.

见题面 Input 部分

见题面 Output 部分