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
// CODE FESTIVAL 2016 qual C
// E - 順列辞書 / Encyclopedia of Permutations

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_N 500000
#define MOD 1000000007LL
#define MAX_BIT_IDX MAX_N
using namespace std;

typedef long long int ll;


template <typename T>
class BIT {
public:
  T b[MAX_BIT_IDX + 1];
  int n;
private:
public:
  void init(int num);
  T sum(int i);
  void add(int i, T x);
private:
};

template <typename T>
void BIT<T>::init(int num) {
  n = num;
  for (int i = 0; i <= n; i++) {
    b[i] = 0;
  }
  return;
}

template <typename T>
T BIT<T>::sum(int i) {
  T s = 0;

  for (; i > 0; i -= i & -i) {
    s += b[i];
  }
  return s;
}

template <typename T>
void BIT<T>::add(int i, T x) {
  for (; i <= n; i += i & -i) {
    b[i] += x;
  }
  return;
}


int N, K;
int P[MAX_N];
int cnt_less[MAX_N + 1];
ll sum_unused, sum_cnt_more;
ll fac[MAX_N + 1];
BIT<int> bit;
ll ans;

int main() {

  ll t1, t2, cur_k;
  ll inv2 = (MOD + 1) / 2;

  scanf("%d", &N);
  fill(cnt_less, cnt_less + N, 1); cnt_less[0] = 0;
  fac[0] = 1;
  for (int i = 1; i <= N; i++) {
    fac[i] = (fac[i - 1] * i) % MOD;
  }
  bit.init(N);

  sum_unused = (ll)N * (N + 1) / 2 % MOD;
  for (int i = 0; i < N; i++) {
    scanf("%d", &P[i]);
    if (P[i] == 0) {
      K++;
    } else {
      cnt_less[P[i]] = 0;
      sum_unused = (sum_unused - P[i] + MOD) % MOD;
    }
  }
  for (int i = 1; i <= N; i++) {
    cnt_less[i] += cnt_less[i - 1];
  }

  cur_k = 0;
  sum_cnt_more = 0;
  ans = 0;
  for (int i = 0; i < N; i++) {
    if (P[i] == 0) {
      t1 = (sum_unused * fac[K - 1] - fac[K] + MOD) % MOD;
      t2 = (sum_cnt_more * fac[K - 1] % MOD + cur_k * fac[K] % MOD * inv2 % MOD) % MOD;
      cur_k++;
    } else {
      t1 = (P[i] - 1) * fac[K] % MOD;
      t2 = ((ll)bit.sum(P[i]) * fac[K] % MOD + cur_k * cnt_less[P[i] - 1] % MOD * fac[max(K - 1, 0)] % MOD) % MOD;
      sum_cnt_more = (sum_cnt_more + K - cnt_less[P[i]]) % MOD;
      bit.add(P[i], 1);
    }
    ans = (ans + (t1 - t2 + MOD) % MOD * fac[N - 1 - i]) % MOD;
  }
  ans = (ans + fac[K]) % MOD;

  printf("%lld\n", ans);

  return 0;

}


