题目内容

给定一个仅由$'0/1'$组成的字符串 $s$。对任意一个（不为空）子序列$t$，记其长度为$|t|$、其中字符 $'1'$的数量为 x。若满足$|t|$ 是 x 的倍数且$x$不为 $0$，则称 t 为 “好的”。

请你统计 $s$中 “好的” 子序列的个数。注意，如果两个子序列是通过选取原字符串中不同位置的字符集合得到的，那么即使它们构成的字符串相同，也应被视为不同的子序列。由于答案可能很大，请将答案对 $(10^9+7)$取模后输出。

【子序列】定义 子序列为从原字符串中删除任意个（可以为零）字符得到的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1≤T≤2×10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入整数$n (1≤n≤2×10^5)$表示字符串长度；
• 第二行输入一个只包含 $'0/1'$的字符串 $s$。

保证所有测试中 $n$的总和不超过 $5×10^5$

输出描述

对于每组测试数据，输出一个整数，表示 $s$ 的 “不同好的子序列” 的个数。

由于答案可能很大，输出对 $10^9+7$取模的结果

样例1

输入

3
3
101
2
00
2
01

输出

5
0
2

说明

样例一：$s$="$101$"，符合的子序列（用位置集合表示）：{$1$}, {$3$}, {$1,2$}, {$2,3$}, {$1,3$}。

样例二：$s$="$00$"，无符合子序列（因 $x=0$不计）。

样例三：$s$="$01$"，符合的子序列：{$2$}, {$1,2$}。