Migrated from Lutece 891 Diagrams & Tableaux

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A Young diagram is an arrangement of boxes in rows and columns conforming to the following rules:

• the boxes in each row and each column are contiguous,
• the left borders of all rows are aligned, and
• each row is not longer than the one above.

Here are some examples of Young diagrams:

A semi-standard Young tableau for a given number $N$ is a Young diagram that has its boxes filled according to the following rules:

• Each box contains a single integer between $1$ and $N$, inclusive,
• each integer is greater than or equal to the integer in the box to its left, and
• each integer is strictly greater than the integer in the box above.

Here is a list of all semi-standard Young tableaux for $N=3$, based on a particular Young diagram:

Your task is to count how many semi-standard Young tableaux are possible, based on a given Young diagram, with a given $N$.

Input

Each test case consists of two lines. The first line of each test case specifies the Young diagram. This line starts with the number $k$ satisfying $1\le{}k \le{}7$, the number of rows, followed by $k$ positive integers $l_1,l_2,\ldots,l_k$. These integers specify the number of boxes on each row of the Young diagram, and they satisfy $7\ge{}l_1\ge{}l_2\ge\cdots\ge{}l_k\ge{}1$. The second line contains the integer $N$, satisfying $k\le{}N\le{}7$.

Output

For each test case, print one line containing the number of semi-standard Young tableaux based on the given Young diagram, with the given $N$.

Samples

1 1
1
1 1
2
2 2 1
4
4 3 2 1 1
4

1
2
20
20

Resources

Northwestern European Regional Contest 2013