#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

int A, N;

int phi(int x) {
    int res = x;
    for(int i = 2; i * i <= 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;
}

int lgput(int base, int exp) {
    if(exp == 0) return 1;
    if(exp & 1) return 1LL * base * lgput(base, exp - 1) % N;
    else return lgput(1LL * base * base % N, exp / 2) % N;
}

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

int main() {
	read();

    return 0;
}