Поэзия (Poetry)
На улице Одуванчиков жил известный поэт. Настоящее имя этого поэта было Пудик. Однако, как известно, поэты любят красивые имена. Поэтому, когда Пудик стал поэтом, он взял себе другое имя и стал называться Цветик. Цветик прославился тем, что написал стихотворение в честь полёта на воздушном шаре. Его стихотворение все выучили наизусть и распевали на улицах:гигАнтский шАр, пОлный пАры,взлетЕл недАром дО до облАка.наш коротЫшка, хОтя не птИца,летАть он однАко годИтся.нет никАких препЯтствий тепЕрьдля нАшего умА!(Заглавными буквами выделены гласные в ударных слогах).
Но вот у него началась творческая депрессия, и он не мог придумать ни одного нового слова для стихов. Выход подсказал Незнайка: «Возьми свои старые стихи, переставь в каждой строке слова, и ты получишь новые». А Знайка добавил, что если в строке 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.