Alice was given the $n$ integers from $1$ to $n$. She wrote all possible permutations in increasing lexicographical order, and wrote each permutation in a new line. For example, for $n=3$, there are $\boldsymbol{6}$ possible permutations:

$[1,2,3]$
$[1,3,2]$
$[2,1,3]$
$[2,3,1]$
$[3,1,2]$
$[3,2,1]$

She then chose one permutation among them as her favorite permutation.

After some time, she forgot some elements of her favorite permutation. Nevertheless, she still tried to write down its elements. She wrote a $0$ in every position where she forgot the true value.

She wants to know the sum of the line numbers of the permutations which could possibly be her favorite permutation, i.e., permutations which can be obtained by replacing the $0$s. Can you help her out? 

Since the sum can be large, find it modulo $10^9+7$.

Input Format

The first line contains a single integer $n$.

The next line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ denoting Alice's favorite permutation with some positions replaced by $0$.  

Constraints

$1\leq n\leq3\cdot10^5$
$0\leq a_i\leq n$
The positive values appearing in $[a_1,\ldots,a_n]$ are distinct.

Subtask  

For ~33% of the total points, $n\leq5000$  

Output Format

Print a single line containing a single integer denoting the sum of the line numbers of the permutations which could possibly be Alice's favorite permutation.

Sample Input 0
4
0 2 3 0

Sample Output 0
23

Explanation 0

The possible permutations are $[1,2,3,4]$ and $[4,2,3,1]$. The permutation $[1,2,3,4]$ occurs on line $1$ and the permutation $[4,2,3,1]$ occurs on line $22$. Therefore the sum is $1+22=23$.

Sample Input 1
4
4 3 2 1

Sample Output 1
24

Explanation 1

There is no missing number in the permutation. Therefore, the only possible permutation is $[4,3,2,1]$, and it occurs on line $24$. Therefore the sum is $24$.

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


n = int(input())
x = list(map(int, input().split()))

class fenwick:

	def __init__(self, n):
		self.tree = [0] * (n + 1)

	def update(self, i):
		i += 1
		while i < len(self.tree):
			self.tree[i] += 1
			i += i & -i

	def query(self, i):
		sum = 0
		i += 1
		while i > 0:
			sum += self.tree[i]
			i -= i & -i
		return sum

def solve(x):
	n = len(x)
	mod = 1000000007
	missing = [True] * n
	bit1 = fenwick(n)
	bit2 = fenwick(n)
	for i in range(n):
		x[i] -= 1
		if x[i] != -1:
			missing[x[i]] = False
	missisng_elems = []
	for i in range(n):
		if missing[i]:
			missisng_elems.append(i)
	missing_sum = 0
	m = len(missisng_elems)
	for i in missisng_elems:
		missing_sum += i
		if i < n - 1:
			bit2.update(i + 1)
	fact = [1] * 500010
	for i in range(1, 500010):
		fact[i] = i * fact[i - 1] % mod
	total_cost = 0
	p = 0
	y = 0
	for i in range(n - 1):
		if x[i] != -1:
			if m == 0:
				D1 = bit1.query(x[i])
				bit1.update(x[i] + 1)
				cost = (x[i] - D1) * fact[n - i - 1]
			else:
				D1 = bit1.query(x[i]) * m
				no_of_smaller_missing_elems = bit2.query(x[i])
				D2 = no_of_smaller_missing_elems * p
				bit1.update(x[i] + 1)
				cost = (x[i] * m - (D1 + D2)) * fact[m - 1] * fact[n - i - 1]
				y += m - no_of_smaller_missing_elems
		else:
			if p == 0:
				cost = (missing_sum - y) * fact[m - 1] * fact[n - i - 1]
			else:
				D1 = p * m * (m - 1) // 2
				D2 = y * (m - 1)
				cost = (missing_sum * (m - 1) - (D1 + D2)) * fact[m - 2] * fact[n - i - 1]
			p += 1
		total_cost += cost % mod
	return (total_cost + fact[m]) % mod
print(solve(x))


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)


class fenwick:

	def __init__(self, n):
		self.tree = [0] * (n + 1)

	def update(self, i):
		i += 1
		while i < len(self.tree):
			self.tree[i] += 1
			i += i & -i

	def query(self, i):
		sum = 0
		i += 1
		while i > 0:
			sum += self.tree[i]
			i -= i & -i
		return sum

def solve(x):
	n = len(x)
	mod = 1000000007
	missing = [True] * n
	bit1 = fenwick(n)
	bit2 = fenwick(n)
	for i in range(n):
		x[i] -= 1
		if x[i] != -1:
			missing[x[i]] = False
	missisng_elems = []
	for i in range(n):
		if missing[i]:
			missisng_elems.append(i)
	missing_sum = 0
	m = len(missisng_elems)
	for i in missisng_elems:
		missing_sum += i
		if i < n - 1:
			bit2.update(i + 1)
	fact = [1] * 500010
	for i in range(1, 500010):
		fact[i] = i * fact[i - 1] % mod
	total_cost = 0
	p = 0
	y = 0
	for i in range(n - 1):
		if x[i] != -1:
			if m == 0:
				D1 = bit1.query(x[i])
				bit1.update(x[i] + 1)
				cost = (x[i] - D1) * fact[n - i - 1]
			else:
				D1 = bit1.query(x[i]) * m
				no_of_smaller_missing_elems = bit2.query(x[i])
				D2 = no_of_smaller_missing_elems * p
				bit1.update(x[i] + 1)
				cost = (x[i] * m - (D1 + D2)) * fact[m - 1] * fact[n - i - 1]
				y += m - no_of_smaller_missing_elems
		else:
			if p == 0:
				cost = (missing_sum - y) * fact[m - 1] * fact[n - i - 1]
			else:
				D1 = p * m * (m - 1) // 2
				D2 = y * (m - 1)
				cost = (missing_sum * (m - 1) - (D1 + D2)) * fact[m - 2] * fact[n - i - 1]
			p += 1
		total_cost += cost % mod
	return (total_cost + fact[m]) % mod
a = input()
a = list(map(int, input().split()))
print(solve(a))


from bisect import bisect_right, bisect_left
MOD = 10 ** 9 + 7
N = 3 * 10 ** 5

class SegmentTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [0] * (2 * self.size)
		self.build(arr)

	def build(self, arr):
		for i in range(n):
			self.tree[i + n] = arr[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def query(self, l, r):
		if l > r:
			return 0
		l += self.size
		r += self.size
		s = 0
		while l <= r:
			if l % 2 == 1:
				s += self.tree[l]
				l += 1
			if r % 2 == 0:
				s += self.tree[r]
				r -= 1
			l >>= 1
			r >>= 1
		return s

	def update(self, i, x):
		i += n
		self.tree[i] = x
		while i > 1:
			self.tree[i >> 1] = self.tree[i] + self.tree[i ^ 1]
			i >>= 1

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * inv_fac[k] * inv_fac[n - k] % MOD

def factorial(n):
	if n < 0:
		return 0
	return fac[n]

def my_bisect(a, x):
	return bisect_left(a, x)
fac = [1] * (N + 1)
inv_fac = [1] * (N + 1)
for i in range(1, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv_fac[i] = inv_fac[i - 1] * pow(i, MOD - 2, MOD) % MOD
n = int(input().strip())
p = list(map(int, input().strip().split()))
S = set(range(n))
for i in range(n):
	p[i] -= 1
	if p[i] != -1:
		S.remove(p[i])
sum_S = sum(S)
m = len(S)
S = sorted(S)
ans = fac[m]
c = 0
T = 0
H = SegmentTree([0] * n)
for k in range(n):
	if p[k] == -1:
		A = factorial(n - 1 - k) * factorial(c) * factorial(m - 1 - c) % MOD
		B = (binomial(m - 1, c) * (sum_S - T) - binomial(m - 2, c - 1) * m * (m - 1) // 2) % MOD
		ans = (ans + A * B) % MOD
		c += 1
	else:
		A = fac[n - 1 - k] * factorial(c) * factorial(m - c) % MOD
		B = ((p[k] - H.query(0, p[k] - 1)) * binomial(m, c) - my_bisect(S, p[k]) * binomial(m - 1, c - 1)) % MOD
		ans = (ans + A * B) % MOD
		H.update(p[k], 1)
		j = bisect_right(S, p[k])
		T += m - j
print(ans)