#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

int A, N ;

int phi(int x)
{
    int sol = x ;

    for(int i = 2; i * i <= x; ++i)
    {
        if( x % i == 0 )
        {
            sol = sol / i * (i - 1) ;

            while( x % i == 0 )
                 x /= i ;
        }
    }

    if( x != 1 )
        sol = sol / x * (x - 1) ;

    return sol ;
}

int putere(int x, int e, int mod)
{
    if( e == 0 )
        return 1 ;

    if( e % 2 == 0 )
    {
        int r = putere( x, e / 2, mod ) ;
        r = ( 1LL * r * r ) % mod ;
        return r ;
    }

    int r = putere( x, e / 2, mod ) ;
    r = ( 1LL * ( ( 1LL * r * r ) % mod ) * x ) % mod ;
    return r ;
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

    scanf("%d%d", &A, &N);

    printf("%d", putere(A, phi(N) - 1, N) );

	return 0 ;
}