홀수 색칠

시간 제한1초메모리 제한256 MB

요약

색칠 결과가 각 행과 열의 검은 공 개수를 홀수로 만들도록 칠하는 방법 수를 세어서 998244353로 나눈 값을 구합니다.

난이도: 어려움10점 중 9점
유형: 수학, 조합론, 비트 연산, 그래프
정답자: 아직 제출이 없습니다

문제

R개의 행과 C개의 열로 이루어진 격자가 있다. 행은 0부터 R − 1까지, 열은 0부터 C − 1까지 번호가 매겨져 있다. r번째 행과 c번째 열에 있는 칸을 (r, c)로 나타내자. Troy는 격자에 N(N ≥ R + C)개의 공을 넣는다. i번째 공은 ((i − 1) mod R, (i − 1) mod C)번 칸에 들어간다. Ondrej는 격자에 M개의 공을 넣는다. j번째 공은 (Xj, Yj)번 칸에 들어간다. 같은 칸에 여러 개의 공이 들어갈 수도 있다.

모든 공은 검은색 또는 흰색으로 칠해진다. 모든 행과 모든 열에 검은 공이 홀수 개 있도록 공을 칠하는 방법의 수를 구하시오. 방법의 수를 998244353으로 나눈 나머지를 구하시오.

입력

첫째 줄에 네 정수 R, C, N, M이 주어진다. (1 ≤ R, C, N ≤ 2^29, R + C ≤ N, 1 ≤ M ≤ 2^16)

둘째 줄에 M개의 정수 X1, ..., XM이 주어진다. (0 ≤ Xj < R)

셋째 줄에 M개의 정수 Y1, ..., YM이 주어진다. (0 ≤ Yj < C)

출력

방법의 수를 한 줄에 하나의 정수로 출력한다.

힌트

첫 번째 예제에서 Troy는 (0, 0), (1, 1), (0, 2), (1, 3), (0, 0), (1, 1)에 공을 넣었고, Ondrej는 (1, 3), (1, 0)에 공을 넣었다.

예제3

예제 1
입력
```
2 4 6 2
1 1
3 0
```
예상 출력
```
8
```
예제 2
입력
```
6 4 50 5
0 1 2 3 4
3 3 3 3 3
```
예상 출력
```
503245988
```
예제 3
입력
```
2 4 6 2
1 0
3 2
```
예상 출력
```
0
```