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$