Cows in the FooLand city are interesting animals. One of their specialities is related to producing offsprings. A cow in FooLand produces its first calve (female calf) at the age of two years and proceeds to produce other calves (one female calf a year).
Now the farmer Harold wants to know how many animals would he have at the end of N years, if we assume that none of the calves dies, given that initially, he has only one female calf?
Since the answer can be huge, print it modulo 10^{9}+7.
 
Example 1:
Input: N = 2
Output: 2
Explanation: At the end of 1 year, he will have 
only 1 cow, at the end of 2 years he will have 
2 animals (one parent cow C1 and other baby 
calf B1 which is the offspring of cow C1).
Example 2:
Input: N = 4
Output: 5
Explanation: At the end of 1 year, he will have
only 1 cow, at the end of 2 years he will have
2 animals (one parent cow C1 and other baby
calf B1 which is the offspring of cow C1). At
the end of 3 years, he will have 3 animals (one
parent cow C1 and 2 female calves B1 and B2, C1
is the parent of B1 and B2).At the end of 4 
years,he will have 5 animals (one parent cow C1,
3 offsprings of C1 i.e. B1, B2, B3 and one 
offspring of B1).
 
Your Task:
You don't need to read or print anything. Your task is to complete the function TotalAnimal() which takes N as input parameter and returns the total number of animals at the end of N years modulo 10^{9} + 7.
 
Expected Time Complexity: O(log_{2}N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
	def TotalAnimal(self, N):
		# Code here

Solutions:
class Solution:

	def multiple(self, a, b, m):
		ans = [[0, 0], [0, 0]]
		ans[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % m
		ans[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % m
		ans[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % m
		ans[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % m
		return ans

	def binpow(self, a, n, m):
		ans = [[1, 0], [0, 1]]
		while n > 0:
			if n & 1:
				ans = self.multiple(ans, a, m)
			a = self.multiple(a, a, m)
			n >>= 1
		return ans

	def TotalAnimal(self, N):
		M = int(1000000000.0 + 7)
		a = [[1, 1], [1, 0]]
		a = self.binpow(a, N, M)
		return a[0][0]


class Solution:

	def fast_fibonacci(self, ans, n):
		if n == 0:
			ans[0] = 0
			ans[1] = 1
			return
		self.fast_fibonacci(ans, n // 2)
		a = ans[0]
		b = ans[1]
		c = 2 * b - a
		if c < 0:
			c = c + 1000000007
		c = a * c % 1000000007
		d = (a * a + b * b) % 1000000007
		if n % 2 == 0:
			ans[0] = c
			ans[1] = d
		else:
			ans[0] = d
			ans[1] = (c + d) % 1000000007

	def TotalAnimal(self, N):
		ans = [0, 0]
		self.fast_fibonacci(ans, N + 1)
		return ans[0]


class Solution:

	def TotalAnimal(self, N):
		maxVal = pow(10, 9) + 7

		def fib(n):
			F = [[1, 1], [1, 0]]
			if n == 0:
				return 0
			power(F, n)
			return F[0][0]

		def multiply(F, M):
			x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
			y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
			z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
			w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
			F[0][0] = x % maxVal
			F[0][1] = y % maxVal
			F[1][0] = z % maxVal
			F[1][1] = w % maxVal

		def power(F, n):
			if n == 0 or n == 1:
				return
			M = [[1, 1], [1, 0]]
			power(F, n // 2)
			multiply(F, F)
			if n % 2 != 0:
				multiply(F, M)
		return fib(N)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.TotalAnimal(N)
		print(ans)


class Solution:

	def multiply(self, mat, m):
		temp = [[0, 0], [0, 0]]
		x = 1000000007
		temp[0][0] = mat[0][0] * m[0][0] + mat[0][1] * m[1][0]
		temp[0][1] = mat[0][0] * m[0][1] + mat[0][1] * m[1][1]
		temp[1][0] = mat[1][0] * m[0][0] + mat[1][1] * m[1][0]
		temp[1][1] = mat[1][0] * m[0][1] + mat[1][1] * m[1][1]
		mat[0][0] = temp[0][0] % x
		mat[0][1] = temp[0][1] % x
		mat[1][0] = temp[1][0] % x
		mat[1][1] = temp[1][1] % x

	def mat_power(self, mat, n):
		if n == 1:
			return
		self.mat_power(mat, n // 2)
		self.multiply(mat, mat)
		m = [[1, 1], [1, 0]]
		if n % 2 != 0:
			self.multiply(mat, m)

	def TotalAnimal(self, N):
		mat = [[1, 1], [1, 0]]
		if N == 0:
			return 1
		self.mat_power(mat, N + 1)
		return mat[0][1]


class Solution:

	def TotalAnimal(self, N):

		def multiply(mat1, mat2):
			temp1 = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]
			temp2 = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]
			temp3 = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]
			temp4 = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]
			mat1[0][0] = temp1 % (10 ** 9 + 7)
			mat1[0][1] = temp2 % (10 ** 9 + 7)
			mat1[1][0] = temp3 % (10 ** 9 + 7)
			mat1[1][1] = temp4 % (10 ** 9 + 7)

		def find_pr(mat, n):
			if n == 1:
				return
			find_pr(mat, n // 2)
			multiply(mat, mat)
			m = [[1, 1], [1, 0]]
			if n & 1:
				multiply(mat, m)
		if N == 0:
			return 0
		mat = [[1, 1], [1, 0]]
		find_pr(mat, N)
		return mat[0][0] % (10 ** 9 + 7)


MOD = 1000000007

def mfib(n):
	if n == 0:
		return 0
	(m, r) = ([[0, 1], [1, 1]], [[1, 0], [0, 1]])
	n -= 1
	while n > 0:
		if n & 1 != 0:
			t00 = (r[0][0] * m[0][0] % MOD + r[0][1] * m[1][0] % MOD) % MOD
			t01 = (r[0][0] * m[0][1] % MOD + r[0][1] * m[1][1] % MOD) % MOD
			t10 = (r[1][0] * m[0][0] % MOD + r[1][1] * m[1][0] % MOD) % MOD
			t11 = (r[1][0] * m[0][1] % MOD + r[1][1] * m[1][1] % MOD) % MOD
			r = [[t00, t01], [t10, t11]]
		t00 = (m[0][0] * m[0][0] % MOD + m[0][1] * m[1][0] % MOD) % MOD
		t01 = (m[0][0] * m[0][1] % MOD + m[0][1] * m[1][1] % MOD) % MOD
		t10 = (m[1][0] * m[0][0] % MOD + m[1][1] * m[1][0] % MOD) % MOD
		t11 = (m[1][0] * m[0][1] % MOD + m[1][1] * m[1][1] % MOD) % MOD
		m = [[t00, t01], [t10, t11]]
		n >>= 1
	return r[1][1]

class Solution:

	def TotalAnimal(self, n):
		return mfib(n + 1)