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;
/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compile and get accepted.
 *      ____________
 *     /         __ \
 *    /   __    |  | \
 *   /   |__|   |  |  \
 *  (           |__|   )
 *   \                /
 *    \      ___     /
 *     \____________/
 *
 *
 */
const long long mod = 1000000007;

int BIT[500010];

void upd(int ind,int val) {
	while(ind < 500010) {
		BIT[ind] += val;
		ind |= (ind+1);
	}
}

long long get(int ind) {
	long long res = 0;
	while(ind >= 0) {
		res += BIT[ind];
		ind = (ind & (ind+1)) - 1;
	}
	return res;
}

long long fact[500010],inv[500010];

long long pow_mod(long long base,long long power) {
	long long res = 1;
	while(power) {
		if(power&1)
			res = res * base % mod;
		base = base * base % mod;
		power >>= 1;
	}
	return res;
}

void init() {
	fact[0] = fact[1] = inv[0] = inv[1] = 1;
	for(int i = 2;i < 500010;i++) {
		fact[i] = fact[i-1] * i % mod,inv[i] = pow_mod(fact[i],mod-2);
	}
}

inline void suM(long long & res, long long summand) {
	res += summand;
	if(res >= mod)
		res -= mod;
}

bool vis[500010];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	init();

	int N;
	cin>>N;
	vector<long long> P(N);
	vector<long long> toAdd;
	long long res = 0;
	long long unknown = 0,totalUnknown = 0,bigger = 0,with = 0,sumUnknown = 0;
	for(int i = 0;i < N;i++)
		cin>>P[i],totalUnknown += P[i] == 0,vis[P[i]] = true;

	for(int i = 1;i <= N;i++) {
		if(!vis[i]) {
			if(totalUnknown > 1) {
				suM(with,fact[totalUnknown - 2] * toAdd.size() % mod);
			}
			if(totalUnknown) {
				suM(sumUnknown,(i-1) * fact[totalUnknown - 1] % mod);
			}
			toAdd.push_back(i);
		}
	}

	for(int i = 0;i < N;i++) {
		long long cur = 0;
		if(P[i] != 0) {
			suM(cur,fact[totalUnknown] * get(P[i]) % mod);
			if(totalUnknown) {
				cur = (cur + (unknown * fact[totalUnknown - 1] % mod) 
						* (lower_bound(toAdd.begin(),toAdd.end(),P[i]) - toAdd.begin())) % mod;
				suM(bigger,fact[totalUnknown - 1] * (toAdd.end() - upper_bound(toAdd.begin(),toAdd.end(),P[i])) % mod);
			}
			cur = (fact[totalUnknown] * (P[i] - 1ll) + mod - cur)%mod;
			upd(P[i],1);
		}else {
			suM(cur,bigger);
			suM(cur,with * unknown%mod);
			cur = (sumUnknown + mod - cur)%mod;
			unknown++;
		}
		cur = cur * fact[N-i-1] % mod;
//		cerr<<cur<<'\n';
		suM(res,cur);
	}

	suM(res,fact[totalUnknown]);
	cout<<res<<'\n';

	return 0;
}
/**/
