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