#include<cstdio>
#include<vector>
#include<cstring>
#define N 300001
#define M 2001
#define mod 1000000007
using namespace std;
int a[N];
long long count[N],dj[N];
long long hz[N];
long long f[5][N],g[5][M][M],beh[N];
int n;
vector<int>place[N];
long long ksmi(long long x,long long y)
{
	long long p=y,ab=x,total=1;
	while (p)
	{
		if (p%2==1) total=total*ab%mod;
		ab=ab*ab%mod;
		p/=2;
	}
	return total;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) hz[i]--;
	for (int i=1;i<=n;i++) hz[a[i]]++;
	for (int i=n;i>=1;i--) hz[i]+=hz[i+1];
	for (int i=1;i<=n;i++)
		if (hz[i]+1<=0)
		{
			printf("0\n");
			return 0;
		}
	for (int i=1;i<=n;i++) count[a[i]]++;
	for (int i=1;i<=n;i++)
		place[i].resize(count[i]+1);
	memset(count,0,sizeof(count));
	for (int i=1;i<=n;i++)
	{
		count[a[i]]++;
		place[a[i]][count[a[i]]]=i;
	}
	dj[4]=0;dj[3]=-1;dj[2]=-2;dj[1]=-1;dj[0]=0;
	f[0][n+1]=1;
	for (int i=n;i>=1;i--)
	{
		for (int j=4;j>=0;j--)
		{
			if (hz[i]+1+dj[j]<0) continue;
			f[j][i]=(f[j][i]+f[j][i+1]*(hz[i]+1+dj[j])%mod)%mod;
		}
		f[4][i]=(f[4][i]+f[3][i+1])%mod;
		f[3][i]=(f[3][i]+f[2][i+1])%mod;
		if (hz[i]+1+dj[2]>0)
			f[2][i]=(f[2][i]+f[1][i+1]*count[i]%mod*(hz[i]+1+dj[2])%mod)%mod;
		if (hz[i]+1+dj[1]>0)
			f[1][i]=(f[1][i]+f[0][i+1]*count[i]%mod*(hz[i]+1+dj[1])%mod)%mod;
		f[3][i]=(f[3][i]+f[1][i+1]*count[i]%mod)%mod;
		if (hz[i]+1+dj[2]>0)
			f[2][i]=(f[2][i]+f[0][i+1]*(count[i]*(count[i]-1)/2)%mod*(hz[i]+1+dj[2])%mod)%mod;
		f[3][i]=(f[3][i]+f[0][i+1]*(count[i]*(count[i]-1)/2)%mod)%mod;
	}
	long long ans1=f[4][1];
	dj[4]=0;dj[3]=-1;dj[2]=0;dj[1]=-1;
	beh[n+1]=1;
	for (int i=n;i>=1;i--)
		beh[i]=beh[i+1]*(hz[i]+1)%mod;
	for (int i=1;i<=n;i++)
	{
		if (hz[a[i]]+1+dj[1]>0)
			g[1][a[i]][i]=(g[1][a[i]][i]+beh[a[i]+1]*(hz[a[i]]+1+dj[1])%mod)%mod;
		g[2][a[i]][i]=(g[2][a[i]][i]+beh[a[i]+1])%mod;	
	}
	for (int i=n;i>=1;i--)
	{
		for (int k=1;k<=n;k++)
		{
			int l=1,r=count[i];
			long long ans=0;
			while (l<=r)
			{
				int mid=(l+r)/2;
				if (place[i][mid]<=k)
				{
					ans=mid;
					l=mid+1;
				}
				else
					r=mid-1;
			}
			ans=count[i]-ans;
			for (int j=4;j>=1;j--)
			{
				if (hz[i]+1+dj[j]>=0)
					g[j][i][k]=(g[j][i][k]+g[j][i+1][k]*(hz[i]+1+dj[j])%mod)%mod;
			}
			g[2][i][k]=(g[2][i][k]+g[1][i+1][k])%mod;
			if (hz[i]+1+dj[3]>=0)
				g[3][i][k]=(g[3][i][k]+g[2][i+1][k]*ans%mod*(hz[i]+1+dj[3])%mod)%mod;
			g[4][i][k]=(g[4][i][k]+g[2][i+1][k]*ans%mod)%mod;
			g[4][i][k]=(g[4][i][k]+g[3][i+1][k])%mod;
		}
	}
	for (int i=1;i<=n;i++)
		ans1=(ans1+g[4][1][i])%mod;
	printf("%d\n",ans1);
}