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 <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
# define mp make_pair
# define int ll
const int mod = 1e9 + 7;
int32_t main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    static int p[1 << 20];
    int n;
    IOS;
    fi>>n;
    static int was[1 << 20];
    for (int i = 1;i <= n;++i)
        was[i] = 1;
    for (int i = 1;i <= n;++i)
        fi>>p[i],was[p[i]] = 0;
    static int t[1 << 20];
    static int f[1 << 20];
    f[0] = f[1] = 1;
    for (int i = 2;i <= 1e6 + 5;++i)
        f[i] = (1ll * i * f[i - 1]) % mod;
    auto U = [&](int i)
    {
        for (;i <= n;i += i&(-i))
            t[i] ++;
    };
    auto Q = [&](int i)
    {
        int ans = 0;
        for (;i;i -= i&(-i))
            ans += t[i];
        return ans;
    };
    const int sum = accumulate(was + 1,was + 1 + n,0) % mod;
    int ans = 0;
    int S = 0;
    was[0] = 0;
    for (int i = 1;i <= n;++i)
        if (was[i])
            S += i - 1;
    S %= mod;
    for (int i = 1;i <= n;++i)
        was[i] += was[i - 1];
    static int sums[1 << 20];
    for (int i = 1;i <= n;++i)
        sums[i] = sums[i - 1] + (p[i] == 0);
    int w = 0;
    for (int i = 1;i <= n;++i)
    {
        if (p[i])
        {
            int now = 0;
            ans = (ans + (f[n - i] * (p[i] - 1) % mod) * f[sum]) % mod;
            now = Q(p[i]) * f[n - i] % mod;
            now = now * f[sum] % mod;
            (ans += mod - now) %= mod;
            now = 0;
            now = sums[i] * was[p[i]] % mod;
            now = now * f[sum - 1] % mod;
            now = now * f[n - i] % mod;
            (ans += mod - now) %= mod;
            w += sum - was[p[i]];
            w %= mod;
            U(p[i]);
        }
        else
        {
            ans = (ans + (f[n - i] * S % mod) * f[sum - 1]) % mod;
            int now = w * f[sum - 1] % mod;
            now = now * f[n - i] % mod;
            (ans += mod - now) %= mod;
            if (sum >= 2)
            {
                now = (sum * (sum - 1) / 2) % mod;
                now = (now * sums[i - 1]) % mod;
                now = (now * f[sum - 2]) % mod;
                now = (now * f[n - i]) % mod;
                (ans += mod - now) %= mod;
            }
        }
    }
    (ans += f[sum]) %= mod;
    fo << ans << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}