#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for (int i = 0; i < (int)(n); ++i) //#define cerr if(false) cerr #ifdef DEBUG #define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__); #else #define show(...) 42 #endif using namespace std; using ll = long long; using pii = pair; template ostream &operator<<(ostream &os, pair a) { os << '(' << a.first << ',' << a.second << ')'; return os; } template ostream &operator<<(ostream &os, vector v) { for (auto x : v) os << x << ' '; return os; } void debug() { cerr << '\n'; } template void debug(H a, T... b) { cerr << a; if (sizeof...(b)) cerr << ", "; debug(b...); } template class modint{ public: int a; modint(const long long v = 0):a(v % MOD){} int getmod() const{ return MOD; } modint operator+(const modint rhs) const{ return modint(*this) += rhs; } modint operator-(const modint rhs) const{ return modint(*this) -= rhs; } modint operator*(const modint rhs) const{ return modint(*this) *= rhs; } modint operator/(const modint rhs) const{ return modint(*this) /= rhs; } modint operator+(const long long rhs) const{ return modint(*this) += rhs; } modint operator-(const long long rhs) const{ return modint(*this) -= rhs; } modint operator*(const long long rhs) const{ return modint(*this) *= rhs; } modint operator/(const long long rhs) const{ return modint(*this) /= rhs; } friend modint operator+(const long long a, const modint b){ return b + a; } friend modint operator-(const long long a, const modint b){ return -b + a; } friend modint operator*(const long long a, const modint b){ return b * a; } friend modint operator/(const long long a, const modint b){ return modint(a) / b; } modint &operator+=(const modint rhs){ a += rhs.a; if(a >= MOD){ a -= MOD; } return *this; } modint &operator-=(const modint rhs){ if(a < rhs.a){ a += MOD; } a -= rhs.a; return *this; } modint &operator*=(const modint rhs){ a = (long long)a * rhs.a % MOD; return *this; } modint &operator/=(modint rhs){ int x = MOD - 2; while(x){ if(x % 2){ *this *= rhs; } rhs *= rhs; x /= 2; } return *this; } modint &operator++(){ *this += 1; return *this; } modint &operator--(){ *this -= 1; return *this; } modint operator++(int){ modint res = *this; ++(*this); return res; } modint operator--(int){ modint res = *this; res -= 1; return res; } modint &operator+=(const long long rhs){ *this += modint(rhs); return *this; } modint &operator-=(const long long rhs){ *this -= modint(rhs); return *this; } modint &operator*=(const long long rhs){ *this *= modint(rhs); return *this; } modint &operator/=(const long long rhs){ *this /= modint(rhs); return *this; } modint operator+() const{ return *this; } modint operator-() const{ return modint()-*this; } bool operator==(const modint rhs) const{ return a == rhs.a; } bool operator==(const long long rhs) const{ return a == rhs; } friend bool operator==(const long long a, const modint b){ return a == b.a; } bool operator!=(const modint rhs) const{ return a != rhs.a; } bool operator!=(const long long rhs) const{ return a != rhs; } friend ostream &operator<<(ostream &os, const modint x){ os << x.a; return os; } friend istream &operator>>(istream &is, modint &x){ is >> x.a; return is; } explicit operator bool() const{ return a > 0; } bool operator!(){ return a == 0; } explicit operator int() const{ return a; } explicit operator long long() const{ return (long long) a; } friend modint pow(modint a, long long b){ modint res = 1; while(b){ if(b % 2){ res *= a; } a *= a; b /= 2; } return res; } }; using mint = modint<1000000007>; vectorg[200005]; int par[200005]; int sz[200005]; int b[200005]; int gya[200005]; mint r[200005]; vector>d; int find(int x){ if(par[x] == x)return x; else return par[x] = find(par[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x == y)return; if(sz[x] >= sz[y]){ for(auto z:d[y]){ d[x].push_back(z); } sz[x] += sz[y]; par[y] = x; }else{ swap(x,y); for(auto z:d[y]){ d[x].push_back(z); } sz[x] += sz[y]; par[y] = x; } } int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n)cin >> r[i]; d.resize(n); rep(i,n){ sz[i] = 1; par[i] = i; d[i].emplace_back(i); } rep(i,n-1){ int a,b; cin >> a >> b; a--,b--; if(b > a)swap(a,b); g[a].push_back(b); } vectorp; rep(i,n){ for(auto x: g[i]){ unite(i,x); } int t = find(i); show(i,t); p.emplace_back(d[t][0],d[t].back()); } int t = find(0); rep(i,n){ gya[d[t][i]] = i; } for(auto &x : p){ b[gya[x.first]]++; b[gya[x.second]+1]--; } rep(i,n)b[i+1] += b[i]; mint ans = 1; rep(i,n){ ans *= (r[i] + b[gya[i]]); } cout << ans << endl; }