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>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

template<ll mod>
struct ModInt{
  using M=ModInt;
  ll a;
  M& put(ll v){
    a=(v<mod)?v:v-mod;
    return *this;
  }
  ModInt(ll v=0){put(v%mod+mod);}
  M operator+(M x){return M().put(a+x.a);}
  M operator-(M x){return M().put(a+mod-x.a);}
  M operator*(M x){return M().put(a*x.a%mod);}
  M operator/(M x){return x.inv()*a;}
  M& operator+=(M x){return *this=*this+x;};
  M& operator-=(M x){return *this=*this-x;};
  M& operator*=(M x){return *this=*this*x;};
  M& operator/=(M x){return *this=*this/x;};
  bool operator==(M x){return a==x.a;}
  M pow(ll m) {
    M x=*this,res=1;
    while(m){
      if(m&1)res*=x;
      x*=x;
      m>>=1;
    }
    return res;
  }
  M inv(){return pow(mod-2);}
};
using mint = ModInt<MOD>;

int N;
int P[514514];
int l[514514];
int BIT[514514];
mint t[514514];
mint fact[514514];

void Add(int k, int x) {
  k++;
  while (k < 514514) {
    BIT[k] += x;
    k += k&-k;
  }
}

int Get(int k) {
  ++k;
  int ret = 0;
  while (k > 0) {
    ret += BIT[k];
    k -= k&-k;
  }
  return ret;
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> N;
  reps(i, 1, N+1) {
    cin >> P[i];
  }

  fact[0] = 1; 
  reps(i, 1, N+1) {
    fact[i] = fact[i-1] * i;
  }

  int m = 0;
  set<int> bs;
  reps(i, 1, N+1) {
    if (P[i] != 0) bs.insert(P[i]);
    else m++;
  }

  int rem = 0;
  int prev = -1;
  int cnt = 0;
  mint bsum = 0;
  for (int b : bs) {
    Add(b, 1);
    bsum += mint(b-prev-1) * rem;
    rem++;
    l[b] = b-rem;
    prev = b;
  }
  bsum += mint(N-prev) * rem;

  rreps(i, 1, N+1) {
    t[i] = t[i+1];
    t[i] += (P[i] == 0);
  }
  
  mint mc2 = mint(m)*(m-1)/2;
  mint ans = 0;
  reps(i, 1, N) {
    if (P[i] != 0) {
      ans += fact[N-i] * t[i+1] * fact[m-1] * l[P[i]];
      int idx = Get(P[i]-1);
      ans += fact[N-i] * idx * fact[m];
      bsum -= m-l[P[i]];
      --rem;
      Add(P[i], -1);
    } else {
      if (m >= 2) ans += fact[N-i] * fact[m-2] * t[i+1] * mc2;
      if (m >= 1) ans += fact[N-i] * fact[m-1] * bsum;
    }
    //cout << "bsum=" << bsum.a << endl;
    //cout << i << ": " << ans.a << endl;
  }
  ans += fact[m];
  cout << ans.a << endl;
}
