시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 0 0 0 0.000%

문제

There are $n$ lights aligned in a row. These lights are numbered $1$ to $n$ from left to right. Initially some of the lights are turned on. Chiaki would like to turn off all the lights.

Chiaki starts from the $p$-th light. Each time she can go left or right (i.e. if Chiaki is at $x$, then she can go to $x-1$ or $x+1$) and then press the switch of the light in that position (i.e. if the light is turned on before, it will be turned off and vise versa).

For each $p=1,2,\dots,n$, Chiaki would like to know the minimum steps needed to turn off all the lights.

입력

There are multiple test cases. The first line of input is an integer $T$ indicates the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 10^6$) -- the number of lights.

The second line contains a binary string $s$ where $s_i=1$ means the $i$-th light is turned on and $s_i=0$ means $i$-th light is turned off.

It is guaranteed that the sum of all $n$ does not exceed $10^7$.

출력

For each test cases, output $(\sum\limits_{i=1}^{|s|} i \times z_i) \bmod (10^9+7)$, where $z_i$ is the number of step needed when Chikai starts at the $i$-th light.

예제 입력 1

3
3
000
3
111
8
01010101


예제 출력 1

0
26
432