@Swayam Bhardwaj:
Did you copy-paste some c-code? Your ";" suggest this....
Hints: No need to do the modulo more than once (finally). Python is able to calculate using unlimited large integers, no need to keep intemediate results in restricted ranges like "long long" or whatever.
If this is not enough speed-up, think about using psyco
import psyco
psyco.full()
after moving the main loop into a function.
cheers Daft