문제
바닥이 가로 n(n <= 10,000)칸, 세로 4칸으로 이루어졌을 때, 가로 1칸, 세로 2칸(회전 가능하다)의 타일을 이용해 타일을 까는 경우의 수를 계산하자.
가능한 경우의 수가 많기 때문에 m(m <= 100,000)으로 나눈 나머지만 출력하기로 하자.
입력
첫 줄에 바닥의 가로 길이를 나타내는 자연수 n과, 나머지 연산을 하기 위한 자연수 m이 입력된다.
출력
첫 줄에 가능한 경우의 수를 m으로 나눈 나머지를 출력한다.
예제1
입력
3100 출력
11
예제2
입력
10100 출력
61
예제3
입력
123321 출력
11