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

Chef starts with an empty string S. Then, 
First, he appends \texttt{a} once to S
Next, he appends \texttt{b} twice to S
Next, he appends \texttt{a} thrice to S
Next, he appends \texttt{b} four times to S

and so on. For example, the first 13 characters of S are \texttt{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 ≤ i < |A| such that A_{i} \neq A_{i+1}. For example, the value of \texttt{aaa} is 0 and the value of \texttt{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(K+1)/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 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3
4
7
----- Sample Output 1 ------ 
2
6
24
----- explanation 1 ------ 
Test case $1$: The first three characters of $S$ are $\texttt{abb}$. The values of the substrings are as follows:
- $\texttt{a}, \texttt{b}, \texttt{b}, \texttt{bb}$ have a value of $0$.
- $\texttt{ab}, \texttt{abb}$ have a value of $1$.

So, the beauty of the string is $2$.

Test case $2$: The first $4$ characters of $S$ are $\texttt{abba}$. Its substrings of non-zero value are:
- $\texttt{ab}, \texttt{abb}, \texttt{ba}, \texttt{bba}$ with value $1$
- $\texttt{abba}$ with value $2$.

So, the beauty of the string is $1 + 1 + 1 + 1 + 2 = 6$.

Difficulty: VERY_HARD
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input()) - 1
	mx = int((2 * n) ** 0.5)
	if mx * (mx + 1) > 2 * n:
		mx -= 1
	(mx_pow, val) = ([], mx)
	for i in range(5):
		mx_pow += [val]
		val *= mx
	pow_4 = mx * (mx + 1) * (2 * mx + 1) * (3 * mx_pow[1] + 3 * mx - 1) // 30
	pow_3 = (mx * (mx + 1) // 2) ** 2
	pow_2 = mx * (mx + 1) * (2 * mx + 1) // 6
	pow_1 = mx * (mx + 1) // 2
	ans = (-pow_4 - 2 * pow_3 + (2 * n + 1) * pow_2 + 2 * (n + 1) * pow_1) // 4
	ans = int(ans)
	print(ans % MOD)


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'
formula = lambda x: (x ** 3 + 3 * x ** 2 + 2 * x) // 6
sqaure = lambda x: x * (x + 1) // 2
pref = ddc(int)
pref[0] = pref[1] = 0
for i in range(2, 100001):
	pref[i] = pref[i - 1] + i * formula(i - 1)

def process(arr, n):
	(l, h) = (1, 100000)
	while l < h:
		nex = (l + h + 1) // 2
		if sqaure(nex) > n:
			h = nex - 1
		else:
			l = nex
	nex = l
	ans = 0
	ans += (n - sqaure(nex)) * formula(nex) + pref[nex]
	return ans % mod

def main():
	for _ in range(int(input())):
		n = intin()
		arr = []
		print(process(arr, n))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	lb = 0
	rb = 1000000000
	while lb < rb:
		mb = (lb + rb + 1) // 2
		if mb * (mb + 1) // 2 <= n:
			lb = mb
		else:
			rb = mb - 1
	x = lb
	curr = (x - 1) * x * (x + 1) * (x + 2) * (2 * x + 1) // 60
	pr = x * (x + 1) // 2
	rem = n - pr
	x += 2
	add = x * (x - 1) * (x - 2) // 6
	curr += rem * add
	curr %= 1000000007
	print(curr)


import math

def lower_tri_num_pos(n):
	return int(0.5 * (-1 + math.sqrt(1 + 8 * n)))
t = int(input())
vals = {}
n = 1000000000
switches = lower_tri_num_pos(n)
remaining = int(n - switches * (switches + 1) / 2)
tot = 0
num = 2
cursum = 0
for i in range(1, switches):
	cursum += int(i * (i + 1) / 2)
	tot += num * cursum
	num += 1
	vals[i] = (tot, cursum)
for _ in range(t):
	n = int(input())
	switches = lower_tri_num_pos(n)
	remaining = int(n - switches * (switches + 1) / 2)
	(tot, cursum) = vals[switches - 1]
	cursum += int(switches * (switches + 1) / 2)
	tot += remaining * cursum
	print(tot % 1000000007)


import math
mod = 1000000007
tc = int(input())
ls = []
ls2 = []
n = mod + 100000
ans = 0
nw = 2
temp = 0
add2 = 1
n -= 1
ls.append(0)
ls2.append(0)
while temp + nw <= n:
	temp += nw
	ans += nw * (add2 * (add2 + 1) * (add2 + 2)) // 6
	add2 += 1
	nw += 1
	ls.append(ans)
	ls2.append(temp)
while tc > 0:
	n = int(input())
	n -= 1
	ind = int((math.sqrt(8 * n + 1) - 1) // 2)
	ind = min(ind + 100, len(ls) - 1)
	while ind > -1 and ls2[ind] > n:
		ind -= 1
	ans = ls[ind]
	temp = ls2[ind]
	add2 = ind + 1
	ans += (n - ls2[ind]) * (add2 * (add2 + 1) * (add2 + 2) // 6)
	if n == 0:
		print(0)
	else:
		print(int(ans) % mod)
	tc -= 1


import sys
import os
import math
import collections

def binary_search(data, elem):
	low = 0
	high = len(data) - 1
	while low <= high:
		middle = (low + high) // 2
		if data[middle] == elem:
			return middle
		elif data[middle] > elem:
			high = middle - 1
		else:
			low = middle + 1
	return low
T = int(input())
mod = int(1000000000.0 + 7)
C = []
for i in range(1, 100000):
	d = i * (i - 1) // 2
	if d > 1000000000.0:
		break
	C.append(d)
A = [0] * len(C)
B = [0] * len(C)
for i in range(1, len(C)):
	A[i] = A[i - 1] + C[i]
	B[i] = B[i - 1] + C[i] * C[i]
	A[i] %= mod
	B[i] %= mod
for _ in range(T):
	N = int(input())
	i = binary_search(C, N) - 1
	print((N * A[i] - B[i]) % mod)


tt = int(input())
for t in range(tt):
	N = int(input())
	n = 0
	nr = N + 1
	while n + 1 < nr:
		m = (n + nr) // 2
		if m * (m + 1) < 2 * N:
			n = m
		else:
			nr = m
	s1 = n * (n + 1) // 2
	s2 = s1 * (2 * n + 1) // 3
	s3 = s1 * s1
	s4 = s2 * (3 * n * n + 3 * n - 1) // 5
	res = N * (s2 + s1) // 2 - (s4 + 2 * s3 + s2) // 4
	print(res % 1000000007)


def s1(n):
	res = 1
	res *= n
	res *= n + 1
	res //= 2
	return res

def s2(n):
	res = 1
	res *= n
	res *= n + 1
	res *= 2 * n + 1
	res //= 6
	return res

def s3(n):
	res = 1
	res *= s1(n)
	res *= s1(n)
	return res

def s4(n):
	res = 1
	res *= n
	res *= n + 1
	res *= 2 * n + 1
	res *= 3 * n * n + 3 * n - 1
	res //= 30
	return res
tt = int(input())
for t in range(tt):
	N = int(input())
	n = 0
	nr = N + 1
	while n + 1 < nr:
		m = (n + nr) // 2
		if m * (m + 1) < 2 * N:
			n = m
		else:
			nr = m
	res = N * (s2(n) + s1(n)) // 2 - (s4(n) + 2 * s3(n) + s2(n)) // 4
	print(res % 1000000007)


from bisect import bisect_right
from collections import Counter
a = [n * (n + 1) // 2 for n in range(1, 10 ** 5)]
prev = [a[0]]
for i in a[1:]:
	prev.append(prev[-1] + i)
sums = [1]
i = 1
curr = 2
while i < 10 ** 9 + 1:
	i += curr
	sums.append(sums[-1] + i * i)
	curr += 1

def solve():
	n = int(input())
	index = bisect_right(a, n)
	index -= 1
	rem = n - a[index]
	res = 0
	mod = 10 ** 9 + 7
	res -= sums[index]
	res += prev[index] * n
	print(res % mod)
try:
	for tc in range(int(input())):
		solve()
except:
	pass