Given a sequence as follow:
1,1,7,19,73....
Find the N^{th} term of the given sequence.

Example 1:
Input: N = 1
Output: 1
Example 2:
Input: N = 4
Output: 19

Your Task:
Your task is to complete the function NthTerm() which takes N as input paramater and returns N^{th} term of the given sequence modulo 10^{9}+7.

Expected Time Complexity: O(log(N))
Expected Space Compelxity: O(K) where K is constant.

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

见题面

见题面