import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static long[][] matrix;

// An+4 =An+3 + 5*An+2 +An+1 -An
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		matrix = new long[4][4];
		while (M != 0 || N != 0) {
			long result = solve();
			System.out.println(result);
			N = scan.nextInt();
			M = scan.nextInt();
		}
		scan.close();
	}

	private static long solve() {
		if (N == 1) {
			return 1 % M;
		}
		if (N == 2) {
			return 5 % M;
		}
		if (N == 3) {
			return 11 % M;
		}
		matrix[0][0] = 1;
		matrix[0][1] = 5;
		matrix[0][2] = 1;
		matrix[0][3] = -1;
		for (int i = 1; i < matrix.length; i++) {
			matrix[i][i - 1] = 1;
		}
		matrix = pow(matrix, N - 3);
		long[][] init = { { 11 }, { 5 }, { 1 }, { 1 } };
		matrix = mul(matrix, init);

		return matrix[0][0];
	}

	private static long[][] mul(long[][] matA, long[][] matB) {
		long[][] matrix = new long[matA.length][matB[0].length];
		for (int i = 0; i < matA.length; i++) {
			for (int j = 0; j < matB[0].length; j++) {
				for (int k = 0; k < matA[0].length; k++) {
					matrix[i][j] = (matrix[i][j] + matA[i][k] * matB[k][j]) % M;
				}
			}
		}
		return matrix;
	}

	private static long[][] pow(long[][] mat, int n) {
		long[][] matrix = new long[mat.length][mat[0].length];
		for (int i = 0; i < matrix.length; i++) {
			matrix[i][i] = 1;
		}
		while (n > 0) {
			if ((n & 1) == 1) {
				matrix = mul(mat, matrix);
			}
			mat = mul(mat, mat);
			n >>= 1;
		}
		return matrix;
	}
}