#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<auto&operator<<(ostream&o,pairp){return o<<"{"<auto&operator<<(ostream&o,sets){for(auto&e:s)o< auto&operator<<(ostream&o,priority_queueq){while(!q.empty())o<auto&operator<<(ostream&o,mapm){for(auto&e:m)o<auto&operator<<(ostream&o,vectorv){for(auto&e:v)o<void ashow(T t,A...a){cout< P; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector

vp; typedef vector vd; typedef vector vs; const int MAX_N = 200005; template class BSTNode { public: int from, to, sz; _Tp value, al, lazy; BSTNode *left, *right, *par; BSTNode(int _from, int _to) noexcept : from(_from), to(_to), sz(1), value(id1), al(id2), lazy(id1), left(nullptr), right(nullptr), par(nullptr){} static const _Tp id1 = (_Tp)0; static const _Tp id2 = (_Tp)0; static void opr1(_Tp& arg1, const _Tp arg2){ arg1 += arg2; } static _Tp opr2(const _Tp arg1, const _Tp arg2){ return arg1 + arg2; } inline bool isRoot() const { return !par; } inline bool isVertex() const noexcept { return from == to; } void push(){ if(lazy != id1){ opr1(value, lazy), al += lazy * sz; if(left) opr1(left->lazy, lazy); if(right) opr1(right->lazy, lazy); lazy = id1; } } void eval(){ sz = 1, al = value; if(left) left->push(), sz += left->sz, al = opr2(left->al, al); if(right) right->push(), sz += right->sz, al = opr2(al, right->al); } void rotate(bool right_){ BSTNode *p = par, *g = p->par; if(right_){ if((p->left = right)) right->par = p; right = p, p->par = this; }else{ if((p->right = left)) left->par = p; left = p, p->par = this; } p->eval(), eval(); if(!(par = g)) return; if(g->left == p) g->left = this; if(g->right == p) g->right = this; g->eval(); } }; template BSTNode<_Tp>* splay(BSTNode<_Tp> *u) noexcept { if(!u) return nullptr; while(!(u->isRoot())){ BSTNode<_Tp> *p = u->par, *gp = p->par; if(p->isRoot()){ // zig p->push(), u->push(); u->rotate((u == p->left)); }else{ gp->push(), p->push(), u->push(); bool flag = (u == p->left); if((u == p->left) == (p == gp->left)){ // zig-zig p->rotate(flag), u->rotate(flag); }else{ // zig-zag u->rotate(flag), u->rotate(!flag); } } } u->push(); return u; } template BSTNode<_Tp>* join(BSTNode<_Tp> *root1, BSTNode<_Tp> *root2) noexcept { if(!root1 || !root2) return root1 ? root1 : root2; BSTNode<_Tp> *cur = nullptr, *nx = root1; do{ cur = nx, cur->push(), nx = cur->right; }while(nx); BSTNode<_Tp> *ver = splay(cur); ver->right = root2, ver->eval(), root2->par = ver; return ver; } template pair*, BSTNode<_Tp>*> split_lower_bond(BSTNode<_Tp> *ver) noexcept { BSTNode<_Tp> *res = splay(ver)->left; ver->left = nullptr, ver->eval(); if(res) res->par = nullptr; return make_pair(res, ver); } template pair*, BSTNode<_Tp>*> split_upper_bond(BSTNode<_Tp> *ver) noexcept { BSTNode<_Tp> *res = splay(ver)->right; ver->right = nullptr, ver->eval(); if(res) res->par = nullptr; return make_pair(ver, res); } template class EulerTourTree { private: struct edge { int from, to; edge(){} edge(int _from, int _to) : from(_from), to(_to){} bool operator<(const edge& val) const { return (from == val.from) ? (to < val.to) : (from < val.from); } }; void reroot(BSTNode *ver){ BSTNode *res = splay(ver)->left; if(!res) return; while(ver->right) ver->push(), ver = ver->right; ver->right = res, ver->eval(), res->par = ver, splay(res); } void link(BSTNode *ver1, BSTNode *ver2){ reroot(ver1), reroot(ver2); BSTNode* e1 = new BSTNode(ver1->from, ver2->from); BSTNode* e2 = new BSTNode(ver2->from, ver1->from); edge_set[(edge){ver1->from, ver2->from}] = e1; edge_set[(edge){ver2->from, ver1->from}] = e2; join(join(ver1, e1), join(ver2, e2)); } void cut(BSTNode *edge1, BSTNode *edge2){ splay(edge1), splay(edge2); BSTNode *p = edge1->par; if(p != edge2) p->par = nullptr, edge1->rotate((edge1 == p->left)); if(edge1->left) edge1->left->par = nullptr; if(edge1->right) edge1->right->par = nullptr; if(edge1 == edge2->left){ if(edge2->right) edge2->right->par = nullptr; join(edge1->left, edge2->right); }else{ if(edge2->left) edge2->left->par = nullptr; join(edge2->left, edge1->right); } delete edge1; delete edge2; } bool isConnected(BSTNode *ver1, BSTNode *ver2){ splay(ver1), splay(ver2); return ver1->par; } T& get(BSTNode *ver){ return splay(ver)->value; } void range(BSTNode *edge1, BSTNode *edge2, const T& val){ auto res1 = split_lower_bond(edge1); auto res2 = split_upper_bond(edge2); BSTNode::opr1(res2.first->lazy, val); join(join(res1.first,res2.first), res2.second); } T query(BSTNode *edge1, BSTNode *edge2){ auto res1 = split_lower_bond(edge1); auto res2 = split_upper_bond(edge2); T res = res2.first->al; return join(join(res1.first,res2.first), res2.second), res; } public: int V; BSTNode** vertex_set; map*> edge_set; EulerTourTree(const int node_size) noexcept : V(node_size){ vertex_set = new BSTNode*[V]; for(int i = 0; i < V; i++) vertex_set[i] = new BSTNode(i, i); } void reroot(const int node_id) noexcept { reroot(vertex_set[node_id]); } void link(const int node1_id, const int node2_id) noexcept { link(vertex_set[node1_id], vertex_set[node2_id]); } void cut(const int node1_id, const int node2_id){ auto it1 = edge_set.find((edge){node1_id, node2_id}); auto it2 = edge_set.find((edge){node2_id, node1_id}); assert(it1 != edge_set.end()); cut(it1->se, it2->se); } bool isConnected(const int node1_id, const int node2_id) noexcept { return isConnected(vertex_set[node1_id], vertex_set[node2_id]);} T& get(int ver_id){ return get(vertex_set[ver_id]); } void component_range(int ver_id, const T& val) noexcept { range(ver_id, -1, val); } void range(int ver_id, int par_id, const T& val) noexcept { if(par_id < 0) return BSTNode::opr1(splay(vertex_set[ver_id])->lazy, val); auto it1 = edge_set.find((edge){par_id, ver_id}); auto it2 = edge_set.find((edge){ver_id, par_id}); assert(it1 != edge_set.end()); range(it1->se, it2->se, val); } T component_query(int ver_id) noexcept { return query(ver_id, -1); } T query(int ver_id, int par_id) noexcept { if(par_id < 0) return splay(vertex_set[ver_id])->al; auto it1 = edge_set.find((edge){par_id, ver_id}); auto it2 = edge_set.find((edge){ver_id, par_id}); assert(it1 != edge_set.end()); return query(it1->se, it2->se); } vector > G; vector parent; EulerTourTree(const int node_size, bool _build) noexcept : V(node_size), G(V), parent(V){ vertex_set = new BSTNode*[V]; for(int i = 0; i < V; i++) vertex_set[i] = new BSTNode(i, i); } void add_edge(int u, int v){ G[u].push_back(v), G[v].push_back(u); } BSTNode* dfs(int u, int p, BSTNode *cur){ parent[u] = p; cur = join(cur, vertex_set[u]); for(auto& v : G[u]){ if(v != p){ BSTNode* e1 = new BSTNode(u, v); edge_set[(edge){u, v}] = e1; cur = join(cur, e1); cur = dfs(v, u, cur); BSTNode* e2 = new BSTNode(v, u); edge_set[(edge){v, u}] = e2; cur = join(cur, e2); } } return cur; } vector build(int _root){ BSTNode *cur = nullptr; dfs(_root, -1, cur); return parent; } }; int r[MAX_N]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n){ cin >> r[i]; } EulerTourTree et(n, true); rep(i,n-1){ int u, v; cin >> u >> v; et.add_edge(u-1, v-1); } auto par = et.build(0); rrep(i,n){ et.component_range(i, 1); for(auto& to : et.G[i]) if(to < i) et.cut(to, i); } int ans = 1; rep(i,n){ ans = (ll)ans * (et.get(i) + r[i]) % MOD; } cout << ans << "\n"; return 0; }