#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 node { public: using KT = KeyType; using VT = ValueType; KT key; VT value, lazy; node *left, *right, *par; node(KT _key, VT _value) : key(_key), value(_value), lazy(id1), left(nullptr), right(nullptr), par(nullptr){} static const VT id1 = (VT)0; static const VT id2 = (VT)0; void opr1(VT& arg1, const VT arg2) const { arg1 += arg2; } VT opr2(const VT arg1, const VT arg2) const { return arg1 + arg2; } bool isRoot() const { return !par; } void push(){ if(lazy != id1){ opr1(value, lazy); if(left) opr1(left->lazy, lazy); if(right) opr1(right->lazy, lazy); lazy = id1; } } void eval(){ if(left) left->push(); if(right) right->push(); } void rotate(bool _right){ node *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 node* splay(node* u){ if(!u) return nullptr; while(!(u->isRoot())){ node *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 pair*, bool> find(const KT _key, node* root){ node *cur = nullptr, *nx = root; while(nx){ cur = nx, cur->push(); if(cur->key == _key) break; if(cur->key > _key) nx = cur->left; else nx = cur->right; } return make_pair(splay(cur), cur && cur->key == _key); } template pair*, bool> lower_bound(const KT _key, node* root){ node *cur = nullptr, *nx = root, *res = nullptr; while(nx){ cur = nx, cur->push(); if(cur->key >= _key){ nx = cur->left; if(!res || cur->key <= res->key) res = cur; }else nx = cur->right; } node* tmp = splay(cur); return res ? make_pair(splay(res), res) : make_pair(tmp, res); } template pair*, bool> upper_bound(const KT _key, node* root){ node *cur = nullptr, *nx = root, *res = nullptr; while(nx){ cur = nx, cur->push(); if(cur->key > _key){ nx = cur->left; if(!res || cur->key <= res->key) res = cur; }else nx = cur->right; } node* tmp = splay(cur); return res ? make_pair(splay(res), res) : make_pair(tmp, res); } template node* join(node* root1, node* root2){ if(!root1 || !root2) return root1 ? root1 : root2; node *cur = nullptr, *nx = root1; while(nx){ cur = nx, cur->push(), nx = cur->right; } node* ver = splay(cur); ver->right = root2, ver->eval(), root2->par = ver; return ver; } template node* insert(node* ver, node* root){ if(!root) return ver; node *cur = nullptr, *nx = root; while(nx){ cur = nx, cur->push(); if(cur->key > ver->key) nx = cur->left; else nx = cur->right; } if(cur->key > ver->key) cur->left = ver, ver->par = cur; else cur->right = ver, ver->par = cur; cur->eval(); return splay(ver); } template pair*, bool> erase(const KT _key, node* root){ pair*, bool> ver = find(_key, root); if(!ver.second) return ver; return make_pair(join(ver.first->left, ver.first->right), true); } template node* merge(node* root1, node* root2){ if(!root2) return root1; return insert(root2, root1); } template pair*, node*> split(const KT _key, node* root){ node *res1 = nullptr, *res2 = lower_bound(_key, root); if(res2) res1 = res2->left, res2->left = nullptr, res2->eval(); else return make_pair(root, nullptr); if(res1) res1->par = nullptr; return make_pair(res1, res2); } template node* range(KT lvalue, KT rvalue, VT x, node* root){ auto pnn1 = split(lvalue, root); auto pnn2 = split(rvalue, pnn1.second); if(pnn2.first) opr1(pnn2.first->lazy, x); return join(pnn1.first, join(pnn2.first, pnn2.second)); } template pair*, VT> query(KT lvalue, KT rvalue, node* root){ auto pnn1 = split(lvalue, root); auto pnn2 = split(rvalue, pnn1.second); VT res = (pnn2.first ? pnn2.first->al : node::id2); return make_pair(join(pnn1.first, join(pnn2.first, pnn2.second)), res); } vector G[MAX_N]; int ans[MAX_N]; node* ptr[MAX_N]; void dfs(node* cur) { cur->push(); ans[cur->key] += cur->value; if(cur->left) dfs(cur->left); if(cur->right) dfs(cur->right); } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n){ cin >> ans[i]; } rep(i,n-1){ int u, v; cin >> u >> v; if(u > v) swap(u, v); G[v-1].pb(u-1); } rep(i,n){ ptr[i] = new node(i, 1); each(v,G[i]){ splay(ptr[v]), ptr[v]->lazy += 1; merge(ptr[v], ptr[i]); } } dfs(ptr[n-1]); int ret = 1; rep(i,n){ ret = (ll)ret * ans[i] % MOD; } cout << ret << "\n"; return 0; }