You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

羊城有善蹴鞠者。会足协之杯，于校园之东北角，施两球场，蹴鞠者站球场中，$n$ 人，一球，二门，三裁判而已。观众团坐。少倾，但闻球场中哨声一响，满坐寂然，无敢哗者。

当是时，传球声，微微风声，队员疾跑声，教练呼喊声，拉拉队助威声，一时齐发，众妙毕备。满场观众无不伸颈，侧目，微笑，默叹，以为妙绝。

未几，我球员施一长传，彼球员截之，望我龙门冲来。

但见守门员 oql 立于门，若有所思——

题目描述

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

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

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

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

你只需要告诉他答案对 $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\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$ 不相等。