Задача 427
n-последовательности

Последовательность целых чисел S = {si} называется n-последовательностью, если она имеет n элементов и каждый элемент si удовлетворяет 1 ≤ sin. Таким образом, существует всего nn различных n-последовательностей.Например, последовательность S = {1, 5, 5, 10, 7, 7, 7, 2, 3, 7} является 10-последовательностью.

Для любой последовательности S пусть L(S) будет длиной самой длинной непрерывной подпоследовательности S, состоящей из одинаковых элементов. Например, для приведенной выше последовательности S L(S) = 3, потому что она содержит три последовательные семерки.

Пусть f(n) = L(S) для всех n-последовательностей S.

Например, f(3) = 45, f(7) = 1403689 и f(11) = 481496895121.

Найдите f(7 500 000) mod 1 000 000 009.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net