На вулиці Кульбаби жив відомий поет. По-справжньому цього поета називали Пудик. Але, як відомо, поети дуже люблять красиві імена. От і Пудик, коли зробився поетом, прибрав собі інше ім'я і став зватися Квітик. Квітик прославився тим, що написав вірш на честь польоту на повітряній кулі. Його вірш усі вивчили напам'ять і виспівували на вулицях: гігАнтська кУля, пОвна пАри, знялАсь недАром Аж до хмАри. наш кОротУлька, хОч не птИця, літАти вІн однАк годИться. ніЯких пЕрешкОд немА тепЕр для нАшогО умА! (Великими літерами виділені голосні у наголошених складах). Та ось у нього почалася творча депресія і він не міг вигадати жодного нового слова для віршів. Вихід підказав Незнайко: «Візьми свої старі вірші, перестав у кожному рядку слова, і ти отримаєш нові». А Знайко додав, якщо у рядку m слів, то існує m! перестановок, наприклад, для рядка з 5 слів число перестановок буде 5! = 1∙2∙3∙4∙5 = 120. Але виявилося, що не все так просто. Вірші мають свій ритм, коли ненаголошені та наголошені склади розташовані у певному порядку. Квітик визнає тільки ямб, у якому всі непарні склади ненаголошені, а парні – наголошені, як у наведеному вірші. Довгі слова можуть мати декілька наголошених складів (наприклад, пЕрешкОд), а односкладові слова можуть мати, а можуть не мати наголос (наприклад, Аж до) і міняти цей наголос не годиться. Тому у четвертому рядку так переставити слова можна: «однАк годИться вІн літАти», а так «вІн літАти годИться однАк» – ні, бо порушено ритм. А перестановка у п’ятому рядку «пЕрешкОд немА ніЯких», хоч і має правильний ритм, але це вже хорей (наголошені непарні склади), а Квітик принципово його не визнає. Складіть програму для наступної задачі: дано рядок із N слів, написаний ямбом, і кількість складів у кожному слові. Знайти кількість перестановок слів (включаючи початкову), які утворюють рядки, також написані ямбом.

Вхідні дані

Програма читає число N (2 ≤ N ≤ 16) і N натуральних чисел `a[1], a[2], …, a[N] (1 ≤ a[і] ≤ 10)` – кількості складів у словах. Всі числа знаходяться у одному рядку і відокремлені пропусками.

Вихідні дані

Кількість припустимих перестановок

Примітки:

• Цей приклад для першого рядка вірша.
• Тести мають відповіді, у яких кількість перестановок не перевищує 2∙109.