Забудькуватий Зеник

Обмеження: 2 сек., 256 МіБ

Забудькуватий Зеник є багатим програмістом. Зеник цінує свою величезну зарплату і зберігає її в двох різних банках (ми не будемо згадувати назви цих банків, оскільки вони не заплатили нам за рекламу). Відповідно, Зеник має дві банківські картки. PIN-код, до кожної з карток, містить рівно \(n\) цифр, кожна з яких 0 або 1. Щоб не забути PIN-код до карток, бо зберігати записані PIN-коди дуже необачно, Зеник вирішив записати собі рядок \(x\) з цифр 0 і 1, для цього він виконав таку операцію: рядок \(x\) містить 1 лише в позиціях де цифри в його паролях відрізняються і 0 в іншому випадку.

Зеник знає, що якщо забуде один з PIN-кодів, то за допомогою рядка \(x\) та іншого PIN-коду зможе відновити забутий. Але, от халепа, він забув обидва PIN-коди. Зеник неймовірно засмутився і навіть трохи поплакав. Зрозумівши, що сльози не повернуть його статки, він вирішив перебрати всі можливі пари PIN-кодів, які дають рядок \(x\) після виконання відповідної операції. Скажіть Зенику, скільки пар PIN-кодів йому потрібно буде перебрати.

Вхідні дані

У першому рядку задано одне ціле число \(n\) та рядок \(x\) — довжина PIN-кодів та результат виконання операції для паролів відповідно.

Вихідні дані

В єдиному рядку виведіть кількість пар PIN-кодів, які мають довжину \(n\) і дають рядок \(x\) в результаті виконання операції.

Обмеження

\(1 \le n = |x| \le 30\),

де \(|x|\) — довжина рядка \(x\),

рядок \(x\) містить лише цифри 0 та 1,

Оцінювання задачі складається із наступних блоків:

По 1 балу — приклади з умови,

8 балів — блок тестів у яких \(n \le 10\),

10 балів — блок тестів у яких \(n \le 20\),

5 балів — блок тестів у яких \(n \le 30\),

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 10	4

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0111	16

Примітки

Пари які задовольняють перший приклад: (01, 11), (11, 01), (00, 10), (10, 00).