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

uint64_t n;

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

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

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

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