{"raw_statement":[{"iden":"statement","content":"It was a long time since Informikas has had something to do with recursions and this had to be fixed. For that reason he decided to come up with some recursion and later solve it all by himself.\n\nThe first recursion Informikas managed to come up was\n\n\n\n\"Nah, too easy\", he told to himself, crumpled the paper and threw it to a trash can.\n\n\n\n\"Squaring is overrated. Still too easy\", he thought while the paper was flying towards a trash can.\n\n\n\n\"Oh no, what have I done! This recursion has no terminating condition! It's too hard even for me!\", Informikas shouted out loud. \n\nCould you be so kind and, given the value of a, help out Informikas by finding the value of h(0).\n\nSingle integer a (0 ≤ a ≤ 1018).\n\nCalculate the integer part of h(0). As the answer can be quite a large number, output it modulo 109 + 7 (1000000007). In cases when the recursion goes infinitely long, output \"Nobody got time for that\" (without quotation marks).\n\n"},{"iden":"input","content":"Single integer a (0 ≤ a ≤ 1018)."},{"iden":"output","content":"Calculate the integer part of h(0). As the answer can be quite a large number, output it modulo 109 + 7 (1000000007). In cases when the recursion goes infinitely long, output \"Nobody got time for that\" (without quotation marks)."},{"iden":"examples","content":"Input0Output1Input1Output2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the dimension of the square matrix.  \n- Let $ W_k \\in \\mathbb{Z} $ denote the upper bound on the submatrix sum.  \n- Let $ A_k = (a_{i,j}^{(k)})_{i,j=1}^{N_k} $ be an $ N_k \\times N_k $ matrix with positive integer entries.  \n\nFor a square submatrix of size $ s \\times s $ with top-left corner at $ (i,j) $, define its **diagonal sum** as:  \n$$\nS(i,j,s) = \\sum_{d=0}^{s-1} a_{i+d,j+d}^{(k)} + \\sum_{d=0}^{s-1} a_{i+d,j+s-1-d}^{(k)} - \\delta \\cdot a_{i+\\lfloor (s-1)/2 \\rfloor, j+\\lfloor (s-1)/2 \\rfloor}^{(k)}\n$$  \nwhere $ \\delta = 1 $ if $ s $ is odd (to avoid double-counting the center), and $ \\delta = 0 $ otherwise.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 20 $  \n2. For each test case $ k $:  \n   - $ 1 \\le N_k \\le 1000 $  \n   - $ W_k $ is a 32-bit signed integer  \n   - $ 1 \\le a_{i,j}^{(k)} \\le 2^{31}-1 $ for all $ i,j $  \n\n**Objective**  \nFor each test case $ k $, find the maximum integer $ s \\in \\{1, \\dots, N_k\\} $ such that there exists a top-left corner $ (i,j) $ with $ 1 \\le i \\le N_k - s + 1 $, $ 1 \\le j \\le N_k - s + 1 $, and  \n$$\nS(i,j,s) \\le W_k\n$$  \nIf no such submatrix exists, output 0.","simple_statement":"Find the largest square submatrix whose diagonal sum (main + secondary, count center once) is ≤ W.","has_page_source":false}