SP8427 BTCODE_I - Permutation Game

Harsha is given 9 integers a $ _{1} $ , a $ _{2} $ , a $ _{3} $ , .... a $ _{9} $ . This denotes that he is given a $ _{1} $ 1's, a $ _{2} $ 2's,......a $ _{9} $ 9's. Let 'x' = (a $ _{1} $ + a $ _{2} $ + ...a $ _{9} $ ). 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. Whats 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'.

The first line of input contains 9 integers a $ _{1} $ , a $ _{2} $ , ....a $ _{9} $ . 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'.

For each query, output 2 space separted 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 $ _{1} $ , v $ _{2} $ , .... v $ _{m} $ ) and (u $ _{1} $ , u $ _{2} $ , .... u $ _{n} $ ) are distinct if: 1\) m != n 2\) m = n, there exists some index 'k' (1