题目内容

给定一个仅由字符 0 和 1 组成的序列 $s$。现在要从 $s$ 中任意选取一个子序列（即删除零个或多个元素后保持原来顺序的序列）。设该子序列的长度为 $L$，其中包含的字符 1 的个数为 $k$。如果 $k > 0$ 且 $L$ 是 $k$ 的整数倍，则称该子序列是 和谐的。

请注意，如果两个子序列选取的元素位置集合不同，即使它们构成的字符串相同，也视为不同的子序列。请你统计 $s$ 中所有和谐子序列的个数。由于答案可能很大，请将结果对 1000000007（即 $10^9+7$）取模后输出。

本题包含多组测试数据。单个字符串的长度 $n$ 不超过 200000（即 $2 \times 10^5$），所有测试数据中 $n$ 的总和不超过 500000（即 $5 \times 10^5$），测试数据组数 $T$ 不超过 200000。

输入描述

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

接下来对于每组测试数据：

第一行包含一个整数 $n$，表示序列的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，字符串仅由字符 0 和 1 构成。

输出描述

对于每组测试数据，输出一行一个整数，表示对应序列中和谐子序列的个数对 $10^9+7$ 取模的结果。

样例1

输入

2
1
1
1
0

输出

1
0

说明

对于第一组数据，序列为 1，$cnt1 = 1$，$cnt0 = 0$。只能选择 $x = 1$ 个 1，方案数为 $\binom{1}{1} = 1$；此时必须选择 $0$ 个 0（因为 $0$ 是 $1$ 的倍数），方案数为 $\binom{0}{0} = 1$。因此和谐子序列总数为 1。唯一的和谐子序列是 1 本身。 对于第二组数据，序列为 0，$cnt1 = 0$。因为没有字符 1，无法构成 $k > 0$ 的和谐子序列，答案为 0。

样例2

输入

2
3
111
4
1010

输出

7
10

说明

第一组数据，序列 111 中 $cnt1 = 3$，$cnt0 = 0$。枚举 $x$：

• $x = 1$：选 1 的方案 $\binom{3}{1} = 3$，选 0 的方案 $\binom{0}{0} = 1$，贡献 $3$。
• $x = 2$：选 1 的方案 $\binom{3}{2} = 3$，选 0 的方案 $\binom{0}{0} = 1$，贡献 $3$。
• $x = 3$：选 1 的方案 $\binom{3}{3} = 1$，选 0 的方案 $\binom{0}{0} = 1$，贡献 $1$。 总和为 $3 + 3 + 1 = 7$，即 7。

第二组数据，序列 1010 中 $cnt1 = 2$，$cnt0 = 2$。

• $x = 1$：选 1 的方案 $\binom{2}{1} = 2$；选 0 的个数 $y$ 可以是 $0, 1, 2$，方案为 $\binom{2}{0} + \binom{2}{1} + \binom{2}{2} = 4$。贡献 $2 \times 4 = 8$。
• $x = 2$：选 1 的方案 $\binom{2}{2} = 1$；合法 $y$ 为 $0, 2$，方案为 $\binom{2}{0} + \binom{2}{2} = 2$。贡献 $1 \times 2 = 2$。 总和为 $8 + 2 = 10$，即 10。

样例3

输入

1
5
11001

输出

19

说明

序列 11001 中 1 有 $cnt1 = 3$ 个，0 有 $cnt0 = 2$ 个。

• $x = 1$：选 1 的方案 $\binom{3}{1} = 3$；可选 0 的数量 $y$ 为 $0, 1, 2$，方案数 $\binom{2}{0} + \binom{2}{1} + \binom{2}{2} = 4$，贡献 $12$。
• $x = 2$：选 1 的方案 $\binom{3}{2} = 3$；$y$ 为 $0, 2$，方案数 $\binom{2}{0} + \binom{2}{2} = 2$，贡献 $6$。
• $x = 3$：选 1 的方案 $\binom{3}{3} = 1$；$y$ 只能为 $0$，贡献 $1$。 总和为 $12 + 6 + 1 = 19$，即 19。