Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

F. Fun Times
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a set $$$\mathcal{A}$$$ of integers from $$$0$$$ to $$$n - 1$$$, define the value $$$f(\mathcal{A})$$$ as follows. The set undergoes $$$n - 1$$$ steps: at step $$$i$$$ ($$$1 \le i \le n - 1$$$), each element $$$x$$$ of the current set is replaced with $$$(x + 1) \bmod (n - i)$$$. Note that all elements are replaced simultaneously and are kept in the set only once, so after a step the size of the set may decrease.

Let $$$\mathcal{A}_i$$$ denote the set obtained after the $$$i$$$-th step. Then $$$f(\mathcal{A})$$$ is the sum of the values of $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$ of all obtained sets: $$$$$$f(\mathcal{A}) = \operatorname{mex}(\mathcal{A}_1) + \operatorname{mex}(\mathcal{A}_2) + \ldots + \operatorname{mex}(\mathcal{A}_{n - 1}).$$$$$$

Dima has a set $$$\mathcal{S}$$$ consisting of distinct integers from $$$0$$$ to $$$n - 1$$$.

Dima wants to find the sum of $$$f(\mathcal{S}')$$$ over all sets $$$\mathcal{S}'$$$ such that $$$\mathcal{S} \subseteq \mathcal{S}' \subseteq \{0, 1, \ldots, n - 1\}$$$. In other words, he wants the sum of $$$f$$$ over all supersets of $$$\mathcal{S}$$$ contained in $$$\{0, 1, \ldots, n - 1\}$$$. Please help him.

Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line contains a binary string $$$s$$$ of length $$$n$$$, representing the set $$$\mathcal{S}$$$. For each $$$0 \le i \lt n$$$, the integer $$$i$$$ belongs to $$$\mathcal{S}$$$ if and only if the $$$(i+1)$$$-th character of $$$s$$$ is 1.

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

Output

For each test case, output one integer — the required sum modulo $$$10^9 + 7$$$.

Example
Input
4
5
10110
3
000
9
101010101
6
000111
Output
30
14
306
78
Note

In the first example, there are only $$$4$$$ sets containing the given $$$\mathcal{S}$$$ as a subset: $$$\{0, 2, 3\}$$$, $$$\{0, 1, 2, 3\}$$$, $$$\{0, 2, 3, 4\}$$$, and $$$\{0, 1, 2, 3, 4\}$$$.

For the set $$$\mathcal{A} = \{0, 2, 3\}$$$, the sequence of transformations is as follows: $$$$$$\{0, 2, 3\} \to \{0, 1, 3\} \to \{1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ The values of $$$\operatorname{mex}$$$ of the obtained sets are $$$2, 0, 2, 1$$$, respectively, so: $$$$$$f(\{0, 2, 3\}) = 2 + 0 + 2 + 1 = 5.$$$$$$

For the set $$$\mathcal{A} = \{0, 1, 2, 3\}$$$: $$$$$$\{0, 1, 2, 3\} \to \{0, 1, 2, 3\} \to \{0, 1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 1, 2, 3\}) = 4 + 3 + 2 + 1 = 10.$$$$$$

For the set $$$\mathcal{A} = \{0, 2, 3, 4\}$$$: $$$$$$\{0, 2, 3, 4\} \to \{0, 1, 3\} \to \{1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 2, 3, 4\}) = 2 + 0 + 2 + 1 = 5.$$$$$$

For the set $$$\mathcal{A} = \{0, 1, 2, 3, 4\}$$$: $$$$$$\{0, 1, 2, 3, 4\} \to \{0, 1, 2, 3\} \to \{0, 1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 1, 2, 3, 4\}) = 4 + 3 + 2 + 1 = 10.$$$$$$

Thus, the final answer is the sum over these four sets: $$$$$$5 + 10 + 5 + 10 = 30.$$$$$$

In the second test case, $$$\mathcal{S}$$$ is empty, so all $$$8$$$ subsets of $$$\{0, 1, 2\}$$$ are considered. The value of $$$f$$$ is $$$0$$$ for the empty set, $$$1$$$ for each of $$$\{0\}$$$, $$$\{2\}$$$, and $$$\{0, 2\}$$$, $$$2$$$ for $$$\{1\}$$$, and $$$3$$$ for each of the remaining three sets. Thus, the answer is $$$0 + 3 \cdot 1 + 2 + 3 \cdot 3 = 14$$$.