ProjectEuler 467 Superinteger - 拼圖

467. Superinteger

http://projecteuler.net/problem=467

如果一整數n為另一整數s的子序列，則我們稱s為n的延伸數。

意即，若s為n的延伸數，則可以藉由刪去s中的某些數字而得到n。

例如，2718281828是18828的延伸數，而314159則不是151的延伸數。

令p(n)為第n個質數、c(n)為第n個合數。例如，p(1) = 2、p(10) = 29、c(1) = 4以及
c(10) = 18。

{p(i) : i ≧ 1} = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...}
{c(i) : i ≧ 1} = {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

令序列PD、CD各項分別為序列{p(i)}、{c(i)}各項的數字根。

（數字根是將一數字的每個位數相加，若和為兩位以上則不斷重覆此步驟最後得到的數）

PD = {2, 3, 5, 7, 2, 4, 8, 1, 5, 2, ...}
CD = {4, 6, 8, 9, 1, 3, 5, 6, 7, 9, ...}

令P_n、C_n分別為將PD、CD的前n項接在一起所得到的數。

P_10 = 2357248152
C_10 = 4689135679

令f(n)為正整數中，同時為P_n和C_n的延伸數裡的最小者。

例如，f(10) = 2357246891352679以及f(100) mod 1000000007 = 771661825。

請求出f(10000) mod 1000000007。

--