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 forn(i, n) for (int i = 0; i < int(n); i++)
#define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define x first
#define y second

using namespace std;

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; } 
template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
template<typename X, typename Y> inline ostream& operator<< (ostream& out, const map<X, Y>& a) { return out << vector<pair<X, Y>>(all(a)); }
template<typename T> inline ostream& operator<< (ostream& out, pair<T*, int> a) { return out << vector<T>(a.x, a.x + a.y); }

inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;

#ifdef SU1
#define LOG
#endif

const int N = 500 * 1000 + 5;
int n;
int a[N];

const int MOD = int(1e9) + 7;

bool read() {
	if (!(cin >> n))
		return false;
	forn(i, n) {
		assert(scanf("%d", &a[i]) == 1);
		--a[i];
	}
	return true;
}

int lt[N];
int rt[N];

bool used[N];

int ft[N];
int fact[N];

void incft(int pos, int delta) {
	for (; pos < N; pos |= (pos + 1))
		ft[pos] += delta;
}

int getft(int pos) {
	int res = 0;
	for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += ft[pos];
	return res;
}

int mul(int a, int b) {
	return int((a * 1ll * b) % MOD);
}

void inc(int &a, int b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}

int cg[N];

void solve() {
	memset(used, 0, sizeof(used));
	memset(ft, 0, sizeof(ft));
	memset(rt, 0, sizeof(rt));
	int fr = 0;
	forn(i, n) {
		if (a[i] == -1) {
			fr++;
			rt[i]++;
		} else
			used[a[i]] = true;
	}
	nfor(i, n - 1) {
		rt[i] += rt[i + 1];
	}
	lt[0] = 0;
	forn(i, n - 1) {
		lt[i + 1] = lt[i];
		if (!used[i])
			lt[i + 1]++;
	}
	
	cg[n - 1] = 0;
	nfor(i, n - 1) {
		cg[i] = cg[i + 1];
		if (!used[i + 1])
			cg[i]++;
	}
	
	fact[0] = 1;
	forn(i, n)
		fact[i + 1] = mul(fact[i], i + 1);
		
	int slt = 0;
	forn(i, n)
		if (!used[i])
			inc(slt, lt[i]);
			
	int ccg = 0;
	
	int res = fact[fr];
	nfor(i, n) {
		if (a[i] != -1) {
			inc(res, mul(mul(rt[i], mul(lt[a[i]], fact[fr - 1])), fact[n - i - 1])); // occ - nocc
			inc(res, mul(getft(a[i]), mul(fact[fr], fact[n - i - 1])));			// occ - occ
			incft(a[i], +1);
			inc(ccg, cg[a[i]]);
		} else {
			inc(res, mul(mul(slt, mul(rt[i] - 1, fact[fr - 2])), fact[n - i - 1])); // nocc - nocc
			inc(res, mul(mul(ccg, fact[fr - 1]), fact[n - i - 1]));	// nocc - occ
			
		}
	}
	
	cout << res << endl;
}

int main() {
#ifdef SU1
    assert(freopen("input.txt", "rt", stdin));
    //assert(freopen("output.txt", "wt", stdout));
#endif
    
    cout << setprecision(10) << fixed;
    cerr << setprecision(5) << fixed;

    while (read()) {
		ld stime = gett();
		solve();
		cerr << "Time: " << gett() - stime << endl;
		//break;
	}
	
    return 0;
}