#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ll;
typedef pair< int , int > PII;

ll a, n;

ll power(ll b, ll p){
    int rs = 1;
    for (; p; p >>= 1){
        if (p & 1) rs = rs * b % n;
        b *= b;
        b %= n;
    }

    return rs;
}

ll fi(ll n){
    ll rs = n;
    for (int i = 2; i <= sqrt(n); i++){
        if (n % i == 0){
            while (n % i == 0) n /= i;
            rs = rs / i * (i - 1);
        }
    }
    return (n == 1 ? rs : rs / n * (n - 1));
}

ll inv_mod(ll base){
    return power(base, fi(n) - 1);
}

int main(){
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> n;
    cout << inv_mod(a);

    return 0;
}