Turn Off The Light

There are $n$ lights in a row, numbered $1$ to $n$ from left to right. Some of the lights are on at the start. Chiaki wants to turn off all the lights.

Chiaki starts at the $p$-th light. Each step, she moves one position to the left or to the right, then presses the switch of the light at her new position. Pressing a switch turns a lit light off and an unlit light on.

For each $p=1,2,\dots,n$, find the minimum number of steps needed to turn off all the lights.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

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$. If $s_i=1$, the $i$-th light is on. If $s_i=0$, the $i$-th light is off.

The sum of $n$ over all test cases does not exceed $10^7$.

For each test case, print $\left(\sum_{i=1}^{|s|} i \times z_i\right) \bmod (10^9+7)$, where $z_i$ is the minimum number of steps needed when Chiaki starts at the $i$-th light.