有 $n$ 盏灯排成一排，从左到右编号为 $1$ 到 $n$。初始时，其中一些灯是亮着的。Chiaki 想要关掉所有的灯。

Chiaki 从第 $p$ 盏灯开始。每次她可以向左或向右移动（即如果 Chiaki 在 $x$ 位置，她可以移动到 $x-1$ 或 $x+1$），然后按下该位置灯的开关（即如果灯之前是亮的，它会熄灭；反之亦然）。

对于每个 $p = 1, 2, \dots, n$，Chiaki 想知道关掉所有灯所需的最少步数。

输入格式

输入包含多组测试数据。第一行是一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示灯的数量。 第二行包含一个二进制字符串 $s$，其中 $s_i = 1$ 表示第 $i$ 盏灯是亮的，$s_i = 0$ 表示第 $i$ 盏灯是灭的。

保证所有 $n$ 的总和不超过 $10^7$。

输出格式

对于每组测试数据，输出 $(\sum_{i=1}^{|s|} i \times z_i) \pmod{10^9 + 7}$，其中 $z_i$ 是从第 $i$ 盏灯开始时关掉所有灯所需的最少步数。

样例

输入 1

3
3
000
3
111
8
01010101

输出 1

0
26
432