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. 

import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Main {
    private static int [] even,odd;
    private static int n;
    private static ArrayList<Integer> [] G;
    private static int [] A,siz;
    private static int ans;
    private static int mod = 1000*1000*1000 + 7;

    private static void dfs(int u,int p) {
        even[u] = 1;
        siz[u] = 1;
        for (int v : G[u]) if (v != p) {
            dfs(v,u);
            even[u] += odd[v];
            odd[u] += even[v];
            siz[u] += siz[v];
        }
    }
    private static int add(int a,int b) {
        a += b;
        a = (a%mod + mod)%mod;
        return a;
    }
    private static int mul(int a,int b) {
        long c = a*(long)b;
        c = (c%mod + mod)%mod;
        return (int)c;
    }
    private static void dfs(int u,int p,int e,int o) throws Exception{
//        System.err.println(e + " " + o);
        if (e < 0) throw new Exception("e = " + e);
        if (o < 0) throw new Exception("o = " + o);

        int tmp = add(e+o + 1,e-o);
        e++;
        for (int v : G[u]) if (v != p) {
            tmp = add(tmp,mul(e - o,siz[v])) ;
            tmp = add(tmp,mul(odd[v] - even[v],e + o));
            e += odd[v];
            o += even[v];
        }

        tmp = mul(tmp,A[u]);

//        System.err.println(u + ". " + tmp);
        ans = add(ans,tmp);

        for (int v : G[u]) if(v != p) {
            int go = e - odd[v];
            int ge = o - even[v];
            dfs(v,u,ge,go);
        }
    }
    public static void main(String[] args) throws Exception {
        IO io = new IO(null, null);
        n = io.getNextInt();
        A = new int[n+1];
        even = new int[n+1];
        odd = new int[n+1];
        siz = new int[n+1];
        G = new ArrayList[n+1];
        for (int i = 1;i <= n;i++) {
            A[i] = io.getNextInt();
            G[i] = new ArrayList<>();
        }

        for (int e = 1;e < n;e++){
            int a = io.getNextInt(),b = io.getNextInt();
            G[a].add(b);
            G[b].add(a);
        }

        dfs(1,0);



        dfs(1,0,0,0);
        io.println(ans);
        io.close();
    }


}





class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}
