## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Alternating Strings CodeChef Solution | CodeChef Problem Solution 2022

Chef likes to spend his summer vacation playing with strings. Chef likes alternating patterns, but he only likes the characters $\mathtt{\text{a}}$ and $\mathtt{\text{b}}$, so he does the following:

Chef starts with an empty string $S$. Then,

• First, he appends $\mathtt{\text{a}}$ once to $S$
• Next, he appends $\mathtt{\text{b}}$ twice to $S$
• Next, he appends $\mathtt{\text{a}}$ thrice to $S$
• Next, he appends $\mathtt{\text{b}}$ four times to $S$

and so on. For example, the first $13$ characters of $S$ are $\mathtt{\text{abbaaabbbbaaa}}$.

Now, Chef takes the string formed by the first $N$ characters of $S$, and wants to calculate its beauty. The beauty of a string is calculated as follows:

• First, we define the value of a string $A$ to be the number of positions $1\le i<|A|$ such that ${A}_{i}\ne {A}_{i+1}$. For example, the value of $\mathtt{\text{aaa}}$ is $0$ and the value of $\mathtt{\text{abba}}$ is $2$.
• Then, the beauty of a string is defined to be the sum of values of all its substrings. Two substrings are considered distinct if they occur at different positions, so every string of length $K$ has exactly $K\cdot \left(K+1\right)/2$ substrings.

You are given $N$. Help Chef by calculating the beauty of the string formed by the first $N$ characters of $S$. The answer may be large, so report it modulo $1000000007$.

### Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases. The description of $T$ test cases follows.

• The first and only line of each test case contains a single integer $N$.

### Output Format

For each test case, output in a single line the beauty of the string modulo ${10}^{9}+7$.

### Constraints

• $1\le T\le {10}^{5}$