#P18356. Under the Epilogue
Under the Epilogue
Under the Epilogue
输入:标准输入
输出:标准输出
题目描述
有 个位置,编号为 。位置 有两个参数 ,满足 。每次位于 时,可以移动到任意满足 的位置 。
你可以任选一个位置 作为起点,移动任意多步后回到 。也可以一步都不移动,直接停在 。
令 为这次从 出发并回到 的过程中,至少经过一次的所有位置组成的集合。起点也属于 。位置和边都允许重复经过。
求总共可以得到多少个不同的集合 ,答案对 取模。只按集合是否相同计数;起点、移动顺序或移动次数不同,但集合相同的,只计一次。
输入格式
第一行包含一个整数 。
接下来 行,第 行包含两个整数 。
输出格式
输出一行一个整数,表示不同集合 的数量对 取模的结果。
数据范围
- ;
- 对于所有 ,。
本题只有一个测试用例,没有测试用例数 。
样例输入 1
5
1 2
2 5
3 4
2 5
4 5
样例输出 1
12