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;

typedef long long ll;
typedef long double ld;

#define get dlafkjsdlfajks

const int M = 500100;
const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int mul(ll x, ll y) {
  return x * y % mod;
}

int fact[M];

void pre() {
  fact[0] = 1;
  for (int i = 1; i < M; ++i) {
    fact[i] = mul(i, fact[i - 1]);
  }
}

int bin(int x, int to) {
  int y = 1;
  while (to) {
    if (to & 1)
      y = mul(x, y);
    x = mul(x, x);
    to >>= 1;
  }
  return y;
}

int inv(int x) {
  //assert(x != 0);
  return bin(x, mod - 2);
}

int f[M];
int n, p[M], sm[M];
bool u[M];

void addf(int at, int what) {
  for (int i = at; i < M; i |= (i + 1))
    f[i] += what;
}

int get(int r) {
  int ans = 0;
  for (int i = r - 1; i >= 0; i = (i & (i + 1)) - 1)
    ans += f[i];
  return ans;
}

int get(int l, int r) {
  return get(r) - get(l);
}

void read() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    --p[i];

    if (p[i] != -1) {
      u[p[i]] = true;
    }
  }
}

void kill() {
  int cnt = 0;
  for (int i = 0; i < n; ++i)
    if (!u[i]) {
      sm[i] = 1;
      ++cnt;
    }

  for (int i = 1; i <= n; ++i)
    sm[i] += sm[i - 1];

  int ans = 0;
  int ma = 0;
  int i2 = (mod + 1) / 2;
  int sum = 0;

  for (int i = n - 1; i >= 0; --i) {
    int bon = 0;

    if (p[i] == -1) {
      bon = add(bon, mul(ma, i2));
      bon = add(bon, mul(sum, inv(cnt)));
      ++ma;
    } else {
      bon = add(bon, mul(mul(ma, sm[p[i]]), inv(cnt)));
      bon = add(bon, get(-1, p[i]));
      addf(p[i], 1);
      sum = add(sum, cnt - sm[p[i]]);
    }

    int rest = n - 1 - i;
    ans = add(ans, mul(bon, fact[rest]));
  }

  ans = add(ans, 1);
  ans = mul(ans, fact[cnt]);
  cout << ans << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  pre();
  read();
  kill();
}
