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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#define SIZE 500005
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct BIT
{
	int bit[SIZE];
	
	void init()
	{
		memset(bit,0,sizeof(bit));
	}
	void add(int k,int x)
	{
		while(k<SIZE)
		{
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int get(int k)
	{
		int ret=0;
		while(k>0)
		{
			ret+=bit[k];
			k-=k&-k;
		}
		return ret;
	}
	int get(int s,int t)
	{
		return get(t)-get(s-1);
	}
};
BIT bit;
ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int A[SIZE];
ll sum[SIZE];
bool use[SIZE];

int main()
{
	make();
	int n;
	scanf("%d",&n);
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		if(A[i]>=1) use[A[i]]=true;
	}
	vector <int> zan;
	for(int i=1;i<=n;i++) if(!use[i]) zan.push_back(i);
	int now=0;
	ll st=0;
	ll ret=fac[zan.size()];
	bit.init();
	for(int i=n-1;i>=0;i--)
	{
		if(A[i]==0)
		{
			now++;
			ll way=C(zan.size(),now)*C(now,2)%MOD*fac[now-1]%MOD*fac[zan.size()-now]%MOD;
			way+=st*fac[zan.size()-1]%MOD;
			if(way>=MOD) way-=MOD;
			sum[i]=way;
		}
		else
		{
			int pos=lower_bound(zan.begin(),zan.end(),A[i])-zan.begin();
			st+=zan.size()-pos;
			if(now>=1)
			{
				sum[i]=(ll) pos*C(zan.size()-1,now-1)%MOD*fac[zan.size()-now]%MOD*fac[now]%MOD;
			}
			sum[i]+=(ll) bit.get(A[i])*(ll) fac[zan.size()]%MOD;
			if(sum[i]>=MOD) sum[i]-=MOD;
			bit.add(A[i],1);
			st%=MOD;
		}
		ret+=sum[i]*fac[n-i-1]%MOD;
		if(ret>=MOD) ret-=MOD;
		//printf("%lld\n",sum[i]);
	}
	printf("%lld\n",ret);
	return 0;
}
