阿里是哈米德的弟弟,明天是他的生日。哈米德希望他的兄弟能够赢得他的礼物,所以他给了他一个困难的编程问题,并告诉他如果他能成功解决它,他会给他一台全新的笔记本电脑。 Ali 还不是像 Hamed 那样非常有才华的程序员,虽然他通常不会作弊,但这一次是个例外。这是关于一台全新的笔记本电脑。于是他决定偷偷向你寻求帮助。请阿里解决这个问题。
给出了一个 n 顶点加权有根树。 1 号顶点是树的根。我们将 d(u, v) 定义为顶点 u 和 v 之间的最短路径上的边权重之和。具体来说,我们定义 d(u, u) = 0。另外,我们将每个顶点 v 的 S(v) 定义为包含所有顶点 u 的集合,使得 d(1, u) = d(1, v) + d(v, u)。然后使用以下公式定义函数 f(u, v):
$$f(u,v) = \sum_{x \in S(v)} d(u,x)^2 - \sum_{x \notin S(v)} d(u,x)^2$$
目标是计算给定的 q 个顶点对中的每一个的 f(u, v)。由于答案可能相当大,因此打印它对 109 + 7 取模就足够了。
输入
在第一行输入一个整数n (1 ≤ n ≤ 105),给出了树的顶点数。
在接下来的 n - 1 行中,每一行给出三个空格分隔的整数 ai、bi、ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109),指示 ai 和 bi 之间的边,权重等于 ci。
在下一行中,给出了整数 q (1 ≤ q ≤ 105),即顶点对的数量。
在接下来的 q 行中,每一行给出两个空格分隔的整数 ui, vi (1 ≤ ui, vi ≤ n),这意味着您必须计算 f(ui, vi)。
保证给定的边形成一棵树。
输出
输出 q 行。在第 i 行中打印 f(ui, vi) 模 109 + 7 的值。
示例
输入 #1
5 1 2 1 4 3 1 3 5 1 1 3 1 5 1 1 1 5 2 4 2 1 3 5
输出 #1
10 1000000005 1000000002 23 1000000002
输入 #2
8 1 2 100 1 3 20 2 4 2 2 5 1 3 6 1 3 7 2 6 8 5 6 1 8 2 3 5 8 2 6 4 7 6 1
输出 #2
999968753 49796 999961271 999991235 999958569 45130