I tried to solved THIS PROBLEM on hackerearth, but I am getting wrong answer.This is link to my code please help me in finding what’s wrong with my approach.

# Problem in solving this problem based on bits and array?

Overflow is the problem.

In the function **moduloExp()**, all the calculations are done modulo M\ (10^{10} + 11).

But, the intermediate result of **ans * cnt** can be of order M^{2} which is greater than the limit of `long`

.

**UPDATE 1**:

Note that M = 10^{10} + 11 = 3 \cdot 191 \cdot 17452007 = m_1 \cdot m_2 \cdot m_3. So we can use Chinese Remainder Theorem **(CRT)** to solve the following system of linear congruences.

The unique solution of this system is x = \sum\ a_i \cdot y_i \cdot z_i \ (mod\ M)

Where, y_i = M / m_i and z_i = y_i^{-1}\ (mod\ m_i).

Usually **Euclid’s Extended Algorithm** is used to find y^{-1} (as m_1,\ m_2,\ m_3 are pairwise coprime). But in this case you can also use **Fermat’s Little Theorem** (as m_1,\ m_2,\ m_3 are prime themselves).

The idea in the above approach is to first find the answer mod m_1,\ m_2,\ m_3 (which is easy as they are primes and much smaller than M) and then combine those results to find the answer mod M using **CRT**.

Here is the accepted solution in **C++**: https://www.hackerearth.com/submission/10428557/

**OR**

You can simply use a language that supports big integers (like **Python**). The builtin function **pow(a, b, c)** in Python calculates a^{b}\ mod\ c.

Here is the accepted solution in **Python**: https://www.hackerearth.com/submission/10429278/

**UPDATE 2**: Detailed Explanation

Let the actual answer be x. We have to find x\ \%\ M (10^{10} + 11). But, since M is too large, the intermediate calculations do not fit in `long long`

.

**CRT** states that if we know the value of x\ \%\ m_i\ (i = 1,2,...,k), then we can find the value of x\ \%\ M where M = \prod\ m_i = m_1 \cdot m_2\ \cdot \dots\ \cdot m_k. Given that m_1,\ m_2, \dots,\ m_k should be pairwise coprime.

M can be prime factored as M = 3 \cdot 191 \cdot 17452007. So, m_1 = 3,\ m_2 = 191,\ m_3 = 17452007 and these are pairwise coprime.

Find a_1 = x\ \%\ m_1 ,\ a_2 = x\ \%\ m_2,\ a_3 = x\ \%\ m_3.

Now, x\ \%\ M = \sum\ a_i \cdot y_i \cdot z_i \ (mod\ M) (y_i and z_i have already been described above).

To read more about **CRT**, go through the above link.

Thanks for pointing that out, What is the solution then.

I tried BigInteger after you mentioned overflow but getting TLE.

I’ve updated my answer and added the solution explanation. Have a look.

z_i = y_i^{-1} (\%\ m_i) means that z_i imes y_i \equiv\ 1\ (\%\ m_i). Here z_i is the modular multiplicative inverse of y_i. You can read about this the following link: http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

x≡a1 (mod m1)

x≡a2 (mod m2)

x≡a3 (mod m3)

How x could be congurent to a1,a2,a3 can you please simplify it. I am little weak in number theory please explain. I might be getting silly but please help.

Because the mod is different every time. Take x = 20, m1 = 6, m2 = 7, m3 = 8.

Then x = 2 (mod 6), x = 6 (mod 7), x = 4 (mod 8)