Problem Background

In Guangzhou, there are skilled football players. During the Football Association Cup, two football fields were set up in the northeastern corner of the campus. The players, $n$ in number, stand on the field with one ball, two goals, and three referees. The audience sits in groups. Shortly after, a whistle blows on the field, and the entire audience falls silent, not daring to make a sound.

At this moment, the sounds of passing, gentle winds, players running fast, coaches shouting, cheerleaders cheering, all erupt simultaneously, showcasing the full array of wonders. The entire audience stretches their necks, glances sideways, smiles, and silently marvels, thinking it marvelous.

Not long after, one of our players makes a long pass, which the opposing player intercepts and charges towards our goal.

But see the goalkeeper oql standing at the goal, seemingly lost in thought—

Problem Description

It turns out he is pondering this problem:

The $n$ players on the field form a circle, numbered from $1$ to $n$, with the ball initially in the hands of player $1$. There are $m$ passes in total, each pass must be made to another player, but not back to oneself. The question is to find the number of ways the ball can be passed back to player $1$ after $m$ passes.

However, he finds this problem too simple, so he adds $k$ restrictions, each in the form of $a, b$, indicating that player $a$ cannot pass the ball to player $b$.

To divert oql's attention back to the game, you need to quickly tell him the number of valid ways to pass the ball back to player $1$ after $m$ passes.

You only need to tell him the result modulo $998244353$.

Input Format

The input data includes $k+1$ lines:

The first line contains three integers $n, m, k$, representing the number of players, the number of passes, and the number of restrictions, respectively.

The next $k$ lines each contain two integers $a_i, b_i$, indicating that player $a_i$ cannot pass the ball to player $b_i$.

The data guarantees that there will not be different $i, j$ such that $a_i = a_j$ and $b_i = b_j$.

Output Format

Output a single integer, which is the number of valid ways to pass the ball back to player $1$ after $m$ passes, modulo $998244353$.

Sample Input and Output

Sample Input #1

2 1 0

Sample Output #1

0

Sample Input #2

3 3 0

Sample Output #2

2

Sample Input #3

7 13 5
1 3
4 5
5 4
6 1
2 2

Sample Output #3

443723615

Notes

For $10\%$ of the data, $k = 0$.

For another $15\%$ of the data, $n \leq 500$.

For another $20\%$ of the data, $n \leq 5 \times 10^4$.

For another $20\%$ of the data, $k \leq 300$.

For $100\%$ of the data, $1 \leq n \leq 10^9$, $0 \leq m \leq 200$, $0 \leq k \leq \min(n \times (n-1), 5 \times 10^4)$, $1 \leq a_i, b_i \leq n$, not guaranteed that $a_i, b_i$ are not equal.

见题面 Input 部分

见题面 Output 部分