Harsha is given 9 integers a₁, a₂, a₃ ... a₉. This denotes that he is given a₁ 1's, a₂ 2's ... a₉ 9's. Let 'x' = (a₁ + a₂ + ... a₉). Now, Harsha makes all possible 'x' digit numbers by using these given digits. Let S be the set of all such numbers which he makes. Now he constructs a directed graph containing |S| nodes, in which each node denotes a unique number from the set. For all numbers u, v belonging to S, there is a directed edge from node 'u' to node 'v in the graph iff u > v. It is easy to note that we obtain a directed acyclic graph. What's more, the edges of the graph are weighted. The weight of an edge joining node 'u' and node 'v' is equal to u + v. Now, Deepak decides to test Harsha's memory and gives him 'Q' queries. Each query consists of two numbers 'u', 'v' (u > v, both belonging to the set S). For each query Harsha must provide the following answers:

1. How many distinct paths are there from node 'u' to node 'v' in the graph.
2. For each distinct path 'i' from node 'u' to node 'v', let S_i denote the sum of weights of all edges on this path. Calculate the value of sum(S_i), for every distinct path 'i' from node 'u' to node 'v'.

Input

The first line of input contains 9 integers a₁, a₂ ... a₉. The second line contains a single integer 'Q', denoting the number of queries. Each of the next 'Q' lines contain 2 numbers 'u' and 'v'.

Output

For each query, output two space separated integers denoting the number of distinct paths and sum of weights of all paths respectively. Since the output can be large, output these quantities modulo 1000000007.

Two paths (v₁, v₂ ... v_m) and (u₁, u₂ ... u_n) are distinct if:

1. m != n
2. m = n, there exists some index 'k' (1 ≤ k ≤ m) such that v_k ≠ u_k

Constraints

1 ≤ (a₁ + a₂ + ... a₉) ≤ 500

1 ≤ Q ≤ 20

a_i ≥ 0

Example

Input:
2 0 1 0 0 0 0 0 0
1
311 113

Output:
2 1110

Explanation

Test case 1: The set S for the above problem is {311, 113, 131}. The edges of the graph are 311→131, 311→113, 131→113. There are two distinct paths from 311 to 113, namely (311→131→113) and (311→113). The sum of weights of edges on path-1 = (311 + 131) + (131 + 113) = 686. For path-2, the sum of weights of edges = (311 + 113) = 424. Therefore, answer = 686 + 424 = 1110.