How to efficiently calculate the value of $$$ \frac{3^{n}-1}{2} $$$ modulo an even number $$$ p $$$, when the bound on $$$ n $$$ is up to $$$ 10^{18} $$$ and $$$ p $$$ is up to $$$ 10^9 $$$?
Large Numbers Modulo a Non-Prime
How to efficiently calculate the value of $$$ \frac{3^{n}-1}{2} $$$ modulo an even number $$$ p $$$, when the bound on $$$ n $$$ is up to $$$ 10^{18} $$$ and $$$ p $$$ is up to $$$ 10^9 $$$?