427 : nの数列
整数の数列 S={si} が n 個の要素を持ち、それぞれの要素 si が 1≤si≤n を満たすとき、これを nの数列 と呼ぼう。したがって全体で nn 個の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)=∑L(S) と定義しよう。
例として、f(3)=45,f(7)=1403689,f(11)=481496895121 である。
f(7 500 000)mod1 000 000 009 を求めよ。