BTCODE_I - Permutation Game

Harsha is given 9 integers a1, a2, a3 ... a9. This denotes that he is given a1 1's, a2 2's ... a9 9's. Let 'x' = (a1 + a2 + ... a9). 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 Si denote the sum of weights of all edges on this path. Calculate the value of sum(Si), for every distinct path 'i' from node 'u' to node 'v'.

Input

The first line of input contains 9 integers a1, a2 ... a9. 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 (v1, v2 ... vm) and (u1, u2 ... un) are distinct if:

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

Constraints

1 ≤ (a1 + a2 + ... a9) ≤ 500

1 ≤ Q ≤ 20

ai ≥ 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.


Added by:suhash
Date:2011-02-26
Time limit:1.711s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India

hide comments
2012-11-08 22:38:16 :D
Of course it feasible. My solution was O(Q*L*BASE) where BASE is 10. Constant factor was a pretty high.

Yes, most problems are easy if you limit them to very small constraints. That's why those are high in the first place.
2011-04-30 10:16:56 kiransk
is this feasible? 500 digit permutation itself is expensive? finding all path and their total length is easy.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.