stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <utility>

#include <vector>

using ll=long long;

#define rep(i,a,b) for(ll i=a;i<ll(b);i++)

#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)

#define endl "\n"

#define ALL(x) x.begin(),x.end()

#define ALLR(x) x.rbegin(),x.rend()

using namespace std;



using P=pair<ll, ll>;

vector<P> prime_factorize(ll N) {

    vector<P> res;

    for (ll a = 2; a*a <= N; a++) {

        if (N % a != 0) continue;

        ll ex = 0; // 指数



        // 割れる限り割り続ける

        while (N % a == 0) {

            ex++;

            N /= a;

        }



        // その結果を push

        res.push_back(P(a, ex));

    }



    // 最後に残った数について

    if (N != 1) res.push_back(P(N, 1));

    return res;

}



const int MAX = 1e6;



ll N, ans;

vector<ll> pCount(MAX);

int main() {

	cin >> N;



	// 素因分解

	const auto &res = prime_factorize(N);

    rep(i, 0, res.size()) {

		int a = res[i].second;



		int b = 1;

		while(1){

			a -= b;

			if(a < 0) break;

			ans++;

			b++;

		}

    }

	cout << ans << endl;



    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <utility>

#include <vector>

#include <string>

#include <algorithm>

#include <cmath>

using namespace std;

using ll=long long;

#define rep(i,a,b) for(ll i=a;i<ll(b);i++)

#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)

#define endl "\n"

#define ALL(x) x.begin(),x.end()

#define ALLR(x) x.rbegin(),x.rend()

#define INF 1e9

#define DEBUG(x) cout<<"debug: "<<x<<endl



vector<pair<ll, ll>> GetPrimes(ll parm){

    // first: prime, second: ex

    vector<pair<ll, ll>> res;



    ll ex = 0;

    while (parm % 2 == 0) {

        ex++;

        parm /= 2;

    }

    if(ex != 0) res.push_back({2, ex});



    for(ll i = 3; i*i <= parm; i += 2 ){

        ex = 0;

        while(parm % i == 0){

            ex++;

            parm /= i;

        }

        if(ex != 0) res.push_back({i, ex});

    }



    if(parm != 1) res.push_back({parm, 1});

    return res;

}



ll n, ans;

int main() {

    cin >> n;

    const auto &res = GetPrimes(n);



    for(auto p : res){

        ll ex = p.second;

        int i = 1;

        while(ex > 0){

            ex -= i; i++;

            if(ex >= 0) ans++;

        }

    }



    cout << ans << endl;



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=2005;

int n,sz[N];ll ans=1e18,f[N],g[N];

char s[N];vector<int>G[N];

void dfs(int x,int p)

{

	sz[x]=s[x]=='1';g[x]=0;ll mx=0,sum=0;

	for(int i=0;i<G[x].size();i++)if(G[x][i]!=p)

	{

		int y=G[x][i];dfs(y,x);sz[x]+=sz[y];

		g[y]+=sz[y];g[x]+=g[y];f[y]+=sz[y];

		if(f[y]>=f[mx])sum+=g[mx],mx=y;else sum+=g[y];

	}

	if(sum>=f[mx])f[x]=(sum-f[mx])&1;else f[x]=f[mx]-sum;

}

int main()

{

	scanf("%d%s",&n,s+1);

	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);

	for(int i=1;i<=n;i++){dfs(i,0);if(!f[i])ans=min(ans,g[i]);}

	printf("%d\n",ans==1e18?-1:ans/2);return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

const int N=2005;

int n,he[N],to[N*2],nx[N*2],s[N],f[N],g[N],ans=1e9;char c[N];

inline void wk(int w,int x,int y)

{to[w]=y,nx[w]=he[x],he[x]=w;}

inline int mn(int x,int y){return x<y?x:y;}

void dfs(int x,int fa)

{

	s[x]=c[x]&1,g[x]=0;int a=0;

	for(int i=he[x],y;i;i=nx[i])if((y=to[i])!=fa)

		dfs(y,x),s[x]+=s[y],g[y]+=s[y],f[y]+=s[y],g[x]+=g[y],g[y]>g[a]&&(a=y);

	if(f[a]<=g[x]-g[a])f[x]=g[x]&1;else f[x]=f[a]-(g[x]-g[a]);

}

int main()

{

	scanf("%d%s",&n,c+1);

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),wk(i*2,x,y),wk(i*2+1,y,x);

	for(int i=1;i<=n;++i)

		dfs(i,0),!f[i]&&(ans=mn(ans,g[i]>>1));

	return printf("%d",ans==1e9?-1:ans),0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 2010;



struct edge {

    int to, next;

} e[N * 2];



int head[N], ecnt;



inline void adde(int from, int to) {

    e[++ecnt] = (edge){to, head[from]}, head[from] = ecnt;

    e[++ecnt] = (edge){from, head[to]}, head[to] = ecnt;

}



// sum: 子树内棋子个数 dp: 子树内最少操作步数

int sum[N], dp[N];



int val[N];



void dfs(int u, int f) {

    sum[u] = val[u], dp[u] = 0;

    for (int i = head[u]; i; i = e[i].next)

        if (e[i].to != f) {

            dfs(e[i].to, u);

            sum[u] += sum[e[i].to], dp[u] += dp[e[i].to] + sum[e[i].to];

        }

}



// 子树的最小剩余深度

int dfs2(int u, int f) {

    int mx = 0;

    for (int i = head[u]; i; i = e[i].next)

        if (e[i].to != f) 

            if (dp[e[i].to] >= dp[mx]) 

                mx = e[i].to;

    if (!mx) return 0;

    int tmp = dfs2(mx, u) + sum[mx];

    if (dp[u] - dp[mx] - sum[mx] >= tmp) return dp[u] & 1;

    return tmp - (dp[u] - dp[mx] - sum[mx]);

}



char s[N];



int main() {

    int n; scanf("%d%s", &n, s + 1);

    for (int i = 1; i <= n; i++) val[i] = s[i] == '1';

    for (int i = 1, a, b; i < n; i++) scanf("%d%d", &a, &b), adde(a, b);

    int res = 1e9;

    for (int i = 1; i <= n; i++) {

        dfs(i, 0);

        if (!dfs2(i, 0)) res = min(res, dp[i] / 2);

    }

    if (res < 1e8) printf("%d\n", res);

    else puts("-1");

    return 0;

}//

// Optimized solution to the same problem (faster):
#include<cstdio>

const int N=2005;

int n,he[N],to[N*2],nx[N*2],s[N],f[N],g[N],ans=1e9;char c[N];

inline void wk(int w,int x,int y)

{to[w]=y,nx[w]=he[x],he[x]=w;}

inline int mn(int x,int y){return x<y?x:y;}

void dfs(int x,int fa)

{

	s[x]=c[x]&1,g[x]=0;int a=0;

	for(int i=he[x],y;i;i=nx[i])if((y=to[i])!=fa)

		dfs(y,x),s[x]+=s[y],g[y]+=s[y],f[y]+=s[y],g[x]+=g[y],g[y]>g[a]&&(a=y);

	if(f[a]<=g[x]-g[a])f[x]=g[x]&1;else f[x]=f[a]-(g[x]-g[a]);

}

int main()

{

	scanf("%d%s",&n,c+1);

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),wk(i*2,x,y),wk(i*2+1,y,x);

	for(int i=1;i<=n;++i)

		dfs(i,0),!f[i]&&(ans=mn(ans,g[i]>>1));

	return printf("%d",ans==1e9?-1:ans),0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 2005

#define inf 0x3f3f3f3f

int n;

int fir[N], tar[N << 1], nex[N << 1], cnt;

int mn[N], mx[N], siz[N];

int now, tot, ans = inf;

char S[N];

void Add(int a, int b)

{

	++cnt;

	tar[cnt] = b;

	nex[cnt] = fir[a];

	fir[a] = cnt;

}

void Dfs(int r, int fa, int d)

{

	if (S[r] == '1')

		now += d;

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs(v, r, d + 1);

	}

}

void Dfs1(int r, int fa, int d)

{

	if (S[r] == '1')

		tot += d;

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs1(v, r, d + 1);

	}

}

void Dfs2(int r, int fa)

{

	int tot = 0, p = 0;

	siz[r] = S[r] - '0';

	for (int i = fir[r]; i; i = nex[i])

	{

		int v = tar[i];

		if (v == fa)

			continue;

		Dfs2(v, r);

		if (mn[v] > mn[p])

			p = v;

		tot += mx[v];

		siz[r] += siz[v];

	}

	mx[r] = tot;

	tot -= mx[p];

	mn[r] = max(0, mn[p] - tot);

	if (fa)

	{

		mn[r] += siz[r];

		mx[r] += siz[r];

	}

}

void Solve(int r)

{

	tot = 0;

	Dfs1(r, 0, 0);

	if (tot & 1)

		return;

	Dfs2(r, 0);

	if (mn[r] > 0)

		return;

	ans = min(ans, tot / 2);

}

int main()

{

	scanf("%d%s", &n, S + 1);

	for (int i = 1; i < n; i++)

	{

		int a, b;

		scanf("%d%d", &a, &b);

		Add(a, b), Add(b, a);

	}

	for (int i = 1; i <= n; i++)

		Solve(i);

	if (ans == inf)

		puts("-1");

	else

		printf("%d\n",ans);

}


// Optimized solution to the same problem (faster):
#include<cstdio>

const int N=2005;

int n,he[N],to[N*2],nx[N*2],s[N],f[N],g[N],ans=1e9;char c[N];

inline void wk(int w,int x,int y)

{to[w]=y,nx[w]=he[x],he[x]=w;}

inline int mn(int x,int y){return x<y?x:y;}

void dfs(int x,int fa)

{

	s[x]=c[x]&1,g[x]=0;int a=0;

	for(int i=he[x],y;i;i=nx[i])if((y=to[i])!=fa)

		dfs(y,x),s[x]+=s[y],g[y]+=s[y],f[y]+=s[y],g[x]+=g[y],g[y]>g[a]&&(a=y);

	if(f[a]<=g[x]-g[a])f[x]=g[x]&1;else f[x]=f[a]-(g[x]-g[a]);

}

int main()

{

	scanf("%d%s",&n,c+1);

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),wk(i*2,x,y),wk(i*2+1,y,x);

	for(int i=1;i<=n;++i)

		dfs(i,0),!f[i]&&(ans=mn(ans,g[i]>>1));

	return printf("%d",ans==1e9?-1:ans),0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define maxn 2010

#define INF 0x7fffffff

template <typename T>inline T read()

{

    register T sum=0;

    register char cc=getchar();

    int sym=1;

    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();

    if(cc=='-')sym=-1,cc=getchar();

    sum=sum*10+cc-'0';

    cc=getchar();

    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();

    return sym*sum;

}

template <typename T>inline T read(T &a)

{

    a=read<T>();

    return a;

}

template <typename T,typename... Others> inline void read(T& a, Others&... b)

{

    a=read(a);

	read(b...);

}

struct Edge

{

	int v;

	Edge *next;

	Edge(int a=0,Edge *b=NULL)

	{

		v=a;

		next=b;

	}

}*head[maxn];

int n,ans=INF,a[maxn],f[maxn],g[maxn];

char str[maxn];

void dfs(int k,int fa)

{

	f[k]=a[k];

	g[k]=0;

	for(Edge *i=head[k];i!=NULL;i=i->next)

		if(i->v!=fa)

		{

			dfs(i->v,k);

			f[k]+=f[i->v];

			g[k]+=g[i->v]+f[i->v];

		}

}

int dp(int k,int fa)

{

	int mx=0;

	for(Edge *i=head[k];i!=NULL;i=i->next)

		if(i->v!=fa)

			if(g[i->v]>=g[mx])

				mx=i->v;

	if(!mx)return 0;

	int t=dp(mx,k)+f[mx],o=g[k]-g[mx]-f[mx];

	if(o>=t)

		return g[k]&1;

	return t-o;

}

int main()

{

	read(n);

	scanf("%s",str+1);

	for(int i=1;i<=n;i++)

		a[i]=str[i]-'0';

	for(int i=1;i<n;i++)

	{

		int x,y;

		read(x,y);

		head[x]=new Edge(y,head[x]);

		head[y]=new Edge(x,head[y]);

	}

	for(int i=1;i<=n;i++)

	{

		dfs(i,0);

		if(dp(i,0)==0)

			ans=min(ans,g[i]>>1);

	}

	if(ans!=INF)printf("%d\n",ans);

	else puts("-1");

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

const int N=2005;

int n,he[N],to[N*2],nx[N*2],s[N],f[N],g[N],ans=1e9;char c[N];

inline void wk(int w,int x,int y)

{to[w]=y,nx[w]=he[x],he[x]=w;}

inline int mn(int x,int y){return x<y?x:y;}

void dfs(int x,int fa)

{

	s[x]=c[x]&1,g[x]=0;int a=0;

	for(int i=he[x],y;i;i=nx[i])if((y=to[i])!=fa)

		dfs(y,x),s[x]+=s[y],g[y]+=s[y],f[y]+=s[y],g[x]+=g[y],g[y]>g[a]&&(a=y);

	if(f[a]<=g[x]-g[a])f[x]=g[x]&1;else f[x]=f[a]-(g[x]-g[a]);

}

int main()

{

	scanf("%d%s",&n,c+1);

	for(int i=1,x,y;i<n;++i)

		scanf("%d%d",&x,&y),wk(i*2,x,y),wk(i*2+1,y,x);

	for(int i=1;i<=n;++i)

		dfs(i,0),!f[i]&&(ans=mn(ans,g[i]>>1));

	return printf("%d",ans==1e9?-1:ans),0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int mod = 1e9+7;

int main()

{

    int n,sign=0;

    int a[100005];

    int m[100005]={0};

    cin>>n;

    for(int i=0;i<n;i++)

    {

        cin>>a[i];

        m[a[i]]++;

    }

    if(n%2)

    {

        if(m[0]!=1){

            sign=1;

        }

        for(int i=2;i<n;i+=2)

        {

            if(m[i] != 2){

                sign = 1;

            }

        }

    }

    else

    {

        for(int i=1;i<n;i+=2)

        {

            if(m[i] != 2)

            {

                sign = 1;

            }

        }

    }

    ll s = 1;

    for(int i=0;i < floor(n/2);i++)

    {

        s = ((s%mod)*2)%mod;

    }

    if(sign)

    {

        cout<<"0\n";

    }

    else

    {

        cout<<s<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <cmath> 

#define ll long long



ll MOD=1e9+7;

ll a[100005];

using namespace std;



int main(){

	ll n;

	cin>>n;

	

	ll flag=1;//标志 

	ll ans=1;

	

	if(n%2==0){ //偶数 

		for(ll i=0;i<n;i++){

			ll x;

			cin>>x;

			a[x]++;

			if(x>=n || x%2==0 || a[x]>2){

				flag=0;

				cout<<"0"<<endl;

				break;

			}

			if(a[x]==1)

				ans=ans*2%MOD;

		}

	} 

	

	else{ //奇数 

		for(ll i=0;i<n;i++){

			ll x;

			cin>>x;

			a[x]++;

			if(x>=n || x%2==1 || a[0]>1 ||a[x]>2){

				flag=0;

				cout<<"0"<<endl;

				break;

			}

			if(x!=0 && a[x]==1)

				ans=ans*2%MOD;

		}

	}

	if(flag)

		cout<<ans<<endl;

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <map>

#define ll long long

#define mod 1000000007

using namespace std;

map<int,int>m;

int an[100010];

int main(){

  int n,a;

  ll ans=1;

  cin>>n;

  if(n%2!=0){

    for(int i=1;i<=n;i++){

      cin>>a;

      m[a]++;

      if(m[a]==3||m[0]==2||a%2!=0){

        cout<<0<<endl;

        return 0;

      }

    }

    for(int i=1;i<=n/2;i++){

      ans=ans*2%mod;

    }

  }

  else {

    for(int i=0;i<n;i++){

      cin>>a;

      m[a]++;

      if(m[a]==3||a%2==0){

        cout<<0<<endl;

        return 0;

      }

    }

    for(int i=1;i<=n/2;i++){

      ans=ans*2%mod;

    }

  }

  cout<<ans<<endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define N (100010)

#define MD (1000000007)

int n,ans,a[N],f[N];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;

	if (n&1){

		if (f[0]!=1) ans=0; else ans=1;

		for (int i=2;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	else {

		ans=1;

		for (int i=1;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	printf("%d\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<iostream>

#include<map>

using namespace std;

int a[100010];

map<int,int>mp;

int main()

{

    int m=1;

    int n,i,t;

    cin>>n;

    for(i=0;i<n;i++)

    {

        cin>>t;

        mp[t]++;

    }

    if(n%2==0)

    {

        for(t=1;t<n;t+=2)

        {

            if(m>1000000007)

            {

                m-=1000000007;

            }

            if(mp[t]==2)

            {

                m*=2;

            }

            else

            {

                cout<<0;

                return 0;

            }

        }

    }

    else

    {

        if(mp[0]!=1)

        {

            cout<<0;

            return 0;

        }

        for(t=2;t<n;t+=2)

        {

            if(m>1000000007)

            {

                m-=1000000007;

            }

            if(mp[t]==2)

            {

                m*=2;

            }

            else

            {

                cout<<0;

                return 0;

            }

        }

    }

    cout<<m%1000000007;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define N (100010)

#define MD (1000000007)

int n,ans,a[N],f[N];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;

	if (n&1){

		if (f[0]!=1) ans=0; else ans=1;

		for (int i=2;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	else {

		ans=1;

		for (int i=1;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	printf("%d\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



const int MM = 1e9 + 7;

const double eps = 1e-8;

const int MAXN = 2e6 + 10;



int n, m;



void prework(){



}



void read(){



}



int a[MAXN];



ll calc(int p){

	ll ret = 1;

	for(int i = 1; i <= p; i++)

		ret = ret * 2 % MM;

	return ret;

}



void solve(int casi){

	cin>>n;

	for(int i = 1; i <= n; i++)

		scanf("%d", &a[i]);

	sort(a + 1, a + n + 1);

	if (n & 1){	

		for(int i = 1; i <= n; i++){

			if (a[i] != i / 2 * 2){

				puts("0");

				return ;

			}

		}

		cout<<calc(n/2)<<endl;

	}

	else{

		for(int i = 1; i <= n; i++){

			if (a[i] != (i + 1) / 2 * 2 - 1){

				puts("0");

				return ;

			}

		}

		cout<<calc(n/2)<<endl;

	}

}



void printans(){



}





int main(){

	prework();

	int T = 1;

//	cin>>T;

	for(int i = 1; i <= T; i++){

		read();

		solve(i);

		printans();

	}

	return 0;

}






// Optimized solution to the same problem (faster):
#include<stdio.h>

#define N (100010)

#define MD (1000000007)

int n,ans,a[N],f[N];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;

	if (n&1){

		if (f[0]!=1) ans=0; else ans=1;

		for (int i=2;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	else {

		ans=1;

		for (int i=1;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	printf("%d\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cstdlib>

#include <set>

#include <queue>

using namespace std;



#define X first

#define Y second

#define N 100010

typedef long long ll;

typedef pair<int,int> pii;

const int Mod=1000000007;



const double INF=1e18;



int n;

int a[N],cnt[N];



int Solve1()

{

	int res=1;

	if (cnt[0]!=1) return 0;



	for (int i=2;i<n;i+=2)

	{

		if (cnt[i]!=2) return 0;

		res=1ll*res*2%Mod;

	}

	return res;

}



int Solve2()

{

	int res=1;

	for (int i=1;i<n;i+=2)

	{

		if (cnt[i]!=2) return 0;

		res=1ll*res*2%Mod;

	}

	return res;

}



int main()

{

	//freopen("in.in","r",stdin);

	//freopen("out.out","w",stdout);

	

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++;

	

	if (n&1) printf("%d\n",Solve1());

	else printf("%d\n",Solve2());

	

	return 0;



}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define N (100010)

#define MD (1000000007)

int n,ans,a[N],f[N];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;

	if (n&1){

		if (f[0]!=1) ans=0; else ans=1;

		for (int i=2;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	else {

		ans=1;

		for (int i=1;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	printf("%d\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long LL;



const int MOD = 1e9 +7;

const int N = 1e5 + 10;

int a[N], b[N];



int mypow(LL a, LL b) {

    LL ret = 1;

    while (b) {

        if (b & 1) ret = ret * a % MOD;

        a = a * a % MOD;

        b >>= 1;

    }

    return ret;

}





int main() {

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        scanf("%d",  a + i);

        b[i] = abs((n - i - 1) - i);

    }

    sort(a, a + n);

    sort(b, b + n);

    bool flag = true;

    for (int i = 0; i < n; i++) if (a[i] != b[i]) {

        flag = false;

        break;

    }

    if (!flag) puts("0");

    else printf("%d\n", mypow(2, n / 2));

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#define N (100010)

#define MD (1000000007)

int n,ans,a[N],f[N];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;

	if (n&1){

		if (f[0]!=1) ans=0; else ans=1;

		for (int i=2;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	else {

		ans=1;

		for (int i=1;i<n;i+=2){

			if (f[i]!=2){

				ans=0;

				break;

			}

			else {

				ans=ans*2%MD;

			}

		}

	}

	printf("%d\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int mod = 1000000007;

int num[100005];

int poss[100005];

long long PowerMod(long long a, long long b, long long c)

{

long long ans = 1;

a = a % c;

while(b>0)

{

if(b % 2 == 1)

ans = (ans * a) % c;

b = b/2;

a = (a * a) % c;

}

return ans;

}

int main()

{

    long long  n;

    memset(poss,0,sizeof(poss));

    cin>>n;

    for(int i=0;i<n;i++)

    {

        scanf("%d",&num[i]);

        poss[num[i]]++;

    }

    if(n%2==0)

    {

        for(int i=1;i<n;i+=2)

        {

            if(poss[i]!=2)

            {

                printf("0\n"); return 0;

            }

        }

        long long  k = n/2;

        cout<<PowerMod(2ll,k,mod)<<endl;

    }

    else

    {

        if(poss[0]!=1) {printf("0\n");return 0; }

        for(int i=2;i<n;i+=2)

        {



            if(poss[i]!=2)

            {

                printf("0\n"); return 0;

            }

        }

            long long  k = n/2;

            cout<<PowerMod(2ll,k,mod)<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
# include <cstdio>

# include <map>

# include <cmath>



using namespace std;



const int mod = 1e9+7;



int main()

{

	int n;

	int  a[100005];

	map<int,int> m;

	scanf("%d",&n);

	

	for(int i = 0;i < n;i++)

	{

		scanf("%d",&a[i]);

		m[a[i]]++;

	}



	int flag = 0; 

	if(n%2) //奇数 

	{

		if(m[0] != 1)

		{

			flag = 1;

		}

		for(int i = 2;i < n;i+=2)

		{

			if(m[i] != 2)

			{

				flag = 1;

			}

		}

	}else{

		for(int i = 1;i < n;i+=2)

		{

			if(m[i] != 2)

			{

				flag = 1;

			}

		}

	}

	long long sum = 1;

	

	for(int i =0;i < floor(n/2);i++)

	{

		sum = ((sum % mod) * 2)% mod;

	}

	

	if(n%2)

	{

		if(flag)

		printf("0\n");

		else

		printf("%lld\n",sum);

	}	

	else

	{

		if(flag)

		printf("0\n");

		else

		printf("%lld\n",sum);

	}



	return 0;

 } 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

#include<utility>

#include<stack>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

const int maxn = 1e5 + 5;

const int mod = 1e9 + 7;

int a[maxn];

long long b[maxn];



void init() {

	long long tmp = 1;

	for(int i = 1; i < maxn; i++) {

		tmp = (tmp * i) % mod;

		b[i] = tmp;

	}

}



bool cmp(int x, int y) {

	return x > y;

}



int main() {

	int n;

	long long ans = 1;

	bool flag = 1;

	init();

	cin >> n;

	for(int i = 0; i < n; i++) {

		scanf("%d", &a[i]);

	}

	sort(a, a + n, cmp);

	for(int i = 0; i < n; i++) {

		int key = 1, j = i + 1;

		while(j < n && a[j] == a[i]) {

			j++;

			key++;

		}

		i = j - 1;

		if(key % 2 == 0) {

			ans = (ans * b[key]) % mod;

		} else {

			if(i != n - 1) {

				ans = 0;

			}

			break;

		}

	}

	cout << ans << '\n';

	return 0;

}


// Optimized solution to the same problem (faster):
# include <cstdio>

# include <map>

# include <cmath>



using namespace std;



const int mod = 1e9+7;



int main()

{

	int n;

	int  a[100005];

	map<int,int> m;

	scanf("%d",&n);

	

	for(int i = 0;i < n;i++)

	{

		scanf("%d",&a[i]);

		m[a[i]]++;

	}



	int flag = 0; 

	if(n%2) //奇数 

	{

		if(m[0] != 1)

		{

			flag = 1;

		}

		for(int i = 2;i < n;i+=2)

		{

			if(m[i] != 2)

			{

				flag = 1;

			}

		}

	}else{

		for(int i = 1;i < n;i+=2)

		{

			if(m[i] != 2)

			{

				flag = 1;

			}

		}

	}

	long long sum = 1;

	

	for(int i =0;i < floor(n/2);i++)

	{

		sum = ((sum % mod) * 2)% mod;

	}

	

	if(n%2)

	{

		if(flag)

		printf("0\n");

		else

		printf("%lld\n",sum);

	}	

	else

	{

		if(flag)

		printf("0\n");

		else

		printf("%lld\n",sum);

	}



	return 0;

 } 

// Fastest known solution for this problem: