You are given test cases. Each test case contains an integer . Find the value of the following function:
such that
Formally, you are required to find the summation from to for .
Input format
Output format
Print the answer as described above modulo .
Constraints
In the first test case we have n=1 so we have to find the summation of f[0]+f[1] = 0+1 = 1,
also the second test case the answer will be 0+1+1+2+3+5+8+13 = 33.