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<cstdio>
#include<cstring>
typedef long long LL;
const int N=2;
const int M=1e6+50;
const int mod=998244353;
struct mat{
    LL c[N][N];
    void clear(){memset(c,0,sizeof(c));}
}a,t;
mat operator * (mat a,mat b){
    mat c;c.clear();
    for(int k=0;k<N;++k)
    for(int i=0;i<N;++i)
    for(int j=0;j<N;++j)
    if(a.c[i][k]&&b.c[k][j])
    c.c[i][j]=(c.c[i][j]+1ll*a.c[i][k]*b.c[k][j]%mod)%mod;
    return c;
}
int get(long long v){
	a.c[0][0]=t.c[0][0]=t.c[0][1]=t.c[1][0]=1;
    while(v){
        if(v&1)a=a*t;
        t=t*t;v>>=1; 
    }
    return a.c[0][1];
}
int n,Ans_1,Ans_2,f[M],g[M],inv[M];
LL m;
int main(){
    scanf("%d%lld",&n,&m);
    Ans_1=get(m+2*(n-1));
	m%=mod;f[1]=g[1]=inv[1]=Ans_2=1;
	for(int i=2;i<=n;i++){
    	f[i]=(f[i-1]+f[i-2])%mod;
		g[i]=1ll*g[i-1]*m%mod;
		inv[i]=(mod-1ll*(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=n+1;i<=2*n;i++)
	f[i]=(f[i-1]+f[i-2])%mod;
	for(int i=2;i<n;i++){
		Ans_1=(Ans_1-1ll*Ans_2*f[2*n+2-i*2]%mod+mod)%mod;
		Ans_2=1ll*Ans_2*m%mod*inv[i-1]%mod;
		m++;
	}
	if(n!=1)Ans_1=(Ans_1-Ans_2+mod)%mod;
	printf("%d\n",Ans_1);
}