시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 334 167 118 50.862%

문제

준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다.

세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노를 이용해서 빈 공간이 없도록 채우는 방법의 수는 몇일까?

아래 그림은 N = 3, M = 6인 예이다.

N과 M이 주어졌을 때, 격자판을 2x1크기의 도미노로 채우는 방법의 수를 구하는 방법을 작성하시오. 도미노는 회전시켜 1x2크기로 채울 수 있다. 도미노로 모두 채웠을 때, 빈 칸이 존재하면 안된다.

입력

첫째 줄에 격자판의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 14)

출력

첫째 줄에 주어진 격자판을 2x1크기의 도미노로 빈 공간이 없도록 채우는 방법의 수를 9901로 나눈 나머지를 출력한다.

예제 입력

3 6

예제 출력

41

힌트

출처

  • 문제를 만든 사람: ntopia