Задача E. Гадание на ромашках

Автор:Г. Гренкин, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Однажды Аполлинарий Матвеевич очутился на поле, на котором росли ромашки. Он сорвал несколько ромашек и стал гадать, любит или не любит его Марфа Геннадьевна. А гадал он так: брал каждую ромашку по отдельности и отрывал от неё лепестки, приговаривая: "любит", "не любит", "любит", "не любит"... Если при отрывании последнего лепестка он говорил "любит", то для этой ромашки ответ — "любит", а иначе для этой ромашки ответ — "не любит". Аполлинарий Матвеевич посчитал, сколько ромашек дали ответ "любит" и сколько ромашек дали ответ "не любит". Если количество ромашек с ответом "любит" строго больше, чем количество ромашек, давших ответ "не любит", то Аполлинарий Матвеевич считает, что Марфа Геннадьевна его любит. А в противном случае ромашки, увы, говорят обратное.

Аполлинарий Матвеевич задумался: сколько существует способов сорвать букет таким образом, чтобы ответ был "любит"?

Дано N — число ромашек на поле и числа ai — количества лепестков на ромашках. Требуется определить, сколькими способами можно сорвать букет, чтобы ответ был "любит".

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai — количества лепестков на ромашках.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — число способов сорвать букет, чтобы ответ был "любит".

Ограничения

1 ≤ N ≤ 31

1 ≤ ai ≤ 20

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
8 5
1
2
3
5 8 7
4

0.090s 0.009s 13