Problem: Let the main characters of this problem be personages from some recent movie. New Avengers seem to make a lot of buzz. I didn't watch any part of the franchise and don't know its heroes well, but it won't stop me from using them in this problem statement. So, Thanos and Dr. Strange are doing their superhero and supervillain stuff, but then suddenly they stumble across a regular competitive programming problem.

You are given a tree with n vertices.

In each vertex v there is positive integer a_{v}.

You have to answer q queries.

Each query has a from u v x.

You have to calculate ∏_{w ∈ P} gcd(x, a_{w}) mod (10^{9} + 7), where P is a set of vertices on path from u to v. In other words, you are to calculate the product of gcd(x, a_{w}) for all vertices w on the path from u to v. As it might be large, compute it modulo 10^9+7. Here gcd(s, t) denotes the greatest common divisor of s and t.

Note that the numbers in vertices do not change after queries.

I suppose that you are more interested in superhero business of Thanos and Dr. Strange than in them solving the problem. So you are invited to solve this problem instead of them.

Input

In the first line of input there is one integer n (1 ≤ n ≤ 10^{5}) — the size of the tree.

In the next n-1 lines the edges of the tree are described. The i-th edge is described with two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) and it connects the vertices u_{i} and v_{i}. It is guaranteed that graph with these edges is a tree.

In the next line there are n integers a_1, a_2, …, a_n (1 ≤ a_{v} ≤ 10^{7}).

In the next line there is one integer q (1 ≤ q ≤ 10^{5}) — the number of queries.

And in the next q lines the queries are described. Each query is described with three integers u_{i}, v_{i} and x_{i} (1 ≤ u_{i}, v_{i} ≤ n, 1 ≤ x_{i} ≤ 10^{7}).

Output

Print q numbers — the answers to the queries in the order they are given in the input. Print each answer modulo 10^9+7 = 1000000007. Print each number on a separate line.

Examples

Input

4
1 2
1 3
1 4
6 4 9 5
3
2 3 6
2 3 2
3 4 7


Output

36
4
1


Input

6
1 2
2 3
2 4
1 5
5 6
100000 200000 500000 40000 800000 250000
3
3 5 10000000
6 2 3500000
4 1 64000


Output

196000
12250
999998215

Solution (in JAVA):

Solution:
//package com.company;

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));
//        Task tt = new Task();
//        tt.generate(22, 1000000, pw);
//        pw.close();
//        pw = new PrintWriter(new FileOutputStream("Test.out"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.out.println("Memory increased:" + (usedMemoryAfter-usedMemoryBefore) / 1000000 );
//        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    public static class Task {
        // Common
        public class Pair {
            int a, b;

            public Pair(int a, int b) {
                this.a = a;
                this.b = b;
            }
        }
        // Tree
        public class Node {
            List<Node> edges;
            Node parent;
            int first;
            int last;
            int idx;
            Node(int idx) {
                this.idx = idx;
                edges = new ArrayList<>();
            }
        }
        Node[] nodes;
        int root;

        // Segment tree lca
        int[] st;
        int[] val;
        int[] height;
        public int minOf(int idx) {
            int left = st[idx << 1];
            int right = st[idx << 1 | 1];
            return height[left] < height[right] ? left: right;
        }
        public void build(int left, int right, int idx) {
            if (right == left + 1) {
                st[idx] = val[left];
                return;
            }
            int mid = (left + right) >> 1;
            build(left, mid, idx << 1);
            build(mid, right, idx << 1 | 1);
            st[idx] = minOf(idx);
        }
        public int query(int left, int right, int qLeft, int qRight, int idx) {
            if (qLeft >= right || qRight <= left) return -1;
            if (qLeft <= left && right <= qRight) {
                return st[idx];
            }
            int mid = (left + right) >> 1;
            int qL = query(left, mid, qLeft, qRight, idx << 1);
            int qR = query(mid, right, qLeft, qRight, idx << 1 | 1);
            if (qL == -1) return qR;
            if (qR == -1) return qL;
            return height[qL] < height[qR] ? qL : qR;
        }
        public void buildLCA() {
            st = new int[(val.length << 2) + 10];
            build(0, val.length, 1);
        }
        public int lca(Node u, Node v) {
            int qL = u.first;
            int qR = v.first;
            if (qL > qR) {int tmp = qL; qL = qR; qR = tmp;}
            return query(0, val.length, qL, qR + 1, 1);
        }

        // Traverse graph
        int dfsIndex = 0;
        public void dfs(Node curNode, int depth, Node parent) {
            height[curNode.idx] = depth;
            val[dfsIndex] = curNode.idx;
            curNode.first = dfsIndex++;
            curNode.last = curNode.first;
            curNode.parent = parent;
            for (Node edge : curNode.edges) {
                if (edge == parent) continue;
                dfs(edge, depth + 1, curNode);
                val[dfsIndex] = curNode.idx;
                curNode.last = dfsIndex++;
            }

        }

        // fenwick
        int[] fenwick;
        void modify(int x, int v) {
            while (x < fenwick.length) {
                fenwick[x] += v;
                x |= x + 1;
            }
        }
        int getSum(int x) {
            int v = 0;
            while (x >= 0) {
                v += fenwick[x];
                x = (x & (x + 1)) - 1;
            }
            return v;
        }

        void addNode(Node node) {
            modify(node.first, 1);
            modify(node.last + 1, -1);
        }

        void rmNode(Node node) {
            modify(node.last + 1, 1);
            modify(node.first, -1);
        }

        int getSum(Node u, Node v) {
            Node lca = nodes[lca(u, v)];
            int uRoot = getSum(u.first);
            int vRoot = getSum(v.first);
            int lRoot = getSum(lca.first);
            if (lca.parent != null) {
                lRoot += getSum(lca.parent.first);
            }
            return uRoot + vRoot - lRoot;
        }

        // sieve
        final int M = 10000005;
        int[] factors;
        List<Integer> primes;
        List<Pair>[] primeEvents;
        public void sieve() {
            factors = new int[M];
            Arrays.fill(factors, -1);
            primes = new ArrayList<>();
            for (int i = 2; i < M; i++) {
                if (factors[i] == -1) {
                    factors[i] = primes.size();
                    primes.add(i);
                }
                for (int j = 0; j < primes.size(); j++) {
                    int pr = primes.get(j);
                    if (i * pr >= M) break;
                    factors[i * pr] = j;
                    if (i % pr == 0) break;
                }
            }
            primeEvents = new List[primes.size()];

        }

        int n, q;
        final int MOD = 1_000_000_007;
        public void init() {
            sieve();
            nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node(i);
            }
            val = new int[n << 1];
            height = new int[n];
            fenwick = new int[n << 1];
        }
        public void postInit() {
            root = 0;
            dfs(nodes[root], 0, null);
            buildLCA();
        }
        public void resolveNode(Node node, int x) {
            while (x != 1) {
                int factIdx = factors[x];
                int fact = primes.get(factIdx);
                int count = 0;
                while (x % fact == 0) {
                    x /= fact;
                    count++;
                }
                if (primeEvents[factIdx] == null) {
                    primeEvents[factIdx] = new ArrayList<>();
                }
                primeEvents[factIdx].add(new Pair(node.idx, count));
            }
        }
        int add(int a, int b) {
            int c = a + b;
            if (c >= MOD) return c - MOD;
            return c;
        }
        int mult(int a, int b) {
            long c = (long) a * b % MOD;
            return (int) c;
        }
        int power(int a, int b) {
            int res = 1;
            while (b != 0) {
                if ((b & 1) != 0) {
                    res = mult(res, a);
                }
                a = mult(a, a);
                b >>= 1;
            }
            return res;
        }
        void initQ(){
            queryU = new int[q];
            queryV = new int[q];
            queryRes = new int[q];
            Arrays.fill(queryRes, 1);
        }
        int[] queryU;
        int[] queryV;
        int[] queryRes;
        public void resolveQuery(int u, int v, int x, int idx) {
            queryU[idx] = u;
            queryV[idx] = v;
            while (x != 1) {
                int factIdx = factors[x];
                int fact = primes.get(factIdx);
                int count = 0;
                while (x % fact == 0) {
                    x /= fact;
                    count++;
                }
                if (primeEvents[factIdx] == null) continue;
                for (int i = 1; i <= count; i++) {
                    primeEvents[factIdx].add(new Pair(-idx - 1, i));
                }
            }
        }

        public void solve() {
            for (int i = 0; i < primes.size(); i++) {
                List<Pair> events = primeEvents[i];
                if (events == null) continue;
                events.sort(new Comparator<Pair>() {
                    @Override
                    public int compare(Pair p1, Pair p2) {
                        if (p2.b == p1.b) return Integer.compare(p2.a, p1.a);
                        return p2.b - p1.b;
                    }
                });
                  for (Pair event: events) {
                    if (event.a >= 0) {
                        addNode(nodes[event.a]);
                    } else {
                        int num = -event.a - 1;
                        int sum = getSum(nodes[queryU[num]], nodes[queryV[num]]);
                        queryRes[num] = mult(queryRes[num], power(primes.get(i), sum));
                    }
                }
                for (Pair event: events) {
                    if (event.a >= 0) {
                        rmNode(nodes[event.a]);
                    }
                }
            }
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            init();
            for (int i = 0; i < n - 1; i++) {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 1;
                nodes[a].edges.add(nodes[b]);
                nodes[b].edges.add(nodes[a]);
            }
            postInit();
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt();
                resolveNode(nodes[i], a);
            }
            q = sc.nextInt();
            initQ();
            for (int i = 0; i < q; i++) {
                int u = sc.nextInt() - 1;
                int v = sc.nextInt() - 1;
                int x = sc.nextInt();
                resolveQuery(u, v, x, i);
            }
            solve();
            for (int i = 0; i < q; i++) {
                pw.println(queryRes[i]);
            }

        }



    }


    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public Scanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

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

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}