当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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 consists of several test cases followed by a line containing double 0. Each test case consists of two integers, N and M, respectively.
For each test case, output the answer modules M.
1 10000 3 10000 5 10000 0 0
1 11 95
| 时间上限 | 内存上限 |
| 1000 | 65536 |