Задача . Много чисел

Логический преобразователь работает следующим образом:
1. На вход преобразователю подаётся целое неотрицательное число N, меньшее 26410, записанное в шестнадцатеричной системе счисления. Запись числа переводится в двоичную систему счисления и разбивается на 16 групп по 4 разряда (при необходимости в начале записи дописываются незначащие нули).  
2. Двигаясь справа налево по очереди берется каждая группа двоичных разрядов и представляется как последовательность из четырех логических переменных X₀X₁X₂X₃, так, что единичное значение двоичного разряда соответствует значению "истина", а нулевое - значению "ложь". Например, в числе 0…010111 первая такая последовательность будет X₀ = «ложь», X₁ = «истина», X₂ = «истина», X₃ = «истина».
3. Полученные последовательности логических переменных по очереди подставляются в логическое выражение:  и вычисляется его значение.
4. Вычисленные значения преобразуются в двоичные разряды (также «истина» = 1, а «ложь» = 0) и образуют двоичную последовательность, заполняемую от младшего к старшему разряду.
5. Результатом работы преобразователя является шестнадцатиразрядное двоичное число (запись может содержать незначащие нули). На вход преобразователю подали запись числа, равного FEDCBA987654321016 и получили некоторое число M. Сколько всего существует таких чисел, которые можно подать на вход преобразователю и получить в результате такое же число M?
Поскольку число может получиться достаточно большое, посчитайте и укажите в ответе сумму его цифр при записи в десятичной системе счисления.