{"raw_statement":[{"iden":"statement","content":"Ученые Берляндии разработали новый передовой защищенный отечественный язык программирования LOCALC++. В целом, этот язык является клоном языка C++ с той лишь разницей, что в LOCALC++ числа выводятся в консоль с разделителями.\n\nВ данной задаче рассматриваются только неотрицательные целые числа. При выводе число разбивается на группы из трех цифр, начиная с младших разрядов, и каждая группа отделяется пробелом. Например, число $178489$ будет выведено в виде $178 \" \"489$, число $17009$ в виде $17 \" \"009$, а число $5$ будет выведено в таком же виде.\n\nПрограмма управления атомными электростанциями Берляндии, написанная на LOCALC++, вывела в лог очень важную статистику в виде набора чисел через пробел. Известно, что исходные числа были строго меньше $10^K$. Необходимо определить количество различных наборов чисел, вывод которых бы привел к такому же логу.\n\nВ первой строке задано число $N$, определяющее количество входных групп цифр и число $K$ ($1 <= N <= 2 dot.op 10^5$, $3 <= K <= 6 dot.op 10^5$).\n\nВо второй строке задано $N$ групп цифр через пробел — лог программы управления атомными электростанциями Берляндии.\n\nНеобходимо вывести количество возможных исходных наборов чисел c учетом того, что они могли быть только строго меньше $10^K$. Гарантируется, что хотя бы один такой набор существует. Так как результат может быть достаточно большим, его необходимо вывести по модулю $10^9 + 7$.\n\n"},{"iden":"входные данные","content":"В первой строке задано число $N$, определяющее количество входных групп цифр и число $K$ ($1 <= N <= 2 dot.op 10^5$, $3 <= K <= 6 dot.op 10^5$).Во второй строке задано $N$ групп цифр через пробел — лог программы управления атомными электростанциями Берляндии."},{"iden":"выходные данные","content":"Необходимо вывести количество возможных исходных наборов чисел c учетом того, что они могли быть только строго меньше $10^K$. Гарантируется, что хотя бы один такой набор существует. Так как результат может быть достаточно большим, его необходимо вывести по модулю $10^9 + 7$."},{"iden":"примеры","content":"Входные данные8 7\n10 500 303 4 507 89 654 003\nВыходные данные6\nВходные данные3 6\n328 032 0\nВыходные данные1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of digit groups in the log.  \nLet $ K \\in \\mathbb{Z}^+ $ be the upper bound exponent such that each original number satisfies $ 0 \\leq x < 10^K $.  \nLet $ G = (g_1, g_2, \\dots, g_N) $ be the sequence of digit groups from the log, where each $ g_i $ is a string of digits (possibly with leading zeros), and $ 1 \\leq |g_i| \\leq 3 $.  \n\nLet $ L_i = |g_i| $ be the length of group $ g_i $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 2 \\times 10^5 $  \n2. $ 3 \\leq K \\leq 6 \\times 10^5 $  \n3. For each $ i \\in \\{1, \\dots, N\\} $: $ 1 \\leq L_i \\leq 3 $  \n4. Each original number $ x_j $ satisfies $ 0 \\leq x_j < 10^K $  \n\n**Objective**  \nDetermine the number of distinct sequences of non-negative integers $ (x_1, x_2, \\dots, x_N) $, where each $ x_j < 10^K $, such that when each $ x_j $ is formatted in LOCALC++ (grouped into triplets from the right, separated by spaces), the resulting string matches the input log $ G $.  \n\nEach group $ g_i $ corresponds to a 1-, 2-, or 3-digit segment of some $ x_j $, and the grouping must respect the rule: digits are split from the right into chunks of at most 3.  \n\nLet $ m $ be the number of numbers in the original sequence (unknown). The grouping of $ G $ into $ m $ numbers must be such that:  \n- Each number is formed by concatenating one or more consecutive groups from $ G $,  \n- The total number of digits in each number is at most $ K $,  \n- The rightmost group of each number has length 1, 2, or 3 (as required),  \n- The concatenation of all groups in order yields $ G $.  \n\nLet $ dp[i] $ be the number of ways to partition the first $ i $ groups into valid numbers (each of length ≤ $ K $ digits).  \n\nThen:  \n$$\ndp[0] = 1\n$$\n$$\ndp[i] = \\sum_{\\substack{j = \\max(0, i - \\lfloor K/3 \\rfloor) \\\\ \\text{and } \\sum_{k=j+1}^i L_k \\leq K}}^{i-1} dp[j] \\cdot \\mathbb{I}\\left[\\sum_{k=j+1}^i L_k \\leq K\\right]\n$$\n\nBut since each group has length ≤ 3, and we must form numbers by concatenating consecutive groups such that the total digit length of each number is ≤ $ K $, and the grouping must be consistent with the right-aligned triplet rule (i.e., the last group of a number can be 1, 2, or 3 digits — which it always is by input), the only constraint is:  \n- The total number of digits in a number formed by concatenating groups $ g_{j+1}, \\dots, g_i $ must be ≤ $ K $.  \n\nThus, for each $ i $, we consider all $ j < i $ such that the total digit length $ S = \\sum_{k=j+1}^i L_k \\leq K $, and add $ dp[j] $ to $ dp[i] $.  \n\n**Final Objective**  \nCompute $ dp[N] \\mod (10^9 + 7) $, where:  \n$$\ndp[i] = \\sum_{\\substack{j = i - \\min(i, \\lceil K/3 \\rceil) \\\\ \\sum_{k=j+1}^i L_k \\leq K}}^{i-1} dp[j]\n$$  \nwith $ dp[0] = 1 $.","simple_statement":"You are given N groups of digits, separated by spaces, representing a logged output from a program that prints numbers with space separators every 3 digits (from right). Each original number was strictly less than $10^K$. Count how many different original lists of numbers could have produced this exact logged output. Answer modulo $10^9 + 7$.","has_page_source":false}