#line 2 "lib/template.hpp"
#pragma GCC optimize("O3")
using namespace std;
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <climits>
#include <cassert>
#include <functional>
#include <iterator>
#include <utility>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
#include <limits>
#include <optional>
#include <variant>
#include <any>

#include <array>
#include <bit>
#include <compare>
#include <concepts>
#include <format>
#include <numbers>
#include <ranges>
#include <span>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <version>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using i128=__int128;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
#define vec(d,T,n,...) vec_##d(T,n,__VA_ARGS__)
#define vec_1(T,n,a) vector<T> n(a)
#define vec_2(T,n,a,b) vector<vector<T>> n(a,vector<T>(b))
#define vec_3(T,n,a,b,c) vector<vector<vector<T>>> n(a,vector<vector<T>>(b,vector<T>(c)))
#define vec_4(T,n,a,b,c,d) vector<vector<vector<vector<T>>>> n(a,vector<vector<vector<T>>>(b,vector<vector<T>>(c,vector<T>(d))))
#define vec_5(T,n,a,b,c,d,e) vector<vector<vector<vector<vector<T>>>>> n(a,vector<vector<vector<vector<T>>>>(b,vector<vector<vector<T>>>(c,vector<vector<T>>(d,vector<T>(e)))))
#define vec_6(T,n,a,b,c,d,e,f) vector<vector<vector<vector<vector<vector<T>>>>>> n(a,vector<vector<vector<vector<vector<T>>>>>(b,vector<vector<vector<vector<T>>>>(c,vector<vector<vector<T>>>(d,vector<vector<T>>(e,vector<T>(f))))))
#define vec_7(T,n,a,b,c,d,e,f,g) vector<vector<vector<vector<vector<vector<vector<T>>>>>>> n(a,vector<vector<vector<vector<vector<vector<T>>>>>>(b,vector<vector<vector<vector<vector<T>>>>>(c,vector<vector<vector<vector<T>>>>(d,vector<vector<vector<T>>>(e,vector<vector<T>>(f,vector<T>(g)))))))
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
template<class T>void print(T a) { cout << a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
template <typename T>
T floor(T a, T b) {
  return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
  return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
  return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
  T q = floor(x, y);
  return {q, x - q * y};
}
void YesNo(bool b){
    cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
    cout<<"Yes"<<endl;
}
void No(){
    cout<<"No"<<endl;
}
template<class T=ll>
T isqrt(T x){
    T F=sqrtl(x);
    while((F+1)*(F+1)<=x)F++;
    while(F*F>x)F--;
    return F;
}
template<class T>
int popcount(T n){
    return __builtin_popcountll(n);
}
template<class T,class L=ll>
L sum(vc<T>&a){
    return accumulate(all(a),L(0));
}
template<class T>
vc<T>subset(T S){
    vc<T>ans;
    for(T x=S;x>0;x=(x-1)&S)ans.pb(x);
    ans.pb(0);
    return ans;
}
template<class T>
T max(vc<T>&a){
    return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
    return *min_element(all(a));
}
vvc<int>readgraph(int n,int m,int off = -1){
    vvc<int> g(n);
    rep(i, m){
        int u,v;
        cin>>u>>v;
        u+=off,v+=off;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}
vvc<int> readtree(int n,int off=-1){
    return readgraph(n,n-1,off);
}
template<class T,class L=ll>
vc<L> presum(vc<T> &a){
    vc<L> ret(a.size()+1);
    rep(i,a.size())ret[i+1]=ret[i]+a[i];
    return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
    for (auto&v:a)v += b;
    return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
    for (auto&v:a)v-=b;
    return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
    for (auto&v:a)v*=b;
    return a;
}
template<class T=ll>
constexpr T POW(T a,T b){
    T res=1;
    while(b){
        if(b&1)res*=a;
        a*=a;
        b/=2;
    }
    return res;
}
constexpr ll ten(ll a){
    return POW<ll>(10,a);
}
template<class T>
struct Compress{    
    vc<T>v;
    bool worked;
    Compress(){worked=0;}
    Compress(int n){v.reserve(n);worked=0;}
    void push(T x){
        v.push_back(x);
    }
    void work(){
        if(worked)return;
        worked=1;
        sort(all(v));
        v.erase(unique(all(v)),v.end());
    }
    int find(T x){
        work();
        auto itr=lower_bound(all(v),x);
        if((*itr)==x)return itr-v.begin();
        return -1;
    }
    int find_next(T x){
        work();
        return lower_bound(all(v),x)-v.begin();
    }
    int find_prev(T x){
        work();
        return lower_bound(all(v),x)-v.begin()-1;
    }
};
int tbit(int32_t x){return x==0?-1:31-__builtin_clz((uint32_t)x);}
int lbit(int32_t x){return x==0?-1:__builtin_ctz((uint32_t)x);}
int tbit(uint32_t x){return x==0?-1:31-__builtin_clz(x);}
int lbit(uint32_t x){return x==0?-1:__builtin_ctz(x);}
int tbit(int64_t x){return x==0?-1:63-__builtin_clzll((uint64_t)x);}
int lbit(int64_t x){return x==0?-1:__builtin_ctzll((uint64_t)x);}
int tbit(uint64_t x){return x==0?-1:63-__builtin_clzll(x);}
int lbit(uint64_t x){return x==0?-1:__builtin_ctzll(x);}
int tbit(int32_t x,int p){return p<0?-1:tbit((int32_t)(x&(p>=31?~0u:(1u<<(p+1))-1)));}
int lbit(int32_t x,int p){return p>31?-1:lbit((int32_t)(x&(~0u<<p)));}
int tbit(uint32_t x,int p){return p<0?-1:tbit((uint32_t)(x&(p>=31?~0u:(1u<<(p+1))-1)));}
int lbit(uint32_t x,int p){return p>31?-1:lbit((uint32_t)(x&(~0u<<p)));}
int tbit(int64_t x,int p){return p<0?-1:tbit((int64_t)(x&(p>=63?~0ULL:(1ULL<<(p+1))-1)));}
int lbit(int64_t x,int p){return p>63?-1:lbit((int64_t)(x&(~0ULL<<p)));}
int tbit(uint64_t x,int p){return p<0?-1:tbit((uint64_t)(x&(p>=63?~0ULL:(1ULL<<(p+1))-1)));}
int lbit(uint64_t x,int p){return p>63?-1:lbit((uint64_t)(x&(~0ULL<<p)));}
std::istream& operator>>(std::istream& is, __int128& x) {
    std::streambuf* sb = is.rdbuf();

    int c = sb->sgetc();
    while (c <= ' ') c = sb->snextc();

    bool neg = false;
    if (c == '-') {
        neg = true;
        c = sb->snextc();
    }

    unsigned __int128 v = 0;

    while ((unsigned)(c - '0') < 10) {
        v = v * 10 + (c - '0');
        c = sb->snextc();
    }

    x = neg ? -(__int128)v : (__int128)v;
    return is;
}

std::ostream& operator<<(std::ostream& os, __int128 x) {
    std::streambuf* sb = os.rdbuf();

    if (x == 0) {
        sb->sputc('0');
        return os;
    }

    char buf[40];
    int pos = 39;

    bool neg = x < 0;
    unsigned __int128 v = neg ? -(unsigned __int128)x : (unsigned __int128)x;

    while (v) {
        buf[--pos] = char('0' + (v % 10));
        v /= 10;
    }

    if (neg) buf[--pos] = '-';

    sb->sputn(buf + pos, 39 - pos);
    return os;
}
#ifdef LOCAL

template<typename T, typename U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p);
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T> std::ostream& operator<<(std::ostream& os, const std::deque<T>& dq);
template<typename T> std::ostream& operator<<(std::ostream& os, const std::list<T>& lst);
template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T> std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& s);
template<typename K, typename V> std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m);
template<typename K, typename V> std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, V>& m);
template<typename T> std::ostream& operator<<(std::ostream& os, std::stack<T> st);
template<typename T> std::ostream& operator<<(std::ostream& os, std::queue<T> q);
template<typename T, std::size_t N> std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template <typename T, typename Container, typename Compare>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T, Container, Compare> pq);

#define dbg(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__)

template <typename T>
void debug_func(int i, T name) {
  cout << endl;
}

template <typename T1, typename T2, typename... T3>
void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
  for ( ; name[i] != ',' && name[i] != '\0'; i++ ) cout << name[i];
  cout << ":" << a << " ";
  debug_func(i + 1, name, b...);
}
// pair
template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// vector
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) os << ", ";
        os << v[i];
    }
    os << "]";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::deque<T>& dq) {
    os << "[";
    for (size_t i = 0; i < dq.size(); ++i) {
        if (i > 0) os << ", ";
        os << dq[i];
    }
    os << "]";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::list<T>& lst) {
    os << "[";
    bool first = true;
    for (const auto& x : lst) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "]";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& x : s) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "}";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& s) {
    os << "{";
    bool first = true;
    for (const auto& x : s) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << "}";
    return os;
}

template<typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) {
    os << "{";
    bool first = true;
    for (const auto& kv : m) {
        if (!first) os << ", ";
        os << kv;
        first = false;
    }
    os << "}";
    return os;
}

template<typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, V>& m) {
    os << "{";
    bool first = true;
    for (const auto& kv : m) {
        if (!first) os << ", ";
        os << kv;
        first = false;
    }
    os << "}";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, std::stack<T> st) {
    os << "[";
    bool first = true;
    while (!st.empty()) {
        if (!first) os << ", ";
        os << st.top();
        st.pop();
        first = false;
    }
    os << "]";
    return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, std::queue<T> q) {
    os << "[";
    bool first = true;
    while (!q.empty()) {
        if (!first) os << ", ";
        os << q.front();
        q.pop();
        first = false;
    }
    os << "]";
    return os;
}

template<typename T, typename Container, typename Compare>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T, Container, Compare> pq) {
    os << "[";
    while (!pq.empty()) {
        os << pq.top() << (pq.size() > 1 ? ", " : "");
        pq.pop();
    }
    return os << "]";
}
template<typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
    os << "[";
    for (std::size_t i = 0; i < N; ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}
#else
#define dbg(...) 1111
#endif
#line 3 "lib/math/barrett.hpp"
struct Barrett{
    using u64=uint64_t;
    using u32=uint32_t;
    using i128=__int128_t;
    u64 m;
    int mod;
    void set(int mod_){
        mod=mod_;
        m=(i128(1)<<64)/mod;
    }
    unsigned reduce(uint64_t x){
        x-=(((i128)x*m)>>64)*mod;
        return x<mod?x:x-mod;
    }
};
#line 4 "lib/math/d_mint.hpp"
template<int id>
struct DynamicModInt{
    using u32=uint32_t;
    using u64=uint64_t;
    u32 val;
    DynamicModInt():val(0){}
    DynamicModInt(ll x){
        int v=x%get_mod();
        if(v<0)v+=get_mod();
        val=v;
    }
    static DynamicModInt raw(int v){
        assert(v>=0);
        DynamicModInt mi;
        mi.val=v;
        return mi;
    }
    DynamicModInt &operator+=(const DynamicModInt&m){
        if((val+=m.val)>=get_mod())val-=get_mod();
        return *this;
    }
    DynamicModInt &operator-=(const DynamicModInt&m){
        if((val+=(get_mod()-m.val))>=get_mod())val-=get_mod();
        return *this;
    }
    DynamicModInt &operator*=(const DynamicModInt&m){
        val=rem(u64(val)*m.val);
        return *this;
    }
    DynamicModInt &operator/=(const DynamicModInt&m){
        val=rem(u64(val)*m.inv().val);
        return *this;
    }
    DynamicModInt operator-() const{
        return DynamicModInt(-val);
    }
    DynamicModInt operator+() const {
        return *this;
    }
    friend DynamicModInt operator+(DynamicModInt lhs, const DynamicModInt& rhs){
        return lhs+=rhs;
    }
    friend DynamicModInt operator-(DynamicModInt lhs, const DynamicModInt& rhs){
        return lhs-=rhs;
    }
    friend DynamicModInt operator*(DynamicModInt lhs, const DynamicModInt& rhs){
        return lhs*=rhs;
    }
    friend DynamicModInt operator/(DynamicModInt lhs,const DynamicModInt&rhs){
        return lhs/=rhs;
    }
    bool operator==(const DynamicModInt&p) const{
        return p.val==val;
    }
    bool operator!=(const DynamicModInt&p) const{
        return p.val!=val;
    }
    DynamicModInt pow(int64_t n) const{
        DynamicModInt res(1),mul(val);
        while(n){
            if(n%2)res*=mul;
            mul*=mul;
            n/=2;
        }
        return res;
    }

    friend ostream&operator<<(ostream&os,const DynamicModInt&p){
        os<<p.val;
        return os;
    }
    friend istream&operator>>(istream&is,DynamicModInt&p){
        int64_t x;
        is>>x;
        p=DynamicModInt(x);
        return is;
    }
    DynamicModInt inv()const{
        int a=val,b=get_mod(),u=1,v=0,t;
        #ifdef LOCAL
        assert(gcd(a,b)==1);
        #endif
        while(b>0){
            t=a/b;
            swap(a-=t*b,b);
            swap(u-=t*v,v);
        }
        return DynamicModInt(u);
    }
    inline static u32 rem(u64 x){return BarrettReduction().reduce(x);}
    static inline int &get_mod(){
        static int mod=0;
        return mod;
    }
    static void set_mod(int md){
        assert(0<md&&md<=(1ll<<30)-1);
        get_mod()=md;
        BarrettReduction().set(md);
    }
    static inline Barrett&BarrettReduction(){
        static Barrett b;
        return b;
    }
};

#line 4 "lib/math/mod.hpp"
template<class mint>
struct Binom{
    inline static vector<mint>fact={1},invfact={1};
    static void build(int n){
        if(n<(int)fact.size())return;
        fact=invfact=vector<mint>(n+1);
        fact[0]=1;
        for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i;
        invfact[n]=(1/fact[n]);
        for(int i=n-1;i>=0;i--)invfact[i]=invfact[i+1]*(i+1);
    }
    static mint C(int a,int b){//aCb
        if(a<0||b<0||a-b<0)return mint(0);
        while((int)fact.size()<=a){
            fact.push_back(fact.back()*(fact.size()));
        }
        while((int)invfact.size()<=a){
            invfact.push_back(invfact.back()/invfact.size());
        }
        return fact[a]*invfact[b]*invfact[a-b];
    }
    static mint P(int a,int b){
        if(a<b||b<0)return 0;
        return fact[a]*invfact[a-b];
    }
    static mint H(int a,int b){
        return C(a+b-1,b);
    }  
};
template<class T>
pair<T,T> inv(T x,T m){
    T a1,a2;
    T res=extgcd(x,m,a1,a2);
    return {a1,m/res};
}
template<class T>
pair<T,T> mod_solve(T a,T b,T m){//return x s.t. ax=b mod m
    a%=m,b%=m;if(a<0)a+=m;if(b<0)b+=m;
    T g=gcd(gcd(a,b),m);
    a/=g,b/=g,m/=g;
    if(gcd(a,m)>1)return {-1,-1};
    return {(inv(a,m).first*b)%m,inv(a,m).second};
}
//https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp.html
int64_t mod_sqrt(const int64_t &a, const int64_t &p) {
  assert(0 <= a && a < p);
  if (a < 2) return a;
  using Mint = DynamicModInt<409075245>;
  Mint::set_mod(p);
  if (Mint(a).pow((p - 1) >> 1) != 1) return -1;
  Mint b = 1, one = 1;
  while (b.pow((p - 1) >> 1) == 1) b += one;
  int64_t m = p - 1, e = 0;
  while (m % 2 == 0) m >>= 1, e += 1;
  Mint x = Mint(a).pow((m - 1) >> 1);
  Mint y = Mint(a) * x * x;
  x *= a;
  Mint z = Mint(b).pow(m);
  while (y != 1) {
    int64_t j = 0;
    Mint t = y;
    while (t != one) {
      j += 1;
      t *= t;
    }
    z = z.pow(int64_t(1) << (e - j - 1));
    x *= z;
    z *= z;
    y *= z;
    e = j;
  }
  return x.val;
}
#line 4 "lib/math/s_mint.hpp"
template<uint32_t mod>
struct StaticModInt{
    using u32=uint32_t;
    using u64=uint64_t;
    u32 val;
    StaticModInt():val(0){}
    StaticModInt(ll x){
        int v=x%mod;
        if(v<0)v+=mod;
        val=v;
    }
    constexpr static uint32_t get_mod(){
        return mod;
    }
    static StaticModInt raw(int v){
        assert(v>=0);
        StaticModInt mi;
        mi.val=v;
        return mi;
    }
    StaticModInt &operator+=(const StaticModInt&m){
        if((val+=m.val)>=mod)val-=mod;
        return *this;
    }
    StaticModInt &operator-=(const StaticModInt&m){
        if((val+=(mod-m.val))>=mod)val-=mod;
        return *this;
    }
    StaticModInt &operator*=(const StaticModInt&m){
        val=u64(val)*m.val%mod;
        return *this;
    }
    StaticModInt &operator/=(const StaticModInt&m){
        val=u64(val)*m.inv().val%mod;
        return *this;
    }
    StaticModInt operator-() const{
        return StaticModInt(mod-val);
    }
    StaticModInt operator+() const {
        return *this;
    }
    friend StaticModInt operator+(StaticModInt lhs, const StaticModInt& rhs){
        return lhs+=rhs;
    }
    friend StaticModInt operator-(StaticModInt lhs, const StaticModInt& rhs){
        return lhs-=rhs;
    }
    friend StaticModInt operator*(StaticModInt lhs, const StaticModInt& rhs){
        return lhs*=rhs;
    }
    friend StaticModInt operator/(StaticModInt lhs,const StaticModInt&rhs){
        return lhs/=rhs;
    }
    bool operator==(const StaticModInt&p) const{
        return p.val==val;
    }
    bool operator!=(const StaticModInt&p) const{
        return p.val!=val;
    }
    StaticModInt pow(int64_t n) const{
        StaticModInt res(1),mul(val);
        while(n){
            if(n%2)res*=mul;
            mul*=mul;
            n/=2;
        }
        return res;
    }

    friend ostream&operator<<(ostream&os,const StaticModInt&p){
        os<<p.val;
        return os;
    }
    friend istream&operator>>(istream&is,StaticModInt&p){
        int64_t x;
        is>>x;
        p=StaticModInt(x);
        return is;
    }
    StaticModInt inv()const{
        int a=val,b=mod,u=1,v=0,t;
        #ifdef LOCAL
        assert(gcd(a,b)==1);
        #endif
        while(b>0){
            t=a/b;
            swap(a-=t*b,b);
            swap(u-=t*v,v);
        }
        return StaticModInt(u);
    }
};

#line 3 "lib/math/kth_root.hpp"
//floor(a^{1/b})
ull kth_root(ull a,ull b){
    if(a==0)return 0;
    if(b==1)return a;
    if(b>=64)return 1;
    auto my_pow=[&](ull A,ull B)->ull{
        ull res=1;
        while(B){
            if(B%2){
                if(i128(res)*A>a)return 0;
                res*=A;
            }
            B/=2;
            if(B){
                if(i128(A)*A>a)return 0;
                A*=A;
            }
        }
        return res;
    };
    ull ac=1,wa=(ull(1)<<(64/b+1))+1;
    while(wa-ac>1){
        ull wj=ac+wa>>1;
        auto res=my_pow(wj,b);
        if(res&&res<=a){
            ac=wj;
        }else wa=wj;
    }
    return ac;
}
#line 4 "a.cpp"
using mint=StaticModInt<998244353>;
vc<ll>is{1000000,2000000,3000000,4000000,5000000,6000000,7000000,8000000,9000000,10000000,11000000,12000000,13000000,14000000,15000000,16000000,17000000,18000000,19000000,20000000,21000000,22000000,23000000,24000000,25000000,26000000,27000000,28000000,29000000,30000000,31000000,32000000,33000000,34000000,35000000,36000000,37000000,38000000,39000000,40000000,41000000,42000000,43000000,44000000,45000000,46000000,47000000,48000000,49000000,50000000,51000000,52000000,53000000,54000000,55000000,56000000,57000000,58000000,59000000,60000000,61000000,62000000,63000000,64000000,65000000,66000000,67000000,68000000,69000000,70000000,71000000,72000000,73000000,74000000,75000000,76000000,77000000,78000000,79000000,80000000,81000000,82000000,83000000,84000000,85000000,86000000,87000000,88000000,89000000,90000000,91000000,92000000,93000000,94000000,95000000,96000000,97000000,98000000,99000000,100000000,101000000,102000000,103000000,104000000,105000000,106000000,107000000,108000000,109000000,110000000,111000000,112000000,113000000,114000000,115000000,116000000,117000000,118000000,119000000,120000000,121000000,122000000,123000000,124000000,125000000,126000000,127000000,128000000,129000000,130000000,131000000,132000000,133000000,134000000,135000000,136000000,137000000,138000000,139000000,140000000,141000000,142000000,143000000,144000000,145000000,146000000,147000000,148000000,149000000,150000000,151000000,152000000,153000000,154000000,155000000,156000000,157000000,158000000,159000000,160000000,161000000,162000000,163000000,164000000,165000000,166000000,167000000,168000000,169000000,170000000,171000000,172000000,173000000,174000000,175000000,176000000,177000000,178000000,179000000,180000000,181000000,182000000,183000000,184000000,185000000,186000000,187000000,188000000,189000000,190000000,191000000,192000000,193000000,194000000,195000000,196000000,197000000,198000000,199000000,200000000,201000000,202000000,203000000,204000000,205000000,206000000,207000000,208000000,209000000,210000000,211000000,212000000,213000000,214000000,215000000,216000000,217000000,218000000,219000000,220000000,221000000,222000000,223000000,224000000,225000000,226000000,227000000,228000000,229000000,230000000,231000000,232000000,233000000,234000000,235000000,236000000,237000000,238000000,239000000,240000000,241000000,242000000,243000000,244000000,245000000,246000000,247000000,248000000,249000000,250000000,251000000,252000000,253000000,254000000,255000000,256000000,257000000,258000000,259000000,260000000,261000000,262000000,263000000,264000000,265000000,266000000,267000000,268000000,269000000,270000000,271000000,272000000,273000000,274000000,275000000,276000000,277000000,278000000,279000000,280000000,281000000,282000000,283000000,284000000,285000000,286000000,287000000,288000000,289000000,290000000,291000000,292000000,293000000,294000000,295000000,296000000,297000000,298000000,299000000,300000000,301000000,302000000,303000000,304000000,305000000,306000000,307000000,308000000,309000000,310000000,311000000,312000000,313000000,314000000,315000000,316000000,317000000,318000000,319000000,320000000,321000000,322000000,323000000,324000000,325000000,326000000,327000000,328000000,329000000,330000000,331000000,332000000,333000000,334000000,335000000,336000000,337000000,338000000,339000000,340000000,341000000,342000000,343000000,344000000,345000000,346000000,347000000,348000000,349000000,350000000,351000000,352000000,353000000,354000000,355000000,356000000,357000000,358000000,359000000,360000000,361000000,362000000,363000000,364000000,365000000,366000000,367000000,368000000,369000000,370000000,371000000,372000000,373000000,374000000,375000000,376000000,377000000,378000000,379000000,380000000,381000000,382000000,383000000,384000000,385000000,386000000,387000000,388000000,389000000,390000000,391000000,392000000,393000000,394000000,395000000,396000000,397000000,398000000,399000000,400000000,401000000,402000000,403000000,404000000,405000000,406000000,407000000,408000000,409000000,410000000,411000000,412000000,413000000,414000000,415000000,416000000,417000000,418000000,419000000,420000000,421000000,422000000,423000000,424000000,425000000,426000000,427000000,428000000,429000000,430000000,431000000,432000000,433000000,434000000,435000000,436000000,437000000,438000000,439000000,440000000,441000000,442000000,443000000,444000000,445000000,446000000,447000000,448000000,449000000,450000000,451000000,452000000,453000000,454000000,455000000,456000000,457000000,458000000,459000000,460000000,461000000,462000000,463000000,464000000,465000000,466000000,467000000,468000000,469000000,470000000,471000000,472000000,473000000,474000000,475000000,476000000,477000000,478000000,479000000,480000000,481000000,482000000,483000000,484000000,485000000,486000000,487000000,488000000,489000000,490000000,491000000,492000000,493000000,494000000,495000000,496000000,497000000,498000000,499000000,500000000,501000000,502000000,503000000,504000000,505000000,506000000,507000000,508000000,509000000,510000000,511000000,512000000,513000000,514000000,515000000,516000000,517000000,518000000,519000000,520000000,521000000,522000000,523000000,524000000,525000000,526000000,527000000,528000000,529000000,530000000,531000000,532000000,533000000,534000000,535000000,536000000,537000000,538000000,539000000,540000000,541000000,542000000,543000000,544000000,545000000,546000000,547000000,548000000,549000000,550000000,551000000,552000000,553000000,554000000,555000000,556000000,557000000,558000000,559000000,560000000,561000000,562000000,563000000,564000000,565000000,566000000,567000000,568000000,569000000,570000000,571000000,572000000,573000000,574000000,575000000,576000000,577000000,578000000,579000000,580000000,581000000,582000000,583000000,584000000,585000000,586000000,587000000,588000000,589000000,590000000,591000000,592000000,593000000,594000000,595000000,596000000,597000000,598000000,599000000,600000000,601000000,602000000,603000000,604000000,605000000,606000000,607000000,608000000,609000000,610000000,611000000,612000000,613000000,614000000,615000000,616000000,617000000,618000000,619000000,620000000,621000000,622000000,623000000,624000000,625000000,626000000,627000000,628000000,629000000,630000000,631000000,632000000,633000000,634000000,635000000,636000000,637000000,638000000,639000000,640000000,641000000,642000000,643000000,644000000,645000000,646000000,647000000,648000000,649000000,650000000,651000000,652000000,653000000,654000000,655000000,656000000,657000000,658000000,659000000,660000000,661000000,662000000,663000000,664000000,665000000,666000000,667000000,668000000,669000000,670000000,671000000,672000000,673000000,674000000,675000000,676000000,677000000,678000000,679000000,680000000,681000000,682000000,683000000,684000000,685000000,686000000,687000000,688000000,689000000,690000000,691000000,692000000,693000000,694000000,695000000,696000000,697000000,698000000,699000000,700000000,701000000,702000000,703000000,704000000,705000000,706000000,707000000,708000000,709000000,710000000,711000000,712000000,713000000,714000000,715000000,716000000,717000000,718000000,719000000,720000000,721000000,722000000,723000000,724000000,725000000,726000000,727000000,728000000,729000000,730000000,731000000,732000000,733000000,734000000,735000000,736000000,737000000,738000000,739000000,740000000,741000000,742000000,743000000,744000000,745000000,746000000,747000000,748000000,749000000,750000000,751000000,752000000,753000000,754000000,755000000,756000000,757000000,758000000,759000000,760000000,761000000,762000000,763000000,764000000,765000000,766000000,767000000,768000000,769000000,770000000,771000000,772000000,773000000,774000000,775000000,776000000,777000000,778000000,779000000,780000000,781000000,782000000,783000000,784000000,785000000,786000000,787000000,788000000,789000000,790000000,791000000,792000000,793000000,794000000,795000000,796000000,797000000,798000000,799000000,800000000,801000000,802000000,803000000,804000000,805000000,806000000,807000000,808000000,809000000,810000000,811000000,812000000,813000000,814000000,815000000,816000000,817000000,818000000,819000000,820000000,821000000,822000000,823000000,824000000,825000000,826000000,827000000,828000000,829000000,830000000,831000000,832000000,833000000,834000000,835000000,836000000,837000000,838000000,839000000,840000000,841000000,842000000,843000000,844000000,845000000,846000000,847000000,848000000,849000000,850000000,851000000,852000000,853000000,854000000,855000000,856000000,857000000,858000000,859000000,860000000,861000000,862000000,863000000,864000000,865000000,866000000,867000000,868000000,869000000,870000000,871000000,872000000,873000000,874000000,875000000,876000000,877000000,878000000,879000000,880000000,881000000,882000000,883000000,884000000,885000000,886000000,887000000,888000000,889000000,890000000,891000000,892000000,893000000,894000000,895000000,896000000,897000000,898000000,899000000,900000000,901000000,902000000,903000000,904000000,905000000,906000000,907000000,908000000,909000000,910000000,911000000,912000000,913000000,914000000,915000000,916000000,917000000,918000000,919000000,920000000,921000000,922000000,923000000,924000000,925000000,926000000,927000000,928000000,929000000,930000000,931000000,932000000,933000000,934000000,935000000,936000000,937000000,938000000,939000000,940000000,941000000,942000000,943000000,944000000,945000000,946000000,947000000,948000000,949000000,950000000,951000000,952000000,953000000,954000000,955000000,956000000,957000000,958000000,959000000,960000000,961000000,962000000,963000000,964000000,965000000,966000000,967000000,968000000,969000000,970000000,971000000,972000000,973000000,974000000,975000000,976000000,977000000,978000000,979000000,980000000,981000000,982000000,983000000,984000000,985000000,986000000,987000000,988000000,989000000,990000000,991000000,992000000,993000000,994000000,995000000,996000000,997000000,998000000};
vc<mint>val{360505342,780215459,372435678,418614595,520327800,546542455,1605249,200818716,706547124,308698529,334013511,586595783,878430431,652367248,190183443,722246516,631090252,356940586,551222090,232818884,187666330,937284923,150652391,874163876,661639239,869482392,8659537,289024567,970209168,65963104,118542509,393158834,242732721,399469498,909193581,849604713,806165538,691294461,834502659,305207030,413235298,491974748,200497448,578527474,763662726,620762675,212804469,607496987,470732383,830884507,864069314,190605100,840024726,547212792,491949663,847037302,933939038,752104997,520649867,724863740,482871591,153986378,846418142,58534447,965558899,8675520,254040111,447695201,483655959,892529670,547892851,309869189,522425949,920560252,123518345,20329478,585820306,565537877,176302898,353982253,480338174,569893538,754569648,964487759,903313980,916326120,199354206,158324133,413579036,89680060,611215272,785609029,482733798,529812885,865017385,304998053,328892922,735612023,118264680,791779710,129934413,288636052,419485244,105659085,596565729,342228669,517073829,676862556,328168433,669527739,799586011,886161805,59173702,202359706,193567918,677041559,302101312,894658912,346508249,580569886,952480912,264081430,643324717,776421447,906853200,61367733,126729720,305712276,899747035,555910961,38755763,493158704,803115146,851719145,530560858,234580573,535182609,965440448,804826748,870879834,988556056,58090382,241949076,806325963,265153760,120012956,601583314,62647609,850320736,223733526,527482511,763687355,223930132,367549025,876432887,194622537,474748563,458022993,612477270,147307597,355512363,437612781,896554974,458585588,445048352,327687352,640799783,795303753,491190466,735424638,176752904,88790855,994185147,671916430,933364733,440264236,848328083,420260428,428692643,704250972,625941337,960863280,834648628,727412683,677592478,113327119,487150553,763757245,518315877,419735073,713507376,254550013,770091533,612013673,556489010,814633540,788564072,276144168,410952978,303483821,90732481,699712073,515203812,217458540,281496554,424873970,465259566,388323425,84941001,197405329,705425033,128979208,400300650,435392751,576758373,964107641,234945692,964960071,901869706,505120874,772566968,232724371,901462246,911992018,212264045,200123673,76509088,263670017,627509015,315337439,774809326,826241582,952040949,421005594,335579026,178471767,143689073,291504965,499505547,567358614,852060284,98454290,95073303,617035093,876747353,806219506,394816898,869242549,294658376,541594903,872436151,938016156,533245973,770795575,809013679,943240400,186416122,132764914,632248458,89612294,136365453,567431053,724096307,80387566,413614935,549726969,225097179,38097534,634914899,321436935,541949088,332413823,337763100,816777943,17034469,885384794,909700616,776506233,166834962,614091430,368766400,862503306,513564100,841792172,734689322,129782572,466188420,27526711,951647141,394550823,768956882,921900462,316129552,22252468,448975128,868113734,979236193,784112544,557368277,745188109,574879030,314102424,512982956,963764989,923198334,236331000,691497801,811510039,437106780,902762325,83180182,33583996,411216950,31109731,223147797,92462678,536485857,232752986,69990221,973669534,380698845,831499033,504657680,636085849,659476852,519896859,646718535,952330002,222013942,96633245,829704938,887692978,138932711,65913665,965073423,636506947,643742038,726155671,168604708,971955839,311961724,948469225,170196789,335128677,322069021,567207869,416070741,238578837,520681722,24568427,113606063,605869759,967568779,458947530,211139903,853893957,795503248,423359228,40441271,122245912,981684868,346416264,583947239,751865438,588742732,820837835,673033467,936261139,405039728,628162443,583290933,885619745,51933527,88742382,964416749,755909862,417464714,876572717,545169958,525205202,688729424,144346027,171814135,677940457,482582296,464558698,28852005,434102464,805523261,939509067,770171779,727828322,784845053,326678022,795032718,659759319,839505405,800347196,47517171,934676557,703366433,440327198,290555721,585074654,167601352,700607402,414555777,621608476,90226160,609090975,384455615,904965643,499204668,338923305,577900626,955813591,609985886,117570302,877361036,20618092,979246498,736613634,807607518,290253740,333880588,539228264,523780371,649953370,90781454,466647451,453729194,590424962,297771452,411085136,682968172,258877855,510993812,319007095,447094773,472399422,245788336,518396367,877541194,512717509,117811415,374866752,237942482,791396773,822042255,758895755,401062879,428438982,543133769,634148087,409519739,346680477,534428832,543028743,919494855,869427081,94591167,566362862,450719490,1750261,306522903,620767396,513770361,114050009,662363797,942117792,922500926,123218949,837527175,792258402,495072095,656229939,368208077,40489970,848380051,368751275,722812741,134310039,793195236,11795594,706717042,338869942,837912563,331161332,815825430,98620132,434895030,521564766,873339857,788429138,841345362,84943105,771970255,608223336,125751783,530904025,56739512,467449149,281098362,736116377,219157059,288343388,325206292,347407853,903480640,69743991,131305409,995101386,290824360,14263357,251877386,408279544,199691901,591897998,128918936,390774357,29040889,420771441,707278153,54931328,917277109,17303009,380238239,781946288,216302411,26180059,668274171,950738776,90143733,172559539,751160799,207514844,15416030,662466567,298049583,398534479,490475402,760291266,937349030,123567285,21045319,473529232,933746952,832871141,342671168,949926427,512087072,636365935,273816335,164194986,70237888,824026011,131363110,77213040,872995952,212476272,698750792,577386238,435614415,945011317,488215592,94687647,288383563,531372400,837271627,299517334,708957525,382615221,489025321,721603503,342038576,762704635,995981174,128781406,928110460,491450826,431829891,828854079,714449042,431720119,197729068,100924760,513058446,173817175,726474160,416443923,185884836,714560066,726635892,71677109,340438506,146032138,428185993,334219474,195517915,630249299,638779126,710276444,40334500,911217891,567240569,707652676,769201448,121989448,639060235,215606487,614545536,217642428,408536344,217156640,746110785,589828115,482034915,793291820,61637103,755601851,138681035,514771293,57557008,667116404,206863234,762421856,462910272,407351633,441641135,798082585,493774765,705592857,900537615,780349544,686741088,288020484,816679962,165879592,417822157,610389159,218390727,507887675,692086096,757252970,643866871,59024681,472907600,12322764,784262413,68404777,4203523,251684442,22596564,703492842,545341297,745998520,983729314,678063269,753953885,677627542,956790038,35024564,606963901,629102006,812129281,845723241,719597113,801522474,600596327,245073614,45674322,921537895,106518874,471623033,623121503,626427576,603069738,87015983,145105265,253788094,552716494,430864380,962781365,856122145,726652164,372657066,578407981,873938460,130111472,26231817,71559367,270144780,790632221,216462044,70026408,835720526,927339147,272763185,558288251,492496590,244397660,699764672,435788632,498533929,773409226,270093711,667103894,766132472,458768936,593031744,828562891,92227345,116670173,1493274,4312648,646567063,530278799,336893916,974532272,362147635,340902005,564705255,669453435,297402772,713156281,26220558,315303986,144380086,944338920,317399155,90684223,251281780,94811845,898160057,134378083,433590834,908799685,246170832,995510770,191313819,951905361,571511597,996640903,489550415,37016643,828462591,694719503,196022199,70878578,236373705,85667260,211891648,405766374,915430538,788837897,522040363,275075983,136335166,831159282,572952122,80524856,427079340,530191939,771345873,224148218,748792301,117452012,745736591,293068452,629220052,909348113,987590563,444568630,110251345,507111814,564563300,548996295,269938653,129879130,645217078,47920547,865602826,123256305,321501044,170616769,800708678,880958223,34973529,180929256,561847417,898981819,300903681,495277228,632034830,63115122,620882339,296469953,325799230,549436326,518085061,575320956,742958106,976572103,882346439,16480567,296073277,635540747,853414193,599299916,883541759,879019665,887917964,155158507,544038765,377831068,188331863,985365289,822282851,625835629,366719207,958273254,365972536,694261562,865874964,347152004,989557597,480748406,564153313,770175076,945231444,846424171,642660729,273773774,27786718,677008356,707004468,554479422,65197988,626770595,157468656,195926157,158227360,946241961,19528334,24927874,641313480,382964957,440063257,842584453,431685477,909663141,718663288,293152010,907733627,461274316,641348732,850163281,150532208,659909381,367780543,142468006,791800354,582585182,229735127,247512943,38126687,260198083,350863099,818746940,774702697,29655706,420591417,411793136,894388597,375069406,277417577,299373430,127947814,287692217,645849160,741436938,198532875,488433484,786516942,241302499,264721205,209104028,492304836,920159155,110743926,43209707,247789597,278977325,791619630,268126844,97730617,508292755,129909820,822877110,349468598,4768365,764802911,608625453,160017099,949609111,77749663,201950016,477260210,136986765,865514366,55577030,834912765,41105733,931755218,531593867,716901879,342021458,915012420,73468679,696647568,934392850,694811717,358699332,186838007,285781569,926625101,264073284,33091497,374180606,216469298,141106746,90105500,905326377,290876269,629399413,686097310,409485626,274399760,405084504,715463669,203892935,600063707,342062534,129446590,409644729,390511442,601486842,711520498,188117009,905898445,129054017,317342635,596131370,642295206,7410026,227223115,241402055,313814037,764400669,628516334,543463438,164422751,718375817,843641520,846672661,924365092,459670634,900061196,420641180,869872944,355981787,190525406,228614993,793620144,813962739,862609441,312655028,952932806,288348438,722752665,67699724,438386879,856789597,497004810,155029922,780836638,866318685,871655454,565061584,9313423,139635202,795598554,105544809,306015802,822173403,486730370,934320137,908838402};
void solve(){
    LL(n);chmin(n,998244352);
    int idx=-1;
    rep(i,is.size()){
        if(is[i]<=n)idx=i;
    }
    mint ans=0;if(idx>=0)ans+=val[idx];
    int front=1;if(idx>=0)front=is[idx]+1;
    //[0,front)
    while(front<=n){
        mint mul=1;
        for(int k=1;;k++){
            ll n=kth_root(front,k);
            mul*=n;
            if(n==1)break;
        }
        ans+=mul;
        ++front;
    }
    PRT(ans);
    /*
    ll B=1e6;
    mint now=0;
    vc<ll>is;
    vc<mint>val;
    for(int i=1;i<=998244352;i++){
        mint mul=1;
        for(int k=1;;k++){
            ll n=kth_root(i,k);
            mul*=n;
            if(n==1)break;
        }
        now+=mul;

        if(i%B==0){
            cerr<<i<<"\n";
            is.pb(i);
            val.pb(now);
        }
    }
    cout<<"vc<ll>is{";rep(i,is.size()){
        if(i)cout<<",";cout<<is[i];
    }
    cout<<"};\n";
    cout<<"vc<mint>val{";rep(i,val.size()){
        if(i)cout<<",";cout<<val[i];
    }
    cout<<"};\n";*/
}
signed main(){
    dbg("==============="s);
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cout<<fixed<<setprecision(20);
    int t=1;
    // cin >> t;
    while(t--)solve();
}