Problem 3504 --Permutation Counting

3504: Permutation Counting

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

For a given permutation a1,a2,⋯,anof length n, we defined the neighbor sequence bof 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,5is 0,0,0,1,0.
Now we give you an integer nand a sequence b1,b2,⋯,bn−1of length n−1, you should calculate the number of permutations of length nwhose neighbor sequence equals to b.

To avoid calculation of big number, you should output the answer module 109+7. 

Input

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−1integer: b1,b2,⋯,bn−1
There are no more than 20cases with n>300.

Output

For each test case:
Output one integer indicating the answer module 109+7. 

Sample Input复制

2
3
1 0
5
1 0 0 1

Sample Output复制

2
11

推荐代码 查看3504 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛