题目描述

场上有 $n$ 名球员围成一圈，编号从 $1$ 到 $n$，球初始在 $1$ 号球员手中。一共进行 $m$ 次传球，每次传球必须传给一个人，但不能传到自己手中。求第 $m$ 次传球后球传回 $1$ 号球员的方案数。

此外，有 $k$ 条限制，每条限制形如 $a, b$，表示 $a$ 号球员不能将球传给 $b$ 号球员。

请你计算合法方案数，结果对 $998244353$ 取模。

输入格式

输入数据包括 $k+1$ 行：

第一行三个整数 $n, m, k$，分别表示球员数、传球次数、限制条数。

接下来 $k$ 行，每行两个整数 $a_i, b_i$，表示 $a_i$ 号球员不能将球传给 $b_i$ 号球员。

数据保证不会出现不同的 $i, j$ 使得 $a_i = a_j$ 且 $b_i = b_j$。

输出格式

输出一个整数，表示 $m$ 轮后传回 $1$ 号球员的合法方案数对 $998244353$ 取模后的结果。

样例

2 1 0

0

3 3 0

2

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

443723615

提示

对于 $10\%$ 的数据，$k = 0$。

对于另外 $15\%$ 的数据，$n \le 500$。

对于另外 $20\%$ 的数据，$n \le 5 \times 10^4$。

对于另外 $20\%$ 的数据，$k \le 300$。

对于 $100\%$ 的数据，$1 \le n \le 10^9$，$0 \le m \le 200$，$0 \le k \le \min(n \times (n-1), 5 \times 10^4)$，$1 \le a_i, b_i \le n$，不保证 $a_i, b_i$ 不相等。