stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.130182463804755x):
#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN = 2000;

const int INF = (1<<30);

struct edge{

	int to; edge *nxt;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}

int a[MAXN + 5], N;

int f[MAXN + 5], s[MAXN + 5];

void dfs(int x, int fa) {

	s[x] = a[x], f[x] = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		dfs(p->to, x), s[x] += s[p->to];

		f[x] += f[p->to] + s[p->to];

	}

}

int get(int x, int fa) {

	int mx = 0;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == fa ) continue;

		if( mx == 0 || f[p->to] > f[mx] ) mx = p->to;

	}

	if( mx == 0 ) return 0;

	int k = get(mx, x) + s[mx];

	if( f[x] - f[mx] - s[mx] >= k ) return f[x] & 1;

	else return k - (f[x] - f[mx] - s[mx]);

}

char S[MAXN + 5];

int main() {

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

	for(int i=1;i<=N;i++) a[i] = S[i] - '0';

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

		int u, v; scanf("%d%d", &u, &v);

		addedge(u, v);

	}

	int ans = INF;

	for(int j=1;j<=N;j++) {

		dfs(j, 0);

		if( get(j, 0) == 0 )

			ans = min(ans, f[j]/2);

	}

	if( ans == INF ) printf("-1\n");

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

}

//
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.450086730530774x):
#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;

}
// Slower C++ solution:
#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;

}//

// Faster C++ solution for the same problem (measured speedup: 5.151374596986001x):
#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;

}
// Slower C++ solution:
#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);

}


// Faster C++ solution for the same problem (measured speedup: 5.14761643709369x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.144399553110441x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.4121877313943014x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.4121877313943014x):
#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]++;//a[7]++

			

			//给出数据x出错 

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

				flag=0;

				cout<<"0"<<endl;

				break;

			}

			

			//正确情况 

			if(a[x]==1)

				ans=ans*2%MOD; // a * b %c == a%c * b%c 

		}

	} 

	

	else{ //奇数 

	

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

			ll x;

			cin>>x;

			a[x]++;

			

			//给出数据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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.4079265667747234x):
#include<iostream>



int a[100005];

int num[100005];

const int mod = 1000000007;



int main() {

    int n;

    std:: cin >> n;

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

        std::cin >> a[i];

        num[a[i]]++;

    }

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

        if(i % 2 == 0) {

            if(num[n - i] != 0) {

                std::cout << 0 << std::endl;

                return 0;

            }

        } else {

            if(num[n - i] != 2) {

                std::cout << 0 << std::endl;

                return 0;

            }

        }

    }

    if(n % 2 == 0 && num[0] != 0) {

        std::cout << 0 << std::endl;

        return 0;

    } else if(n % 2 != 0 && num[0] != 1) {

        std::cout << 0 << std::endl;

        return 0;

    }

    n /= 2;

    long long ans = 1;

    long long two = 2;

    while(n) {

        if(n & 1)

            ans *= two;

        ans %= mod;

        two *= two;

        two %= mod;

        n >>= 1;

    }

    std::cout << ans << std::endl;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.23031548505721x):
#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);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.238878356943423x):
#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);

}
// Slower C++ solution:
#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;

}






// Faster C++ solution for the same problem (measured speedup: 5.20277414314728x):
#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);

}
// Slower C++ solution:
#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;



}


// Faster C++ solution for the same problem (measured speedup: 5.153210442365201x):
#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);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.142726741127216x):
#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);

}