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>

using namespace std;

typedef long long LL;

struct mat {
	LL a[2][2];
	mat() {memset(a, 0, sizeof a);}
};

const LL mod = 998244353;
LL c[1005000], f[1005000];
LL n, m;

mat operator * (mat a, mat b) {
	mat c;
	for(int i = 0; i <= 1; ++ i) for(int j = 0; j <= 1; ++ j) for(int k = 0; k <= 1; ++ k) (c.a[i][j] += a.a[i][k] * b.a[k][j] % mod) %= mod;
	return c;
}

mat ksm(mat a, LL b) {
	mat ans;
	ans.a[0][0] = 0; ans.a[0][1] = 0;
	ans.a[1][0] = 1; ans.a[1][1] = 1;
	if(b < 0) return ans;
	while(b) {
		if(b & 1) ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}

LL ksm(LL a, LL b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}

int main() {
	scanf("%lld%lld", &n, &m);
	mat fib;
	fib.a[1][0] = 1, fib.a[1][1] = 1, fib.a[0][0] = 0, fib.a[0][1] = 1;
	fib = ksm(fib, m + 2 * (n - 1) - 2);
	LL ans = fib.a[1][1];
	f[1] = 1, f[2] = 1;
	for(int i = 3; i <= (n << 1) + 10; ++ i) f[i] = (f[i - 1] + f[i - 2]) % mod;
	c[0] = 1; for(int i = 1; i <= n; ++ i) c[i] = c[i - 1] * ((m - 1 + i) % mod) % mod * ksm(i, mod - 2) % mod;
	for(int i = 1; i < n; ++ i) ans = (ans - f[i << 1] * c[n - i - 1] % mod) % mod;
	printf("%lld\n", (ans + mod) % mod);
} 