Informatica Online Judge

  타일 채우기I [0455 / 01C7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 600   Total Tried : 904


The Champion of this Problem (C++) : gs17033 - ms / 109byte
My Best Submission (C++) : N/A

[]

Background

2*1 혹은 2*2크기의 타일을 2*n 크기의 직사각형모양 틀에 넣으려고 한다. 이 때 나오는 경우의 수를 구하여라.
경우의 수가 커지므로, 주어지는 수 m으로 나눈 나머지를 출력한다.

(모든 타일은 회전하여 활용할 수 있다.)

Input

첫 줄에는 직사각형 틀의 가로 길이 n이 주어진다.
둘째 줄에는 m이 주어진다.
(1<=n<=100,000, 1<=m<=40,000)

Output

경우의 수를 m으로 나눈 나머지를 출력한다.

IO Example

입력
8
100

출력
71

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]