16550번 - Odd Colouring 다국어

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 (X_j, Y_j). 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.

Line 1 contains four integers R, C, N, M (1 ≤ R, C, N ≤ 2²⁹; R + C ≤ N; 1 ≤ M ≤ 2¹⁶).

Line 2 contains M integers X₁, . . . , X_M (0 ≤ X_j < R).

Line 3 contains M integers Y₁, . . . , Y_M (0 ≤ Y_j < C).

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

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).