#include <bits/stdc++.h>
using namespace std ;
ifstream in ("inversmodular.in") ;
ofstream out ("inversmodular.out") ;
int n , a ;
int nrdiz ( int n )
{
    int nr = 1 , i = 2 , s = 1 ;
    while ( n != 1 )
    {
        int cnt = 0 ;
        while ( n % i == 0 )
        {
            cnt ++ ;
            n /= i ;
        }
    i ++ ;
    if ( cnt )
    s *= cnt + 1 ;
    }
    return s - 2 ;
}
int lgpower ( int a , int x )
{
    if ( x == 1 )   return a ;
    if ( x % 2 == 0 )   return lgpower( ( a * a ) % n , x >> 1 ) ;
    if ( x % 2  )   return ( a * lgpower( ( a * a ) % n , x >> 1 ) ) % n ;
}
int main ()
{
    in >> a >>  n ;
 int xi = n - 1 - nrdiz( n ) ;
 out << lgpower ( a , xi - 1 ) ;
}