ProjectEuler 427 n-sequences - 拼圖

427. n-sequences

http://projecteuler.net/problem=427

如果一整數數列S = {s_i}恰有n項，並且每一項都符合1≦s_i≦n，則我們稱此數列S為

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。


令f(n) = ΣL(S)對所有n-數列S求和。


例如，f(3) = 45，f(7) = 1403689以及f(11) = 481496895121。

請求出f(7500000) mod 1000000009。

--