A couple of tests that I obtained from my working program:

998 999 972
48 63 159 174 270 285 381 396 492 507 603 618 714 729 825 840 936 951

998 999 900
-1

Scroll down for hint.
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v

Hint:  (A*B) MOD C = ((A MOD C) * B) MOD C

Edited by author 13.10.2011 19:15

Edited by author 13.10.2011 19:16

With numbers 998 999 972 answer must be -1< because, 1 < M < 999