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

[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 a$\mathtt{\text{a}}$ and b$\mathtt{\text{b}}$, so he does the following:

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

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

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

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

Solution Click Below:-  CLICK HERE

• First, we define the value of a string A$A$ to be the number of positions 1≤i<|A|$1\le i<|A|$ such that Ai≠Ai+1$A_i\ne A_{i+1}$. For example, the value of aaa$\mathtt{\text{aaa}}$ is 0$0$ and the value of abba$\mathtt{\text{abba}}$ is 2$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$K$ has exactly K⋅(K+1)/2$K\cdot (K+1)/2$ substrings.

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

Input Format

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

Biryani classes CodeChef Solution

Alternating Strings CodeChef Solution

The Attack of Knight CodeChef Solution

Air Hockey CodeChef Solution 

Jogging CodeChef Solution

Triple Xor CodeChef Solution

Dense Bracket Sequence CodeChef Solution

Atleast and Atmost CodeChef Solution

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

Output Format

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

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤109