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>

const long long mod=1000000007ll;
const int BS=19;

void bitadd(int *bit,int i,int v)
{
  int p=i+1;
  while(p<1<<BS){
    bit[p]+=v;
    p+=p&-p;
  }
}

int bitsum(int *bit,int i)
{
  int p=i+1,ret=0;
  while(p>0){
    ret+=bit[p];
    p-=p&-p;
  }
  return ret;
}


int main()
{
  int n;
  scanf("%d",&n);
  static int P[500010];
  static bool B[500010]={0};
  int L=0;
  for(int i=0;i<n;i++){
    scanf("%d",P+i);
    if(P[i]==0){
      L++;
    }
    else{
      B[P[i]]=1;
    }
  }
  static int A[500010];
  A[n]=0;
  for(int i=n-1;i>0;i--){
    A[i]=A[i+1]+!B[i+1];
  }
  static int A2[500010];
  A2[1]=0;
  for(int i=2;i<=n;i++){
    A2[i]=A2[i-1]+B[i-1];
  }
  static long long F[500010];
  F[0]=1ll;
  for(int i=1;i<=n;i++){
    F[i]=F[i-1]*i%mod;
  }
  static int bit[1<<19]={0};
  long long ans=0ll;
  long long S0=0ll,S1=0ll;
  for(int i=1;i<=n;i++){
    if(!B[i]){
      S0+=A[i];
    }
    else{
      S1+=A[i];
    }
  }
  int K=0;
  for(int i=0;i<n;i++){
    //printf("%lld %lld\n",S0,S1);
    if(P[i]==0){
      ans+=S0%mod*(L-K-1)%mod*(L>=2?F[L-2]:0ll)%mod*F[n-i-1]%mod;
      ans%=mod;
      ans+=S1%mod*F[L-1]%mod*F[n-i-1]%mod;
      ans%=mod;
      K++;
    }
    else{
      int k=bitsum(bit,P[i]-1);
      ans+=(long long)(A2[P[i]]-k)*F[L]%mod*F[n-i-1]%mod;
      ans%=mod;
      ans+=(long long)(P[i]-1-A2[P[i]])*(L-K)%mod*(L>=1?F[L-1]:0)%mod*F[n-i-1]%mod;
      ans%=mod;
      S1-=A[P[i]];
      bitadd(bit,P[i],1);
    }
    //printf("%lld\n",ans);
  }
  ans+=F[L];
  ans%=mod;
  printf("%lld\n",ans);
  return 0;
}
