18986번 - Turn Off The Light 다국어

문제

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.

제한

힌트