A. Вырезание и вставка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мы начинаем со строки $$$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$$$. Затем, исполняется следующая процедура:

  1. Применить передвижение один раз.
  2. Применить вырезание один раз.
  3. Несколько применить вставку, количество раз равно $$$s_\ell$$$.
  4. Если $$$\ell = x$$$, остановиться. Иначе, вернуться к шагу 1.

Вам дана изначальная строка $$$s$$$ и целое число $$$x$$$. Какой будет длина строки $$$s$$$ когда процедура остановится? Так как это число может быть очень большим, выведите его остаток при делении на $$$10^9 + 7$$$.

Гарантируется, что $$$\ell \le |s|$$$ в любой момент времени.

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$), количество наборов входных данных. В следующих строках находятся их описания.

В первой строке каждого набора входных данных записано единственное целое число $$$x$$$ ($$$1 \le x \le 10^6$$$). Во второй строке находится изначальная строка $$$s$$$ ($$$1 \le |s| \le 500$$$). Гарантируется, что $$$s$$$ состоит только из символов «1», «2», «3».

Гарантируется, что сумма $$$x$$$ по всем тестовым случаям не превосходит $$$10^6$$$. Гарантируется, что во всех тестовых случаях во время процедуры $$$\ell \le |s|$$$ в любой момент времени.

Выходные данные

Для каждого тестового случая, выведите остаток при делении длины строки после процедуры на $$$10^9 + 7$$$.

Пример
Входные данные
4
5
231
7
2323
6
333
24
133321333
Выходные данные
25
1438
1101
686531475
Примечание

Давайте проиллюстрируем, что происходит в первом тестовом случае. Изначально у нас $$$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$$$.