{"problem":{"name":"H. Log Concave Sequences","description":{"content":"A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2. For example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10230H"},"statements":[{"statement_type":"Markdown","content":"A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2.\n\nFor example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = (2, 2, 3) is not logarithm concave.\n\nIn this problem, you will have to answer what is the number of log concave sequences which contain only the numbers 0, 1 or 2, with N elements.\n\nAs this number could be very large, print the answer mod 109 + 7.\n\nThe input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence.\n\nOne integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2.\n\n## Input\n\nThe input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence.\n\n## Output\n\nOne integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A, B \\in \\mathbb{Z} $ with $ 1 \\leq A, B \\leq 28 $.  \nLet $ O_1, O_2, O_3 \\in \\Sigma^A $ be the strings of the three Owls members, where $ \\Sigma = \\{ \\text{'A'}, \\text{'B'}, \\dots, \\text{'Z'} \\} $.  \nLet $ G_1, G_2, G_3 \\in \\Sigma^B $ be the strings of the three Goats members.  \n\nFor a string $ S \\in \\Sigma^n $, define the score:  \n$$\n\\text{score}(S) = \\left( \\sum_{i=1}^{n} \\text{val}(S[i]) \\right) \\mod M, \\quad \\text{where } M = 10^{15} + 37, \\quad \\text{val}(c) = \\text{ASCII}(c)\n$$\n\n**Constraints**  \nFor each position $ i \\in \\{1, \\dots, A\\} $, the Owls' resulting string $ S_O $ must satisfy:  \n$$\nS_O[i] \\in \\{ O_1[i], O_2[i], O_3[i] \\}\n$$  \nFor each position $ i \\in \\{1, \\dots, B\\} $, the Goats' resulting string $ S_G $ must satisfy:  \n$$\nS_G[i] \\in \\{ G_1[i], G_2[i], G_3[i] \\}\n$$\n\n**Objective**  \nMinimize $ \\text{score}(S_O) $ over all valid $ S_O \\in \\Sigma^A $, and minimize $ \\text{score}(S_G) $ over all valid $ S_G \\in \\Sigma^B $.  \nCompare the minimal scores:  \n- If $ \\min \\text{score}(S_O) < \\min \\text{score}(S_G) $, output \"Owls\"  \n- If $ \\min \\text{score}(S_O) > \\min \\text{score}(S_G) $, output \"Goats\"  \n- If $ \\min \\text{score}(S_O) = \\min \\text{score}(S_G) $, output \"Tie\"","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10230H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}