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 <= n <= 10^(18)$).
Print the answer modulo $1000000007$.
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_).
## Input
An integer $n$ ($1 <= n <= 10^(18)$).
## Output
Print the answer modulo $1000000007$.
[samples]
## Note
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_).
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ A = (a_1, a_2, \dots, a_n) $, $ B = (b_1, b_2, \dots, b_n) $ be two arrays of length $ n $, such that $ A \cup B $ is a permutation of $ \{1, 2, \dots, 2n\} $.
Let $ C = (c_1, c_2, \dots, c_{2n}) $ be the array constructed by repeatedly removing the first element of either $ A $ or $ B $ (if non-empty) and appending it to $ C $, until both are empty.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ A, B \subseteq \{1, 2, \dots, 2n\} $, $ |A| = |B| = n $, $ A \cap B = \emptyset $, $ A \cup B = \{1, 2, \dots, 2n\} $
**Objective**
Find the lexicographically minimal array $ C $ obtainable by the described operations.