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

Limits: 2 sec., 256 MiB

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

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

Input

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

Output

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

Constraints

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

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

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

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

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

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

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
2 10	4

Input (stdin) сopy	Output (stdout) сopy
4 0111	16

Notes

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