eolymp
bolt
Try our new interface for solving problems
Problems

The Function

The Function

Time limit 20 seconds
Memory limit 64 MiB

Given an positive integer N, compute the following function f(N):

Here x/i denotes integer division.

Since the F(N) can be quite large; please output F(N) % 1000000007.

Input data

First line contains T, the number of test cases. Next T lines contain the value of N for each test case.

It is known that 1T50, 1N10^9.

Output data

Output T lines, i-th line containing the answer for i-th test case.

Examples

Input example #1
50
16808
282475250
622650074
984943659
144108931
470211273
101027545
457850879
458777924
7237710
823564441
115438166
784484493
74243043
114807988
137522504
441282328
16531730
823378841
143542613
896544304
474833170
264817710
998097158
817129561
131570934
197493100
404280279
893351817
505795336
954899098
636807827
563613513
101929268
580723811
704877634
358580980
624379150
128236580
784558822
530511968
110010673
551901394
617819337
399125486
156091746
356425229
899894092
585640195
937186358
Output example #1
798891814
965597375
781629348
231400999
681820990
326512869
570253390
553618273
729705082
172153172
840905619
926147771
473302851
222933489
780491825
292562451
160305720
354723852
873364684
711644071
900530547
427807301
376833173
86908677
258244673
663554101
778321897
623547825
471574703
743517145
408116618
272491640
207875466
268455915
739468574
509513128
508783180
566031677
168576807
488778900
265663314
77697112
413399613
670920154
128767216
688934127
376560969
975499331
669113588
391639208
Author Ajay Somani
Source Sevastopol - 2010