네 줄로 타일 깔기 > 문제은행 : 정보올림피아드&알고리즘



2138 : 네 줄로 타일 깔기

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
374 회   
시도횟수
697 회   

문제

바닥이 가로 n(n <= 10,000)칸, 세로 4칸으로 이루어졌을 때, 가로 1칸, 세로 2칸(회전 가능하다)의 타일을 이용해 타일을 까는 경우의 수를 계산하자.

가능한 경우의 수가 많기 때문에 m(m <= 100,000)으로 나눈 나머지만 출력하기로 하자.


입력형식

첫 줄에 바닥의 가로 길이를 나타내는 자연수 n과, 나머지 연산을 하기 위한 자연수 m이 입력된다.


출력형식

첫 줄에 가능한 경우의 수를 m으로 나눈 나머지를 출력한다.


입력 예

3 100

출력 예

11

입력 예

10 100

출력 예

61

입력 예

123 321

출력 예

11

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP