If your code gives wrong answers, check these: Are you taking mod after every operation? Are you handling negative results correctly? Are you using the right modulus value?
Test with small values where you can compute the answer by hand. If mod works on small inputs but fails on large ones, you probably have overflow somewhere.
Print intermediate values to see where the computation goes wrong.