## 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 ¡Ü 10^9) rectangle with 2 ¡Á 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ¡Ü 10^5).## 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## Source

POJ Monthly--2007.10.06, Dagger