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

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

long long phin(long long n)
{
    long long ok = 1;
    for(int i = 2;  i*i <= n; i++)
    {
        if(n%i == 0)
        {
            ok = 0;
            break;
        }
    }

    if(ok)
        return n-1;
    else
    {
        long long cnt = 0;
        for(long long i = 1; i < n; i++)
        {
            if(cmmdc(i, n) == 1)
                cnt++;
        }
        return cnt;
    }
}

long long lgput(long long a, long long p, long long n)
{
    if(p == 0)
        return 1;
    else if(p%2 == 0)
        return lgput(a*a%n, p/2, n);
    else
        return a*lgput(a*a%n, p/2, n)%n;
}

int main(void)
{

    FILE *in, *out;
    if((in = fopen("inversmodular.in", "r")) == NULL)
    {
        perror("Eroare la deschidere fisierului de intrare");
        exit(EXIT_FAILURE);
    }
    if((out = fopen("inversmodular.out", "w")) == NULL)
    {
        perror("Eroare la deschidere fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    long long a, n;
    if(fscanf(in, "%lld %lld", &a, &n) != 2)
    {
        perror("Eroare la citirea datelor din fisierul de intrare");
        exit(EXIT_FAILURE);
    }

    fprintf(out, "%lld\n", lgput(a, phin(n)-1, n));

    if(fclose(in) != 0)
    {
        perror("Eroare la inchiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }
    if(fclose(out) != 0)
    {
        perror("Eroare la inchiderea fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    return 0;
}