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 <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int mod = 1e9 + 7;

inline int add(int a, int b) {
  return a+b >= mod ? a+b-mod : a+b;
}

inline int sub(int a, int b) {
  return a >= b ? a-b : a-b+mod;
}

inline int mul(int a, int b) {
  return llint(a)*b % mod;
}

const int MAX = 500050;

int f[MAX];
int P[MAX];

int L[MAX];

int sum(int x) {
  int r = 0;
  for (++x; x; x -= x&-x)
    r += L[x];
  return r;
}

void addv(int x, int v) {
  for (++x; x < MAX; x += x&-x)
    L[x] += v;
}

bool ima[MAX];
int ls[MAX];
int G[MAX];

int main(void) {
  int N;
  scanf("%d", &N);
  REP(i, N) scanf("%d", &P[i]);

  f[0] = 1;
  REP(i, N) f[i+1] = mul(f[i], i+1);

  int F = 0;
  REP(i, N) {
    F += P[i] == 0;
    ima[P[i]] = true;
  }

  ls[0] = 0;
  for (int i = 1; i <= N; ++i)
    ls[i] = ls[i-1] + !ima[i];
  
  int ans = f[F];
  int L = 0;

  int gg = 0;
  for (int i = N-1; i >= 0; --i) {
    if (P[i]) {
      gg = add(gg, F -  ls[P[i]]);
    } else {
      G[i] = gg;
    }
  }
  REP(i, N) {
    int total = 0;
    if (P[i]) {
      int FL = P[i]-1 - sum(P[i]) - ls[P[i]];
      total = add(total, mul(FL, f[F]));

      if (F > 0) {
        total = add(total, mul(mul(ls[P[i]], F-L), f[F-1]));
      }
      addv(P[i], 1);
    } else {
      L++;
      if (F > 1) {
        int pairs = ((llint(F) * (F - 1)) / 2) % mod;
        total = add(total, mul(pairs, mul(F-L, f[F-2])));
      }
      total = add(total, mul(G[i], f[F-1]));
    }

    ans = add(ans, mul(total, f[N-i-1]));
  }

  printf("%d\n", ans);
  return 0;
}
