#include <iostream>
#include <fstream>
#include <stdint.h>

int main() {
    std::ifstream fin("inversmodular.in");
    std::ofstream fout("inversmodular.out");

    int64_t a, n;
    fin >> a >> n;

    int64_t euler = n, val = n;
    for(int64_t d = 2; d * d <= val; ++d) {
        if(val % d)
            continue;
        
        euler = (euler / d) * (d - 1);
        while(!(val % d))
            val /= d;
    }
    if(val != 1)
        euler = (euler / val) * (val - 1);
    
    int64_t exp = euler - 1;
    int64_t res = 1;

    for(; exp; exp >>= 1) {
        if(exp & 1)
            res = (res * a) % n;
        a = (a * a) % n;
    }

    fout << res << '\n';

    fin.close();
    fout.close();
    
    return 0;
}