DCOUNT - Counting Diameter

no tags 

Given an integer 'K', construct a set 'S' containing all integers from 1 to 2*K-1 (both inclusive). Construct a graph 'G' with vertices represented by all the K-1 element subsets of 'S'. There is an  edge from vertex 'u' to vertex 'v' in 'G', if the corresponding subsets of 'u' and 'v' do not have any element in common. The distance d(u,v) between a vertex 'u' to a vertex 'v' is defined as the shortest path from 'u' to 'v' in 'G'. The diameter of 'G' is defined as the longest distance between any two vertices in 'G'. Output the diameter of the graph and the number of pairs of vertices which have distance equal to the diameter.

Input

The first line of input contains a number 't', the number of test cases.

Each of the following 't' lines contains an integer 'K'.

Output

For each testcase output two space separated integers, the diameter and the number of pairs. Since the numbers can be huge, output all the numbers modulo 1,000,000,007.

Example

Input:

2

2

3

Output:

1 6

2 60
Explanation:

For Case 1:

The graph is a triangle, so  the diameter is 1 and the distance between any 2 pairs of different  vertices is 1. The 6 pairs are: ({1},{2}), ({2},{1}), ({1},{3}),({3},{1}),  ({2},{3}), ({3},{2}).

Constraints:

t <= 25

2 <= K <= 100,000


hide comments
Radhakrishnan Venkataramani: 2010-12-27 22:35:30

Wats the answer for n=4?
is it 840 ?

suhash: 2010-04-15 02:35:25

sorry, done!! :)

~!(*(@*!@^&: 2010-04-15 02:33:39

break the lines, pls.


Added by:suhash
Date:2010-04-13
Time limit:0.389s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:ByteCode 2010