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 <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int N=500010;
const int mod=1000000007;

int a[N],s1[N],s2[N],s3[N],fac[N],c[N];
bool ok[N];

int lowbit(int x) {return x&(-x);}

void change(int x,int n)
{
	while (x<=n)
	{
		c[x]++;x+=lowbit(x);
	}
}

int query(int x)
{
	int s=0;
	while (x)
	{
		s+=c[x];x-=lowbit(x);
	}
	return s;
}

int main()
{
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);ok[a[i]]=1;}
	s1[0]=0;for (int i=1;i<=n;i++) if (!ok[i]) s1[i]=s1[i-1]+1; else s1[i]=s1[i-1];
	s2[n+1]=0;for (int i=n;i;i--) if (!ok[i]) s2[i]=s2[i+1]+1; else s2[i]=s2[i+1];
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=ll(fac[i-1])*i%mod;
	s3[0]=0;for (int i=1;i<=n;i++) if (!a[i]) s3[i]=(s3[i-1]+fac[n-i])%mod; else s3[i]=s3[i-1];
	int ans=0;
	int cnt=0,k=s1[n];
	for (int i=n;i;i--)
		if (a[i])
		{
			if (k) ans=(ll(s2[a[i]])*s3[i]%mod*fac[k-1]+ans)%mod;
			if (k) ans=(ll(s1[a[i]])*cnt%mod*fac[n-i]%mod*fac[k-1]+ans)%mod;
			ans=(ll(query(a[i]))*fac[n-i]%mod*fac[k]+ans)%mod;
			change(a[i],n);
		}
		else
		{
			if (k>1) ans=(ll(k)*(k-1)/2%mod*cnt%mod*fac[n-i]%mod*fac[k-2]+ans)%mod;
			cnt++;
		}
	printf("%d\n",(ans+fac[k])%mod);
	return 0;
}
