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 <vector>
#include <utility>
using namespace std;
typedef long long ll;
ll n,N = 1000020,bit[1000010],a[500010],b[500010],c[2][500010],d[2][500010];
ll mod = 1000000007,f[500010],ans = 0;
bool used[500010];
vector<pair<ll,ll>> v;
vector<ll> w;
ll sum(int i){
	ll s = 0;
	while(i>=0){
		s += bit[i];
		i = (i&(i+1)) - 1;
	}
	return s;
}

ll add(int i, int x){
	while(i<=N){
		bit[i] += x;
		i |= i+1;
	}
}

void rev1(){
	int i,j = 0;
	for(i=1;i<=n;i++){
		if(used[i]) b[i] = j;
		j++;
	}
	for(i=(int)v.size()-1;i>=0;i--){
		(ans += f[n - v[i].first]*(sum(b[v[i].second]))) %= mod;
		add(b[v[i].second],1);
	}
	(ans *= (f[w.size()])) %= mod;
}

void rev2(){
	ll i,k = w.size();
	ll inv = (mod + 1)/2;
	for(i=0;i<w.size();i++){
		(ans += f[n - w[i]]*f[k]%mod*(k - 1 - i)%mod*inv) %= mod;
	}
}

void rev3(){
	for(int i=1;i<=n;i++){
		if(a[i]) (ans += (d[0][a[i]]*c[0][i] + d[1][a[i]]*c[1][i]%mod*f[n-i])%mod*f[w.size()-1]%mod) %= mod;
	}
}

int main(){
	ll i,cnt1 = 0,cnt2 = 0,cnt3 = 0,sum = 0;
	cin >> n;
	for(i=1;i<=n;i++) used[i] = false;
	f[0] = 1;
	for(i=1;i<=n;i++){
		cin >> a[i];
		if(a[i]){
			v.push_back({i,a[i]});
			used[a[i]] = true;
		}else{
			w.push_back(i); cnt1++;
		}
		f[i] = f[i-1]*i%mod;
	}
	for(i=1;i<=n;i++){
		if(a[i]){
			c[0][i] = sum;
			c[1][i] = cnt1 - cnt2;
		}else{
			cnt2++; (sum += f[n - i]) %= mod;
		}
	}
	for(i=1;i<=n;i++){
		if(used[i]) d[1][i] = cnt3;
		else cnt3++;
	}
	cnt3 = 0;
	for(i=n;i>=1;i--){
		if(used[i]) d[0][i] = cnt3;
		else cnt3++;
	}
	rev1(); rev2(); rev3();
	(ans += f[w.size()]) %= mod;
	cout << ans << endl;
}