## Problem: Fibonacci Sum

*Difficulty: Easy

Given a number positive number n, find value of f0 + f1 + f2 + …. + fn where fi indicates i’th Fibonacci number. Remember that f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, …

```Input  : n = 3
Output : 4
Explanation : 0 + 1 + 1 + 2  = 4

Input  :  n = 4
Output :  7
Explanation : 0 + 1 + 1 + 2 + 3  = 7
```

Since the answer can be very large, answer modulo 1000000007 should be printed.

Input:
First line contains an integer, the number of test cases ‘T’ Each test case should contain a positive integer N.
Output:
Print sum of fibonacci numbers.
Constraints:
1 <=T<= 20000
1 <= N <=100000
Example:
Input:
2
6
5

Output:
20
12

Implementation: Python2.7
Sum of first nth fibo

```#code
def sum_first_100k_fibo():
# this will be faster than
# calculate and return first-100k-fibo-number list
f1, f2 = 1, 2
fibo = [f1, f2]
yield f1
yield f2
while len(fibo) < 100000:
f1, f2 = f2, f1+f2+1
fibo.append(f2)
yield f2

if __name__ == '__main__':
fibo = sum_first_100k_fibo()
fibo_dict = []
for i in range(100000):
fibo_dict.append(fibo.next())
t = input()
for _ in range(t):
n = input()
print fibo_dict[n-1] % 1000000007

```