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 <set>
#include <map>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define REP(i, x, y) for(int i = (int)x; i <= (int)y; i ++)
#define FOR(i, x, y) for(int i = (int)x; i <  (int)y; i ++)
#define PER(i, x, y) for(int i = (int)x; i >= (int)y; i --)
#define trace(x) cerr << #x << " " << x << endl;
#define dprintf(...) fprintf(stderr, __VA__ARGS__)
#define dln()        fprintf(stderr, "\n")
using namespace std;
typedef long long LL;
typedef long double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
const	int N = 200005;
const	int P = 998244353;
const	int inf = 1e9;
const	LL Inf = 1e15;

inline int IN(){
	char ch = getchar(); int x = 0, f = 0;
	while(ch < '0' || ch > '9') ch = getchar(), f = (ch == '-');
	while(ch >= '0' && ch <= '9'){
		x = (x << 1) + (x << 3) + ch - 48;
		ch = getchar();
	}
	return f ? (-x) : x;
}

inline int Pow(int x, int y, int p){
	int an = 1;
	for(; y; y >>= 1, x = (LL)x * x % p) if(y & 1) an = (LL)an * x % p;
	return an;
}

void renew(int &x, int y){
	x += y;
	if(x < 0) x += P;
	else if(x >= P) x -= P;
}

template<typename T> inline void chkmin(T &a, const T &b) {if(a > b) a = b;}
template<typename T> inline void chkmax(T &a, const T &b) {if(a < b) a = b;}

int n;
LL m;

struct mat{
	int v[2][2];
	void EE(){
		v[1][0] = v[0][1] = 0;
		v[0][0] = v[1][1] = 1;
	}
}c, e, ans;

mat operator *(const mat &a, const mat &b){
	REP(i, 0, 1) REP(j, 0, 1){
		c.v[i][j] = 0;
		REP(k, 0, 1) c.v[i][j] = (c.v[i][j] + (LL)a.v[i][k] * b.v[k][j]) % P;
	}
	return c;
}

int Fib(LL x){
	ans.EE();
	e.v[0][0] = 1;
	e.v[0][1] = 1;
	e.v[1][0] = 1;
	e.v[1][1] = 0;
	for(; x; x >>= 1){
		if(x & 1) ans = ans * e;
		e = e * e;
	}
	return ans.v[0][0];
}

struct vec3{
	int x, y, z;
	vec3(int xx = 0, int yy = 0, int zz = 0) : x(xx), y(yy), z(zz) {}
	vec3 operator +(const vec3 &a)const{
		return vec3((x + a.x) % P, (y + a.y) % P, (z + a.z) % P);
	}
	vec3 operator -(const vec3 &a)const{
		return vec3((x + P - a.x) % P, (y + P - a.y) % P, (z + P - a.z) % P);
	}
	vec3 operator *(const vec3 &a)const{
		int xx = (LL)((((LL)z * a.y - (LL)y * a.z) % P + P) % P) * Pow((((LL)x * a.y - (LL)y * a.x) % P + P) % P, P - 2, P) % P;
		xx = (P - xx) % P;
		int yy = (LL)(0LL + P - z - (LL)x * xx % P + P) % P * Pow(y, P - 2, P) % P;
		return vec3(xx, yy, 1);
	}
	int operator ^(const vec3 &a)const{
		return ((LL)x * a.x + (LL)y * a.y + (LL)z * a.z) % P;
	}
}w[N], eA, eB, xAB;
int Cx[N];//(-1) ^ i * C(n - 1, i)
int ww[N];

int main(){
	cin >> n >> m;
	if(m == 1){
		printf("%d\n", 1);
		return 0;
	}
	if(n == 1){
		printf("%d\n", Fib(m - 1));
		return 0;
	}
	m --;
	Cx[0] = 1;
	REP(i, 1, n - 1) Cx[i] = (LL)Cx[i - 1] * ((n - 1) - i + 1) % P * Pow(i, P - 2, P) % P;
	REP(i, 0, n) if(!(i & 1)) Cx[i] = (P - Cx[i]) % P;
	REP(i, 0, n - 2){
		if(i == 0){
			w[i] = vec3(P - 1, 0, 1);			
		}else
		if(i == 1){
			w[i] = w[0] + vec3(Cx[i], Cx[i - 1], 0);
		}else{
			w[i] = w[i - 1] + w[i - 2] + vec3(Cx[i], Cx[i - 1], 0);
		}
	}
	eA = vec3(0, 0, 0);
	if(n >= 3) eA = eA - w[n - 3];
	eA = eA - w[n - 2] + vec3(P - Cx[n - 1], P - Cx[n - 2], 0);
	eB = vec3(0, 0, 0) - w[n - 2] + vec3(0, P - Cx[n - 1], 0);
	xAB = eA * eB;
	REP(i, 0, n - 2) ww[i] = w[i] ^ xAB;
	int ans = ((LL)xAB.x * Fib(m) + (LL)xAB.y * Fib(m - 1)) % P;
	int outer = 1, tms = 0, gm = (m + n - 2) % P;
	FOR(i, 0, n - 2){
		if(gm == 0) tms ++;
		else outer = (LL)outer * gm % P;
		gm --;
		if(gm < 0) gm += P;
	}
	REP(i, 1, n - 2) outer = (LL)outer * Pow(i, P - 2, P) % P;
	int am = (m + n - 2) % P;
	int bm = m % P;
	REP(i, 0, n - 2){
		if(i > m) break;
		if(!tms) ans = (ans + (LL)outer * ww[i]) % P;
		if(!am){
			tms --;
		}else{
			outer = (LL)outer * Pow(am, P - 2, P) % P;
		}
		if(!bm){
			tms ++;
		}else{
			outer = (LL)outer * bm % P;
		}
		am --; bm --;
		if(am < 0) am += P;
		if(bm < 0) bm += P;
	}
	printf("%d\n", ans);
	return 0;
}



















