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>
using namespace std;
namespace fdata
{
inline char nextchar()
{
    static const int BS = 1 << 21;
    static char buf[BS], *st, *ed;
    if (st == ed)
        ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? -1 : *st++;
}
#ifdef lky233
#define nextchar getchar
#endif
template <typename Y>
inline void poread(Y &ret)
{
    ret = 0;
    char ch;
    while (!isdigit(ch = nextchar()))
        ;
    do
        ret = ret * 10 + ch - '0';
    while (isdigit(ch = nextchar()));
}
#undef nextcar
} // namespace fdata
using fdata::poread;
#define int long long
const int MAXN =  5e5 + 10;
const int MOD = 1e9 + 7;
inline int qpow(int a, int b)
{
	register int res = 1;
	for(; b; b >>= 1)
	{
		if(b & 1)
			res = (long long)res * a % MOD;
		a =  (long long)a * a % MOD;	
	}	
	return res;
}
int n;
int a[MAXN];
bool vis[MAXN];
int fac[MAXN], inv_fac[MAXN];
int s[MAXN], ans[MAXN];

inline int C(int n, int m)
{
	if(n < m)
		return 0;
	return (long long) fac[n] * inv_fac[n - m] % MOD * inv_fac[m] % MOD;
}

int tree[MAXN];
inline void add(int x, int d)
{
	for(; x <= n; x += (x & -x))
		tree[x] = (tree[x] + d) % MOD;
}
inline int ask(int x)
{
	register int res = 0;
	for(; x; x -= (x & -x))
		res = (res + tree[x]) % MOD;
	return res;
}

signed main()
{
#ifdef lky233
	freopen("testdata.in",  "r", stdin);
	freopen("testdata.out", "w", stdout);
#endif
	poread(n);
	for(register int i = 1; i <= n; ++i)
		poread(a[i]);
	fac[0] = fac[1] = 1;
	for(register int i = 2; i <= n; ++i)
		fac[i] = (long long)fac[i - 1] * i % MOD;
	inv_fac[n] = qpow(fac[n], MOD - 2);
	for(register int i = n - 1; i >= 0; --i)
		inv_fac[i] = (long long)inv_fac[i + 1] * (i + 1) % MOD;
	register int k = 0, sum = 0;
	for(register int i = 1; i <= n; ++i)
		a[i] ? vis[a[i]] = 1 : ++k;
	for(register int i = n; i >= 1; --i)
	{
		s[i] += s[i + 1];
		if(!vis[i])
		{
			++s[i];
			sum = (sum + i - 1) % MOD;
		}
	}
	register int pre = 0, rem = 0;
	for(register int i = 1; i <= n; ++i)
	{
		if(!a[i])
		{
			ans[i] = (ans[i] + MOD - pre) % MOD;
			if(k >= 2)
				ans[i] = (ans[i] + MOD - (long long)rem * C(k,2) % MOD * fac[k - 2] % MOD) % MOD;
			ans[i] = (ans[i] + sum * fac[k - 1] % MOD) % MOD;
			++rem;
		}
		else
		{
			ans[i] = (ans[i] + (long long)(a[i] - 1) * fac[k] % MOD) % MOD;
			ans[i] = (ans[i] + MOD - (long long)ask(a[i] - 1) * fac[k] % MOD) % MOD;
			if(k) ans[i] = (ans[i] + MOD - (long long)rem * (s[1] - s[a[i]]) % MOD * fac[k - 1] % MOD) % MOD;
			if(k) pre = (pre + (long long)s[a[i] + 1] * fac[k - 1] % MOD) % MOD;
			add(a[i], 1);
		}
	}
	register int res = fac[k];
	for(register int i = 1; i <= n; ++i)
		res = (res + fac[n - i] * ans[i] % MOD) % MOD;
	cerr << res << endl;
	printf("%lld\n", res);
	return 0;
	
}
