湫秋系列故事——安排座位

Time Limit: 20000/10000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

  为了给腾讯公司找到更多优秀的人才,HR湫秋最近去某高校组织了一次针对该校所有系的聚会,邀请了每个系的一些优秀学生来参加。

  作为组织者,湫秋要安排他们的座位。这并不是一件很简单的事情,因为只有一排位置,并且位置总数恰好等于参加聚会的人数。为了促进交流,两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法(任意两个合理的安排方法,只要有一个位置的同学不同,都被认为是不同的)。

Input

输入第一行为T,表示有T组测试数据。
每组数据一个N开始,表示一共有多少个系。下面的一行包含N个整数Ai,表示每个系的到场人数。

[Technical Specification]
1. 1 <= T <= 47
2. 1 <= N, Ai <= 47
3. 1 <= Sum(Ai) <= 447

Output

对每组数据,先输出为第几组数据,然后输出结果。由于结果可能很大,输出对1,000,000,007 取余后的结果。

Sample Input

3 2 1 2 2 1 3 3 1 2 3

Sample Output

Case 1: 2 Case 2: 0 Case 3: 120

Hint

liuyiding

Source

2013腾讯编程马拉松复赛第一场(3月29日)

提交代码