600 - This was an UVa problem. Except for the factorial twist, this is pretty straightforward (if you've done the UVa, I mean.. I didn't.) The thing is to note that a^b % m has a rho function-like kind of thing, so for that, you'll need to find out what b is.. which can be done recursively. The factorial twist doesn't add much to it, if you happen to notice that for any b >= m, b! % m = 0.
1000 - I have no idea how to do this. Looked like it could be done with some sort of inclusion-exclusion, but the intermediate values were way too huge. Also though of some sort of matrix multiplication thing, but couldn't quite come up with it.. ah well.
How did everyone else found the problems?