#include <bits/stdc++.h>
#define int long long

using namespace std;

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

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

int exp_rpd(int b, int e, int Mod){
    int p = 1;
    while(e > 0){
        if(e % 2 == 1){
            p *= b;
            //cout << "b = " << b << endl;
            //cout << "p = " << p << " p % 7 = " << p % 7 << endl;
            p %= Mod;
            //cout << " p = " << p << endl;
        }

        e /= 2;
        b *= b;
        b %= Mod;
    }
    return p;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k; fin >> n >> k;
        
    //cout << "phi = " << phi(k) << endl;
    int x = exp_rpd(n, phi(k) - 1, k);
    fout << x << endl;

    //cout << n * x % k << endl;



    return 0;
}