ProjectEuler 423 Consecutive die throw - 拼圖

423. Consecutive die throws

http://projecteuler.net/problem=423

令n為正整數。

將一六面骰重覆骰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)

所以，在(1, 1, 5, 6, 6, 6, 3)這組結果中c = 3。

定義C(n)為將骰子重覆骰n次的所有可能結果中，其c值不超過π(n)（註１）的組數。

例如，C(3) = 216，C(4) = 1290，C(11) = 361912500以及
C(24) = 4727547363281250000。

定義S(L)為ΣC(n)對1 ≦ n ≦ L的和。

例如，S(50) mod 1000000007 = 832833871。

請求出S(50000000) mod 1000000007。

（註１）在這裡的π指的是質數計數函數，即π(n)代表有多少質數≦ n。

--