Help: overflow with (a*b) mod c

[bugzpodder]

Okay, I am using MIPS 32... but it doesnt really matter since i just want to deal with this issue in a more abstract level (relevant to probably every assembly lang, although i am no expert).

Anyways: the problem - compute r=(a*b) mod c
input restrictions: 0<=a,b,c<2^31 and c is non-zero
for any of you not familiar with mod, u=v mod w means u is the non-negative remainder you get when you divide v by w.
that means r<c and the output fits in a 32-bit register.
The problem is with overflow. a*b can be as many as 64-bits (the case i am interested in). computing a mod c and b mod c may not help at all since they can still be over 32-bits. note that if we want to compute u=v mod w, and v is 32-bits, it only takes 2 instructions (divide, get result). but in this case... the best algorithm i've implemented takes around 800 instructions. is there a fast and savvy way to do this efficiently?
technical details, when multiply in MIPS, the result is stored in two registers, HI and Lo, and Hi contains the higher order 32-bits and Lo contains lower order 32-bits of the product. thats probalby all u need to know about mips.