表示言語
/ /分数: 100 点
问题陈述
Cenix 想要填写 N \times M 网格使用以下六种类型的方形瓷砖。每种类型的瓷砖都有很多,并且可以在放置前旋转它们。放置图块时,连接到路径的每条边必须接触到连接到相邻图块上的路径的边。然而,并非所有路径都需要连接。

在填充网格时,Cenix 意识到这个任务太简单了。 Cenix 现在打算仅使用连接一侧的图块和连接三侧的图块来填充剩余的单元格。

一个网格,其中一些单元格已经填充了图块,如下所示。
- 放置在的图块类型 i第行和 j网格的第列表示为 A_{i,j}.
- 如果该单元格中没有放置图块, A_{i,j} is -1.
- 如果在该单元格中放置了一个图块, A_{i,j} 是总和 1 (如果图块连接到顶部边缘), 2 (如果连接到底部边缘), 4 (如果连接到左边缘),以及 8 (如果连接到右边缘)。
找出仅使用这两种类型的图块来填充剩余单元格的方法数。
约束
- 1 \le N, M \le 500\,000
- 1 \le NM \le 500\,000
- -1 \le A_{i,j} \le 15
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
输出
输出填充网格的方式数,取模 998\,244\,353.
样本输入 1
3 3 10 -1 6 -1 -1 -1 9 -1 -1
示例输出 1
2

示例输入 2
1 3 -1 -1 -1
示例输出 2
0
示例输入 3
5 5 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 3 0 3 0 0 -1 0 -1
示例输出 3
2
表示言語
/ /점수 : 100 점
문제
세닉스는 다음 6종류의 정사각형 타일을 이용해 N \times M 크기의 격자판을 채우려 한다. 각 타일은 충분히 많으며 회전해서 놓을 수 있다. 타일을 놓을 때는 길이 연결된 모든 변이 이웃한 타일의 길이 연결된 변과 맞닿아야 한다. 모든 길이 하나로 연결될 필요는 없다.

세닉스는 격자판을 채우다가 격자판을 채우는 게 너무 쉽다는 생각이 들었다. 세닉스는 남은 칸을 한 변에 길이 연결된 타일과 세 변에 길이 연결된 타일만을 이용해 전부 채우려 한다.

일부 칸을 타일로 채운 격자판이 다음과 같이 주어진다.
- 격자판의 위에서부터 i번째, 왼쪽에서부터 j번째 칸에 놓인 타일의 종류는 A_{i,j}다.
- 해당 칸에 타일이 놓여 있지 않다면 A_{i,j}는 -1이다.
- 해당 칸에 타일이 놓여 있다면 A_{i,j}는 그 타일의 윗변에 길이 연결된 경우 1, 아랫변에 길이 연결된 경우 2, 왼변에 길이 연결된 경우 4, 오른변에 길이 연결된 경우 8을 모두 더한 값이다.
남은 칸을 두 종류의 타일로 모두 채우는 방법의 수를 구해 보자.
제한
- 1 \le N, M \le 500\,000
- 1 \le NM \le 500\,000
- -1 \le A_{i,j} \le 15
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
출력
격자판을 채우는 방법의 수를 998\,244\,353으로 나눈 나머지를 출력한다.
입력 예 1
3 3 10 -1 6 -1 -1 -1 9 -1 -1
출력 예 1
2

입력 예 2
1 3 -1 -1 -1
출력 예 2
0
입력 예 3
5 5 -1 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 3 0 3 0 0 -1 0 -1
출력 예 3
2