Последовательность целых чисел S = {s_i} называется n-последовательностью, если она имеет n элементов и каждый элемент s_i удовлетворяет 1 ≤ s_i ≤ n. Таким образом, существует всего nⁿ различных 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.