E869120 defined a sequence $a$ like this:


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


He also defined sequences $d_1, d_2, d_3, \dots , d_n$, as the following recurrence relation :


* $d_{1, j} = a_j$
* $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$


You are given integers $n$ and $m$. Please calculate the value of $d_{n, m}$.
Since the answer can be large number, print the answer modulo $998,244,353$.
Can you solve this problem???

Input

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



> $n \quad m$

Output

* Print $d_{n, m}$ modulo $998,244,353$.



Constraints

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



Subtasks

Subtask 1 [ $100$ points ]


* The testcase in this subtask satisfies $1 \le n, m \le 3,000$.

Subtask 2 [ $170$ points ]


* The testcase in this subtask satisfies $1 \le m \le 200,000$.

Subtask 3 [ $230$ points ]


* The testcase in this subtask satisfies $1 \le n \le 3$.

Subtask 4 [ $420$ points ]


* The testcase in this subtask satisfies $1 \le n \le 1000$.

Subtask 5 [ $480$ points ]


* There are no additional constraints.

Output

* Print $d_{n, m}$ modulo $998,244,353$.



Constraints

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



Subtasks

Subtask 1 [ $100$ points ]


* The testcase in this subtask satisfies $1 \le n, m \le 3,000$.

Subtask 2 [ $170$ points ]


* The testcase in this subtask satisfies $1 \le m \le 200,000$.

Subtask 3 [ $230$ points ]


* The testcase in this subtask satisfies $1 \le n \le 3$.

Subtask 4 [ $420$ points ]


* The testcase in this subtask satisfies $1 \le n \le 1000$.

Subtask 5 [ $480$ points ]


* There are no additional constraints.

Input

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



> $n \quad m$

Examples

Input

4 7


Output

176


Input

12 20


Output

174174144


Input

16 30


Output

102292850
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 998244353;

struct Matrix{
    LL x[2][2];
    Matrix operator * (Matrix A){
        Matrix C;
        for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				LL &t = C.x[i][j];
				t = 0;
				for(int k=0; k<2; k++){
					t = t + x[i][k] * A.x[k][j] % mod;
				}
				t %= mod;
			}
        }
        return C;
    }
};

Matrix pow(Matrix A, LL p){
    Matrix S;
    for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			S.x[i][j] = i==j?1:0;
		}
    }
    while(p){
		if(p & 1)	S = S * A;
		A = A * A;
		p >>= 1;
    }
    return S;
}

LL Fab(LL p){
	if(p == 0){
		return 0;
	}
    if(p <= 2){
		return 1;
    }
    Matrix A;
    A.x[0][0] = A.x[0][1] = A.x[1][0] = 1;
    A.x[1][1] = 0;
    A = pow(A, p - 2);
    return (A.x[0][0] + A.x[1][0]) % mod;
}

LL rev(LL x){
    int p = mod - 2;
    LL s = 1;
    while(p){
		if(p & 1)	s = s * x % mod;
		x = x * x % mod;
		p >>= 1;
    }
    return s;
}

int n;
LL m;

int main(){
    while(~scanf("%d %lld", &n, &m)){
        LL sum = Fab(2 * (n - 1));
        int k = n - 2;
        LL g = 1;
        for(int i=1; i<=k; i++){
			g = (m + i - 1) % mod * g % mod * rev(i) % mod;
            sum = sum + g * Fab(2 * (k - i + 1)) % mod;
            sum = sum % mod;
        }
        sum = Fab(m + 2*(n - 1)) - sum;
        sum = (sum % mod + mod) % mod;
        printf("%lld\n", sum);
    }
	return 0;
}
