eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Поезія (Poetry)

Поезія (Poetry)

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Та ось у нього почалася творча депресія і він не міг вигадати жодного нового слова для віршів. Вихід підказав Незнайко: «Візьми свої старі вірші, перестав у кожному рядку слова, і ти отримаєш нові». А Знайко додав, якщо у рядку 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∙10^9.

Приклад

Вхідні дані #1
4
3 2 2 2
Вихідні дані #1
6
Джерело II етап (міські та районні тури Дніпропетровської області) 2016-2017 н.р.