I was trying to find a solution to precompute for each $$$i, inv_i = (k^i)^{-1} \mod{p}$$$. I know the standard method using binary exponention, that is $$$inv_i = (k^i)^{p - 2}$$$ however this precomputation works in $$$O(N \log P)$$$. Is there any faster method to do this.

I know that if we instead precompute $$$inv_i = i^{-1} \mod{p}$$$ we can use this code to do this in $$$O(N)$$$, however I'm not sure how to modify this to work for any $$$k^i$$$.

Here is the code we can use for computing $$$inv_i = i^{-1} \mod{p}$$$

Edit: I just noticed that we can rewrite $$$inv_i = inv_{i-1} * k^{-1} \mod{p}$$$. So we just compute $$$k^{\mod - 2}$$$ and then use this relation.