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! 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)