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<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007LL;
VI fc,invfc;
in ncr(in a, in b){
  if(b==0 || b==a)
    return 1;//even if a<0
  if(b<0 || b>a)
    return 0;
  return fc[a]*invfc[b]%mdl*invfc[a-b]%mdl;
}
void inifc(){
  const in mxfc=1001000;
  fc.resize(mxfc);
  invfc.resize(mxfc);
  fc[0]=fc[1]=invfc[0]=invfc[1]=1;
  for(in i=2;i<mxfc;++i){
    fc[i]=fc[i-1]*i%mdl;
    invfc[i]=invfc[mdl%i]*(mdl-mdl/i)%mdl;
  }
  for(in i=2;i<mxfc;++i){
    invfc[i]*=invfc[i-1];
    invfc[i]%=mdl;
  }
}
in n;
VI mar;
VI fr;
in bef(in a){
  return lower_bound(all(fr),a)-fr.begin();
}
struct fenw{
  VI fw;
  in n;
  void ini(in pn){
    n=pn;
    fw.clear();
    fw.resize(n,0);
  }
  void ad(in l, in x){
    while(l<n){
      fw[l]+=x;
      l|=(l+1);
    }
  }
  in sm(in l){
    in r=0;
    while(l>=0){
      r+=fw[l];
      l&=(l+1);
      --l;
    }
    return r;
  }
};
VI rfr;
fenw ff;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  inifc();
  in sm=0;
  cin>>n;
  ff.ini(n+3);
  mar.resize(n);
  forn(i,n)
    cin>>mar[i];
  rfr.resize(n+1,1);
  rfr[0]=0;
  forn(i,n)
    rfr[mar[i]]=0;
  for(in i=1;i<=n;++i){
    if(rfr[i])
      fr.PB(i);
  }
  in ranksum=0;
  forv(i,fr)
    ranksum+=fr[i]-1;
  ranksum%=mdl;
  in cval;
  in crank;
  in usd0=0;
  in pfr=sz(fr)-1;
  if(pfr==-1)
    pfr=0;
  else
    pfr=fc[pfr];
  sm+=fc[sz(fr)];
  in cbef;
  in inv2=(mdl+1)/2;
  forn(i,n){
    if(i==n-1)
      cval=0;
    else
      cval=fc[n-1-i];
    if(mar[i]!=0){
      crank=mar[i]-1-ff.sm(mar[i]);
      sm+=crank*cval%mdl*fc[sz(fr)];
      cbef=bef(mar[i]);
      sm-=cbef*usd0%mdl*pfr%mdl*cval;
      sm%=mdl;
      ff.ad(mar[i],1);
      ranksum-=sz(fr)-cbef;
      ranksum%=mdl;
    }
    else{
      sm+=ranksum*cval%mdl*pfr;
      sm-=fc[sz(fr)]*usd0%mdl*inv2%mdl*cval;
      sm%=mdl;
      ++usd0;
    }
  }
  sm%=mdl;
  if(sm<0)
    sm+=mdl;
  cout<<sm<<endl;
  return 0;
}
