Poetry#8285
On Dandelion Street lived a renowned poet named Pudyik. However, as poets often prefer more elegant names, Pudyik adopted the name Kvityk when he began his poetic career. Kvityk gained fame for composing a poem celebrating a hot air balloon flight. The poem became so popular that everyone memorized it and sang it in the streets:
gIgAntic bAlloon, fUll of stEam,rOse up to the clOud, not in vAin.our shOrtling, thOugh not a bIrd,he's fIt to flY, that's the wOrd.no ObstAcles remAinfor our mInd agAin!
(Vowels in stressed syllables are highlighted in uppercase.)
Unfortunately, Kvityk later fell into a creative slump and struggled to find new words for his poems. Neznaiko suggested a solution: "Rearrange the words in your old poems, and you'll create new ones." Znaiko added that if a line contains words, there are possible permutations. For example, a line with words can be rearranged in 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 ways.
However, maintaining the poem's rhythm is crucial. Kvityk only accepts iambic meter, where odd syllables are unstressed and even syllables are stressed, as demonstrated in the poem. Long words may have multiple stressed syllables (for example, ObstAcles), and monosyllabic words may or may not be stressed (for example, to the), but altering their stress is not allowed.
For example, in the fourth line, the words can be rearranged as "he's fIt to flY, that's the wOrd," but not as "that's the wOrd, he's fIt to flY," because it disrupts the rhythm. Similarly, the permutation "ObstAcles remAin no" in the fifth line maintains the rhythm, but shifts to trochaic meter (stressed odd syllables), which Kvityk does not accept.
Your task is to write a program that, given a line of words written in iambic meter with the number of syllables in each word, computes the number of permutations of the words (including the original order) that also yield lines written in iambic meter.
\InputFileThe program reads a single line containing the integer (2 \le N \le 16) and natural numbers a_1, a_2, \ldots, a_N (1 \le a_i \le 10) — the number of syllables in each word. All numbers are separated by spaces.
\OutputFilePrint the number of valid permutations.
Example 1
This sample is based on the first line of the poem.
Test cases are such that the answer does not exceed 2 \cdot 10^9.