{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"An integer $n$ ($0 <= n <= 10^(18)$)."},{"iden":"output","content":"Print the answer modulo $1000000007$."},{"iden":"examples","content":"Input3\nOutput2\nInput6\nOutput8\nInput50\nOutput586268941\n"},{"iden":"note","content":"The 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}$$"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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}} $","simple_statement":"Timmy must play a song of n chords in order. He can switch between any two chords with a given time cost. He can change at most one chord in the song to any other chord to minimize total transition time. Find the minimum possible total time.","has_page_source":false}