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 <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, a[500009], bit[500009], mod = 1000000007; bool used[500009]; vector<long long>A, B;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (long long i = 0; i < 63; i++) {
		if ((b&(1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long a, long long b, long long m) {
	a %= m;
	return (a*modpow(b, m - 2, m)) % m;
}
void Add(long long p, long long x) {
	p++;
	while (p <= 500008) { bit[p] += x; p += (p&-p); }
}
long long Sum(long long p) {
	p++; long long s = 0;
	while (p >= 1) { s += bit[p]; p -= (p&-p); }
	return s;
}

int main() {
	cin >> N;
	for (long long i = 1; i <= N; i++) {
		scanf("%lld", &a[i]); if (a[i] >= 1)used[a[i]] = true;
	}
	for (long long i = 1; i <= N; i++) {
		if (used[i] == true)A.push_back(i);
		if (used[i] == false)B.push_back(i);
	}
	long long fact2 = 1;
	for (long long i = 0; i < B.size(); i++) { fact2 *= (i + 1); fact2 %= mod; }
	long long cnt = 0, fact = 1, ret = 0, sum = 0, cnt2 = 0;
	for (long long i = N; i >= 1; i--) {
		if (a[i] == 0) {
			long long V = sum; V = Div(V, B.size(), mod);
			long long W = cnt2; W = Div(W, 2, mod);
			long long X = V + W; X *= fact2; X %= mod;
			ret += X * fact; ret %= mod; cnt2++;
		}
		else {
			long long pos1 = lower_bound(B.begin(), B.end(), a[i]) - B.begin();
			sum += (B.size() - pos1);
			long long V = Sum(a[i]); Add(a[i], 1);
			long long W = pos1; W = Div(W, B.size(), mod); W *= cnt2; W %= mod;
			long long X = V + W; X *= fact2; X %= mod;
			ret += X*fact; ret %= mod;
		}
		cnt++; fact *= cnt; fact %= mod;
	}
	ret += fact2; ret %= mod;
	cout << ret << endl;
	return 0;
}