#P17781. 千早爱音不是罪过
千早爱音不是罪过
背景
『即使失败一次,也得相信自己还能重新开始;不然人生这么长,会撑不住哦。』
『 一起在迷失之中前进吧!』
题目描述
爱音喜欢「描绘未来」。
她将未来的事件想象成了一棵带点权有根树,事件 为根,事件 的权值为 。
爱音想要给每个事件确定一个发生顺序,具体地,事件 的发生顺序必须为 ,其余事件的发生顺序应大于其父亲的发生顺序,所有事件的发生顺序互不相同且均为 内的整数。
如果一个点的发生顺序恰为其父亲的发生顺序加一,称这两个事件是紧密相连的。只保留紧密相连的树边,会得到若干个连通块,爱音认为每个连通块的权值是其内所有点权的异或和,而这个发生顺序设计方案的价值是所有连通块的权值乘积。
爱音想知道所有合法发生顺序设计方案的价值和,请你帮她求出该值,对 取模。
输入格式
第一行输入 。
第二行输入 个数,第 个数为 。
接下来输入 行,每行两个数 表示存在树边 。
输出格式
输出一行一个整数表示答案。
4
0 9 0 8
1 2
2 3
2 4
72
9
1 2 3 4 5 6 7 8 9
1 2
1 3
2 4
3 5
2 6
6 7
6 8
1 9
190486596
提示
【数据范围】
对所有数据,满足 。
【样例解释 #1】
两种合法的发生顺序设计方式及其价值分别为:
- ,两个连通块为 ,价值为 。
- ,两个连通块为 ,价值为 。
总价值为 。
看来已经不需要我了吧。