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<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int const N = 5e5 + 41;
int const MOD = 1e9 + 7;

int n, f[N], invF[N], p[N], cntFree, ans, mark[N], grFree[N], leBusy[N], F[N];

int mul(int a, int b){
	return a * 1LL * b % MOD;
}

void add(int &a, int b){
	a += b;
	if(a >= MOD){
		a -= MOD;
	}
}

void sub(int &a, int b){
	a -= b;
	while(a < 0){
		a += MOD;
	}
}

int bp(int x, int d){
	if(!d){
		return 1;
	}
	if(d&1){
		return x * 1LL * bp(x, d-1) % MOD;
	}
	int r = bp(x, d/2);
	return r * 1LL * r % MOD;
}

void calcF(){
	f[0] = invF[0] = 1;
	for(int i=1;i<N;++i){
		f[i] = f[i-1] * 1LL * i % MOD;
		invF[i] = bp(f[i], MOD-2);
	}
}

int getC(int n, int k){
	if(k > n){
		return 0;
	}
	int ret = f[n];
	ret = ret * 1LL * invF[k] % MOD;
	ret = ret * 1LL * invF[n-k] % MOD;
	return ret;
}

void prepare(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
}

void read(){
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d",&p[i]);
		if(p[i] != 0){
			mark[p[i]] = 1;
		}else{
			++cntFree;
		}
	}
}

void solveFF(){
	int cntLeftFree = 0;
	for(int i=0;i<n;++i){
		if(p[i] != 0){
			continue;
		}
		if(cntFree-cntLeftFree-1 >= 0){
			int cur = (cntFree * 1LL * (cntFree-1) / 2) % MOD;
			cur = mul(cur, getC(cntFree - 2, cntLeftFree));
			cur = mul(cur, f[cntLeftFree]);
			cur = mul(cur, f[cntFree-cntLeftFree-1]);
			cur = mul(cur, f[n-1-i]);
			add(ans, cur);
		}
		++cntLeftFree;
	}
}

int buildGrFree(){
	int ret = 0;
	int curFree = 0;
	for(int i=n;i>0;--i){
		if(mark[i]){
			add(ret, curFree);
			grFree[i] = curFree;
		}else{
			++curFree;
		}
	}
	return ret;
}

void solveFC(){
	int ways = buildGrFree();
	int cntFreeLeft = 0;
	for(int i=0;i<n;++i){
		if(p[i] == 0){
			if(cntFree-cntFreeLeft-1 >= 0){
				int cur = ways;
				cur = mul(cur, getC(cntFree-1, cntFreeLeft));
				cur = mul(cur, f[cntFreeLeft]);
				cur = mul(cur, f[cntFree-cntFreeLeft-1]);
				cur = mul(cur, f[n-1-i]);
				add(ans, cur);
			}
			++cntFreeLeft;
		}else{
			sub(ways, grFree[p[i]]);
		}
	}
}

void buildLeBusy(){
	int curFree = 0;
	for(int i=1;i<=n;++i){
		if(mark[i]){
			leBusy[i] = curFree;
		}else{
			++curFree;
		}
	}
}

void solveCF(){
	buildLeBusy();
	int cntLeftFree = 0;
	for(int i=0;i<n;++i){
		if(p[i] == 0){
			++cntLeftFree;
		}else{
			if(cntFree-cntLeftFree >= 0){
				int cur = leBusy[p[i]];
				cur = mul(cur, getC(cntFree-1, cntLeftFree));
				cur = mul(cur, f[cntLeftFree]);
				cur = mul(cur, f[cntFree-cntLeftFree]);
				cur = mul(cur, f[n-1-i]);
				add(ans, cur);
			}
		}
	}
}

void upd(int x, int add){
	while(x < N){
		F[x] += add;
		x |= (x+1);
	}
}

int get(int x){
	int ret = 0;
	while(x >= 0){
		ret += F[x];
		x = (x&(x+1)) - 1;
	}
	return ret;
}

void buildFen(){
	for(int i=n-1;i>=0;--i){
		if(p[i] != 0){
			upd(p[i], 1);
		}
	}
}

void solveCC(){
	buildFen();
	int cntLeftFree = 0;
	for(int i=0;i<n;++i){
		if(p[i] == 0){
			++cntLeftFree;
		}else{
			if(cntFree - cntLeftFree >= 0){
				int cur = get(p[i]-1);
				cur = mul(cur, getC(cntFree, cntLeftFree));
				cur = mul(cur, f[cntLeftFree]);
				cur = mul(cur, f[cntFree-cntLeftFree]);
				cur = mul(cur, f[n-1-i]);
				add(ans, cur);
			}
			upd(p[i], -1);
		}
	}
}

void solve(){
	add(ans, f[cntFree]);
	solveFF();
	solveFC();
	solveCF();
	solveCC();
}

int main(){
	prepare();
	calcF();
	read();
	solve();
	printf("%d\n",ans);

#ifdef _DEBUG
	vector<int> ac;
	for(int i=0;i<4;++i){
		ac.push_back(i + 1);
	}
	int cn = 0;
	do{
		++cn;
		printf("%d : ",cn);
		for(int i=0;i<4;++i){
			printf("%d ",ac[i]);
		}
		printf("\n");
	} while(next_permutation(ac.begin(), ac.end()));
#endif
	return 0;
}