Ecrade has an integer $$$x$$$. He will show you this number in the form of a binary number of length $$$n$$$.

There are two kinds of operations.

Replace $$$x$$$ with $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$, where $$$\left\lfloor \dfrac{x}{2}\right\rfloor$$$ is the greatest integer $$$\le \dfrac{x}{2}$$$.
Replace $$$x$$$ with $$$\left\lceil \dfrac{x}{2}\right\rceil$$$, where $$$\left\lceil \dfrac{x}{2}\right\rceil$$$ is the smallest integer $$$\ge \dfrac{x}{2}$$$.

Ecrade will perform several operations until $$$x$$$ becomes $$$1$$$. Each time, he will independently choose to perform either the first operation or the second operation with probability $$$\frac{1}{2}$$$.

Ecrade wants to know the expected number of operations he will perform to make $$$x$$$ equal to $$$1$$$, modulo $$$10^9 + 7$$$. However, it seems a little difficult, so please help him!

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$x$$$ in binary representation.

The second line of each test case contains a binary string of length $$$n$$$: the number $$$x$$$ in the binary representation, presented from the most significant bit to the least significant bit. It is guaranteed that the most significant bit of $$$x$$$ is $$$1$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single integer representing the expected number of operations Ecrade will perform to make $$$x$$$ equal to $$$1$$$, modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Note

For simplicity, we call the first operation $$$\text{OPER 1}$$$ and the second operation $$$\text{OPER 2}$$$.

In the first test case, $$$x=6$$$, and there are six possible series of operations:

$$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 1}} 1$$$, the probability is $$$\dfrac{1}{4}$$$.
$$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$, the probability is $$$\dfrac{1}{8}$$$.
$$$6 \xrightarrow{\text{OPER 1}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$, the probability is $$$\dfrac{1}{8}$$$.
$$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 1}} 1$$$, the probability is $$$\dfrac{1}{4}$$$.
$$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 1}} 1$$$, the probability is $$$\dfrac{1}{8}$$$.
$$$6 \xrightarrow{\text{OPER 2}} 3 \xrightarrow{\text{OPER 2}} 2 \xrightarrow{\text{OPER 2}} 1$$$, the probability is $$$\dfrac{1}{8}$$$.

Thus, the expected number of operations is $$$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}$$$.

Math Division

Examples