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
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

MOD = 10**9 + 7

# 右側に自身より低い数値をいくつ残せているか

N,*A = map(int,read().split())

A_rev = A[::-1]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

right_zero = [0] * (N+1)
for i,x in enumerate(A_rev):
    right_zero[i+1] = right_zero[i] 
    if x == 0:
        right_zero[i+1] += 1

zero_cnt = right_zero[-1]
inv = pow(zero_cnt,MOD-2,MOD)

rest_smaller = [1] * (N+1)
for x in A:
    rest_smaller[x] = 0
rest_smaller = list(itertools.accumulate(rest_smaller))

right_smaller_prob = [(MOD+1)//2] * N
for i,x in enumerate(A_rev):
    if x != 0:
        right_smaller_prob[i] = rest_smaller[x] * inv

right_smaller_filled = [0] * N
bit = BIT(max_n = N)
p = 0
for i,x in enumerate(A_rev):
    if x != 0:
        right_smaller_filled[i] = bit.get_sum(x)
        bit.add(x,1)
        p += zero_cnt-rest_smaller[x]
    else:
        right_smaller_filled[i] = p * inv

fact = [1] * (N+1)
for n in range(1,N+1):
    fact[n] = fact[n-1] * n % MOD

answer = (1+sum(y*(x*p+z) for x,p,y,z in zip(right_zero,right_smaller_prob,fact,right_smaller_filled))) * fact[zero_cnt] % MOD
print(answer)