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>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<int MOD>
struct ModInt{
	int x;
	ModInt(): x(0){}
	ModInt(ll y){
		x=y%MOD;
		if(x<0) x+=MOD;
	}

	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=MOD-p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1ll*x*p.x%MOD);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inv();
		return *this;
	}

	ModInt operator-() const{ return ModInt(-x);}
	ModInt operator+(const ModInt &p) const{ return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p) const{ return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p) const{ return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p) const{ return ModInt(*this)/=p;}
	bool operator==(const ModInt &p) const{ return x==p.x;}
	bool operator!=(const ModInt &p) const{ return x!=p.x;}

	ModInt pow(ll n) const{
		ModInt ret(1), p(x);
		while(n){
			if(n&1) ret*=p;
			p*=p;
			n>>=1;
		}
		return ret;
	}
	ModInt inv() const{
		return pow(MOD-2);
	}
};
const int MOD=998244353;
using mint=ModInt<MOD>;
struct Qsqrt5{
	mint a, b;
	Qsqrt5(){}
	Qsqrt5(mint a, mint b):a(a), b(b){}
	Qsqrt5(mint a):a(a), b(0){}
	Qsqrt5 &operator+=(const Qsqrt5 &x){
		a+=x.a; b+=x.b;
		return *this;
	}
	Qsqrt5 &operator-=(const Qsqrt5 &x){
		a-=x.a; b-=x.b;
		return *this;
	}
	Qsqrt5 &operator*=(const Qsqrt5 &x){
		mint p=a*x.a+mint(5)*b*x.b;
		mint q=a*x.b+b*x.a;
		a=p, b=q;
		return *this;
	}
	Qsqrt5 &operator/=(const Qsqrt5 &x){
		*this*=x.inv();
		return *this;
	}
	Qsqrt5 operator-() const{ return Qsqrt5(-a, -b);};
	Qsqrt5 operator+(const Qsqrt5 &x) const{ return Qsqrt5(a, b)+=x;};
	Qsqrt5 operator-(const Qsqrt5 &x) const{ return Qsqrt5(a, b)-=x;};
	Qsqrt5 operator*(const Qsqrt5 &x) const{ return Qsqrt5(a, b)*=x;};
	Qsqrt5 operator/(const Qsqrt5 &x) const{ return Qsqrt5(a, b)/=x;};
	Qsqrt5 pow(ll n) const{
		Qsqrt5 ret(1), p(a, b);
		while(n){
			if(n&1) ret*=p;
			p*=p;
			n>>=1;
		}
		return ret;
	}
	Qsqrt5 inv() const{
		mint c=(a*a-mint(5)*b*b).inv();
		return Qsqrt5(a*c, -b*c);
	}
};
int main()
{
	int n; ll m;
	cin>>n>>m;
	Qsqrt5 x(mint((MOD+1)/2), mint((MOD+1)/2)), y(mint((MOD+1)/2), -mint((MOD+1)/2));
	Qsqrt5 x1=x*((Qsqrt5)(1)-x).inv(), y1=y*((Qsqrt5)(1)-y).inv();
	Qsqrt5 x1p[200020], y1p[200020];
	x1p[0]=Qsqrt5(1), y1p[0]=Qsqrt5(1);
	for(int i=1; i<n; i++){
		x1p[i]=x1p[i-1]*x1;
		y1p[i]=y1p[i-1]*y1;
	}
	Qsqrt5 ans=x.pow(m)*x1p[n-1]-y.pow(m)*y1p[n-1];
	if(!(n&1)) ans=-ans;
	mint c(1);
	for(int i=0; i<n-1; i++){
		Qsqrt5 add=(x1p[n-1-i]-y1p[n-1-i])*Qsqrt5(c);
		if((i+n)&1) ans-=add;
		else ans+=add;
		c*=mint(m+i);
		c/=mint(i+1);
	}
	ans/=Qsqrt5(0, 1);
	cout<<ans.a.x<<endl;
	return 0;
}