#include <bits/stdc++.h>
using namespace std;
long long add(long long x, long long y) { return (x + y) % 1000000007; }
long long sub(long long x, long long y) {
  return (x - y + 1000000007) % 1000000007;
}
long long mul(long long x, long long y) { return (x * y) % 1000000007; }
set<int> adj[400005];
set<int> cdtree[400005];
vector<vector<long long> > oddin;
vector<vector<long long> > evenin;
vector<vector<long long> > oddex;
vector<vector<long long> > evenex;
int val[400005];
int sz[400005];
int root;
int dad[400005];
int v;
long long ans;
int dfssz(int a, int p = -1) {
  sz[a] = 1;
  for (auto x : adj[a]) {
    if (x != p) sz[a] += dfssz(x, a);
  }
  return sz[a];
}
int getcentriod(int v, int p, int n) {
  for (auto x : adj[v]) {
    if (x != p && sz[x] > n / 2) return getcentriod(x, v, n);
  }
  return v;
}
void indfs(int n, int p, long long pos, long long neg, int l, int cnt) {
  if (l % 2 == 0) {
    evenin[cnt].push_back(0ll + neg + val[n]);
    neg = neg + val[n];
    pos = pos - val[n];
  } else {
    oddin[cnt].push_back(0ll + pos + val[n]);
    neg = neg - val[n];
    pos = pos + val[n];
  }
  for (auto x : adj[n]) {
    if (x != p) {
      indfs(x, n, pos, neg, l + 1, cnt);
    }
  }
}
void outdfs(int n, int p, long long pos, long long neg, int l, int cnt) {
  if (l % 2 == 0) {
    evenex[cnt].push_back(0ll + neg + val[n]);
    neg = neg + val[n];
    pos = pos - val[n];
  } else {
    oddex[cnt].push_back(0ll + pos + val[n]);
    neg = neg - val[n];
    pos = pos + val[n];
  }
  for (auto x : adj[n]) {
    if (x != p) {
      outdfs(x, n, pos, neg, l + 1, cnt);
    }
  }
}
void conquer(int n) {
  oddin.clear();
  evenin.clear();
  oddex.clear();
  evenex.clear();
  int cnt = 0;
  int sz = adj[n].size() + 5;
  oddin.resize(sz);
  evenin.resize(sz);
  oddex.resize(sz);
  evenex.resize(sz);
  for (auto x : adj[n]) {
    cnt += 1;
    indfs(x, n, val[n], -val[n], 2, cnt);
    outdfs(x, n, 0, 0, 1, cnt);
  }
  long long oddexsum = 0;
  long long evenexsum = 0;
  long long evenexcnt = 0;
  long long oddexcnt = 0;
  for (int i = 1; i < sz; i++) {
    for (auto x : oddex[i]) {
      oddexcnt++;
      oddexsum = add(oddexsum, x);
    }
  }
  for (int i = 1; i < sz; i++) {
    for (auto x : evenex[i]) {
      evenexcnt++;
      evenexsum = add(evenexsum, x);
    }
  }
  for (int i = 1; i < sz; i++) {
    long long insum = 0;
    for (auto x : evenin[i]) {
      insum = add(insum, x);
    }
    long long cntin = evenin[i].size();
    long long cntout = oddexcnt;
    long long outsum = oddexsum;
    for (auto y : oddex[i]) {
      cntout -= 1;
      outsum = sub(outsum, y);
    }
    ans = add(ans, mul(outsum, cntin));
    ans = add(ans, mul(insum, cntout));
  }
  for (int i = 1; i < sz; i++) {
    long long insum = 0;
    for (auto x : oddin[i]) {
      insum = add(insum, x);
    }
    long long cntin = oddin[i].size();
    long long cntout = evenexcnt;
    long long outsum = evenexsum;
    for (auto y : evenex[i]) {
      cntout -= 1;
      outsum = sub(outsum, y);
    }
    ans = add(ans, mul(outsum, cntin));
    ans = add(ans, mul(insum, cntout + 2));
  }
  ans = add(ans, val[n]);
}
void divide(int a, int p) {
  int n = dfssz(a, p);
  int c = getcentriod(a, p, n);
  if (p != -1) {
    dad[c] = p;
    cdtree[p].insert(c);
    cdtree[c].insert(p);
  } else
    root = c;
  conquer(c);
  vector<int> temp(adj[c].begin(), adj[c].end());
  for (auto x : temp) {
    adj[x].erase(c);
    adj[c].erase(x);
    divide(x, c);
  }
}
void decompose() { divide(1, -1); }
int main() {
  cin >> v;
  for (int i = 1; i < v + 1; i++) {
    cin >> val[i];
  }
  for (int i = 0; i < v; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].insert(b);
    adj[b].insert(a);
  }
  decompose();
  cout << (ans + 1000000007) % 1000000007 << '\n';
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

Given a tree with n nodes numbered from 1 to n. Each node i has an associated value V_i.

If the simple path from u_1 to u_m consists of m nodes namely u_1 → u_2 → u_3 → ... u_{m-1} → u_{m}, then its alternating function A(u_{1},u_{m}) is defined as A(u_{1},u_{m}) = ∑_{i=1}^{m} (-1)^{i+1} ⋅ V_{u_{i}}. A path can also have 0 edges, i.e. u_{1}=u_{m}.

Compute the sum of alternating functions of all unique simple paths. Note that the paths are directed: two paths are considered different if the starting vertices differ or the ending vertices differ. The answer may be large so compute it modulo 10^{9}+7. 

Input

The first line contains an integer n (2 ≤ n ≤ 2⋅10^{5} ) — the number of vertices in the tree.

The second line contains n space-separated integers V_1, V_2, …, V_n (-10^9≤ V_i ≤ 10^9) — values of the nodes.

The next n-1 lines each contain two space-separated integers u and v (1≤ u, v≤ n, u ≠ v) denoting an edge between vertices u and v. It is guaranteed that the given graph is a tree.

Output

Print the total sum of alternating functions of all unique simple paths modulo 10^{9}+7. 

Examples

Input

4
-4 1 5 -2
1 2
1 3
1 4


Output

40


Input

8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8


Output

4

Note

Consider the first example.

A simple path from node 1 to node 2: 1 → 2 has alternating function equal to A(1,2) = 1 ⋅ (-4)+(-1) ⋅ 1 = -5.

A simple path from node 1 to node 3: 1 → 3 has alternating function equal to A(1,3) = 1 ⋅ (-4)+(-1) ⋅ 5 = -9.

A simple path from node 2 to node 4: 2 → 1 → 4 has alternating function A(2,4) = 1 ⋅ (1)+(-1) ⋅ (-4)+1 ⋅ (-2) = 3.

A simple path from node 1 to node 1 has a single node 1, so A(1,1) = 1 ⋅ (-4) = -4.

Similarly, A(2, 1) = 5, A(3, 1) = 9, A(4, 2) = 3, A(1, 4) = -2, A(4, 1) = 2, A(2, 2) = 1, A(3, 3) = 5, A(4, 4) = -2, A(3, 4) = 7, A(4, 3) = 7, A(2, 3) = 10, A(3, 2) = 10. So the answer is (-5) + (-9) + 3 + (-4) + 5 + 9 + 3 + (-2) + 2 + 1 + 5 + (-2) + 7 + 7 + 10 + 10 = 40.

Similarly A(1,4)=-2, A(2,2)=1, A(2,1)=5, A(2,3)=10, A(3,3)=5, A(3,1)=9, A(3,2)=10, A(3,4)=7, A(4,4)=-2, A(4,1)=2, A(4,2)=3 , A(4,3)=7 which sums upto 40. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long add(long long x, long long y) { return (x + y) % 1000000007; }
long long sub(long long x, long long y) {
  return (x - y + 1000000007) % 1000000007;
}
long long mul(long long x, long long y) { return (x * y) % 1000000007; }
set<int> adj[400005];
set<int> cdtree[400005];
vector<vector<long long> > oddin;
vector<vector<long long> > evenin;
vector<vector<long long> > oddex;
vector<vector<long long> > evenex;
int val[400005];
int sz[400005];
int root;
int dad[400005];
int v;
long long ans;
int dfssz(int a, int p = -1) {
  sz[a] = 1;
  for (auto x : adj[a]) {
    if (x != p) sz[a] += dfssz(x, a);
  }
  return sz[a];
}
int getcentriod(int v, int p, int n) {
  for (auto x : adj[v]) {
    if (x != p && sz[x] > n / 2) return getcentriod(x, v, n);
  }
  return v;
}
void indfs(int n, int p, long long pos, long long neg, int l, int cnt) {
  if (l % 2 == 0) {
    evenin[cnt].push_back(0ll + neg + val[n]);
    neg = neg + val[n];
    pos = pos - val[n];
  } else {
    oddin[cnt].push_back(0ll + pos + val[n]);
    neg = neg - val[n];
    pos = pos + val[n];
  }
  for (auto x : adj[n]) {
    if (x != p) {
      indfs(x, n, pos, neg, l + 1, cnt);
    }
  }
}
void outdfs(int n, int p, long long pos, long long neg, int l, int cnt) {
  if (l % 2 == 0) {
    evenex[cnt].push_back(0ll + neg + val[n]);
    neg = neg + val[n];
    pos = pos - val[n];
  } else {
    oddex[cnt].push_back(0ll + pos + val[n]);
    neg = neg - val[n];
    pos = pos + val[n];
  }
  for (auto x : adj[n]) {
    if (x != p) {
      outdfs(x, n, pos, neg, l + 1, cnt);
    }
  }
}
void conquer(int n) {
  oddin.clear();
  evenin.clear();
  oddex.clear();
  evenex.clear();
  int cnt = 0;
  int sz = adj[n].size() + 5;
  oddin.resize(sz);
  evenin.resize(sz);
  oddex.resize(sz);
  evenex.resize(sz);
  for (auto x : adj[n]) {
    cnt += 1;
    indfs(x, n, val[n], -val[n], 2, cnt);
    outdfs(x, n, 0, 0, 1, cnt);
  }
  long long oddexsum = 0;
  long long evenexsum = 0;
  long long evenexcnt = 0;
  long long oddexcnt = 0;
  for (int i = 1; i < sz; i++) {
    for (auto x : oddex[i]) {
      oddexcnt++;
      oddexsum = add(oddexsum, x);
    }
  }
  for (int i = 1; i < sz; i++) {
    for (auto x : evenex[i]) {
      evenexcnt++;
      evenexsum = add(evenexsum, x);
    }
  }
  for (int i = 1; i < sz; i++) {
    long long insum = 0;
    for (auto x : evenin[i]) {
      insum = add(insum, x);
    }
    long long cntin = evenin[i].size();
    long long cntout = oddexcnt;
    long long outsum = oddexsum;
    for (auto y : oddex[i]) {
      cntout -= 1;
      outsum = sub(outsum, y);
    }
    ans = add(ans, mul(outsum, cntin));
    ans = add(ans, mul(insum, cntout));
  }
  for (int i = 1; i < sz; i++) {
    long long insum = 0;
    for (auto x : oddin[i]) {
      insum = add(insum, x);
    }
    long long cntin = oddin[i].size();
    long long cntout = evenexcnt;
    long long outsum = evenexsum;
    for (auto y : evenex[i]) {
      cntout -= 1;
      outsum = sub(outsum, y);
    }
    ans = add(ans, mul(outsum, cntin));
    ans = add(ans, mul(insum, cntout + 2));
  }
  ans = add(ans, val[n]);
}
void divide(int a, int p) {
  int n = dfssz(a, p);
  int c = getcentriod(a, p, n);
  if (p != -1) {
    dad[c] = p;
    cdtree[p].insert(c);
    cdtree[c].insert(p);
  } else
    root = c;
  conquer(c);
  vector<int> temp(adj[c].begin(), adj[c].end());
  for (auto x : temp) {
    adj[x].erase(c);
    adj[c].erase(x);
    divide(x, c);
  }
}
void decompose() { divide(1, -1); }
int main() {
  cin >> v;
  for (int i = 1; i < v + 1; i++) {
    cin >> val[i];
  }
  for (int i = 0; i < v; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].insert(b);
    adj[b].insert(a);
  }
  decompose();
  cout << (ans + 1000000007) % 1000000007 << '\n';
  return 0;
}

```