Chef and Trump Cards SOLUTION
Gourmet specialist is playing a game with his companion Chefu. The standards of the game are as per the following:
There are two heaps of cards. One heap has a place with Chef and the other to Chefu. One or the two heaps might be unfilled.
At any second, each card utilized in the game has a positive number worth. At whatever point the estimation of a card becomes non-positive, it is taken out from the game.
The game is played in adjusts. In each round, every player all the while draws one card from the head of his heap.
On the off chance that one player’s heap is unfilled, this player can’t draw a card and hence loses the game. (Note that it is inconceivable for the two heaps to be vacant.)
In the event that the estimations of the drawn cards are equivalent, every player basically puts the card he attracted to the base of his heap.
Something else, the player whose card has the higher worth successes this round. This player puts the card he attracted to the base of his heap. At that point, the card his rival attracted is moved to him and he puts this card to the base of his heap (beneath the card he just drew) also.
At whatever point a card is moved from one player to the next, the estimation of that card diminishes by 1.
When there is no exchange of cards between the players during 10100 continuous rounds, every player ascertains the aggregate of estimations of the cards that are at present in his heap. On the off chance that one player has a higher total, this player dominates the match. Something else, the game finishes in a draw.
You are given N cards (numbered 1 through N). For each substantial I, the estimation of the I-th card is Ci. Your undertaking is to convey the cards between the players before the beginning of the game ― appoint each card to one of the players. It isn’t important to appropriate the cards similarly between the major parts in any capacity. After you convey the cards, every player orchestrates the cards in his heap in some request he picks (not really useful for this player). When the game beginnings, they may not modify their heaps any longer.
Locate the quantity of dispersions of cards with the end goal that it is inconceivable for the game to end in a draw, paying little mind to how the players structure their beginning heaps. Since this number may be enormous, figure it modulo 1,000,000,007. Two dispersions of cards are unique if there is a whole number I (1≤i≤N) with the end goal that the I-th card has a place with Chef in one dissemination and to Chefu in the other appropriation.
The primary line of the information contains a solitary number T indicating the quantity of experiments. The portrayal of T experiments follows.
The principal line of each experiment contains a solitary whole number N.
The subsequent line contains N space-isolated numbers C1,C2,… ,CN.
For each experiment, print a solitary line containing one whole number ― the quantity of approaches to circulate the cards between the players with the end goal that the game doesn’t end in a draw, modulo 1,000,000,007.
1≤Ci≤109 for each legitimate I
the whole of N over all experiments doesn’t surpass 106
Subtask #1 (5 focuses): N≤8
Subtask #2 (25 focuses): N≤200
Subtask #3 (70 focuses): unique requirements
1 2 6
Model case 1: We can just give the two cards to Chef or both to Chefu. In the event that we gave one of them to Chef and the other to Chefu, the game would end in a draw.
Model case 2: One of the potential approaches to maintain a strategic distance from an attract is to give cards 1 and 4 to Chef and the rest to Chefu. We should expect that Chef frames a heap with cards [6,1] (start to finish); Chefu’s heap is [2,2]. At that point, the game continues this way:
In the first round, Chef draws the card with esteem 6 and wins a card with esteem 2 from Chefu, so his heap is [1,6,1] and Chefu’s heap is  after this round. Note that the estimation of the card moved from Chefu to Chef diminished to 1.
In the second round, Chef draws a card with esteem 1 and Chefu draws his card with esteem 2, so Chefu wins the round. The estimation of the card that is moved from Chef to Chefu diminishes to 0, so this card is eliminated from the game. After this round, Chef’s heap is [6,1] and Chefu’s heap is .
In the third round, Chef again draws the card with esteem 6 and wins Chefu’s last card. After this round, Chef’s heap is [1,6,1] and Chefu’s heap is unfilled. Thusly, Chefu loses the game.