One day Mr. Takahashi picked up a dictionary containing all of the N! permutations of integers 1 through N. The dictionary has N! pages, and page i (1 ≤ i ≤ N!) contains the i-th permutation in the lexicographical order.

Mr. Takahashi wanted to look up a certain permutation of length N in this dictionary, but he forgot some part of it.

His memory of the permutation is described by a sequence P_1, P_2, ..., P_N. If P_i = 0, it means that he forgot the i-th element of the permutation; otherwise, it means that he remembered the i-th element of the permutation and it is P_i.

He decided to look up all the possible permutations in the dictionary. Compute the sum of the page numbers of the pages he has to check, modulo 10^9 + 7.

Constraints

* 1 ≤ N ≤ 500000
* 0 ≤ P_i ≤ N
* P_i ≠ P_j if i ≠ j (1 ≤ i, j ≤ N), P_i ≠ 0 and P_j ≠ 0.

Input

The input is given from Standard Input in the following format:


N
P_1 P_2 ... P_N


Output

Print the sum of the page numbers of the pages he has to check, as modulo 10^9 + 7.

Examples

Input

4
0 2 3 0


Output

23


Input

3
0 0 0


Output

21


Input

5
1 2 3 5 4


Output

2


Input

1
0


Output

1


Input

10
0 3 0 0 1 0 4 0 0 0


Output

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
int fact[1111111];
int inv[1111111];
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}

int C(int n,int k){
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}

struct BIT{
    int N;
    vector<int>dat;
    void init(int n){
        N=n;
        dat.resize(N+1);
    }
    BIT(){}
    BIT(int n){init(n);}

    void add(int k,int x){
        for(k++;k<=N;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N;
int P[555555];

bool ex[555555];
int acc[555555];
signed main(){
    fact[0]=1;
    for(int i=1;i<1111111;i++)fact[i]=fact[i-1]*i%mod;
    inv[1111111-1]=mpow(fact[1111111-1],mod-2);
    for(int i=1111111-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;

    cin>>N;
    rep(i,N)cin>>P[i];
    rep(i,N)ex[P[i]]=true;
    for(int i=1;i<=N;i++){
        acc[i]=acc[i-1];
        if(!ex[i])acc[i]++;
    }


    int ans=0;
    int emp=0;

    int allemp=acc[N];
    BIT bit;bit.init(N+114);
    int sum=0;
    for(int i=N-1;i>=0;i--){
        int f=fact[N-i-1];
        if(P[i]){
            ans=(ans+bit.sum(P[i])*fact[allemp]%mod*f)%mod;
            int s=acc[P[i]];
            if(s){
                ans=(ans+fact[allemp-1]*emp%mod*s%mod*f)%mod;
            }
            bit.add(P[i],1);
            if(allemp)sum=(sum+fact[allemp-1]*(acc[N]-acc[P[i]]))%mod;
            continue;
        }
        int tmp=allemp*(allemp-1)/2;
        tmp%=mod;
        if(emp)ans=(ans+tmp*fact[allemp-2]%mod*emp%mod*f)%mod;
        ans=(ans+sum*f)%mod;
        emp++;
    }
    ans=(ans+fact[allemp])%mod;
    cout<<ans<<endl;
    return 0;
}
