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 <iostream>
#include <vector>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll TEN(int n) { return (n==0)?1:10*TEN(n-1); }
template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    const ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    const ModInt operator-(const ModInt &r) const {return make(normS(v+normS(MD-r.v)));}
    const ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

/**
 * Fenwick Tree 
 *
 * 0-indexed
 */
template<class T>
struct Fenwick {
    int N;
    vector<T> seg;
    Fenwick(int N) : N(N) {
        seg.resize(N+1);
        fill_n(begin(seg), N+1, 0);
    }
    /// i番目の要素にxを追加する
    void add(int i, T x) {
        i++;
        while (i <= N) {
            seg[i] += x;
            i += i & -i;
        }
    }
    /// [0, i)のsum
    T sum(int i) {
        T s{0};
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    }
    /// [a, b)のsum
    T sum(int a, int b) {
        return sum(b) - sum(a);
    }
};

const int MN = 500500;
Mint fact[MN];

void first() {
    fact[0] = 1;
    for (int i = 1; i < MN; i++) {
        fact[i] = fact[i-1]*i;
    }
}

int main() {
    first();
    int n, m = 0;
    cin >> n;
    int a[n];
    Fenwick<int> unfw(n);
    for (int i = 0; i < n; i++) {
        unfw.add(i, 1);
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i]; a[i]--;
        if (a[i] == -1) {
            m++;
        } else {
            unfw.add(a[i], -1);
        }
    }

    Mint ans = 0;
    int unfix = 0;
    Mint unfix_fix = 0;
    Fenwick<int> fw(n);
    for (int i = n-1; i >= 0; i--) {
        int d = a[i];
        Mint res = 0;
        if (d == -1) {
            res += unfix_fix * fact[m-1];
            if (unfix) {
                Mint mc2 = ull(m) * (m-1) / 2;
                res += Mint(unfix) * mc2 * fact[m-2];
            }
            unfix++;
        } else {
            int co = fw.sum(d);
            res += fact[m] * co;
            res += Mint(unfix) * unfw.sum(d) * fact[m-1];
            unfix_fix += unfw.sum(d, n);
            fw.add(d, 1);
        }
        ans += res * fact[n-1-i];
//        cout << res.v << " " << ans.v << endl;
    }
    ans += fact[m];
    cout << ans.v << endl;
    return 0;
}
