Antichains

All submissions for this problem are available.
Given an integer N, let F_{N} be the set of factors of N. e.g., F_{6} = {1,2,3,6}.
The radical of an integer N, denoted by rad(N), is defined as the product of the distinct prime factors of N. e.g., rad(12) = 2 * 3 = 6.
Define an antichain of a set S of integers to be a subset of S such that for any two elements x and y in the antichain, rad(x) and rad(y) do not divide each other. e.g., antichains in F_{6} are {}, {1}, {2}, {3}, {6} and {2,3}.
Given N, find the size of the largest antichain of F_{N}, and the number of antichains of F_{N} of that size. Since the answers can be large, print both of them modulo (10^{9}+7).
e.g., if N = 6, the largest antichain is of size 2, and there is only 1 antichain of that size.
Since N can be large, the input is the prime factorization of N. The input has two arrays of size M: base and power, and N = base_{1}^{power1} * base_{2}^{power2} * … * base_{M}^{powerM}.
Input
 The first line contains T, the number of test cases. Description of the T test cases follows.
 Each test case starts with a single integer M.
 The next M lines each contain 2 integers separated by a space. The i^{th} line contains base_{i} and power_i.
Output
 For each test case, output one line containing two spaceseparated integers, respectively the size of the largest antichain modulo (10^{9}+7) and the number of antichains of that size, again modulo (10^{9}+7).
Constraints
 1 ≤ T ≤ 10
 1 ≤ M ≤ 10^{5}
 2 ≤ base_{i} ≤ 10^{9}
 1 ≤ power_i ≤ 10^{9}
 base_{i} is a prime number for all 1 ≤ i ≤ M
 For any 1 ≤ i ≠ j ≤ M, base_{i} ≠ base_{j}
NOTE: Input files can be large. Please use fast input methods (e.g. scanf in C/C++, BufferedReader in Java)
Example
Input: 2 2 2 1 3 1 2 2 2 3 1 Output: 2 1 2 2
Explanation
Example case 1. The largest antichain size is 2, and there is only one of it {2,3}
Example case 2. The largest antichain size is 2, and there are two of those: {2,3} and {4,3}
Author:  piyushkumar 
Editorial  http://discuss.codechef.com/problems/KOL1508 
Tags  acm15kol, combinatorics, piyushkumar, sperners, theorem 
Date Added:  10122015 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 