#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: int id; T val, lazy; node *left, *right, *par; node(int key, int value) : id(key), val(value), lazy(0), left(nullptr), right(nullptr), par(nullptr){} bool isRoot(){ return !par; } void push(){ if(lazy){ val += lazy; if(left) left->lazy += lazy; if(right) right->lazy += lazy; lazy = 0; } } 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; } if(!(par = g)) return; if(g->left == p) g->left = this; if(g->right == p) g->right = this; } }; template node* splay(node* u){ 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; } // 存在しない key の場合何が返ってくるかは不定 template node* find(const int key, node* root) { node *cur = nullptr, *nx = root; while(nx){ cur = nx, cur->push(); if(cur->id == key) break; if(cur->id > key) nx = cur->left; else nx = cur->right; } return splay(cur); } template node* join(node* root1, node* root2) { if(!root1) return root2; node *cur = nullptr, *nx = root1; while(nx){ cur = nx, cur->push(), nx = cur->right; } node* ver = splay(cur); ver->right = root2, 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->id > ver->id) nx = cur->left; else nx = cur->right; } if(cur->id > ver->id) cur->left = ver, ver->par = cur; else cur->right = ver, ver->par = cur; return splay(ver); } template node* erase(const int key, node* root) { node* ver = find(key, root); return join(ver->left, ver->right); } template node* merge(node* root1, node* root2) { if(!root2) return root1; return insert(root2, root1); } vector G[MAX_N]; int ans[MAX_N]; node* ptr[MAX_N]; void dfs(node* cur) { cur->push(); ans[cur->id] += cur->val; 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; }