## 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:`
`223`
`Output:`
`1 62 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 <= 252 <= 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