序列
题号：NC276697
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有一个长度为  的  串 ，你需要重复如下操作  次：

  • 设  为当前  的长度。选择一个 ，使得 s_is_{i+1}s_{i+2}s_{i+3}=0011，并将 s_i,s_{i+1},s_{i+2},s_{i+3} 删去。假如这是第 j 次操作，记 x_j=i。

请求出有多少种不同的将整个字符串删空的方案，答案对 10^9+7 取模。认为两种方案不同，当且仅当存在一个 ，使得两种方案的 x_j 不相等。

输入描述:

本题有多组数据。
第一行，一个正整数 。
接下来，对于每组数据：
  • 第一行，一个正整数 ；
  • 第二行，一个长为  的字符串 。

输出描述:

T 行，每行一个非负整数，表示答案。
示例1

输入

复制 
4
1
1001
2
00110011
5
00000000011111101111
5
00011000111100110011

输出

复制 
0
2
1
40

备注:

记  为单个测试点中所有数据的  之和。
  • ；
  • 。