#43 「 骨牌填充 」

统计

你有多少种方法用 2x1 的多米诺骨牌填满 4xN 的矩形。

答案会很大,所以你只需输出答案模 M 的值。

输入格式

读入包括多组测试数据,以两个 0 结尾。

每组数据包含两个整数,N,M。

输出格式

每行输出答案模 M 的值。

样例数据

input

1 10000
3 10000
5 10000
0 0

output

1
11
95

数据规模与约定

$1 \le n \le 10^9, 0 < M \le 10^5$。

时间限制:1s

空间限制:512MB

Author: zrt