{"problem":{"name":"D. Magic Strings","description":{"content":"Consider the sequence of strings $F_1, F_2, \\\\dots$, defined as: $$ F_1 = ab\\text{,} $$ $$ F_{k+1} = F_kF_kb\\text{.} $$ Calculate the number of distinct _subsequences_ of the string $F_n$ modulo $10","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10235D"},"statements":[{"statement_type":"Markdown","content":"Consider the sequence of strings $F_1, F_2, \\\\dots$, defined as:\n\n$$ F_1 = ab\\text{,} $$ $$ F_{k+1} = F_kF_kb\\text{.} $$\n\nCalculate the number of distinct _subsequences_ of the string $F_n$ modulo $10^9 + 7$.\n\nThe first line of input contains a single integer $t$ ($1 <= t <= 10$), which is the number of test cases.\n\nThe second line of input contains $t$ integers $n$ ($1 <= n <= 10^(18)$), one for each test case.\n\nFor each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces.\n\nThe first three strings are: $F_1 = texttt(a b)$, $F_2 = texttt(a b a b b)$, and $F_3 = texttt(a b a b b a b a b b b)$.\n\n## Input\n\nThe first line of input contains a single integer $t$ ($1 <= t <= 10$), which is the number of test cases.The second line of input contains $t$ integers $n$ ($1 <= n <= 10^(18)$), one for each test case.\n\n## Output\n\nFor each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces.\n\n[samples]\n\n## Note\n\nThe first three strings are: $F_1 = texttt(a b)$, $F_2 = texttt(a b a b b)$, and $F_3 = texttt(a b a b b a b a b b b)$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ F_1 = \"ab\" $, and for $ k \\geq 1 $, define $ F_{k+1} = F_k F_k b $.  \nLet $ s_n = |F_n| $ denote the length of $ F_n $, and let $ a_n $ denote the number of distinct subsequences of $ F_n $.\n\n**Constraints**  \n1. $ 1 \\leq t \\leq 10 $  \n2. For each test case, $ 1 \\leq n \\leq 10^{18} $\n\n**Recurrence**  \nLet $ a_n $ be the number of distinct subsequences of $ F_n $.  \nThen:  \n- $ a_1 = 4 $ (subsequences of \"ab\": \"\", \"a\", \"b\", \"ab\")  \n- For $ n \\geq 1 $:  \n  $$\n  a_{n+1} = 2a_n + 1\n  $$\n\n**Objective**  \nFor each test case with input $ n $, compute $ a_n \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10235D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}