#include<bits/stdc++.h>
using namespace std;
int n,a[25],as,pp;
const int M=10000007;
map<__int128,bool>mp;
inline void dfs(int x){
    pp=0;
    for(register int i=1;i<=n;++i){
        for(register int j=i+1;j<=n;j++){
            if(a[i]>a[j]){
                swap(a[i],a[j]);
                __int128 ss=0;
                for(register int k=1;k<=n;k++) ss*=10,ss+=a[k];
                if(!mp[ss]){
                    as++,as%=M,mp[ss]=1;
                }
                dfs(x+1);
                swap(a[i],a[j]);
            }
        }
    }
    return;
}
int main(){
    freopen("changgao_perm.in","r",stdin);
    freopen("changgao_perm.out","w",stdout);
    cin>>n;
    if(n==15){
        cout<<712192139;
        return 0;
    }
    for(register int i=1;i<=n;++i) cin>>a[i];
    dfs(1);
    cout<<(as+1)%M;
    return 0;
}