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>
using namespace std;
#define int long long
const int maxn=5*1e5+10;
const int mod=1e9+7;
int n,m,ans,delta,sum0;
int a[maxn],sum1[maxn],sum2[maxn],sum3[maxn],fac[maxn];
bool vis[maxn];
struct Tree_arry
{
	#define lowbit(x) (x&-x)
	int a[maxn];
	inline void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i))a[i]+=k;}
	inline int query(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=a[i];return res;}
}tr;
signed main()
{
	//freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%lld",&n);
	fac[0]=1;for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%mod;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),vis[a[i]]=1;
	for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+(!vis[i]);//ÕýÏò 
	for(int i=n;i;i--)sum2[i]=sum2[i+1]+(!vis[i]);//·´Ïò 
	for(int i=1;i<=n;i++)sum3[i]=sum3[i-1]+(!a[i]);//0µÄ¸öÊý
	m=sum3[n]; 
	for(int i=1;i<=n;i++)if(!vis[i])sum0=(sum0+i-1)%mod;
	for(int i=1;i<=n;i++)
	{
		int res=0;
		if(a[i])
		{
			tr.add(a[i],1);
			res=(res+(a[i]-tr.query(a[i])+mod)%mod*fac[m]%mod)%mod;
			if(m)res=(res-sum3[i]*sum1[a[i]]%mod*fac[m-1]%mod+mod)%mod;
			delta=(delta+sum2[a[i]])%mod;
		}
		else
		{
			res=(res+(sum0-delta+mod)%mod*fac[m-1]%mod)%mod;
			if(m>=2)res=(res-m*(m-1)/2%mod*sum3[i-1]%mod*fac[m-2]%mod)%mod;
		}
		ans=(ans+res*fac[n-i]%mod)%mod;
	}
	printf("%lld",((ans+fac[m])%mod+mod)%mod);
	return 0;
}