#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define nmax 25
//#define MOD 1000000007
//#define fin cin
//#define fout cout
using namespace std;

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

/**
Se dau a si n prime intre ele.
Sa se determine un numar natural b a.i. (a * b) % n = 1

(x + y) % n = (x%n + y%n) % n
(x - y) % n = (x%n - y%n + n) % n
(x * y) % n = (x%n * y%n) % n
(x * y * z)%n = (x * y % n) * z % n

 x          x % n
--- % n != ------- % n
 y          y % n

a = 7
n = 17
=> b = 5

a = 8
n = 11
b = 7

40
-- % 11 = 40 * 7 % 11 = 280 % 11 = 5
8

280 : 11 = 25
22
---
 60
 55
 --
  5
*/

int Phi(int n)
{
    int f, p;
    p = n;
    for (f = 2; f * f <= n; f++)
    {
        if (n % f == 0)
        {
            p = p / f * (f - 1);
            while (n % f == 0)
                n /= f;
        }
    }
    if (n > 1) p = p / n * (n - 1);
    return p;
}

int ExpoLog(int a, int n, int MOD)
{
    int p;
    for (p = 1; n > 0; n /= 2)
    {
        if (n % 2 == 1) p = 1LL * p * a % MOD;
        a = 1LL * a * a % MOD;
    }
    return p;
}

int main()
{
    int a, n, phi, b;
    fin >> a >> n;
    phi = Phi(n);
    b = ExpoLog(a, phi - 1, n);
    fout << b;
	return 0;
}