在你的帮助下,跳蚤国王发现把小队排列成理想情况是不可能的,于是他放弃了让小队重新排列的计划,直接下令强攻实验室。
在经过一番血战之后,跳蚤军队成功攻克了实验室中的大部分区域并把 picks 博士与他的猴子们逼入了最后一间房间中——同时也是存储了绝大部分资料和研究成果的最重要的房间。
这间房间的建造利用了跳蚤夸克神奇的力量,因此跳蚤国王发现强行闯入房间是不可能的,而唯一的入口——房间正门却被一个密码锁锁住了。
在这个密码锁上画了一张
经过一番探索,跳蚤国王发现这个密码锁的密码等于这样一个问题的答案:
密码锁上给出了一张
跳蚤国王发现这个问题并不是非常简单,于是他让你——这附近最著名的民间科学家来帮他计算这个问题的答案。
输入格式
第一行两个正整数
接下来的
输出格式
输出期望值对
样例一
input
2 1 1 2 4096
output
200000000
explanation
图中只有一条边,有
样例二
input
3 3 1 2 4000 2 3 6000 1 3 3000
output
296883784
explanation
图中有三条边,定向概率均已给出,容易发现有
样例三
input
6 15 1 2 10000 1 3 0 1 4 10000 1 5 10000 1 6 10000 2 3 10000 2 4 10000 2 5 10000 2 6 10000 3 4 10000 3 5 10000 3 6 10000 4 5 10000 4 6 0 5 6 10000
output
500494593
explanation
可以发现定向的图是固定的,只有
样例四
input
4 0
output
99696143
explanation
注意没有输入的边的两个方向的定向概率均为
样例五
input
5 4 1 5 10000 1 4 10000 1 3 10000 1 2 10000
output
985337417
explanation
容易看出期望强连通分量数是前一个图的期望强连通分量数加1,但是题目求的是强连通分量数乘以
样例六
input
4 4 1 2 4194 1 3 9971 2 4 7191 1 4 1102
output
433654756
样例七
input
13 7 1 2 3 4 5 6 7 8 9 10 11 12 1 13 15 3 4 18 5 6 21
output
940436965
限制与约定
子任务 | 分值 | 限制与约定 | |
---|---|---|---|
1 | 19 | ||
2 | 23 | ||
3 | 7 | ||
4 | 24 | ||
5 | 27 |
对于所有数据,
对每一个
对于
时间限制:
空间限制: