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;
template<long long mod = 1000000007ll > class umod_t{
private:
    long long number;
public:
    umod_t(): number(0ll){}
    umod_t(long long value){ value %= mod; if(value < 0) value += mod; number = value; }
    umod_t & operator += (umod_t other){ number += other.number; if(number >= mod) number -= mod; return * this; }
    umod_t & operator -= (umod_t other){ number -= other.number; if(number < 0) number += mod; return * this; }
    umod_t & operator *= (umod_t other){ number = number * other.number % mod; return * this; }
    umod_t & operator /= (umod_t other){ return * this *= other.inverse(); }
    umod_t operator + (umod_t other) const { return umod_t(*this) += other; }
    umod_t operator - (umod_t other) const { return umod_t(*this) -= other; }
    umod_t operator * (umod_t other) const { return umod_t(*this) *= other; }
    umod_t operator / (umod_t other) const { return umod_t(*this) /= other; }
    bool operator < (umod_t other) const { return number < other.number; }
    bool operator > (umod_t other) const { return number > other.number; }
    bool operator <= (umod_t other) const { return number <= other.number; }
    bool operator >= (umod_t other) const { return number >= other.number; }
    bool operator == (umod_t other) const { return number == other.number; }
    bool operator != (umod_t other) const { return number != other.number; }
    umod_t inverse() const {
        long long a = number, b = mod, u = 1, v = 0;
        while(b){
            long long t = a/b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if(u < 0)
            u += mod;
        return u;
    }
    long long getNumber(){
        return number;
    }
};
using umod = umod_t<>;
template< typename T > class fenwick_tree{
private:
	static const int default_size = 100100;
	int my_size;
	vector<T> fenwick;
public:
	fenwick_tree(){
		my_size = default_size;
		clear();
	}
	fenwick_tree(int size){
		my_size = size;
		clear();
	}
	void clear(){
		fenwick.assign(my_size, T());
	}
	void add(int pos, T v){
		for(;pos < my_size; pos += pos & - pos)
			fenwick[pos] = fenwick[pos] + v;
	}
	T sum(int pos){
		T ans = T();
		for(;pos; pos -= pos & - pos)
			ans = ans + fenwick[pos];
		return ans;
	}
};
int main(){
	int n; cin >> n;
	vector<int> a(n), seen(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
		if(a[i] >= 0) seen[a[i]] = 1;
	}
	vector<int> missing;
	for(int i = 0; i < n; i++) if(!seen[i]) missing.push_back(i);
	int K = missing.size();
	long long T = 1ll * K * (K - 1) / 2;
	umod sum = 0;
	for(auto e : missing) sum += e;
	vector<umod> fat(n + 1);
	fat[0] = 1;
	for(int i = 1; i <= n; i++) fat[i] = fat[i - 1] * i;
	fenwick_tree<umod> alive(n + 1);
	umod ans = 0, bad = 0;
	int open = 0;
	for(int i = 0; i < n; i++){
		if(a[i] >= 0){
			ans += fat[K] * a[i] * fat[n - i - 1];
		} else {
			ans += fat[K - 1] * sum * fat[n - i - 1];
		}
		if(a[i] >= 0){
			ans -= fat[K] * alive.sum(a[i] + 1) * fat[n - i - 1];
			int smaller = lower_bound(missing.begin(), missing.end(), a[i]) - missing.begin();
			if(missing.size() && open){
				ans -= fat[K - 1] * open * smaller * fat[n - i - 1];
			}
			bad += K - smaller;
			alive.add(a[i] + 1, 1);
		} else {
			open++;
			ans -= fat[K - 1] * bad * fat[n - i - 1];
			if(open >= 2){
				ans -= fat[K - 2] * T * (open - 1) * fat[n - i - 1];
			}
		}
	}	
	ans += fat[K];
	cout << ans.getNumber() << endl;
	return 0;
}
