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;
int modulo(1e9 + 7);
const int N(555555);
int a[N], cnt[N], le[N], bt[N], fac[N];
bool vst[N];
int n;
int getSum(int x) {
	int res(0);
	for(int i(x); i; i -= i & -i)
		res += bt[i];
	return res;
}
void inc(int x) {
	for(int i(x); i <= n; i += i & -i)
		bt[i] += 1;
}
int main() {
	cin >> n;
	fac[0] = 1;
	for(int i(1); i <= n; i++) {
		fac[i] = 1ll * i * fac[i - 1] % modulo;
	}
	for(int i(1); i <= n; i++) {
		cin >> a[i];
		cnt[i] = cnt[i - 1];
		if(a[i] == 0) {
			cnt[i]++;
		}else {
			vst[a[i]] = true;
		}
	}
	int sum(0);
	for(int i(1); i <= n; i++) {
		if(!vst[i]) {
			le[i] = 1;
			sum = (sum + i) % modulo;
		}
	}
	for(int i(1); i <= n; i++) {
		le[i] += le[i - 1];
	}
	int ans(0), cur(0);
	for(int i(1); i <= n; i++) {
		if(a[i]) {
			int tmp(0);
			tmp = (tmp + 1ll * (a[i] - 1) * fac[cnt[n]]) % modulo;
			int nu(getSum(a[i]));
			tmp = (tmp - 1ll * fac[cnt[n]] * nu % modulo + modulo) % modulo;
			//k = cnt[i], l = cnt[n] - k, a = le[a[i]]
			if(cnt[i]) {
				tmp = (tmp - 1ll * le[a[i]] * cnt[i] % modulo * fac[cnt[n] - 1] % modulo + modulo) % modulo;
			}
			//printf("tmp[%d] = %d\n", i, tmp);
			ans = (ans + 1ll * fac[n - i] * tmp) % modulo;
			inc(a[i]);
			cur = (cur + (cnt[n] - le[a[i]])) % modulo;
		}else {
			//k = cnt[i], m = cnt[n]
			int tmp(0);
			tmp = (tmp + 1ll * (sum - cnt[n] + modulo) * fac[cnt[n] - 1]) % modulo;

			tmp = (tmp - 1ll * cnt[n] * (cnt[n] - 1) / 2 % modulo * (cnt[i] - 1) % modulo * fac[cnt[n] - 2] % modulo + modulo) % modulo;
			tmp = (tmp - 1ll * cur * fac[cnt[n] - 1] % modulo + modulo) % modulo;
			ans = (ans + 1ll * fac[n - i] * tmp) % modulo;
		}

	}
	cout << (ans + fac[cnt[n]]) % modulo << endl;
}
