E. Jsteyki
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kantipa wants to make a board game that takes place on a grid. The grid is an $$$N\times N$$$ grid with $$$N$$$ rows and $$$N$$$ columns. The rows are numbered from $$$1$$$ to $$$N$$$ from top to bottom and the columns are numbered from $$$1$$$ to $$$N$$$ from left to right. The tile in row $$$x$$$ and column $$$y$$$ is denoted as $$$(x, y)$$$. There are $$$D$$$ special tiles with the $$$i$$$-th special tile being tile $$$(R_i, C_i)$$$. It's guaranteed that the special tiles are pairwise distinct.

In each level of the game, there's a start tile and a goal tile. The player has one game piece that's initially located in the start tile in the beginning of the level. A piece in tile $$$(x, y)$$$ can do one of the following five moves:

  • Move to $$$(x-1, y)$$$. This takes $$$1$$$ second.
  • Move to $$$(x, y-1)$$$. This takes $$$1$$$ second.
  • Move to $$$(x+1, y)$$$. This takes $$$1$$$ second.
  • Move to $$$(x, y+1)$$$. This takes $$$1$$$ second.
  • Move to $$$(x', y')$$$ such that $$$(x', y') \neq (x, y)$$$ and one of the following is satisfied:
    • $$$x'+y' = x+y$$$
    • $$$x'-y' = x-y$$$
    (Or in other words, this move is exactly the same as a move for a chess bishop. This takes $$$0$$$ seconds.)

Note that in a move, the piece cannot go outside the grid. A level ends once the player's piece lands on the goal tile. Since the bishop move is very overpowered, each level limits the maximum number of times the player can do the bishop move in that level.

To make an entire board game, Kantipa must make a sequence of exactly $$$K$$$ levels. The sequence of levels can be represented as three arrays $$$S$$$, $$$G$$$, and $$$L$$$, each with length $$$K$$$, such that $$$1\leq S_j,G_j\leq D$$$ and $$$0\leq L_j\leq B$$$ (the constant $$$B$$$ is given). These three arrays signify a sequence of levels where in the $$$j$$$-th level, the start tile is the $$$S_j$$$-th special tile, the goal tile is the $$$G_j$$$-th special tile, and the maximum number of times the player can do the bishop move is $$$L_j$$$.

The sequence of levels must follow the following restrictions:

  • For each level, the start tile must be different from the goal tile ($$$S_j\neq G_j$$$ must hold).
  • The minimum amount of time to complete each of the $$$K$$$ levels in the sequence must be strictly increasing.

Note that a special tile can be used as a start tile or a goal tile multiple times, if used in different levels.

Find the number of different valid sequences of levels. Since the number can be very large, print it modulo $$$998\,244\,353$$$.

Two sequences of levels are said to be different if and only if at least one of $$$S$$$, $$$G$$$, or $$$L$$$ in both sequences are different.

Input

The first line contains four integers $$$N$$$, $$$D$$$, $$$K$$$, and $$$B$$$ ($$$1 \leq N \leq 100\,000$$$; $$$1 \leq D \leq \min(100\,000,N^2)$$$; $$$1 \leq K,B \leq 100\,000$$$) — the size of the board, the number of special tiles, the number of levels in a valid sequence, and the maximum limit for the value of $$$L_j$$$.

The $$$i$$$-th of the next $$$D$$$ lines contains two integers $$$R_i$$$ and $$$C_i$$$ ($$$1\leq R_i,C_i\leq N$$$) — the location of each special tile. The special tiles are pairwise distinct.

Output

An integer representing the number of different valid sequences of levels modulo $$$998\,244\,353$$$.

Examples
Input
5 4 5 2
3 4
1 1
4 1
3 3
Output
15168
Input
2 2 2 2
1 1
2 2
Output
8
Note

In the first example, an example of a valid sequence of levels is $$$S = [2, 3, 3, 3, 2]$$$, $$$G = [4, 2, 1, 2, 1]$$$, $$$L = [1, 2, 1, 1, 0]$$$. Each level of this game is described as follows:

  1. In the $$$1$$$-st level, the start tile is $$$(1, 1)$$$, the goal tile is $$$(3, 3)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(1, 1)$$$, bishop move to $$$(3, 3)$$$. This takes $$$0$$$ seconds.
  2. In the $$$2$$$-nd level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(1, 1)$$$, the bishop move limit is $$$2$$$. A way to get the minimum time is from $$$(4, 1)$$$, bishop move to $$$(2, 3)$$$, move to $$$(2, 2)$$$, bishop move to $$$(1, 1)$$$. This takes $$$1$$$ second.
  3. In the $$$3$$$-rd level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(3, 4)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(4, 1)$$$, move to $$$(5, 1)$$$, bishop move to $$$(2, 4)$$$, move to $$$(3, 4)$$$. This takes $$$2$$$ seconds.
  4. In the $$$4$$$-th level, the start tile is $$$(4, 1)$$$, the goal tile is $$$(1, 1)$$$, the bishop move limit is $$$1$$$. A way to get the minimum time is from $$$(4, 1)$$$, move to $$$(3, 1)$$$, move to $$$(2, 1)$$$, move to $$$(1, 1)$$$. This takes $$$3$$$ seconds.
  5. In the $$$5$$$-th level, the start tile is $$$(1, 1)$$$, the goal tile is $$$(3, 4)$$$, the bishop move limit is $$$0$$$. A way to get the minimum time is from $$$(1, 1)$$$, move to $$$(1, 2)$$$, move to $$$(2, 2)$$$, move to $$$(3, 2)$$$, move to $$$(3, 3)$$$, move to $$$(3, 4)$$$. This takes $$$5$$$ seconds.

Notice that the minimum amount of time to complete each level is strictly increasing. Since this meets all requirements, this is a valid sequence of levels.

In the second example, the following is every possible sequence of levels that's valid:

  • $$$S=[1,1]$$$, $$$G=[2,2]$$$, $$$L=[1,0]$$$
  • $$$S=[1,1]$$$, $$$G=[2,2]$$$, $$$L=[2,0]$$$
  • $$$S=[1,2]$$$, $$$G=[2,1]$$$, $$$L=[1,0]$$$
  • $$$S=[1,2]$$$, $$$G=[2,1]$$$, $$$L=[2,0]$$$
  • $$$S=[2,1]$$$, $$$G=[1,2]$$$, $$$L=[1,0]$$$
  • $$$S=[2,1]$$$, $$$G=[1,2]$$$, $$$L=[2,0]$$$
  • $$$S=[2,2]$$$, $$$G=[1,1]$$$, $$$L=[1,0]$$$
  • $$$S=[2,2]$$$, $$$G=[1,1]$$$, $$$L=[2,0]$$$