#include <iostream>
#include <stdio.h>

using namespace std;

bool prim(int n){
    if(n<=1)
        return false;
    for(int j=2; j*j<=n; ++j)
        if(n%j==0)
            return false;
    return true;
}

int fi(int n){
    int k=1;

    for(int i=2; i*i<n; ++i){
        if(n%i==0){
            ++k;
            if(n/i!=i)
                ++k;
        }
    }

    if(prim(n))
        return n-1;
    return n-k;
}

int putere(int b, int p){
    if(p==0)
        return 1;
    if(p==1)
        return b;
    if(p%2==0){
        int x=putere(b, p/2);
        return x*x;
    }
    return b*putere(b, p-1);
}

int main()
{
    FILE *fin=fopen("inversmodular.in", "r");
    FILE *fout=fopen("inversmodular.out", "w");

    int n, a;

    fscanf(fin, "%d%d", &a, &n);
    a=putere(a, fi(n)-1);
    fprintf(fout, "%d", a%n);

    return 0;
}