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;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C& _a4, C _b4) { _a4 = min(_a4, _b4); }
template<class C> void maxi(C& _a4, C _b4) { _a4 = max(_a4, _b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream& operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto& vv : V) os << vv << ","; os << "]";
  return os;
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int P = 1e9 + 7;
const int MAX = 1e6;
int dp[MAX];
int n;
int sum(int x){
  int res = 0;
  for(;x; x -= (x&-x)){
    res += dp[x];
  }
  return res;
}
void add(int x){
  for(;x <= n; x += (x & -x))
    dp[x] ++;
}

int p[MAX];
int zerd[MAX];
int md[MAX];
int sil[MAX];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  sil[0] = 1;
  R(i,n){
    sil[i+1] = sil[i] * (i+1) % P;
    cin >> p[i];
  }
  int zer = 0;
  for(int i = n-1;i>=0;i--){
    zerd[i] = zer;
    if(p[i] == 0){
      zer++;
    }else{
      md[i] = sum(p[i]);
      add(p[i]);
    }
  }
  int res = 0;
  int ss = 0;
  R(i,n){
    int pom = 0;
    if(p[i] != 0){
      pom += md[i] * sil[zer] % P;
      int wolne = p[i] - sum(p[i]);
      pom += wolne * sil[zer-1] % P * zerd[i] % P;
      res += ss * (zer - wolne) % P * sil[zer-1] % P;
    }else{
      ss += sil[n-i-1];
      ss %= P;
      pom = sil[zer] * zerd[i]% P * ((P+1) / 2) % P; ;
    }
    debug(pom);
    res += (pom % P * sil[n-i-1]) % P; 
    debug(res);
  }
  debug(res);
  res += sil[zer]; // indeksowanie ??
  cout << res % P << "\n";
}
