Count of Valid Pairing Configurations

We are given a collection of n objects labelled \(A_1, A_2,\dots,A_n\). Each object is originally one of two types:

• Element board: it initially carries an element.
• Mirror: it initially carries no element.

An element board can be paired with at most one mirror. If an element board is paired with a mirror then the mirror will receive the element carried by the board. Note that a mirror cannot be paired with more than one board. After all pairings (if any) are performed, the final number of elements on each object is observed.

Thus, if an element board is not paired it still carries its element (final count = 1), while if it is paired it transfers its element (final count = 0). On the other hand, a mirror if not paired remains element‐less (final count = 0), and a mirror if paired will carry the element transferred from its paired board (final count = 1).

You are given the total number of objects n and the final element count on each object. Count how many valid configurations (assignments of types and pairings) could have produced the given final counts.

Hint: For an object with final count 0, it can be either a paired board or an unpaired mirror; for an object with final count 1, it can be either an unpaired board or a paired mirror. Let there be \(n_0\) objects with final count 0 and \(n_1\) objects with final count 1. If we decide to designate \(k\) out of the \(n_0\) zeros as boards (thus paired) then exactly \(k\) out of the \(n_1\) ones must be designated as mirrors (thus paired) so that the pairing is one-to-one. The overall number of configurations is therefore:

[ \sum_{k=0}^{\min(n_0, n_1)} \binom{n_0}{k} \times \binom{n_1}{k} \times k!. ]

inputFormat

The first line contains a single integer n representing the total number of objects.

The second line contains n space-separated integers, each being either 0 or 1. The \(i\)th integer represents the final number of elements on the \(i\)th object.

outputFormat

Output a single integer — the total number of valid pairing configurations.

sample

3
0 1 1

3