There is a deck of cards. There are $n$ types of cards, labeled $1, 2, \dots, n$, with $C$ cards of each type. Thus, there are $nC$ cards in total.

Three consecutive cards $(i, i+1, i+2)$ or three identical cards $(i, i, i)$ can form a set. A collection of cards is called a winning hand if it can be partitioned into several (possibly zero) sets.

You have drawn some initial cards from the deck. Now you want to pick some additional cards to form a winning hand. How many possible winning hands can you form? Output the answer modulo $998244353$.

Two collections of cards are considered the same if and only if they contain the same number of each type of card.

Input

The first line contains two integers $n$ and $C$, representing the number of card types and the number of cards of each type, respectively.

The second line contains an integer $X$, representing the number of types of cards you initially have.

The next $X$ lines each contain two integers $k_i$ and $a_i$, representing that you have $a_i$ cards of type $k_i$. The $k_i$ values are given in increasing order.

Output

Output a single non-negative integer representing the answer, modulo $998244353$.

Examples

Input 1

3 3
0

Output 1

10

Note 1

The possible winning hands are:

1. $\{\}$ (no cards selected)
2. $\{1,1,1\}$
3. $\{2,2,2\}$
4. $\{3,3,3\}$
5. $\{1,2,3\}$
6. $\{1,1,1,2,2,2\}$
7. $\{1,1,1,3,3,3\}$
8. $\{2,2,2,3,3,3\}$
9. $\{1,1,2,2,3,3\}$
10. $\{1,1,1,2,2,2,3,3,3\}$

Input 2

9 4
9
1 3
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 3

Output 2

3521

Subtasks

For all data, $1\le n\le 10^{18}, 0\le a_i\le C\le 1000, 0\le X\le 1000$. Note that $a_i$ and $C$ may be $0$.

• For $20\%$ of the data, $n=9, C=4$;
• For another $15\%$ of the data, $n\le 10^5, C = 2$;
• For another $15\%$ of the data, $X\le 5, C \le 10$;
• For another $10\%$ of the data, $X=0$;
• For another $20\%$ of the data, $n\le 10^5$;
• For the remaining $20\%$ of the data, there are no special restrictions.