Given a number positive number N, find value of f_{0} + f_{1} + f_{2} + . + f_{N} where f_{i} indicates ith Fibonacci number.
Remember that f_{0} = 0, f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, 
Since the answer can be very large, answer modulo 1000000007 should be returned.
Example 1:
Input:
N = 3
Output:
4
Explanation:
0 + 1 + 1 + 2  = 4
Example 2:
Input :
N = 4
Output :
7
Explanation :
0 + 1 + 1 + 2 + 3 = 7
Your Task:
You don't need to read input or print anything. Your task is to complete the function fibSum() which takes an integer N as input parameter and returns the sum of all the Fibonacci number from F_{0} to F_{N}.
Expected Time Complexity: O(Log N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 100000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def fibSum (self,N):

        #code here

Solutions:
class Solution:

	def fibSum(self, N):
		(a, b, i) = (1, 1, 2)
		while i < N + 2:
			(a, b, i) = (b, a + b, i + 1)
			if b >= 1000000007:
				b %= 1000000007
		return b - 1


class Solution:

	def fibSum(self, N):
		sum = 1
		a = 0
		b = 1
		for i in range(2, N + 3):
			c = a + b
			a = b
			b = c
		return (b - 1) % 1000000007


class Solution:

	def fibSum(self, N):
		l = [1, 1]
		for i in range(N):
			l.append(l[-1] % (10 ** 9 + 7) + l[-2] % (10 ** 9 + 7))
		return sum(l[:N]) % (10 ** 9 + 7)


class Solution:

	def fibSum(self, N):
		arr = [1] * N
		if N <= 2:
			return sum(arr)
		else:
			for i in range(2, N):
				arr[i] = arr[i - 1] % 1000000007 + arr[i - 2] % 1000000007
		return sum(arr) % 1000000007


class Solution:

	def fibSum(self, n):
		num = [0, 1]
		if N < 2:
			return sum(num)
		for i in range(2, N + 1):
			num.append(num[-1] % 1000000007 + num[-2] % 1000000007)
		return sum(num) % 1000000007


class Solution:

	def fibSum(self, N):
		(f1, f2) = (0, 1)
		k = [0, 1]
		s = 1
		if N == 0 | N == 1:
			return N
		for i in range(2, N + 1):
			k.append(k[-1] % (10 ** 9 + 7) + k[-2] % (10 ** 9 + 7))
		return sum(k) % (10 ** 9 + 7)


class Solution:

	def fibSum(self, N):
		F = [[1, 1], [1, 0]]
		self.power(F, N + 1)
		return (F[0][0] - 1) % 1000000007

	def multiply(self, 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
		F[0][1] = y
		F[1][0] = z
		F[1][1] = w

	def power(self, F, n):
		if n == 0 or n == 1:
			return
		M = [[1, 1], [1, 0]]
		self.power(F, n // 2)
		self.multiply(F, F)
		if n % 2 != 0:
			self.multiply(F, M)


class Solution:

	def fibSum(self, N):
		if N == 1:
			return 1
		elif N == 2:
			return 2
		else:
			(s, a, b) = (2, 1, 1)
			m = 10 ** 9 + 7
			for i in range(N - 2):
				c = (a + b) % m
				s += c
				a = b
				b = c
			return s % m


class Solution:

	def fibSum(self, N):
		dp = [0 for i in range(N + 1)]
		(dp[0], dp[1]) = (0, 1)
		for i in range(2, N + 1, 1):
			dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007
		return sum(dp) % 1000000007


class Solution:

	def fibSum(self, n):
		MOD = 1000000007
		if n == 0:
			return 0
		elif n == 1:
			return 1
		(a, b) = (0, 1)
		for i in range(2, n + 3):
			c = (a + b) % MOD
			a = b
			b = c
		return (b - 1) % MOD


class Solution:

	def fibSum(self, N):
		N = N + 3
		a = 0
		b = 1
		if N <= 0:
			print('Irrelevant input provided.')
		else:
			for i in range(2, N):
				c = a + b
				a = b
				b = c
		return (c - 1) % 1000000007


class Solution:

	def fibSum(self, N):
		mod = 10 ** 9 + 7
		res = 0
		(a, b) = (1, 1)
		while N:
			res = (res + a) % mod
			(a, b) = (b, (a + b) % mod)
			N -= 1
		return res


class Solution:

	def fibSum(self, N):
		arr = [0, 1]
		for i in range(2, N + 1):
			arr.append(arr[i - 1] % 1000000007 + arr[i - 2] % 1000000007)
		return sum(arr) % 1000000007


class Solution:

	def fibSum(self, N):
		if N == 1:
			b = [1]
		elif N != 1:
			b = [1, 1]
		for i in b:
			if len(b) < N:
				i = b[-1] % 1000000007 + b[-2] % 1000000007
				b.append(i % 1000000007)
		return sum(b) % 1000000007


class Solution:

	def fibSum(self, n):
		if n <= 0:
			return 0
		(l, r) = (0, 1)
		sm = l + r
		for i in range(2, n + 1):
			new = int(l % 1000000007) + int(r % 1000000007)
			(l, r) = (r, new)
			sm += int(new % 1000000007)
		return int(sm % 1000000007)


class Solution:

	def fibSum(self, N):
		m = 1000000007
		ans = 0
		a = 0
		b = 1
		for i in range(N):
			t = (a + b) % m
			a = b
			b = t
			ans += a
		return ans % m


class Solution:

	def fibSum(self, N):
		m = 1000000007
		x = [0, 1]
		for i in range(N - 1):
			t = (x[-1] + x[-2]) % m
			x.append(t)
		return sum(x) % m


class Solution:

	def fibSum(self, n):
		mod = 10 ** 9 + 7
		dp = [0] * (n + 5)
		dp[0] = 0
		dp[1] = 1
		sum = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
			sum = (sum % mod + dp[i] % mod) % mod
		return sum


class Solution:

	def fibSum(self, N):
		mod = 1000000007
		t = [0 for i in range(N + 1)]
		t[0] = 0
		t[1] = 1
		su = 0
		for i in range(2, N + 1):
			t[i] = (t[i - 1] + t[i - 2]) % mod
		for i in range(0, N + 1):
			su = (su + t[i]) % mod
		return su


class Solution:

	def fibSum(self, N):
		num = [0, 1]
		m = 10 ** 9 + 7
		if N < 2:
			return sum(num)
		for i in range(2, N + 1):
			num.append(num[-1] % m + num[-2] % m)
		return sum(num) % m


class Solution:

	def fibSum(self, N):
		S = 1
		M = 10 ** 9 + 7
		d = {0: 0, 1: 1}
		for i in range(2, N + 1):
			d[i] = d[i - 1] % M + d[i - 2] % M
			S += d[i]
		return S % M


class Solution:

	def fibSum(self, n):
		m = 1000000007
		dp = [0] * (n + 1)
		if n == 1 or n == 2:
			return n
		dp[0] = 0
		dp[1] = 1
		sum_ = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % m
			sum_ += dp[i]
		return int(sum_ % m)


class Solution:

	def fibSum(self, N):
		if N <= 2:
			return N
		sum = 2
		l = [0, 1, 1]
		while len(l) <= N:
			k = (l[-1] + l[-2]) % 1000000007
			sum += k
			sum = sum % 1000000007
			l.append(k)
		return sum


class Solution:

	def fibSum(self, N):
		if N == 1:
			return 1
		if N == 0:
			return 0
		(a, b, sum) = (0, 1, 1)
		for i in range(N - 1):
			c = (a + b) % (10 ** 9 + 7)
			sum = (sum + c) % (10 ** 9 + 7)
			a = b
			b = c
		return sum


class Solution:

	def fibSum(self, N):
		l = [0, 1]
		m = 1000000007
		if N < 2:
			return sum(l)
		for i in range(2, N + 1):
			l.append(l[-1] % m + l[-2] % m)
		return sum(l) % m


class Solution:

	def fibSum(self, n):
		a = 1
		b = 1
		if n == 1:
			return 1
		if n == 2:
			return 2
		mod = 1000000007
		add = 2
		for i in range(3, n + 1):
			(a, b) = (b % mod, a % mod + b % mod)
			add += b % mod
		return add % mod
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fibSum(N))


class Solution:

	def fibSum(self, N):
		a = [0, 1]
		if N == 1:
			return 0
		if N == 2:
			return 1
		for i in range(N - 1):
			a.append(a[i] % 1000000007 + a[i + 1] % 1000000007)
		return sum(a) % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fibSum(N))


class Solution:

	def fibSum(self, N):
		a = 0
		b = 1
		for i in range(2, N + 3):
			c = a + b
			a = b
			b = c
		return (c - 1) % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.fibSum(N))


class Solution:

	def fibSum(self, N):
		MOD = 1000000000.0 + 7
		num = [0, 1]
		if N < 2:
			return int(sum(num))
		for i in range(2, N + 1):
			num.append(num[-1] % MOD + num[-2] % MOD)
		return int(sum(num) % MOD)


class Solution:

	def fibSum(self, N):
		c = [0, 1]
		i = 0
		if N < 2:
			return sum(c)
		while N > 1:
			c.append(c[i] % 1000000007 + c[i + 1] % 1000000007)
			i += 1
			N -= 1
		return sum(c) % 1000000007


class Solution:
	global f
	f = [0] * 10 ** 6

	def fib(self, n):
		global f
		if n == 0:
			return 0
		if n == 1 or n == 2:
			f[n] = 1
			return f[n]
		if f[n]:
			return f[n]
		if n & 1:
			k = (n + 1) // 2
		else:
			k = n // 2
		if n & 1:
			f[n] = self.fib(k) * self.fib(k) + self.fib(k - 1) * self.fib(k - 1)
		else:
			f[n] = (2 * self.fib(k - 1) + self.fib(k)) * self.fib(k)
		return f[n]

	def fibSum(self, N):
		return (self.fib(N + 2) - 1) % (10 ** 9 + 7)


import math

class Solution:

	def fibSum(self, N):
		f = 0
		s = 1
		f_sum = [0, 1]
		if N < 2:
			return sum(f_sum)
		for i in range(2, N + 1):
			f_sum.append(f_sum[-1] % 1000000007 + f_sum[-2] % 1000000007)
		return sum(f_sum) % 1000000007


class Solution:

	def fibSum(self, N):
		m = 1000000000.0 + 7
		if N == 0:
			return 0
		if N == 1:
			return 1
		(a, b, s) = (0, 1, 1)
		for i in range(2, N + 1):
			c = int((a + b) % m)
			s = int((s + c) % m)
			(a, b) = (b, c)
		return s


class Solution:

	def fibSum(self, N):
		yo = 1000000007
		if N == 0:
			return 0
		elif N == 1:
			return 1
		else:
			N = N - 1
			sumi = 1
			past = 0
			ans = 1
			while N > 0:
				a = (sumi + past) % yo
				past = sumi % yo
				sumi = a % yo
				ans = (ans + a) % yo
				N = N - 1
			return ans


class Solution:

	def fibSum(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		(a, b) = (0, 1)
		s = 1
		for i in range(2, N + 1):
			c = (a + b) % 1000000007
			s = (s + c) % 1000000007
			a = b
			b = c
		return s


class Solution:

	def fibSum(self, N):
		num_list = [0, 1]
		if N < 2:
			return sum(num_list)
		else:
			for i in range(2, N + 1):
				num_list.append(num_list[-1] % 1000000007 + num_list[-2] % 1000000007)
			return sum(num_list) % 1000000007


class Solution:

	def fibSum(self, N):
		fib0 = 0
		fib1 = 1
		fib2 = 1
		mod = 1000000007
		Sum = fib0 + fib1 + fib2
		if N == 0:
			return 0
		elif N == 1:
			return 1
		elif N == 2:
			return Sum
		else:
			for i in range(2, N):
				fib3 = fib1 + fib2
				Sum += fib3
				fib1 = fib2 % mod
				fib2 = fib3 % mod
			return int(Sum % mod)


class Solution:

	def fibSum(self, N):
		if N == 1:
			return 1
		first = 0
		second = 1
		s = first + second
		for i in range(2, N + 1):
			curr = (first + second) % 1000000007
			s = s % 1000000007 + curr
			first = second
			second = curr
		return s % 1000000007


class Solution:

	def fibSum(self, N):
		a = [1] * N
		a[1] = 1
		b = 2
		for i in range(2, N):
			a[i] = (a[i - 1] % 1000000007 + a[i - 2] % 1000000007) % 1000000007
			b = a[i] + b
		return b % 1000000007


class Solution:

	def fibSum(self, N):
		ans = [None] * (N + 1)
		if N == 0 or N == 1:
			return N
		ans[0] = 0
		ans[1] = 1
		sum = 1
		for i in range(2, N + 1):
			ans[i] = (ans[i - 1] + ans[i - 2]) % 1000000007
			sum = sum % 1000000007 + ans[i]
		return sum % 1000000007


class Solution:

	def fibSum(self, N):
		fib = [0] * (N + 1)
		fib[0] = 0
		fib[1] = 1
		j = 1000000007
		for i in range(2, N + 1):
			fib[i] = fib[i - 1] % j + fib[i - 2] % j
		return sum(fib) % j


class Solution:

	def fibSum(self, N):
		MOD = 1000000007
		if N == 1:
			return 1
		if N == 2:
			return 2
		a = [0] * N
		a[0] = a[1] = 1
		ans = 2
		for i in range(2, N):
			a[i] = a[i - 1] % MOD + a[i - 2] % MOD
			ans += a[i] % MOD
		return ans % MOD


class Solution:

	def fibSum(self, N):
		(sum, curr, next, count) = (0, 0, 1, 0)
		while count < N:
			(sum, curr, next, count) = ((sum + next) % 1000000007, next, (curr + next) % 1000000007, count + 1)
		return sum


MAX = 1000000007

class Solution:

	def fibSum(self, n):
		if n < 2:
			return n
		a = 0
		b = 1
		sum = 1
		for i in range(2, n + 1):
			c = (a + b) % MAX
			a = b % MAX
			b = c % MAX
			sum += c % MAX
		return sum % MAX


class Solution:

	def fibSum(self, n):
		a = 1
		b = 1
		if n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			for i in range(3, n + 3):
				res = a + b
				a = b
				b = res
		return (res - 1) % (10 ** 9 + 7)


class Solution:

	def fibSum(self, N):
		if N == 1:
			return 1
		else:
			a = 0
			b = 1
			Sum = 1
			for _ in range(2, N + 1):
				c = (a + b) % 1000000007
				Sum = (Sum + c) % 1000000007
				a = b
				b = c
		return Sum


from functools import lru_cache

class Solution:

	def fibSum(self, N):

		@lru_cache(None)
		def fib(n):
			n = int(n)
			if n == 0:
				return 0
			if n == 1 or n == 2:
				return 1
			if n % 2 == 0:
				mid = n / 2
				fn = (2 * fib(mid - 1) + fib(mid)) * fib(mid)
			else:
				mid = (n + 1) / 2
				fn = fib(mid) * fib(mid) + fib(mid - 1) * fib(mid - 1)
			return fn
		return (fib(N + 2) - 1) % 1000000007


class Solution:

	def fibSum(self, N):
		f0 = 0
		f1 = 1
		ans = f0 + f1
		for i in range(2, N + 1):
			t = f0 + f1
			f0 = f1
			f1 = t
			ans += t
		return ans % 1000000007


class Solution:

	def fibSum(self, N):

		def mul(t, s):
			mod = 1000000007
			res = [[0, 0], [0, 0]]
			res[0][0] = (t[0][0] * s[0][0] + t[0][1] * s[1][0]) % mod
			res[0][1] = (t[0][0] * s[0][1] + t[0][1] * s[1][1]) % mod
			res[1][0] = (t[1][0] * s[0][0] + t[1][1] * s[1][0]) % mod
			res[1][1] = (t[1][0] * s[0][1] + t[1][1] * s[1][1]) % mod
			return res
		n = N
		x = n
		t = [[1, 1], [1, 0]]
		mat = t
		p = 0
		mod = 1000000007
		while x > 1:
			mat = mul(mat, mat)
			mat = mat
			x = x >> 1
			p += 1
		while n - 2 ** p != 0:
			mat = mul(mat, t)
			mat = mat
			n -= 1
		return (mat[0][0] + mat[0][1] - 1) % mod


class Solution:

	def fibSum(self, n):
		a = 0
		b = 1
		temp = 0
		count = 1
		for i in range(2, n + 1):
			temp = (a + b) % 1000000007
			a = b
			b = temp
			count = (count + temp) % 1000000007
		return count


class Solution:

	def fibSum(self, N):
		start = 0
		end = 1
		sum1 = 0
		i = 2
		while i <= N + 2:
			sum1 = (start + end) % 1000000007
			start = end
			end = sum1
			i += 1
		return sum1 - 1