#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;i>n; if(n<3){ cout<<0< A; A[-1] = 0; A[0] = 2; ll k=0; ll e=1; REP(i,n+2){ ll Am = 0; A[k+e] = 0; e = -e; REP(j,i){ Am += A[k]; Am %= MOD; A[k] = Am; k += e; } } ll i = n+1; ll res; if(i%2==0)res = A[-i/2+1]; else res = A[i/2]; cout<