Find the nth Carol Number.
A Carol number is an integer of form 4^{n} – 2^{(n+1)} – 1. An equivalent formula is (2^{n}-1)^{2} – 2.
 
Example 1:
Input:
n = 2
Output:
7
Explanation:
After replacing the 
value of n in the 
formula we get 7.
 
Example 2:
Input:
n = 4
Output:
223
Explanation:
After replacing the 
value of n in the 
formula we get 223.
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function nthCarolNumber() which takes an integer n and returns the value mod 10^{9}+7.
 
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= n <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3
class Solution:
    def nthCarolNumber (self,n):
        # code here 

Solutions:
class Solution:

	def nthCarolNumber(self, n):
		m = 10 ** 9 + 7
		b = 1
		a = 2
		while n != 1:
			if n % 2:
				b = b * a % m
				n = (n - 1) // 2
			else:
				n = n // 2
			a = a ** 2 % m
		return ((a * b - 1) ** 2 - 2) % m


m = 1000000007

def pow(a, b):
	if b == 1:
		return a
	res = pow(a * a % m, b // 2) % m
	if b % 2 == 0:
		return res
	else:
		return a * res

class Solution:

	def nthCarolNumber(self, n):
		return (pow(4, n) - pow(2, n + 1) - 1) % m


import math

class Solution:

	def nthCarolNumber(self, n):
		M = 1000000007
		S = pow(2, n, M) - 1
		S = pow(S, 2, M) - 2
		return S


class Solution:

	def nthCarolNumber(self, n):
		x = 2
		r = 1
		m = 1000000007
		while n > 0:
			if n & 1:
				r = r % m * (x % m) % m
			x = x % m * (x % m) % m
			n = n >> 1
		r = (r - 1) * (r - 1) % m - 2
		return r