Odd Colouring

Time limit1sMemory limit256 MB

Summary

Count black/white ball colorings under cycle-index and Hadamard identities with large R, C, N, returning the count modulo 998244353.

Level: Hard9 of 10
Topics: Math, Combinatorics, Bit manipulation, Graph
Solved: No attempts yet

Problem

There is a grid with R rows and C columns. Rows are numbered 0 to R − 1 and columns are numbered 0 to C − 1. Let the cell at row r and column c be denoted as (r, c). Troy will add N(N ≥ R + C) balls to the grid; the i-th ball will be added to cell ((i − 1) mod R, (i − 1) mod C). Ondrej will add M balls to the grid; the j-th ball will be added to cell (Xj, Yj). Multiple balls may be added to the same cell.

Every ball will be painted either black or white. Determine the number of ways to paint the balls such that every row and every column has an odd number of black balls. Compute the number of ways modulo 998244353.

Input

Line 1 contains four integers R, C, N, M (1 ≤ R, C, N ≤ 2^29; R + C ≤ N; 1 ≤ M ≤ 2^16).

Line 2 contains M integers X1, ..., XM (0 ≤ Xj < R).

Line 3 contains M integers Y1, ..., YM (0 ≤ Yj < C).

Output

Print one line with one integer, the number of ways.

Hint

For the first example, Troy added balls to (0, 0), (1, 1), (0, 2), (1, 3), (0, 0), (1, 1) and Ondrej added balls to (1, 3), (1, 0).

Examples3

Example 1
Input
```
2 4 6 2
1 1
3 0
```
Expected output
```
8
```
Example 2
Input
```
6 4 50 5
0 1 2 3 4
3 3 3 3 3
```
Expected output
```
503245988
```
Example 3
Input
```
2 4 6 2
1 0
3 2
```
Expected output
```
0
```