P14867 [HackerEarth] Given f(n)= [((1^2)x(nC1)^2) + ((2^2)x(nC2)^2) + ((3^2)x(nC3)^2) + ...... + ((n^2)x(nCn)^2)]%MOD.
普及
题目描述

Given f(n)= [((1^2)x(nC1)^2) + ((2^2)x(nC2)^2) + ((3^2)x(nC3)^2) + ...... + ((n^2)x(nCn)^2)]%MOD.

Let there are k primes between 1 and n(inclusive) namely p1,p2,p3..pk.Your task is to find sum where:
sum=(f(p1) + f(p2) + f(p3) +...+f(pk))%MOD

Input:

t:testcases

for each test case n is given

Output:

Print the value of sum.

Constraints:

1 ≤ t ≤ 100

1 ≤ n ≤ 10^6

MOD: 10^9 + 7

SAMPLE INPUT
2
1
5

SAMPLE OUTPUT
0
1812

输入格式

见题面

输出格式

见题面

样例输入
100 1000000 1 2 3 4 5 6 7 8 9 10 1641 738681 253361 766761 628961 459121 978561 228201 931241 673081 398441 19641 119801 477681 193081 217441 584161 156081 6121 11681 495281 696841 748641 788721 795801 217881 869041 590841 461521 74761 796481 681401 395761 952441 706921 186561 605641 308441 274721 801481 514361 348921 389641 31121 492641 121401 887601 73681 11521 361601 357681 770561 905921 952201 635601 269161 974801 614001 600241 975721 141921 785161 504921 963361 798161 750241 473601 198641 295041 557241 677761 985041 452921 221481 861521 644721 83281 917161 661641 193321 185561 908161 397201 559081 92241 895441 200841 762881 250801
样例输出
425164818 0 8 62 62 1812 1812 47088 47088 47088 47088 433360643 661769794 167395075 456192006 251609778 209769242 754302604 68907408 215843680 386578099 317353867 839180578 818921459 3555331 781082738 318594401 349979502 92507662 418127580 368953430 493011108 143826441 882600923 913850485 92854201 177458259 441677125 365057055 325603619 234853798 517467683 810642730 440694151 889461612 13869765 675501015 808456084 999590265 425161013 786409520 32267754 342181540 583447471 873719553 512812114 211271255 883742227 100832753 867991666 53569159 327261181 309435699 926210665 932516364 3198488 867139696 130688741 877673035 628112039 727672271 391411843 369143243 409272084 39501104 622210474 163175102 366953136 541063576 131728562 14338595 517718532 478819235 975612078 782551115 834387537 54857270 650679927 752354138 537540401 225633584 450682940 997699533 450549752 296920145 119334502 6615824 785897093 213113101 720247423