Calculate the value of 2 raised to the power of twice the binary representation of N | Java 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
class GFG { static final long M = 1000000007 ; static long power ( long X , long Y ) { long res = 1 ; X = X % M ; if ( X == 0 ) return 0 ; while ( Y > 0 ) { if ( Y % 2 == 1 ) { res = ( res * X ) % M ; } Y = Y >> 1 ; X = ( X * X ) % M ; } return res ; } static long findValue ( int N ) { long [ ] dp = new long [ N + 1 ] ; dp [ 1 ] = 2 ; dp [ 2 ] = 1024 ; for ( int i = 3 ; i <= N ; i ++ ) { int y = ( i & ( - i ) ) ; int x = i - y ; if ( x == 0 ) { dp [ i ] = power ( dp [ i / 2 ] , 10 ) ; } else { dp [ i ] = ( dp [ x ] * dp [ y ] ) % M ; } } return ( dp [ N ] * dp [ N ] ) % M ; } public static void main ( String [ ] args ) { int n = 150 ; System . out . print ( findValue ( n ) ) ; } }