Solution

Answer: 146133880

Let

$$a=(\dots a_2a_1a_0),\qquad b=(\dots b_2b_1b_0)$$

and define the freshman’s product $a\boxtimes b$ digitwise by

$$(a\boxtimes b)_i \equiv a_i b_i \pmod{10}.$$

For several numbers,

$$x_1\boxtimes x_2\boxtimes \cdots \boxtimes x_R$$

has digit $i$

$$d_i \equiv \prod_{k=1}^R (x_k)_i \pmod{10}.$$

We must compute

$$F(R,M)=\sum_{0\le x_1,\dots,x_R\le M} x_1\boxtimes\cdots\boxtimes x_R.$$

For the problem:

$$R=234567,\qquad M=765432.$$

All computations are modulo

$$P=1,000,000,009.$$

1. Key mathematical insight

The decimal positions are completely independent.

If the digit at position $j$ contributes $c_j$, then

$$F(R,M)=\sum_{j\ge0} 10^j c_j.$$

So we solve each decimal position separately.

Counting digits at one position

Fix a decimal position $j$.

Let $C_j(d)$ be the number of integers $x\in[0,M]$ whose $j$-th digit equals $d$.

These counts are obtained by the standard digit-counting formula.

For position value $p=10^j$:

$\text{high} = \lfloor M/(10p)\rfloor$
$\text{cur} = \lfloor M/p\rfloor \bmod 10$
$\text{low} = M\bmod p$

Then initially every digit appears

$$\text{high}\cdot p$$

times, and the partial block contributes the usual corrections.

Residue dynamics mod 10

At one digit position, each selected number contributes a digit $d\in{0,\dots,9}$.

The resulting digit is

$$r \equiv d_1d_2\cdots d_R \pmod{10}.$$

We only care about the residue mod $10$, so there are only 10 states.

Define a transition matrix $T$ by

$$T[a][b] = \sum_{\substack{d=0\ ad\equiv b\pmod{10}}}^{9} C_j(d).$$

Interpretation:

current residue = $a$
choose a new digit $d$
new residue = $ad\bmod 10$

If the starting residue is $1$, then after $R$ choices:

$$\text{dp} = e_1 T^R.$$

Here $\text{dp}[r]$ equals the number of sequences producing residue $r$.

Hence the total contribution of this decimal position is

$$S_j=\sum_{r=0}^9 r\cdot \text{dp}[r].$$

Finally,

$$F(R,M)=\sum_j 10^j S_j \pmod P.$$

Since the matrix is only $10\times10$, fast exponentiation is trivial.

2. Python implementation

MOD = 1_000_000_009

R = 234567
M = 765432

# Count how many numbers in [0, M]
# have digit d at decimal position pos.
def digit_counts(M, pos):
    p = 10 ** pos

    high = M // (p * 10)
    cur = (M // p) % 10
    low = M % p

    cnt = [high * p] * 10

    for d in range(cur):
        cnt[d] += p

    cnt[cur] += low + 1

    return [x % MOD for x in cnt]

def mat_mul(A, B):
    n = len(A)
    m = len(B[0])
    k = len(B)

    C = [[0] * m for _ in range(n)]

    for i in range(n):
        for t in range(k):
            if A[i][t]:
                a = A[i][t]
                for j in range(m):
                    C[i][j] = (C[i][j] + a * B[t][j]) % MOD

    return C

def mat_pow(MAT, e):
    n = len(MAT)

    # identity matrix
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]

    while e:
        if e & 1:
            R = mat_mul(R, MAT)

        MAT = mat_mul(MAT, MAT)
        e >>= 1

    return R

def solve(R, M):
    ans = 0
    pow10 = 1

    pos = 0
    while 10 ** pos <= M:

        cnt = digit_counts(M, pos)

        # transition matrix
        T = [[0] * 10 for _ in range(10)]

        for a in range(10):
            for d in range(10):
                b = (a * d) % 10
                T[a][b] = (T[a][b] + cnt[d]) % MOD

        # T^R
        P = mat_pow(T, R)

        # start state is residue 1
        dp = P[1]

        # weighted digit sum
        Sj = sum(r * dp[r] for r in range(10)) % MOD

        ans = (ans + pow10 * Sj) % MOD

        pow10 = (pow10 * 10) % MOD
        pos += 1

    return ans

print(solve(R, M))

3. Code walkthrough

`digit_counts`

Computes how often each digit $0\ldots9$ appears at a fixed decimal position among all numbers $0\le x\le M$.

This is the standard positional digit-counting technique.

`mat_mul`

Multiplies matrices modulo $10^9+9$.

Since matrices are only $10\times10$, this is extremely fast.

`mat_pow`

Binary exponentiation of matrices:

$$T^R$$

in $O(\log R)$ matrix multiplications.

Transition matrix

For each current residue $a$ and new digit $d$,

$$b=(ad)\bmod 10.$$

The number of ways this happens is the count of digit $d$.

Thus:

T[a][b] += cnt[d]

Recovering the answer

Starting residue is $1$, because multiplying no digits yet corresponds to multiplicative identity.

After exponentiation:

dp = P[1]

contains counts for each final residue.

Then:

Sj = sum(r * dp[r])

is the total contribution of that decimal position.

Finally we multiply by $10^j$.

4. Verification on the examples

The program gives:

$$F(2,7)=204$$

matching the statement.

Also:

$$F(23,76)\equiv 5870548 \pmod{1,000,000,009}$$

again matching the statement exactly.

So the method is validated.

5. Final computation

Running the algorithm for

$$R=234567,\qquad M=765432$$

gives

$$F(234567,765432)\equiv 146133880 \pmod{1,000,000,009}.$$

Answer: 146133880

Project Euler Problem 778