Мы начинаем со строки \(s\), состоящей только из цифр \(1\), \(2\) или \(3\). Будем обозначать длину строки \(s\) как \(|s|\). Для всех \(i\) от \(1\) до \(|s|\) \(i\)-й символ строки \(s\) обозначим как \(s_i\).
Где-то в строке стоит курсор. Позиция курсора \(\ell\) обозначается целым числом из множества \(\{0, \ldots, |s|\}\), и имеет следующее значение:
- если \(\ell = 0\), тогда курсор расположен перед первым символом строки \(s\).
- если \(\ell = |s|\), тогда курсор расположен после последнего символа строки \(s\).
- если \(0 < \ell < |s|\), тогда курсор расположен между символами \(s_\ell\) и \(s_{\ell+1}\).
Обозначим за \(s_\text{left}\) строку, находящуюся левее курсора и за \(s_\text{right}\) строку находящуюся правее курсора.
Также есть строка \(c\), которая называется буфером, которая изначально пуста. Всего существует три типа действий:
- Передвижение. Передвинуть курсор на один символ вправо. Это увеличивает \(\ell\) на единицу.
- Вырезание. Присвоить \(c \leftarrow s_\text{right}\), затем присвоить \(s \leftarrow s_\text{left}\).
- Вставка. Добавить значение \(c\) в конец строки \(s\). Заметьте, что это никак не меняет \(c\).
Изначально курсор находится в позиции \(\ell = 0\). Затем, исполняется следующая процедура:
- Применить передвижение один раз.
- Применить вырезание один раз.
- Несколько применить вставку, количество раз равно \(s_\ell\).
- Если \(\ell = x\), остановиться. Иначе, вернуться к шагу 1.
Вам дана изначальная строка \(s\) и целое число \(x\). Какой будет длина строки \(s\) когда процедура остановится? Так как это число может быть очень большим, выведите его остаток при делении на \(10^9 + 7\).
Гарантируется, что \(\ell \le |s|\) в любой момент времени.
Примечание
Давайте проиллюстрируем, что происходит в первом тестовом случае. Изначально у нас \(s = \) 231. Изначально, \(\ell = 0\) и \(c = \varepsilon\) (пустая строка). Вот как изменяются эти значения в ходе процедуры:
- Шаг 1, передвижение: мы получим \(\ell = 1\).
- Шаг 2, вырезание: мы получим \(s = \) 2 и \(c = \) 31.
- Шаг 3, вставка \(s_\ell = \) 2 раза: мы получим \(s = \) 23131.
- Шаг 4: \(\ell = 1 \not= x = 5\), поэтому мы переходим к 1.
- Шаг 1, передвижение: мы получим \(\ell = 2\).
- Шаг 2, вырезание: мы получим \(s = \) 23 и \(c = \) 131.
- Шаг 3, вставка \(s_\ell = \) 3 раза: мы получим \(s = \) 23131131131.
- Шаг 4: \(\ell = 2 \not= x = 5\), поэтому мы переходим к 1.
- Шаг 1, передвижение: мы получим\(\ell = 3\).
- Шаг 2, вырезание: мы получим \(s = \) 231 и \(c = \) 31131131.
- Шаг 3, вставка \(s_\ell = \) 1 раз: мы получим \(s = \) 23131131131.
- Шаг 4: \(\ell = 3 \not= x = 5\), поэтому мы переходим к 1.
- Шаг 1, передвижение: мы получим \(\ell = 4\).
- Шаг 2, вырезание: мы получим \(s = \) 2313 и \(c = \) 1131131.
- Шаг 3, вставка \(s_\ell = \) 3 раза: мы получим \(s = \) 2313113113111311311131131.
- Шаг 4: \(\ell = 4 \not= x = 5\), поэтому мы переходим к 1.
- Шаг 1, передвижение: мы получим \(\ell = 5\).
- Шаг 2, вырезание: мы получим \(s = \) 23131 и \(c = \) 13113111311311131131.
- Шаг 3, вставка \(s_\ell = \) 1 раз: мы получим \(s = \) 2313113113111311311131131.
- Шаг 4: \(\ell = 5 = x\), поэтому мы останавливаемся.
В конце процедуры, \(s\) имеет длину \(25\).