Changing Rabin-Karp without modulo to Rabin-Karp with modulo
Don't wait to do the modular reduction at the end.  Every time you do an addition or multiplication, immediately reduce modulo the modulus.  This keeps all intermediate results small.