Fibonacci Power |  ; Iterative function to compute modular power ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now ; Helper function that multiplies 2 matrices F and M of size 2 * 2 , and puts the multiplication result back to F [ ] [ ] ; Helper function that calculates F [ ] [ ] raise to the power n and puts the result in F [ ] [ ] Note that this function is designed only for fib ( ) and won 't work as general power function ; Function that returns nth Fibonacci number ; Driver Code
mod = 1000000007 ; NEW_LINE def modularexpo ( x , y , p ) : NEW_LINE INDENT res = 1 ; NEW_LINE x = x % p ; NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p ; NEW_LINE DEDENT y = y >> 1 ; NEW_LINE x = ( x * x ) % p ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def multiply ( F , M , m ) : NEW_LINE INDENT x = ( ( F [ 0 ] [ 0 ] * M [ 0 ] [ 0 ] ) % m + ( F [ 0 ] [ 1 ] * M [ 1 ] [ 0 ] ) % m ) % m ; NEW_LINE y = ( ( F [ 0 ] [ 0 ] * M [ 0 ] [ 1 ] ) % m + ( F [ 0 ] [ 1 ] * M [ 1 ] [ 1 ] ) % m ) % m ; NEW_LINE z = ( ( F [ 1 ] [ 0 ] * M [ 0 ] [ 0 ] ) % m + ( F [ 1 ] [ 1 ] * M [ 1 ] [ 0 ] ) % m ) % m ; NEW_LINE w = ( ( F [ 1 ] [ 0 ] * M [ 0 ] [ 1 ] ) % m + ( F [ 1 ] [ 1 ] * M [ 1 ] [ 1 ] ) % m ) % m ; NEW_LINE F [ 0 ] [ 0 ] = x ; NEW_LINE F [ 0 ] [ 1 ] = y ; NEW_LINE F [ 1 ] [ 0 ] = z ; NEW_LINE F [ 1 ] [ 1 ] = w ; NEW_LINE DEDENT def power ( F , n , m ) : NEW_LINE INDENT if ( n == 0 or n == 1 ) : NEW_LINE INDENT return ; NEW_LINE DEDENT M = [ [ 1 , 1 ] , [ 1 , 0 ] ] ; NEW_LINE power ( F , n // 2 , m ) ; NEW_LINE multiply ( F , F , m ) ; NEW_LINE if ( n % 2 != 0 ) : NEW_LINE INDENT multiply ( F , M , m ) ; NEW_LINE DEDENT DEDENT def fib ( n , m ) : NEW_LINE INDENT F = [ [ 1 , 1 ] , [ 1 , 0 ] ] ; NEW_LINE if ( n == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT power ( F , n - 1 , m ) ; NEW_LINE return F [ 0 ] [ 0 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 ; NEW_LINE base = fib ( n , mod ) % mod ; NEW_LINE expo = fib ( n , mod - 1 ) % ( mod - 1 ) ; NEW_LINE result = modularexpo ( base , expo , mod ) % mod ; NEW_LINE print ( result ) ; NEW_LINE DEDENT