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

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

Вхідні дані

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

Вихідні дані

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

Примітки:

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