/**
 * Author: Andu Scheusan (not_andu)
 * Created: 29.12.2023 17:32:45
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "inversmodular.in"
#define OUTFILE "inversmodular.out"

typedef long long ll;

ll getPhi(ll number){

    ll d = 2, phi = number;

    while(d * d <= number){
        if(number % d == 0){
            phi = phi / d * (d - 1);
            while(number % d == 0){
                number /= d;
            }
        }
        ++d;
    }

    if(number != 1){
        phi = phi / number * (number - 1);
    }

    return phi;

}

ll binPow(ll number, ll exponent, ll MOD){
    ll ans = 1;
    while(exponent){
        if(exponent & 1) ans = (ans * number) % MOD;
        number = (number * number) % MOD;
        exponent >>= 1;
    }
    return ans;
}

void solve(){

    ll a, n; cin >> a >> n;

    ll phi = getPhi(n);

    cout << binPow(a, phi - 1, n);

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}