import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Scanner;

class Main {

    public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {
        //System.out.println( totient( 1112123123123l ) );
        Scanner scanner = new Scanner(new FileInputStream("inversmodular.in"));
        PrintWriter writer = new PrintWriter("inversmodular.out", "UTF-8");

        long a = scanner.nextLong();
        long n = scanner.nextLong();
        long result = solve(a, totient(n)-1, n );
        writer.println(result);
        writer.close();
    }

    public static long totient( long n ){
        long ret = n;
        for ( int i=2; i*i<=n; i++ ){
            while ( n % i == 0 ){
                n = n / i;
                ret = ret - ret/i;
            }
        }
        if ( n > 1 ){
            ret = ret - ret/n;
        }
        return ret;
    }

    public static long solve( long a, long p, long mod  ){
        if ( p == 0 ){
            return 1;
        }
        if ( p == 1 ){
            return a;
        }
        if ( p%2==0 ){
            long aux = solve( a, p/2, mod );
            return ( aux * aux ) % mod;
        } else {
            return ( a * solve( a, p-1, mod ) ) % mod ;
        }
    }

}