has a solution iff . So is solvable iff .
Therefore .
for which integers with does the congruence have solutions? For each case when there are solutions, find how many solutions are not congruent modulo 1001.
Originally, I thought this problem might have something to do with multiplicative inverses, but I didn't get anywhere on that front.
If it matters, I calculated to be 77.