Poetry
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 m words, there are m! permutations possible. For instance, a line with 5 words can be rearranged in 5! = 1∙2∙3∙4∙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 (e.g., ObstAcles), and monosyllabic words may or may not be stressed (e.g., to the), but altering their stress is not allowed.
For example, in the fourth line, 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 with N words written in iambic meter and the number of syllables in each word, calculates the number of permutations of the words (including the original order) that preserve the iambic meter.
Input
The program reads the number N (2 ≤ N ≤ 16) and N natural numbers a[1], a[2], …, a[N] (1 ≤ a[i] ≤ 10) representing the number of syllables in each word. All numbers are provided in a single line, separated by spaces.
Output
Output the number of valid permutations.
Notes:
This example is based on the first line of the poem.
The solutions are constrained such that the number of permutations does not exceed
2∙10^9.