406974: GYM102644 B String Mood

Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing.

Limak is happy right now. Among all $$$26^n$$$ possible strings with $$$n$$$ uppercase English letters, count such strings that Limak will be happy after reading that string. Print the answer modulo $$$10^9+7$$$.

An integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Print the answer modulo $$$1000000007$$$.

1

19

2

403

11

145418665

There are 19 strings of length $$$n = 1$$$ that will leave Limak happy: B, C, F, G, H, J, K, L, M, N, P, Q, R, T, V, W, X, Y, Z. The string "O" shouldn't be counted because the mood is switched from happy to sad.

For $$$n = 2$$$, there are 403 good strings: AA, AE, AH, AI, AO, AU, BB, ..., RZ, SA, SE, SH, SI, SO, SU, TB, TC, TF, ..., YQ, YR, YT, YV, YW, YX, YY, YZ, ZB, ZC, ZF, ZG, ZH, ZJ, ZK, ZL, ZM, ZN, ZP, ZQ, ZR, ZT, ZV, ZW, ZX, ZY, ZZ. The string "AO" is counted because the mood flips twice. Similarly, the string "SO" is counted because it first makes Limak sad (letter S) and then switches his mood from sad to happy (letter O).