KIMO2 - simple calculation

The problem statement is very, easy just compute the value of x given the value of n.

Input

The first line will contains T the number of test cases, the following T lines will contain the value of n.

1 <= T <= 10^5

1 <= n < 10^7

Output

For every n print the value of x % (10^9 + 7).

Example

Input:
5
1
5
10
15
33

Output:
1
80
5120
245760
733919781

Added by:abdelkarim
Date:2013-05-17
Time limit:2s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:owner

hide comments
2013-05-17 20:04:37 abdou_93
easy one :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.