CF2081A Math Division

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. 1. 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} $ . 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!

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 $ .

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 < M $ and $ x \cdot q \equiv p \pmod{M} $ .

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} $ .