#include <stdio.h>

int phi(int N) {

        int res = 1;
        for(int i = 2; i * i <= N; ++i) {

                if(N % i == 0) {
                      res = res * (i - 1);
                      N = N / i;
                      while(N % i == 0) {
                        res = res * i;
                        N = N / i;
                      }
                }
        }

        if(N > 1) res *= N - 1;
        
        return res;
}

int exp(int A,int P,int N) {

        long long res = 1, pow = A;
        for(; P > 0 ; P = P / 2 ) {

                if(P % 2 == 1)
                 res = res * pow % N;
                pow = pow * pow % N;
        }
        return res;
}


int main() {
        freopen("inversmodular.in","r",stdin);
        freopen("inversmodular.out","w",stdout);

        int A,N;
        scanf("%d%d",&A,&N);

        int P = phi(N) - 1, res = exp(A,P,N);

        printf("%d",res);
}