{"problem":{"name":"B. String Mood","description":{"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_) fl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264B"},"statements":[{"statement_type":"Markdown","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## Input\n\nAn integer $n$ ($1 <= n <= 10^(18)$).\n\n## Output\n\nPrint the answer modulo $1000000007$.\n\n[samples]\n\n## Note\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.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_).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}