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;
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long 
int n, m; 
int tree[MAXN];
inline void add(int x, int d)
{
	for(; x <= n; x += (x & -x))
		tree[x] += d;
}
inline int ask(int x)
{
	register int res = 0;
	for(; x; x -= (x & -x))
		res += tree[x];
	return res;
}
int a[MAXN];
int s[MAXN], suf[MAXN];
int fac[MAXN];
signed main()
{
	poread(n);
	fac[0] = 1;
	for(register int i = 1; i <= n; ++i)
		fac[i] = (long long)fac[i - 1] * i % MOD;
	int m = n;
	for(register int i = 1; i <= n; ++i)
	{
		poread(a[i]);
		if(a[i])
			++s[a[i]], --m;
	}
	for(register int i = 1; i <= n; ++i)
		suf[i] = s[i] = 1 - s[i], s[i] += s[i - 1];
	for(register int i = n; i >= 1; --i)
		suf[i] += suf[i + 1];
	register int sum = 0, cnt = 0;
	register int res = 0;
	for(register int i = n; i >= 1; --i)
	{
		if(a[i])
		{
			sum = (long long)ask(a[i] - 1) * fac[m] % MOD;
			if(cnt)
				sum = (sum + (long long)cnt * s[a[i]] % MOD * fac[m - 1] % MOD) % MOD;
			res = (res + (long long)sum * fac[n - i] % MOD) % MOD;
			add(a[i], 1);
//			cerr << sum << endl;
		}
		else
		{
			++cnt;
		}
//		cerr << "*" << res << endl;
	}
	cnt = sum = 0;
	for(register int i = 1; i <= n; ++i)
	{
		if(a[i])
		{
			if(cnt)
				res = (res + (long long)sum * suf[a[i]] % MOD * fac[m - 1] % MOD) % MOD;
		}
		else
		{
			sum = (sum + fac[n - i]) % MOD;
			++cnt;
		}
//		cerr << "*" << res << endl;
	}
	sum =  (long long)(m * (m - 1) >> 1 ) % MOD, cnt = 0;
//	cerr << sum << " " << m <<  endl;
	if(m >= 2)	
		for(register int i = 1; i <= n; ++i)
		{
			if(!a[i])
			{
				++cnt;
				res = (res + (long long)sum * (m - cnt) % MOD * fac[m - 2] % MOD * fac[n - i] % MOD);
//				cerr << sum << " " << m - cnt << " " << fac[m - 2] << " " << fac[n - i] << endl;
			}
//			cerr << "#" << res << endl;
		}
	res = (res + fac[m]) % MOD;
	cout << res << endl;
}
