Given is a positive integer N. Find the number of permutations (P_1,P_2,\cdots,P_{3N}) of (1,2,\cdots,3N) that can be generated through the procedure below. This number can be enormous, so print it modulo a prime number M.

* Make N sequences A_1,A_2,\cdots,A_N of length 3 each, using each of the integers 1 through 3N exactly once.
* Let P be an empty sequence, and do the following operation 3N times.
* Among the elements that are at the beginning of one of the sequences A_i that is non-empty, let the smallest be x.
* Remove x from the sequence, and add x at the end of P.

Constraints

* 1 \leq N \leq 2000
* 10^8 \leq M \leq 10^9+7
* M is a prime number.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of permutations modulo M.

Examples

Input

1 998244353


Output

6


Input

2 998244353


Output

261


Input

314 1000000007


Output

182908545
#include "bits/stdc++.h"
using namespace std;

long long N, M;
int di[3] = { 1, 2, 3 }, dj[3] = { 1, -1, 0 };
vector<long long> INV;

void init() {
	INV.resize(N + 1);
	INV[1] = 1;
	for (int i = 2; i <= N; i++) {
		INV[i] = M - (INV[M % i] * (M / i)) % M;
	}
}

int main() {
	cin >> N >> M;
	N *= 3;
	init();
	static long long DP[6001][12001] = {};
	DP[0][N] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N * 2; j++) {
			if (DP[i][j] == 0) continue;
			for (int k = 0; k < 3; k++) {
				int ni = i + di[k], nj = j + dj[k];
				if (0 <= ni && ni <= N && 0 <= nj && nj <= N * 2) {
					DP[ni][nj] += (DP[i][j] * INV[ni]) % M;
					DP[ni][nj] %= M;
				}
			}
		}
	}
	long long ANS = 0;
	for (int i = N; i <= N * 2; i++) {
		ANS += DP[N][i];
		ANS %= M;
	}
	for (int i = 1; i <= N; i++) {
		ANS *= i;
		ANS %= M;
	}
	cout << ANS << endl;
}