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>
 
#define all(x) (x).begin(), (x).end()
#define li long long
#define itn int
 
using namespace std;
 
inline int nxt(){
	int n;
	scanf("%d", &n);
	return n;
}

const int mod = 1000000007;

const int N = 555555;
long long fact[N];
long long invfact[N];
long long inv[N];

struct Fenwick{
	int n;
	vector<int> a;

	Fenwick(int nn): n(nn) {
		a.resize(n);
	}

	void add(int pos, int x) {
		while (pos < n) {
			a[pos] += x;
			pos = pos | (pos + 1);
		}
	}

	int get(int pos) {
		int res = 0;
		while (pos >= 0) {
			res += a[pos];
			pos = (pos & (pos + 1)) - 1;
		}
		return res;
	}
};

inline long long C(int n, int k) {
	return fact[n] * invfact[k] % mod * invfact[n - k] % mod;
}

long long waycount(int num_places, int num_left, int num_cand, int first) {
	long long res = 0;
	for (int i = 0; i <= num_cand && i <= num_left; i++) {
		res += 1ll * (first - i) * C(num_left, i) % mod * C(num_places - num_left, num_cand - i) % mod *
			   fact[num_left] % mod * fact[num_places - num_left] % mod;
	}
	return res % mod;
}

int main(){

	int n = nxt();
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = nxt();
	}

	inv[1] = 1;
	for (int i = 2; i < N; i++) {
		inv[i] = mod - 1ll * (mod / i) * inv[mod % i] % mod;
	}
	for (int i = 1; i < 100; i++) {
		assert(1ll * i * inv[i] % mod == 1);
	}
	fact[0] = 1;
	invfact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = fact[i - 1] * i % mod;
		invfact[i] = invfact[i - 1] * inv[i] % mod;
	}

	long long ans = 0;
	Fenwick fenv(n + 1);
	Fenwick free_f(n + 1);
	for (int i = 0; i < n; i++) {
		free_f.add(i + 1, 1);
	}
	long long total_sum = 0;
	for (int i = 0; i < n; i++) {
		if (a[i]) {
			free_f.add(a[i], -1);
			total_sum -= a[i];
		}
		total_sum += i + 1;
	}
	int total_free = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			total_free += 1;
		}
	}
	int free_places = 0;
	long long xuita = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			long long tmp = (total_sum % mod * fact[total_free - 1] % mod - fact[total_free] % mod -
					  xuita % mod * fact[total_free - 1] - fact[total_free] % mod * free_places % mod * inv[2] % mod) % mod + mod;
			tmp %= mod;
			ans += tmp * fact[n - i - 1] % mod;
			free_places += 1;
		} else {
			xuita += total_free - free_f.get(a[i]);
			long long tmp = (a[i] - 1 - fenv.get(a[i])) * fact[total_free] % mod - 1ll * free_f.get(a[i]) * free_places % mod * fact[total_free - 1] % mod;
			tmp %= mod;
			tmp += mod;
			ans += tmp * fact[n - 1 - i] % mod;
			fenv.add(a[i], 1);
		}
	}

	cout << (ans + fact[total_free]) % mod << "\n";

	return 0;
}