Rohan has a special love for the matrices especially for the first element of the matrix. Being good at Mathematics, he also loves to solve the different problem on the matrices. So one day he started to multiply the matrix with the original matrix. The elements of the original matrix are given by a_{00}=1 , a_{01}=1, a_{10}=1, a_{11}=0.
Given the power of the matrix, n calculate the a^{n} and return the a_{10} element mod 1000000007.
Example 1:
Input: n = 3
Output: 2
Explanation: Take the cube of the original matrix
i.e a^{3} and the first element(a_{10}) is 2.
Example 2:
Input: n = 4
Output: 3
Explanation: Take the cube of the original matrix
i.e a^{4} and the first element(a_{10}) is 3.
Your Task:
You dont need to read input or print anything. Complete the function firstElement() which takes n as input parameter and returns the a_{10} element mod 1000000007.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=10^{6}

见题面

见题面