小 Q 与树
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小 Q 在纸上画树,画着画着,小 Q 在纸上画出了一棵  个点, 条边的树,其中他给第  个点都赋了一个点权 ,每条边的距离为

他想要知道


对  取模后的值。

输入描述:

第一行一个整数 ,表示点的个数。               
接下来 个整数,其中第  个整数表示 。       
最后  行,每行两个整数 ,表示节点  与节点  之间有一条无向边。

输出描述:

一行一个整数,表示答案。
示例1

输入

复制
5
3 2 4 6 5
1 2
2 3
2 4
4 5

输出

复制
112