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 <stdio.h>
#include <algorithm>
using namespace std;

const long long mod = 998244353;
long long inv[500500],fib[500500];

pair<long long, long long> ffib(long long n)
{
	if (n == 0) return {1,0};
	if (n % 2){
		auto p = ffib(n-1);
		return {p.second,(p.first+p.second)%mod};
	}
	auto p = ffib(n/2);
	return {(p.first*p.first+p.second*p.second)%mod, (2*p.first+p.second)*p.second%mod};
}

int main()
{
	inv[1] = 1; fib[1] = 1;
	for (int i=2;i<500500;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fib[i] = (fib[i-1] + fib[i-2]) % mod;
	}

	int N; long long M;
	scanf ("%d %lld",&N,&M);

	long long base = ffib(M+(N-1)*2).second;
	long long mul = 1;

	M %= mod;
	for (int i=1;i<N;i++){
		base = (base + mod - mul * fib[2*(N-i)] % mod) % mod;
		mul = mul * M % mod;
		mul = mul * inv[i] % mod;
		if (!mul) break;
		M = (M + 1) % mod;
	}
	printf ("%lld\n",base);

	return 0;
}