Matrix exponentiation to calculate power of { tMat } ^ n - 1 store res in " res " matrix .
while ( $ n ) { if ( $ n & 1 ) { $ tmp = array_fill ( 0 , 2 , array_fill ( 0 , 2 , 0 ) ) ; $ tmp [ 0 ] [ 0 ] = ( $ res [ 0 ] [ 0 ] * $ tMat [ 0 ] [ 0 ] + $ res [ 0 ] [ 1 ] * $ tMat [ 1 ] [ 0 ] ) % $ MOD ; $ tmp [ 0 ] [ 1 ] = ( $ res [ 0 ] [ 0 ] * $ tMat [ 0 ] [ 1 ] + $ res [ 0 ] [ 1 ] * $ tMat [ 1 ] [ 1 ] ) % $ MOD ; $ tmp [ 1 ] [ 0 ] = ( $ res [ 1 ] [ 0 ] * $ tMat [ 0 ] [ 0 ] + $ res [ 1 ] [ 1 ] * $ tMat [ 1 ] [ 0 ] ) % $ MOD ; $ tmp [ 1 ] [ 1 ] = ( $ res [ 1 ] [ 0 ] * $ tMat [ 0 ] [ 1 ] + $ res [ 1 ] [ 1 ] * $ tMat [ 1 ] [ 1 ] ) % $ MOD ; $ res [ 0 ] [ 0 ] = $ tmp [ 0 ] [ 0 ] ; $ res [ 0 ] [ 1 ] = $ tmp [ 0 ] [ 1 ] ; $ res [ 1 ] [ 0 ] = $ tmp [ 1 ] [ 0 ] ; $ res [ 1 ] [ 1 ] = $ tmp [ 1 ] [ 1 ] ; } $ n = ( int ) ( $ n / 2 ) ; $ tmp = array_fill ( 0 , 2 , array_fill ( 0 , 2 , 0 ) ) ; $ tmp [ 0 ] [ 0 ] = ( $ tMat [ 0 ] [ 0 ] * $ tMat [ 0 ] [ 0 ] + $ tMat [ 0 ] [ 1 ] * $ tMat [ 1 ] [ 0 ] ) % $ MOD ; $ tmp [ 0 ] [ 1 ] = ( $ tMat [ 0 ] [ 0 ] * $ tMat [ 0 ] [ 1 ] + $ tMat [ 0 ] [ 1 ] * $ tMat [ 1 ] [ 1 ] ) % $ MOD ; $ tmp [ 1 ] [ 0 ] = ( $ tMat [ 1 ] [ 0 ] * $ tMat [ 0 ] [ 0 ] + $ tMat [ 1 ] [ 1 ] * $ tMat [ 1 ] [ 0 ] ) % $ MOD ; $ tmp [ 1 ] [ 1 ] = ( $ tMat [ 1 ] [ 0 ] * $ tMat [ 0 ] [ 1 ] + $ tMat [ 1 ] [ 1 ] * $ tMat [ 1 ] [ 1 ] ) % $ MOD ; $ tMat [ 0 ] [ 0 ] = $ tmp [ 0 ] [ 0 ] ; $ tMat [ 0 ] [ 1 ] = $ tmp [ 0 ] [ 1 ] ; $ tMat [ 1 ] [ 0 ] = $ tmp [ 1 ] [ 0 ] ; $ tMat [ 1 ] [ 1 ] = $ tmp [ 1 ] [ 1 ] ; }