#include <stdio.h>
#include <stdlib.h>

long long cmmdc(long long a, long long b)
{
    if(b == 0)
        return a;
    return cmmdc(b, a % b);
}

// DOAR phi corect (fără brute force)
long long phin(long long n)
{
    long long result = n;

    for(long long i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            while(n % i == 0)
                n /= i;

            result -= result / i;
        }
    }

    if(n > 1)
        result -= result / n;

    return result;
}

long long lgput(long long a, long long p, long long n)
{
    long long r = 1;
    a %= n;

    while(p)
    {
        if(p % 2)
            r = (r * a) % n;
        a = (a * a) % n;
        p /= 2;
    }

    return r;
}

int main(void)
{
    FILE *in, *out;

    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");

    long long a, n;
    fscanf(in, "%lld %lld", &a, &n);

    // IMPORTANT: trebuie gcd(a,n)=1
    if(cmmdc(a, n) != 1)
    {
        fprintf(out, "0\n");
    }
    else
    {
        long long phi = phin(n);
        long long res = lgput(a, phi - 1, n);
        fprintf(out, "%lld\n", res);
    }

    fclose(in);
    fclose(out);

    return 0;
}