Sponge

Interview

Time limit1sMemory limit1024 MB

Summary

Given K labeled viruses on a W by H grid that each move one king step or stay each second, count the distinct placements possible after T seconds modulo 998244353.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

The sponge is a grid with $W$ cells across and $H$ cells down. It is divided into $1 \times 1$ cells, and holes in various places let viruses move through it.

Every second, a virus can move to one of the 8 neighboring cells (up, down, left, right, or diagonally) without leaving the sponge, or it can stay in its current cell. Several viruses can occupy the same cell. Their shapes differ, so they can be told apart.

raa was watching the viruses and wondered how many distinct virus distributions are possible after $T$ seconds. Two distributions differ if the position of any virus differs. Help raa count them.

Input

The first line contains the width $W$ , the height $H$ , the number of viruses $K$ , and the time $T$ that raa observes the viruses, separated by spaces. ( $1 \leq W, H, K \leq 10^6$ , $0 \leq T \leq 10^6$ )

The next $K$ lines give the current positions of the viruses. Line $i+1$ contains two integers $x_i$ and $y_i$ , separated by a space. This means virus $i$ is in the cell that is $x_i$ cells from the left and $y_i$ cells from the top of the sponge. ( $1 \leq x_i \leq W$ , $1 \leq y_i \leq H$ )

All numbers in the input are integers.

Output

Print the number of distinct virus distributions possible after $T$ seconds. The count can be very large, so print it modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
7 6 1 2
3 3
```
Expected output
```
25
```
Example 2
Input
```
5 4 2 1
3 3
1 4
```
Expected output
```
36
```