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 <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct BIT {
  int n;
  vector<int> xs;
  BIT(int n) : n(n), xs(n+1, 0) {}
  void add(int i, int v) {
    for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
  }
  int sum(int i) {
    int s = 0;
    for (int x=i+1; x>0; x-=x&-x) s += xs[x];
    return s;
  }
};
inline int nC2(int x) { return (1LL*x*(x-1)/2) % MOD; }
inline int mul(int x, int y) { return (1LL*x*y) % MOD; }

int N;
int A[500000];
bool used[500000];
int fact[500001];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  fact[0] = 1;
  for (int i=1; i<=500000; i++) fact[i] = (1LL*i*fact[i-1]) % MOD;
  cin >> N;
  BIT bit(N);
  int X = 0, Y = 0;
  rep(i, N) {
    cin >> A[i], A[i]--;
    if (A[i] == -1) X++;
    else used[A[i]] = true;
  }
  vector<int> unused;
  rep(i, N) if (!used[i]) unused.pb(i);
  int s = fact[X], r = 0;
  for (int i=N-1; i>=0; i--) {
    int w = 0;
    if (A[i] == -1) {
      // ? -> ?
      if (X >= 2) w = (w+mul(mul(Y, nC2(X)), fact[X-2])) % MOD;
      // ? -> C
      w = (w + mul(r, fact[X-1])) % MOD;
      Y++;
    }
    else {
      int a = bit.sum(A[i]);
      // C -> C
      w = (w + mul(a, fact[X])) % MOD;
      // C -> ?
      if (X > 0) {
        int c = upper_bound(all(unused), A[i]) - unused.begin();
        r = (r+X-c) % MOD;
        w = (w + mul(mul(c, Y), fact[X-1])) % MOD;
      }
      bit.add(A[i], 1);
    }
    s = (s + 1LL*w*fact[N-1-i]) % MOD;
  }
  cout << s << "\n";
  return 0;
}
