import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.regex.Pattern;

public class Main {

	static final int N = 16;
	static long[][] m = new long[N][N], t1 = new long[N][N],
			t2 = new long[N][N], r = new long[N][N];
	static int i, j;
	static int H, M;

	public static void main(String[] args) throws Exception {

		for (i = 0; i < N; i++)
			go(0, 0);

		// for (int i = 0; i < N; i++) {
		// for (int j = 0; j < N; j++)
		// System.out.print(m[i][j] + " ");
		// System.out.println();
		// }

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(Pattern.quote(" "));
		H = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);
		while (!(H == 0 && M == 0)) {

			pow(H);

			System.out.println(r[0][0]);

			nm = br.readLine().split(Pattern.quote(" "));
			H = Integer.parseInt(nm[0]);
			M = Integer.parseInt(nm[1]);
		}

	}

	private static void pow(int h) {
		if (h == 0) {
			for (int i = 0; i < N; i++) {
				Arrays.fill(r[i], 0);
				r[i][i] = 1;
			}
			return;
		}
		if (h == 1) {
			copy(m, r);
			return;
		}
		pow(h >> 1);
		mod();
		copy(r, t1);
		copy(r, t2);
		mul();
		mod();
		if ((h & 1) == 1) {
			copy(m, t1);
			copy(r, t2);
			mul();
			mod();
		}
	}

	private static void mod() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				r[i][j] %= M;
	}

	private static void mul() {
		for (int i = 0; i < N; i++)
			Arrays.fill(r[i], 0);
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (t1[i][j] != 0)
					for (int k = 0; k < N; k++)
						if (t2[j][k] != 0)
							r[i][k] += (t1[i][j] * t2[j][k]);
	}

	private static void copy(long[][] a, long[][] b) {
		for (int i = 0; i < N; i++)
			System.arraycopy(a[i], 0, b[i], 0, N);
		// for (int j = 0; j < N; j++)
		// b[i][j] = a[i][j] % M;
	}

	private static void go(int bit, int state) {
		if (bit == 4) {
			m[i][state] = 1;
			return;
		}
		int mask = (1 << bit);
		if ((i & mask) != 0)
			go(bit + 1, state);
		else {
			go(bit + 1, state | mask);
			if (bit < 3 && (i & (mask << 1)) == 0)
				go(bit + 2, state);
		}
	}
}