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 <cstdio>
#include <cstring>
#define MOD 1000000007
#define lowbit(x) (x&-x) 
using namespace std; 
const int MAXN = 500005; 
int a[MAXN],n,c[MAXN];
typedef long long ll;
inline void add(int &x,int a)
{
	x+=a;
	if(x>=MOD)x-=MOD;
}
inline void add(int x)
{
	for(;x<=n;x+=lowbit(x))add(c[x],1);
}
inline int sum(int x) {
	int ret=0;
	for(;x;x-=lowbit(x))add(ret,c[x]);
	return ret;
}
inline int ksm(int x,int k)
{
	int ret=1;
	while(k){
		if(k&1)ret=(ll)ret*x%MOD;
		x=(ll)x*x%MOD;
		k>>=1;
	}
	return ret;
}
int s[MAXN];
int ans=0,tot,fac[MAXN],t[MAXN],inv,inv1,ave;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		if(a[i])s[a[i]]=1;
		else ++tot;
	}
	for(int i=1;i<=n;++i){
		if(!s[i])add(ave,i-1);
		s[i]=s[i-1]+s[i];
	}
	inv=ksm(tot,MOD-2);
	inv1=ksm(tot-1,MOD-2);
	int now=0,t=0;
	for(int i=1;i<=tot;++i){
		add(t,(ll)(i-1)*inv1%MOD);
	}
	fac[0]=1;
	for(int i=1;i<=n;++i)fac[i]=(ll)fac[i-1]*i%MOD;
	t=(ll)t*inv%MOD;
	int del=0;
	for(int i=1;i<n;++i){
		int o=sum(a[i]);
		if(!a[i])add(ans,(ll)(((ll)ave*inv%MOD-(ll)now*t%MOD+MOD)%MOD-del+MOD)%MOD*fac[tot]%MOD*fac[n-i]%MOD);
		else add(ans,(ll)(((a[i]-1+MOD)%MOD-o+MOD)%MOD-(ll)now*(a[i]-s[a[i]])%MOD*inv%MOD+MOD)%MOD*fac[tot]%MOD*fac[n-i]%MOD);
		if(a[i]) add(del,(ll)(tot-(a[i]-s[a[i]]))*inv%MOD),add(a[i]);
		else ++now;
	}
	add(ans,fac[tot]);
	cout<<ans<<endl;
	return 0;
}  
