#include<bits/stdc++.h>
template<typename _Tp>void read(_Tp &x){
	char ch=getchar();bool f=0;while(!isdigit(ch))f|=ch=='-',ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
	if(f)x=-x;
}
template<typename _Tp,typename ...Args>void read(_Tp &x,Args &...args){read(x),read(args...);}
const int N=100005,mod=998244353;
template<typename _Tp1,typename _Tp2>inline void add(_Tp1 &a,_Tp2 b){a=a+b>=mod?a+b-mod:a+b;}
template<typename _Tp1,typename _Tp2>inline void sub(_Tp1 &a,_Tp2 b){a=a<b?a+mod-b:a-b;}
std::mt19937 rnd(1);
int a[N],b[N],d[N],nd[N],tmp[5005][5005];
int main(){
	int n;read(n);
	assert(n%2==0);
	for(int i=1;i<=n;++i)a[i]=rnd()%10;
	for(int i=1;i<=n;++i)d[i]=(a[i]+mod-a[i-1])%mod;
//	for(int i=1;i<=n;++i)read(a[i]);
	for(int k=1;k<=5000;++k){
		for(int i=1;i<=n/2;++i)b[i]=(a[i]+a[n-i+1])%mod;
		for(int i=1;i<=n;++i)a[i]=b[(i+1)/2];
		for(int i=1;i<=n;++i)nd[i]=i%2?(b[(i+1)/2]+mod-b[i/2])%mod:0;
		for(int i=1;i<=n;++i)if(i%2){
			int x=(i+1)/2,y=i/2;
			nd[i]=(d[x]+mod-d[n-y+1])%mod;
		}
		else nd[i]=0;
		nd[1]=b[1];
		for(int i=1;i<=n;++i)d[i]=nd[i];
		for(int i=1;i<=n;++i)assert(d[i]==(a[i]+mod-a[i-1])%mod);
//		for(int i=1;i<=n;++i)printf("%d%c",d[i]," \n"[i==n]);
		for(int i=1;i<=n;++i)tmp[k][i]=d[i];
	}
	for(int p=1;p<=5000;++p){
		bool flag=1;
		for(int i=2;i<=n;++i)flag&=tmp[5000][i]==tmp[5000-p][i];
		if(flag)fprintf(stderr,"@ %d\n",p);
	}
	return 0;
}
