Description

There is a deck of cards. There are $n$ types of cards, labeled $1,2,\ldots,n$, and each type has $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 set. If a multiset of cards can be divided into several (possibly zero) sets, then it is called a winning hand.

You have drawn some initial cards from the deck. Now you want to pick some cards to form a winning hand. How many different winning hands can you form? Output the answer modulo $998244353$. That is, based on the initial cards, you may select some additional cards (or select none).

Two groups of cards are considered the same if and only if, for every card type, the quantities of that type in the two groups are the same.

Input Format

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

The second line contains one integer $X$, representing the number of types present in the initial cards.

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

Output Format

Output one line with one non-negative integer, the answer modulo $998244353$.

3 3
0

10

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

3521

Hint

Sample Explanation 1

All valid choices are as follows:

1. $\{\}$ (choose no cards)
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\}$

Constraints

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

• For $20\%$ of the data, $n=9$ and $C=4$.
• For another $15\%$ of the data, $n\leq 10^5$ and $C=2$.
• For another $15\%$ of the data, $X\leq 5$ and $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, there are no special restrictions.

Translated by ChatGPT 5