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
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <list>
#include <numeric>
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<int, ll> i_ll;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define pb push_back
 
int INF = INT_MAX / 10;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int pow_mod(ll x, ll n, int M) {
	ll ans = 1;
	for (; n; n>>=1) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
	}
	return ans;
}

ll inv_mod(int x, int p) {
	return pow_mod(x, p - 2, p);
}

struct bit {
	vector<ll> v;
	bit(int n) : v(n + 1) {}
	ll sum(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	void add(int i, ll x) {
		for (i++; i < v.size(); i += i & -i) v[i] += x;
	}
};

int main() {
	int N; cin >> N;
	vector<int> a(N);
	rep(i, N) {
		scanf("%d", &a[i]);
		a[i]--;
	}
	reverse(a.begin(), a.end());
	bit unko(N), unko2(N);
	rep(i, N) if (a[i] != -1) unko.add(a[i], 1);
	rep(i, N) if (unko.sum(i + 1) - unko.sum(i) == 0) unko2.add(i, 1);
	int kakutei = unko.sum(N), mikakutei = unko2.sum(N);
	int hatena = 0;
	ll hoge = 0, fact = 1, ans = 0;
	bit b(N);
	rep(i, N) {
		int x = a[i];
		ll z = 0;
		if (x == -1) {
			z = (hatena * inv_mod(2, MOD) + hoge) % MOD;
			hatena++;
		}
		else {
			hoge = (hoge + (unko2.sum(N) - unko2.sum(x)) * inv_mod(mikakutei, MOD)) % MOD;
			z = (b.sum(x) + unko2.sum(x) * inv_mod(mikakutei, MOD) % MOD * hatena) % MOD;
			b.add(x, 1);
		}
		ans = (ans + z * fact) % MOD;
		fact = fact * (i + 1) % MOD;
	}
	ans = (ans + 1) % MOD;
	for (int i = 1; i <= mikakutei; i++)
		ans = ans * i % MOD;
	ans = (ans + MOD) % MOD;
	cout << ans << endl;
}
