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 up(__i,__start,__end) for (int __i = (__start); __i <= (__end); __i++)
#define down(__i, __start,__end) for (int __i = (__start); __i >= (__end); __i--)
#define fi first
#define se second
#define bin(__o) (1 << (__o))
#define bug(x) std::cerr<<"[ "<<(#x)<<":  "<<x<<" ]"<<std::endl
#define bugline std::cerr<<"Passing:  "<<__LINE__<<std::endl
#define bugm(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template<typename T> inline T max(T a, T b) {return a > b ? a : b;}
template<typename T> inline T min(T a, T b) {return a < b ? a : b;}
template<typename T> inline bool cmax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<typename T> inline bool cmin(T &a, T b) {return a > b ? a = b, 1 : 0;}

#define cadd(_x,_y) _x = add(_x, _y)
#define cpop(_x,_y) _x = pop(_x, _y)
#define cmul(_x,_y) _x = mul(_x, _y)

const int mod = 1e9 + 7;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll)a * b % mod;}

int qpow(int a, int b)  {
	int c = 1;
	while (b) {
		if (b & 1) cmul(c, a);	
		b >>= 1; cmul(a, a);
	}
	return c;
}

const int maxn = 5e5 + 5;

int n, a[maxn], fac[maxn];

int c[maxn];

inline int lowbit(int i) { return i & (-i); }

void cg(int o, int v) {
	for (int i = o; i <= n; i += lowbit(i))
		c[i] += v;
}

int get(int o) {
	int sum = 0;
	for (int i = o; i >= 1; i -= lowbit(i))
		sum += c[i];
	return sum;
}

int c2(int m) {
	return (ll)m * (m - 1) / 2 % mod;
}

int suf[maxn], pre[maxn];

int main() {
	
	scanf("%d", &n);	
	up (i, 1, n) scanf("%d", &a[i]);
	fac[0] = 1;
	up (i, 1, n) fac[i] = mul(i, fac[i - 1]);
	int ans = 0, cur = 0, all = 0, cof = 0, bs = 0;
	up (i, 1, n) all += a[i] == 0, cadd(bs, i - 1), pre[i] = 1, suf[i] = 1;
	up (i, 1, n) if (a[i] != 0) cpop(bs, a[i] - 1);
	up (i, 1, n) if (a[i] > 0) suf[a[i]] = 0, pre[a[i]] = 0;
	down (i, n, 1) suf[i] += suf[i + 1];
	up (i, 1, n) pre[i] += pre[i - 1];
	up (i, 1, n) {
		int sum = 0;
		cur += a[i] == 0;
		if (a[i] != 0) {
			cadd(sum, mul(fac[all], a[i] - 1));
			int w = get(a[i] - 1);
			cpop(sum, mul(fac[all], w));
			if (all > 0) cpop(sum, mul(pre[a[i]], mul(cur, fac[all - 1])));
			cadd(cof, suf[a[i]]);
			cg(a[i], 1);
		} else {
			if (all > 0) cadd(sum, mul(bs, fac[all - 1]));
			if (cur >= 2) cpop(sum, mul(c2(all), mul(cur - 1, fac[all - 2])));
			if (all > 0) cpop(sum, mul(cof, fac[all - 1]));
		}
		cadd(ans, mul(sum, fac[n - i]));
	}
	printf("%d\n", add(ans, fac[all]));
	
	return 0;

}