Monellako tavalla voit rakentaa palikoista tornin, jonka leveys on 2 ja korkeus on n? Käytössäsi on rajattomasti kaiken kokoisia suorakulmaisia palikoita, joissa leveys ja korkeus ovat kokonaislukuja.

Esimerkiksi kun n=6, tässä on joitakin mahdollisia ratkaisuja:

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen syötteessä on t riviä, joista jokaisella on kokonaisluku n: tornin korkeus.

Tuloste

Ilmoita jokaisesta testistä tornien määrä modulo 10^9+7.

Esimerkki

Syöte:

3
2
6
1337

Tuloste:

8
2864
640403945

Osatehtävä 1 (15 pistettä)

• 1 \le t \le 10
• 1 \le n \le 10

Osatehtävä 2 (41 pistettä)

• 1 \le t \le 100
• 1 \le n \le 100

Osatehtävä 3 (44 pistettä)

• 1 \le t \le 100
• 1 \le n \le 10^6