#include <vector>
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cassert>
// #include <bits/stdc++.h>

#define hash ajlasd

using namespace std;

typedef long long ll;

template<class T>
void print(vector<T> s){
	for (T i : s)
		cout << i << " ";
	cout << endl;
}

namespace fft{

    typedef double dbl;
    typedef long long ll;

    struct Complex{
        dbl x, y;
        Complex(dbl x = 0, dbl y = 0) : x(x), y(y) {}
    };

    Complex operator + (Complex a, Complex b) { return Complex(a.x + b.x, a.y + b.y); }
    Complex operator - (Complex a, Complex b) { return Complex(a.x - b.x, a.y - b.y); }
    Complex operator * (Complex a, Complex b) { return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
    Complex conj(Complex a) { return Complex(a.x, -a.y); }

    int base = 1;
    const dbl PI = atan2(0, -1);
    vector<Complex> roots = {{0, 0}, {1, 0}};
    vector<int> rev = {0, 1};

    void ensureBase(int b){
        if (b <= base)
            return;

        rev.resize(1 << b);
        for (int i = 0; i < (1 << b); i++)
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (b - 1));

        roots.resize(1 << b);
        while (base < b){
            dbl angle = PI / (1 << base);
            for (int i = (1 << (base - 1)); i < (1 << base); i++){
                roots[i << 1] = roots[i];
                dbl angle_i = (2 * i + 1 - (1 << base)) * angle;
                roots[(i << 1) + 1] = Complex(cos(angle_i), sin(angle_i));
            }
            base++;
        }
    }

    void fft(vector<Complex> &f, int n){
        int shift = 0;
        while ((1 << shift) < n)
            shift++;
        ensureBase(shift);
        shift = base - shift;
        for (int i = 0; i < n; i++)
            if (i > (rev[i] >> shift))
                swap(f[i], f[rev[i] >> shift]);

        for (int len = 1; len < n; len *= 2){
            for (int i = 0; i < n; i += 2 * len){
                for (int j = i, k = i + len; j < i + len; j++, k++){
                    Complex z = f[k] * roots[k - i];
                    f[k] = f[j] - z;
                    f[j] = f[j] + z;
                }
            }
        }
    }

    vector<Complex> f;
    vector<ll> answer;

    vector<ll> multiply(vector<int> &a, vector<int> &b){
        int need = a.size() + b.size() - 1;
        int bb = 0;
        while ((1 << bb) < need)
            bb++;
        ensureBase(bb);
        int n = (1 << bb);
        f.resize(n);
        for (int i = 0; i < n; i++){
            f[i].x = (i < a.size() ? a[i] : 0);
            f[i].y = (i < b.size() ? b[i] : 0);
        }
        fft(f, n);
        Complex r = Complex(0, -0.25 / n);
        for (int i = 0; i <= n / 2; i++){
            int j = (n - i) & (n - 1);
            Complex z = (f[j] * f[j] - conj(f[i] * f[i])) * r;
            if (i != j)
                f[j] = (f[i] * f[i] - conj(f[j] * f[j])) * r;
            f[i] = z;
        }
        fft(f, n);
        answer.resize(need);
        for (int i = 0; i < need; i++)
            answer[i] = (ll)(f[i].x + 0.5);
        // print(answer);
        return answer;
    }

    // const int k = 15;

    // vector<int> multiplyWithMod(vector<int> &a, vector<int> &b, int mod){
    // 	int kk = (1 << k);
    // 	int kkk = (kk << k) % mod;
    // 	int need = a.size() + b.size() - 1;
    // 	vector<ll> answer(need, 0);
    // 	vector<int> aa(a.size());
    // 	vector<int> bb(b.size());

    // 	for (int i = 0; i < a.size(); i++)
    // 		aa[i] = a[i] >> k;
    // 	for (int i = 0; i < b.size(); i++)
    // 		bb[i] = b[i] >> k;
    // 	vector<ll> c = multiply(aa, bb);
    // 	for (int i = 0; i < need; i++){
    // 		ll x = c[i] % mod;
    // 		answer[i] += x * (kkk - kk);
    // 	}

    // 	for (int i = 0; i < a.size(); i++)
    // 		aa[i] = a[i] & (kk - 1);
    // 	for (int i = 0; i < b.size(); i++)
    // 		bb[i] = b[i] & (kk - 1);
    // 	c = multiply(aa, bb);
    // 	for (int i = 0; i < need; i++){
    // 		ll x = c[i] % mod;
    // 		answer[i] += x * (1 - kk);
    // 	}

    // 	for (int i = 0; i < a.size(); i++)
    // 		aa[i] += a[i] >> k;
    // 	for (int i = 0; i < b.size(); i++)
    // 		bb[i] += b[i] >> k;
    // 	c = multiply(aa, bb);
    // 	for (int i = 0; i < need; i++){
    // 		answer[i] += c[i] % mod * kk;
    // 		answer[i] %= mod;
    // 		if (answer[i] < 0)
    // 			answer[i] += mod;
    // 	}

    // 	vector<int> ans(need);
    // 	for (int i = 0; i < need; i++)
    // 		ans[i] = answer[i];
    // 	return ans;
    // }
};

int mod;

int power(ll a, int n){
	ll res = 1;
	while (n > 0){
		if (n & 1)
			res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n >> mod;
	vector<int> cnt(mod, 0);
	for (int i = 1; i < mod; i++)
		cnt[power(i, n)]++;
	vector<ll> c = fft::multiply(cnt, cnt);
	for (int i = mod; i < c.size(); i++)
		c[i - mod] += c[i];
	c.resize(mod);
	ll answer = 0;
	for (int i = 1; i < mod; i++){
		int val = power(i, n) * 2 % mod;
		answer += cnt[val];
	}
	for (int i = 0; i < mod; i++)
		answer += cnt[i] * c[i];
	assert(answer % 2 == 0);
	cout << answer / 2 << endl;
	return 0;
}