CERI2018E  A recurrence relation
Our task is to print some terms of the sequence defined by :
Input
The first line of the input consist of a single integer number t which determines the number of tests.
In each of next t lines there is a single integer number n.
Constraints
 0 < t ≤ 30 000
 0 < n < 1 000 000
Output
Print u_{n} modulo 1 000 000 007
Example
Input: 3 2 3 10 Output: 5 122 360914800
hide comments
[Rampage] Blue.Mary:
20180504 06:53:05
There are two typos in problem description:

Added by:  Francky 
Date:  20180503 
Time limit:  5s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 