PAINTBLK - Painting Blocks (Act I)

n blocks are put in a line. You have k (1 <= k <= 15) kinds of dope, the i-th dope is enough to paint ci (1 <= ci <= 5) blocks. You may assume the sum of all the ci equals to n. Your task is to calculate the number of ways to paint the blocks with these kinds of dope, such that no two adjacent blocks are painted with the same kind of dope.

Input

Ten test cases (given one after another, you have to process all!) For each test case, the first line contains an integer k, the second line contains k integers, c1, c2 ... ck.

Output

Ten lines, each contains an integer, the number of ways modulo 1000000007.

Example

Input:
3
1 2 3
5
2 2 2 2 2
10
1 1 2 2 3 3 4 4 5 5
[and 7 test cases more]

Output:
10
39480
85937576
[and 7 test cases more]

Added by:Fudan University Problem Setters
Date:2008-09-01
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource::P

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.