题号：NC52801
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld
题目描述
Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。
为了方便，点用
编号。
设)
表示点 x 到点 y 不同的路径数量（规定 %20%3D%200)
），Bobo 想知道
%20%5Ccdot%20a_i%20%5Ccdot%20b_j)
除以)
的余数。
其中，
是给定的数列。
为了方便，点用
设
除以
其中，
输入描述:
输入包含不超过 15 组数据。
每组数据的第一行包含两个整数 n, m ().
接下来 n 行的第 i 行包含两个整数(
).
最后 m 行的第 i 行包含两个整数，代表一条从点
到
的边 (
)。
输出描述:
对于每组数据，输出一个整数表示要求的值。