32991번 - 폭죽놀이

레헬른의 가장 큰 볼거리는 단연 폭죽놀이다. 레헬른의 루시드는 폭죽놀이의 성공적인 마무리를 위해 고민하고 있다.

루시드는 하늘에서 폭죽이 터질 $N$개의 지점을 미리 정해 두었다. 각 지점에는 1번부터 $N$번까지 번호가 붙어 있다. 또한 각 지점을 잇는 $N-1$개의 경로가 존재하여, 임의의 두 지점을 경로만을 따라 이동할 수 있다. 즉 지점들은 1번 지점을 루트로 하는 트리 구조로 볼 수 있다.

각 폭죽은 터질 때 주위 온도에 영향을 미치며, 그 범위는 다음의 두 종류 중 하나이다.

1. 폭죽이 터진 지점과 거리가 1 이하인 모든 정점
2. 폭죽이 터진 지점을 루트로 하는 서브트리 내의 모든 정점

각 폭죽에는 고유한 값 ($A$, $B$)가 있어 폭죽이 영향을 미치는 범위에 있는 지점의 온도가 원래 $x$였다면, 폭죽이 터진 뒤의 온도는 $Ax+B$가 된다.

루시드는 폭죽놀이가 진행될 때 원하는 지점의 온도를 실시간으로 확인할 수 있는 프로그램을 원한다. 다른 축제 준비로 너무 바쁜 루시드를 위해 프로그램을 작성해 보자. 프로그램은 다음 쿼리를 처리할 수 있어야 한다.

• 1 v a b: $v$번 지점에서 1번 종류의 폭죽이 터진다. 폭죽의 고유한 값은 ($a$, $b$)이다.
• 2 v a b: $v$번 지점에서 2번 종류의 폭죽이 터진다. 폭죽의 고유한 값은 ($a$, $b$)이다.
• 3 v: $v$번 지점의 현재 온도를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

첫 번째 줄에 지점의 개수 $N$이 주어진다.

두 번째 줄에 각 지점의 초기 온도 $x_1, x_2, \cdots , x_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $2$번 지점부터 $N$번 지점까지의 부모의 번호 $p_2, p_3, \cdots , p_N$이 공백으로 구분되어 주어진다.

네 번째 줄에 쿼리의 개수 $Q$가 주어진다.

그다음 줄부터 $Q$개 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 쿼리의 형식은 지문을 참고하여라.

주어지는 모든 입력은 정수이다.

3번 쿼리가 주어질 때마다 쿼리에서 묻는 지점의 온도를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 하나씩 출력하여라.

• $2 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $0 \le x_i < 1\,000\,000\,007$ ($1 \le i \le N$)
• $1 \le p_i \le N$ ($2 \le i \le N$)
• $1 \le v \le N$
• $0 \le a, b < 1\,000\,000\,007$
• 주어지는 지점들의 구조는 트리 구조이다.
• 3번 쿼리는 최소 1회 주어진다.