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 <stdio.h>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;

vi fen(500001);

void add(int i) {
  for (; i < fen.size(); i |= i+1) {
    fen[i] += 1;
  }
}

int sum(int i) {
  int s = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    s += fen[i];
  return s;
}

vl fac(fen.size(), 1);

int main() {
  for (int i = 2; i < fac.size(); ++i) fac[i] = fac[i-1] * i % mod;
  int n;
  cin >> n;
  vi p(n), was(n+1);
  int k = 0;
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    was[p[i]] = 1;
    if (p[i] == 0) ++k;
  }
  vi up(n + 1), dw(n+1);
  for (int i = n-1; i > 0; --i) {
    up[i] = up[i + 1] + 1 - was[i + 1];
  }
  for (int i = 2; i <= n; ++i) {
    dw[i] = dw[i-1] + 1 - was[i-1];
  }
  ll res = 0, su = 0;
  int e = 0;
  int inv2 = (mod+1)/2;
  for (int i = n-1; i >= 0; --i) {
    if (p[i] == 0) {
      res = (res + fac[n-i-1] * (fac[k] * e % mod * inv2 % mod + fac[k-1] * su % mod)) % mod;
//      cerr << i << ' ' << e << ' ' << su << ' ' << res << endl;
      ++e;
    } else {
      int ls = sum(p[i]);
      res = (res + fac[n-i-1] * (fac[k] * ls % mod + fac[k-1] * e % mod * dw[p[i]] % mod)) % mod;
//      cerr << i << ' ' << ls << ' ' << res << endl;
      add(p[i]);
      su = (su + up[p[i]]) % mod;
    }
  }
  cout << (res + mod + fac[k]) % mod << endl;
  return 0;
}