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<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

ll kaijou[500010];
void init(){
	kaijou[0] = 1;
	rep1(i,500009){
		kaijou[i] = kaijou[i-1] * i;
		kaijou[i] %= M;
	}
}

struct BIT{
	int siz;
	int s[1<<20+1];
	void init(){
		siz = 1<<20;
		rep1(i,siz)s[i] = 0;
	}
	void add(int a){
		while(a <= siz){
			s[a] ++;
			a += a&-a;
		}
	}
	int sum(int a){
		int ret = 0;
		while(a > 0){
			ret += s[a];
			a -= a&-a;
		}
		return ret;
	}
}bit;

int main(){
	init();
	bit.init();
	static int n;
	static int p[500010];
	scanf("%d",&n);
	rep(i,n)scanf("%d",&p[i]);
	
	static int K[500010] = {} , cnt[500010] = {};
	rep1(i,n)cnt[i] = 1;
	rep(i,n){
		K[i] = K[i-1];
		if(p[i] == 0){
			K[i] ++;
		}
		else {
			cnt[p[i]] = 0;
		}
	}
	K[n] = K[n-1];
	rep1(i,500009)cnt[i] += cnt[i-1];
	
	ll c=0,d=0,hoge = 0;
	rep1(i,n){
		if(cnt[i] > cnt[i-1]){
			c += i-1;
			d += cnt[i-1];
		}
	}
	c *= K[n]-1;
	c %= M;
	d %= M;
	
	ll ret = 0;
	rep(i,n){
		if(p[i] != 0){
			ll _ret = 0;
			_ret = kaijou[K[n]]*(p[i]-1-bit.sum(p[i])); _ret %= M;
			_ret += M-( (kaijou[K[n]-1]*K[i])%M*cnt[p[i]] )%M;
			_ret *= kaijou[n-i-1]; _ret %= M;
			ret += _ret; ret %= M;
			bit.add(p[i]);
			hoge += K[n]-cnt[p[i]];
			hoge %= M;
		}
		else {
			ll _ret = c;
			_ret +=M-( (K[n]-1)*hoge )%M;
			_ret +=M-( d*((i==0)?0:K[i-1]) )%M;
			_ret *= kaijou[n-i-1]; _ret %= M;
			_ret *= (K[n] < 2)?0:kaijou[K[n]-2];
			_ret %= M;
			ret += _ret;
			ret %= M;
		}
		/*else {
			ll _ret = 0;
			rep1(j,n){
				if(cnt[j] == cnt[j-1])continue;
				//cout << "__" << i << " " << j << endl;
				ll __ret = 0;
				__ret = kaijou[K[n]-1]*(j-1-bit.sum(j)); __ret %= M;
				//cout << __ret << endl;
				__ret += M-( (kaijou[K[n]-2]*((i==0)?0:K[i-1]))%M*cnt[j-1] )%M;
				//cout << __ret << endl;
				__ret *= kaijou[n-i-1]; __ret %= M;
				//cout << __ret << endl;
				_ret += __ret;
			}
			ret += _ret; ret %= M;
		}*/
		//cout << i << " " << ret << endl;
	}
	
	cout << (ret+kaijou[K[n]])%M << endl;
}
