eolymp
bolt
Try our new interface for solving problems
Problems

Diagrams & Tableaux

Diagrams & Tableaux

Time limit 1 second
Memory limit 64 MiB

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 data

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 1k7, 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 7l_1l_2 ≥ ... ≥ l_k1. The second line contains the integer N, satisfying kN7.

Output data

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.

Examples

Input example #1
1 1
1
1 1
2
2 2 1
4
4 3 2 1 1
4
Output example #1
1
2
20
20
Source ACM ICPC NWERC 2013