Counting Distinct Necklaces

Madeline distributed strawberries to her friends, and in return they collected a variety of colorful beads to make a necklace for her. There are a total of n beads available in k different colors. In particular, for each color i (1 ≤ i ≤ k), there are a_i beads. Note that beads are identical if they share the same color.

The necklace must be a complete structure in the sense that all the beads form one connected block. Moreover, the beads must be strung together to form a base cycle tree – a graph that is a connected tree with one additional edge, thereby forming a unique cycle (often called a unicyclic graph). After consulting with Madeline’s friends, it was agreed that two subtrees attached to the base cycle are considered different if and only if either the color of the corresponding vertex differs or their structures differ; furthermore, the relative order among different subtrees matters.

In addition, if two necklaces can be transformed into each other by a rotation of the base cycle, they are considered essentially identical. For the purpose of this problem, you may assume that the only structural variability comes from the circular arrangement of beads on the base cycle. In other words, the answer is equivalent to the number of distinct circular arrangements (necklaces) of a multiset where beads of the same color are indistinguishable.

The number of distinct necklaces is given by the formula:

$$ \frac{n!}{n \cdot \prod_{i=1}^{k}a_i!} $$

where $$n = \sum_{i=1}^{k}a_i.$$

inputFormat

The first line contains a single integer k (1 ≤ k ≤ 10), the number of bead colors.

The second line contains k space‐separated integers a₁, a₂, ..., a_k (1 ≤ a_i ≤ 10), where a_i denotes the number of beads of color i.

outputFormat

Output a single integer representing the number of essentially distinct necklaces that can be formed following the rules described above.

sample

2
1 1

1