Ученые Берляндии разработали новый передовой защищенный отечественный язык программирования LOCALC++. В целом, этот язык является клоном языка C++ с той лишь разницей, что в LOCALC++ числа выводятся в консоль с разделителями.
В данной задаче рассматриваются только неотрицательные целые числа. При выводе число разбивается на группы из трех цифр, начиная с младших разрядов, и каждая группа отделяется пробелом. Например, число $178489$ будет выведено в виде $178 " "489$, число $17009$ в виде $17 " "009$, а число $5$ будет выведено в таком же виде.
Программа управления атомными электростанциями Берляндии, написанная на LOCALC++, вывела в лог очень важную статистику в виде набора чисел через пробел. Известно, что исходные числа были строго меньше $10^K$. Необходимо определить количество различных наборов чисел, вывод которых бы привел к такому же логу.
В первой строке задано число $N$, определяющее количество входных групп цифр и число $K$ ($1 <= N <= 2 dot.op 10^5$, $3 <= K <= 6 dot.op 10^5$).
Во второй строке задано $N$ групп цифр через пробел — лог программы управления атомными электростанциями Берляндии.
Необходимо вывести количество возможных исходных наборов чисел c учетом того, что они могли быть только строго меньше $10^K$. Гарантируется, что хотя бы один такой набор существует. Так как результат может быть достаточно большим, его необходимо вывести по модулю $10^9 + 7$.
## Входные Данные
В первой строке задано число $N$, определяющее количество входных групп цифр и число $K$ ($1 <= N <= 2 dot.op 10^5$, $3 <= K <= 6 dot.op 10^5$).Во второй строке задано $N$ групп цифр через пробел — лог программы управления атомными электростанциями Берляндии.
## Выходные Данные
Необходимо вывести количество возможных исходных наборов чисел c учетом того, что они могли быть только строго меньше $10^K$. Гарантируется, что хотя бы один такой набор существует. Так как результат может быть достаточно большим, его необходимо вывести по модулю $10^9 + 7$.
## Примеры
Входные данные8 7
10 500 303 4 507 89 654 003
Выходные данные6
Входные данные3 6
328 032 0
Выходные данные1
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of digit groups in the log.
Let $ K \in \mathbb{Z}^+ $ be the upper bound exponent such that each original number satisfies $ 0 \leq x < 10^K $.
Let $ 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 $.
Let $ L_i = |g_i| $ be the length of group $ g_i $.
**Constraints**
1. $ 1 \leq N \leq 2 \times 10^5 $
2. $ 3 \leq K \leq 6 \times 10^5 $
3. For each $ i \in \{1, \dots, N\} $: $ 1 \leq L_i \leq 3 $
4. Each original number $ x_j $ satisfies $ 0 \leq x_j < 10^K $
**Objective**
Determine 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 $.
Each 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.
Let $ m $ be the number of numbers in the original sequence (unknown). The grouping of $ G $ into $ m $ numbers must be such that:
- Each number is formed by concatenating one or more consecutive groups from $ G $,
- The total number of digits in each number is at most $ K $,
- The rightmost group of each number has length 1, 2, or 3 (as required),
- The concatenation of all groups in order yields $ G $.
Let $ dp[i] $ be the number of ways to partition the first $ i $ groups into valid numbers (each of length ≤ $ K $ digits).
Then:
$$
dp[0] = 1
$$
$$
dp[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]
$$
But 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:
- The total number of digits in a number formed by concatenating groups $ g_{j+1}, \dots, g_i $ must be ≤ $ K $.
Thus, 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] $.
**Final Objective**
Compute $ dp[N] \mod (10^9 + 7) $, where:
$$
dp[i] = \sum_{\substack{j = i - \min(i, \lceil K/3 \rceil) \\ \sum_{k=j+1}^i L_k \leq K}}^{i-1} dp[j]
$$
with $ dp[0] = 1 $.