{"problem":{"name":"C. Fibonacci","description":{"content":"Find the $n$-th Fibonacci number modulo $10^9 + 7$. So, you need to find $F_n$ in the sequence defined as $F_0 = 0$, $F_1 = 1$ and $F_i = F_{i -1} + F_{i -2}$ for $i >= 2$. An integer $n$ ($0 <= n <","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264C"},"statements":[{"statement_type":"Markdown","content":"Find the $n$-th Fibonacci number modulo $10^9 + 7$.\n\nSo, you need to find $F_n$ in the sequence defined as $F_0 = 0$, $F_1 = 1$ and $F_i = F_{i -1} + F_{i -2}$ for $i >= 2$.\n\nAn integer $n$ ($0 <= n <= 10^(18)$).\n\nPrint the answer modulo $1000000007$.\n\nThe first few terms of Fibonacci sequence are $(0, 1, 1, 2, 3, 5, 8, 13, \\\\dots)$. In particular, we have $F_0 = 0$, $F_3 = 2$ and $F_6 = 8$. And for the last sample test:\n\n$$F_{50} = 12586269025 \\equiv 586268941 \\pmod {10^9 + 7}$$\n\n## Input\n\nAn integer $n$ ($0 <= n <= 10^(18)$).\n\n## Output\n\nPrint the answer modulo $1000000007$.\n\n[samples]\n\n## Note\n\nThe first few terms of Fibonacci sequence are $(0, 1, 1, 2, 3, 5, 8, 13, \\\\dots)$. In particular, we have $F_0 = 0$, $F_3 = 2$ and $F_6 = 8$. And for the last sample test:$$F_{50} = 12586269025 \\equiv 586268941 \\pmod {10^9 + 7}$$","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of notes in the song, $ k \\in \\mathbb{Z} $ the number of chords.  \nLet $ S = (s_{i,j}) \\in \\mathbb{R}^{k \\times k} $ be the transition time matrix, where $ s_{i,j} $ is the direct time to switch from chord $ i $ to chord $ j $, with $ s_{i,i} = 0 $.  \nLet $ C = (c_1, c_2, \\dots, c_n) \\in \\{1, \\dots, k\\}^n $ be the sequence of chords in the song.  \n\nLet $ D = (d_{i,j}) \\in \\mathbb{R}^{k \\times k} $ be the shortest-path transition matrix computed via Floyd-Warshall:  \n$$ d_{i,j} = \\min_{\\text{paths } i \\to j} \\sum \\text{edge weights} $$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq k \\leq 100 $  \n3. $ 1 \\leq s_{i,j} \\leq 10^9 $ for all $ i,j \\in \\{1,\\dots,k\\} $  \n4. $ s_{i,i} = 0 $ for all $ i $  \n5. The song sequence $ C $ is fixed except for **at most one** chord that may be changed to any other chord in $ \\{1,\\dots,k\\} $.\n\n**Objective**  \nCompute the minimum total time to play the song, where:  \n- Base time (without any change):  \n  $$ T_0 = \\sum_{i=1}^{n-1} d_{c_i, c_{i+1}} $$  \n- For each position $ p \\in \\{1, \\dots, n\\} $ and each possible replacement chord $ x \\in \\{1, \\dots, k\\} $, define:  \n  - If $ p = 1 $: $ T_p^x = d_{x, c_2} + \\sum_{i=2}^{n-1} d_{c_i, c_{i+1}} $  \n  - If $ p = n $: $ T_p^x = d_{c_{n-1}, x} + \\sum_{i=1}^{n-2} d_{c_i, c_{i+1}} $  \n  - If $ 1 < p < n $: $ T_p^x = d_{c_{p-1}, x} + d_{x, c_{p+1}} + \\sum_{\\substack{i=1 \\\\ i \\neq p-1, p}}^{n-1} d_{c_i, c_{i+1}} $  \n- Let $ T_{\\text{min}} = \\min\\left( T_0,\\ \\min_{p \\in \\{1,\\dots,n\\},\\ x \\in \\{1,\\dots,k\\}} T_p^x \\right) $\n\n**Output**  \n$ T_{\\text{min}} $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}