{"raw_statement":[{"iden":"statement","content":"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.\n\nLimak 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$.\n\nAn integer $n$ ($1 <= n <= 10^(18)$).\n\nPrint the answer modulo $1000000007$.\n\nThere 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.\n\nFor $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_).\n\n"},{"iden":"input","content":"An integer $n$ ($1 <= n <= 10^(18)$)."},{"iden":"output","content":"Print the answer modulo $1000000007$."},{"iden":"examples","content":"Input1\nOutput19\nInput2\nOutput403\nInput11\nOutput145418665\n"},{"iden":"note","content":"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_)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ 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\\} $.  \n\nLet $ 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.\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ A, B \\subseteq \\{1, 2, \\dots, 2n\\} $, $ |A| = |B| = n $, $ A \\cap B = \\emptyset $, $ A \\cup B = \\{1, 2, \\dots, 2n\\} $\n\n**Objective**  \nFind the lexicographically minimal array $ C $ obtainable by the described operations.","simple_statement":"Given two arrays A and B of length n, together containing all numbers from 1 to 2n exactly once.  \nYou can build array C by repeatedly taking the first element from either A or B (if not empty) and appending it to C.  \nFind the lexicographically smallest possible C.","has_page_source":false}