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>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}

// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
//

const int N = 55;
int mod;

int dp[N][N*N];
int sum[N*N];

int get(int i,int j){
  return (sum[j] - (i>0 ? sum[i-1] : 0) + mod)%mod;
}
int ch[N][N];

int pa(int a,int b){
  if(a>b)swap(a,b);
  return (b-a+1)*(a+b)/2;
}
int ways(int dif,int n){
  int mn = 1,mx = min(n-1,dif-1);
  if(mn > mx)return 0;
  return pa(n-mn,n-mx)%mod;
}
int fat[N];

int32_t main(){
  fastio;
  int n;
  cin >> n >> mod;
  fat[0] = 1;
  rep(i,1,N)fat[i] = 1ll*i*fat[i-1]%mod;
  rep(i,0,N){
    ch[i][0] = ch[i][i] = 1;
    rep(j,1,i){
      ch[i][j] = (ch[i-1][j-1] + ch[i-1][j]);
      if(ch[i][j]>=mod)ch[i][j]-=mod;
    }
  }
  dp[0][0] = 1;

  rep(i,1,n+1){
    rep(j,0,N*N){
      sum[j]=dp[i-1][j];
      if(j)sum[j]+=sum[j-1];
      if(sum[j]>=mod)sum[j]-=mod;
    }
    
    rep(j,0,N*N){
      dp[i][j] = get(j-(i-1),j);
    }

  }


  ll res=0;
  rep(i,0,n-1){

    int qtd = n-i;
    int mx = pa(0,qtd-2);

    rep(v2,0,mx+1)rep(v1,v2+1,mx+1){
        res+=1ll*dp[qtd-1][v1] * dp[qtd-1][v2]%mod * ch[n][i]%mod * fat[i]%mod * ways(v1-v2,qtd)%mod;
        if(res>=mod)res-=mod;
    }
    
  }

  
  cout << res << endl;

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}