#P3610. [Heoi2014]林中路径
[Heoi2014]林中路径
[HEOI2014] 林中路径
题目描述
Alice 和 Marisa 都住在一个巨大的由 个路口与 条单向小道构成的森林中。Marisa 非常喜欢到 Alice 家里去玩,但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察, 因此每当她发现 Marisa 走了一条与之前完全相同的路径来到她家时,她就会装作不在家, Marisa 就只好败兴而归。Marisa 发现了这个秘密,因此她决定每次走不同的路径到 Alice 家。
Marisa 体力有限,她不想走超过 条边到达 Alice 家,并且,每当她走 ()条边 到达 Alice 家时,她需要付出 的体力。Marisa 想知道,在 Alice 无论如何都不想接见她之前(即 Marisa 无法走一条长度不超过 的与之前不同的路径),她走完所有这些不同的路径,总共会消耗多少体力。
现在 Marisa 拿到了一张森林的地图,但因为 Marisa 非常笨,她并不知道自己的家和 Alice 的家在哪一个路口,因此她会询问你 次,每次询问假如 Marisa 的家的位置在 而 Alice 的家的位置在 时的答案。
一条长度为 的路径由依次经过的 条有向边组成,前一条边的终点须是后一条边的起点。路径允许重复经过任意路口,也允许重复经过同一条边。长度为 的路径停留在起点。
两条路径完全相同,当且仅当它们经过的边数相等,且每个位置经过的边编号均相同。连接同一对路口的不同边仍各有自己的编号。
输入格式
输入数据第一行包含四个整数 , , , ,含义如题所述。
接下来 行,每行两个整数 , ,表示从第 个路口到第 个路口有一条单向小道。路口的标号为 ,输入中第 条小道的编号为 。
接下来 行,每行两个整数 和 ,含义如题所述。
输出格式
对于每个询问,输出一行,表示这次询问的答案。由于 Marisa 接受不了非常大的数, 你只需要输出答案模 的值。
样例 #1
2 0 1 1
1 2
0
样例 #2
2 2 2 1
1 2
2 1
1 1
4
样例 #3
2 2 100 1
1 2
2 1
1 2
166650
样例 #4
2 3 100 2
1 2
1 2
2 1
2 2
2 1
632506153
518794755
数据范围
对于 的数据,,,,。
对于 的数据,,,,。
对于 的数据,,,,。
对于 的数据,,,,,。
样例解释
样例 1 中,从 到 不存在合法路径。
样例 2 中,Marisa 可以重复经过一个路口,即使这个路口是 Alice 的家或她自己的家。