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 <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

i64 modpow(i64 a, int p = MOD - 2)
{
	if (p == 0) return 1;
	i64 ret = modpow(a, p / 2);
	ret = ret * ret % MOD;
	if (p % 2 == 1) ret = ret * a % MOD;
	return ret;
}

struct segtree
{
	static const int DEPTH = 19;
	static const int N = 1 << DEPTH;

	int val[2 * N];

	void init()
	{
		for (int i = 0; i < 2 * N; ++i) val[i] = 0;
	}

	void incl(int p, int v)
	{
		p += N;
		while (p) {
			val[p] += v;
			p >>= 1;
		}
	}

	int query(int L, int R)
	{
		L += N; R += N;
		int ret = 0;
		while (L < R) {
			if (L & 1) ret += val[L++];
			if (R & 1) ret += val[--R];
			L >>= 1; R >>= 1;
		}
		return ret;
	}
};
int N, P[505050];
vector<int> uus;
bool used[505050];
segtree seg;
i64 invs[505050];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", P + i);
		--P[i];
	}
	invs[0] = 0;
	for (int i = 1; i <= N; ++i) invs[i] = modpow(i);

	i64 mult = 1;
	int uu = 0;

	for (int i = 0; i < N; ++i) {
		if (P[i] >= 0) used[P[i]] = true;
	}
	for (int i = 0; i < N; ++i) if (!used[i]) uus.push_back(i);

	seg.init();

	i64 ret = 0;
	i64 ap = 0;
	i64 waf = uus.size() * (uus.size() - 1) / 2 % MOD;
	waf = waf * invs[uus.size()] % MOD;
	if (uus.size() > 0) waf = waf * invs[uus.size() - 1] % MOD;

	i64 fuee = 1;
	int pohe = 0;
	for (int i = 0; i < N; ++i) {
		if (P[i] == -1) {
			++pohe;
			fuee = fuee * pohe % MOD;
		}
	}

	i64 m2 = 1;
	for (int i = N - 1; i >= 0; --i) {
		if (P[i] == -1) {
		//	ADD(ret, ap);
			ADD(ret, (waf * uu % MOD + ap * invs[uus.size()]) % MOD * m2 % MOD * fuee % MOD);
///			printf("%lld\n", (waf * uu + ap * invs[uus.size()]) % MOD * m2 % MOD * fuee % MOD);
//			printf("%lld %lld\n", uu, ap);
			++uu;
			mult = mult * uu % MOD;
		} else {
			int lt = lower_bound(uus.begin(), uus.end(), P[i]) - uus.begin();
			int gt = uus.size() - lt;
	//		int gt = (uus.size() - (lower_bound(uus.begin(), uus.end(), P[i]) - uus.begin()));
//			int lt = uus.size() - lt;
//			printf("%d %d\n", lt, gt);
			ADD(ap, gt);
			ADD(ret, (seg.query(0, P[i]) + lt * invs[uus.size()] % MOD * uu) % MOD * m2 % MOD * fuee);
			seg.incl(P[i], 1);
		}
		m2 *= N - i;
		m2 %= MOD;
	}
//	printf("%lld\n", mult);

	ADD(ret, mult);
//	ADD(ret, 1);
	//ret = ret * mult % MOD;

	printf("%lld\n", ret);

	return 0;
}
