#include <bits/stdc++.h>
using namespace std;

// --------------------------------------------------------------------------------------------------------------

#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

namespace VvyLw {
namespace Twitter {
void wa_haya_exe(){ cin.tie(nullptr); ios::sync_with_stdio(false); }
}
void solve();
}; // VvyLw

mt19937 Random() {
    random_device seed_gen;
    mt19937 engine {seed_gen()};
    return engine;
}

// --------------------------------------------------------------------------------------------------------------

template <class T> using V = vector<T>;
template <class T, class U> using P = pair<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqr = priority_queue<T,V<T>,greater<T>>;
template <class T, class U> using pqs = priority_queue<P<T,U>>;
template <class T, class U> using pqrs = priority_queue<P<T,U>,V<P<T,U>>,greater<P<T,U>>>;
template <class T, class U> bool chmax(T& a, const U& b) { if (a<b) { a=b; return 1; } return 0; }
template <class T, class U> bool chmin(T& a, const U& b) { if (a>b) { a=b; return 1; } return 0; }
template <class T, class U> inline bool overflow_if_add(T a, U b) { return (numeric_limits<T>::max()-a)<b; }
template <class T, class U> inline bool overflow_if_mul(T a, U b) { return (numeric_limits<T>::max()/a)<b; }
using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
namespace pairs {
template <class T> using PP = pair<T,T>;
template<class T> PP<T> operator+(const PP<T>& a, const PP<T>& b) { return {a.first + b.first, a.second + b.second}; }
template<class T> PP<T> operator-(const PP<T>& a, const PP<T>& b) { return {a.first - b.first, a.second - b.second}; }
template<class T> PP<T> operator-(const PP<T>& a) { return {-a.first, -a.second}; }
template<class T, class U> PP<T> operator*(const PP<T>& a, const U& b) { return {a.first * b, a.second * b}; }
template<class T, class U> PP<T> operator/(const PP<T>& a, const U& b) { return {a.first / b, a.second / b}; }
template<class T> PP<T>& operator+=(PP<T>& a, const PP<T>& b) { return a = a + b; }
template<class T> PP<T>& operator-=(PP<T>& a, const PP<T>& b) { return a = a - b; }
template<class T, class U> PP<T>& operator*=(PP<T>& a, const U& b) { return a = a * b; }
template<class T, class U> PP<T>& operator/=(PP<T>& a, const U& b) { return a = a / b; }
template<class T> PP<T> rotate(const PP<T>& a) { return {-a.second, a.first}; } // 90 degree ccw
template<class T> T dot(const PP<T>& a, const PP<T>& b) { return a.first * b.first + a.second * b.second; }
template<class T> T cross(const PP<T>& a, const PP<T>& b) { return dot(rotate(a), b); }
template<class T> T square(const PP<T>& a) { return dot(a, a); }
template<class T> ld abs(const PP<T>& a) { return hypotl(a.first, a.second); }
template<class T> T gcd(const PP<T>& a) { return gcd(a.first, a.second); }
template<class T> PP<T> normalize(PP<T> a) {
    if(a == PP<T>{}) return a;
    a /= gcd(a);
    if(a < PP<T>{}) a = -a;
    return a;
}
} // pairs
using namespace pairs;
using vi = V<ll>;
using vu = V<ul>;
using vd = V<ld>;
using vc = V<char>;
using vs = V<string>;
using vb = V<bool>;
using wi = V<vi>;
using wu = V<vu>;
using wd = V<vd>;
using wc = V<vc>;
using ws = V<vs>;
using wb = V<vb>;
using pi = PP<ll>;
using pd = PP<ld>;
using pc = PP<char>;
using ps = PP<string>;
const int dx[]={-1,-1,-1,0,0,1,1,1};
const int dy[]={-1,0,1,-1,1,-1,0,1};
const int MOD = 998244353;
const int M0D = 1000000007;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const double PI = acos(-1);
const double E = 2.718281828459045;

#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<n; ++i)
#define rep2(i,n) for(ll i=0; i<n; ++i)
#define rep3(i,a,b) for(ll i=a; i<=b; ++i)
#define rep4(i,a,b,c) for(ll i=a; i<=b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define loop(i,a,b,c) for(ll i=a; i<b; i=c)
#define rvp1(n) for(ll i=n-1; i>=0; i--)
#define rvp2(i,n) for(ll i=n-1; i>=0; i--)
#define rvp3(i,a,b) for(ll i=a; i>=b; i--)
#define rvp4(i,a,b,c) for(ll i=a; i>=b; i-=c)
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(v) v.rbegin(),v.rend()
#define rall2(v,a) v.rbegin(),v.rbegin()+a
#define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<n; ++i)
#define sqrp2(i,n) for(ll i=0; i*i<n; ++i)
#define sqrp3(i,a,b) for(ll i=a; i*i<b; ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)
#define irp(it,v) for(auto it=v.begin(); it!=v.end(); ++it)
#define ir(it,v) for(auto it=v.begin(); it!=v.end();)
#define FE(v,f) for_each(all(v),f)

namespace IO {
template <class T> void scan(T& a){ cin >> a; }
template <class T, class U> void scan(P<T,U>& p){ scan(p.first); scan(p.second); }
template <class T> void scan(V<T>& a){ for(auto &i: a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
template <class T> void print(const T& a){ cout << a; }
template <class T, class U> void print(const P<T,U>& p){ print(p.first); cout<<" "; print(p.second); }
template <class T> void print(const V<T>& a){ if(!a.empty()){ print(a[0]); for(auto i=a.begin(); ++i!=a.end();){ cout<<" "; print(*i); } } }
void bl(){ cout<<' '; }
void out(){ cout<<'\n'; }
template <class T> void out(const T& t){ print(t); cout<<'\n'; }
template <class Head, class... Tail> void out(const Head& head, const Tail&... tail) { print(head); cout<<" "; out(tail...); }
template <class T> void vout(V<T>& v) { FE(v,[](T x){out(x);}); }
void fix(short x){ cout << fixed << setprecision(x); }
void Alpha(){ cout << boolalpha; }
void Flush(){ flush(cout); }
}; // IO
using namespace IO;
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size); in(name)
#define WEC(type,name,h,w) V<V<type>> name(h,V<type>(w)); in(name)
#define fin(...) do{ out(__VA_ARGS__); return; }while(false)

namespace yesno_sys {
inline void YES(bool ok=1) { out(ok?"YES":"NO"); }
inline void NO(bool ok=1) { YES(!ok); }
inline void Yes(bool ok=1) { out(ok?"Yes":"No"); }
inline void No(bool ok=1) { Yes(!ok); }
inline void yes(bool ok=1) { print(ok?"yes":"no"); }
inline void no(bool ok=1) { yes(!ok); }
}; // yesno_sys
using namespace yesno_sys;

#ifdef local
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) static_cast<void>(0)
#endif
#define elif else if
#define scp(a,x,b) a<=x&&x<=b
#define eid(el,v) &el-&v[0]
#define mp make_pair
#define mt make_tuple
#define gt(tpl,x) get<x>(tpl)
#define bif(bit,tar) (tar>>bit)&1
#define nxp(x) next_permutation(all(x))
#define prp(x) prev_permutation(all(x))
#define strpl(s,a,b) regex_replace(s,regex(a),b)
#define rgxmt(s,rgx) regex_match(s,regex(rgx))
namespace zia_qu {
inline ll Mod(ll x, ll m){ return (x+m)%m; }
inline ll sqr(ll x){ return x*x; }
inline ll cub(ll x){ return x*x*x; }
inline ul Pow(ul a, uint b) { 
    ul res=1;
    while(b>0) {
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
inline ll Ceil(ld x, ll m){ return ceil(x/m); }
inline ld Round(ld x, ll m, uint fx){ if(fx==0) return (ll)round(x/m); else { ul y=Pow(10,fx+1); return round((x*y)/m/y); } }
inline ld Log(ll x, int e){ return log(x)/log(e); }
inline int bitdigit(ll x){ return 64-__builtin_clzll(x); }
inline int popcnt(ll x){ return __builtin_popcountll(x); }
inline bool popcnt_OE(ll x){ return __builtin_parityll(x); }
inline int fione(ll x){ return __builtin_ffsll(x); }
inline int zrcnt(ll x){ return __builtin_ctzll(x); }
inline void strins(string &s, string t, ll id){ s.insert(id,t); }
inline string toupper(string s){ each(c,s) c=std::toupper(c); return s; }
inline string tolower(string s){ each(c,s) c=std::tolower(c); return s; }
inline string to_hex(ll x) {
    stringstream ss;
    ss<<hex<<x;
    string s=ss.str();
    //s=toupper(s);
    return s;
}
inline string to_oct(ll x) {
    stringstream s;
    s<<oct<<x;
    return s.str();
}
inline string to_bin(ll x) {
    stringstream s;
    s<<bitset<64>(x);
    return s.str();
}
inline ll to_ten(string s, short base){ return stoll(s,nullptr,base); }
inline vi ten_to_adic(ll m, ll n) {
    vi res;
    ll now=m;
    while(now!=0) {
        res.emplace_back(now%n);
        now/=n;
    }
    //rev(res);
    return res;
}
inline ll adic_to_ten(vi &v, ll u) {
    ll res=0;
    //rev(v);
    each(el,v) {
        ll idx=eid(el,v);
        res+=Pow(u,idx)*el;
    }
    return res;
}
template <class... T> constexpr auto symin(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }
template <class... T> constexpr auto symax(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }
template <class K, class V> inline K kymin(const map<K,V> m){ return m.begin()->first; }
template <class K, class V> inline K kymax(const map<K,V> m){ return m.rbegin()->first; }
template <class K, class V> inline V kymin_v(const map<K,V> m){ return m.begin()->second; }
template <class K, class V> inline V kymax_v(const map<K,V> m){ return m.rbegin()->second; }
template <class K, class V> inline V vlmin(map<K,V> &m){
    auto pr = *min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second > y.second; });
    return pr.second;
}
template <class K, class V> inline V vlmax(map<K,V> &m){
    auto pr = *max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.second;
}
template <class K, class V> inline K vlmin_k(map<K,V> &m){
    auto pr = *min_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second > y.second; });
    return pr.first;
}
template <class K, class V> inline K vlmax_k(map<K,V> &m){
    auto pr = *max_element(all(m),[](P<K,V> const &x, P<K,V> const &y){ return x.second < y.second; });
    return pr.first;
}
template <class T> inline T stmin(set<T> s){ return *s.begin(); }
template <class T> inline T stmax(set<T> s){ return *s.rbegin(); }
}; // zia qu

namespace Lady_sANDy {
template <class T> inline void rev(T& v){ reverse(all(v)); }
template <class T> inline void rev(T& v, ll a, ll b){ reverse(all(v,a,b)); }
template <class T> inline void Sort(T& v){ sort(all(v)); }
template <class T> inline void Sort(T& v, ll a, ll b){ sort(all(v,a,b)); }
template <class T> inline void Sortt(T& v){ sort(rall(v)); }
template <class T> inline void Sortt(T& v, ll a, ll b){ sort(rall(v,a,b)); }
template <class T> inline void Sorth(T& v){ make_heap(all(v)); sort_heap(all(v)); }
template <class T, class I> inline ll dst(T& v, I itr){ return distance(v.begin(),itr); }
template <class T, class I> inline ll dstl(T& v, I itr){ return distance(itr,v.end()); }
template <class T> inline T mrg(T& a, T& b){ T res; merge(all(a),all(b),back_inserter(res)); return res; }
template <class T> inline T Min(const V<T>& v){ return *min_element(all(v)); }
template <class T> inline T Max(const V<T>& v){ return *max_element(all(v)); }
template <class T> inline ll Min_i(const T& v){ return dst(v,min_element(all(v))); }
template <class T> inline ll Max_i(const T& v){ return dst(v,max_element(all(v))); }
template <class T, class U> inline ll LB(const T& v, const U x){ return dst(v,lower_bound(all(v),x)); }
template <class T, class U> inline ll UB(const T& v, const U x){ return dst(v,upper_bound(all(v),x)); }
template <class T, class U> inline bool BS(const T& v, const U x){ return binary_search(all(v),x); }
template <class T, class U, class Boolean> inline bool BS(const T& v, const U x, Boolean fn){ return binary_search(all(v),x,fn); }
template <class T, class Boolean> inline bool All(const T& v, Boolean fn){ return all_of(all(v),fn); }
template <class T, class Boolean> inline bool Exist(const T& v, Boolean fn){ return any_of(all(v),fn); }
template <class T, class Boolean> inline void pt(T& v, Boolean fn){ partition(all(v),fn); }
template <class T, class Boolean> inline ll ptp(T& v, Boolean fn){ return dst(v,partition_point(all(v),fn)); }
template <class T, class U> inline ll Find(T& v, const U x){ auto itr=find(all(v),x); if(itr==v.end()) return -1LL; return dst(v,itr); }
template <class T, class U> inline void rpl(T& v, U fn, U r){ replace(all(v),fn,r); }
template <class T, class Boolean, class U> inline void rplif(T& v, Boolean fn, U r){ replace_if(all(v),fn,r); }
template <class T, class Boolean> inline ul cntif(T& v, Boolean fn){ return count_if(all(v),fn); }
template <class T> inline T Count(V<T>& v, ll x) { /* Sort(v); //*/ return UB(v,x)-LB(v,x); }
template <class T> inline T IP(const V<T>& v, const V<T>& u, T init){ return inner_product(all(v),u.begin(),init); }
template <class T> inline V<T> iot(T n, ll init){ V<T> a(n); iota(all(a),init); return a;}
template <class T> inline void vins(V<T>& v, T x, ll id){ v.insert(v.begin()+id,x); }
template <class T, class U> inline void vins(T& v, U u, ll id){ v.insert(v.begin()+id,all(u)); }
template <class T, class U> inline void vins(T& v, U u, ll id, ll a, ll b){ v.insert(v.begin()+id,all(u,a,b)); }
template <class T, class U> inline ll ers(T& v, U x){ v.erase(remove(all(v),x),v.end()); return v.size(); }
template <class T, class Boolean> ll ersif(T& v, Boolean x){ v.erase(remove_if(all(v),x),v.end()); return v.size(); }
template <class T> inline ll unq(T& v){ Sort(v); v.erase(unique(all(v)),v.end()); return v.size(); }
template <class T> inline bool eql(const T& v, const T& w){ return (v.size()==w.size() && equal(all(v),w.begin())); }
template <class T> inline T cp(const T& v){ T res; copy(all(v),back_inserter(res)); return res; }
template <class T> inline T cp(const T& v, ll a, ll b){ T res; copy(all(v,a,b),back_inserter(res)); return res; }
template <class T> inline void rtt(T& s, ll idx){ ll id=zia_qu::Mod(idx,s.size()); rotate(all(s,id),s.end());  }
template <class T> inline void rtt(T& s, ll a, ll b, ll c){ rotate(all(s,a,b),s.end()-c);  }
template <class T> inline V<T> psum(V<T>& v) {
    V<T> s(v.size()+1);
    partial_sum(all(v),s.begin());
    rtt(s,-1);
    return s;
}
template <class T> inline V<T> adf(V<T>& v) {
    V<T> res(v.size());
    adjacent_difference(all(v),res.begin());
    rtt(res, 1);
    res.resize(v.size()-1);
    return res;
}
#ifdef local
#define rext(...) static_cast<vi>(0)
template <class T> inline ll vsum(V<T> &v){ return accumulate(all(v),0LL); }
template <class T> inline ll vsum(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),0LL); }
template <class T> inline ld vdsum(V<T> &v){ return accumulate(all(v),0.0L); }
template <class T> inline ld vdsum(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),0.0L); }
template <class T> inline ll vmul(V<T> &v){ return accumulate(all(v),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ll vmul(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v){ return accumulate(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); }
#else
template <class T> inline V<T> rext(V<T>& v, mt19937 eng, ll size){ V<T> res; sample(all(v),back_inserter(res),size,eng); return res; }
template <class T> inline T rext(V<T>& v, mt19937 eng){ V<T> res; sample(all(v),back_inserter(res),1,eng); return res.front(); }
template <class T> inline ll vsum(V<T> &v){ return reduce(all(v),0LL); }
template <class T> inline ll vsum(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),0LL); }
template <class T> inline ld vdsum(V<T> &v){ return reduce(all(v),0.0L); }
template <class T> inline ld vdsum(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),0.0L); }
template <class T> inline ll vmul(V<T> &v){ return reduce(all(v),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ll vmul(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v){ return reduce(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); }
#endif
}; // Lady s&y

namespace Heileden {
/* BFS Sample
template <class T> inline void bfs(V<V<T>>& g, T start, vb& visited) {
    queue<T> que;
    que.emplace(start);
    visited[start]=1;
    while(!que.empty()) {
        T v=que.front();
        que.pop();
        each(nv,g[v]) {
            if(!visited[nv]) {
                visited[nv]=1;
                que.emplace(nv);
            }
        }
    }
}//*/

/* DFS Sample
template <class T> inline void dfs(V<V<T>>& g, T v, vb& visited) {
    visited[v]=1;
    each(nv,g[v]) if(!visited[nv]) dfs(g,nv,visited);
}//*/

/* Permutation Sample
template <class T> inline void nPr(V<T>& v) {
    Sort(v);
    do {out(v);} while(nxp(v));
}//*/

/* Binary Search Sample
template <class T, class U> inline ll MGRBS(T v, U x, ll& ng, ll& ok) {
    while(abs(ok-ng)>1) {
        ll mid = (ok+ng)/2;
        if(v[mid]==x) ok=mid;
        else ng=mid;
    }
    return ok;
}//*/

/* Dijikstra-like Sample
template <class T> inline T dijikstra(const V<T>& v) {
    pqr<T> pq;
    T res=0;
    while(!pq.empty()) {
        each(el,v) pq.emplace(el+res);
        res=pq.top();
        pq.pop();
    }
    return res;
}//*/

// divisor
template <class T> inline V<T> divisor(T n) {
    V<T> div;
    sqrp(i,1,n+1) {
        if(n%i==0) {
            div.emplace_back(i);
            if(i*i!=n) div.emplace_back(n/i);
        }
    }
    Lady_sANDy::Sort(div);
    return div;
}

// prime judge
inline bool is_prime(ul n) {
    if(n==1) return 0;
    sqrp(i,2,n+1) if(n%i==0) return 0;
    return 1;
}

// Siege of Eratosthenes
inline vb SoE(ll n) {
    vb prime(n+1,1);
    if(n>=0) prime[0]=0;
    if(n>=1) prime[1]=0;
    sqrp(i,2,n+1) {
        if(!prime[i]) continue;
        rep(j,i*i,n+1,i) prime[j]=0;
    }
    return prime;
}

// prime factor
template <class T> inline V<PP<T>> prmfct(T n) {
    V<PP<T>> res;
    rep(i,2,n+1) {
        if(n%i!=0) continue;
        T tmp=0;
        while(n%i==0) {
            tmp++;
            n/=i;
        }
        res.emplace_back(i,tmp);
    }
    if(n!=1) res.emplace_back(n,1);
    return res;
}

// Manacher
V<int> manacher(const string &s) {
    const int n = s.size();
    V<int> radius(n);
    int i = 0, j = 0;
    while(i < n) {
        while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) ++j;
        radius[i] = j;
        int k = 1;
        while(i - k >= 0 && i + k < n && k + radius[i - k] < j) {
            radius[i + k] = radius[i - k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return radius;
}

// factorial
template <class T> T factorial(T n) {
    T res=1;
    while(n>0) res*=n--;
    return res;
}

// permutation
template <class T> T perm(T n, T r) {
    T tmp=n;
    T res=1;
    while(n>tmp-r) res*=n--;
    return res;
}

// binomial
template <class T> T binom(T n, T r) {
    if(r < 0 || n < r) return 0;
    T ret = 1;
    rep(i,1,r) {
        ret *= n--;
        ret /= i;
    }
    return ret;
}

// integer judge
inline bool is_int(ld n){ ll r=floor(n); return r==n; }
inline bool is_sqr(ll n){ return is_int(sqrt(n)); }

/* grundy sample
template <class T> inline bool grundy(V<T> v) {
    ll res=0;
    each(el,v) res^=el;
    return res!=0;
}//*/
}; // Heileden

//constexpr const int mod=MOD;
constexpr const int mod=M0D;
struct mint{
    uint num = 0;
    constexpr mint() noexcept {}
    constexpr mint(const mint &x) noexcept : num(x.num){}
    constexpr operator ll() const noexcept { return num; }
    constexpr mint& operator+=(mint x) noexcept { num += x.num; if(num >= mod) num -= mod; return *this; }
    constexpr mint& operator++() noexcept { if(num == mod - 1) num = 0; else num++; return *this; }
    constexpr mint operator++(int) noexcept { mint ans(*this); operator++(); return ans; }
    constexpr mint operator-() const noexcept { return mint(0) -= *this; }
    constexpr mint& operator-=(mint x) noexcept { if(num < x.num) num += mod; num -= x.num; return *this; }
    constexpr mint& operator--() noexcept { if(num == 0) num = mod - 1; else num--; return *this; }
    constexpr mint operator--(int) noexcept { mint ans(*this); operator--(); return ans; }
    constexpr mint& operator*=(mint x) noexcept { num = ul(num) * x.num % mod; return *this; }
    constexpr mint& operator/=(mint x) noexcept { return operator*=(x.inv()); }
    template<class T> constexpr mint(T x) noexcept {
        using U = typename conditional<sizeof(T) >= 4, T, int>::type;
        U y = x; y %= U(mod); if(y < 0) y += mod; num = uint(y);
    }
    template <class T> constexpr mint operator+(T x) const noexcept { return mint(*this) += x; }
    template <class T> constexpr mint& operator+=(T x) noexcept { return operator+=(mint(x)); }
    template <class T> constexpr mint operator-(T x) const noexcept { return mint(*this) -= x; }
    template <class T> constexpr mint& operator-=(T x) noexcept { return operator-=(mint(x)); }
    template <class T> constexpr mint operator*(T x) const noexcept { return mint(*this) *= x; }
    template <class T> constexpr mint& operator*=(T x) noexcept { return operator*=(mint(x)); }
    template <class T> constexpr mint operator/(T x) const noexcept { return mint(*this) /= x; }
    template <class T> constexpr mint& operator/=(T x) noexcept { return operator/=(mint(x)); }
    constexpr mint inv() const noexcept { ll x = 0, y = 0; extgcd(num, mod, x, y); return x; }
    static constexpr ll extgcd(ll a, ll b, ll &x, ll &y) noexcept { ll g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; }
    constexpr mint pow(ul x) const noexcept { mint ans = 1, cnt = *this; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; }
    friend ostream& operator<<(ostream& os, const mint& m){ os << m.num; return os; }
    friend istream &operator>>(istream &is, mint &a) {
        ll t;
        is >> t;
        a=mint(t);
        return (is);
    }
};
#define MINT(...) mint __VA_ARGS__; in(__VA_ARGS__)
using vm = V<mint>;
using wm = V<vm>;
using pm = PP<mint>;
vm fac(1,1),inv(1,1);
void reserve(ll a){
    if(fac.size()>=a) return;
    if(a<fac.size()*2) a=fac.size()*2;
    if(a>=mod) a=mod;
    while(fac.size()<a) fac.emplace_back(fac.back()*mint(fac.size()));
    inv.resize(fac.size());
    inv.back()=fac.back().inv();
    for(ll i=inv.size()-1; !inv[i-1]; i--) inv[i-1]=inv[i]*i;
}
mint fact(ll n){ if(n<0) return 0; reserve(n + 1); return fac[n]; }
mint nPr(ll n,ll r){
    if(r<0 || n<r) return 0;
    if(n>>24){ mint ans=1; rep(r) ans*=n--; return ans; }
    reserve(n+1); return fac[n]*inv[n-r];
}
mint nCr(ll n,ll r){ if(r<0 || n<r) return 0; r=min(r,n-r); reserve(r+1); return nPr(n,r)*inv[r]; }
mint nHr(ll n,ll r){ if(!n && !r) return 1; if(n<=0 || r<0) return 0; return nCr(n+r-1,r); }

// --------------------------------------------------------------------------------------------------------------

using namespace zia_qu;
using namespace Lady_sANDy;
using namespace Heileden;

int main() {
    VvyLw::Twitter::wa_haya_exe();
    /*INT(t); while(t--)//*/
    VvyLw::solve();
}

// --------------------------------------------------------------------------------------------------------------


void VvyLw::solve() {
    const int rng=1e6;
    /*rep(i,1,1000) {
        ll x=i*1000LL;
        print(fact(x));
        out(',');
    }//*/
    ll a[]={0,
    641419708,
100292593,
341406877,
593395757,
541108809,
969117405,
849641758,
532467852,
299200938,
531950728,
682831525,
577889084,
153223816,
927344283,
576865589,
317614965,
645000912,
810673643,
483115382,
368774859,
11347322,
766392363,
701339131,
965651681,
232201666,
77721395,
267878880,
806918317,
994209082,
548996970,
831650911,
200360748,
31612358,
981996609,
835874618,
67347184,
715730781,
139475086,
840550890,
422550956,
703248501,
320014428,
473720669,
246899301,
820210693,
78896243,
404489692,
473058849,
784876961,
737935835,
570111271,
445302346,
993964922,
703924556,
553695703,
307636910,
9410113,
387514542,
821332424,
309944332,
667808941,
364031813,
26031301,
616292959,
392352826,
727093888,
716823510,
972353660,
837816787,
296716438,
256832184,
604632373,
993845228,
687268896,
796945456,
388289544,
130425525,
135821388,
293931387,
65533322,
706983555,
645452094,
429183481,
808037302,
840311971,
314136411,
284583633,
19122513,
583838047,
851076783,
495303973,
591254491,
820309560,
894437844,
978160598,
318526308,
78568538,
300098050,
781314189,
457992974,
810232079,
133097627,
482100617,
356519615,
755011148,
139468211,
301044356,
268147727,
90312874,
559938709,
477645764,
259920986,
609542121,
848001963,
436467039,
126142258,
975976294,
426153882,
851177716,
118586228,
858440059,
170487827,
36333448,
584611895,
319001333,
849250992,
779262371,
411557429,
536809703,
177829816,
46648320,
350302884,
960114799,
430900437,
653893017,
902349808,
642672336,
981466142,
841137570,
830760447,
504975434,
289509856,
507591365,
175583016,
190233572,
973411258,
640470390,
82067555,
285589169,
240586351,
941855646,
962394741,
888183450,
870741191,
198661311,
996128105,
306612706,
770455357,
585184040,
611862881,
571451636,
725655669,
823629411,
610766863,
456839561,
59996720,
265818227,
763184678,
186848069,
267145356,
920680841,
101278761,
987532374,
328110256,
312778040,
135914446,
806422332,
699703979,
362695335,
334356152,
906332280,
201761485,
647824348,
105501058,
640326947,
981027538,
584596772,
258397918,
87518070,
706226766,
887434314,
475800730,
440981254,
312608844,
678649477,
8289646,
646019716,
358757469,
257510447,
107146451,
491522320,
147390880,
187390946,
757515880,
219920862,
44598880,
781183727,
60971813,
378587118,
469491375,
342662199,
581534598,
911385887,
553154844,
649693772,
265358995,
167531559,
914563847,
483118873,
469619345,
107802802,
884720651,
530892398,
752000194,
660136491,
631467899,
293250339,
66680976,
689081385,
630906046,
871684010,
666124073,
345576459,
790014252,
6260416,
75003243,
911204757,
687694799,
172759290,
658967159,
61958696,
412185586,
184191744,
247050552,
987459542,
161463264,
723857507,
409855571,
289369921,
50180518,
548694181,
245357084,
129182064,
734897297,
456901092,
571220378,
477539220,
512704957,
221466432,
287209856,
60620791,
737403289,
753575706,
233151863,
839142168,
234240119,
417984149,
229679385,
429481467,
372045574,
22998498,
373583894,
713548056,
267330203,
389741527,
933690870,
41189219,
77938347,
987021716,
702584502,
788463623,
572702990,
350661070,
781966098,
305275963,
206775296,
962715789,
229585834,
119569247,
210306242,
416150817,
690126643,
522802765,
342229409,
564464342,
368788183,
614079877,
607847441,
88465660,
373281933,
213838802,
719843924,
507977466,
19434639,
243959960,
395942940,
118168258,
684953395,
179081719,
330131954,
70110549,
618257200,
62863595,
777843045,
980418272,
309626261,
535376485,
636217986,
143096434,
179035946,
956278383,
621703982,
725715228,
857767425,
345832821,
213633073,
157532098,
487537111,
849801425,
642845435,
319149940,
896653343,
680264051,
205250346,
514145995,
780942965,
949985635,
215648079,
880496572,
293008185,
851438222,
202569677,
654458787,
927957860,
784412643,
794249305,
682107141,
116954611,
35653891,
889591949,
893679312,
907890404,
324869834,
467772374,
101532178,
943477841,
456633619,
708568481,
597831736,
832275593,
651178524,
412586966,
277308197,
990832219,
816594770,
460267027,
845063865,
171979335,
819381912,
783222990,
405337586,
288986879,
675480585,
805877048,
948901511,
855554180,
771180772,
65150285,
827439539,
698245208,
876778508,
203416423,
483631820,
96765717,
695232868,
477301732,
653468216,
79323369,
198992295,
968856847,
633491376,
976492434,
826678580,
808037739,
902461680,
614351373,
528441544,
182548361,
980133727,
559805077,
869383939,
978840326,
314000690,
959000834,
856005428,
274125098,
36011898,
995577108,
766216019,
612250579,
688073752,
547647475,
467665755,
109124789,
359405516,
456925520,
635445587,
967029794,
725329636,
425371772,
796856205,
620903151,
807954218,
338506329,
663019841,
33156533,
791113302,
621098959,
396744531,
408721018,
746665783,
511662841,
508293995,
788458324,
544799669,
287745397,
50154413,
427103363,
381189839,
227278675,
900074435,
613534600,
500552894,
181975257,
879019034,
849029423,
919052656,
668500633,
690172889,
231684727,
678222565,
23645260,
621285071,
515317957,
823744253,
146879070,
443685005,
146221861,
846117791,
711739673,
832122283,
329569053,
686640047,
665423642,
535260540,
32793033,
682135041,
381619272,
417013856,
93615261,
932155204,
629353676,
10320907,
232170568,
365882953,
580983135,
208004913,
294111525,
540405918,
795156156,
701650729,
546421276,
123385585,
414060514,
125749926,
149514118,
376290090,
386531804,
758161115,
111810641,
845093102,
419209336,
188285206,
124927837,
298448241,
683580606,
233924038,
778924854,
445611924,
154425679,
201302388,
293094634,
140124904,
112582078,
387646221,
6016511,
830383992,
607689609,
403236459,
950741508,
456882249,
804138346,
890701069,
504444082,
637461484,
940358287,
183538116,
964032960,
654516661,
384634755,
320725827,
44821033,
203932527,
622395046,
45824090,
593532124,
745956370,
244072502,
743994983,
797824545,
58780355,
709819079,
691933729,
321792583,
288222406,
226144630,
356125631,
934717533,
361576010,
581839401,
913952661,
726388121,
965187412,
935299955,
606242968,
924880898,
666371168,
229919917,
528356427,
899281002,
180647802,
31241308,
332987642,
805616393,
877036688,
95654799,
866698670,
610035146,
596367345,
343434222,
936251061,
134707066,
523794633,
171237061,
792695537,
262405894,
340930969,
553872179,
150308900,
924042332,
570505384,
879176764,
990648856,
469386997,
886642171,
943765912,
453569392,
797540981,
761809226,
973241307,
61894919,
627333027,
510402437,
828208151,
56956114,
222104605,
652791086,
739140505,
191124935,
253333132,
914889888,
145298115,
312001483,
793332112,
484733770,
276302316,
843557645,
866898497,
165404163,
679209364,
685318173,
998767109,
107702632,
931423638,
473989428,
449656911,
760653417,
887485139,
622697268,
663967499,
605515890,
247778530,
162217217,
833476199,
665612111,
227641050,
624962767,
158177667,
836560196,
840761205,
777445472,
323916364,
737463916,
833673413,
783459896,
815002850,
492028082,
758133380,
72763520,
567656070,
53294986,
913030124,
419797592,
501255706,
677098815,
988378213,
439726371,
329175197,
500823768,
152546903,
183307819,
665282791,
235331099,
48393618,
707642533,
914607739,
749786216,
118339569,
250507905,
44613330,
153358347,
314934847,
730704051,
701953715,
780803591,
175666781,
92548653,
719749095,
358043484,
82447511,
960887141,
14669256,
762121346,
597698852,
664902098,
242967280,
406122994,
544735003,
603880634,
402958911,
124401812,
985591894,
361809997,
904417343,
868744334,
920050913,
896281364,
774264645,
619391846,
571952764,
908418682,
196156559,
491432439,
297444905,
812822843,
622705850,
754770420,
451361308,
553774704,
757842436,
711948902,
500713207,
754926023,
211374774,
378912980,
408668259,
12280499,
835797831,
448175753,
526226141,
293959562,
445257455,
997840405,
322571901,
588225665,
345435435,
261918860,
104050332,
232529758,
184978106,
975900312,
531377426,
251176948,
229118010,
882183133,
513537151,
50867573,
567520164,
624888472,
402043945,
121376335,
908318314,
912816423,
211604803,
876694648,
165819171,
181767292,
71245470,
710835983,
99111089,
230244822,
260818411,
499240983,
906202444,
162275749,
933757306,
59572946,
478754513,
161567192,
19484938,
589311803,
810734940,
243083547,
259534248,
591294196,
671365457,
494898815,
78710457,
283649619,
419049924,
187263502,
472930903,
12385828,
826859777,
440494651,
994626083,
330683188,
177821398,
244411149,
253026585,
463286078,
578481619,
876689500,
145274938,
774239862,
815295234,
821500934,
581365761,
574279161,
713158286,
937412725,
271157897,
988864517,
756436321,
495053769,
37638418,
43218680,
901727617,
808962313,
874682245,
122232957,
856814318,
748905129,
327934694,
554416598,
483793256,
928255311,
958450843,
3618746,
220437571,
922890983,
266112694,
667468020,
18992782,
257287349,
72824104,
643571417,
504602731,
827865458,
644158465,
992051025,
776531520,
177740638,
220635341,
579800026,
980895408,
468943312,
725574561,
145869478,
63869907,
663307218,
216733111,
699973399,
941754362,
738614905,
201596668,
512192351,
514584320,
472096579,
114643102,
701178424,
424492167,
512298596,
77740167,
520707075,
496129791,
268873461,
478398710,
435654841,
972816308,
46984740,
19652299,
804754049,
646533728,
993584556,
331478750,
325673994,
795749974,
499206491,
728256514,
224704,
526699434,
474315381,
113248522,
605410958,
533966369,
481797897,
547099968,
885198875,
963945752,
51516127,
27177875,
425774757,
907294033,
552007909,
966880832,
191622514,
820722508,
670621826,
933338751,
413352220,
642756565,
221762453,
362810925,
656978107,
834663866,
756062657,
170001461,
356068748,
18380550,
181059098,
841160160,
306463694,
482593224,
387063299,
7734487,
503104382,
619397280,
783099639,
857887831,
877659076,
821860586,
435990756,
990386420,
751827693,
504043541,
297611364,
388167107,
16809335,
720850066,
453512146,
157608575,
885612265,
831034782,
609061024,
858971448,
140312223,
190418212,
304503138,
730342129,
479882385,
927382894,
514084546,
175944650,
631737004,
848482164,
273619941,
310035443,
605810399,
178869710,
759464452,
393354318,
420841465,
225513279,
301648647,
707027751,
698860315,
18730041,
407950080,
711198175,
629229921,
348820947,
516927272,
337723734,
35126335,
913407519,
259302747,
238781658,
637276227,
194146825,
698051228,
663884683,
333805025,
152750269,
860739395,
667044581,
135511734,
808756301,
241681918,
768522507,
408890883,
85643805,
234392595,
264614140,
736473025,
878596254,
578016337,
278730911,
903559665,
643362481,
422213747,
788945099,
763504638,
75183433,
633835834,
501543259,
548910042,
831233334,
105643855,
281968565,
248344733,
392406273,
317735104,
201989123,
233583164,
729225857,
409390920,
226721862,
714177874,
947088120,
110794644,
545679397,
857057099,
116923462,
587408713,
709230826,
291024236,
330781825,
323114444,
949574384,
208224500,
348901683,
83622998,
262509325,
479758791,
321225275,
863646797,
181074508,
685870089,
121835953,
599489113,
381308939,
947952168,
910844113,
642457172,
381450047,
521770027,
107674516,
859796154,
641102369
    };
    LL(n);
    ll m=n/rng;
    n%=rng;
    out(a[m]+fact(n));
    //*/
}