/*
    Invers Modular
*/
#define ll long long int
ll power(ll a, ll b, ll mod)
{
    if (b < 0) return power(1.0 / a, -b,mod);
    if (b == 0)
        return 1;
    ll  temp = power(a, b / 2, mod);
    ll  result = ((temp % mod)  * (temp % mod)) % mod;
    if (b % 2 == 1)
        result = ( result * (a % mod) ) % mod;
    return result;
}

int phi(int n)
{
    int result = n;
    int i;
    for (i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
            {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define  _CRT_SECURE_NO_WARNINGS
int main()
{
    int A, N;
    FILE* f;
    f = fopen("inversmodular.in", "rt");
    FILE* g;
    g = fopen("inversmodular.out", "wt");
    fscanf(f, "%d%d", &A, &N);

    ll invMod = power(A, phi(N) - 1, N);
    fprintf(g, "%lld", (invMod % N));
    fclose(f);
    fclose(g);
    return 0;
}