#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#ifndef ONLINE_JUDGE
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
#endif

typedef long long ll;

const int MAXN = 100;
int A, N;

int phi(int x) {
    int res = x;
    for(int i = 2; (i << 1) <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1);

            while(x % i == 0)
                x /= i;
        }
    }

    if(x != 1)
        res = res / x * (x - 1);

    return res;
}

ll lgput(int base, ll exp) {
    ll sol = 1;
    for(int i = 0; (1 << i) <= exp; ++i) {
        if( ((1 << i) & exp) > 0 )
            sol = (sol * base) % N;

        base = (base * base) % N;
    }

    return sol;
}

void read() {
	fin >> A >> N;
    fout << lgput(A, phi(N) - 1);
}

int main() {
	read();

    return 0;
}