전등 끄기

직선 위에 $n$개의 전등이 놓여 있고, 왼쪽에서 오른쪽으로 $1$번부터 $n$번까지 번호가 매겨져 있다. 처음에는 일부 전등이 켜져 있다. 치아키는 모든 전등을 끄려고 한다.

치아키는 $p$번 전등에서 출발한다. 한 번의 동작에서 왼쪽이나 오른쪽으로 한 칸 이동한 뒤, 그 위치 전등의 스위치를 누른다. 스위치를 누르면 켜져 있던 전등은 꺼지고, 꺼져 있던 전등은 켜진다.

각 $p=1,2,\dots,n$에 대해, 모든 전등을 끄는 데 필요한 최소 동작 횟수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 전등의 개수 $n$ ($2 \le n \le 10^6$)이 주어진다.

둘째 줄에 이진 문자열 $s$가 주어진다. $s_i=1$이면 $i$번 전등이 켜져 있고, $s_i=0$이면 꺼져 있다.

모든 테스트 케이스의 $n$을 합한 값은 $10^7$을 넘지 않는다.

각 테스트 케이스에 대해 $\left(\sum_{i=1}^{|s|} i \times z_i\right) \bmod (10^9+7)$을 출력한다. 여기서 $z_i$는 치아키가 $i$번 전등에서 출발할 때 필요한 최소 동작 횟수이다.