//http://www.infoarena.ro/problema/inversmodular
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
#define llu unsigned long long int
llu  a,n,p,re = 1;

int fi2(llu n)
{
    llu res = n;
    vector<int> primes;
    for(int i = 2 ; i*i <= n ; i++)
    {
        if(n%i == 0)
            primes.push_back(i);
        while(n%i == 0)
            n /= i;
    }
    for(const auto& prim :primes)
        res -= res/prim;
    if(n>1)
        res -= res/n;
    return res;
}

int main()
{
    in >> a >> n;//Se dau a si n si se vrea x a.i. ax=1(mod n) si ne folosim de faptul ca a^fi(n)=1(mod n) unde fi(n)=nr. de nr. <n prime cu n
    p = fi2(n)-1;//deci x = a^(fi(n)-1) iar pentru a ridica la putere folosim ridicarea la putere in timp logaritmic
    while(p)
    {
        if (p&1)
            re = ((re%n)*(a%n))%n;
        a = ((a%n)*(a%n))%n;
        p >>= 1;
    }
    out<<re;//afisam a^(f(n)-1)
}