A. Math Divisiontime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputEcrade 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!InputThe 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$$$.OutputFor 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 < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$. ExampleInput331103100101101001011Output500000006
2
193359386
NoteFor 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}$$$.