该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

开题报告

时间限制：2000ms

空间限制：1024MB

题目背景

对大多数老师的学生而言，开题报告只是一个形式上的过场，但 $Z$ 老师的学生并非如此。 $Z$ 老师认为，开题报告是学生阶段性成果的展现，如果还没有完成 $50$% 的课题内容，就是进度缓慢的。因此他要求，学生的开题报告应该逻辑清晰、内容丰富，最好内容比别的同学的论文正文都要多。

在改完期末试卷后， $Z$ 老师决定开始检查学生们的开题报告，每天检查一份。（事实上，这非常罕见。一般来说，他会拖到报告 $ddl$ 的前两天晚上，才跟他的学生们讲解（他的）开题报告的基本要求。尽管时间紧迫，但他的要求并不会降低）。

$Z$ 老师检查学生开题报告的顺序服从均匀分布，并且会在检查的前一天晚上通知该同学。而每名同学会选取一个同学作为参照（由于有的人比较懒惰，可能选自己作为参照），如果他的开题报告字数大于自己的字数，那么他就会在那天晚上快马加鞭，多写一段，以应对检查。

题目描述

$Z$ 老师共有 $n$ 名学生，编号 $1-n$ 。 最开始，第 $i$ 名学生写了 $a_i$ 字的初稿，并选取一名同学 $b_i$ 作为参照。如果在即将检查时，第 $i$ 名学生发现第 $b_i$ 名学生的字数比自己多，那么他就会补写 $w_i$ 字。 $Z$ 老师会以均匀分布的概率选择一个次序，逐个检查每个学生的开题报告。 各位学生想要知道，自己最终会写的开题报告字数的期望是多少，请你帮帮他们。

显然，每个学生的字数期望可以用一个有理数 $\frac{x}{y}$ 表示，请输出这个有理数在 $10^9+7$ 下取模的结果。

输入格式

每组数据包含多个测试用例。第一行包含一个整数 $t(1≤t ≤ 5\times10^5)$ ，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n(1 ≤ n ≤ 5⋅10^5)$ ，表示学生的数量。 第二行包含 $n$ 个整数 $a_i(1 ≤ a_i ≤ 10^9)$ ，表示每个学生开题报告初稿的字数。 第三行包含 $n$ 个整数 $b_i(1 ≤ b_i ≤ n)$ ，表示每个学生的参考对象。 第四行包含 $n$ 个整数 $w_i(1 ≤ w_i ≤ 10^9)$ ，表示每个学生（如果需要补写）会补写的字数。 保证所有测试用例中 $n$ 的总和不超过 $5\times10^5$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，代表每名学生开题报告的期望字数，并对结果在 $10^9 + 7$ 下取模。

样例输入

4
4
2 5 5 2
4 2 1 3
3 2 1 4
3
5 4 3
1 1 1
6 6 6
3
5 4 3
2 3 1
1 2 3
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4

样例输出

500000007 5 5 6 
5 10 9 
166666673 5 6 
500000006 4 3 4 5