Matrix exponentiation to calculate power of { tMat } ^ n - 1 store res in " res " matrix .
while ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT tmp = [ [ 0 for x in range ( 2 ) ] for y in range ( 2 ) ] ; NEW_LINE tmp [ 0 ] [ 0 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 0 ] [ 1 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 0 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 1 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE res [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; NEW_LINE res [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; NEW_LINE res [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; NEW_LINE res [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; NEW_LINE DEDENT n = n // 2 ; NEW_LINE tmp = [ [ 0 for x in range ( 2 ) ] for y in range ( 2 ) ] ; NEW_LINE tmp [ 0 ] [ 0 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 0 ] [ 1 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 0 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 1 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tMat [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; NEW_LINE tMat [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; NEW_LINE tMat [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; NEW_LINE tMat [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; NEW_LINE DEDENT