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<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)n; ++i)

int fn[500001], fc[500001], x[500001], md = 1e9 + 7, n, mis[500001];
bool p[500001];

inline int gt(int i) { int an = 0; while (i)an += fn[i], i ^= i & -i; return an; }
inline void ad(int i) { while (i <= n)++fn[i], i += i & -i; }

int main(){
	scanf("%d", &n);
	f(i, 1, n + 1)scanf("%d", x + i), p[x[i]] = true;
	int missum = 0, z = 0;
	f(i, 1, n + 1)if (!p[i]){
		mis[z++] = i, missum += i - 1;
		if (missum >= md)missum -= md;
	}
	fc[0] = 1;
	f(i, 1, n + 1)fc[i] = (ll)fc[i - 1] * i % md;
	int an = fc[z], beh = 0, k = 0, zsum = (ll)z * (z - 1) / 2 % md;
	f(i, 1, n + 1){
		if (x[i]){
			int sm = upper_bound(mis, mis + z, x[i]) - mis;
			int t = (ll)gt(x[i]) * fc[z] % md + (ll)sm * beh % md * fc[z - 1] % md;
			an += (ll)fc[n - i] * ((ll)fc[z] * (x[i] - 1) % md - t) % md;
			if (an >= md)an -= md;
			else if (an < 0)an += md;
			k += z - sm;
			if (k >= md)k -= md;
			ad(x[i]);
		}else {
			int t = (ll)fc[z - 1] * k % md + (ll)beh * zsum % md * fc[z - 2] % md;
			an += (ll)fc[n - i] * ((ll)missum * fc[z - 1] % md - t) % md;
			if (an >= md)an -= md;
			else if (an < 0)an += md;
			++beh;
		}
	}
	printf("%d\n", an);
}
