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
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 2e3 + 5;

int DP[3 * N][N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n, m; cin >> n >> m;
	DP[0][0] = 1;
	for (int i = 1; i <= 3 * n; i++) for (int j = 0; j <= (i >> 1); j++) {
		DP[i][j] = DP[i - 1][j];
		if (j && i >= 2) DP[i][j] = (DP[i][j] + 1LL * (i - 1) * DP[i - 2][j - 1] % m) % m;
		if (j && i >= 3) DP[i][j] = (DP[i][j] + 1LL * (i - 1) * (i - 2) % m * DP[i - 3][j - 1] % m) % m;
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) ans = (ans + DP[3 * n][i]) % m;
	cout << ans << endl;


	return 0;
}
