safdsafsafdsa

#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");

int powrest (int a, int b, int c) {
    int rest, p = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            rest = (rest * a) % c;
        }
        b /= 2;
        a = a * a % c;
    }
    return rest;
}

int logpow (int a, int n) {
    int p = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            p *= a;
        }
        a *= a;
        n /= 2;
    }
    return p;
}

int phi (int n) {
    int p = 2, k, rez = 1;
    while (p * p <= n) {
        k = 0;
        while (n % p == 0) {
            n /= p;
            k ++;
        }
        if (k > 0) {
            rez *= logpow (p, k - 1) * (p - 1);
        }
        p ++;
    }
    if (n > 1) {
        rez *= (n - 1);
    }
    return rez;
}

int main() {
    int a, n, rez;
    in >> a >> n;
    rez = powrest (a, phi (n) - 1, n);
    out << rez + 1;
    return 0;
}