結果
| 問題 | No.2605 Pickup Parentheses |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2024-01-12 21:35:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 198 ms / 2,000 ms |
| コード長 | 19,911 bytes |
| コンパイル時間 | 5,962 ms |
| コンパイル使用メモリ | 292,696 KB |
| 最終ジャッジ日時 | 2025-02-18 17:52:53 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 68 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = unsigned long long;#define endl "\n"typedef pair<int, int> Pii;#define REP(i, n) for (int i = 0; i < (n); ++i)#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(x) begin(x), end(x)#define rrep(i,a,b) for(int i=a;i>=b;i--)#define fore(i,a) for(auto &i:a)#define all(s) (s).begin(),(s).end()#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))#define se second#define pb push_back#define P pair<ll,ll>#define PQminll priority_queue<ll, vector<ll>, greater<ll>>#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>#define PQminP priority_queue<P, vector<P>, greater<P>>#define PQmaxP priority_queue<P,vector<P>,less<P>>#define NP next_permutation//const ll mod = 1000000009;const ll mod = 998244353;//const ll mod = 1000000007;const ll inf = 4100000000000000000ll;const ld eps = ld(0.00000000001);static const long double pi = 3.141592653589793;template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}void yes(bool a){cout<<(a?"yes":"no")<<endl;}void YES(bool a){cout<<(a?"YES":"NO")<<endl;}void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))template<class T>auto min(const T& a){ return *min_element(all(a)); }template<class T>auto max(const T& a){ return *max_element(all(a)); }template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}template<class T>bool chmax(T &a,const T b) { if (a<b) { a=b; return 1; } return 0;}template<class T>bool chmin(T &a,const T b) { if (b<a) { a=b; return 1; } return 0;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1;} return ret; }vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }ll pop(ll x){return __builtin_popcountll(x);}ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}P hyou(P a){ll x=fastgcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}P Pgyaku(P a){ return hyou({a.se,a.fi});}#define die(a) cout<<a<<endl,exit(0);template<class T>pair<T,ll> maxid(vector<T> a){ll v=a[0],id=0;for(int i=1;i<a.size();i++){if(chmax(v,a[i])){id=i;}}return {v,id};}template<class T>pair<T,ll> minid(vector<T> a){ll v=a[0],id=0;for(int i=1;i<a.size();i++){if(chmin(v,a[i])){id=i;}}return {v,id};}template<class T> vector<pair<T,ll>> RLE(vector<T> a){vector<pair<T,ll>> r;ll v=1;for(int i=1;i<int(a.size());i++){if(a[i]==a[i-1]){v++;}else{r.pb({a[i-1],v});v=1;}}r.pb({a.back(),v});return r;}void compress(vector<ll> &arr){ll n=arr.size();map<ll,ll> m;for(int i=0;i<n;i++){m[arr[i]]=0;}ll s=0;for(auto& i:m){i.second=s++;}for(int i=0;i<n;i++){arr[i]=m[arr[i]];}}vector<pair<char,ll>> RLE(string a){vector<pair<char,ll>> r;ll v=1;for(int i=1;i<int(a.size());i++){if(a[i]==a[i-1]) v++;else{r.pb({a[i-1],v});v=1;}}r.pb({a.back(),v});return r;}template <int N> struct ndFORimpl {std::array<int, N> v;ndFORimpl(std::array<int, N> v_) : v(v_) {}struct ndFORitr {const std::array<int, N> &v;std::array<int, N> tmp;bool is_end;ndFORitr(const std::array<int, N> &v_) : v(v_), tmp(), is_end(false) {}bool operator!=(const ndFORitr &) const { return !is_end; }void operator++() {int pos = N - 1;while (pos != -1) {tmp[pos] += 1;if (tmp[pos] == v[pos]) {tmp[pos] = 0;pos -= 1;} else {break;}}if (pos == -1) {is_end = true;}}const std::array<int, N> &operator*() const { return tmp; }};ndFORitr begin() const { return ndFORitr(v); }ndFORitr end() const { return ndFORitr(v); }};template <class... Ts> auto ndFOR(Ts... v) {return ndFORimpl<std::tuple_size<std::tuple<Ts...>>::value>({v...});}void cincout(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(15);}template<class T>vector<T> NTT(vector<T> a,vector<T> b){ll nmod=T::mod();int n=a.size();int m=b.size();vector<int> x1(n);vector<int> y1(m);for(int i=0;i<n;i++){ll tmp1;tmp1=a[i].val();x1[i]=tmp1;}for(int i=0;i<m;i++){ll tmp1;tmp1=b[i].val();y1[i]=tmp1;}auto z1=convolution<167772161>(x1,y1);auto z2=convolution<469762049>(x1,y1);auto z3=convolution<1224736769>(x1,y1);vector<T> res(n+m-1);ll m1=167772161;ll m2=469762049;ll m3=1224736769;ll m1m2=104391568;ll m1m2m3=721017874;ll mm12=m1*m2%nmod;for(int i=0;i<n+m-1;i++){int v1=(z2[i]-z1[i])*m1m2%m2;if(v1<0) v1+=m2;int v2=(z3[i]-(z1[i]+v1*m1)%m3)*m1m2m3%m3;if(v2<0) v2+=m3;res[i]=(z1[i]+v1*m1+v2*mm12);}return res;}template<class T>struct FormalPowerSeries:vector<T>{using vector<T>::vector;using F=FormalPowerSeries;F &operator=(const vector<T> &g){int n=g.size();int m=(*this).size();(*this).resize(n);for(int i=0;i<n;i++) (*this)[i]=g[i];return (*this);}F &operator=(const F &g){int n=g.size();int m=(*this).size();(*this).resize(n);for(int i=0;i<n;i++) (*this)[i]=g[i];return (*this);}F &operator-(){for(int i=0;i<(*this).size();i++) (*this)[i]*=-1;return (*this);}F &operator+=(const F &g){int n=(*this).size();int m=g.size();if(n<m) (*this).resize(m);for(int i=0;i<m;i++) (*this)[i]+=g[i];return (*this);}F &operator+=(const T &r){if((*this).size()==0) (*this).resize(1);(*this)[0]+=r;return (*this);}F &operator-=(const F &g){int n=(*this).size();int m=g.size();if(n<m) (*this).resize(m);for(int i=0;i<m;i++) (*this)[i]-=g[i];return (*this);}F &operator-=(const T &r){if((*this).size()==0) (*this).resize(1);(*this)[0]-=r;return (*this);}F &operator*=(const F &g){(*this)=convolution((*this),g);return (*this);}F &operator*=(const T &r){for(int i=0;i<(*this).size();i++) (*this)[i]*=r;return (*this);}F &operator/=(const F &g){int n=(*this).size();(*this)=convolution((*this),g.inv());(*this).resize(n);return (*this);}F &operator/=(T r){r=r.inv();for(int i=0;i<(*this).size();i++) (*this)[i]*=r;return (*this);}F &operator<<=(const int d) {int n=(*this).size();(*this).insert((*this).begin(),d,0);return *this;}F &operator>>=(const int d) {int n=(*this).size();(*this).erase((*this).begin(),(*this).begin()+min(n, d));return *this;}F operator*(const T &g) const { return F(*this)*=g;}F operator-(const T &g) const { return F(*this)-=g;}F operator+(const T &g) const { return F(*this)+=g;}F operator/(const T &g) const { return F(*this)/=g;}F operator*(const F &g) const { return F(*this)*=g;}F operator-(const F &g) const { return F(*this)-=g;}F operator+(const F &g) const { return F(*this)+=g;}F operator/(const F &g) const { return F(*this)/=g;}F operator%(const F &g) const { return F(*this)%=g;}F operator<<(const int d) const { return F(*this)<<=d;}F operator>>(const int d) const { return F(*this)>>=d;}F pre(int sz) const {return F(begin(*this), begin(*this) + min((int)this->size(), sz));}F inv(int deg=-1) const {int n=(*this).size();if(deg==-1) deg=n;assert(n>0&&(*this)[0]!=T(0));F g(1);g[0]=(*this)[0].inv();while(g.size()<deg){int m=g.size();F f(begin(*this),begin(*this)+min(n,2*m));F r(g);f.resize(2*m);r.resize(2*m);internal::butterfly(f);internal::butterfly(r);for(int i=0;i<2*m;i++) f[i]*=r[i];internal::butterfly_inv(f);f.erase(f.begin(),f.begin()+m);f.resize(2*m);internal::butterfly(f);for(int i=0;i<2*m;i++) f[i]*=r[i];internal::butterfly_inv(f);T in=T(2*m).inv();in*=-in;for(int i=0;i<m;i++) f[i]*=in;g.insert(g.end(),f.begin(),f.begin()+m);}return g.pre(deg);}T eval(const T &a){T x=1;T ret=0;for(int i=0;i<(*this).size();i++){ret+=(*this)[i]*x;x*=a;}return ret;}void onemul(const int d,const T c){int n=(*this).size();for(int i=n-d-1;i>=0;i--){(*this)[i+d]+=(*this)[i]*c;}}void onediv(const int d,const T c){int n=(*this).size();for(int i=0;i<n-d;i++){(*this)[i+d]-=(*this)[i]*c;}}F diff() const {int n=(*this).size();F ret(n);for(int i=1;i<n;i++) ret[i-1]=(*this)[i]*i;ret[n-1]=0;return ret;}F integral() const {int n=(*this).size(),mod =T::mod();vector<T> inv(n);inv[1]=1;for(int i=2;i<n;i++) inv[i]=T(mod)-inv[mod%i]*(mod/i);F ret(n);for(int i=n-2;i>=0;i--) ret[i+1]=(*this)[i]*inv[i+1];ret[0]=0;return ret;}F log(int deg=-1) const {int n=(*this).size();if(deg==-1) deg=n;assert((*this)[0]==T(1));return ((*this).diff()*(*this).inv(deg)).pre(deg).integral();}F exp(int deg=-1) const {int n=(*this).size();if(deg==-1) deg=n;assert(n==0||(*this)[0]==0);F Inv;Inv.reserve(deg);Inv.push_back(T(0));Inv.push_back(T(1));auto inplace_integral = [&](F& f) -> void {const int n = (int)f.size();int mod=T::mod();while(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 = [](F &f) -> void {if(f.empty()) return;f.erase(begin(f));T coeff=1,one=1;for(int i=0;i<f.size();i++){f[i]*=coeff;coeff++;}};F b{1,1<(int)(*this).size()?(*this)[1]:0},c{1},z1,z2{1,1};for(int m=2;m<=deg;m<<=1){auto y=b;y.resize(2*m);internal::butterfly(y);z1=z2;F z(m);for(int i=0;i<m;i++) z[i]=y[i]*z1[i];internal::butterfly_inv(z);T si=T(m).inv();for(int i=0;i<m;i++) z[i]*=si;fill(begin(z),begin(z)+m/2,T(0));internal::butterfly(z);for(int i=0;i<m;i++) z[i]*=-z1[i];internal::butterfly_inv(z);for(int i=0;i<m;i++) z[i]*=si;c.insert(end(c),begin(z)+m/2,end(z));z2=c;z2.resize(2*m);internal::butterfly(z2);F x(begin((*this)),begin((*this))+min<int>((*this).size(),m));x.resize(m);inplace_diff(x);x.push_back(T(0));internal::butterfly(x);for(int i=0;i<m;i++) x[i]*=y[i];internal::butterfly_inv(x);for(int i=0;i<m;i++) x[i]*=si;x-=b.diff();x.resize(2*m);for(int i=0;i<m-1;i++) x[m+i]=x[i],x[i]=T(0);internal::butterfly(x);for(int i=0;i<2*m;i++) x[i]*=z2[i];internal::butterfly_inv(x);T si2=T(m<<1).inv();for(int i=0;i<2*m;i++) x[i]*=si2;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));internal::butterfly(x);for(int i=0;i<2*m;i++) x[i]*=y[i];internal::butterfly_inv(x);for(int i=0;i<2*m;i++) x[i]*=si2;b.insert(end(b),begin(x)+m,end(x));}return b.pre(deg);}F pow(ll m){int n=(*this).size();int x=0;while(x<(*this).size()&&(*this)[x]==T(0)){x++;}if(m==0){F ret(n);ret[0]=1;return ret;}if(x*m>=n){F ret(n);return ret;}F f(n-x);T y=(*this)[x];for(int i=x;i<n;i++) f[i-x]=(*this)[i]/y;f=f.log();for(int i=0;i<f.size();i++) f[i]*=m;f=f.exp();y=y.pow(m);for(int i=0;i<f.size();i++) f[i]*=y;F ret(n);for(int i=x*m;i<n;i++) ret[i]=f[i-x*m];return ret;}F shift(T c){int n=(*this).size();int mod=T::mod();vector<T> inv(n+1);inv[1]=1;for(int i=2;i<=n;i++) inv[i]=mod-inv[mod%i]*(mod/i);T x=1;for(int i=0;i<n;i++){(*this)[i]*=x;x*=(i+1);}F g(n);T y=1;T now=1;for(int i=0;i<n;i++){g[n-i-1]=now*y;now*=c;y*=inv[i+1];}auto tmp=convolution(g,(*this));T z=1;for(int i=0;i<n;i++){(*this)[i]=tmp[n+i-1]*z;z*=inv[i+1];}return (*this);}pair<F,F> division(F g){F f=(*this);int n=f.size();int m=g.size();if(n<m){F p(0);return {p,f};}F p(n-m+1),q(n-m+1);for(int i=0;i<n-m+1;i++) p[i]=f[n-i-1];for(int i=0;i<n-m+1&&i<m;i++) q[i]=g[m-i-1];p/=q;for(int i=0;i<(n-m+1)/2;i++) swap(p[i],p[(n-m+1)-i-1]);g.resize(n);g*=p;for(int i=0;i<n;i++) f[i]-=g[i];int v=n-m+1,u=0;for(int i=0;i<n;i++) if(f[i].val()) chmax(u,i+1);p.resize(v);f.resize(u);return {p,f};}vector<T> multieva(vector<T> p){int m=p.size();int n=(*this).size();int M=1;int l=0;while(M<m){M*=2;l++;}p.resize(M);swap(m,M);vector<vector<F>> g(l+1);g[0].resize(m);for(int i=0;i<m;i++){g[0][i].resize(2);g[0][i][0]=-p[i];g[0][i][1]=1;}for(int i=0;i<l;i++){g[i+1].resize(m>>(i+1));for(int j=0;j<(m>>(i+1));j++) g[i+1][j]=g[i][2*j]*g[i][2*j+1];}g[l][0]=(*this).division(g[l][0]).se;for(int i=l;i>=1;i--){for(int j=0;j<(m>>(i-1));j++){g[i-1][j]=g[i][j/2].division(g[i-1][j]).se;}}for(int i=0;i<M;i++) if(g[0][i].size()==0) g[0][i].resize(1);vector<T> ret(M);for(int i=0;i<M;i++) ret[i]=g[0][i][0];return ret;}};template<class T>void GaussJordan(vector<vector<T>> &A,bool is_extended = false){ll m=A.size(),n=A[0].size();ll rank=0;for(int i=0;i<n;i++){if(is_extended&&i==n-1) break;ll p=-1;for(int j=rank;j<m;j++){if(A[j][i]!=T(0)){p=j;break;}}if(p==-1) continue;swap(A[p],A[rank]);auto k=A[rank][i];for(int i2=0;i2<n;i2++){A[rank][i2]/=k;}for(int j=0;j<m;j++){if(j!=rank&&A[j][i]!=T(0)){auto fac=A[j][i];for(int i2=0;i2<n;i2++){A[j][i2]-=A[rank][i2]*fac;}}}rank++;}}template<class T>void linear_equation(vector<vector<T>> a, vector<T> b, vector<T> &res) {ll m=a.size(),n=a[0].size();vector<vector<T>> M(m,vector<T>(n+1));for(int i=0;i<m;i++){for(int j=0;j<n;j++){M[i][j]=a[i][j];}M[i][n]=b[i];}GaussJordan(M,true);res.assign(n,0);for(int i=0;i<n;i++) res[i]=M[i][n];}template<class F>pair<F,F> Characteristic_equation(const F &a) {using T=typename F::value_type;ll n=a.size();ll p=n/2;ll u=p+(p+1);vector<vector<T>> f(u,vector<T>(u));f[0][0]=1;for(int i=1;i<=p;i++){f[i][i-1]=-1;}for(int i=p;i<u;i++){ll t=0;for(int j=1+i-p;j<u;j++){f[j][i]=a[t];t++;}}vector<T> b(u);b[0]=1;vector<T> res(u);linear_equation(f,b,res);F X(p),Y(p+1);for(int i=0;i<p;i++) X[i]=res[i];for(int j=p;j<res.size();j++) Y[j-p]=res[j];return {X,Y};}template <class T>T getK(FormalPowerSeries<T> p, FormalPowerSeries<T> q,ll k){if(p.size()==0) return 0;if(k==0) return p[0]/q[0];if(p.size()>=q.size()){p=p.division(q).se;}if(q[0].val()!=1){for(int i=0;i<p.size();i++) p[i]/=q[0];for(int i=q.size()-1;i>=0;i--) q[i]/=q[0];}if(k<0) return T(0);ll d=q.size();p.resize(d-1);while(k){auto qn=q;for(int i=1;i<d;i+=2) qn[i]*=-1;p*=qn;q*=qn;for(int i=0;i<d-1;i++){p[i]=p[(i<<1)|(k&1)];}for(int i=0;i<d;i++){q[i]=q[(i<<1)];}p.resize(d-1);q.resize(d);k/=2;}return p[0];}using fps=FormalPowerSeries<modint998244353>;using mint = modint998244353;vector<mint> chirp_z_transform(ll n,ll m,fps x,mint w,mint a=mint(1)){vector<mint> y(n),v(n+m-1);vector<mint> u(n+m-1);u[0]=1;for(int i=1;i<n+m-1;i++) u[i]=u[i-1]*w;v[0]=1;for(int i=1;i<n+m-1;i++) v[i]=v[i-1]*u[i-1];mint ap=1;for(int i=0;i<n;i++){y[i]=x[i]*ap/v[i];ap*=a;}rever(y);y=convolution(y,v);vector<mint> ans(m);for(int i=0;i<m;i++) ans[i]=y[n-1+i]/v[i];return ans;}fps mergeconv(vector<fps> a){while(a.size()>1){ll n=a.size();vector<fps> b((n+1)/2);for(int i=0;i<a.size();i+=2){if(i+1<a.size()) b[i/2]=a[i]*a[i+1];else b[i/2]=a[i];}a=b;}return a[0];}pair<fps,fps> mergeconvfrac(vector<pair<fps,fps>> a){while(a.size()>1){ll n=a.size();vector<pair<fps,fps>> b((n+1)/2);for(int i=0;i<a.size();i+=2){if(i+1<a.size()) b[i/2]={a[i].fi*a[i+1].se+a[i+1].fi*a[i].se,a[i].se*a[i+1].se};else b[i/2]=a[i];}a=b;}return a[0];}constexpr ll MAX = 500010;ll fac[MAX],finv[MAX],inv[MAX];void COMinit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}ll binom(ll n,ll k){if(n<k) return 0;if(n<0||k<0) return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}ll pownk(ll n,ll k){//[x^k] 1/(1-x)^nif(n==0&&k==0) return 1;return binom(n+k-1,k);}ll catalan(ll n){return binom(2*n,n)*inv[n+1]%mod;}int main(){cincout();COMinit();ll n,m;cin>>n>>m;if(n%2) die(0);vector<ll> x;vector<mint> cat(n+1);for(int i=0;i<=n;i++){if(i==0){cat[i]=1;}else{cat[i]=binom(2*i,i)*inv[i+1];}}for(int i=0;i<m;i++){ll a,b;cin>>a>>b;ll k=b-a+1;if(k%2) continue;x.pb(k/2);}vector<fps> f;f.pb(fps({1}));for(int i=0;i<x.size();i++){fps g(x[i]+1);g[0]=1;g[x[i]]=-cat[x[i]];f.pb(g);}fps v=mergeconv(f);mint ans=0;for(int i=0;i<v.size();i++){ans+=v[i]*cat[n/2-i];}cout<<ans.val()<<endl;}