19666번 - Cryptography 다국어

Charles the Cryptographer has been researching novel methods of generating random numbers. In particular, by combining multiple sources of random numbers, he hopes to create a cryptographically secure pseudorandom number generator (CSPRNG).

One algorithm that he has recently invented is as follows:

1. Randomly generate a sequence S of N distinct positive integers S₁, . . . , S_N
2. Randomly shuffle S to obtain a permutation¹ P of N elements P₁, . . . , P_N
3. Find the lexicographical order of P
4. As the answer can be very large, output the value modulo² 1 000 000 007

The lexicographical order of P is defined as the number of permutations of S that are lexicographically smaller than³ or equal to P.

Unfortunately, Charles is a Cryptographer and not a Coder. Given the resultant permutation P, help Charles to find its lexicographical order, modulo 1 000 000 007.

¹A permutation P of a sequence S is a rearrangement of the elements of S

²The remainder when the value is divided by 1 000 000 007

³A permutation P₁, . . . , P_N is considered lexicographically smaller than another permutation P'₁ , . . . , P'_N if there exists 1 ≤ k ≤ N such that P_k < P'_k and P_i = P'_i for i = 1, . . . , k − 1.

Your program must read from standard input.

The first line contains a single integer N.

The second line contains N space-separated integers, P₁, . . . , P_N.

Your program must print to standard output. The output should contain a single integer on a single line, the lexicographical order of P, modulo 1 000 000 007.

• 1 ≤ N ≤ 3 × 10⁵
• 1 ≤ P_i ≤ 10⁹
• P_i ≠ P_j for i ≠ j