Consider a permutation^ p of length 3n. Each time you can do one of the following operations:
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.
^ 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).
Input
The only line of input contains two numbers n and M (1 ≤ n ≤ 10^6, 10^8 ≤ M ≤ 10^9). It is guaranteed that M is a prime number.
Output
Output the answer modulo M.
Examples
Note
In 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.