// Arup Guha
// 5/10/2017
// Solution to 2016 NCPC Problem E: Exponial

import java.util.*;

public class e {

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		long n = stdin.nextLong();
		long m = stdin.nextLong();
		System.out.println(solve(n,m));
	}

	public static long solve(long n, long m) {

		// Base cases - the small numbers are weird, so you have to separate these out.
		if (m == 1) return 0;
		if (n == 1) return 1;
		if (n == 2) return 2%m;
		if (n == 3) return 9%m;
		if (n == 4) return (1<<18)%m;

		// It matters if n and m share a common factor or not.
		long common = gcd(n, m);
		long tmp = solve(n-1, phi(m));

		// If they don't, it's easy.
		if (common == 1) return  modexp(n, tmp, m);

		// Otherwise, what you do is realize that we want n ^ (k*phi(m) + tmp). We can calculate n ^ tmp mod m easily.
		// Now, we have to deal with n ^ (k*phi(m)) which is really n ^ phi(m) mod m. We can rewrite this as
		// ( (n/common)*common ) ^ phi(m) mod m. We know (n/common) ^ phi(m) = 1 mod m. So, just calculate the other part.
		return (modexp(common, phi(m), m)*modexp(n, tmp, m))%m;
	}

	public static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a%b);
	}

	// Calculates phi(n).
	public static long phi(long n) {

		long saven = n;

		// Store all unique divisors of n here.
		ArrayList<Long> div = new ArrayList<Long>();

		long i = 2;

		// Just get unique divisors of n.
		while (i*i <= n) {
			if (n%i == 0) div.add(i);
			while (n%i == 0) n/= i;
			i++;
		}

		// We are missing one.
		if (n > 1) div.add(n);

		// Alternate formula for phi.
		long res = saven;
		for (Long d : div)
			res = res/d*(d-1);
		return res;
	}

	// Usual modular exponentiation algorithm.
	public static long modexp(long base, long exp, long mod) {

		if (exp == 0) return 1%mod;
		if (exp == 1) return base%mod;

		if (exp%2 == 0) {
			long tmp = modexp(base, exp/2, mod);
			return (tmp*tmp)%mod;
		}

		return (base*modexp(base, exp-1, mod))%mod;
	}
}