#include <bits/stdc++.h>
using namespace std;
const int m=1000000007;

unsigned long long enc(const vector<int>& v){
    unsigned long long c=0,b=1;
    for(int i=0;i<v.size();i++){int x=v[i];c+=x*b;b*=11;}
    return c;
}

vector<int> dec(unsigned long long c,int n){
    vector<int> p(n);
    for(int i=0;i<n;++i){p[i]=c%11;c/=11;}
    return p;
}

int main(){
	freopen("changgao_perm.in","r",stdin);
	freopen("changgao_perm.out","w",stdout);
    int n;scanf("%d",&n);vector<int> a(n);for(int i=0;i<n;++i)scanf("%d",&a[i]);
    unordered_set<unsigned long long> vis;queue<unsigned long long> q;
    unsigned long long ic=enc(a);vis.insert(ic);q.push(ic);
    while(!q.empty()){
        unsigned long long cc=q.front();q.pop();
        vector<int> cp=dec(cc,n);
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                if(cp[i]>cp[j]){
                    swap(cp[i],cp[j]);
                    unsigned long long nc=enc(cp);
                    if(!vis.count(nc)){vis.insert(nc);q.push(nc);}
                    swap(cp[i],cp[j]);
                }
    }
    printf("%d\n",(int)(vis.size()%m));
    return 0;
}