E. Partial Sortingtime limit per test1.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputConsider a permutation^\dagger p of length 3n. Each time you can do one of the following operations:  Sort the first 2n elements in increasing order.  Sort the last 2n elements in increasing order. 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 (3n)! permutations p of size 3n.Since the answer could be very large, output it modulo a prime M.^\dagger A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).InputThe only line of input contains two numbers n and M (1 \leq n \leq 10^6, 10^8 \leq M \leq 10^9). It is guaranteed that M is a prime number.OutputOutput the answer modulo M.ExamplesInput
1 100009067
Output
9
Input
2 100000357
Output
1689
Input
69 999900997
Output
193862705
NoteIn the first test case, all the permutations are:  [1, 2, 3], which requires 0 operations;  [1, 3, 2], which requires 1 operation;  [2, 1, 3], which requires 1 operation;  [2, 3, 1], which requires 2 operations;  [3, 1, 2], which requires 2 operations;  [3, 2, 1], which requires 3 operations. Therefore, the answer is 0+1+1+2+2+3=9.
1 100009067

9 
['combinatorics', 'math', 'number theory', '*2300']