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<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000000007;
int M=510000;
long long inv[510000];
long long fact[510000];
long long factinv[510000];
int b[510000];
int at[510000];
int v[510000];
pair<int,int> p[510000];
int bit[510000];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<510000;a|=a+1)bit[a]+=b;
}
int main(){
	inv[1]=fact[0]=factinv[0]=1;
	for(int i=2;i<M;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<M;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=1;i<M;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	int a;scanf("%d",&a);
	int ind=0;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		b[i]--;
		v[b[i]]++;
		if(b[i]>=0){
			p[ind++]=make_pair(b[i],i);
		}
	}
	int sz=0;
	for(int i=0;i<a;i++)if(!v[i])at[sz++]=i;
	long long ret=0;
	int cnt=0;
	long long ad=0;
	long long hu=0;
	long long ks=1;
	int ps=0;
	for(int i=0;i<a;i++)if(b[i]==-1)ps++;
	for(int i=a-1;i>=0;i--){
		
		if(b[i]==-1){
			cnt++;
			ret=(ret+(long long)(cnt)*(cnt-1)/2%mod*inv[cnt]%mod*fact[ps]%mod*ks)%mod;
			ret=(ret+ad%mod*inv[sz]%mod*ks%mod*fact[ps])%mod;
		}else{
			int ts=sum(0,b[i]);
			hu=(hu+(long long)ts*ks%mod)%mod;
			int tmp=lower_bound(at,at+sz,b[i])-at;
			hu=(hu+(long long)tmp*cnt%mod*inv[sz]%mod*ks)%mod;
			add(b[i],1);
			ad+=sz-tmp;
		}
	//	printf("%lld\n",ret);
		ks=ks*(a-i)%mod;
	}
	//printf("%lld\n",ret);
	ret=(ret+fact[cnt])%mod;
	ret=(ret+hu%mod*fact[cnt])%mod;
	printf("%lld\n",ret);
}