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;

static const int kModulo = 1000 * 1000 * 1000 + 7;

class FenwickTree {
  public:
    FenwickTree(int size):
        m_size(size), m_data(size + 1) {}

    void add(int x, int y) {
        for (; x <= m_size; x += (x & -x))
            m_data[x] += y;
    }

    int query(int x) {
        int sum = 0;
        for (; x > 0; x -= (x & -x))
            sum += m_data[x];
        return sum;
    }

  private:
    int m_size;
    vector<int> m_data;
};

int main() {
    ios::sync_with_stdio(false);
    int N; cin >> N;

    vector<int> P(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i];
    vector<int> many(N, 0);
    vector<bool> exists(N, false);
    FenwickTree T(N);
    for (int i = N - 1; i >= 0; --i) {
        if (P[i] == 0)
            ++many[i];
        else {
            exists[P[i] - 1] = true;
            T.add(P[i], 1);
        }
        if (i + 1 < N)
            many[i] += many[i + 1];
    }

    vector<int> lower(N, 0), higher(N, 0);
    for (int i = 0; i < N; ++i) {
        if (!exists[i])
            ++lower[i];
        if (i > 0)
            lower[i] += lower[i - 1];
    }
    for (int i = N - 1; i >= 0; --i) {
        if (!exists[i])
            ++higher[i];
        if (i < N - 1)
            higher[i] += higher[i + 1];
    }

    int totalPairs = 0;
    for (int i = 0; i < N; ++i)
        if (exists[i]) {
            totalPairs = (totalPairs + higher[i]) % kModulo;
        }

    vector<int> fact(N + 1, 0);
    fact[0] = fact[1] = 1;
    for (int i = 2; i <= N; ++i)
        fact[i] = 1LL * fact[i - 1] * i % kModulo;

    int answer = fact[many[0]];

    for (int i = 0; i < N; ++i)
        if (P[i] == 0) {
            int to_the_right = many[i] - 1;
            if (to_the_right > 0) {
                int aux = (1LL * many[0] * (many[0] - 1) / 2) % kModulo; // pick this value and one to the right
                aux = (1LL * aux * to_the_right) % kModulo; // which one of them
                aux = (1LL * aux * fact[many[0] - 2]) % kModulo; // all the others
                aux = (1LL * aux * fact[N - i - 1]) % kModulo; // how much we add
                answer = (answer + aux) % kModulo;
            }
            int aux = (1LL * totalPairs * fact[many[0] - 1]) % kModulo;
            aux = (1LL * aux * fact[N - i - 1]) % kModulo;
            answer = (answer + aux) % kModulo;
        } else {
            int to_the_right = many[i];
            if (to_the_right > 0) {
                int aux = (1LL * lower[P[i] - 1]) % kModulo; // pick the value to the right
                aux = (1LL * aux * to_the_right) % kModulo; // which one of them
                aux = (1LL * aux * fact[many[0] - 1]) % kModulo; // all the others
                aux = (1LL * aux * fact[N - i - 1]) % kModulo; // how much we add
                answer = (answer + aux) % kModulo;
            }

            int aux = T.query(P[i] - 1);
            aux = (1LL * aux * fact[many[0]]) % kModulo;
            aux = (1LL * aux * fact[N - i - 1]) % kModulo;
            answer = (answer + aux) % kModulo;
            totalPairs -= higher[P[i] - 1];
            if (totalPairs < 0)
                totalPairs += kModulo;
            T.add(P[i], -1);
        }

    cout << answer << "\n";
}
