Quad Tiling

Time Limit: 1000MS

Memory Limit: 65536K

Description

Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:In how many ways can you tile a 4 × N (1 ≤ N ≤ 109) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 105).

Input

Input consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.

Output

For each test case, output the answer modules M.

Sample Input

1 10000
3 10000
5 10000
0 0

Sample Output

1
11
95

Hint

Source

POJ Monthly--2007.10.06, Dagger

提交代码