Определим симбер как натуральное число, в котором каждая четная цифра (если такие есть) встречается четное число раз, а каждая нечетная цифра (если такие есть) - нечетное число раз.

Например, 141221242 - это 9-тизначный симбер, потому что он состоит из трех цифр 1, четырех цифр 2 и двух цифр 4.

Пусть Q(n) будет количеством всех симберов, имеющих не больше n цифр.

Известно, что Q(7) = 287975 и Q(100) mod 1 000 000 123 = 123864868.

Найдите (∑_1≤u≤39 Q(2^u)) mod 1 000 000 123.