#include <cstdio>
#include <math.h>

#define LL long long
#define MOD p

FILE *fin, *fout;
using namespace std;
LL b, p, ans, term, pi;

LL phi(LL nr)
{
    LL cur = nr;
    for(LL i = 2;i * i <= nr; ++i)
    {
        if (nr % i == 0)
        {
            while(nr % i == 0)nr /= i;
            cur = (cur / i) * (i - 1);
        }
    }
        if (nr != 1) cur = cur / nr * (nr - 1);
    return cur;
}


int power(LL x, int y)
{
    int sol = 1;
    for(;y; y>>=1)
    {
        if(y&1)
        {
            sol = ((LL)sol*x)%MOD;
        }
        x = ((LL)x*x)%MOD;
    }
    return sol;
}

int gcd(int x, int y)
{
    if(y == 0) return x;
    return gcd(y, x%y);
}

int main()
{
    fin = freopen("valuare.in", "r", stdin);
    fout = freopen("valuare.out", "w", stdout);
    scanf("%lld%lld", &b,&p);
    pi =phi(p);
    if(gcd(b-1, p) || pi == p-1)
    {
        ans = (power(b, b) + MOD - power(b, 2) + b%MOD +MOD -1)%MOD;
        term = power(b-1, 2);
        term = power(term, pi - 1);
        ans = (ans*term)%MOD;
    }
    else
    {
        term = 1;
        for(int i = b-1; i>= 1; --i)
        {
            ans = (ans + term * i)%MOD;
        }
    }
    printf("%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}