Поезія (Poetry)

На вулиці Одуванчиків жив відомий поет. По-справжньому цього поета називали Пудик. Але, як відомо, поети дуже люблять красиві імена. От і Пудик, коли зробився поетом, прибрав собі інше ім'я і став зватися Квітник. Квітник прославився тим, що написав вірш на честь польоту на повітряній кулі. Його вірш усі вивчили напам'ять і виспівували на вулицях:

гігАнтична кУля, пОвна пАри,знялАся недАрма аж до хмАри.наш корОтулька, хоч не птИця,літАти він однАк годИться.ніЯких пЕрешкОд немАтепЕр для нАшого умА!

(Великі літери виділяють голосні в наголошених складах.)

Та ось у нього почалася творча депресія, і він не міг вигадати жодного нового слова для віршів. Вихід підказав Незнайко: «Візьми свої старі вірші, перестав у кожному рядку слова, і ти отримаєш нові». А Знайко додав, якщо у рядку $m$ слів, то існує $m!$ перестановок. Наприклад, для рядка з $5$ слів кількість перестановок буде 5! = 1\cdot2\cdot3\cdot4\cdot5=120.

Але виявилось, що не все так просто. Вірші мають свій ритм, коли ненаголошені та наголошені склади розташовані у певному порядку. Квітник визнає тільки ямб, у якому всі непарні склади ненаголошені, а парні — наголошені, як у наведеному вірші. Довгі слова можуть мати декілька наголошених складів (наприклад, пЕрешкОд), а односкладові — мати чи ні наголос (наприклад, аж до), але міняти цей наголос не можна.

Тому у четвертому рядку слова можна переставити так: «однАк годИться він літАти», а так: «він літАти годИться однАк» — не можна, бо порушено ритм. А перестановка у пʼятому рядку «пЕрешкОд немА ніЯких», хоча ритм зберігається, є вже хореєм (наголошені непарні склади), а Квітник принципово його не визнає.

Складіть програму для наступної задачі: задано рядок із $N$ слів, написаний ямбом, і кількість складів у кожному слові. Необхідно знайти кількість перестановок слів (включно з початковою), котрі утворюють рядки, також написані ямбом.

\InputFileПрограма читає один рядок, що містить ціле число $N$ (2 \le N \le 16) і $N$ натуральних чисел a_1, a_2, \ldots, a_N (1 \le a_i \le 10) — кількість складів у кожному слові. Всі числа розділені пробілами.

\OutputFileВиведіть кількість допустимих перестановок.