Задача 423
Последовательные броски кубика

Пусть n будет натуральным числом.
6-гранный кубик бросают n раз. Пусть c будет количеством пар последовательных бросков с одинаковым результатом.

Например, если n = 7 и были выброшены числа (1,1,5,6,6,6,3), тогда одинаковый результат имеют следующие пары последовательных бросков:
(1,1,5,6,6,6,3)
(1,1,5,6,6,6,3)
(1,1,5,6,6,6,3)
Посему, c = 3 для (1,1,5,6,6,6,3).

Определим C(n) как количество возможных реузальтатов n бросков 6-гранного кубика таких, что c не превышает π(n).1
Например, C(3) = 216, C(4) = 1290, C(11) = 361912500 и C(24) = 4727547363281250000.

Определим S(L) как C(n) для 1 ≤ nL.
Например, S(50) mod 1 000 000 007 = 832833871.

Найдите S(50 000 000) mod 1 000 000 007.

1 π обозначает функцию распределения простых чисел, т.е. π(n) - это количество простых чисел ≤ n.

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