Matrix exponentiation to calculate power of { tMat } ^ n - 1 store res in " res " matrix .
while ( n ) { if ( n & 1 ) { ll tmp [ 2 ] [ 2 ] ; 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 = n / 2 ; ll tmp [ 2 ] [ 2 ] ; 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 ] ; }