A. Математическое деление
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Экрада есть целое число $$$x$$$, заданное в виде двоичного представления длины $$$n$$$.

Существует два типа операций:

  1. Заменить $$$x$$$ на $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$, где $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$ — это наибольшее целое число $$$\le \dfrac{x}{2}$$$.
  2. Заменить $$$x$$$ на $$$\left\lceil \dfrac{x}{2}\right\rceil$$$, где $$$\left\lceil \dfrac{x}{2}\right\rceil$$$ — это наименьшее целое число $$$\ge \dfrac{x}{2}$$$.

Экрад выполнит несколько операций, пока $$$x$$$ не станет равным $$$1$$$. Каждый раз он будет независимо выбирать либо первую операцию, либо вторую операцию с вероятностью $$$\frac{1}{2}$$$.

Экрад хочет знать математическое ожидание количества операций, которые он выполнит, чтобы сделать $$$x$$$ равным $$$1$$$, по модулю $$$10^9 + 7$$$. Однако это оказалось слишком сложным для него, так что, пожалуйста, помогите ему!

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина $$$x$$$ в двоичном виде.

Вторая строка каждого набора входных данных содержит бинарную строку размера $$$n$$$ — двоичное представление $$$x$$$, записанное от старшего бита к младшему. Гарантируется, что старший бит $$$x$$$ равен $$$1$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — математическое ожидание количества операций, которое Экрад выполнит, чтобы сделать $$$x$$$ равным $$$1$$$ по модулю $$$10^9+7$$$.

Формально, пусть $$$M = 10^9+7$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x \lt M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Пример
Входные данные
3
3
110
3
100
10
1101001011
Выходные данные
500000006
2
193359386
Примечание

Для простоты мы будем называть первую операцию $$$\text{OPER 1}$$$, а вторую операцию $$$\text{OPER 2}$$$.

В первом наборе входных данных $$$x=6$$$, и существует шесть возможных последовательностей операций:

  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 1}} 1$$$, вероятность $$$\dfrac{1}{4}$$$.
  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$, вероятность $$$\dfrac{1}{8}$$$.
  • $$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$, вероятность $$$\dfrac{1}{8}$$$.
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 1}} 1$$$, вероятность $$$\dfrac{1}{4}$$$.
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$, вероятность $$$\dfrac{1}{8}$$$.
  • $$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$, вероятность $$$\dfrac{1}{8}$$$.

Таким образом, математическое ожидание количества операций равно $$$2 \cdot \dfrac{1}{4} + 3 \cdot \dfrac{1}{8} + 3 \cdot \dfrac{1}{8} + 2 \cdot \dfrac{1}{4} + 3 \cdot \dfrac{1}{8} + 3 \cdot \dfrac{1}{8} = \dfrac{5}{2} \equiv 500\,000\,006 \pmod{10^9 + 7}$$$.