This is the easy version of the problem. The only difference between the easy version and the hard version is the constraints on n. You can only make hacks if both versions are solved.

A permutation of 1, 2, …, n is a sequence of n integers, where each integer from 1 to n appears exactly once. For example, [2,3,1,4] is a permutation of 1, 2, 3, 4, but [1,4,2,2] isn't because 2 appears twice in it.

Recall that the number of inversions in a permutation a_1, a_2, …, a_n is the number of pairs of indices (i, j) such that i < j and a_i > a_j.

Let p and q be two permutations of 1, 2, …, n. Find the number of permutation pairs (p,q) that satisfy the following conditions:

  * p is lexicographically smaller than q. 
  * the number of inversions in p is greater than the number of inversions in q. 



Print the number of such pairs modulo mod. Note that mod may not be a prime.

Input

The only line contains two integers n and mod (1≤ n≤ 50, 1≤ mod≤ 10^9).

Output

Print one integer, which is the answer modulo mod.

Example

Input


4 403458273


Output


17

Note

The following are all valid pairs (p,q) when n=4.

  * p=[1,3,4,2], q=[2,1,3,4], 
  * p=[1,4,2,3], q=[2,1,3,4], 
  * p=[1,4,3,2], q=[2,1,3,4], 
  * p=[1,4,3,2], q=[2,1,4,3], 
  * p=[1,4,3,2], q=[2,3,1,4], 
  * p=[1,4,3,2], q=[3,1,2,4], 
  * p=[2,3,4,1], q=[3,1,2,4], 
  * p=[2,4,1,3], q=[3,1,2,4], 
  * p=[2,4,3,1], q=[3,1,2,4], 
  * p=[2,4,3,1], q=[3,1,4,2], 
  * p=[2,4,3,1], q=[3,2,1,4], 
  * p=[2,4,3,1], q=[4,1,2,3], 
  * p=[3,2,4,1], q=[4,1,2,3], 
  * p=[3,4,1,2], q=[4,1,2,3], 
  * p=[3,4,2,1], q=[4,1,2,3], 
  * p=[3,4,2,1], q=[4,1,3,2], 
  * p=[3,4,2,1], q=[4,2,1,3]. 
#include <bits/stdc++.h>
using namespace std;

template<typename A, typename B>
string to_string(pair<A, B> p);

template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string &s) {
	return '"' + s + '"';
}

string to_string(const char *s) {
	return to_string((string) s);
}

string to_string(bool b) {
	return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(v[i]);
	}
	res += "}";
	return res;
}

template<size_t N>
string to_string(bitset<N> v) {
	string res = "";
	for (size_t i = 0; i < N; i++) {
		res += static_cast<char>('0' + v[i]);
	}
	return res;
}

template<typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

template<typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", "
			+ to_string(get<2>(p)) + ")";
}

template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", "
			+ to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void dbg_out() {
	cout << endl;
}

template<typename Head, typename ... Tail>
void dbg_out(Head H, Tail ... T) {
	cout << " " << to_string(H);
	dbg_out(T...);
}

#ifndef ONLINE_JUDGE
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", dbg_out(__VA_ARGS__)
#else
#define dbg(...) ;
#endif

#define import ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define read(x) cin >> x
#define out(x) cout << x
#define readInt(x) scanf("%d",&x)
#define readLong(x) scanf("%lld",&x)
#define readDouble(x) scanf("%Lf",&x)
#define readString(x) scanf("%s",&x)
#define outInt(x) printf("%d",x)
#define outLong(x) printf("%lld\n",x)
#define outDouble(x) printf("%Lf",x)
#define outString(x) printf("%s",x)
#define outLine(x) cout << x << endl
#define readArr(x,size) for(int i=0;i<size;i++)read(x[i])
#define outArr(x,size) for(int i=0;i<size;i++){cout << x[i] << " ";}out(endl)
#define ll long long
#define ld long double
#define pii pair<int,int>
#define len(s) (int)(s.length())
#define bitCnt(msk) __builtin_popcount(msk)
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int mrand(int a) {
	return rng() % a;
}

int mod;
vector<vector<int>>memo2,memo3;
vector<int>memo;
int maxInv;
int solve(int dif,int n) {
	if(memo3[n][dif]!=-1)return memo3[n][dif];
	int ans=0;
	for(int i=1;i<dif && i<n;i++) {
		ans+=(n-i);
	}
	return memo3[n][dif]=ans;
}
int perms(int n,int invs) {
	if(invs<0)return 0;
	if(memo2[n][invs]!=-1)return memo2[n][invs];
	if(n==1)return memo2[n][invs]=invs==0?1:0;
	int ans=0;
	for(int i=1;i<=n;i++) {
		ans=(ans+perms(n-1, invs-(i-1)))%mod;
	}
	return memo2[n][invs]=ans;
}

int dp(int n) {
	if(n==1)return 0;
	if(memo[n]!=-1)return memo[n];
	int ans=(int)((n*1ll*dp(n-1))%mod);

	for(int invi=2;invi<=maxInv;invi++) {
		int permsi=perms(n-1, invi);
		for(int invj=0;invj+1<invi;invj++) {
			int permsj=perms(n-1, invj);
			int dif=invi-invj;
			ll inc=(permsi*1ll*permsj)%mod;
			inc=(inc*solve(dif, n))%mod;
			ans=(ans+((int)inc))%mod;
		}
	}

	return memo[n]=ans;
}

void test_case() {
	int n;
	cin >> n;
	maxInv=(n*(n-1))/2;
	cin >> mod;
	memo.resize(n+1,-1);
	for(int i=0;i<=n;i++) {
		memo2.push_back(vector<int>(maxInv+1,-1));
		memo3.push_back(vector<int>(maxInv+1,-1));
	}

	outLine(dp(n));
}

int main() {
	import;
	int tc=1;
//	cin >> tc;
	while(tc-->0)
		test_case();
	return 0;
}

