描述

给出一棵以点1为根的树，N个点，点有点权
求各个点子树点权和模\(10^9\)+7的值

输入

第一行：一个正整数N
第二行：N个数V_1、V_2、...、V_N为各点点权
第三行：N-1个数F_2、F_3、...、F_N为各点父节点(1<=F_i<i)

输出

N行
输出1至N各点子树点权和

样例1

输入

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

输出

21
20
18
15
11
6

范围

20% 1<=N<=10
50% 1<=N<=1000
90% 1<=N<=\(10^5\)
100% 1<=N<=\(10^7\) 1<=V_i<=\(10^7\)

限制

前9个点 1000ms
第10个点 3000ms
128M