Now, Watson asks Sherlock: What will be the sum of length of solid lines after $N$ seconds?

As the number can be large print result mod$({10}^9+7).$

For example, after o seconds, the length is $4.$

After $1$ second, the length is $6.$

Input Format

First line contains $T,$ the number of testcases. Each testcase contains $N$ in one line.

Output Format

For each testcase, print the required answer in a new line.

Constraints

$1T{10}^5$

$0N{10}^9$

Sample input

Sample output

import mathimport randomimport sys# Complete the 'solve' function below.# The function is expected to return an INTEGER.# # Write your code here fptr $=$ open$($os$.$environ$[\text{'}$OUTPUT$\_$PATH'$],\text{'}$w$\text{'})$ for t$\_$itr in range$($t$)$: result $=$ solve$($n$)$ fptr$.$close$()$

Solve in Python Programming Language and explain the logic behind the problem and also explain each line of code $.$