Counting Connected Subtrees with Specified Color Counts

You are given a tree with n nodes, where each node i has a color c_i. It is guaranteed that for any color, there are at most 5 nodes in the tree with that color.

Then you are given several queries. In each query, three distinct colors a, b, c are specified together with three non-negative integers n_a, n_b, n_c. For each query, count the number of non-empty connected subgraphs of the tree that contain only nodes whose colors are in the set {a, b, c} and contain exactly n_a nodes of color a, n_b nodes of color b, and n_c nodes of color c. Since the answer may be large, output it modulo \(10^9+7\).

A connected subgraph is defined as an induced subgraph on a set of vertices that is connected in the original tree.

inputFormat

The first line contains an integer n indicating the number of nodes in the tree.

The second line contains n integers c₁, c₂, \dots, c_n representing the colors of the nodes.

Each of the next n-1 lines contains two integers u and v that denote an edge between nodes u and v.

The following line contains an integer q, the number of queries.

Each of the next q lines contains six integers: a b c n_a n_b n_c, where a, b, c are three distinct colors, and n_a, n_b, n_c are the required counts of nodes of these colors in the subgraph.

outputFormat

For each query, output a single integer on a new line representing the number of connected subgraphs that satisfy the conditions, modulo \(10^9+7\).

sample

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

3
1