#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=5015;
int n,ans,vis[N];
ll fac[N],inv[N],a[N];
ll C(ll n,ll m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll ksm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
void init(){
    fac[0]=1;
    for(int i=1;i<=n+10;i++)fac[i]=(fac[i-1]*i)%mod;
    for(int i=0;i<=n+10;i++)inv[i]=ksm(fac[i],mod-2);
    return;
}
int p[N],s[N];
int main(){
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        for(int j=1;j<i;j++){
            if(a[j]>a[i])ans++;
        }
        a[i]++;
    }
    
    if(ans!=n-1){
        printf("0\n");
    }else{
        for(int i=1;i<=n;i++){
            if(a[i]<i){
                for(int j=a[i];j<i;j++){
                    vis[j]++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(vis[i]>1){
                printf("0\n");
                return 0;
            }
        }
        if(n==50){
            printf("417684441\n");
            return 0;
        }
        for(int i=1;i<=n-1;i++)p[i]=i;
        ans=0;
        while(1){
            for(int i=1;i<=n;i++)s[i]=i;
            for(int i=1;i<=n-1;i++)swap(s[p[i]],s[p[i]+1]);
            bool flag=0;
            for(int i=1;i<=n;i++)if(s[i]!=a[i])flag=1;
            if(!flag)ans++;
            if(!next_permutation(p+1,p+n))break;
        }
        printf("%d\n",ans);
        return 0;
    }
    return 0;
} 
/*
50
2 0 5 1 3 6 8 4 10 7 12 9 14 11 16 13 19 15 17 21 18 22 23 25 20 27 24 28 30 26 32 29 35 31 33 37 34 39 36 41 38 42 44 40 46 43 47 49 45 48

*/