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;
const int N = 5e5 + 5, MOD = 1e9 + 7;
int tree[N], n, a[N];
void add(int x) {
	++ x;
	while (x <= n) {
		tree[x] ++;
		x += x & -x;
	}
}
int query(int x) {
	++ x;
	int res = 0;
	while (x) {
		res += tree[x];
		x -= x & -x;
	}
	return res;
}
int r[N], P[N];
int main() {
	P[0] = 1;
	for (int i = 1; i < N; ++ i) P[i] = 1LL * P[i - 1] * i % MOD;
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) r[i] = 1;
	int R = 0;
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		a[i] --;
		if (a[i] >= 0) r[a[i]] = 0; else R ++;
	}
	long long sum = 0;
	for (int i = n - 1; i >= 0; -- i) {
		if (r[i] == 1) (sum += i) %= MOD;
		r[i] += r[i + 1];
	}
	long long ans = P[R], sc = 0, tmp = 0;
	for (int i = 1; i <= n; ++ i) {
		if (a[i] >= 0) {
			(ans += 1LL * a[i] * P[n - i] % MOD * P[R]) %= MOD;
			(ans += 1LL * (MOD - query(a[i])) * P[n - i] % MOD * P[R]) %= MOD;
			(ans += 1LL * (MOD - 1LL * sc * (R - r[a[i]]) % MOD * P[R - 1] % MOD) * P[n - i]) %= MOD;
			add(a[i]);
			(tmp += r[a[i]]) %= MOD;
		}
		else {
			(ans += 1LL * sum * P[R - 1] % MOD * P[n - i]) %= MOD;
			(ans += MOD - 1LL * tmp * P[R - 1] % MOD * P[n - i]) %= MOD;
			(ans += MOD - 1LL * (R - 1) * R / 2 % MOD * sc % MOD * P[R - 2] % MOD * P[n - i]) %= MOD;
			sc ++;
		}
	}
	cout << ans << endl;
}

