Description

原来他在想这么一个问题：

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

但他觉得这个问题太简单了，于是加了 $k$ 条限制，每条限制形如 $a,b$，表示 $a$ 号球员不能将球传给 $b$ 号球员。

为了使得 oql 的注意力转移回球场上，你需要在最短的时间内告诉他这个方案数是多少。

你只需要告诉他答案对 $998244353$ 取模后的结果。

Input Format

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

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

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

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

Output Format

输出一个整数，表示 $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

Hint

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

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

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

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

对于 $100\%$ 的数据，$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$，不保证 $a_i,b_i$ 不相等。