Modular inverse of 1 to n in O(n) time

 you can calculate modular inverses to first n integers in O(n) time using this formula: inv[i] = (-(p+i-1)/i + inv[p%i] + p)%p;