격자판 채우기
시간 제한2초메모리 제한128 MB
N행 M열(N, M은 14 이하) 격자를 2x1 도미노로 빈틈없이 채우는 방법의 수를 9901로 나눈 나머지로 구합니다.
문제
세로가 N칸, 가로가 M칸인 직사각형 격자판이 있다. 이 격자판을 2x1 도미노로 빈칸 없이 모두 채우려고 한다. 도미노는 회전해서 1x2로 놓을 수 있다.
N과 M이 주어질 때, 격자판을 도미노로 채우는 방법의 수를 구하라.
입력
첫째 줄에 두 정수 N과 M이 주어진다.
출력
격자판을 빈칸 없이 채우는 방법의 수를 9901로 나눈 나머지를 출력한다.
제한
- 1 ≤ N, M ≤ 14