Outo DNA

• Time limit: 1.00 s
• Memory limit: 512 MB

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.