크기의 직사각형 격자를 도미노와 트로미노로 빈틈없이 덮으려고 한다.
도미노는 한 변의 길이가 인 정사각형 두 개를 한 변으로 이어 붙인 모양이다. 트로미노는 다음 두 종류를 모두 사용할 수 있다.
각 타일은 격자에 맞추어 회전하여 사용할 수 있고, 종류별 개수에는 제한이 없다. 타일끼리 겹치거나 격자 밖으로 나가면 안 된다.
격자를 덮는 방법의 수를 로 나눈 나머지를 구하여라. 각 타일이 차지하는 칸들의 집합이 다르면 서로 다른 방법으로 센다. 같은 모양의 타일끼리는 구별하지 않는다.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 격자를 덮는 방법의 수를 로 나눈 나머지를 출력한다.
도미노만 사용하는 방법은 가지, L자 트로미노 두 개를 사용하는 방법은 가지, 일자 트로미노 두 개를 사용하는 방법은 가지이다.
