Given is an integer N. How many permutations (P_0,P_1,\cdots,P_{2N-1}) of (0,1,\cdots,2N-1) satisfy the following condition?

* For each i (0 \leq i \leq 2N-1), N^2 \leq i^2+P_i^2 \leq (2N)^2 holds.



Since the number can be enormous, compute it modulo M.

Constraints

* 1 \leq N \leq 250
* 2 \leq M \leq 10^9
* 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 that satisfy the condition, modulo M.

Examples

Input

2 998244353


Output

4


Input

10 998244353


Output

53999264


Input

200 998244353


Output

112633322
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,t) for(int i=0;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N = 1005;
int P;  
int mul(int a, int b) { return 1ll * a * b % P; } 
int add(int a, int b) { a += b; return a >= P ? a - P : a; }
void upd(int &a, int b) { a = add(a, b); }

int n, g[N], f[N], ans;

int getF(int i) {
	int x = -1; 
	for (; (x + 1) * (x + 1) + i * i < n * n;++x) ;
	return min(n + n, x + 1);
}

int getG(int i) {
	int x = -1; 
	for (; (x + 1) * (x + 1) + i * i <= n * n * 4; ++x) ; 
	return min(n + n, x + 1);
}

struct Bound { int u, i; } ; 
bool operator<(const Bound &a, const Bound &b) { return a.u < b.u || (a.u == b.u && a.i > b.i); } 

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("d.in", "r", stdin); 
#endif
	cin >> n >> P;
	vector<Bound> v;
	lop(i, n) v.pb(Bound { getF(i), i }); 
	rep(i, n, n + n - 1) v.pb(Bound { getG(i), i });
	lop(i, n) g[i] = getG(i);
	sort(all(v)); 
	lop(k, n + 1) {
		mem(f, 0); 
		f[0] = 1;
		int a = 0, b = 0;
		for (auto e : v) {
			dec(i, k, 0) {
				if (e.i < n) {
					f[i] = mul(f[i], max(0, g[e.i] - (n + k + a - i)));
					if (i) upd(f[i], mul(f[i - 1], max(0, e.u - (b + i - 1))));
				} else {
					f[i] = mul(f[i], max(0, e.u - (b + i)));
				}
			}
			if (e.i < n) ++a; else ++b;	
		}
		upd(ans, k % 2 == 0 ? f[k] : mul(P - 1, f[k])); 
	}
	cout << ans << endl;
	return 0;
}