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 <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(998244353)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(10)
#define highest(x) (63 - __builtin_clzl(x))

template< typename Monoid >
struct SegmentTree
{
    using F = function< Monoid(Monoid, Monoid) >;
    
    int sz;
    vector< Monoid > seg;
    
    const F f;
    const Monoid M1;
    
    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1)
    {
        sz = 1;
        while(sz < n) sz <<= 1;
        seg.assign(2 * sz, M1);
    }
    
    void set(int k, const Monoid &x)
    {
        seg[k + sz] = x;
    }
    
    void build()
    {
        for(int k = sz - 1; k > 0; k--) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }
    
    void update(int k, const Monoid &x)
    {
        k += sz;
        seg[k] = x;
        while(k >>= 1) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }
    
    Monoid query(int a, int b)
    {
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if(a & 1) L = f(L, seg[a++]);
            if(b & 1) R = f(seg[--b], R);
        }
        return f(L, R);
    }
    
    Monoid operator[](const int &k) const
    {
        return seg[k + sz];
    }
};

const long MODULE = mod;

struct mod_matrix{
private:
    vector<vector<long>> array;
    
    void error_output(){
        if(MODULE == -1){
            cout << "ERROR : MODULE is undefined!" << endl;
            abort();
        }
    }
public:
    mod_matrix(size_t matrix_size) : array(matrix_size, vector<long>(matrix_size, 0)){ error_output(); };
    mod_matrix(vector<vector<long>> arr) : array(arr){ error_output(); };
    
    vector<long>& operator [](size_t index){
        return array[index];
    }
    
    mod_matrix operator *(mod_matrix another){
        mod_matrix ans(size());
        for(int i = 0; i < size(); i++){
            for(int j = 0; j < size(); j++){
                ans[i][j] = 0;
                for(int k = 0; k < size(); k++){
                    ans[i][j] += array[i][k] * another[k][j] % MODULE;
                }
            }
        }
        return ans;
    }
    
    mod_matrix power(long exponent){
        if(exponent % 2){
            return power(exponent - 1) * (*this);
        }else if(exponent){
            mod_matrix root_ans = power(exponent / 2);
            return root_ans * root_ans;
        }else{
            mod_matrix ans = mod_matrix(size());
            for(int i = 0; i < size(); i++){
                ans[i][i] = 1;
            }
            return ans;
        }
    }
    
    size_t size(){
        return array.size();
    }
    
    void output(){
        for(int i = 0; i < size(); i++){
            for(int j = 0; j < size(); j++){
                cout << array[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
};

long fibonatti(long index){
    return mod_matrix({{1, 1}, {1, 0}}).power(index)[1][0];
}

typedef __int128_t int128;

int main(){
    int n;
    long m;
    cin >> n >> m;
    long ans = fibonatti(2 * n + m - 2);
    long inv_fact = 1;
    SegmentTree< long > facts(n * 2 - 4, [](long a, long b){ return (a % mod) * (b % mod) % mod; }, 1);
    for(int i = 0; i < n * 2 - 4; i++){
        facts.set(i, 2 * n + m - 2 - (n * 2 - 4 - i));
    }
    facts.build();
    for(int i = 0; i < n - 1; i++){
        ans = (ans + mod - facts.query(n * 2 - 4 - i * 2, n * 2 - 4 - i) * power(inv_fact, mod - 2, mod) % mod) % mod;
        inv_fact = (inv_fact * (i + 1)) % mod;
    }
    cout << ans << endl;
}
