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;

int S, n0, s1, mod, ans, N, Q, ap[500009], P[500009], aib[500009], fac[500009];

int mul (int x, int y) {return 1LL * x * y % mod;}
void U (int pos) {while (pos <= N) aib[pos] ++, pos += pos - (pos & (pos - 1));}
int Qry (int pos) {int sum = 0; while (pos) sum += aib[pos], pos &= pos - 1; return sum;}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N), mod = 1e9 + 7, fac[0] = 1;
for (int i=1; i<=N; i++)
    fac[i] = mul (fac[i - 1], i);
long long S2 = 0;
for (int i=1; i<=N; i++)
    scanf ("%d", &P[i]), Q += (P[i] == 0), S2 += P[i], ap[P[i]] ++;
ans = fac[Q], ap[0] = 0, S = (1LL * N * (N + 1) / 2 - S2 - Q) % mod;
for (int i=1; i<=N; i++)
    ap[i] += ap[i - 1];
for (int i=1; i<=N; i++)
{
    if (P[i]) ans += mul (fac[N - i], mul (fac[Q], P[i] - 1));
    else ans += mul (fac[N - i], mul (fac[Q - 1], S));
    if (ans >= mod) ans -= mod;
}
int coef00 = 0;
if (Q >= 2) coef00 = mul ((1LL * Q * (Q - 1) / 2) % mod, fac[Q - 2]);
for (int i=1; i<=N; i++)
{
    int ways = 0;
    if (P[i] != 0)
        ways = mul (Qry (P[i]), fac[Q]) + mul (n0, mul (P[i] - ap[P[i]], fac[Q - 1]));
    else
        ways = s1 + mul (n0, coef00);
    if (ways >= mod) ways -= mod;
    ans -= mul (ways, fac[N - i]);
    if (ans < 0) ans += mod;
    if (P[i] != 0)
    {
        U (P[i]), s1 += mul (Q - (P[i] - ap[P[i]]), fac[Q - 1]);
        if (s1 >= mod) s1 -= mod;
    }
    else n0 ++;
}
printf ("%d\n", ans);
return 0;
}
