P7603 - Permutation Counting

内存限制：128 MB 时间限制：6 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

提交提交记录统计 Web Board

For a given permutation

a1,a2,⋯,an of length

n, we defined the neighbor sequence

b of

a, the length of which is

n−1, as following:

bi={01ai<ai+1ai>ai+1

.

For example, the neighbor sequence of permutation

1,2,3,6,4,5 is

0,0,0,1,0.

Now we give you an integer

n and a sequence

b1,b2,⋯,bn−1 of length

n−1, you should calculate the number of permutations of length

n whose neighbor sequence equals to

b.

To avoid calculation of big number, you should output the answer module

109+7.

The first line contains one positive integer

T (

1≤T≤50), denoting the number of test cases. For each test case:
The first line of the input contains one integer

n,(2≤n≤5000).
The second line of the input contains

n−1 integer:

b1,b2,⋯,bn−1
There are no more than

20 cases with

n>300.

For each test case:

Output one integer indicating the answer module

109+7.

2
11

7603: Permutation Counting