极为奇怪的代妈
#include <iostream>
#include <stdio.h>
using namespace std;

struct e{
	long long int gush[5][5];
	e(){
		for(int i = 0; i < 5; i++)
			for(int j = 0; j < 5; j++)
				gush[i][j] = 0;
	}
	e(const e& eee){
		for(int i = 0; i < 5; i++){
			for(int j = 0; j < 5; j++){
				gush[i][j] = eee.gush[i][j];
			}
		}
	}
};

int dt[25] = {1,2,1,0,1,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0};

e ee;

void init(int M){
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			ee.gush[i][j] = dt[i*5+j]%M;
		}
	}
}

e mult(e e1, e e2, int m){
	e temp;
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			long long int tmp = 0;
			for(int k = 0; k < 5; k++){
				tmp += e1.gush[i][k] * e2.gush[k][j];
			}
			temp.gush[i][j] = tmp%m;
		}
	}
	return temp;
}

e power(int n, int m){
	if(n == 1) return ee;
	e temp = power(n/2, m);
	if(n%2 == 0) return mult(temp, temp, m);
	else return mult(ee, mult(temp, temp, m), m);
}

int main() {
	while(1){
		int N, M;
		scanf("%d%d", &N, &M);
		if(N==0 && M==0) break;
		if(N == 0){
			printf("%d\n",1%M);
			continue;
		}
		if(M == 1){
			printf("%d\n", 0);
			continue;
		}
		if(N == 1){
			printf("%d\n", 1);
			continue;
		}
		init(M);
		e eee = power(N-1, M);
		long long int ans = eee.gush[0][0] + eee.gush[0][1] + eee.gush[0][2] + eee.gush[0][4];
		printf("%I64d\n", ans%M);
	}
	return 0;
}