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,…,n, Chiaki would like to know the minimum steps needed to turn off all the lights.
Input
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≤n≤106) -- the number of lights. The second line contains a binary string s where si=1 means the i-th light is turned on and si=0 means i-th light is turned off. It is guaranteed that the sum of all n does not exceed 107.
Output
For each test cases, output (∑i=1|s|i×zi)mod(109+7), where zi is the number of step needed when Chikai starts at the i-th light.