How to calculate 2 ^ n modulo 1000000007, n = 10 ^ 9

Question

What is the fastest way to calculate this, I saw how some people used matrices, and when I searched the Internet, they talked about eigenvalues ​​and eigenvectors (I don’t know about this) ... a question arose that reduced to the recursive equation f ( n) = (2 * f (n-1)) + 2 and f (1) = 1, n can be up to 10 ^ 9 .... I already tried using DP, storing up to 1,000,000 values ​​and using the general fast exponential method , all this time im usually weak in these modular issues that require calculating large values

Answer 1

f(n) = (2*f(n-1)) + 2 with f(1)=1 

equivalently

 (f(n)+2) = 2 * (f(n-1)+2) = ... = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1) 

so finally

 f(n) = 3 * 2^(n-1) - 2 

where you can apply fast modular nutritional methods.

Answer 2

Modular exponentiation by the method of square and multiplication:

 function powerMod(b, e, m) x := 1 while e > 0 if e%2 == 1 x, e := (x*b)%m, e-1 else b, e := (b*b)%m, e//2 return x 

Answer 3

 //Include library const int mod = 1e9+7; //Here base is assumed to be 2 int cal_pow(int x){ int res; if (x == 0) res=1; else if (x == 1) res=2; else { res = cal_pow(x/2); if (x % 2 == 0) res = (res * res) % mod; else res = (((res*res) % mod) * 2) % mod; } return res; } int main(){ int n, ans; cin >> n; ans = cal_pow(n); cout << ans; return 0; }