- Time limit: 1.00 s
- Memory limit: 512 MB
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.