Nikita has a row of $N$ white tiles indexed from $\mbox{1}$ to $N$. This time, she's painting them green! 

Find the number of ways Nikita can paint certain tiles in green so that the indices of the green tiles form an Arithmetic Progression. As this value can be quite large, your answer must be modulo $(10^9+7)$.

Note: Nikita must paint at least $\mbox{1}$ tile.

Input Format

The first line contains a single integer, $\mathbf{T}$, denoting the number of test cases. 

Each test case consists of a single line containing an integer, $N$, denoting the length of row of tiles.

Constraints

$1\leq T\leq10$
$1\leq N\leq10^{10}$

Scoring

$1\leq N\leq2000$ for $20\%$ of test data.
$1\leq N\leq10^5$ for $50\%$ of test data.
$1\leq N\leq10^{10}$ for $\textbf{100\%}$ of test data.

Output Format

On a new line for each test case, print the number of ways Nikita can paint her white tiles green so that the indices of the green tiles form an Arithmetic Progression. Because this number can be quite large, your answer must be modulo $(10^9+7)$.

Sample Input
3
3
4
5

Sample Output
7
13
22

Explanation

Test Case 0:

There are $7$ valid ways to paint the tiles:

Thus, we print the result of $7\%(10^9+7)$ on a new line, which is $7$.

Test Case 1:

There are $13$ valid ways to paint the tiles:

Thus, we print the result of $13\%(10^9+7)$ on a new line, which is $13$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Combinatorics


Solutions:
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
from math import sqrt
import itertools as it
from itertools import accumulate as acc, permutations as per
from copy import deepcopy
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PaintingTilesRev06.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def faireNz(N, nz):
	raimax = (N - 1) // nz
	cb = nz - (N - 1) % nz - 1
	res = -cb * raimax + nz * (raimax * (raimax + 1) // 2)
	return res

def arithm(db, nel, rai):
	return (rai * nel * (nel - 1) // 2 + db * nel) % modo

def faire(N):
	(rh, deb) = (N, N - 1)
	tz = 1
	while True:
		nx = N // (tz + 1)
		(nel, rai) = (deb - nx, (tz + 1) * tz // 2)
		if nel < 4:
			break
		db = faireNz(N, deb)
		rh += arithm(db, nel, rai)
		(deb, tz) = (nx, tz + 1)
	for nz in range(1, deb + 1):
		rh = (rh + faireNz(N, nz)) % modo
	return rh
if home:
	cr = ch()
trace = 0
rd = open(filou) if filou else stdin
if home:
	prv = 0
LN = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
maxNb = max(LN)
for N in LN:
	if home:
		print(N)
	for f in (faire,):
		if home:
			cr = ch()
		r = f(N)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
			prv = r
		else:
			print(r)


import math
mod = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	toret = n
	for i in range(1, int(math.sqrt(n)) + 1):
		toret += n - i * i
		toret += 2 * n * (n // i - i)
		toret -= i * (i + 1 + n // i) * (n // i - i)
	print(toret % mod)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
from math import sqrt
import itertools as it
from itertools import accumulate as acc, permutations as per
from copy import deepcopy
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PaintingTilesRev06.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def faireNz(N, nz):
	raimax = (N - 1) // nz
	cb = nz - (N - 1) % nz - 1
	res = -cb * raimax + nz * (raimax * (raimax + 1) // 2)
	return res

def arithm(db, nel, rai):
	return (rai * nel * (nel - 1) // 2 + db * nel) % modo

def faire(N):
	(rh, deb) = (N, N - 1)
	tz = 1
	while True:
		nx = N // (tz + 1)
		(nel, rai) = (deb - nx, (tz + 1) * tz // 2)
		if nel < 4:
			break
		db = faireNz(N, deb)
		rh += arithm(db, nel, rai)
		(deb, tz) = (nx, tz + 1)
	for nz in range(1, deb + 1):
		rh = (rh + faireNz(N, nz)) % modo
	return rh
if home:
	cr = ch()
trace = 0
rd = open(filou) if filou else stdin
if home:
	prv = 0
LN = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
maxNb = max(LN)
for N in LN:
	if home:
		print(N)
	for f in (faire,):
		if home:
			cr = ch()
		r = f(N)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
			prv = r
		else:
			print(r)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
from math import sqrt
import itertools as it
from itertools import accumulate as acc, permutations as per
from copy import deepcopy
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PaintingTilesRev06.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def faireNz(N, nz):
	raimax = (N - 1) // nz
	cb = nz - (N - 1) % nz - 1
	res = -cb * raimax + nz * (raimax * (raimax + 1) // 2)
	return res

def arithm(db, nel, rai):
	return (rai * nel * (nel - 1) // 2 + db * nel) % modo

def faire(N):
	(rh, deb) = (N, N - 1)
	tz = 1
	while True:
		nx = N // (tz + 1)
		(nel, rai) = (deb - nx, (tz + 1) * tz // 2)
		if nel < 4:
			break
		db = faireNz(N, deb)
		rh += arithm(db, nel, rai)
		(deb, tz) = (nx, tz + 1)
	for nz in range(1, deb + 1):
		rh = (rh + faireNz(N, nz)) % modo
	return rh
if home:
	cr = ch()
trace = 0
rd = open(filou) if filou else stdin
if home:
	prv = 0
LN = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
maxNb = max(LN)
for N in LN:
	if home:
		print(N)
	for f in (faire,):
		if home:
			cr = ch()
		r = f(N)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
			prv = r
		else:
			print(r)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
from math import sqrt
import itertools as it
from itertools import accumulate as acc, permutations as per
from copy import deepcopy
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PaintingTilesRev06.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def faireNz(N, nz):
	raimax = (N - 1) // nz
	cb = nz - (N - 1) % nz - 1
	res = -cb * raimax + nz * (raimax * (raimax + 1) // 2)
	return res

def arithm(db, nel, rai):
	return (rai * nel * (nel - 1) // 2 + db * nel) % modo

def faire(N):
	(rh, deb) = (N, N - 1)
	tz = 1
	while True:
		nx = N // (tz + 1)
		(nel, rai) = (deb - nx, (tz + 1) * tz // 2)
		if nel < 4:
			break
		db = faireNz(N, deb)
		rh += arithm(db, nel, rai)
		(deb, tz) = (nx, tz + 1)
	for nz in range(1, deb + 1):
		rh = (rh + faireNz(N, nz)) % modo
	return rh
if home:
	cr = ch()
trace = 0
rd = open(filou) if filou else stdin
if home:
	prv = 0
LN = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
maxNb = max(LN)
for N in LN:
	if home:
		print(N)
	for f in (faire,):
		if home:
			cr = ch()
		r = f(N)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
			prv = r
		else:
			print(r)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
from collections import Counter
from functools import reduce as red
from math import sqrt
import itertools as it
from itertools import accumulate as acc, permutations as per
from copy import deepcopy
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)

def inv(n):
	return pow(n, modo - 2, modo)
if home:
	filou = lolPath + '\\PaintingTilesRev06.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def faireNz(N, nz):
	raimax = (N - 1) // nz
	cb = nz - (N - 1) % nz - 1
	res = -cb * raimax + nz * (raimax * (raimax + 1) // 2)
	return res

def arithm(db, nel, rai):
	return (rai * nel * (nel - 1) // 2 + db * nel) % modo

def faire(N):
	(rh, deb) = (N, N - 1)
	tz = 1
	while True:
		nx = N // (tz + 1)
		(nel, rai) = (deb - nx, (tz + 1) * tz // 2)
		if nel < 4:
			break
		db = faireNz(N, deb)
		rh += arithm(db, nel, rai)
		(deb, tz) = (nx, tz + 1)
	for nz in range(1, deb + 1):
		rh = (rh + faireNz(N, nz)) % modo
	return rh
if home:
	cr = ch()
trace = 0
rd = open(filou) if filou else stdin
if home:
	prv = 0
LN = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
maxNb = max(LN)
for N in LN:
	if home:
		print(N)
	for f in (faire,):
		if home:
			cr = ch()
		r = f(N)
		if home:
			t = cr.lap()
			print(f.__name__, r, t)
			prv = r
		else:
			print(r)


P = 10 ** 9 + 7
N = 100000
for t in range(int(input())):
	n = int(input())
	ans = 0
	nn = min(n, N)
	K = 0
	for d in range(1, nn + 1):
		K = n // d
		ans += K * (K - 1) // 2 * d
		ans += n % d * K
	ans %= P
	if nn < n:
		dd = nn + 1
		dn = 0
		dnr = 0
		rr = 0
		for i in range(1, N + 1):
			dn = n // (i + 1)
			if dn * (i + 1) < n:
				dn += 1
			if dn > n:
				dn = n + 1
			if dn - 1 >= dd:
				ans += (dn - 1 + dd) * (dn - dd) // 2 * i
			if dn < dd:
				dn = dd
			if dn <= n:
				dnr = n - i * dn
				if dnr > 0:
					rr = (dnr + i - 1) // i
					ans += (dnr + dnr - (rr - 1) * i) * rr // 2 * i
	print((ans + n) % P)