{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence."},{"iden":"output","content":"One integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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\"","simple_statement":"Given two teams, Owls and Goats, each with 3 members.  \nEach member has a string of ratings (letters 'A' to 'Z').  \n\nFor each position i in the team’s string, you pick one character from the same position i of any of the 3 members.  \nYou must build one string of length A for Owls, and one of length B for Goats.  \n\nThe score of a string is the sum of ASCII values of all its characters, modulo (10^15 + 37).  \n\nBoth teams choose their strings to get the **lowest possible score**.  \n\nCompare the two lowest scores.  \nOutput: \"Owls\", \"Goats\", or \"Tie\".","has_page_source":false}