ProjectEuler 477 Number Sequence Game - 拼圖

477. Number Sequence Game

https://projecteuler.net/problem=477

給定由N個數字排成一排所組成的數列S，進行如下的數列遊戲：

兩個玩家輪流行動，在一個回合中，玩家必須移除數列的第一個或最後一個數。

玩家的得分為他所移除的所有數的和。

現假設每個玩家都採取了最佳策略。

例如當N=4及S={1,2,10,3}時，每個玩家採取的最佳策略如下：

　‧玩家1：移除第一個數1。
　‧玩家2：移除最後一個數3。
　‧玩家1：移除最後一個數10。
　‧玩家2：移除第一個數2。

玩家1的得分是1+10=11。

令F(N)為當雙方玩家皆採取最佳策略時，
玩家1在S={S_1, S_2, ... S_N}定義如下時的得分：

　‧S_1 = 0
　‧S_(i+1) = (S_i^2 + 45) mod 1000000007

這數列前幾項為S={0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ...}。

已知F(2) = 45、F(4) = 4284990、F(100) = 26365463243、F(10^4) = 2495838522951。

請求出F(10^8)。

--