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;

long long int n, m, i, j, ans, ns, f1, f2, f3;
long long int mod = 998244353;
//long long int mod = 1000000000;
long long int fib[200008];

long long int modinv(long long int b, long long int nn){
    long long int ret = b % mod, mo = mod - 2;
    nn %= mod;
    while(mo){
        //cout << mo << " " << ret << " " << nn << endl;
        if(mo&1){
            ret = (ret * nn) % mod;
        }
        nn = (nn * nn) % mod;
        mo >>= 1;
    }
    return ret % mod;
}

struct matrix{
    long long int a[2][2];

    matrix operator *(matrix to){
        matrix ret;
        ret.a[0][0] = ((a[0][0] * to.a[0][0]) % mod + (a[0][1] * to.a[1][0]) % mod) % mod;
        ret.a[1][0] = ((a[1][0] * to.a[0][0]) % mod + (a[1][1] * to.a[1][0]) % mod) % mod;
        ret.a[0][1] = ((a[0][0] * to.a[0][1]) % mod + (a[0][1] * to.a[1][1]) % mod) % mod;
        ret.a[1][1] = ((a[1][0] * to.a[0][1]) % mod + (a[1][1] * to.a[1][1]) % mod) % mod;
        return ret;
    }
};

inline long long int fibmod(long long int mm){
    --mm;
    matrix ret, np;
    ret.a[0][0] = 1;
    ret.a[0][1] = 0;
    ret.a[1][0] = 0;
    ret.a[1][1] = 1;
    np.a[0][0] = 1;
    np.a[0][1] = 1;
    np.a[1][0] = 1;
    np.a[1][1] = 0;
    while(mm){
        if(mm&1){
            ret = ret * np;
        }
        np = np * np;
        mm >>= 1;
    }
    return ret.a[0][0];
}

template <typename T>
inline T binommod(T mm, T nn){
    T ret = 1;
    if(mm - nn < nn){nn = mm - nn;}
    for(j = 1; j <= nn; ++j){
        ret = (ret * modinv(mm - nn + j, j)) % mod;
    }
    return ret;
}

int main(){
    scanf("%lld%lld", &n, &m);
    fib[0] = 1;
    f1 = 1;
    f2 = 1;
    for(i = 1; i < n + 1; ++i){
        //fib[i] = (3 * fib[i - 1] - fib[i - 2] + mod) % mod;
        f3 = (f1 + f2) % mod;
        f1 = f2;
        f2 = f3;
        f3 = (f1 + f2) % mod;
        f1 = f2;
        f2 = f3;
        fib[i] = f3;
    }
    ans = 0;
    //cout << fib[99896] << " " << fib[99897] << " " << fib[99898] << endl;
    //cout << modinv(99999999999999999, 99999999999999999) << endl;
    ns = 1;
    for(i = n - 1; i >= 0; --i){
        //cout << ans << "\t";// << fib[i - 1] << " * " << ns << endl;
        ans = (ans + (ns * fib[i - 1]) % mod + mod) % mod;
        ns = ((ns * modinv(m + n - i - 1, n - i)) % mod + mod) % mod;
    }
    // << endl;
    cout << (fibmod(m + 2 * n - 2) - ans + mod) % mod << endl;
    return 0;
}
