Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PARTS - Parts

Una composición de un número n es una secuencia ordenada de números que suman n,
por ejemplo para n = 4 tenemos 8 composiciones:
    
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 3
4 = 1 + 2 + 1
4 = 1 + 1 + 2
4 = 1 + 1 + 1 + 1

Una parte de una composición es uno de los sumandos de la composición, para n = 4,
el total de partes en todas sus composiciones es 20. Dado un entero n (1 <= n <= 10^9)
calcule el número de partes módulo 10^9 + 7.

Input

La entrada inicia con un entero T (T <= 40)
Siguen T líneas cada una con un entero n (1 <= n <= 10^9)

Output

Una línea con la respuesta por cada caso.

Example

Input:
4
1
2
3
4

Output: 1
3
8
20

Adicionado por:MarioYC
Fecha:2013-09-22
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP CPP C++ 4.3.2 CPP14 JAVA
Fuente:Own

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.