結果
| 問題 | No.2137 Stairs of Permutation |
| ユーザー |
 hari64
|
| 提出日時 | 2022-11-25 23:19:29 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 23,194 bytes |
| コンパイル時間 | 3,804 ms |
| コンパイル使用メモリ | 256,240 KB |
| 実行使用メモリ | 101,848 KB |
| 最終ジャッジ日時 | 2024-10-02 05:49:22 |
| 合計ジャッジ時間 | 7,226 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,632 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
ソースコード
#include <bits/stdc++.h> // clang-format off
using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{using s=string;template<class T>s f(T i){s S=i==INF||i==INFll?"inf":to_string(i);return s(max(0,3-int(S.size())),' ')+S;}
template<class T>auto v(T&x,s&&e)->decltype(cerr<<x){return cerr<<x<<e;}void v(int x,s&&e){cerr<<f(x)<<e;}void v(long long x,s&&e){cerr<<f(x)<<e;}void v(float x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(long double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}
template<class T,class U>void v(const pair<T,U>&p,s&&e="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+e);}template<class T,class U>void v(const tuple<T,U>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),")"+e);}template<class T,class U,class V>void v(const tuple<T,U,V>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),")"+e);}template<class T,class U,class V,class W>void v(const tuple<T,U,V,W>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),", ");v(get<3>(t),")"+e);}
template<class T>void v(const vector<T>&vx,s);template<class T>auto ve(int,const vector<T>&vx)->decltype(cerr<<vx[0]){cerr<<"{";for(const T&x:vx)v(x,",");return cerr<<"}\n";}template<class T>auto ve(bool,const vector<T>&vx){cerr<<"{\n";for(const T&x:vx)cerr<<" ",v(x,",");cerr<<"}\n";}template<class T>void v(const vector<T>&vx,s){ve(0,vx);}
template<class T>void v(const deque<T>&q,s&&e){v(vector<T>(q.begin(),q.end()),e);}template<class T,class C>void v(const set<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T,class C>void v(const multiset<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T>void v(const unordered_set<T>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}
template<class T,class U,class V>void v(const priority_queue<T,U,V>&p,s&&e){priority_queue<T,U,V>q=p;vector<T>z;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);}template<class T,class U>void v(const map<T,U>&m,s&&e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<" [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;}
template<class T>void _view(int n,s&S,T&var){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S<<"\033[0m = ";v(var,"\n");}template<class T>void grid([[maybe_unused]]T _){}void grid(const vector<vector<bool>>&vvb){cerr<<"\n";for(const vector<bool>&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}}
void _debug(int,s){}template<typename H,typename... T>void _debug(int n,s S,const H&h,const T&... t){int i=0,cnt=0;for(;i<int(S.size());i++){if(S[i]=='(')cnt++;if(S[i]==')')cnt--;if(cnt==0&&S[i]==',')break;}if(i==int(S.size()))_view(n,S,h);else{s S1=S.substr(0,i),S2=S.substr(i+2);if(S2=="\"grid\""){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S1<<"\033[0m = ";grid(h);}else _view(n,S1,h),_debug(n,S2,t...);}}}
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;} // https://rsk0315.hatenablog.com/entry/2021/01/18/065720
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
#ifndef hari64
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif // clang-format on
// clang-format off
// https://ei1333.github.io/library/math/fps/formal-power-series-friendly-ntt.cpp
struct NumberTheoreticTransformFriendlyModInt{
static vector<mint>roots,iroots,rate3,irate3;
static int max_base;
NumberTheoreticTransformFriendlyModInt()=default;
static void init(){
if(roots.empty()){const unsigned mod=mint::mod();assert(mod>=3&&mod%2==1);auto tmp=mod-1;max_base=0;while(tmp%2==0)tmp>>=1,max_base++;mint root=2;while(root.pow((mod-1)>>1)==1)root+=1;assert(root.pow(mod-1)==1);roots.resize(max_base+1);iroots.resize(max_base+1);rate3.resize(max_base+1);irate3.resize(max_base+1);roots[max_base]=root.pow((mod-1)>>max_base);iroots[max_base]=mint(1)/roots[max_base];
for(int i=max_base-1;i>=0;i--){roots[i]=roots[i+1]*roots[i+1];iroots[i]=iroots[i+1]*iroots[i+1];}{mint prod=1,iprod=1;for(int i=0;i<=max_base-3;i++){rate3[i]=roots[i+3]*prod;irate3[i]=iroots[i+3]*iprod;prod*=iroots[i+3];iprod*=roots[i+3];}}}}
static void ntt(vector<mint>&a){init();const int n=(int)a.size();assert((n&(n-1))==0);int h=__builtin_ctz(n);assert(h<=max_base);int len=0;mint imag=roots[2];if(h&1){int p=1<<(h-1);for(int i=0;i<p;i++){auto r=a[i+p];a[i+p]=a[i]-r;a[i]+=r;}len++;}
for(;len+1<h;len+=2){int p=1<<(h-len-2);{for(int i=0;i<p;i++){auto a0=a[i];auto a1=a[i+p];auto a2=a[i+2*p];auto a3=a[i+3*p];auto a1na3imag=(a1-a3)*imag;auto a0a2=a0+a2;auto a1a3=a1+a3;auto a0na2=a0-a2;a[i]=a0a2+a1a3;a[i+1*p]=a0a2-a1a3;a[i+2*p]=a0na2+a1na3imag;a[i+3*p]=a0na2-a1na3imag;}}mint rot=rate3[0];
for(int s=1;s<(1<<len);s++){int offset=s<<(h-len);mint rot2=rot*rot;mint rot3=rot2*rot;for(int i=0;i<p;i++){auto a0=a[i+offset];auto a1=a[i+offset+p]*rot;auto a2=a[i+offset+2*p]*rot2;auto a3=a[i+offset+3*p]*rot3;auto a1na3imag=(a1-a3)*imag;auto a0a2=a0+a2;auto a1a3=a1+a3;auto a0na2=a0-a2;a[i+offset]=a0a2+a1a3;a[i+offset+1*p]=a0a2-a1a3;a[i+offset+2*p]=a0na2+a1na3imag;a[i+offset+3*p]=a0na2-a1na3imag;}rot*=rate3[__builtin_ctz(~s)];}}}
static void intt(vector<mint>&a,bool f=true){
init();const int n=(int)a.size();assert((n&(n-1))==0);int h=__builtin_ctz(n);assert(h<=max_base);int len=h;mint iimag=iroots[2];for(;len>1;len-=2){int p=1<<(h-len);{for(int i=0;i<p;i++){auto a0=a[i];auto a1=a[i+1*p];auto a2=a[i+2*p];auto a3=a[i+3*p];auto a2na3iimag=(a2-a3)*iimag;auto a0na1=a0-a1;auto a0a1=a0+a1;auto a2a3=a2+a3;a[i]=a0a1+a2a3;a[i+1*p]=(a0na1+a2na3iimag);a[i+2*p]=(a0a1-a2a3);a[i+3*p]=(a0na1-a2na3iimag);}}
mint irot=irate3[0];for(int s=1;s<(1<<(len-2));s++){int offset=s<<(h-len+2);mint irot2=irot*irot;mint irot3=irot2*irot;for(int i=0;i<p;i++){auto a0=a[i+offset];auto a1=a[i+offset+1*p];auto a2=a[i+offset+2*p];auto a3=a[i+offset+3*p];auto a2na3iimag=(a2-a3)*iimag;auto a0na1=a0-a1;auto a0a1=a0+a1;auto a2a3=a2+a3;a[i+offset]=a0a1+a2a3;a[i+offset+1*p]=(a0na1+a2na3iimag)*irot;a[i+offset+2*p]=(a0a1-a2a3)*irot2;a[i+offset+3*p]=(a0na1-a2na3iimag)*irot3;}irot*=irate3[__builtin_ctz(~s)];}}
if(len>=1){int p=1<<(h-1);for(int i=0;i<p;i++){auto ajp=a[i]-a[i+p];a[i]+=a[i+p];a[i+p]=ajp;}}if(f){mint inv_sz=mint(1)/n;for(int i=0;i<n;i++)a[i]*=inv_sz;}}
static vector<mint>multiply(vector<mint>a,vector<mint>b){int need=a.size()+b.size()-1;int nbase=1;while((1<<nbase)<need)nbase++;int sz=1<<nbase;a.resize(sz,0);b.resize(sz,0);ntt(a);ntt(b);mint inv_sz=mint(1)/sz;for(int i=0;i<sz;i++)a[i]*=b[i]*inv_sz;intt(a,false);a.resize(need);return a;}};
vector<mint>NumberTheoreticTransformFriendlyModInt::roots=vector<mint>();vector<mint>NumberTheoreticTransformFriendlyModInt::iroots=vector<mint>();vector<mint>NumberTheoreticTransformFriendlyModInt::rate3=vector<mint>();vector<mint>NumberTheoreticTransformFriendlyModInt::irate3=vector<mint>();int NumberTheoreticTransformFriendlyModInt::max_base=0;
template<typename T>struct FormalPowerSeriesFriendlyNTT:vector<T>{
using vector<T>::vector;using P=FormalPowerSeriesFriendlyNTT;using NTT=NumberTheoreticTransformFriendlyModInt;
P pre(int deg)const{return P(begin(*this),begin(*this)+min((int)this->size(),deg));}
P rev(int deg=-1)const{P ret(*this);if(deg!=-1)ret.resize(deg,T(0));reverse(begin(ret),end(ret));return ret;}
void shrink(){while(this->size()&&this->back()==T(0))this->pop_back();}
P operator+(const P&r)const{return P(*this)+=r;}
P operator+(const T&v)const{return P(*this)+=v;}
P operator-(const P&r)const{return P(*this)-=r;}
P operator-(const T&v)const{return P(*this)-=v;}
P operator*(const P&r)const{return P(*this)*=r;}
P operator*(const T&v)const{return P(*this)*=v;}
P operator/(const P&r)const{return P(*this)/=r;}
P operator/(const T&v)const{return P(*this)/=v;}
P operator%(const P&r)const{return P(*this)%=r;}
P operator>>(int r)const{return P(*this)>>=r;}
P operator<<(int r)const{return P(*this)<<=r;}
// https://judge.yosupo.jp/problem/convolution_mod
P operator-()const{P ret(this->size());for(int i=0;i<(int)this->size();i++)ret[i]=-(*this)[i];return ret;}
P&operator+=(const P&r){if(r.size()>this->size())this->resize(r.size());for(int i=0;i<(int)r.size();i++)(*this)[i]+=r[i];return*this;}
P&operator-=(const P&r){if(r.size()>this->size())this->resize(r.size());for(int i=0;i<(int)r.size();i++)(*this)[i]-=r[i];return*this;}
P&operator*=(const P&r){if(this->empty()||r.empty()){this->clear();return*this;}auto ret=NTT::multiply(*this,r);return*this={begin(ret),end(ret)};}
P&operator/=(const P&r){if(this->size()<r.size()){this->clear();return*this;}int n=this->size()-r.size()+1;return*this=(rev().pre(n)*r.rev().inv(n)).pre(n).rev(n);}
P&operator%=(const P&r){*this-=*this/r*r;shrink();return*this;}
P&operator+=(const T&r){if(this->empty())this->resize(1);(*this)[0]+=r;return*this;}
P&operator-=(const T&r){if(this->empty())this->resize(1);(*this)[0]-=r;return*this;}
P&operator*=(const T&v){for(int i=0;i<(int)this->size();i++)(*this)[i]*=v;return*this;}
P&operator/=(const T&v){for(int i=0;i<(int)this->size();i++)(*this)[i]/=v;return*this;}
P&operator>>=(int sz){this->erase(this->begin(),this->begin()+min(sz,(int)this->size()));return*this;}
P&operator<<=(int sz){this->insert(this->begin(),sz,T(0));return*this;}
// https://judge.yosupo.jp/problem/division_of_polynomials
pair<P,P>div_mod(const P&r){P q=*this/r;P x=*this-q*r;x.shrink();return make_pair(q,x);}
P dot(P r)const{P ret(min(this->size(),r.size()));for(int i=0;i<(int)ret.size();i++)ret[i]=(*this)[i]*r[i];return ret;}
// operator(x): f(x)の値を評価して返す O(n)
T operator()(T x)const{T r=0,w=1;for(auto&v:*this){r+=w*v;w*=x;}return r;}
// diff(): f'(x)を返す O(n)
P diff()const{const int n=(int)this->size();P ret(max(0,n-1));for(int i=1;i<n;i++)ret[i-1]=(*this)[i]*T(i);return ret;}
// integral(): ∫f(x)dxを返す O(n)
P integral()const{const int n=(int)this->size();P ret(n+1);ret[0]=T(0);for(int i=0;i<n;i++)ret[i+1]=(*this)[i]/T(i+1);return ret;}
// 以下の関数全般の参考資料: https://opt-cp.com/fps-fast-algorithms/
// inv(): 1/f(x)を返す f(0)!=0を要求する deg==-1の時、同じ次数で打ち切る
// https://judge.yosupo.jp/problem/inv_of_formal_power_series
P inv(int deg=-1)const{assert(((*this)[0])!=T(0));const int n=(int)this->size();if(deg==-1)deg=n;P res(deg);res[0]={T(1)/(*this)[0]};for(int d=1;d<deg;d<<=1){P f(2*d),g(2*d);for(int j=0;j<min(n,2*d);j++)f[j]=(*this)[j];for(int j=0;j<d;j++)g[j]=res[j];NTT::ntt(f);NTT::ntt(g);f=f.dot(g);NTT::intt(f);for(int j=0;j<d;j++)f[j]=0;NTT::ntt(f);for(int j=0;j<2*d;j++)f[j]*=g[j];NTT::intt(f);for(int j=d;j<min(2*d,deg);j++)res[j]=-f[j];}return res;}
// log(): logf(x)を返す f(0)==1を要求する deg==-1の時、同じ次数で打ち切る
// https://judge.yosupo.jp/problem/log_of_formal_power_series
P log(int deg=-1)const{assert((*this)[0]==T(1));const int n=(int)this->size();if(deg==-1)deg=n;return(this->diff()*this->inv(deg)).pre(deg-1).integral();}
// sqrt(): √f(x)(i.e. g(x) s.t. g(x)*g(x)==f(x))を返す
// 存在しない場合は空配列を返す deg==-1の時、同じ次数で打ち切る
// https://judge.yosupo.jp/problem/sqrt_of_formal_power_series
P sqrt(int deg=-1,const function<T(T)>&get_sqrt=[](T y){return modsqrt(y);})const{const int n=(int)this->size();if(deg==-1)deg=n;if((*this)[0]==T(0)){for(int i=1;i<n;i++){if((*this)[i]!=T(0)){if(i&1)return{};if(deg-i/2<=0)break;auto ret=(*this>>i).sqrt(deg-i/2,get_sqrt);if(ret.empty())return{};ret=ret<<(i/2);if((int)ret.size()<deg)ret.resize(deg,T(0));return ret;}}return P(deg,0);}
auto sqr=T(get_sqrt((*this)[0]));if(sqr*sqr!=(*this)[0])return{};P ret{sqr};T inv2=T(1)/T(2);for(int i=1;i<deg;i<<=1){ret=(ret+pre(i<<1)*ret.inv(i<<1))*inv2;}return ret.pre(deg);}
P sqrt(const function<T(T)>&get_sqrt,int deg=-1)const{return sqrt(deg,get_sqrt);}
// exp(): exp(f(x))を返す f(0)=0を要求する deg==-1の時、同じ次数で打ち切る
// https://judge.yosupo.jp/problem/exp_of_formal_power_series
P exp(int deg=-1)const{if(deg==-1)deg=this->size();assert((*this)[0]==T(0));P inv;inv.reserve(deg+1);inv.push_back(T(0));inv.push_back(T(1));auto inplace_integral=[&](P&F)->void{const int n=(int)F.size();auto mod=T::getmod();while((int)inv.size()<=n){int i=inv.size();inv.push_back((-inv[mod%i])*(mod/i));}F.insert(begin(F),T(0));for(int i=1;i<=n;i++)F[i]*=inv[i];};
auto inplace_diff=[](P&F)->void{if(F.empty())return;F.erase(begin(F));T coeff=1,one=1;for(int i=0;i<(int)F.size();i++){F[i]*=coeff;coeff+=one;}};P b{1,1<(int)this->size()?(*this)[1]:0},c{1},z1,z2{1,1};
for(int m=2;m<deg;m*=2){auto y=b;y.resize(2*m);NTT::ntt(y);z1=z2;P z(m);for(int i=0;i<m;++i)z[i]=y[i]*z1[i];NTT::intt(z);fill(begin(z),begin(z)+m/2,T(0));NTT::ntt(z);for(int i=0;i<m;++i)z[i]*=-z1[i];NTT::intt(z);c.insert(end(c),begin(z)+m/2,end(z));z2=c;z2.resize(2*m);NTT::ntt(z2);P x(begin(*this),begin(*this)+min<int>(this->size(),m));inplace_diff(x);x.push_back(T(0));NTT::ntt(x);
for(int i=0;i<m;++i){x[i]*=y[i];}NTT::intt(x);x-=b.diff();x.resize(2*m);for(int i=0;i<m-1;++i)x[m+i]=x[i],x[i]=T(0);NTT::ntt(x);for(int i=0;i<2*m;++i)x[i]*=z2[i];NTT::intt(x);x.pop_back();inplace_integral(x);for(int i=m;i<min<int>(this->size(),2*m);++i)x[i]+=(*this)[i];fill(begin(x),begin(x)+m,T(0));NTT::ntt(x);for(int i=0;i<2*m;++i)x[i]*=y[i];NTT::intt(x);b.insert(end(b),begin(x)+m,end(x));}return P{begin(b),begin(b)+deg};}
// pow(k): f^k(x)を返す deg==-1の時、同じ次数で打ち切る
// https://judge.yosupo.jp/problem/pow_of_formal_power_series
P pow(int64_t k,int deg=-1)const{const int n=(int)this->size();if(deg==-1)deg=n;for(int i=0;i<n;i++){if((*this)[i]!=T(0)){T rev=T(1)/(*this)[i];P ret=(((*this*rev)>>i).log()*k).exp()*((*this)[i].pow(k));if(i*k>deg)return P(deg,T(0));ret=(ret<<(i*k)).pre(deg);if((int)ret.size()<deg)ret.resize(deg,T(0));return ret;}}return*this;}
// mod_pow(k,g): f^k(x) (mod g(x))を返す O(nlogklogdeg(f))
P mod_pow(int64_t k,P g)const{P modinv=g.rev().inv();auto get_div=[&](P base){if(base.size()<g.size()){base.clear();return base;}int n=base.size()-g.size()+1;return(base.rev().pre(n)*modinv.pre(n)).pre(n).rev(n);};P x(*this),ret{1};while(k>0){if(k&1){ret*=x;ret-=get_div(ret)*g;ret.shrink();}x*=x;x-=get_div(x)*g;x.shrink();k>>=1;}return ret;}
// taylor_shift(c): g(x)=f(x+c)を満たすg(x)を返す
// https://judge.yosupo.jp/problem/polynomial_taylor_shift
P taylor_shift(T c)const{int n=(int)this->size();vector<T>fact(n),rfact(n);fact[0]=rfact[0]=T(1);for(int i=1;i<n;i++)fact[i]=fact[i-1]*T(i);rfact[n-1]=T(1)/fact[n-1];for(int i=n-1;i>1;i--)rfact[i-1]=rfact[i]*T(i);P p(*this);for(int i=0;i<n;i++)p[i]*=fact[i];p=p.rev();P bs(n,T(1));for(int i=1;i<n;i++)bs[i]=bs[i-1]*c*rfact[i]*fact[i-1];p=(p*bs).pre(n);p=p.rev();for(int i=0;i<n;i++)p[i]*=rfact[i];return p;}
};
using FPS = FormalPowerSeriesFriendlyNTT<mint>;
// https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a
// [x^N] P(x) / Q(x) require: deg(Q(x)) == d && deg(P(x)) <= d - 1 && Q[0] != 0
// summary: [x^N] P(x)/Q(x) = [x^N] P(x)Q(-x)/Q(x)Q(-x) = [x^N] (U_e(x^2)+xU_o(x^2))/V(x^2) -> x^N/2 or x^(N-1)/2
mint BostanMori(long long N,FPS P,FPS Q){int d=Q.size();assert(int(P.size())<=d-1&&Q[0]!=0);if(Q[0]!=1){for(int i=int(P.size())-1;i>=0;i--)P[i]/=Q[0];for(int i=int(Q.size())-1;i>=0;i--)Q[i]/=Q[0];}if(N==0)return P[0]/Q[0];while(N){FPS Qminus=Q;Qminus.shrink();for(int i=1;i<d;i+=2)Qminus[i]*=-1;P.resize(2*d);Q.resize(2*d);P*=Qminus;/*U*/for(int i=0;i<d-1;i++)P[i]=P[(i<<1)|(N&1)];Q*=Qminus;/*V*/for(int i=0;i<d;i++)Q[i]=Q[i<<1];P.resize(d-1);Q.resize(d);N>>=1;}return P[0];}
// clang-format on
// usage: FPS FPS_As(As.begin(), As.end());
// logは恐らく壊れているが、それ以外は基本OK
void test(int N) {
vector<vector<vector<int>>> fs(N + 1);
vector<int> Ps(N);
iota(Ps.begin(), Ps.end(), 0);
do {
int f = 0;
for (int i = 0; i < N; i++) {
if (*max_element(Ps.begin(), Ps.begin() + i + 1) == Ps[i]) {
f++;
}
}
fs[f].push_back(Ps);
} while (next_permutation(Ps.begin(), Ps.end()));
for (int f = 0; f <= N; f++) {
debug(f);
debug(fs[f].size());
// debug(fs[f]);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
// test(1);
// debug("---");
// test(2);
// debug("---");
// test(3);
// debug("---");
// test(4);
// debug("---");
// test(5);
// debug("---");
// test(6);
// debug("---");
// test(7);
int N;
cin >> N;
queue<FPS> q;
for (int i = 0; i < N; i++) {
q.push({i, 1});
}
while (q.size() >= 2) {
auto f1 = q.front();
q.pop();
auto f2 = q.front();
q.pop();
q.push(f1 * f2);
}
FPS f = q.front();
debug(f);
mint ans = 0;
for (int i = 0; i <= N; i++) {
ans += mint(i).pow(3) * f[i];
}
cout << ans << endl;
return 0;
}