C++ :

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=5e5+5;
const int D=1004535809;
ll mi(ll x,int y=D-2)
{
	ll ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}

int a[N],b[N],cnt[N*2];	
ll jie[N*2];

namespace FFT
{
struct Complex
{
	double x,y;
};
Complex operator +(const Complex &a,const Complex &b)
{
	return (Complex){a.x+b.x,a.y+b.y};
}
Complex operator -(const Complex &a,const Complex &b)
{
	return (Complex){a.x-b.x,a.y-b.y};
}
Complex operator *(const Complex &a,const Complex &b)
{
	return (Complex){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
	
const int N=1<<21;
const double pi=acos(-1);
Complex a[N],b[N],c[N],w[N];int rev[N];
void init(int n)
{
	int m=n/2;
	rep(i,1,n-1) rev[i]=(rev[i>>1]>>1)+m*(i&1);
	rep(i,0,n-1)
	{
		double t=2*pi*i/n;
		w[i]=(Complex){cos(t),sin((long double)t)};
	}
}
void fft(Complex *a,int n,int flag)
{
	if(flag==-1)reverse(w+1,w+n);
	rep(i,0,n-1)
	if(rev[i]<i) swap(a[i],a[rev[i]]);
	for(int i=2;i<=n;i<<=1)
	{
		int m=i/2;
		for(int j=0;j<n;j+=i)
		{
			Complex *a1=a+j,*a2=a1+m;
			for(int k=0;k<m;++k)
			{
				Complex x=a1[k],y=a2[k]*w[n/i*k];
				a1[k]=x+y;a2[k]=x-y;
			}
		}
	}
	if(flag==-1)rep(i,0,n-1)a[i].x/=n;
}
void mul(int n)
{
	int d=1;
	while(d<=n)d<<=1;
	init(d);
	fft(a,d,1);fft(b,d,1);
	rep(i,0,d-1)c[i]=a[i]*b[i];
	fft(c,d,-1);
}
};

int main()
{
//	freopen("1.in","r",stdin);
	int n;
	cin>>n;
	rep(i,1,n)scanf("%d",a+i);
	
	rep(i,1,n)b[i]=a[i]-i;
	
	int m=n+a[1];
	jie[0]=1;
	rep(i,1,m)jie[i]=jie[i-1]*i%D;
	
	ll ans=1;
	rep(i,1,n)(ans*=jie[a[i]])%=D;
	rep(i,1,n)(ans*=mi(jie[b[i]+n]))%=D;

	m=b[1]-b[n];
	rep(i,1,n)++FFT::a[b[i]-b[n]].x;
	rep(j,1,n)++FFT::b[b[1]-b[j]].x; //cnt[b[i]-b[j]];
	FFT::mul(m*2); 
	rep(i,1,m)(ans*=mi(i,int(FFT::c[m+i].x+0.5)/*cnt[i]*/))%=D;

	cout<<ans;
}