This is a problem need applying fast matrix power technique. The fast matrix power calculation is similar to fast integer power and with divide and conquer method we can finish it in time.

Quad Tiling is a dynamic programming problem. At first we can give the transition relationship between the state of current line with that of last line.

1. If last line is ====
• ____
• ==__
• _==_
• __==
• ====
2. If last line is ==__
• ====
• __==
3. If last line is __==
• ====
• ==__
4. If last line is _==_
• =__=
5. If last line is =__=
• _==_
6. If last line is ___
• ====

Note that every state won't transit to itself except ====. Then we can write the transition matrix and the result is value of first cell from top left of nth power of this matrix.

import java.io.*;
import java.util.*;

private static int MOD = 1;
private static int[][] multiple(int[][] A, int[][] B) {
int[][] C = new int[A.length][B[0].length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
for (int k = 0; k < B[0].length; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
}
}
}
return C;
}

private static int[][] pow(int[][] A, int n) {
int[][] I = new int[A.length][A.length];
for (int i = 0; i < A.length; i++) {
I[i][i] = 1;
}

while (n > 0) {
if ((n & 1) == 1) I = multiple(I, A);
A = multiple(A, A);
n >>= 1;
}
return I;
}

private static void solve(int n) {
int[][] A = {
{1, 1, 1, 1, 0, 1},
{1, 0, 1, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0}
};

A = pow(A, n);
System.out.println(A[0][0]);
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);

while(in.hasNextInt()) {
int n = in.nextInt();
MOD = in.nextInt();

if (n == 0) return;

solve(n);
}
}
}