Diagrams & Tableaux
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 ≤ k ≤ 7, the number of rows, followed by k positive integers l_1, l_2, ..., l_k. These integers specify the number of boxes on each row of the Young diagram, and they satisfy 7 ≥ l_1 ≥ l_2 ≥ ... ≥ l_k ≥ 1. The second line contains the integer N, satisfying k ≤ N ≤ 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.