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 <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

const int MAXN = 510000;
const ll MOD = 1e9 + 7;
using namespace std;
int n;
int ff[MAXN];
ll fc[MAXN];
ll fc2[MAXN];
int p[MAXN];
ll pr[MAXN];
ll en[MAXN];

ll get(int x) {
	ll ans = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		ans += ff[x];
	return ans;
}

void add(int x) {
	for (; x <= n; x |= (x + 1))
		ff[x] += 1;
}

int main() {
	scanf("%d", &n);
	fc[0] = 1;
	for (int i = 1; i <= n; ++i)
		fc[i] = (fc[i - 1] * i) % MOD;
	fc2[0] = 0;
	fc2[1] = 1;
	fc2[2] = 1;
	for (int i = 3; i <= n; ++i)
		fc2[i] = fc2[i - 1] * i % MOD;
	for (int i = 0; i < n; ++i)
		scanf("%d", p + i), en[p[i]] = 1;
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		cnt += en[i];
	for (int i = 1; i <= n; ++i)
		pr[i] = pr[i - 1] + (en[i] == 0 ? 1 : 0);
	cnt = n - cnt;
	ll ans = fc[cnt];
	int now = 0;
	ll sum = 0;
	for (int i = n - 1; i >= 0; --i) {
		ll x = 0;
		if (p[i] == 0) {
			x = fc2[cnt] * now % MOD;
			x = (x + fc[cnt - 1] * sum) % MOD;
			++now;
		}
		else {
			x = fc[cnt] * get(p[i]) % MOD;
			if (cnt >= 1)
				x = (x + now * fc[cnt - 1] % MOD * pr[p[i]]) % MOD;
			add(p[i]);
			sum = sum + (cnt - pr[p[i]]);
			sum %= MOD;
		}
		ans = (ans + x * fc[n - 1 - i]) % MOD;
	}
	cout << ans << "\n";
	return 0;
}


