#include<bits/stdc++.h>
#define endl '\n'
#include "gondola.h"
using namespace std;
const long long int maxn=1000000009;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int v,st;
};
bool cmp(cell a1,cell a2)
{
return a1.st<a2.st;
}
int n,a[200005],ind[200005],se[200005];
cell c[200005];
vector<bool>used(1000000009);
int valid(int n,int seq[])
{
int br=0;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
}
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
if(!br)br=a[i];
else
{
if(a[i]!=br)
{
return 0;
}
}
}
if(used[a[i]])
{
return 0;
}
used[a[i]]=1;
if(br)br++;
if(br>n)br=1;
}
for(int i=n+2; i<=250000; i++)
{
if(used[i]&&!used[i-1])
{
return 0;
}
}
return 1;
}
int replacement(int n, int seq[], int rseq[])
{
int st=1,val=1,next=n+1;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
}
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
st=i;
val=a[i];
break;
}
}
for(int i=st; i<=n; i++)
{
ind[i]=val;
val++;
if(val>n)val=1;
}
for(int i=1; i<st; i++)
{
ind[i]=val;
val++;
}
for(int i=1; i<=n; i++)
{
c[i].v=ind[i];
c[i].st=a[i];
}
sort(c+1,c+n+1,cmp);
int br=0;
for(int i=1; i<=n; i++)
{
if(c[i].st>n)
{
while(c[i].v!=c[i].st)
{
rseq[br]=c[i].v;
br++;
c[i].v=next;
next++;
}
}
}
return br;
}
long long int fup(long long int base,long long int pow)
{
long long int otg=1;
for(int i=0; i<=30; i++)
{
if(pow&(1<<i))
{
otg*=base;
otg=otg%maxn;
}
base*=base;
base=base%maxn;
}
return otg;
}
bool check()
{
int br=0;
for(int i=1; i<=n; i++)
{
if(a[i]<=n)
{
if(!br)br=a[i];
else
{
if(a[i]!=br)
{
return 0;
}
}
}
if(used[a[i]])
{
return 0;
}
used[a[i]]=1;
if(br)br++;
if(br>n)br=1;
}
return 1;
}
int countReplacement(int n, int seq[])
{
long long int otg=1,now=n,f=0;
for(int i=1; i<=n; i++)
{
a[i]=seq[i-1];
if(a[i]<=n)f=1;
}
if(!check())return 0;
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
{
if(a[i]>now)
{
otg=otg*fup(n-i+1,a[i]-now-1);
otg=otg%maxn;
now=a[i];
}
}
if(f)return otg;
else return (otg*n)%maxn;
}
void test()
{
cin>>n;
long long int otg=1,now=n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
se[i-1]=a[i];
}
if(!check())
{
cout<<0<<endl;
return;
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
{
if(a[i]>n)
{
otg=otg*fup(n-i+1,a[i]-now-1);
otg=otg%maxn;
now=a[i];
}
}
cout<<otg<<endl;
}
/*int main()
{
speed();
test();
return 0;
}
*/
