Измерение количества информации

(Д. Тараскин) Сколько различных чисел-палиндромов, состоящих из 36 цифр, в которых каждая половинка числа (слева и справа от середины) в свою очередь тоже является палиндромом, можно составить в двоичной системе счисления?

Примечание: число-палиндром это такое число, которое справа налево и слева направо читается одинаково. К примеру, 12344321 является числом-палиндромом. Число 123321123321 в десятичной системе подходит под условие задачи.