Partial Sorting solution codeforces

Partial Sorting solution codeforces – Consider a permutation 𝑝p of length 3𝑛3n. Each time you can do one of the following operations:

  • Sort the first 2𝑛2n elements in increasing order.
  • Sort the last 2𝑛2n elements in increasing order.

Partial Sorting solution codeforces

We can show that every permutation can be made sorted in increasing order using only these operations. Let’s call 𝑓(𝑝)f(p) the minimum number of these operations needed to make the permutation 𝑝p sorted in increasing order.

Given 𝑛n, find the sum of 𝑓(𝑝)f(p) over all (3𝑛)!(3n)! permutations 𝑝p of size 3𝑛3n.

Since the answer could be very large, output it modulo a prime 𝑀M.

 A permutation of length 𝑛n is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

Partial Sorting solution codeforces

The only line of input contains two numbers 𝑛n and 𝑀M (1𝑛1061≤n≤106108𝑀109108≤M≤109). It is guaranteed that 𝑀M is a prime number.

Also read: Lucky Permutation solution codeforces

Output

Output the answer modulo 𝑀M.

Examples
input

Copy
1 100009067

Partial Sorting solution codeforces

Copy
9
input

Copy
2 100000357
output

Copy
1689

Partial Sorting solution codeforces

Copy
69 999900997
output

Copy
193862705

Partial Sorting solution codeforces

In the first test case, all the permutations are:

  • [1,2,3][1,2,3], which requires 00 operations;
  • [1,3,2][1,3,2], which requires 11 operation;
  • [2,1,3][2,1,3], which requires 11 operation;
  • [2,3,1][2,3,1], which requires 22 operations;
  • [3,1,2][3,1,2], which requires 22 operations;
  • [3,2,1][3,2,1], which requires 33 operations.

Therefore, the answer is 0+1+1+2+2+3=90+1+1+2+2+3=9.

Leave a Reply

Your email address will not be published. Required fields are marked *