Original problem statement from https://code.google.com/codejam/contest/5254487/dashboard#s=p1:
Watson and Sherlock are gym buddies.
Their gym trainer has given them three numbers, $A, B$, and $N$, and has asked Watson and Sherlock to pick two different positive integers $i$ and $j$, where $i$ and $j$ are both less than or equal to $N$. Watson is expected to eat exactly $i^A$ sprouts every day, and Sherlock is expected to eat exactly $j^B$ sprouts every day.
Watson and Sherlock have noticed that if the total number of sprouts eaten by them on a given day is divisible by a certain integer $K$, then they get along well that day.
So, Watson and Sherlock need your help to determine how many such pairs of $(i, j)$ exist, where $i ≠ j$. As the number of pairs can be really high, please output it modulo $10^9+ 7 (1000000007)$.
So basically how many pairs $(i, j)$ exists, such that $$i^A + j^B = 0\;(mod\,K)$$ while $i,j\le N$ and $i \ne j$?
What is the correct way to solve this and what is the logic behind it?
Thanks!