Project Euler Problem 427
A sequence of integers S = si is called an n-sequence if it has n elements and each element si satisfies 1 leq si leq n.
Solution
Answer: 97138867
Let $A(n,k)$ be the number of $n$-sequences whose longest constant run has length $<k$.
Then
$$f(n)=\sum_S L(S) =\sum_{k=1}^{n}#{S:L(S)\ge k}$$
Since there are $n^n$ sequences total,
$$f(n)=\sum_{k=1}^{n}\left(n^n-A(n,k)\right) = n^{n+1}-\sum_{k=1}^{n}A(n,k).$$
For fixed $k$, define $F(i,k)$ as the number of length-$i$ sequences with no run of length $k$ or more. By inclusion–exclusion on whether the final $k$-block is forced,
$$F(i,k)=nF(i-1,k)-(n-1)F(i-k,k).$$
This recurrence has a path-counting / generating-function interpretation, yielding the closed form
$$A(n,k) = \sum_{t=0}^{\lfloor n/k\rfloor} (1-n)^t ,n^{,n-tk} \binom{n-tk+t}{t}.$$
Thus
$$f(n) = n^{n+1} - \sum_{k=1}^{n} A(n,k).$$
Evaluating this modulo $10^9+9$ for $n=7{,}500{,}000$ using precomputed factorials, inverse factorials, and powers gives the required value. The harmonic-series complexity is $O(n\log n)$.
Answer: 97138867