행 열의 격자와 가지 색의 도미노가 있다. 각 색의 도미노는 무한히 많다. 도미노 하나는 한 변을 공유하는 두 칸을 덮으며, 가로 또는 세로로 놓을 수 있다.
도미노가 격자 밖으로 나가거나 서로 겹치지 않도록 격자의 모든 칸을 덮으려고 한다. 서로 다른 두 도미노가 덮은 칸 중 한 쌍이라도 상하좌우로 이웃하면, 그 두 도미노의 색은 달라야 한다. 꼭짓점에서만 만나는 것은 상관없다.
도미노의 배치와 각 도미노의 색을 정하는 방법의 수를 으로 나눈 나머지를 구하여라. 가지 색을 모두 사용할 필요는 없다. 도미노의 배치가 다르거나, 같은 위치의 도미노 중 하나라도 색이 다르면 서로 다른 방법이다. 격자를 회전하거나 뒤집어서 같아지는 방법도 원래 격자에서 배치 또는 색이 다르면 서로 다르게 센다. 같은 색의 도미노끼리는 구별하지 않는다.
입력은 다음과 같은 형식으로 주어진다.
조건을 만족하는 방법의 수를 으로 나눈 나머지를 출력한다. 가능한 방법이 없으면 을 출력한다.
가로 도미노 두 개 또는 세로 도미노 두 개로 덮을 수 있다. 각 배치에서 두 도미노는 이웃하므로 서로 다른 색을 사용해야 한다. 따라서 가지이다.
아홉 칸을 두 칸짜리 도미노로 모두 덮을 수 없다.
