A regular icosahedron has $20$ faces, $12$ vertices, and $30$ edges. The following is a diagram.

Qiai has a regular icosahedron, and she cuts each face into $n^2$ congruent equilateral triangles using $3n-3$ cuts. For example, the figure below shows the case for $n=2$.

Now, this regular icosahedron has a total of $20n^2$ small triangles. Qiai has $k$ colors. She wants to color these triangles such that $a_i$ triangles are colored with the $i$-th color.

Furthermore, even for the same color, the prices of the pigments differ. For the $i$-th color, there is one pigment available for each price $0, 1, \dots, b_i$. A pigment with price $c$ means that it costs $c$ units of money to color one triangle with it. For the same color, one can use pigments of different prices in the coloring scheme arbitrarily.

Qiai has a budget of $m$ units of money, so she wants to know, for each $0 \le j \le m$, how many ways there are to spend exactly $j$ units of money.

Two coloring schemes are considered the same if one can be transformed into the other by rotating the regular icosahedron. Note: Since Qiai is a professional, she can distinguish the prices of the pigments used on each triangle.

Input

The first line contains three positive integers $n, m, k$.

The next $k$ lines each contain two integers $a_i, b_i$.

Output

Output a single integer. Let $f(j)$ be the number of ways to spend $j$ units of money. You only need to output:

$$ \bigoplus_{j=0}^m ((f(j) \bmod 998244353) + j) $$

Examples

Examples 1 Input

1 100 1
20 1

Examples 1 Output

3554

Note 1

The data before decoding is:

$$ f(0,\dots,10) = [1, 1, 6, 21, 96, 262, 681, 1302, 2157, 2806, 3158] $$

Also, $f(j)=f(20-j)$, and $f(j)=0$ for $j>20$.

Examples 2 Input

1 100 2
9 3
11 2

Examples 2 Output

870

Examples 3 Input

2 100 2
36 3
44 2

Examples 3 Output

788814413

Examples 4 Input

2 100000 2
36 233
44 666

Examples 4 Output

953441426

Constraints

For $100\%$ of the data, it is guaranteed that:

• $1\le n\le 7\times 10^3$
• $0\le m\le 5\times 10^6$
• $1\le k\le 5$
• $1\le a_i$
• $\sum_i a_i = 20n^2$
• $0\le b_i\le m$