Cubes

Even though Petryk Pyatochkin attends school, he still enjoys playing with blocks. He constructs steps along a wall using identical blocks by stacking columns in the following way:

• The first column is placed directly against the wall.

• The second column is placed directly against the wall and immediately to the right of the first column.

• The third column is placed directly against the wall and immediately to the right of the second column, and so forth...

The heights of the columns do not increase from left to right. In other words, if h_i represents the height of the i-th column, then h_1 ≥ h_2 ≥ h_3 ≥ ... .

Petryk follows a specific sequence when setting up the blocks, adhering to these self-imposed rules:

1. A block that is not placed on the floor can only be placed after the block it is supposed to rest on. In other words, you cannot insert blocks beneath already placed ones.

2. A block that is not in the first column can only be placed after the block located to its left has been placed.

Determine the number of different ways to sequentially place the blocks to form steps with the specified column heights h_1, h_2, ..., h_k. Only those arrangements that satisfy conditions (1) and (2) are considered valid.

Input

The first line of the input contains a natural number k — the number of columns (1 ≤ k ≤ 6).

The second line contains k natural numbers h_1, h_2, ..., h_k — the number of blocks in the first, second, ..., k-th column of the steps, respectively (6 ≥ h_1 ≥ h_2 ≥ ... ≥ h_k ≥ 1).

Output

The output should be a single line containing the number of different ways to arrange the blocks in the specified configuration, following the rules (1) and (2) for the given column heights.

For illustration, permissible sequences of block placement will be specified. The number of each block indicates the order in which it is placed.

Examples