Solution

Answer: 471745499

Let a number of length $n$ be dominating if some digit appears strictly more than $n/2$ times.

We must compute

$$D(2022)\pmod{1,000,000,007}.$$

The key is to count valid $n$-digit numbers combinatorially.

1. Mathematical analysis

For a fixed length $n$, define:

A(n)=\text{# dominating } n\text{-digit numbers}.

Then

$$D(N)=\sum_{n=1}^{N} A(n).$$

We therefore need $A(n)$.

Step 1: A dominating digit is unique

Suppose a number has two different digits each occurring more than $n/2$ times.

Then the total number of digits would exceed $n$, impossible.

So every dominating number has a unique dominating digit.

Hence we may:

choose the dominating digit $d$,
choose how many times it appears,
place the remaining digits.

Step 2: Count $n$-digit numbers where digit $d$ appears $k$ times

We require

$$k>\frac n2.$$

We must treat separately:

$d\neq 0$,
$d=0$,

because leading zeros are forbidden.

Case A: Dominating digit $d\neq 0$

Choose one of the $9$ nonzero digits.

Suppose $d$ appears exactly $k$ times.

We count $n$-digit strings:

first digit nonzero,
exactly $k$ copies of $d$,
remaining digits are anything except $d$.

We split according to whether the first digit is $d$.

A1. First digit is $d$

Then among remaining $n-1$ positions we need:

$k-1$ additional copies of $d$,
the other $n-k$ positions can be any of $9$ digits (everything except $d$).

Count:

$$\binom{n-1}{k-1}9^{,n-k}.$$

A2. First digit is not $d$

First digit:

cannot be $0$,
cannot be $d$,

so there are $8$ choices.

Among remaining $n-1$ positions:

choose $k$ positions for $d$,
the other $n-1-k$ positions have $9$ choices each.

Count:

$$8\binom{n-1}{k}9^{,n-1-k}.$$

Therefore for fixed nonzero $d$,

$$\binom{n-1}{k-1}9^{n-k} + 8\binom{n-1}{k}9^{n-1-k}.$$

Multiply by $9$ choices of $d$:

$$9\binom{n-1}{k-1}9^{n-k} + 72\binom{n-1}{k}9^{n-1-k}.$$

Case B: Dominating digit $d=0$

Zero cannot be the leading digit.

So:

first digit: $9$ choices,
among remaining $n-1$ positions choose $k$ zeros,
all other positions: $9$ choices.

Thus:

$$9\binom{n-1}{k}9^{n-1-k}.$$

Step 3: Combine

Total for fixed $n,k$:

$$9\binom{n-1}{k-1}9^{n-k} + 81\binom{n-1}{k}9^{n-1-k}.$$

Use Pascal:

$$\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}.$$

Factor:

$$9^{n-k+1} \left( \binom{n-1}{k-1}+\binom{n-1}{k} \right) = 9^{n-k+1}\binom{n}{k}.$$

So:

$$A(n)= \sum_{k=\lfloor n/2\rfloor+1}^{n} \binom{n}{k}9^{n-k+1}.$$

Therefore

$$D(N) = \sum_{n=1}^{N} \sum_{k=\lfloor n/2\rfloor+1}^{n} \binom{n}{k}9^{n-k+1}.$$

We compute modulo

$$M=1,000,000,007.$$

2. Python implementation

MOD = 1_000_000_007
N = 2022

# Precompute factorials and inverse factorials
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD

invfact = [1] * (N + 1)
invfact[N] = pow(fact[N], MOD - 2, MOD)

for i in range(N, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD

def C(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

# powers of 9
pow9 = [1] * (N + 2)
for i in range(1, N + 2):
    pow9[i] = pow9[i - 1] * 9 % MOD

ans = 0

for n in range(1, N + 1):
    start = n // 2 + 1

    for k in range(start, n + 1):
        ans += C(n, k) * pow9[n - k + 1]
        ans %= MOD

print(ans)

3. Code walkthrough

Factorials

We precompute:

$n!$,
inverse factorials,

so binomial coefficients can be evaluated in $O(1)$:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$

Using Fermat:

$$a^{-1}\equiv a^{M-2}\pmod M.$$

Powers of 9

We need many terms of:

$$9^{n-k+1}.$$

So we precompute all powers.

Main summation

For each digit length $n$:

dominating multiplicity starts at

$$\left\lfloor \frac n2 \right\rfloor +1,$$

sum all valid $k$.

Each contribution is:

$$\binom{n}{k}9^{n-k+1}.$$

4. Verify against examples

For $N=4$:

The program gives:

$$D(4)=603,$$

matching the statement.

For $N=10$:

It gives:

$$D(10)=21893256,$$

also matching.

So the derivation is consistent.

5. Final computation

Evaluating the above program for $N=2022$ yields:

$$D(2022)\equiv 471745499 \pmod{1,000,000,007}.$$

Answer: 471745499

Project Euler Problem 788