Moni on ihmetellyt, miksi Uoleville sattuu niin monenlaista. Selitys on kuitenkin yksinkertainen: kaikki johtuu hänen DNA:ssaan tapahtuneesta mutaatiosta.

Uolevin DNA:sta tiedetään kuitenkin vain vähän. Se voidaan kuvata merkkijonona, jossa on n merkkiä ja jokainen merkki on A, C, G tai T. Lisäksi tiedetään, että sekä A:ta, C:tä, G:tä että T:tä on parillinen määrä (mutaatio ilmenee näin).

Kuinka monta mahdollisuutta on sille, mikä on Uolevin DNA?

Syöte

Syötteen ainoalla rivillä on kokonaisluku n: DNA:n pituus.

Tuloste

Ohjelmasi tulee tulostaa mahdollisuuksien määrä modulo 10^9+7.

Rajat

1 \leq n \leq 10^4

Esimerkki

Syöte:

4

Tuloste:

40

Selitys: Mahdollisuuksia ovat esimerkiksi AAAA, ACCA sekä GCGC.