Maximum Score

Ron likes to play with integers. Recently he is interested in a game where some integers are given and he is allowed to permute them. His point will be calculated from the permutation made by him. Ron knows that he will get as many candies as his point, so he wants to permute the numbers to maximize his point. Say, Ron has got n integers {x1, x2, . . . , xn} and (xi1, xi2, . . . , xin) is the permutation made by him. His point will be the sum of the score of all integers. The score of an individual number xiw in that permutation is calculated by the length of the longest subsequence (Let us consider xj1, xj2, ..., xjm as the subsequence where 1 ≤ j1 < j2 < . . . < jm ≤ n) you can form with the following constraints:

1. Thereexistsanintegerksuchthat1≤k≤mandjk =iw. 2. xj1 ≤xj2 ≤...≤xjk−1 ≤xjk ≥xjk+1 ≥...≥xjm−1 ≥xjm. Therefore, the score of xiw in that permutation will be m. Say, (1, 4, 3) is a permutation made by Ron using the numbers {1, 3, 4}. For this permutation, score of 1 is 1 with subsequence (1), score of 4 is 3 with subsequence (1, 4, 3) and score of 3 is 2 with subsequence (1, 3). So, Ron’s point is 6 for this permutation. Ron is not sure how to achieve the maximum point and he is also wondering about the number of different permutations which generate that maximum value of point. You need to help Ron to calculate these two values. A permutation (x1, x2, . . . , xn) is different from another permutation (y1, y2, . . . , yn) ifthereexistsanintegerisuchthat1≤i≤nandxi isnotequaltoyi. Input The first line of input contains a single integer T (1 ≤ T ≤ 200), which denotes the number of test cases to follow. For each test case, there will be two lines of input. The first line contains a single integer, p (1 ≤ p ≤ 105). The second line contains p pairs of integers. In each pair, there are two integers vi and fi (1 ≤ vi, fi ≤ 105) which indicate that the value vi is present fi times among the given numbers. Therefore, f1 + f2 + . . . + fp = n, where n is the total number of integers given to Ron. All the values of vi will be distinct. Output For each case, in a separate line, print the case number and the maximum sum of scores and the number of permutations to achieve that sum of scores. As the number of permutations can be quite large, print it modulo 1000000007 (109 + 7). Follow Sample Input and Output for details. The value of the maximum sum of scores will fit in 64-bit unsigned integer. Sample Input 2 2 121 1 22 1 2 71 2 35 1

2/2 Sample Output Case 1: 3 2 Case 2: 7 2