Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
 Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Quad Tiling
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 5838Accepted: 2616

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

Source

POJ Monthly--2007.10.06, Dagger

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator