Simbers

We define a simber to be a positive integer in which any odd digit, if present, occurs an odd number of times, and any even digit, if present, occurs an even number of times.

For example, 141221242 is a 9-digit simber because it has three 1's, four 2's and two 4's.

Let Q(n) be the count of all simbers with at most n digits.

You are given Q(7) = 287975 and Q(100) mod 1 000 000 123 = 123864868.

Find (∑_1≤u≤39 Q(2^u)) mod 1 000 000 123.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter