#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int phi(int n) {
    int ans = n, d;
    for( d = 2; d * d <= n; d++ ) {
        if( n % d == 0 ) {
            while( n % d == 0 )
                n /= d;
            ans -= ans / d;
        }
    }
    if( n > 1 )
        ans -= ans / n;
    return ans;
}

int a, n;

int fastExp(int base, int exponent) {
    int ans = 1;
    while( exponent > 0 ) {
        if( exponent & 1 )
            ans = ans * base % n;
        base = ((base % n) * (base % n) % n);
        exponent >>= 1;
    }
    return ans;
}


signed main()
{
    fin >> a >> n;
    fout << fastExp(a, phi(n) - 1);
    return 0;
}