希望大家一直记得我。
“希望大家永远忘了我。”
小 Y 有一个
小 Y 预见到岁月将会磨灭图
- 有
的概率同时存在 向 和 向 的有向边,它们的边权均为 ; - 有
的概率存在 向 、边权为 的有向边,而不存在其反向边; - 有
的概率存在 向 、边权为 的有向边,而不存在其反向边; - 有
的概率 和 之间没有边。
所有
小 Y 认为一个无向图的核心是最小生成树,而一个有向图的核心是最小外向生成树。称图
小 Y 希望图的核心历经岁月侵蚀也保持不变,于是他想知道,有多大的概率,图
你需要将答案对
输入格式
本题有多组测试数据。输入的第一行两个整数
对于每组测试数据,第一行两个整数
输出格式
对于每组测试数据,输出一行一个整数,表示图
样例 1
input
0 2 2 1 1 2 1 3 3 1 2 2 1 3 2 2 3 2
output
750000006 171875002
explanation
该组样例共有 2 组测试数据。
- 对于第一组测试数据,由于图上只有一条边,因此只要
上有边, 的最小外向生成树边权和就一定等于 的最小生成树边权和。 上存在边的概率为 ,故答案为 ,取模后的结果为 。 - 对于第二组测试数据,在所有
种 中,有 13 种情况不满足 的最小外向生成树边权和等于 的最小生成树边权和: 为空图; 仅包含一条有向边,共 6 种情况; 仅包含两条有向边,且指向同一个节点,共 3 种情况; 仅包含两条有向边,且构成一个二元环,共 3 种情况。
由于所有情况等概率出现,因此答案为
【样例 2】
见选手目录下的 years/years2.in
与 years/years2.ans
。
该组样例共有 5 组测试数据。其中每组测试数据分别满足测试点
【样例 3】
见选手目录下的 years/years3.in
与 years/years3.ans
。
该组样例共有 5 组测试数据。其中每组测试数据分别满足测试点
子任务
对于所有测试点,
, , , , , , , ,即 没有重边,- 保证
连通。
测试点编号 | 特殊性质 | |
---|---|---|
A | ||
B | ||
C | ||
C | ||
C | ||
C | ||
无 | ||
无 | ||
无 | ||
无 |
- 特殊性质 A:
, , 。 - 特殊性质 B:
, 。 - 特殊性质 C:
, 。