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<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(int64_t __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(int64_t(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<1000000007>;

const int MX = 500500;

int N;
int fenw[MX];
int P[MX];
int invP[MX];
int pref[MX];
Mint fact[MX];

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   cin >> N;
   for (int i = 1; i <= N; ++i) {
      cin >> P[i];
      if (P[i]) invP[P[i]] = i;
   }
   fact[0] = 1;
   for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i;
   Mint ans = 1;
   for (int i = 1; i <= N; ++i) pref[i] = pref[i-1] + !invP[i];
   Mint invTot = Mint(pref[N]).inv();
   Mint inv2 = Mint(2).inv();
   int cnt = 0;
   Mint tot = 0;
   /*
   for (int i = 1; i <= N; ++i) {
      for (int j = i+1; j <= N; ++j) {
         Mint prob;
         if (P[i] && P[j]) prob = (P[i] > P[j]);
         if (!P[i] && !P[j]) prob = Mint(2).inv();
         if (!P[i] && P[j]) prob = Mint(pref[N] - pref[P[j] - 1]) / Mint(pref[N]);
         if (P[i] && !P[j]) prob = Mint(pref[P[i]-1]) / Mint(pref[N]);
         ans += prob * fact[N-i];
      }
   }*/
   for (int i = N; i > 0; --i) {
      if (P[i]) {
         ans += fact[N-i] * pref[P[i] - 1] * invTot * cnt;
         for (int p = P[i]; p > 0; p -= p & -p) ans += fact[N-i] * fenw[p];
         for (int p = P[i]; p <= N; p += p & -p) fenw[p]++;
         tot += Mint(pref[N] - pref[P[i] - 1]) * invTot;
      } else {
         ans += inv2 * cnt * fact[N-i];
         ans += tot * fact[N-i];
         ++cnt;
      }
   }
   for (int z = 1; z <= pref[N]; ++z) ans *= z;
   cout << ans << '\n';
   return 0;
}
