Description

Consider m natural numbers n₁, n₂, …, n_m with the property n_1³ n_2³ …³ n_m>0.

We define a Young table as an arrangement in a table of n₁+n₂+…+n_m natural numbers (bigger than 0 and any two different), so that the i^th line has n_i elements (1£ i£ m) in ascending order from left to right, and the elements from the same column are in ascending order from bottom to top.

An example of Young table for m=4, n₁=6, n₂=4, n₃=4, n₄=1 is the following:

Given n₁, n₂, …, n_m determine the number of Young tables containing the elements 1, 2, …, n₁+n₂+…+n_m.

Input

• on the first line is: the natural number m;

• on the second line are: the numbers n₁, n₂, …, n_m separated by a space.

Output

contain the number of Young tables that can be built.

Constraints:

• 1<= m<= 20
• n_1<=12

Sample Input

Sample Output

Hint

Source