OpenJudge

10:Strange Card Game

总时间限制:
15000ms
内存限制:
262144kB
描述

You are playing a strange single-player card game. At the beginning, you have several cards. Each card has an integer rank in the range from 1 to N. In each turn, you can discard a non-empty subset of your cards in hand which satisfied one of the following rules:

  1. Four of a kind: Four cards with the same rank. For example, cards with rank 1 1 1 1 or 3 3 3 3;

  2. Consecutive full house: Five cards, three of them with the same rank and the other two with another same rank, and the difference between the two ranks is exactly 1. For example, cards with rank 2 2 2 3 3 or 4 4 5 5 5 is a Consecutive full house, but 2 2 2 4 4 is not;

  3. Five straight: Five cards with consecutive ranks, exactly one card for each rank. For example, cards with 1 2 3 4 5 or 4 5 6 7 8 is a Five straight, but 4 5 7 8 9 or 3 4 5 6 or 5 6 6 7 8 is not.

When there is no card in your hand, you win this game.

Now you are given a deck of cards. You want to know that, how many different subsets of the deck you can start with and win the game at last

Two subsets of the deck are considered the same if and only if they have the exact same number of cards for each rank.

输入
The first line contains an integer T (1 ≤ T ≤ 60), indicating the number of test cases.

For each test case:

The first line contains an integer N (1 ≤ N ≤ 1000), indicating range of the ranks of cards is from 1 to N.

The second line contains N integers, the i-th integer ai (0 ≤ ai ≤ 4) indicating the number of cards with rank i in the deck.
输出
For each test case, output an integer indicating the number of different subsets of the deck you can start with and win the game at last, module 1,000,000,007.
样例输入
1
5
2 3 1 3 4
样例输出
10
提示
In the Sample Output, 10 subsets are:

No.  Ranks of Cards            Comment
1    Empty
2    5 5 5 5
3    1 1 2 2 2
4    1 2 3 4 5
5    4 4 4 5 5
6    4 4 5 5 5
7    1 1 2 2 2 5 5 5 5        =1 1 2 2 2 + 5 5 5 5
8    1 1 2 2 2 4 4 4 5 5     =1 1 2 2 2 + 4 4 4 5 5
9    1 1 2 2 2 4 4 5 5 5     =1 1 2 2 2 + 4 4 5 5 5
10  1 2 3 4 4 4 5 5 5 5     =1 2 3 4 5 + 4 4 5 5 5
全局题号
10078
提交次数
5
尝试人数
1
通过人数
0