| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 152 | 130 | 112 | 86.154% |
$N \times M$ 크기의 백지 퍼즐 격자가 주어진다. 격자의 각 칸에는 퍼즐 조각을 끼울 수 있으며, 조각의 각 면은 볼록하거나, 오목하거나, 평평할 수 있다. 조각은 회전을 고려하지 않으며, 총 3ドル^4 = 81$가지이다.
각 형태의 조각을 수량 제한 없이 사용 가능할 때, 격자를 채우는 방법의 수를 10ドル^9+7$로 나눈 나머지를 계산하라. 하나 이상의 칸에 다른 형태의 조각을 끼울 경우, 다른 방법으로 취급한다.
첫 번째 줄에 두 정수 $N$과 $M$이 차례대로 주어진다. (1ドル \le N \le 8,ドル 1ドル \le M \le 10^5$)
첫 번째 줄에 답을 출력한다.
2 2
81
1 2
3
8 8
889639405