#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
//#define umap unordered_map
#define umap __gnu_pbds::cc_hash_table
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
#define invarg invalid_argument
#define cus_throw(msg) throw invarg(string(msg) + " at " + __FILE__ + ":" + to_string(__LINE__))
random_device rndv;
mt19937 rd(rndv());
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const vector<ll> millerrabin = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
const double eps = 1e-8;
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();if(c=='-'){k=-1;}}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9'));return ret*k;}
inline void read(ll&x){x=readll();}
inline char readchar(){char ret;do{ret=getchar();}while(ret<=32);return ret;}
inline void read(char&x){x=readchar();}
inline string readstr(){string ret;char c;do{c=getchar();}while(c<=32);do{ret+=c;c=getchar();}while((c>32)&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}if(x<0){putchar('-');x*=-1;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
inline ostream& operator<<(ostream& out, __int128 x){if(!x){out<<"0";return out;}if(x<0){out<<"-";x*=-1;}char op[40]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){out<<op[cur--];}return out;}


namespace modint {
    const ll MOD = 1;
    struct modint {
        ll val, mod;
        void setmod(ll x) {
            mod = x;
        }
        explicit operator ll() {
            return val;
        }
        modint() {
            val = 0, mod = MOD;
        }
        modint(__int128 v, ll m = MOD) {
            if (m == 1) {
                cus_throw("init modint without mod");
            }
            v %= m;
            if (v < 0) {
                v += m;
            }
            val = v;
            mod = m;
        }
    };
    #define chkmod(x, y) if (x.mod != y.mod) cus_throw("mod isn't the same")
    modint operator+(modint x, modint y) {
        chkmod(x, y);
        return modint(x.val + y.val, x.mod);
    }
    modint operator-(modint x, modint y) {
        chkmod(x, y);
        return modint(x.val - y.val, x.mod);
    }
    modint operator*(modint x, modint y) {
        chkmod(x, y);
        return modint(__int128(1) * x.val * y.val, x.mod);
    }
    modint qpow(modint x, ll y) {
        if (!y) {
            return modint(1, x.mod);
        } else if (y & 1) {
            return x * qpow(x, y ^ 1);
        } else {
            return qpow(x * x, y >> 1);
        }
    }
    modint inv(modint x) {
        return qpow(x, x.mod - 2);
    }
    modint operator/(modint x, modint y) {
        chkmod(x, y);
        if (ll(y) == 0) {
            cus_throw("modint divide by 0");
        }
        return x * inv(y);
    }
    modint operator+=(modint& x, modint y) {
        return x = x + y;
    }
    modint operator-=(modint& x, modint y) {
        return x = x - y;
    }
    modint operator*=(modint& x, modint y) {
        return x = x * y;
    }
    modint operator/=(modint& x, modint y) {
        return x = x / y;
    }
    bool operator==(modint x, modint y) {
        chkmod(x, y);
        return x.val == y.val;
    }
}