inverse modulo

[darkX]

For each Q, print a single integer in new line denoting inverse modulo of the number of pairs which satisfies the given equation and also present in the given array(A) with 10^9+9 or -1 if there is no such pair exist.

Basically how to get inverse modulo of the number with 10^9+9

[icy1]

http://mathworld.wolfram.com/ModularInverse.html

I'm not really into math, but as I understand it, if you're given a number, e.g. b=2, and a modulo, usually a prime, e.g. m=7, find a number, n or whatever, that when multiplied against b, the product % m will be 1. So (b*n) % m == 1

(2 * 4) % 7 is 1.

So answer is 4. In your case you have a giant prime(?) m and this is probably some running contest question, so I'll stop talking now.