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>
#define mod 1000000007
using namespace std;
long long n,m,a[500050],s[500050],suf[500050],jc[500050],ans,c[500050];
long long lowbit(int x){ return x&(-x); }
void add(long long x){
	while(x<=n){
		c[x]++;
		x+=lowbit(x);
	}
}
long long que(long long x){
	long long ret=0;
	while(x){
		ret=(ret+c[x])%mod;
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n;
	jc[0]=1;
	for(int i=1;i<=n;i++){
		jc[i]=(jc[i-1]*i)%mod;
		cin>>a[i];
		if(a[i]) s[a[i]]=1;
		m+=(a[i]==0);
	}
	for(int i=1;i<=n;i++){
		suf[i]=s[i]=1-s[i],s[i]+=s[i-1];
	}
	for(int i=n;i>=1;i--) suf[i]+=suf[i+1];
	long long cnt=0,sum=0;
	//cout<<ans<<endl;
	for(int i=n;i>=1;i--){
		if(a[i]){
			sum=que(a[i])*jc[m]%mod;
			sum=(sum+cnt*s[a[i]]%mod*jc[m-1]%mod)%mod;
			ans=(ans+sum*jc[n-i]%mod)%mod;
			add(a[i]);
		}
		else cnt++;
	}
	cnt=sum=0;
	//cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		if(a[i]) ans=(ans+sum*suf[a[i]]%mod*jc[m-1]%mod)%mod;
		else sum=(sum+jc[n-i])%mod,cnt++;
	}
	if(m<2){
		cout<<(ans+jc[m])%mod<<endl;
		return 0;
	}
	sum=m*(m-1)/2,cnt=0;
	for(int i=1;i<=n;i++){
		if(!a[i]) cnt++,ans=(ans+sum*(m-cnt)%mod*jc[m-2]%mod*jc[n-i]%mod)%mod;
	}
	cout<<(ans+jc[m])%mod<<endl;
	return 0;
}