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;
typedef long long ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll inv[1000000];
ll FactorialInv[1000000];
ll Factorial[1000000];
ll beki(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll ans = beki(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}
void init_combination(){
    inv[1] = 1;
    FactorialInv[1] = 1;
    Factorial[1] = 1;
    for(int i = 2; i < 1000000; i++){
        inv[i] = beki(i, mod - 2);
        Factorial[i] = Factorial[i - 1] * i % mod;
        FactorialInv[i] = FactorialInv[i - 1] * inv[i] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

struct SegmentTree {
private:
    int n;
    vector<ll> node;
 
public:
    SegmentTree() {
        int sz = 500020;
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
        for(int i=0; i<sz; i++) node[i+n-1] = 0;
        for(int i=n-2; i>=0; i--) node[i] = (node[2*i+1] + node[2*i+2]);
    }
 
    void update(int x, ll val) {
        x += (n - 1);
        node[x] = val;
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = (node[2*x+1] + node[2*x+2]);
        }
    }
    // hannkaikukann 
    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        if(r <= a || b <= l) return 0;
        if(a <= l && r <= b) return node[k];
 
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return (vl + vr);
    }
};

int main() {
    //cout.precision(10);
    init_combination();
    ll N, P[500050];
    set<ll> Disappeared;
    cin >> N;
    for(ll i = 1; i <= N; i++) {
        Disappeared.insert(i);
    }
    for(ll i = 1; i <= N; i++) {
        cin >> P[i];
        Disappeared.erase(P[i]);
    }
    vector<ll> disappeared;
    for(auto itr = Disappeared.begin(); itr != Disappeared.end(); itr++) {
        disappeared.push_back(*itr);
    }
    ll num_disappeared = disappeared.size();
    SegmentTree seg;
    if(disappeared.empty()) {
        ll ans = 0;
        for(int index = N; index >= 1; index--) {
            ll under = seg.getsum(1, P[index]);
            ans = (ans + under * Factorial[N - index]) % mod;
            seg.update(P[index], 1);
        }
        cout << (ans + 1) % mod << endl;
        return 0;
    }
    ll ans = 0;
    ll before_question = 0;
    ll inversion_number = 0;
    for(ll index = N; index >= 1; index--) {
        if(P[index] == 0) {
            ll factor = Factorial[N - index];
            ll EXP = before_question * inv[2] % mod;
            EXP = (EXP + inversion_number * inv[num_disappeared]) % mod;
            ans = (ans + factor * EXP) % mod;
            before_question++;
        }
        if(P[index] != 0) {
            ll factor = Factorial[N - index];
            ll EXP = seg.getsum(1, P[index]);
            ll NUMBER = distance(disappeared.begin(), lower_bound(disappeared.begin(), disappeared.end(), P[index]));
            //cout << NUMBER << endl;
            inversion_number = (inversion_number + num_disappeared - NUMBER) % mod;
            NUMBER = (NUMBER * inv[num_disappeared]) % mod;
            NUMBER = (NUMBER * before_question) % mod;
            ans = (ans + factor * (NUMBER + EXP)) % mod;
            seg.update(P[index], 1);
        }
        //cout << index << " " << before_question << " " << inversion_number << " " << ans << endl;
    }
    cout << (ans + 1) * Factorial[num_disappeared] % mod << endl;
    return 0;
}
