Түбірі $1$-ші төбе болатын $n$ төбеден тұратын ағашты қарастырайық. Ағаштағы әрбір $i$ төбесінің $p_i$ салмағы бар, мұндағы $p_1, p_2, \dots, p_n$ — алмастыру.
$L_{u,v}$ арқылы $u$ төбесінен $v$ төбесіне дейінгі қарапайым жолдың бойындағы ($u$ мен $v$-ны қоса алғанда) кез келген төбенің ең үлкен салмағын белгілейік. Ал $\operatorname{subtree}(i)$ арқылы $i$ төбесінің ішкі ағашын құрайтын төбелер жиынын белгілейік. Біз $S_i = \{u \mid u \in \operatorname{subtree}(i) \land L_{u,i} \le p_i\}$ жиынын анықтаймыз — бұл $i$ төбесінен бастап, тек ұрпақ (бала) төбелерге өту арқылы және салмағы $p_i$-ден аспайтын төбелер арқылы ғана жетуге болатын төбелер жиыны. Осы төбелер жиынының өлшемін $f_i = |S_i|$ деп белгілейік.
Төбенің мәнін $q_{f_i}$ деп анықтаймыз, мұндағы $q$ — берілген $q_1, q_2, \dots, q_n$ мәндер тізбегі.
Енді әрбір $(i, j)$ жұбы үшін $p_i = j$ шартын қанағаттандыратын барлық салмақ конфигурациялары бойынша $i$ төбесінің мәндерінің қосындысын есептегіміз келеді. Жауап өте үлкен болуы мүмкін болғандықтан, нәтижені $10^9 + 7$ модулі бойынша шығарыңыз.
Кіріс деректер
Бірінші жолда ағаштағы төбелер санын білдіретін бір бүтін сан $n$ ($1 \le n \le 700$) берілген.
Келесі жолда $q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$) мәндерін білдіретін $n$ бүтін сан берілген.
Келесі $n - 1$ жолдың әрқайсысында ағаштағы қырды білдіретін екі бүтін сан $u, v$ берілген.
Шығыс деректер
Әрқайсысы $n$ бүтін саннан тұратын $n$ жол шығарыңыз. $i$-ші жолдағы $j$-ші бүтін сан сәйкес жауапты $10^9 + 7$ модулі бойынша білдіреді.
Мысалдар
Кіріс деректер 1
3 1 1 2 1 2 2 3
Шығыс деректер 1
2 2 4 2 2 2 2 2 2
Кіріс деректер 2
4 1 2 3 4 1 2 2 3 1 4
Шығыс деректер 2
6 10 16 24 6 8 10 12 6 6 6 6 6 6 6 6
Кіріс деректер 3
7 3 7 2 4 1 8 9 1 2 1 3 2 4 4 5 3 6 4 7
Шығыс деректер 3
2160 3120 3168 2952 2160 3720 6480 2160 2640 2640 2412 2208 2280 2880 2160 2640 3120 3600 4080 4560 5040 2160 3120 3648 3744 3408 2640 1440 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160 2160