#include <bits/stdc++.h>
using namespace std;

long long n;

static long long expow(long long b, long long e) {
    long long a = 1;
    while(e > 0) {
        if (e % 2)
            a = a * b % n;
        b = b * b % n;
        e = e / 2; }
    return a; }

long long lukeuler(long long n) {
    long long c = n, d = 2;
    while ( d * d <= n) {
        if (n % d == 0) {
            c = c / d;
            c = c * (d - 1); }
        while (n % d == 0) {
            n = n / d; }
        d++; }
    if (n > 1) {
        c = c / n;
        c = c * (n - 1); }
    return c; }

int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    long long  a, eul;
    scanf("%lld %lld", &a, &n);
    eul = lukeuler(n);
    printf("%lld", expow(a, eul - 1));
    return 0; }