사무실 개설

회사가 가로 방향 도로 $N$개와 세로 방향 도로 $M$개로 이루어진 도시에 사무실을 열려고 합니다. 교차로마다 건물이 하나씩 있습니다. 각 건물은 이웃 건물과 세로 도로 최대 두 개, 가로 도로 최대 두 개로 연결되며, 모든 도로의 길이는 1입니다.

밤에는 도로 중 $N \times M - 1$개만 켜져 있고 나머지는 사용할 수 없습니다. 켜진 도로는 트리를 이루므로 어떤 건물에서든 다른 모든 건물로 갈 수 있습니다.

첫 번째 그림은 밤의 도로이고, 두 번째 그림은 낮의 도로입니다. 세 번째 그림은 아래 설명에서 쓰는 작은 예시입니다.

사무실 건물을 고르면 매달 사무실을 순회합니다. 한 건물에서 출발해 선택된 나머지 사무실을 모두 방문한 뒤 처음 건물로 돌아옵니다. 사용할 수 있는 도로만 이용해 순회 길이를 최소화합니다. 순회가 낮에 이루어지는지 밤에 이루어지는지는 알 수 없습니다.

오른쪽 그림의 예에서 건물 A, D, F에 사무실을 열면 낮의 순회 길이는 6이고 밤의 순회 길이는 10입니다.

계획을 단순하게 하려고 낮과 밤의 최소 순회 길이가 같아지도록 사무실 건물을 고릅니다. 이 조건을 만족하는 사무실 건물 선택 방법의 수를 구하세요. 한쪽 선택에만 들어 있는 건물이 하나라도 있으면 두 선택은 다른 것으로 봅니다. 방법의 수가 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구합니다. 사무실 수의 제한은 입력 형식을 참고하세요.

첫째 줄에 정수 $N$, $M$, $T$가 주어집니다. $T$는 열 사무실의 정확한 개수입니다. 다만 $T = 1$이면 사무실을 몇 개든 열 수 있고, 최소 두 개는 열어야 합니다.

다음 $N$개 줄에는 공백 없이 $M$개의 문자가 주어집니다. $(i+1)$번째 줄의 $j$번째 문자는 위에서 $i$번째, 왼쪽에서 $j$번째 건물의 밤 도로를 나타내며 다음 중 하나입니다.

• 0: 이 건물에서 위쪽이나 왼쪽으로 이어지는 도로가 없습니다.
• 1: 이 건물에서 바로 위 건물로 이어지는 도로가 있습니다.
• 2: 이 건물에서 바로 왼쪽 건물로 이어지는 도로가 있습니다.
• 3: 이 건물에서 바로 위 건물과 바로 왼쪽 건물로 이어지는 도로가 모두 있습니다.

도로는 정확히 $N \times M - 1$개이며 트리를 이룹니다.

방법의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력합니다.

• $1 \le T \le 3$
• $1 \le N, M \le 1\,000$