觀察 Constraints 可以發現 MaxN=1e9+9，無法只用迴圈 → 快速幂次
s + t√2 = ( x + y√2 ) ^ n，可以將 整數 和 √2 的係數項以「向量」 的形式描述。
快速幂次的矩陣該如何推導呢 ？ [ [ x, 2y ], [ y, x ] ]
( x + y√2 ) ^ (n+1) = ( x + y√2 )( x + y√2 )^n = ( x + y√2 ) ( s + t√2 ）
s(n+1) = x*s(n) + 2y*t(n)

t (n+1) = y*s(n) +   x*t(n)

init :  ( x + y√2 ) ^ 0 = 1 → s0 = 1, t0 = 0
吳教授的 AP325 有標記是簡化版，原版的內容可以參考 c903: 數字的挑戰
將( 2+√3 )^n 展開後依照 s + t√3 的形式描述，實作細節可以參照這題的做法。

這題的關鍵：找到他的共軛根：( 2 - √3 )^n ，展開後可以得到 s - t√3 的形式。
兩者相加後必定是整數：( 2 + √3 )^n + ( 2 - √3 )^n = 2s，而且 0 < ( 2 - √3 )^n < 1，回到要求可以推得：( 2 + √3 )^n 的整數部分 = 2s - ( 2 - √3 )^n  > 2s - 1。
至於快冪次的矩陣可以從遞迴推導：
( 2+√3 )^( n+1 ) = ( 2+√3 )( 2+√3 )^n = ( 2+√3 ) ( s+t√3 ）
s(n+1) = 2s(n) + 3t(n)

t (n+1) =   s(n) + 2t(n)

s0=1 ，t0=0
對於上述的概要如果有不清楚可以參考範例，連結裡面是用  3+√5

觀察 Constraints 可以發現 MaxN=1e9+9，無法只用迴圈 → 快速幂次
s + t√2 = ( x + y√2 ) ^ n，可以將 整數 和 √2 的係數項以「向量」 的形式描述。
快速幂次的矩陣該如何推導呢 ？ [ [ x, 2y ], [ y, x ] ]
( x + y√2 ) ^ (n+1) = ( x + y√2 )( x + y√2 )^n = ( x + y√2 ) ( s + t√2 ）
s(n+1) = x*s(n) + 2y*t(n)

t (n+1) = y*s(n) +   x*t(n)

init :  ( x + y√2 ) ^ 0 = 1 → s0 = 1, t0 = 0
吳教授的 AP325 有標記是簡化版，原版的內容可以參考 c903: 數字的挑戰
將( 2+√3 )^n 展開後依照 s + t√3 的形式描述，實作細節可以參照這題的做法。

這題的關鍵：找到他的共軛根：( 2 - √3 )^n ，展開後可以得到 s - t√3 的形式。
兩者相加後必定是整數：( 2 + √3 )^n + ( 2 - √3 )^n = 2s，而且 0 < ( 2 - √3 )^n < 1，回到要求可以推得：( 2 + √3 )^n 的整數部分 = 2s - ( 2 - √3 )^n  > 2s - 1。
至於快冪次的矩陣可以從遞迴推導：
( 2+√3 )^( n+1 ) = ( 2+√3 )( 2+√3 )^n = ( 2+√3 ) ( s+t√3 ）
s(n+1) = 2s(n) + 3t(n)

t (n+1) =   s(n) + 2t(n)

s0=1 ，t0=0
對於上述的概要如果有不清楚可以參考範例，連結裡面是用  3+√5

原版的題目是其實是全國賽的題目，題目是算出第N組C(m,2) = n^2的解mod 1e9+7。