{"raw_statement":[{"iden":"statement","content":"After gathering all the infinity stones and dusting half the population of the universe, Thanos went to gardens street. He decided to plant some flowers using the reality stone.\n\nSo Thanos now wants to plant $N$ flowers in least number of steps needed. In each step he can: Choose a number $(0 <= x)$,then Plant $10^x$ plants or remove $10^x$ plants with the help of the power stone. What is the least number of steps he needs to plant exactly $N$ flowers.\n\nA single integer $N$ $(0 <= N <= 10^(10^5))$, the number of flowers Thanos wants to plant.\n\nThe least number of steps Thanos needs to plant $N$ plants.\n\nIn the first sample, fastest way to plant 3000 plants is:\n\nstep 1 plant $10^3$\n\nstep 2 plant $10^3$\n\nstep 3 plant $10^3$\n\nso the answer is 3 steps.\n\n"},{"iden":"input","content":"A single integer $N$ $(0 <= N <= 10^(10^5))$, the number of flowers Thanos wants to plant."},{"iden":"output","content":"The least number of steps Thanos needs to plant $N$ plants."},{"iden":"examples","content":"Input3000\nOutput3Input231\nOutput6"},{"iden":"note","content":"In the first sample, fastest way to plant 3000 plants is:step 1 plant $10^3$step 2 plant $10^3$step 3 plant $10^3$so the answer is 3 steps."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq k < n \\leq 10^5 $, $ 1 \\leq m \\leq 2000 $.  \nThe Zoo is a cycle graph $ C_n $ with vertices $ \\{1, 2, \\dots, n\\} $, where edges connect $ i $ to $ i+1 \\mod n $.  \n\nFor any unordered pair $ \\{a, b\\} $ with $ a \\ne b $, define the two simple paths between $ a $ and $ b $:  \n- Clockwise path length: $ d_{\\text{cw}} = (b - a) \\mod n $  \n- Counterclockwise path length: $ d_{\\text{ccw}} = (a - b) \\mod n $  \nLet $ d = \\min(d_{\\text{cw}}, d_{\\text{ccw}}) $.  \n\nA valid pair $ (a, b) $ satisfies $ 1 \\leq d \\leq k $.  \nFor each such pair, the citizen chooses one of the two paths of length $ d $ (the shorter one, since $ d \\leq k $ and longer path $ > k $), and walks a closed loop starting and ending at $ a $, visiting all vertices on the chosen path, with total walk length $ \\leq m $.  \n\n**Constraints**  \n1. $ 1 \\leq k < n \\leq 10^5 $  \n2. $ 1 \\leq m \\leq 2000 $  \n3. For each valid $ (a, b) $, the chosen path has exactly $ d+1 $ vertices and $ d $ edges, $ 1 \\leq d \\leq k $.  \n4. The walk must:  \n   - Start and end at $ a $,  \n   - Traverse only the $ d $ edges of the chosen path,  \n   - Visit all $ d+1 $ vertices on the path,  \n   - Have total length $ \\leq m $.  \n\n**Objective**  \nCount the number of valid closed walks satisfying the above.  \n\nFor a fixed path of length $ d $ (i.e., $ d $ edges), the citizen must traverse a closed walk starting at $ a $, covering all $ d+1 $ vertices, using only the $ d $ edges of the path, and returning to $ a $. The only way to visit all vertices and return to start on a path graph is to traverse the path from $ a $ to $ b $, then back to $ a $, i.e., walk the path forward and backward — total length $ 2d $.  \n\nThus, for each pair $ (a, b) $ with distance $ d \\in [1, k] $, the *only* valid walk is the round-trip of length $ 2d $, and it is valid iff $ 2d \\leq m $.  \n\nNumber of unordered pairs $ \\{a, b\\} $ at distance $ d $ in $ C_n $: exactly $ n $ for each $ d \\in \\{1, 2, \\dots, \\lfloor n/2 \\rfloor\\} $.  \nSince $ d \\leq k < n/2 $ (because $ k < n $ and $ k \\geq 1 $, but $ n \\geq k+1 $, and we only consider $ d \\leq k $), all $ d \\in [1, k] $ have exactly $ n $ pairs.  \n\nThus, for each $ d \\in [1, \\min(k, \\lfloor m/2 \\rfloor)] $, there are $ n $ valid walks (one per pair).  \n\n**Answer:**  \n$$\n\\boxed{\n\\sum_{d=1}^{\\min(k, \\lfloor m/2 \\rfloor)} n \\mod (10^9 + 7)\n}\n$$","simple_statement":"You are given a circular zoo with n locations. Choose two different locations a and b, and pick one of the two paths between them (clockwise or counterclockwise) with length at most k. Then, walk from a to b along that path and return back to a, visiting all locations on the path exactly once, and the total walk length must be at most m. Count how many such walks are possible. Answer modulo 10^9 + 7.","has_page_source":false}