羽毛
题号：NC208061
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Madeline逃离了镜之寺庙之后，决定与Badeline交谈。Madeline决定不再需要Badeline，并让Madeline自由。Badeline害怕被抛弃，抓住了Madeline并使其焦虑症发作。Madeline试图臆想出一根羽毛让自己平静下来，但是她失败了。Madeline与Badeline一同跌落到一个深水洞穴中。那根羽毛则在空中自由飘动。

为了简化模型，将这个地图分为个点，以及条带权单向边。这个羽毛在第秒时在点，则这根羽毛在第秒时会随机选择点的一条出边到达点，如果点没有出边则这根羽毛就就留在点。

可能会有重边或者自环。

在第秒的时候羽毛会等概率地出现在这个点的任意一个点，现在Madeline想知道羽毛在前秒间走过的边权之和的期望是多少。

结果对（质数）取模。保证答案是有理数。如果你的答案是，那么你需要输出的答案ans满足。

输入描述:

第一行为三个整数。

接下来行，每行三个整数，表示存在一条从到且边权为的有向边。

输出描述:

输出答案对取模的结果。
示例1

输入

复制 
2 2 1
1 1 1
1 2 1

输出

复制 
9630409

说明

第{0}秒时羽毛出现在点{1}时，走过的边权之和只能为{1}。
第{0}秒时羽毛出现在点{2}时，走过的边权之和只能为{0}。
答案即\frac{(1+0)}{2}=\frac{1}{2}。