//#include #include #include #include #include #include using namespace std; #define N 2010 #define MP make_pair #define mod 1000000007 int a[N] = {0, 26, 676, 17576, 456950, 11880050, 308864400, 30034944, 769484794, 709603261, 728074716, 179068890, 418671395, 145374794, 577876849, 548075754, 783184708, 728432446, 492322343, 98487075, 981046376, 296394577, 398200462, 891035088, 640752902, 249710964, 537473542, 698434955, 140486266, 409868837, 219751233, 252658267, 56958271, 234194184, 595267959, 160510196, 749308307, 627161291, 424494584, 24104235, 894002568, 565034444, 78530916, 439197934, 69082161, 670275177, 463881597, 80973165, 378248265, 77575514, 419923509, 893682053, 779526662, 328305236, 37848425, 642007879, 204038325, 97365571, 585294214, 167452596, 252809378, 138904525, 979162384, 271906937, 749345912, 10380475, 790832925, 763982534, 129898077, 117838106, 292967750, 517598234, 210102089, 516701650, 110049108, 921321035, 701794559, 329117249, 805820739, 918313360, 331283343, 385435693, 875809620, 813216127, 861535643, 764034309, 969651555, 880537227, 355576820, 144139665, 506342562, 151476000, 48955535, 669352306, 744595878, 572592723, 663522332, 517772982, 847200624, 712398100, 934292293, 347274991, 849134257, 267538154, 598684798, 883929931, 753821774, 910912190, 716596934, 533272037, 19528647, 734940233, 193522701, 699789364, 706307170, 990480602, 914427987, 280393520, 632552347, 684346035, 932297277, 229891083, 163359553, 138697594, 298705659, 19070045, 411832373, 240201799, 777605313, 740986880, 969849499, 211041866, 46955789, 696178640, 854407214, 938540802, 228165966, 527849200, 363898906, 997851611, 239992596, 43577545, 35543576, 977842876, 424099743, 937154630, 477430819, 967129485, 542872937, 685830682, 895827222, 113270654, 373213656, 557788062, 106809118, 945270725, 246697345, 469429476, 534938363, 276629383, 24930326, 912451660, 350284015, 191649801, 359636648, 539261446, 263697186, 64881797, 696010578, 614738850, 390780387, 538245081, 594107684, 78328534, 267032265, 486711914, 801817685, 889046334, 439397947, 256548779, 624826227, 19323594, 517464846, 40366472, 428872702, 667600332, 420987454, 936511941, 627492825, 624805157, 720247697, 313641632, 467361863, 531279541, 807075676, 142926685, 32047291, 551241132, 155377574, 466649799, 331712422, 843494714, 46423088, 540755390, 766829555, 850200594, 944638104, 41705877, 913614060, 498950696, 356765573, 233257917, 224354461, 359448635, 426525185, 258206850, 104516568, 731214942, 348458811, 604757822, 110789081, 600142668, 892239051, 79269720, 291285702, 569861608, 510425589, 289322237, 240235612, 999585775, 228590334, 710292773, 461721714, 15120280, 678368972, 880273954, 344079877, 568069746, 810589117, 68468199, 178176298, 430840168, 937116513, 653324209, 532021900, 61565179, 172781983, 159226417, 839339412, 283695097, 56522926, 488935672, 728842235, 857520608, 882462518, 720633598, 515417673, 962844361, 972390422, 266310973, 38643515, 933622533, 964425315, 417283739, 883289276, 624957858, 138271489, 162965288, 154865714, 402562198, 9829874, 181444552, 845915502, 929748025, 927701639, 584128681, 39458198, 782212684, 144988830, 166492632, 342353461, 345872963, 367976253, 405066743, 972898786, 648544249, 662744100, 104677976, 399157880, 164498697, 708363713, 800507033, 834235788, 577662944, 310143740, 51061499, 471704414, 822741185, 637677219, 303070114, 87212642, 698999200, 232048711, 456513650, 689038787, 440028462, 639522202, 214735967, 357165551, 285592790, 437357553, 2897161, 146187474, 661054602, 253480785, 518071343, 815168005, 668003052, 31059650, 855767416, 870752684, 939493449, 650338263, 514609473, 611029261, 399424617, 126583509, 425934479, 798564964, 777073569, 39324950, 374086795, 762132647, 388609597, 120725709, 786698608, 400847626, 706798351, 358614296, 656506573, 47980199, 577526518, 50332026, 895968463, 95674909, 49384768, 25703318, 269074847, 604073269, 471285696, 610845069, 155100556, 930782815, 418210706, 602351666, 783629339, 104792460, 269336366, 943953929, 952068651, 133973272, 749895950, 898446510, 557892992, 155885915, 305635145, 485351125, 671804464, 569768098, 173091874, 366610655, 736765486, 911700158, 376907125, 634318875, 73153614, 109490161, 424066110, 167747020, 532582156, 109881954, 255278110, 443555346, 217885110, 917963996, 485111027, 524003045, 176951364, 651635697, 814752419, 83486713, 746870459, 127739488, 952416339, 675656835, 895316249, 84735134, 392705163, 318913412, 908842592, 511528895, 482122174, 562341196, 899806359, 606742889, 722260743, 720249390, 231325193, 845882863, 936435842, 341097100, 85394754, 73192162, 492100316, 267180688, 811829010, 277750077, 918994144, 214330425, 276865905, 254761605, 648948249, 514393772, 452590405, 398310370, 132363437, 581605132, 806973286, 23546109, 303112930, 340807929, 686674088, 264873444, 308886301, 510845608, 115133636, 371638464, 940442532, 680365555, 811163432, 799287555, 270413151, 21603121, 282595486, 365293852, 737311363, 630017287, 315562249, 72272181, 446292750, 853179360, 293607037, 826978402, 344119632, 617626523, 718113617, 996494013, 305853419, 511525875, 346832360, 105291147, 91234382, 583947134, 511816442, 674948747, 267807767, 364323648, 677003826, 728380801, 242706567, 202279563, 334173072, 478979917, 385813625, 974165147, 973966910, 348641644, 419342126, 548766699, 918761501, 171757821, 982150245, 816738818, 266171757, 626520143, 735767656, 711488620, 844410118, 291659451, 188954403, 125599069, 155322970, 746910973, 695825125, 951476427, 855312712, 565356166, 303632212, 107526949, 412883007, 601054060, 36600204, 263431593, 527146271, 679451560, 750735348, 933329139, 87900762, 299130917, 9020219, 901297387, 236212865, 663261579, 19295460, 969247446, 295111838, 91368376, 893191269, 991786858, 408662232, 341008576, 536441349, 152803701, 756340475, 139637873, 219551043, 888234586, 185587333, 334323826, 203643380, 88863349, 670763770, 81762307, 34735503, 681539367, 950929292, 680103763, 814310151, 133579723, 699840645, 193262688, 667076225, 4488677, 620689603, 306362401, 288516864, 389221490, 602518707, 6426301, 954162282, 77681977, 956763825, 715201757, 741188674, 328855980, 631159967, 530115231, 253279191, 363859480, 681347354, 462150401, 683930616, 685708960, 794749110, 109716772, 754370777, 470916188, 375093194, 9503695, 387826778, 310591542, 698050256, 911714162, 8898664, 466576770, 679739662, 880377204, 667340550, 686435015, 853818840, 189859740, 252839574, 412953626, 391323353, 427913643, 804765340, 600058120, 818427260, 581267615, 993824532, 837984762, 326922305, 968289604, 329916404, 628207545, 160338489, 961560761, 752669574, 864220278, 461264877, 953867868, 983825183, 973947787, 791020446, 719834924, 120078491, 773346245, 331491220, 622898690, 193403574, 694836904, 778478941, 667985188, 532525454, 474739232, 881246563, 212780896, 219167002, 829861301, 545229758, 856451252, 788557390, 755959622, 24206180, 218079527, 956133057, 960468897, 367036654, 90964801, 461758555, 994000096, 668086034, 96116754, 955071799, 981864381, 826323000, 81479017, 241659621, 736540754, 491984618, 754624573, 578748282, 633936510, 182733782, 885464112, 553359806, 538942220, 444153107, 411378059, 861834412, 934139156, 183790290, 494096107, 300638545, 463123382, 446450633, 255313790, 122194922, 598983485, 412304757, 337078904, 709178419, 464051748, 757726516, 273916739, 392374816, 600451530, 668576908, 535081063, 102737210, 659879301, 442439126, 126390715, 717728340, 163954301, 201833725, 87908961, 342424598, 804181995, 862888640, 237380475, 611277421, 788663106, 933024770, 324132019, 145497018, 66344930, 399349084, 279775695, 636742599, 896684226, 330062685, 587237428, 349608160, 672706608, 238804620, 527984483, 987392530, 854540524, 247938012, 246776286, 731370319, 652115215, 756545220, 500768479, 735722521, 825905157, 559903568, 38280779, 602237355, 10542340, 276511738, 232285671, 983493641, 307275991, 76382309, 178798287, 61414577, 914879276, 877303304, 339928603, 302779204, 277509, 74632788, 442237462, 928693891, 139103273, 750865391, 466563560, 913305369, 268357629, 205663663, 683166287, 929689279, 462980410, 895899043, 214217901, 327433577, 938762780, 10356191, 913813483, 573311028, 437017291, 103544714, 846825636, 684690787, 876528145, 201113780, 58317492, 398985229, 460412413, 942878196, 56895635, 504655848, 610741716, 307329772, 568183155, 156365816, 796968400, 37934009, 781705457, 415196370, 870895690, 694937568, 525740357, 289340011, 750448141, 138212452, 450014897, 466887019, 377859018, 369023126, 344228865, 277775036, 775675507, 941984962, 885887282, 88693320, 914138771, 217983996, 520401965, 313118013, 287599168, 27978454, 717390770, 824209625, 239470952, 526783367, 761598327, 196315884, 117439191, 883834868, 939748372, 525560439, 728591569, 847509122, 541527886, 940714061, 243776319, 150456349, 373667994, 197516417, 41018874, 305082020, 590432684, 413339289, 721349601, 128039049, 568198258, 439672455, 397743854, 140363930, 444505807, 565339607, 755233404, 126970142, 188578573, 769552793, 127537511, 141721736, 970300825, 989001590, 525603411, 122645216, 931255145, 487594027, 537359434, 905214814, 254206539, 419519381, 473518077, 681099729, 353429402, 701179941, 392726499, 183395798, 932555733, 716950491, 822550235, 801411048, 522793944, 668880304, 827132057, 470157275, 154240557, 288246973, 816119971, 465187308, 238856027, 4082384, 703142856, 652031514, 981418619, 414824319, 206860943, 77596745, 482050056, 162693467, 58506574, 581252306, 61308535, 526685256, 231152222, 478650185, 912191365, 549844020, 517138914, 479357132, 658501384, 374935463, 819849216, 332151253, 173398034, 134962344, 12790663, 28775969, 413224372, 369775023, 294383960, 934583693, 968566627, 938356622, 37673053, 614907214, 773421952, 650055230, 959609550, 577167887, 670816297, 189842965, 945678480, 158443235, 349116776, 330962023, 963050710, 78237438, 306254037, 688554394, 826146543, 523874035, 964373950, 859862801, 702769244, 175149434, 444536674, 61383569, 26741806, 316551134, 116912655, 505139798, 465089514, 178548986, 719457254, 77393612, 384996132, 546174747, 214112100, 632074279, 809027912, 380356988, 536479160, 146601199, 585933493, 725346083, 447019123, 957467174, 245809129, 257385363, 516541398, 493397075, 683095683, 325853606, 558658841, 190202977, 867885418, 418680620, 919225123, 144778640, 67109316, 277826779, 242868291, 695109552, 395115340, 327329344, 438855655, 32508272, 967331642, 967388980, 180722007, 886065361, 854408350, 29892614, 259157817, 586469329, 887993853, 340524674, 374696085, 80365020, 889644342, 617635944, 691132377, 960316197, 727112558, 464027887, 786415679, 438902757, 233657781, 474405173, 674142579, 555138087, 592145681, 535658360, 73552906, 33923465, 78368163, 646113322, 960123624, 115127431, 34109124, 734004286, 81020871, 228356878, 84550693, 848210987, 27963747, 18135507, 357755871, 96378055, 806735748, 521741633, 621385655, 746575564, 242570971, 263304470, 311274908, 428758585, 83448900, 587059685, 481679061, 804690954, 835742178, 52804454, 330939356, 487149490, 772332353, 760529702, 500288275, 828757900, 239396561, 211068127, 980564483, 775729030, 184040657, 508353914, 703089773, 887108362, 463800861, 349974543, 522093856, 396731269, 719991483, 970414920, 178441436, 721195653, 751299903, 273424513, 648001424, 818145713, 489290949, 885951814, 834711522, 248856740, 238001557, 39245244, 152588434, 745880805, 442861914, 533278594, 50532524, 666825625, 265918358, 581912507, 866411991, 856071106, 609889701, 309319544, 382008467, 530442576, 544264465, 417887448, 314861966, 925346758, 452404013, 315318131, 326722256, 361109811, 78754775, 164670917, 113387470, 920328994, 959684322, 835019307, 875815106, 762967913, 845057723, 96018116, 601093506, 554233359, 283624308, 973779080, 290918360, 708043434, 318521507, 937082301, 91180707, 669612644, 446891006, 192108715, 715308901, 857715319, 128323067, 533681881, 993006416, 375283813, 549302421, 939815921, 610053553, 479297011, 729161775, 462808160, 781673363, 341082107, 639090477, 46148367, 658023600, 581560869, 143320676, 572628387, 437748076, 842428279, 320118228, 7364295, 247769847, 381309152, 911082245, 504030834, 910555467, 141713244, 907488359, 993926414, 78200068, 490370682, 62428827, 774989320, 194720494, 803465850, 329391292, 189440669, 57445044, 406925027, 345268388, 240961335, 828868582, 377457380, 182182173, 712703137, 808567033, 586308281, 689460911, 108405261, 604361087, 55681230, 211189317, 780790703, 191531068, 587776997, 2468927, 544424667, 366764579, 841454171, 816085124, 607596500, 628394483, 301902318, 447332259, 440726262, 749020772, 926982045, 918226611, 855735252, 523597231, 438976951, 457735535, 507742680, 111378905, 921427818, 513734809, 663538034, 467516161, 119724813, 269474983, 417898778, 177464210, 620949128, 407802690, 155400490, 603807497, 175266722, 361867564, 523544379, 516966443, 59459405, 499255486, 892033168, 268701223, 499746638, 512025438, 11832251, 590108000, 849142036, 277056923, 907673681, 846815650, 788656000, 578632834, 352611715, 997513431, 218949164, 226857477, 83001548, 220204634, 251591384, 869939059, 543376694, 622678138, 899846925, 647543568, 251715397, 977646942, 922647353, 800241929, 513405131, 907359940, 525174615, 648491814, 25658861, 983132047, 432067763, 21466523, 916658080, 254808912, 823337672, 870116257, 706570689, 615030, 432549127, 493370954, 163377614, 232442186, 229768696, 639712295, 548079236, 439005430, 669923745, 425209988, 353478809, 215313298, 850052207, 471107605, 411827484, 324682099, 190429490, 173476664, 214706206, 465308902, 337294153, 432731350, 883359915, 334635163, 268160413, 153887016, 917064674, 477802344, 718850584, 842939686, 989815000, 790131309, 572149420, 802392819, 116838322, 284513766, 93622465, 374363741, 812499174, 12134276, 974929572, 989075242, 403476907, 187042612, 489868752, 9706586, 165448631, 625599113, 18858110, 247646210, 302585671, 227249677, 437038817, 171853957, 903561135, 811347466, 169063621, 99305221, 992907518, 531908783, 603037770, 196351404, 282448694, 45946511, 118665134, 176508398, 528001019, 579363635, 96826076, 104768040, 523943642, 138443824, 178887517, 31874428, 730144169, 522652689, 116781926, 239469362, 972599278, 221263919, 833313730, 679422825, 350011549, 568702278, 953416027, 803246028, 134107919, 269249021, 165073990, 210773152, 127403963, 581277541, 986366246, 376193456, 595930739, 962260689, 359621764, 945329471, 680297708, 631223232, 421259883, 319520274, 300084487, 21615918, 30516863, 805431644, 439110478, 876474408, 25412879, 524943894, 670779280, 528401115, 103106924, 557182751, 717269547, 438980312, 835814956, 801620032, 910382143, 695427834, 185749805, 788994242, 754296738, 226019324, 232757292, 326833640, 640256267, 996179772, 81741632, 954441481, 809071775, 131371878, 372128021, 814291626, 944787901, 280188329, 981696050, 166806615, 717274605, 644431428, 212815934, 363048902, 507406390, 81780461, 805893664, 877012637, 117168742, 1875760, 901428307, 511820050, 378102680, 783775617, 842458388, 108416775, 366269199, 928608826, 82369755, 431194262, 54320823, 197120902, 65899556, 933531976, 913810647, 831054146, 959918763, 619588431, 264033080, 88506528, 303200807, 393510263, 630439817, 178771944, 68050390, 931553628, 459398847, 475071373, 650595878, 626652177, 807985399, 130835986, 136838777, 891503868, 979465579, 195205250, 654367068, 725947110, 387985427, 207489817, 35558619, 775846470, 472372475, 94438876, 566445294, 331415929, 807502307, 634087956, 325154492, 168618567, 196525179, 257455831, 564989320, 474258075, 417580426, 420695273, 813344126, 290495338, 113368159, 430190365, 851346410, 872623112, 853996804, 449157702, 394440072, 439864156, 86548026, 21306189, 692959184, 20334835, 365005074, 957477143, 570426069, 322706821, 265250503, 959584629, 688548559, 834591946, 68127916, 781710252, 110752556, 14767932, 680768346, 157220710, 318924553, 922840029, 974632062, 409915715, 684694751, 731062843, 641832410, 439749743, 316124585, 942668212, 463563206, 58899774, 628279548, 768563004, 393557898, 760010942, 53295764, 171614890, 623039732, 198759503, 835352957, 428804513, 572924073, 927038260, 219170814, 978328381, 113436004, 773379751, 628603078, 885470566, 186334476, 510202706, 550193427, 168265008, 716528315, 874668505, 986545399, 443555027, 619222876, 233082193, 396502176, 220180908, 244131778, 520371403, 617102057, 540130712, 940104013, 433419186, 841347446, 371765740, 163309013, 410554737, 640737089, 365020765, 407814530, 339309355, 803616061, 768498384, 785594671, 942727494, 420513291, 720886029, 103169986, 114232433, 457211039, 865336338, 919495005, 51059158, 897262210, 695409003, 93258988, 148254731, 423067889, 614540088, 646567497, 104386556, 137353287, 207683346, 235579648, 515406927, 966747864, 943360681, 637886380, 699872684, 27993226, 143807012, 791822903, 90578357, 655206625, 440196859, 649545822, 623732349, 836875456, 753840311, 361202515, 797956714, 824988171, 603684657, 665738165, 360274461, 742431795, 211110217, 845411601, 973840017, 759045525, 457428127, 757841347, 357874632, 328602377, 107958648, 860891292, 436307701, 128940780, 653494080, 468563815, 274966658, 925613587, 728601213, 229536114, 93772521, 297746018, 526366220, 947118821, 280776167, 856529899, 110621811, 198196708, 133710247, 63219073, 878150637, 876998743, 459211010, 359009365, 380477656, 967450572, 673439531, 534193625, 377092822, 618149177, 235890334, 778308115, 808690370, 572220160, 980465754, 34406687, 677314752, 304679531, 410024075, 800458712, 879057691, 238511586, 950699396, 706716468, 398185921, 390044268, 373666166, 47408672, 277977510, 476308581, 42368935, 916375517, 876325580, 876750485, 736289088, 234128391, 179198778, 740406229, 843334754, 73493717, 430867213, 692391869, 918819772, 51970993, 579565563, 758907934, 761112012, 489637361, 241432325, 304542191, 890296750, 906781405, 540508286, 439660619, 173757421, 848157954, 539399598, 32874052, 510789855, 76587436, 506283470, 341518836, 109743389, 938642214, 747610737, 899908192, 654028127, 538676001, 315307636, 700293841, 856936684, 813453703, 267105287, 437391514, 948762341, 331478263, 940802656, 526081115, 959050542, 648357405, 337226179, 615852814, 35909670, 724716407, 411972037, 314952647, 291027023, 448792500, 369304068, 728089586, 654653584, 801180649, 598095097, 348232893, 687715674, 851091320, 175996846, 870095706, 429596471, 892225323, 797937122, 993972536, 103374056, 382092521, 985977573, 786103498, 854339429, 660512045, 523873901, 968134025, 812998904, 625170351, 157581580, 893770602, 913063038, 110380157, 930344596, 844694439, 135479471, 762962321, 578405474, 921181398, 563729433, 582907268, 695452118, 52220153, 264488244, 304012700, 518027320, 163206411, 631160607, 809858226, 105630820, 666241059, 543252352, 878105551, 189973686, 283289445, 784216819, 436998533, 612619666, 845875135, 387333021, 145695228, 472584362, 140315100, 964867124, 444164377, 733664759, 567406129, 630881324, 298804964, 427310166, 924911119, 275655938, 696930295, 437433471, 250492355, 621402787, 733215101, 127755795, 59341816, 7817639, 872881222, 501016764, 542890387, 919708996, 90403332, 825067609, 879498110, 874225967, 469791702, 587894090, 297793639, 886985544, 316831517, 540267241, 602107249, 480149923, 563110045, 134180138, 436002447, 332315554, 562453321, 269282819, 101292147, 325707014, 407049381, 851213410, 599244852, 437690753, 203725046, 16516058, 448296313, 713435313, 456191897, 448087795, 442874845, 678863194, 245645577, 184590162, 727473136, 942721679, 369624103, 995472600, 695459151, 513895993, 120693215, 251208744, 144948646, 921265041, 935560551, 44355600, 529529471, 736140291, 750633826, 407589350, 359086346, 932737791, 485336881, 429025142, 177495028, 296426086, 573656246, 189433818, 487903568, 274840583, 804449064, 179830102, 477993508, 556816598, 366004990, 20377155, 579968414, 158763807, 977734274, 911662081, 204003693, 335000836, 266664998, 141738035, 585096599, 837490632, 108131377, 267964934, 339673365, 894241781, 547001741, 522921867, 104134382, 351449547, 462644732, 955716371, 245265942, 590675838, 791453467, 684880895, 675254643, 789724754, 746506929, 287157765, 584735885, 460014195, 297695894, 561149119, 971479976, 758124410, 268837226, 961039957, 700039482, 247916289, 724892871, 821215763, 850622767, 918284612, 753078102, 49636584, 24982149, 692420735, 175986567, 334736121, 78585365, 732701227, 650567629, 546355273, 240602889, 938144530, 127566999, 657860226, 89293574, 868019828, 379340420, 416345319, 592638888, 708115437, 927490806, 706127890, 543352919, 424289997, 844269863, 297819160, 159475227, 539106026, 910010157, 214784970, 597528538, 58091324, 760120653, 393512630, 293114965, 168705948, 383338428, 128983378, 25693731, 450388334, 126635970, 67950770, 124376738, 974086901, 160360022, 470591308, 125955495, 922670499, 980432291, 726456775, 738988670, 146942973, 309710170, 891045122, 692456394, 330291821, 844833096, 689532453, 616433928, 769986554, 898823018, 131087101, 997416517, 683165550, 291728885, 307773457, 66697076, 654985338, 736396600, 451975098, 83925578, 807431683, 583308744, 866649873, 434757108, 117892796, 482494180, 878601925, 974722273, 395459044, 219580658, 744049102, 977219869, 521240389, 62733608, 29846377, 345509245, 952230680, 189657319, 184930841, 170470769, 626473134, 546868432, 595308144, 216242442, 960475219, 300644817, 934061698, 879542972, 856236811, 746036563, 45408216, 192039463, 587105882, 613838885, 824605512, 638756625, 930025193, 834682837, 86615955, 283099303, 109952165, 991685498, 618423912, 1539074, 291211820, 779369996, 803022068, 840096778, 562220630, 133486515, 395097809, 270123661, 967699492, 823023770, 521172718, 797399101, 539889354, 461529003, 970436142, 296362132, 208181624, 874497198, 476023612, 967560584, 952034451, 890465762, 251519435, 350490836, 311900566, 847770771, 754054066, 843134746, 123989148, 29448699, 914314657, 693812418, 939394070, 688028184, 30866394, 457215913, 402762072, 271109321 }; int main(){ int cas; scanf("%d", &cas); while(cas--){ int n; scanf("%d", &n); printf("%d\n", a[n]); } return 0; }