Problem Description

There is a deck of cards. The cards are categorized into $n$ types, labeled as $1, 2, ..., n$, with each type having $C$ cards. Therefore, the deck contains a total of $nC$ cards.

Three consecutive cards $(i, i+1, i+2)$ or three identical cards $(i, i, i)$ can form a pile. A set of cards is considered a royal set if it can be divided into several (including zero) piles.

You have drawn some initial cards from the deck. Now, you want to select some cards to form a royal set. How many possible royal sets can be formed? The answer should be taken modulo $998244353$.

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

Input Format

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

The second line contains an integer $X$, representing the number of initial card types.

The next $X$ lines each contain two integers $k_i$ and $a_i$, indicating that there are $a_i$ cards of type $k_i$ in the initial set. The $k_i$ values are given in increasing order.

Output Format

Output one line containing one natural number, representing the answer modulo $998244353$.

Sample Input and Output

Input Sample #1

3 3
0

Output Sample #1

10

Input Sample #2

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

Output Sample #2

3521

Notes

Sample Explanation 1

All possible schemes 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\}$

Data Range

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

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

见题面 Input 部分

见题面 Output 部分