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
// ※※※ 解答不能 ※※※
// LHiC氏.
// https://atcoder.jp/contests/code-festival-2016-qualc/submissions/1054054
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAXN = 510000;
const LL MOD = 1e9 + 7;
int n, ff[MAXN], p[MAXN];
LL fc[MAXN], fc2[MAXN], pr[MAXN], en[MAXN];

LL get(int x){
    LL ans = 0;
    for(; x >= 0; x = (x & (x + 1)) - 1) ans += ff[x];
    return ans;
}

void add(int x){
    for(; x <= n; x |= (x + 1)) ff[x] += 1;
}

int main(){
    scanf("%d", &n);
    fc[0] = 1;
    repx(i, 1, n + 1) fc[i] = (fc[i - 1] * i) % MOD;
    fc2[0] = 0;
    fc2[1] = 1;
    fc2[2] = 1;
    repx(i, 3, n + 1) fc2[i] = fc2[i - 1] * i % MOD;
    rep(i, n) scanf("%d", p + i), en[p[i]] = 1;
    int cnt = 0;
    repx(i, 1, n + 1) cnt += en[i];
    repx(i, 1, n + 1) pr[i] = pr[i - 1] + (en[i] == 0 ? 1 : 0);
    cnt = n - cnt;
    LL ans = fc[cnt];
    int now = 0;
    LL sum = 0;
    repr(i, n - 1, 0){
        LL x = 0;
        if(p[i] == 0){
            x = fc2[cnt] * now % MOD;
            x = (x + fc[cnt - 1] * sum) % MOD;
            ++now;
        }else{
            x = fc[cnt] * get(p[i]) % MOD;
            if(cnt >= 1) x = (x + now * fc[cnt - 1] % MOD * pr[p[i]]) % MOD;
            add(p[i]);
            sum = sum + (cnt - pr[p[i]]);
            sum %= MOD;
        }
        ans = (ans + x * fc[n - 1 - i]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}