Background

In Yangcheng, there are people who are good at playing cuju. During the Football Association Cup, at the northeast corner of the campus, two fields are set up. The cuju players stand in the field: $n$ people, one ball, two goals, three referees, that is all. The audience sits around. After a while, as soon as the whistle on the field blows, everyone becomes silent, and no one dares to make noise.

At that moment, the sound of passing, the faint sound of wind, the sound of players sprinting, the coach shouting, and the cheerleaders cheering all burst out together, and every wonderful sound is present. The whole audience stretches their necks, looks sideways, smiles, and sighs silently, thinking it is amazing.

Soon, one of our players makes a long pass. Their player intercepts it and charges toward our goal.

Then we see the goalkeeper oql standing at the goal, as if thinking about something.

Problem Description

It turns out he is thinking about this problem:

There are $n$ players standing in a circle, numbered from $1$ to $n$. At the beginning, the ball is in the hands of player $1$. There are $m$ passes in total. In each pass, the ball must be passed to someone, but it cannot be passed to oneself. Find the number of ways such that after the $m$-th pass, the ball is passed back to player $1$.

But he thinks this problem is too easy, so he adds $k$ restrictions. Each restriction is of the form $a,b$, meaning that player $a$ cannot pass the ball to player $b$.

To bring oql’s attention back to the match as soon as possible, you need to tell him this number of ways in the shortest time.

You only need to output the result modulo $998244353$.

Input Format

The input consists of $k+1$ lines:

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

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 do not exist different $i,j$ such that $a_i=a_j$ and $b_i=b_j$.

Output Format

Output one integer, representing the number of valid ways for the ball to return to player $1$ after $m$ passes, modulo $998244353$.

2 1 0

0

3 3 0

2

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

443723615

Hint

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$, it is not guaranteed that $a_i$ and $b_i$ are different.

Translated by ChatGPT 5