### 问题描述 一个二进制字符串如果 "$01$" 子串数量和 "$10$" 子串数量相等，则称其为美丽的。 大衣有一个长度为 $N​$ 的二进制字符串 $S​$，他想知道字符串 $S​$ 中有多少个非空子序列是美丽的。 答案可能很大，将其对 $10^9+7​$ 取模。 ### 输入格式 第一行输入一个正整数 $T$ 表示测试数据的组数。 接下来 $T$ 组测试数据每组输入两行： - 第一行输入一个正整数 $N$ 表示二进制字符串 $S$ 的长度。 - 第二行输入一个长度为 $N$ 的二进制字符串 $S$。 ### 输出格式 对于每组测试数据，输出一个整数表示字符串 $S$ 中美丽的非空子序列的数量，答案可能很大，将其对 $10^9+7$ 取模，并换行。 ### 样例输入1 ```text 4 2 10 3 110 5 11111 8 10100110 ``` ### 样例输出1 ```text 2 4 31 122 ``` ### 说明 样例 $1$：字符串 $S$ 中美丽的非空子序列有 `{1，0}`，共 $2$ 个。 样例 $2$：字符串 $S$ 中美丽的非空子序列有 `{1,1,0,11}`，共 $4$ 个。 ### 评测数据规模 对于所有的评测数据，$1\le T\le 20$，$1\le N\le 10^4$，$S_i$ 为 $0$ 或 $1$。