#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;

#define vall(A) A.begin(), A.end()
template<typename T> inline void vin(vector<T>& A){for (int i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void vout(const vector<T>& A){for (int i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void vout2d(const vector<vector<T>>& A){for (int i = 0, H = A.size(); i < H; i++){vout(A[i]);}}
template<typename T> inline void adjvin(vector<T>& A){for (int i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void adjvout(const vector<T>& A){for (int i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void adjvout2d(const vector<vector<T>>& A){for (int i = 1, H = A.size(); i < H; i++){adjvout(A[i]);}}
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
template<typename T> void print(T object){cout << (object) << "\n";}
template<typename T, typename U> void print(T object1, U object2){cout << (object1) << " " << (object2) << "\n";}
template<typename T, typename U, typename V> void print(T object1, U object2, V object3){cout << (object1) << " " << (object2) << " " << (object3) << "\n";}
template<typename T, typename U, typename V, typename W> void print(T object1, U object2, V object3, W object4){cout << (object1) << " " << (object2) << " " << (object3) << " " << (object4) << "\n";}
const vector<ull> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904, 9223372036854775808ull};
const vector<ull> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000, 10000000000000000000ull};
const vector<ll> di{0,1,0,-1};
const vector<ll> di8{0,1,1,1,0,-1,-1,-1};
const vector<ll> dj{1,0,-1,0};
const vector<ll> dj8{1,1,0,-1,-1,-1,0,1};



namespace a1073741824{

//library
namespace math{

//math.hpp
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, const ll m){
    ll t = a%m;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a 
/// @param n
/// @param m 
/// @return a^n
ll powll(ll a, ll n){
    ll r = 1;
    for (int i = 1; i <= n; i++){
        r *= a;
    }
    return r;
}

/// @brief floor(sqrt(N))を返す
ll isqrt(ll N){
    if (N){
        ll ok = 1;
        ll ng = min(N,2000000000LL);
        while (ng - ok >= 2){
            ll mid = (ok+ng)/2;
            if (mid*mid <= N){
                ok = mid;
            } 
            else{
                ng = mid;
            }
        }
        return ok;
    }
    else{return 0;}
}

/// @brief floor(log_a(L))を返す
/// @param a
/// @param L
ll ilog(ll a, ll L){
    __int128_t t = 1;
    ll ans = 0;
    while (t <= L){
        ans++;
        t *= a;
    }
    return ans-1;
}

/// @brief 正の整数Nを素因数分解する
/// @param N
/// @return vector<vector<ll> {{素因数1,個数}, {素因数2,個数}, {素因数3,個数}...}
vector<pll> p_fact(ll N){
    if (N == 1){
        return vector<pll> {{1,0}};
    }
    vector<pll> R;//戻り値用リスト

    const int M = isqrt(N);
    for (int i = 2; i <= M; i++){
        if (N % i == 0){
            ll divide_count = 0;
            while (N % i == 0){
                divide_count++;
                N /= i;
            }
            R.push_back({i,divide_count});
        }
    }
    if (N != 1){
        R.push_back({N,1});
    }
    return R;
}

/// @brief 素因数分解リストを受け取って約数関数の値を求める
template<typename T>
ll divisor_function(const vector<array<T,2>>& vv, ll K){
    if (vv[0][0] == 1){
        return 1;
    }
    ll R = 1;
    if (K == 0){
        for (auto x : vv){
            R *= x[1]+1;
        }
    }
    else{
        for (auto x : vv){
            ll r = powll(x[0],K);
            R *= (powll(r,x[1]+1) - 1)/(r - 1);
        }
    }
    return R;
}

/// @brief 素因数分解の結果pを受け取って、約数リストを生成する。
template<typename T>
vector<T> enumerate_divisor(const vector<array<T,2>>& p){
    vector<T> d{1};
    if (p[0][0] == 1){
        return d;
    }
    for (auto &v : p){
        int t = d.size();
        ll temp = 1;
        for (int w = 0; w < v[1]; w++){
            temp *= v[0];
            for (int i = 0; i < t; i++){
                d.push_back(d[i]*temp);
            }
        }
    }
    sort(vall(d));
    return d;
}

/// @brief 有理数のfloorを求める
/// @param y
/// @param x 
/// @return floor(y/x)
inline ll floor2(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        return y/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -((y+x-1)/x);
    }
    else{
        return y/x;
    }
}
/// @brief 有理数のceilを求める
/// @param y 
/// @param x 
/// @return 
inline ll ceil2(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        return (y+x-1)/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -(y/x);
    }
    else{
        return y/x;
    }
}

/// @brief 線形篩
/// @attention コンストラクタに整数Nを渡すことでN以下の整数を扱うことができる。
struct LinearSieve{
    vector<int> p_list;
    vector<int> lpf;
    //Nを渡すことで1以上N以下の整数を扱うことができる
    LinearSieve(int N): lpf(N+1,-1){
        lpf[1] = 1;
        int p_list_size = 0;
        for (int i = 2; i <= N; i++){
            if (lpf[i] < 0){
                p_list.push_back(i);
                p_list_size++;
                lpf[i] = i;
            }
            for (int j = 0; j < p_list_size && p_list[j] <= lpf[i] && p_list[j]*i <= N; j++){
                lpf[p_list[j]*i] = p_list[j];
            }
        }
    }
    vector<pii> p_fact(int x){
        if (x == 1){return {{1,0}};}
        vector<pii> r;
        do{
            if (r.empty() || lpf[x] != r.back()[0]){
                r.push_back({lpf[x], 1});
            }
            else{
                r.back()[1]++;
            }
            x /= lpf[x];
        }while(x > 1);
        return r;
    }
    vector<vector<pii>> p_fact_all(int N){
        vector<vector<pii>> r(N+1);
        r[1].push_back({1,0});
        for (int i = 2; i <= N; i++){
            r[i] = p_fact(i);
        }
        return r;
    }
};

/// @brief 一次不定方程式ax+by=1の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(x,y)}
template<typename T>
array<T,3> axby1(T a, T b){
    T x = 1, y = 0;
    T z = 0, w = 1;
    T tmp;
    while (b){
        T p = a/b, q = a%b;
        tmp = x - y * p; x = y; y = tmp;
        tmp = z - w * p; z = w; w = tmp;
        a = b; b = q;
    }
    return {x, z, a};
}

/// @brief 1/a mod Mを求める
/// @param a 
/// @param M 
/// @return 1/a mod M
template<typename T, typename U>
T inverse_mod(T a, U M){
    auto temp = axby1(a,(T)M);
    assert(temp[2] == 1);
    return (M+temp[0])%M;
}

/// @brief modint
template<const int M>
struct mint{
    int val = 0;
    mint(const ll x){
        val = x%M;
    }
    mint(const mint &m){
        val = m.val;
    }
    mint(){}

    mint inv(){
        val = math::inverse_mod(val, M);
        return *this;
    }
    mint pow(ll N){
        val = math::modpow(val, N, M);
        return *this;
    }
    

    // 入出力用オーバーロード
    friend std::ostream& operator<<(std::ostream& os, const mint m){
        return os << m.val;
    }
    friend std::istream& operator>>(std::istream& is, mint &m){
        ll a;
        is >> a;
        m = a;
        return is;
    }


    void operator=(const ll x){
        val = x%M;
    }
    void operator=(const mint &a){
        val = a.val;
    }
    
    bool operator==(const ll x) const{
        return val == x;
    }
    bool operator==(const mint &a) const{
        return val == a.val;
    }
    bool operator!=(const ll x) const{
        return val != x;
    }
    bool operator!=(const mint &a) const{
        return val != a.val;
    }

    mint operator+(){
        return *this;
    }
    mint operator-(){
        if (val != 0) val = M-val;
        return *this;
    }

    mint operator+(const mint &a) const{
        return mint(val+a.val);
    }
    void operator+=(const mint &a){
        val += a.val;
        if (val >= M) val -= M;
    }
    mint operator+(const ll b) const{
        return mint(val+b%M);
    }
    void operator+=(const ll b){
        val += b%M;
        if (val >= M) val -= M;
    }

    mint operator-(const mint &a) const{
        return mint(M+val-a.val);
    }
    void operator-=(const mint &a){
        val += M-a.val;
        if (val >= M) val -= M;
    }
    mint operator-(const ll b) const{
        return mint(val+M-b%M);
    }
    void operator-=(const ll b){
        val += M-b%M;
        if (val >= M) val -= M;
    }

    mint operator*(const mint &a) const{
        return mint((ll)val*a.val);
    }
    void operator*=(const mint &a){
        val = ((ll)val*a.val)%M;
    }
    mint operator*(const ll b) const{
        return mint(val*(b%M));
    }
    void operator*=(const ll b){
        val = (val*(b%M))%M;
    }

    mint operator/(const mint &a) const{
        return mint((ll)val*inverse_mod(a.val,M));
    }
    void operator/=(const mint &a){
        val = ((ll)val*inverse_mod(a.val,M))%M;
    }
    mint operator/(const ll b) const{
        return mint(val*inverse_mod(b%M,M));
    }
    void operator/=(const ll b){
        val = (val*inverse_mod(b%M,M))%M;
    }
};
struct dynamic_mint{
    int val = 0;
    int M = -1;
    dynamic_mint(const ll x){
        val = x;
    }
    dynamic_mint(const ll x, const ll MOD){
        M = MOD;
        val = x%M;
    }
    dynamic_mint(const dynamic_mint &m){
        update_and_check_mod(m.M);
        val = m.val;
    }
    dynamic_mint(){}

    void update_and_check_mod(const int new_MOD){
        if (M == -1 && new_MOD == -1){
            //cerr << "M is invalid" << endl;
            //assert(false);
        }
        M = max(M, new_MOD);
    }

    dynamic_mint inv(){
        val = math::inverse_mod(val, M);
        return *this;
    }
    dynamic_mint pow(ll N){
        val = math::modpow(val, N, M);
        return *this;
    }
    

    // 入出力用オーバーロード
    friend std::ostream& operator<<(std::ostream& os, const dynamic_mint m){
        return os << m.val;
    }
    friend std::istream& operator>>(std::istream& is, dynamic_mint &m){
        ll a;
        is >> a;
        m = a;
        return is;
    }


    void operator=(const ll x){
        val = x;
    }
    void operator=(const dynamic_mint &a){
        update_and_check_mod(a.M);
        val = a.val;
    }
    
    bool operator==(const ll x) const{
        return val == x;
    }
    bool operator==(const dynamic_mint &a) const{
        return val == a.val;
    }
    bool operator!=(const ll x) const{
        return val != x;
    }
    bool operator!=(const dynamic_mint &a) const{
        return val != a.val;
    }

    dynamic_mint operator+(){
        return *this;
    }
    dynamic_mint operator-(){
        if (val != 0) val = M-val;
        return *this;
    }

    dynamic_mint operator+(const dynamic_mint &a){
        update_and_check_mod(a.M);
        return dynamic_mint(val+a.val, M);
    }
    void operator+=(const dynamic_mint &a){
        update_and_check_mod(a.M);
        val += a.val;
        if (val >= M) val -= M;
    }
    dynamic_mint operator+(const ll b){
        update_and_check_mod(-1);
        return dynamic_mint(val+b%M, M);
    }
    void operator+=(const ll b){
        update_and_check_mod(-1);
        val += b%M;
        if (val >= M) val -= M;
    }

    dynamic_mint operator-(const dynamic_mint &a){
        update_and_check_mod(a.M);
        return dynamic_mint(M+val-a.val, M);
    }
    void operator-=(const dynamic_mint &a){
        update_and_check_mod(a.M);
        val += M-a.val;
        if (val >= M) val -= M;
    }
    dynamic_mint operator-(const ll b){
        update_and_check_mod(-1);
        return dynamic_mint(val+M-b%M, M);
    }
    void operator-=(const ll b){
        update_and_check_mod(-1);
        val += M-b%M;
        if (val >= M) val -= M;
    }

    dynamic_mint operator*(const dynamic_mint &a){
        update_and_check_mod(a.M);
        return dynamic_mint((ll)val*a.val, M);
    }
    void operator*=(const dynamic_mint &a){
        update_and_check_mod(a.M);
        val = ((ll)val*a.val)%M;
    }
    dynamic_mint operator*(const ll b){
        update_and_check_mod(-1);
        return dynamic_mint(val*(b%M), M);
    }
    void operator*=(const ll b){
        update_and_check_mod(-1);
        val = (val*(b%M))%M;
    }

    dynamic_mint operator/(const dynamic_mint &a){
        update_and_check_mod(a.M);
        return dynamic_mint((ll)val*inverse_mod(a.val,M), M);
    }
    void operator/=(const dynamic_mint &a){
        update_and_check_mod(a.M);
        val = ((ll)val*inverse_mod(a.val,M))%M;
    }
    dynamic_mint operator/(const ll b){
        update_and_check_mod(-1);
        return dynamic_mint(val*inverse_mod(b%M,M), M);
    }
    void operator/=(const ll b){
        update_and_check_mod(-1);
        val = (val*inverse_mod(b%M,M))%M;
    }
};

//階乗前計算による二項係数mod998244353
struct factorialncr{
    vector<ll> factorialmod;
    vector<ll> factorialmodinv;
    ll N_MAX_N_MAX;
    ll MOD;
    factorialncr(const ll N_MAX, const ll M){
        N_MAX_N_MAX = max(1ll, N_MAX);
        MOD = M;
        factorialmod = vector<ll>(N_MAX+1);
        factorialmodinv = vector<ll>(N_MAX+1);
        factorialmod[0] = 1;
        factorialmod[1] = 1;
        factorialmodinv[0] = 1;
        factorialmodinv[1] = 1;

        for (int i = 2; i <= N_MAX; i++){
            factorialmod[i] = (i*factorialmod[i-1])%M;
            factorialmodinv[i] = (M-factorialmodinv[M%i]*(M/i)%M)%M;
        }
        for (int i = 1; i <= N_MAX; i++){
            factorialmodinv[i] = (factorialmodinv[i]*factorialmodinv[i-1])%M;
        }
    }

    ll nCr(ll n, ll r){
        if (r < 0 || n < r || n > N_MAX_N_MAX){
            return 0;
        }
        return factorialmod[n]*factorialmodinv[r]%MOD*factorialmodinv[n-r]%MOD;
    }
};

//表の前計算による二項係数modM
struct tablencr{
    vector<vector<ll>> ncrmodlist;
    ll N_MAX_N_MAX;
    public:
    tablencr(const ll N_MAX, const ll M){
        N_MAX_N_MAX = N_MAX;
        ncrmodlist = vector<vector<ll>> (N_MAX+1, vector<ll>(N_MAX+1,0));
        ncrmodlist[0][0] = 1;
        for (int i = 1; i <= N_MAX; i++){
            for (int j = 0; j <= i; j++){
                if (j == 0 || j == i){
                    ncrmodlist[i][j] = 1;
                }
                else{
                    ncrmodlist[i][j] = (ncrmodlist[i-1][j-1] + ncrmodlist[i-1][j])%M;
                }
            }
        }
    }
    ll nCr(ll n, ll r){
        if (r < 0 || n < r || n > N_MAX_N_MAX){
            return 0;
        }
        return ncrmodlist[n][r];
    }
};

//matrix.hpp
/// @brief 行列
/// @attention 行,列共に0-indexed
/// @attention コンストラクタにHとWを渡すと、[0][0]~[H-1][W-1]までできる。
/// @attention コンストラクタ1 matrix(N)...N次単位行列
/// @attention コンストラクタ2 matrix(h,w,v)...全成分がvの行列
/// @attention コンストラクタ3 matrix(vecvec)...2次元vectorで初期化
/// @tparam T 数を表す型
template<typename T>
struct matrix{
    vector<vector<T>> M;
    size_t H,W;

    /// @brief N次単位行列を生成
    /// @param N 
    matrix(size_t N){
        H = N;W = N;
        M = vector<vector<T>>(N,vector<T>(N,0));
        for (int i = 0; i < N; i++){
            M[i][i] = 1;
        }
    }
    /// @brief h×w型の、全要素がvの行列を生成
    /// @param h 
    /// @param w 
    /// @param v 
    matrix(int h, int w, T v){
        H = h;
        W = w;
        M = vector<vector<T>>(H,vector<T>(W,v));
    }
    /// @brief 2次元配列を用いて行列を生成
    /// @param A 
    matrix(const vector<vector<T>> &A){
        M = A;
        H = A.size();
        W = A[0].size();
    }
    
    matrix operator+(const matrix &A)const{
        if (H != A.H  || W != A.W){
            cerr << "size error(operator+)" << endl;
            assert(false);
        }
        matrix ans(M);
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                ans.M[i][j] += A.M[i][j];
            }
        }
        return ans;
    }
    void operator+=(const matrix &A){
        if (H != A.H  || W != A.W){
            cerr << "size error(operator+=)" << endl;
            assert(false);
        }
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                M[i][j] += A.M[i][j];
            }
        }
    }
    matrix operator-(const matrix &A)const{
        if (H != A.H  || W != A.W){
            cerr << "size error(operator-)" << endl;
            assert(false);
        }
        matrix ans(M);
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                ans.M[i][j] -= A.M[i][j];
            }
        }
        return ans;
    }
    void operator-=(const matrix &A){
        if (H != A.H  || W != A.W){
            cerr << "size error(operator-=)" << endl;
            assert(false);
        }
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                M[i][j] -= A.M[i][j];
            }
        }
    }
    matrix operator*(const matrix &A)const{
        if (W != A.H){
            cerr << "size error(operator*)" << endl;
            assert(false);
        }
        matrix ans(H,A.W,0);
        for (int i = 0; i < H; i++){
            for (int k = 0; k < W; k++){
                T constval = M[i][k];
                for (int j = 0; j < A.W; j++){
                    ans.M[i][j] += constval*A.M[k][j];
                }
            }
        }
        return ans;
    }
    void operator*=(const matrix &A){
        if (W != A.H){
            cerr << "size error(operator*=)" << endl;
            assert(false);
        }
        matrix ans(H,A.W,0);
        for (int i = 0; i < H; i++){
            for (int k = 0; k < W; k++){
                T constval = M[i][k];
                for (int j = 0; j < A.W; j++){
                    ans.M[i][j] += constval*A.M[k][j];
                }
            }
        }
        W = A.W;
        M = ans.M;
    }
    matrix operator*(const T c)const{
        matrix ans(H,W,0);
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                ans.M[i][j] = M[i][j] * c;
            }
        }
        return ans;
    }
    void operator*=(const T c){
        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                M[i][j] *= c;
            }
        }
    }

    
    /// @brief i行目を1/c倍
    /// @param i 
    /// @param c 
    void row_transformation_division(size_t i, T c){
        for (int j = 0; j < W; j++){
            M[i][j] /= c;
        }
    }
    /// @brief i行目のc倍を、j行目から減算
    /// @param i 
    /// @param j 
    /// @param c 
    void row_transformation_sub_row(size_t i, T c, size_t j){
        for (int k = 0; k < W; k++){
            M[j][k] -= M[i][k]*c;
        }
    }

    /// @brief 行の数を返す
    size_t size(){return H;}
    bool empty(){return H == 0;}
    vector<T>& operator[](const int row){
        return M[row];
    }

    /// @brief 行列を2次元累積和テーブルに変換する。
    void cumulative2d(){
        for (int i = 0; i < H; i++){
            for (int j = 1; j < W; j++){
                M[i][j] += M[i][j-1];
            }
        }
        for (int i = 1; i < H; i++){
            for (int j = 0; j < W; j++){
                M[i][j] += M[i-1][j];
            }
        }
    }
    T sum_from_origin(int r, int c){
        if (r < 0 || c < 0){return 0;}
        return M[r][c];
    }
    /// @brief r1<=行番号<=r2, c1<=列番号<=c2を満たすような部分の総和を求める。
    /// @param r1 
    /// @param r2 
    /// @param c1 
    /// @param c2 
    /// @return 和
    T rectangle_sum(int r1, int r2, int c1, int c2){
        if (r1 > r2 || c1 > c2){return 0;}
        return M[r2][c2] - M[r2][c1-1] - M[r1-1][c2] + M[r1-1][c1-1];
    }
};

/// @brief A^Nを返す。
/// @param A 
/// @param N 
/// @return A^N
template<typename T>
matrix<T> matrixpow(matrix<T> M, ll N){
    matrix<T> R(M.H);
    if (N){
        while (N){
            if (N%2){
                R *= M;
            }
            M *= M;
            N /= 2;
        }
        return R;
    }
    else{
        return R;
    }
}
/// @brief 与えられた行列を行簡約化する
/// @tparam T 
/// @param M 
/// @return 
template<typename T>
matrix<T> row_simplification(matrix<T> M){
    int non_zero_column = 0;
    for (int i = 0; i < M.H; i++){
        bool finished = false;
        while (!finished){
            if (non_zero_column == M.W){
                return M;
            }
            for (int k = i; k < M.H; k++){
                if (M[k][non_zero_column] != 0){
                    swap(M[i],M[k]);
                    M.row_transformation_division(i, M[i][non_zero_column]);
                    for (int l = 0; l < M.H; l++){
                        if (l == i){continue;}
                        M.row_transformation_sub_row(i, M[l][non_zero_column]/M[i][non_zero_column], l);
                    }
                    finished = true;
                    break;
                }
            }
            non_zero_column++;
        }
    }
    return M;
}
template<typename T>
pair<bool, matrix<T>> inverse_matrix(matrix<T> M){
    if (M.H != M.W){
        cerr << "This is not a square matrix" << endl;
        assert(false);
    }
    for (int i = 0; i < M.H; i++){
        for (int j = 0; j < M.W; j++){
            M[i].push_back(0);
        }
        M[i][M.W+i] = 1;
    }
    M.W *= 2;
    M = row_simplification(M);
    M.W /= 2;
    bool regular = true;
    for (ll i = 0; i < M.H; i++) if (M[i][i] == 0) regular = false;
    for (int i = 0; i < M.H; i++){
        M[i].erase(M[i].begin(), M[i].begin()+M.W);
    }
    return make_pair(regular, M);
}

ll internal_floor_sum(ll A, ll B, ll C){
    if (C < 0){return 0;}
    if (A > B){return internal_floor_sum(B,A,C);}
    if (B%A == 0){
        return (1+floor2(C,A))*(1+floor2(C,B)) - (B/A)*floor2(C,B)*(floor2(C,B)+1)/2;
    }
    ll k = floor2(C-B*floor2(C,B),A);
    return (1+k)*(1+floor2(C,B)) + floor2(B,A)*floor2(C,B)*(floor2(C,B)+1)/2 + internal_floor_sum(A, B%A, C-A*(floor2(B,A)*floor2(C,B)+k+1));
}
/// @brief `\sum_{i=0}^{N} \lfloor\frac{Ci+D}{B}\rfloor`を求める。
/// @param N 
/// @param M 
/// @param A 
/// @param B 
/// @return 
ll floor_sum(ll N, ll B, ll C, ll D){
    if (N < 0){
        return 0;
    }
    if (B < 0){//Bを負にする。
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (C > 0){//Cを負にするが、Cを-Cに置き換えてC>0として扱う。
        D += N*C;
    }
    else{
        C *= -1;
    }
    if (C == 0){
        return (N+1)*floor2(D,B);
    }
    ll k = floor2(D-C*N,B);
    return (N+1)*k + internal_floor_sum(B,C,D-B*(k+1));
}

ll internal_floor_max(ll A, ll B, ll C, ll D, ll E, ll F){
    if (D < 0){return -1000000000000000000;}
    if (B <= 0){return -1000000000000000000;}
    if (E > 0){
        if (B > C){return internal_floor_max(E,C,B,D,A,F);}
        ll M = floor2(D-C*floor2(D, C), B);
        ll tempans = max(A*M+E*floor2(D, C), A*floor2(D, B)) + F;
        return max(tempans, A*(1+M)+internal_floor_max(A, B, C%B, D-B*(1+M+floor2(C, B)*floor2(D, C)), E-A*floor2(C, B), F+A*floor2(C, B)*floor2(D, C)));
    }
    else return A*floor2(D, B) + F;
}
/// @brief `0<=x<=N`の下で、`A*floor2(C*x+D, B)+E*x+F`の最大値を求める。もし何かがおかしいなら`-10^18`が返される。
/// @param N 
/// @param A 
/// @param B 
/// @param C 
/// @param D 
/// @param E 
/// @param F 
/// @return `max`
ll floor_max(ll N, ll A, ll B, ll C, ll D, ll E, ll F){
    if (N < 0){
        return -1000000000000000000;
    }
    assert(B != 0);
    //マイナスを処理
    if (B < 0){
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (A < 0){
        A *= -1;
        C *= -1;
        D *= -1;
        D += B-1;
    }
    //自明なケース
    if (C == 0 or A == 0){
        return A*floor2(D, B) + F + max(0LL, E*N);
    }
    if (E == 0){
        return A*floor2(max(0LL, C*N)+D, B) + F;
    }
    //Cの係数を調整
    if (C > 0){
        F += E*N;
        E *= -1;
        D += C*N;
    }
    else{
        //`A*floor2(D-C*x, B)+E*x+F`, `A,B,C>0`にする
        C *= -1;
    }
    //自明なケースを処理
    if (E < 0){
        return A*floor2(D, B) + F;
    }
    ll x_offset = floor2(D-C*N, B)+1;
    D -= B*x_offset;
    return A*x_offset + max(internal_floor_max(A,B,C,D,E,F), -A+E*N+F);
}

//convolution.hpp
vector<ll> powroot998244353{1LL, 998244352LL, 911660635LL, 372528824LL, 69212480LL, 381091786LL, 515872972LL, 273395035LL, 469477650LL, 503794470LL, 464513504LL, 558899782LL, 504969456LL, 840897051LL, 539927980LL, 417009993LL, 725461291LL, 456548895LL, 712494065LL, 542639453LL, 768214923LL, 303507821LL, 438914733LL, 761881641};
vector<ll> powrootinv998244353{1LL, 998244352LL, 86583718LL, 509520358LL, 661054123LL, 863921598LL, 323451984LL, 689146517LL, 379690232LL, 240519260LL, 899368279LL, 920065956LL, 588792270LL, 118574449LL, 847593593LL, 858760106LL, 987418793LL, 177938570LL, 753608159LL, 786906984LL, 331540181LL, 655706071LL, 268754442LL, 191076546};
vector<ll> powroot1224736769{1LL, 1224736768LL, 24506215LL, 992888437LL, 853017291LL, 235319402LL, 269744380LL, 157861287LL, 894223137LL, 600648668LL, 1091208103LL, 382541006LL, 12818149LL, 149218560LL, 746299392LL, 405692663LL, 633223136LL, 672327338LL, 992917013LL, 758198491LL, 1079610480LL, 1056667043LL, 1039331205LL, 1026803890LL, 449603200};
vector<ll> powrootinv1224736769{1LL, 1224736768LL, 1200230554LL, 961581489LL, 796105727LL, 1023008969LL, 406386483LL, 251411652LL, 655108271LL, 1145368249LL, 780593535LL, 38041180LL, 816166160LL, 659160240LL, 1200430513LL, 392462252LL, 15561184LL, 893027826LL, 928760284LL, 497993173LL, 529117122LL, 637457654LL, 931394937LL, 823596420LL, 55047034};

vector<ll> DFT998244353(vector<ll> X, ll K, bool inverse = false){
    if (K == 1){
        return vector<ll>{(X[0]+X[1])%998244353, (998244353+X[0]-X[1])%998244353};
    }

    vector<ll> even(1<<(K-1));
    vector<ll> odd(1<<(K-1));
    for (int i = 0; i < (1<<(K-1)); i++){
        even[i] = (X[i] + X[(1<<(K-1))+i])%998244353;
    }
    ll temp = 1;
    if (inverse){
        for (int i = 0; i < (1<<(K-1)); i++){
            odd[i] = (temp*(998244353 + X[i] - X[(1<<(K-1))+i]))%998244353;
            temp = (temp*powrootinv998244353[K])%998244353;
        }
    }
    else{
        for (int i = 0; i < (1<<(K-1)); i++){
            odd[i] = (temp*(998244353 + X[i] - X[(1<<(K-1))+i]))%998244353;
            temp = (temp*powroot998244353[K])%998244353;
        }
    }

    even = DFT998244353(even,K-1,inverse);
    odd = DFT998244353(odd,K-1,inverse);
    for (int i = 0; i < (1<<K); i++){
        if (i%2){
            X[i] = odd[i/2];
        }
        else{
            X[i] = even[i/2];
        }
    }
    return X;
}
vector<ll> DFT1224736769(vector<ll> X, ll K, bool inverse = false){
    if (K == 1){
        return vector<ll>{(X[0]+X[1])%1224736769, (1224736769+X[0]-X[1])%1224736769};
    }

    vector<ll> even(1<<(K-1));
    vector<ll> odd(1<<(K-1));
    for (int i = 0; i < (1<<(K-1)); i++){
        even[i] = (X[i] + X[(1<<(K-1))+i])%1224736769;
    }
    ll temp = 1;
    if (inverse){
        for (int i = 0; i < (1<<(K-1)); i++){
            odd[i] = (temp*(1224736769 + X[i] - X[(1<<(K-1))+i]))%1224736769;
            temp = (temp*powrootinv1224736769[K])%1224736769;
        }
    }
    else{
        for (int i = 0; i < (1<<(K-1)); i++){
            odd[i] = (temp*(1224736769 + X[i] - X[(1<<(K-1))+i]))%1224736769;
            temp = (temp*powroot1224736769[K])%1224736769;
        }
    }

    even = DFT1224736769(even,K-1,inverse);
    odd = DFT1224736769(odd,K-1,inverse);
    for (int i = 0; i < (1<<K); i++){
        if (i%2){
            X[i] = odd[i/2];
        }
        else{
            X[i] = even[i/2];
        }
    }
    return X;
}

vector<ll> convolution998244353(vector<ll> A, vector<ll> B){

    if (min(A.size(), B.size()) <= 60) {
        if (A.size() < B.size()) {
            swap(A, B);
        }
        std::vector<ll> ans(A.size() + B.size() - 1);
        for (size_t i = 0; i < A.size(); i++) {
            for (size_t j = 0; j < B.size(); j++) {
                ans[i+j] += A[i] * B[j];
                ans[i+j] %= 998244353;
            }
        }
        return ans;
    }

    ll N = A.size()+B.size()-1;
    ll log2N = 0;
    while ((1LL<<log2N) < N){
        log2N++;
    }

    while (A.size() < (1ULL<<log2N)){
        A.push_back(0);
    }
    while (B.size() < (1ULL<<log2N)){
        B.push_back(0);
    }

    A = DFT998244353(A,log2N);
    B = DFT998244353(B,log2N);
    vector<ll> C((1LL<<log2N),0);
    for (int i = 0; i < (1<<log2N); i++){
        C[i] = (A[i]*B[i])%998244353;
    }
    C = DFT998244353(C,log2N,1);
    ll invpow2log2N = inverse_mod((1LL<<log2N),998244353);
    for (int i = 0; i < (1<<log2N); i++){
        C[i] = (C[i]*invpow2log2N)%998244353;
    }
    return C;
}
vector<ll> convolution1224736769(vector<ll> A, vector<ll> B){

    if (min(A.size(), B.size()) <= 60) {
        if (A.size() < B.size()) {
            swap(A, B);
        }
        std::vector<ll> ans(A.size() + B.size() - 1);
        for (size_t i = 0; i < A.size(); i++) {
            for (size_t j = 0; j < B.size(); j++) {
                ans[i+j] += A[i] * B[j];
                ans[i+j] %= 1224736769;
            }
        }
        for (auto &v : ans){
            v %= 1224736769;
        }
        return ans;
    }

    ll N = A.size()+B.size()-1;
    ll log2N = 0;
    while ((1LL<<log2N) < N){
        log2N++;
    }

    while (A.size() < (1ULL<<log2N)){
        A.push_back(0);
    }
    while (B.size() < (1ULL<<log2N)){
        B.push_back(0);
    }

    A = DFT1224736769(A,log2N);
    B = DFT1224736769(B,log2N);
    vector<ll> C((1LL<<log2N),0);
    for (int i = 0; i < (1<<log2N); i++){
        C[i] = (A[i]*B[i])%1224736769;
    }
    C = DFT1224736769(C,(1<<log2N),1);
    ll invpow2log2N = inverse_mod((1LL<<log2N),1224736769);
    for (int i = 0; i < (1<<log2N); i++){
        C[i] = (C[i]*invpow2log2N)%1224736769;
    }
    return C;
}

/// @brief [x^N](P(x)/Q(x))をmod998244353で求める。
/// @param N 
/// @param P 
/// @param Q 
/// @return 
ll Bostan_Mori998244353(const ll N, vector<ll> P, vector<ll> Q){
    assert(N >= 0);
    if (N == 0){
        return P[0]*math::inverse_mod(Q[0], 998244353);
    }
    vector<ll> Q_minus;
    const int maxloop = (N == 1 ? 1 : 65-__builtin_clzll(N-1));
    for (int _i_ = 0; _i_ < maxloop; _i_++){
        Q_minus.resize(Q.size());
        for (size_t i = 0; i < Q_minus.size(); i += 2){
            Q_minus[i] = Q[i];
        }
        for (size_t i = 1; i < Q_minus.size(); i += 2){
            Q_minus[i] = 998244352*Q[i]%998244353;
        }
        auto A = math::convolution998244353(P,Q_minus);
        auto B = math::convolution998244353(Q,Q_minus);
        Q.resize((B.size()+1)/2);
        for (size_t i = 0; i < B.size(); i += 2){
            Q[i/2] = B[i];
        }
        P.resize((A.size()+!btest(N,_i_))/2);
        for (size_t i = btest(N,_i_); i < A.size(); i += 2){
            P[i/2] = A[i];
        }
    }
    return P[0]*math::inverse_mod(Q[0], 998244353);
}


}

}

using namespace a1073741824;
using namespace math;
using mll = math::mint<998244353>;
using dmll = math::dynamic_mint;

#define lll __int128_t

ll fast_isqrt(ll x){
    ll ret = sqrt(x);
    while (ret*ret > x){
        ret--;
    }
    while ((ret+1)*(ret+1) <= x){
        ret++;
    }
    return ret;
}
long long safe_pow(long long a,long long b){
  long long res=1;
  for(long long i=0;i<b;i++){
      long double dres=res;
      dres*=a;
      if(dres>2e18){return 2e18;}
      res*=a;
  }
  return res;
}


ll sum_iisqrti(ll N){
    if (N <= 0){return 0;}
    ll M = fast_isqrt(N);
    ll ans = 0;
    ans += 149736653*(M*M%998244353*M%998244353-M%998244353)%998244353*(8*M*M%998244353-5*M%998244353-2)%998244353;
    ans += ((M&1) ? (998244353+M)/2 : M/2)*(N%998244353*(N%998244353+1)%998244353-M*M%998244353*(M*M%998244353-1)%998244353)%998244353;
    return (998244353+ans%998244353)%998244353;
}


void solve(){




    auto factorialmodinv = vector<ll>(1000000+1);
    factorialmodinv[0] = 1;
    factorialmodinv[1] = 1;
    for (int i = 2; i <= 1000000; i++){
        factorialmodinv[i] = (998244353-factorialmodinv[998244353%i]*(998244353/i)%998244353)%998244353;
    }




    ll N;
    cin >> N;

    vector<pll> transitions;
    transitions.push_back({N+1, -1});
    for (ll i = 60; i >= 3; i--){
        vector<pll> temp;
        for (ll j = 2;; j++){
            lll temp2 = safe_pow(j,i);
            if (temp2 > N){break;}
            temp.push_back({(ll)temp2, j});
        }
        reverse(vall(temp));
        vector<pll> transitions2;
        while (true){
            if (temp.empty()){
                for (ll i = (ll)transitions.size()-1; i >= 0; i--){
                    transitions2.push_back(transitions[i]);
                }
                break;
            }
            if (transitions.empty()){
                for (ll i = (ll)temp.size()-1; i >= 0; i--){
                    transitions2.push_back(temp[i]);
                }
                break;
            }
            if (temp.back()[0] < transitions.back()[0]){
                transitions2.push_back(temp.back());
                temp.pop_back();
            }
            else{
                transitions2.push_back(transitions.back());
                transitions.pop_back();
            }
        }
        reverse(vall(transitions2));
        transitions = transitions2;
    }
    ll temp = 1;
    ll prev = 1;
    ll ans = 0;
    for (ll i = (ll)transitions.size()-1; i >= 0; i--){
        auto& now = transitions[i];
        if (prev < now[0]){
            ans += temp*(sum_iisqrti(now[0]-1)-sum_iisqrti(prev-1))%998244353;
            ans %= 998244353;
        }
        temp = temp*factorialmodinv[now[1]-1]%998244353*(now[1]%998244353)%998244353;
        prev = now[0];
    }
    print((998244353+ans%998244353)%998244353);

    //ans = 0;
    //for (ll i = 0; i <= N; i++){
    //    temp = i;
    //    for (ll j = 2; j <= 60; j++){
    //        temp = temp*kth_root(i,j)%998244353;
    //    }
    //    ans += temp;
    //    ans %= 998244353;
    //}
    //print((ll)ans);
}

//1000000000000000000

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll T = 1;
    //cin >> T;
    while (T--){
        solve();
    }
}