KOPC12B - K12-Combinations

no tags 

Given n find the value of ((nC1)2+2*(nC2)2+3*(nC3)2+4*(nC4)2+ ... +n*(nCn)2)% MOD, where MOD=10^9+7.

Note: nCr is the number of ways of choosing r items from n items.

Input

The first line of input file contains T which denotes number of test cases. Each of the following line contains an integer n. T<=1000 and n<=10^6.

Output

The output must contain T lines each line corresponding to a testcase.

Example

Input:
2
1
2

Output:
1
6

hide comments
smso: 2019-03-05 16:29:59

Beware: max n > 10^6

julkas: 2018-06-10 13:43:21

Very good problem.

abhishek_ydv60: 2017-05-08 14:48:38

this question shows power of modular arithmetic .. :D

suraj_: 2016-09-30 21:47:39

good question....learned a lot

coder_hsnake: 2016-08-09 09:21:27

ac in one go!!!!

Last edit: 2016-08-09 09:23:03
Mayank Garg: 2015-12-27 16:22:32

12th standard maths ..Easy one :-)

pvsmpraveen: 2015-12-25 18:28:28

My 50th ;) , take care about overflows, gave me 3WA

Dhawal Harkawat: 2015-04-08 11:33:21

silly me! a mistake costed 3 WAs.

mohit kumar jain: 2015-02-19 08:46:58

finally done after a lot of tle and wa

Ankit Sultana: 2015-02-11 06:32:00

Finally !! Worth the effort


Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64