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

Обмеження: 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).