#include typedef uint64_t u64; typedef int64_t i64; typedef long double f128; using namespace std; template struct modint{ u64 val; constexpr modint(const i64 x=0) noexcept:val((x%i64(mod)+i64(mod))%i64(mod)){} constexpr u64 get_mod() const noexcept{ return mod; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; val-=((val>=mod)?mod:0); return *this; } constexpr modint &operator-=(const modint rhs) noexcept{ val+=((val>=1; } return *this; } friend constexpr ostream &operator<<(ostream &os,const modint &x) noexcept{ return os<<(x.val); } friend constexpr istream &operator>>(istream &is,modint &x) noexcept{ u64 t; is>>t; x=t; return is; } }; void scan(){} template void scan(T& n,Args&... args){ cin>>n; scan(args...); } template void scanall(T start,T end){ for(;start!=end;++start){ scan(*start); } } void print(){} template void print(T n,Args... args){ cout< void println(T n){ cout< void println(T n,Args... args){ cout< void printall(T start,T end){ if(start!=end){ cout<<(*start); for(++start;start!=end;++start){ cout<<' '<<(*start); } } cout< void chmax(T& n,T m){ n=max(n,m); } template void chmin(T& n,T m){ n=min(n,m); } template T power(T a,U n){ T res=1; while(n){ res*=((n&1)?a:1); a*=a; n>>=1; } return res; } i64 power(i64 a,i64 n,i64 m){ i64 res=1%m; while(n){ if(n&1){ res=res*a%m; } a=a*a%m; n>>=1; } return res; } template struct combination{ vector fact,fact_inv; combination(int mx=3000000):fact(mx+1,1),fact_inv(mx+1,1){ for(int i=2;i<=mx;++i){ fact[i]=fact[i-1]*i; } fact_inv[mx]/=fact[mx]; for(int i=mx;i>0;--i){ fact_inv[i-1]=fact_inv[i]*i; } } template T nCk(U n,U k){ if(n ans_0(N/2); for(int i=0;i ans={3,6,4,2}; for(int i=8;i<=N;i+=2){ ans.emplace_back(i); } printall(ans.begin(),ans.end()); }