물류

세계적으로 유명한 공업 회사 Universal Manufacturing이 최근 사업을 확장하기로 했다. 이 회사는 램프부터 트랙터까지 많은 종류의 제품을 만들며, 원료에서 완제품까지 생산 과정 전체를 자사 공장에서 처리한다.

회사에는 $N$개의 공장이 있으며 $1 \ldots N$까지 번호가 매겨져 있다. 1번 공장은 본사 공장이다. 공장들은 $N-1$개의 도로로 연결되어 있고, 본사 공장에서 이 도로들을 따라 모든 공장에 갈 수 있다고 알려져 있다.

공장 $i$에는 등급 $T_i$가 있다. 이 공장은 다른 공장에 공급할 등급 $T_i$의 부품을 만들 수 있고, 같은 등급의 완제품도 만들 수 있다. 공장은 더 낮은 등급의 부품을 입력으로 쓸 수 있지만, 만들어 낸 부품이나 제품의 등급은 항상 $T_i$이다.

회사는 $M$개의 매장을 열었다. 매장 $i$는 공장 $C_i$에 있으며, 등급이 $L_i$부터 $R_i$까지인 제품을 판매할 수 있다. 각 제품은 공장의 열 $(j_1, j_2, \ldots, j_c)$을 거친다. 기초 부품은 공장 $j_1$에서 만들어 공장 $j_2$로 보내고, 공장 $j_2$에서 더 높은 등급의 부품을 만든다. 이런 식으로 공장 $j_c$까지 이어지며, 공장 $j_c$에서 완제품을 만들어 매장으로 운송한다. 기초 부품은 항상 본사 공장에서 만들므로 $j_1 = 1$이다. 각 공장은 등급이 더 낮은 부품만 가공할 수 있으므로, 모든 $1 \le i < c$에 대해 $T_{j_i} < T_{j_{i+1}}$이 성립해야 한다.

운송은 생산 과정에서 가장 비싼 부분이다. 제품 하나를 만드는 동안에는 부품으로든 완제품으로든 어떤 공장도 두 번 이상 지나갈 수 없다. 그 공장에서 제품을 가공하지 않는 경우에도 마찬가지다. 어떤 매장에서도 팔 수 없는 제품은 판매되지 않는다.

첫째 줄에 공장 수 $N$ ($1 \le N \le 10^5$)이 주어진다. 둘째 줄에는 정수 $P_1, \ldots, P_N$ ($1 \le P_i < i$)이 주어진다. $P_i$는 공장 $i$와 공장 $P_i$ 사이에 도로가 있다는 뜻이다. 예외로 $P_1 = 0$이며, 이 경우 도로는 없다. 셋째 줄에는 공장의 등급 $T_1, \ldots, T_N$ ($0 \le T_i < N$)이 주어진다. $T_1 = 0$이고 모든 $T_i$는 서로 다르다. 넷째 줄에는 매장 수 $M$ ($1 \le M \le 10^5$)이 주어진다. 마지막 $M$개 줄에는 각각 정수 $C_i$, $L_i$, $R_i$ ($1 \le C_i \le N$, $0 \le L_i \le R_i < N$)가 주어지며, 매장 $i$가 공장 $C_i$에 있고 등급이 $L_i$부터 $R_i$까지인 제품을 판매할 수 있다는 뜻이다.

각 매장 $i$에 대해, 그 매장에서 판매할 수 있는 제품들의 모든 생산 과정에 해당하는 공장 열의 총 개수를 한 줄에 하나씩 출력한다. 이 값은 매우 클 수 있으므로, 실제 값 대신 $10^9+7$로 나눈 나머지를 출력한다.