#include <stdio.h>
#include <math.h>
#include <stdint.h>

uint64_t phi(uint64_t n)
{
    uint64_t r = n , d = 2;
    while(n > 1)
    {
        if(n % d == 0)
        {
            r = r / d * (d - 1);
            while(n % d == 0)
                n /= d;
        }
        d ++;
        if(d * d > n)
            d = n;
    }
    return r;
}

uint64_t eul(uint64_t n){
    uint64_t ans = n;
    uint64_t j = 2;
    while(n > 1){
        if(n % j == 0){
            ans *= 1 - 1.0f/j;
            while(n % j == 0){
                n /= j;
            }
        }
        ++j;
    }
    return ans;
}

uint64_t pw(uint64_t x,uint64_t n){
    uint64_t ans = 1, p = x;
    while(n){
        if(n & 1){
            ans *= p;
        }
        p *= p;
        n >>= 1;
    }
    return ans;
}

int main(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    uint64_t a,n;
    scanf("%llu %llu",&a,&n);
    printf("%llu",pw(a,phi(n) - 1) % n);
    return 0;
}