以下题面由 AI 翻译。

问题描述

Ecrade有一个整数$x$。他将用二进制形式展示这个数字，长度为$n$。

有两种操作：

1. 将$x$替换为$\left\lfloor \dfrac{x}{2}\right\rfloor$，其中$\left\lfloor \dfrac{x}{2}\right\rfloor$是小于等于$\dfrac{x}{2}$的最大整数。
2. 将$x$替换为$\left\lceil \dfrac{x}{2}\right\rceil$，其中$\left\lceil \dfrac{x}{2}\right\rceil$是最小的整数大于等于$\dfrac{x}{2}$。

Ecrade将进行多次操作，直到$x$变为1。每次操作，他独立选择执行第一种操作或第二种操作的概率均为$\frac{1}{2}$。

Ecrade想知道，使$x$等于1所需的期望操作次数是多少，并对结果取模$10^9 + 7$。然而，这个问题似乎有些困难，因此请帮助他！

输入格式

• 第一行包含一个整数$t$（$1 \le t \le 10^5$），表示测试用例的数量。
• 每个测试用例的第一行包含一个整数$n$（$1 \le n \le 10^5$），表示$x$的二进制表示长度。
• 每个测试用例的第二行包含一个长度为$n$的二进制字符串，表示$x$的二进制表示。该字符串从最高有效位到最低有效位排列。
• 保证$x$的最高有效位是1。

输出格式

对于每个测试用例，输出使$x$等于1所需的期望操作次数，并对结果取模$10^9 + 7$。

示例

输入：

3
3
110
3
100
10
1101001011

输出：

500000006
2
193359386

说明

对于第一个测试用例，$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} $$