# include <cstdio>

# define FIN "inversmodular.in"
# define FOUT "inversmodular.out"
# define ll long long

ll N, A, pow;

     ll phi(ll N)
     {
         ll i, sol = 1, pow;
         
         for (i = 2; i * i <= N; ++i)
         {
            pow = 1;
            while (N % i == 0)
            {
               N /= i;
               pow *= i;
            }
            if (pow > 1) 
            {
               pow /= i;
               sol *= (i - 1) * pow;
            }
         }
         if (N > 1) sol *= (N - 1);
         
         return sol;
     }
     
     ll power(ll A, ll B)
     {
         ll i, rez = 1;
         
         for (i = 1; i <= B; i <<= 1)
         {
             if (i & B) rez = (rez * A) % N;
             A = (A * A) % N;
         }
         
         return rez;
     }

     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%lld%lld",&A, &N);
         
         printf("%lld",power(A, phi(N)-1));
         
         return 0;
     }