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

typedef long long ll;
const ll mod=1000000007;
ll ksm(ll a,ll x){
	ll ret=1;
	for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
	return ret;	
}
ll inv(ll a){return ksm(a,mod-2);}

const int maxn=2000;
ll fac[maxn+50];
ll ifac[maxn+50];
void prepare(){
	fac[0]=1;
	for (int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
	ifac[maxn]=inv(fac[maxn]);
	for (int i=maxn-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod; 
}
ll C(ll n,ll m){
	if (m<0 || m>n) return 0;
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;	
}

struct BIT{
	ll tr[maxn+50];
	inline ll lowbit(ll x){return (x&(-x));}
	void add(ll pos,ll val){
		for (int i=pos;i<=maxn;i+=lowbit(i)) tr[i]+=val;
	}
	ll query(ll pos){
		ll ans=0;
		for (int i=pos;i>=1;i-=lowbit(i)) ans+=tr[i];
		return ans;	
	}
};
BIT rec[maxn+50];

ll n;
ll perm[maxn+50];
ll dp[maxn+50][maxn+50];
ll coef[maxn+50];

int main(){
	ios_base::sync_with_stdio(false);
	prepare();
	
	cin >> n;
	for (int i=1;i<=n;i++) cin >> perm[i];
	
	dp[0][0]=1;
	rec[0].add(1,1);
	for (int i=1;i<=n;i++){
		for (int cnt=1;cnt<=n;cnt++){
			dp[i][cnt]=rec[cnt-1].query(perm[i]);
		}
		for (int cnt=1;cnt<=n;cnt++){
			rec[cnt].add(perm[i],dp[i][cnt]);
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=0;j<=i;j++){
			if (j%2==0) coef[i]=(coef[i]+C(i,j)*ksm(i-j,n))%mod;
			else coef[i]=(coef[i]+mod-C(i,j)*ksm(i-j,n)%mod)%mod;
		}
	}
	ll ans=0;
	for (int sel=1;sel<=n;sel++){
		ll sum=0;
		for (int i=1;i<=n;i++) sum=(sum+dp[i][sel])%mod;
		ans=(ans+sum*coef[sel])%mod;
	}
	cout << ans << "\n";
	return 0;	
}