[ABC372] F - Teleporting Takahashi 2

F - Teleporting Takahashi 2

Time Limit: 3 sec / Memory Limit: 1024 MB

分数: 525 分

题面

有一个简单的有向图，有个顶点和条边。这些顶点从到编号，边从到编号。

边从顶点指向顶点。（这里，顶点被视为顶点。）
边 从顶点指向顶点。

高桥位于顶点。在每个顶点，他可以移动到当前顶点存在出边的任意顶点。

计算他正好移动次的方式数量。

也就是找到长度为的整数序列，满足以下三个条件：

• 对于，。
• 。
• 对于，顶点到顶点存在一条有向边。

由于这个数量可能非常大，输出对取模的结果。

限制条件

• ，
• 所有的条有向边都是不同的。
• 所有的输入值都为整数。

---

输入

输入从标准输入中按以下格式给出：

输出

输出结果对取模。

---

输入样例 1

6 2 5
1 4
2 5

输出样例 1

5

上图表示了图。高桥有五种移动方式：

• 顶点 顶点 顶点 顶点 顶点 顶点
• 顶点 顶点 顶点 顶点 顶点 顶点
• 顶点 顶点 顶点 顶点 顶点 顶点
• 顶点 顶点 顶点 顶点 顶点 顶点
• 顶点 顶点 顶点 顶点 顶点 顶点

---

输入样例 2

10 0 200000

输出样例 2

1

---

输入样例 3

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

输出样例 3

451022766