如果整数序列 $S=\{s_i\}$ 有 $n$ 个元素且每个元素 $s_i$ 满足 $1\le s_i\le n$，则该序列称为 $n$ 序列。因此总共有 $n^n$ 个不同的 $n$ 序列。 例如，序列 $S=\{1,5,5,10,7,7,7,2,3,7\}$ 是一个 $10$ 序列。

对于任意序列$S$，令$L(S)$为$S$中具有相同值的最长连续子序列的长度。 例如，对于上面给定的序列 $S$，$L(S)=3$，因为三个连续的 $7$。

令 $f(n)=\sum L(S)$ 对于所有 $n$ 序列 S。

例如，$f(3)=45$、$f(7)=1403689$ 和 $f(11)=481496895121$。

求 $f(7500000)mod1000000009$。