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 <cstring>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 7;
const int MOD = 1e9 + 7;

int n, p[N], nn[N];

int visit[N], lower[N], h[N];

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

void ins(int pos) {
	for (int i = pos; i <= n; i += lowbit(i)) {
		h[i]++;
	}
}

int ask(int pos) {
	int ret = 0;
	for (int i = pos; i; i -= lowbit(i)) {
		ret += h[i];
	}
	return ret;
}

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
	if (a < 0) a += MOD;
}

int calc(int x) {
	return 1LL * x * (x + 1) / 2 % MOD;
}

int main() {
	scanf("%d", &n);
	nn[0] = 1;
	for (int i = 1; i <= n; i++) {
		nn[i] = 1LL * nn[i - 1] * i % MOD;
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		if (p[i] != 0) {
			visit[p[i]] = 1;
		}
	}
	int sum = 0;
	vector<int> remain;
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) {
			remain.push_back(i);
			add(sum, i - 1);
		}
		lower[i] = lower[i - 1] + !visit[i];
	}
	int ans = 0, k = 0;
	int ss = 0;
	for (int i = 1; i <= n; i++) {
		if (p[i] != 0) {
			add(ans, 1LL * nn[n - i] * (p[i] - 1) % MOD * nn[remain.size()] % MOD);
			int s = ask(p[i]);
			add(ans, -1LL * s * nn[n - i] % MOD * nn[remain.size()] % MOD);
			add(ans, -1LL * nn[n - i] * k % MOD * nn[remain.size() - 1] % MOD * lower[p[i]] % MOD);
			add(ss, lower[n] - lower[p[i]]);
			ins(p[i]);
		} else {
			k++;
			add(ans, 1LL * nn[n - i] * sum % MOD * nn[remain.size() - 1] % MOD);
			add(ans, -1LL * ss * nn[n - i] % MOD * nn[remain.size() - 1] % MOD);
			if (remain.size() > 1) {
				add(ans, -1LL * calc(remain.size() - 1) * (k - 1) % MOD * nn[remain.size() - 2] % MOD * nn[n - i] % MOD);
			}
		}
	}
	add(ans, nn[remain.size()]);
	printf("%d\n", ans);
	return 0;
}
