出題者說若這題解完，可以解

d639. 企鵝村三兄弟penguin

結果我剛好倒過來，先解難的，在解比較簡單的這一題....

首先這題不可能用dp來做，因為數字太大了，沒有這麼多空間可以用來儲存

所以我們從矩陣的方法來下手

我們可以觀察到這個數列 a1 a2 a3 a4 ....有以下性質

但k可能= 2147483647   我們不可能將A連成這麼多次

所以我們可以先算出A (A^2) (A^4) (A^8) (A^16) ....的矩陣結果

接下來再把這些結果變成矩陣連乘，例如

我們算出 A^k 接下來在將他乘上向量[ 1 1 ] 即可找出解答

(作矩陣運算時記得取mod10007)