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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
    return powmod(a, MOD-2);
}
ll f[500050];
void fac(int n){
    f[0]=1;
    for(ll i=1; i<=n; i++) f[i]=f[i-1]*i%MOD;
}
template<typename T>
struct BIT{ //1-indexed
    vector<T> bit;
    int size;
    BIT(int n):size(n), bit(n+1, 0){}
    T sum(int i){
        T s=0;
        while(i>0){
            s+=bit[i];
            i-=(i&(-i));
        }
        return s;
    }
    void add(int i, T x){
        while(i<=size){
            bit[i]+=x;
            i+=(i&(-i));
        }
    }
};
int main()
{
	int n;
	scanf("%d", &n);
	fac(n);
	bool used[500050]={};
	int p[500050];
	int cnt0=0;
	ll s1=0, s2=0;
	for(int i=1; i<=n; i++){
		scanf("%d", &p[i]);
		if(p[i]) used[p[i]]=1;
		else cnt0++;
		if(p[i]==0) (s1+=f[n-i])%=MOD;
	}
	for(int i=1; i<=n; i++){
		if(!used[i]) s2+=i-1;
	}
	s2%=MOD;
	ll ans=f[cnt0];
	if(cnt0){
		(ans+=s1*s2%MOD*f[cnt0-1])%=MOD;
	}
	for(int i=1; i<=n; i++){
		if(p[i]) (ans+=f[cnt0]*f[n-i]%MOD*(p[i]-1))%=MOD;
	}
	int c1[500050];
	c1[0]=0;
	for(int i=1; i<=n; i++){
		c1[i]=c1[i-1];
		if(!used[i]) c1[i]++;
	}
	int cnt1=0;
	for(int i=1; i<=n; i++){
		if(p[i] && cnt0){
			ll s=f[n-i]*f[cnt0-1]%MOD*c1[p[i]-1]%MOD*cnt1%MOD;
			(ans+=MOD-s)%=MOD;
		}
		if(p[i]==0) cnt1++;
	}
	BIT<int> bit(n);
	ll s3=0;
	for(int i=1; i<=n; i++){
		if(p[i]){
			ll s=f[n-i]*f[cnt0]%MOD*bit.sum(p[i]-1)%MOD;
			(ans+=MOD-s)%=MOD;
			bit.add(p[i], 1);
			(s3+=c1[n]-c1[p[i]])%=MOD;
		}else{
			if(cnt0){
				ll s=f[n-i]*f[cnt0-1]%MOD*s3%MOD;
				(ans+=MOD-s)%=MOD;
			}
		}
	}
	if(cnt0>=2){
		ll d=(ll)cnt0*(cnt0-1)/2%MOD;
		int cnt2=0;
		for(int i=1; i<=n; i++){
			if(p[i]==0){
				ll s=f[n-i]*f[cnt0-2]%MOD*cnt2%MOD*d%MOD;
				(ans+=MOD-s)%=MOD;
				cnt2++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}