Pell numbers are numbers that are similar to the Fibonacci numbers and are generated by below formula
P_{n} = 2*P_{n-1} + P_{n-2}
with seeds P_{0} = 0 and P_{1} = 1
Your task is to print Nth pell number.

Example 1:
Input:
N = 3
Output:
5
Explanation:
P_{0} = 0, P_{1} = 1, P_{2} = 21+0 = 2,
P_{3} = 22+1 = 5
Example 2:
Input:
N = 4
Output:
12
Explanation:
P_{0} = 0, P_{1} = 1, P_{2} = 21+0 = 2,
P_{3} = 22+1 = 5, P_{4} = 2*5+2 = 12

Your Task:
You don't need to read input or print anything. Your task is to complete the function getNthPell() which takes an Integer N as input and returns the answer modulo (10^{9}+7).

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 10^{5}

见题面

见题面