3238. 传递秘密

【题目描述】

2020年到了，SY国走了许多人，也来了许多新人。为了让新人尽快融入团体，SY国全体人员玩了一把游戏。

游戏的规则是：所有人围成一个圈，按1，2，3···n编号，先由1号同学分享一个他的秘密给一个人（比如他分享给了3号），再由被分享的那个人（即3号）再分享给另外一个人。

求出1号经过m次传递后收到他分享出去的秘密的方案数。答案对998244353取模。

一次只能分享给一个人。

秘密不能分享给自己。

秘密可以连续在两个人之间分享。（就是说1号分享给3号，3号再分享给1号，这种情况是合法的）

到此为止这道题很简单，直到我们发现参与其中的某些人是单相思关系（ 但是也有些人是没有喜欢的人 ）。。。

众所周知，人们不想让自己喜欢的人知道自己的秘密，所以一个人可能会分享给其他所有人（除了他喜欢的人）。

一个人可能喜欢多个人。（别吐槽我）

【输入格式】

第一行三个整数n，m，k。代表参与的人数，传递次数和喜欢关系的个数。 接下来k行，给出单相思名单（ai，bi）（表示ai喜欢bi）。

【输出格式】

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

【样例输入】

2 1 0

【样例输出】

0

【样例输入2】

3 3 0

【样例输出2】

2

【样例输入3】

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

【样例输出3】

443723615

【提示】

对于 100%的数据：1≤n≤10^9，0≤m≤1000，0≤k≤min⁡(n×(n−1),5×10^4)1≤ai,bi≤n，不保证 ai,bi 不相等（意思就是自恋）。