 # 2^n modulus 10^9+7

how to find the 2^n with n<=10^14
and modulus it by 10^9+7

2 Likes

also find the a^b for very large a and b a,b<=10^14

Hello, you can do it by : “modular exponentation by squaring”, you can look about it here : http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Best,

Chaitanya.

In general you can find a ^ b by using : “exponentation by squaring” : http://en.wikipedia.org/wiki/Exponentiation_by_squaring

can we use BigInteger in java to calculate (2^(10^14))%m…???

where m = 10^9+7

1 Like

Try this tutorial this will be really helpful for you.

2 Likes

use repeated squaring with mod

time complexity : O(logN)

``````  long long int cal(long long int N,long long int pow,long long int MOD){

if(N==0 || N===1) return N%MOD;

if(pow==0) return 1;

if(mod==1) return 0;

long long int ans=1;

while(pow){

if(pow%2){

ans=(ans*N)%MOD;
}

N=(N*N)%MOD;
pow/=2;
}
return ans;
}
``````

HAPPY CODING

Perfer my code school modular exponentiation video . its help you .

you can use the fast exponentiation method to find such big powers of N