Calculate the value of 2 raised to the power of twice the binary representation of N | Python3 program to implement the above approach ; Function to find the value of power ( X , Y ) in O ( log Y ) ; Stores power ( X , Y ) ; Update X ; Base Case ; Calculate power ( X , Y ) ; If Y is an odd number ; Update res ; Update Y ; Update X ; Function to calculate ( 2 ^ ( 2 * x ) ) % ( 10 ^ 9 + 7 ) ; dp [ N ] * dp [ N ] : Stores value of ( 2 ^ ( 2 * x ) ) % ( 10 ^ 9 + 7 ) ; Base Case ; Iterate over the range [ 3 , N ] ; Stores rightmost bit of i ; Stores the value of ( i - y ) ; If x is power of 2 ; Update dp [ i ] ; Update dp [ i ] ; Driver Code
M = 1000000007 ; NEW_LINE def power ( X , Y ) : NEW_LINE INDENT res = 1 ; NEW_LINE X = X % M ; NEW_LINE if ( X == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT while ( Y > 0 ) : NEW_LINE INDENT if ( Y % 2 == 1 ) : NEW_LINE INDENT res = ( res * X ) % M ; NEW_LINE DEDENT Y = Y >> 1 ; NEW_LINE X = ( X * X ) % M ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def findValue ( N ) : NEW_LINE INDENT dp = [ 0 ] * ( N + 1 ) ; NEW_LINE dp [ 1 ] = 2 ; NEW_LINE dp [ 2 ] = 1024 ; NEW_LINE for i in range ( 3 , N + 1 ) : NEW_LINE INDENT y = ( i & ( - i ) ) ; NEW_LINE x = i - y ; NEW_LINE if ( x == 0 ) : NEW_LINE INDENT dp [ i ] = power ( dp [ i // 2 ] , 10 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = ( dp [ x ] * dp [ y ] ) % M ; NEW_LINE DEDENT DEDENT return ( dp [ N ] * dp [ N ] ) % M ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 150 ; NEW_LINE print ( findValue ( n ) ) ; NEW_LINE DEDENT