這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4，直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。

這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4，直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。

補充：第4項～第2781671項為一次循環的所有內容。

這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4，直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。

補充：第4項～第2781671項為一次循環的所有內容。

其實本題正解應該是矩陣快速冪，

想法直關，

也很好寫。

循環區段並不是這麼好找，

而且 mod 很大時，

循環區段可能更大，

比賽中也不一定可以即時找到，

還是好好寫矩陣快速冪好了～^^

時間複雜度：$\Theta(k^3\log n)$

這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4，直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。

補充：第4項～第2781671項為一次循環的所有內容。

很感謝提供解題方向，另外心得是，整個循環應該是從第二個1 開始，也就是「1,1,3,5...]，長度仍為2781668