427 : nの数列

整数の数列 $S = \{s_i\}$ が $n$ 個の要素を持ち、それぞれの要素 $s_i$ が $1 \leq s_i \leq n$ を満たすとき、これを nの数列 と呼ぼう。したがって全体で $n^n$ 個のnの数列が存在することになる。例えば、数列 $S = \{1, 5, 5, 10, 7, 7, 7, 2, 3, 7\}$ は10の数列のひとつである。

ある数列 $S$ に対し、同じ値からなる最長の連続部分列の長さを $L(S)$ としよう。例えば、上記で与えられた数列 $S$ の場合、 $L(S) = 3$ となる、なぜなら3回連続して 7 が現れるからである。

全てのnの数列 $S$ に対し関数 $f(n) = \sum L(S)$ と定義しよう。

例として、$f(3) = 45, f(7) = 1403689, f(11) = 481496895121$ である。

$f(7\ 500\ 000) \bmod 1\ 000\ 000\ 009$ を求めよ。