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