Counting Valid Rectangles

An n × m rectangular grid is drawn by plotting all integer points with coordinates \((x,y)\) where \(x \in [0,n]\) and \(y \in [0,m]\) and connecting any two points whose Euclidean distance is 1. This forms a grid having \(n\) rows and \(m\) columns of unit squares.

You are to count the number of axis‐aligned rectangles (whose four sides are parallel to the coordinate axes) that can be drawn using the grid lines such that:

• The perimeter of the rectangle is at most \(k\) (i.e. \(2((x_2-x_1)+(y_2-y_1)) \le k\) in \(\LaTeX\) form, where \(x_1,x_2\) and \(y_1,y_2\) are the grid line coordinates chosen with \(x_1<x_2\) and \(y_1<y_2\)).
• The rectangle does not contain any obstacle unit square inside it. There are \(q\) obstacles. Each obstacle is a \(1\times 1\) square whose bottom-left corner is given. A rectangle is said to contain an obstacle if it completely covers the obstacle unit square. In other words, if a rectangle is determined by grid lines \(x=x_1\) and \(x=x_2\), and \(y=y_1\) and \(y=y_2\), then an obstacle with bottom-left coordinate \((a, b)\) (and top-right \((a+1, b+1)\)) is contained if \(x_1 \le a\) and \(a+1 \le x_2\) and \(y_1 \le b\) and \(b+1 \le y_2\).

Output the number of such rectangles modulo \(998244353\).

inputFormat

The first line of input contains four integers \(n\), \(m\), \(k\), and \(q\) \( (1 \leq n, m \leq \text{small constraints},\ k \geq 4, \ q \ge 0)\). Here, \(n\) and \(m\) indicate the dimensions of the grid (the grid has \(n\) rows and \(m\) columns of unit cells), \(k\) is the maximum allowed perimeter, and \(q\) is the number of obstacles.

Each of the next \(q\) lines contains two integers \(a\) and \(b\) \( (0 \le a < n,\ 0 \le b < m)\) representing the bottom-left coordinate of an obstacle unit square.

outputFormat

Output a single integer, the number of valid rectangles modulo \(998244353\).

sample

1 1 4 0

1