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>
#include<assert.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return(ll)a*b%mod;}
int ad(int a,int b){return(a+b)%mod;}
void inc(int&a,int b){(a+=b)%=mod;}
int p[500010],rp[500010],s[500010],fac[500010],np[500010],l[500010],sn[500010];
//s[i] = '-1's in 0...i
//np[i] = count x [x<=i,x not in p]
//l[i] = count j [j<i,pj<pi,pj!=-1]
//sn[i]= sum [j<=i,pj!=-1] np[pj]
int tr[500010],n;
int lowbit(int x){return x&-x;}
void modify(int x){
	while(x<=n){
		tr[x]++;
		x+=lowbit(x);
	}
}
int query(int x){
	int s=0;
	while(x){
		s+=tr[x];
		x-=lowbit(x);
	}
	return s;
}
int C2(ll n){return n*(n-1)/2%mod;}
int main(){
	int k,i,ans,tmp,snp;
	scanf("%d",&n);
	k=0;
	for(i=0;i<n;i++){
		np[i]=1;
		rp[i]=l[i]=-1;
	}
	for(i=0;i<n;i++){
		scanf("%d",p+i);
		p[i]--;
		if(p[i]==-1)
			k++;
		else{
			np[p[i]]=0;
			rp[p[i]]=i;
		}
		s[i]=k;
	}
	for(i=0;i<n;i++){
		if(~rp[i]){
			l[rp[i]]=query(rp[i]+1);
			modify(rp[i]+1);
		}
	}
	l[0]=0;
	for(i=1;i<n;i++){
		if(l[i]==-1)l[i]=l[i-1];
	}
	snp=0;
	for(i=0;i<n;i++){
		if(np[i])inc(snp,i);
	}
	for(i=1;i<=n;i++)np[i]+=np[i-1];
	fac[0]=1;
	for(i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	for(i=0;i<n;i++){
		if(i)sn[i]=sn[i-1];
		if(~p[i])inc(sn[i],np[p[i]]);
	}
	ans=0;
	for(i=0;i<n;i++){
		if(~p[i]){
			tmp=mul(fac[k],l[i]);
			if(k)inc(tmp,mul(mul(np[p[i]],fac[k-1]),s[i]));
			inc(ans,mul(fac[n-1-i],mul(fac[k],p[i])-tmp));
		}else{
			if(i)
				tmp=mul(fac[k-1],mul(i-s[i-1],np[n])-sn[i]);
			else
				tmp=0;
			if(s[i]>1)inc(tmp,mul(s[i]-1,mul(C2(k),fac[k-2])));
			inc(ans,mul(fac[n-1-i],mul(snp,fac[k-1])-tmp));
		}
	}
	inc(ans,fac[k]);
	printf("%d",ad(ans,mod));
}