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

int n;

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

int lukeuler(int n) {
    int 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); } }

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