Sugar Sweet II

설탕은 달다.

$n$명의 아이가 설탕을 달라고 하고 있다. Chen 교수가 아이들에게 설탕을 나눠 준다. $i$번째 아이는 처음에 설탕을 $a_i$개 가지고 있다.

$n$개의 사건이 균일하게 무작위로 정해진 순서로 일어난다. $i$번째 사건은 다음과 같다.

• $i$번째 아이가 $b_i$번째 아이보다 설탕을 엄격히 적게 가지고 있으면, $i$번째 아이는 설탕을 $w_i$개 더 받는다. 그렇지 않으면 아무 일도 일어나지 않는다.

사건이 무작위 순서로 일어나므로, Chen 교수의 조수 Randias는 모든 사건이 끝난 뒤 각 아이가 가진 설탕 개수의 기댓값을 알고 싶어 한다.

답은 기약분수 $\frac{x}{y}$로 나타낼 수 있다. 여기서 $x$와 $y$는 정수이고 $y \not\equiv 0 \pmod{10^9+7}$이다. $x \cdot y^{-1} \bmod (10^9+7)$의 값을 출력한다. 즉 $0 \le a < 10^9+7$이고 $a \cdot y \equiv x \pmod{10^9+7}$를 만족하는 정수 $a$를 출력한다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 5 \cdot 10^5$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 아이의 수 $n$ ($1 \le n \le 5 \cdot 10^5$)이 주어진다. 둘째 줄에 $a_i$ ($1 \le a_i \le 10^9$)가 $n$개 주어진다. 셋째 줄에 $b_i$ ($1 \le b_i \le n$)가 $n$개 주어진다. 넷째 줄에 $w_i$ ($1 \le w_i \le 10^9$)가 $n$개 주어진다.

모든 테스트 케이스의 $n$의 합은 $5 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 한 줄에 $n$개의 정수를 출력한다. 각 아이가 마지막에 가지게 될 설탕 개수의 기댓값을 위에서 설명한 대로 $10^9+7$로 나눈 나머지로 출력한다.