• Please note there's an issue running the repl.it on mobile phones. If interested in playing with the repl.it please do it on a computer

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 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 0s. Can you help her out?

Since the sum can be large, find it modulo 10⁹ + 7.

The first line contains a single integer n.

The next line contains n space-separated integers a₁,a₂,...,aₙ denoting Alice's favorite permutation with some positions replaced by 0.

• 1 ≤ n ≤ 3 * 10⁵
• 0 ≤ aᵢ ≤ n

• For ~33% of the total points, n ≤ 5000

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.

4
0 2 3 0

23

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.

4
4 3 2 1

24

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.

If you'd care to play around with this code please check out the corresponding repl.it. And if you'd care to follow or get in touch here is my HackerRank profile.