You should minimize the number of mod operations. for example when I use mod each iteration i got 0.9 sec. But when I minimized the number of mod operations I got 0.56 sec. You should use long f(java) and calculate (f mod p) when f > 10^14, but not each time you calculate your f.
