It took me days to come up with a solution to GCDMOD, so I wish to share it with people with the complete approach on how I did it.

Step 1: **Choosing the algorithm to calculate gcd of two numbers**

This was a crucial step, I was confused between using a library for big integers or something. But when the idea clicked, I found out that normal Euclidean GCD was enough (Note normal one, not extended one)

Step 2: **Tweaking the algorithm**

Now next step is to tweak the algorithm so that we can get out desired results. For this, we will use two properties from modular mathematics which are

Now we know that the first step of the Euclidean GCD algorithm is that we recall **gcd(b%a, a)**.

Step 3: **The remaining workout**

Now let’s solve the question for A, B, N, and A eq B

As we discussed we will first step of the Euclidean algorithm will be

Now (A^N)\%(A-B) or (B^N)\%(A-B) can be calculated using **modular exponentiation**

Now all left is to var we calculated is within the range of long long int and now just have to calculate gcd with (A-B)

Step 4: **Checking edge cases**

In this approach, there is only one edge case that is A = B. When this happens, the answer is simple 2 imes(A^N \% 1000000007)

If you have any doubts or think I went wrong somewhere please do tell me. Hope this helps other coders.