A. 数学除法
每次测试的时间限制：2 秒
每次测试的内存限制：512 兆字节

Ecrade 有一个整数 $x$。他会以长度为 $n$ 的二进制数的形式向你展示这个数。

有两种操作：

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

Ecrade 会执行若干次操作，直到 $x$ 变成 $1$。每次操作，他会独立地以 $\frac{1}{2}$ 的概率选择第一种操作，以 $\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$。

所有测试用例的 $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 < M$ 且 $x \cdot q \equiv p \pmod{M}$。

---

示例

输入

3
3
110
3
100
10
1101001011

输出

500000006
2
193359386

---

提示
为简单起见，我们将第一种操作称为“操作 1”，第二种操作称为“操作 2”。

在第一个测试用例中，$x = 6$，共有 6 种可能的操作序列：

• $6 \xrightarrow{\text{操作 1}} 3 \xrightarrow{\text{操作 1}} 1$，概率为 $\frac14$。
• $6 \xrightarrow{\text{操作 1}} 3 \xrightarrow{\text{操作 2}} 2 \xrightarrow{\text{操作 1}} 1$，概率为 $\frac18$。
• $6 \xrightarrow{\text{操作 1}} 3 \xrightarrow{\text{操作 2}} 2 \xrightarrow{\text{操作 2}} 1$，概率为 $\frac18$。
• $6 \xrightarrow{\text{操作 2}} 3 \xrightarrow{\text{操作 1}} 1$，概率为 $\frac14$。
• $6 \xrightarrow{\text{操作 2}} 3 \xrightarrow{\text{操作 2}} 2 \xrightarrow{\text{操作 1}} 1$，概率为 $\frac18$。
• $6 \xrightarrow{\text{操作 2}} 3 \xrightarrow{\text{操作 2}} 2 \xrightarrow{\text{操作 2}} 1$，概率为 $\frac18$。

因此，操作次数的期望值为

$$2 \cdot \frac14 + 3 \cdot \frac18 + 3 \cdot \frac18 + 2 \cdot \frac14 + 3 \cdot \frac18 + 3 \cdot \frac18 = \frac52 \equiv 500000006 \pmod{10^9 + 7}. $$