modulo problem

how to calculate ((2^n)/3)%1000000007…
if n can be as large as 10^18…

First calculate 2^n using modular exponentiation( Code is given below), let this value be x,

Here’s the link containing the algorithm : click here

You can perform division in modulo by calculating the modular multiplicative inverse of 3, let this value be y.

Now calculate (x*y)%1000000007

Here’s the code for calculating multiplicative inverse:

long long int inv(long long int a) {
return pow_(a,mod-2,mod);

Here pow_ is the function for modular exponentiation:

 #define mod 1000000007
 long long int pow_(long long int base,long long int exp,long long int m)
  long long int ret=1;
   return ret%m;
1 Like

hey its not working ans for n=34 should be 726623026 but its not going this way… :frowning:

Since you are dividing 2^n by 3 you need to perform the multiplication of 2^n by the modular inverse of 3%1000000007.

Since 3 is a prime number, you can use Fermat’s Little Theorem to calculate the inverse as:

3^1000000005 % 1000000007 = 333333336

Then you can multiply it with 2^34 % 1000000007 and get your final result.

I’m getting 59956355 in Python…

How did you calculate this answer? Show me your code.

You can also see the question WCOUNT in easy section.
Multiplicative inverse was used in this question.
I have used this method and got AC in this question.