**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≤106, 108≤𝑀≤109108≤M≤109). It is guaranteed that 𝑀M is a prime number.

Also read: Lucky Permutation solution codeforces

Output the answer modulo 𝑀M.

1 100009067

## Partial Sorting solution codeforces

9

2 100000357

1689

## Partial Sorting solution codeforces

69 999900997

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.