n × m 크기의 직사각형 격자가 있습니다. 격자의 가장 왼쪽 위는 (1, 1), 가장 오른쪽 아래는 (n, m)입니다. 각 격자칸은 빈칸, 선로, 장애물 중 하나입니다. 선로는 7가지 종류가 있으며 아래 그림과 같습니다.

격자의 (1, 1)에는 1번 선로가 놓여있고, (n, m)에는 1번, 2번 선로 중 하나가 놓여있습니다. 당신은 기차가 (n, m)에 도착할 수 있도록 격자의 빈칸에 선로를 놓으려 합니다. (선로를 놓지 않고 빈칸인 채로 두어도 됩니다.) 당신이 선로를 완성시키면 기차가 (1, 1)에서 오른쪽 방향으로 출발해 선로를 따라 움직입니다. 이때 기차는 격자에 있는 모든 선로를 한번 이상 지나가야 합니다. 또한, # 모양의 3번 선로는 상하좌우 모든 방향으로 연결되어 있어야 합니다.

당신은 격자의 정보가 주어질 때 격자에 선로를 놓는 방법의 수를 알고 싶습니다.

아래는 n = 3, m = 3인 격자의 예시입니다.

이 격자에 선로를 놓는 방법은 아래 2가지입니다.

격자의 정보를 담고 있는 2차원 정수 배열 grid가 매개변수로 주어집니다. 이때, 격자에 선로를 놓는 방법의 수를 return 하도록 solution 함수를 완성해 주세요. 어떻게 선로를 놓아도 문제의 조건을 만족시킬 수 없다면 0을 return 합니다.

제한사항

• 2 ≤ grid의 세로 길이 = n ≤ 8
• 2 ≤ grid의 가로 길이 = m ≤ 8
  • grid[i][j]는 (i+1, j+1) 위치의 격자칸 정보를 나타냅니다. 격자칸이 빈칸인 경우 0, 선로인 경우 각 선로의 번호(1 ~ 7), 장애물인 경우 -1입니다.
  • grid[0][0] = 1
  • grid[n-1][m-1] = 1 or 2
  • grid에서 빈칸이 한 번 이상 등장합니다.
• n × m ≤ 20

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

격자의 배치는 아래 그림과 같습니다.

이 격자에 선로를 놓는 방법은 아래 2가지입니다.

입출력 예 #3

격자의 배치는 아래 그림과 같습니다.

이 격자에 선로를 놓는 방법은 아래 4가지입니다.

입출력 예 #4

격자의 배치는 아래 그림과 같습니다.

이 격자에 선로를 놓는 방법은 644가지입니다.

입출력 예 #5

선로가 이미 완성되어 있습니다. 선로를 놓지 않는 것도 한 가지 방법으로 세며, 따라서 1을 return 합니다.

입출력 예 #6

어떻게 선로를 놓아도 문제의 조건을 만족시킬 수 없으므로 0을 return 합니다.