#include <bits/stdc++.h>

using namespace std;

#define int long long

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int sigma(int n)
{
    int rez = n;

    if(n % 2 == 0)
    {
        rez /= 2;

        while(n % 2 == 0)
            n /= 2;
    }

    for(int i = 3; i * i <= n; i += 2)
    {
        if(n % i == 0)
        {
            rez /= i;
            rez *= (i - 1);

            while(n % i == 0)
                n /= i;
        }
    }

    if(n != 1)
    {
        rez /= n;
        rez *= (n - 1);
    }

    return rez;
}


int lgput(int n,int p, int b)
{
    int rez = 1;
    int x = n;

    while(p > 0)
    {
        if(p & 1)
        {
            rez = (rez * x) % b;
        }
        x = (x * x) % b;
        p >>= 1;
    }

    return rez;
}

 main()
{
    int a, b;
    in >> a >> b;

    int p = sigma(b) - 1;

    out << lgput(a,p,b);

    return 0;
}