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;
#define int long long
const int MOD=998244353;

vector<vector<int>> q(2),w(2),tmp(2);

int mi[28]={1,1,2,3,5,8,13,1,2,4,7,12,20,33,1,3,7,14,26,46,79,1,4,11,25,51,97,176};
int b[223456],nCkm[223456];//nCkm[i]:nCk(i+m-1,i-1)
void mul(vector<vector<int>> &s,vector<vector<int>> t){
  tmp[0][0]=s[0][0]*t[0][0]+s[0][1]*t[1][0];
  tmp[0][1]=s[0][0]*t[0][1]+s[0][1]*t[1][1];
  tmp[1][0]=s[1][0]*t[0][0]+s[1][1]*t[1][0];
  tmp[1][1]=s[1][0]*t[0][1]+s[1][1]*t[1][1];
  for(int i=0;i<2;i++)for(int j=0;j<2;j++)s[i][j]=tmp[i][j]%MOD;
}
int pw(int n,int k){
  if(k<0)return pw(n,k+MOD-1);
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}
int fi(int a){
  q[0][0]=1,q[0][1]=1,q[1][0]=1,q[1][1]=0;
  w[0][0]=1,w[0][1]=w[1][0]=0,w[1][1]=1;
  while(a){
    if(a&1)mul(w,q);
    mul(q,q);
    a>>=1;
  }
  return w[1][0];
}
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  for(int i=0;i<2;i++){
    q[i].resize(2);
    w[i].resize(2);
    tmp[i].resize(2);
  }
  int n,m;cin>>n>>m;n--;
  nCkm[1]=1;
  for(int i=2;i<=n;i++)nCkm[i]=((nCkm[i-1]*((i+m-1)%MOD))%MOD*pw(i-1,MOD-2))%MOD;
  if(n<4&&m<8)fin(mi[n*7+m-1]);
  b[0]=MOD-1,b[1]=MOD-2;
  for(int i=2;i<223456;i++)b[i]=(3*b[i-1]-b[i-2]+MOD)%MOD;
  int ans=0;
  for(int i=1;i<=n;i++)ans+=(nCkm[i]*b[n-i])%MOD,ans%=MOD;
  ans+=(fi(m+1)*(2*b[n]-b[n+1]+MOD)+fi(m)*(-3*b[n]+b[n+1]+3*MOD))%MOD,ans%=MOD;
  cout<<ans<<endl;
}
