Count the number of labeled strongly connected digraphs with the given number of vertices.  

Input Format 

The first line contains $\mathbf{T}$, the number of queries. 

Following are $\mathbf{T}$ lines. Each line contains one integer $N$, denoting the number of vertices.  

Output Format 

Output $\mathbf{T}$ lines. Each line is the number of labeled strongly connected digraphs with $N$ vertices, modulo $(10^9+7)$. 

Constraints 

$1\leq T\leq1000$ 

$1\leq N\leq1000$  

Sample Input

5
1
2
3
4
1000

Sample Output

1
1
18
1606
871606913

Explanation

You can refer to oeis.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Combinatorics


Solutions:
mod = 10 ** 9 + 7
lim = 1001
fact = [1] * lim
for i in range(2, lim):
	fact[i] = fact[i - 1] * i % mod

def bico(n, k):
	return fact[n] * pow(fact[k] * fact[n - k], mod - 2, mod) % mod
A = [1] * lim
for n in range(2, lim):
	x = pow(2, n * (n - 1), mod)
	for t in range(1, n):
		x = (x - bico(n, t) * pow(2, (n - 1) * (n - t), mod) * A[t]) % mod
	A[n] = x
B = [1] * lim
for n in range(2, lim):
	x = A[n]
	for t in range(1, n):
		x = (x + bico(n - 1, t - 1) * B[t] * A[n - t]) % mod
	B[n] = x
T = int(input())
for t in range(T):
	N = int(input())
	print(B[N])


import sys

def read_one():
	return sys.stdin.readline().strip()

def read_spaced():
	return sys.stdin.readline().strip().split()
mod = 7 + 10 ** 9
N_max = 10 ** 5
fac = [1] * (N_max + 1)
invfac = [1] * (N_max + 1)
for i in range(2, N_max + 1):
	fac[i] = fac[i - 1] * i % mod
invfac[N_max] = pow(fac[N_max], mod - 2, mod)
for i in reversed(range(2, N_max)):
	invfac[i] = invfac[i + 1] * (i + 1) % mod

def binomial(n, k):
	if n < k or k < 0:
		return 0
	return fac[n] * invfac[k] * invfac[n - k] % mod
N_max = 1000
C = [0] * (N_max + 1)
C[1] = 1
e = 0
for n in range(2, N_max + 1):
	e += 2 * (n - 1)
	C[n] = pow(2, e, mod)
	f = n - 1
	for i in range(1, n):
		C[n] = (C[n] - binomial(n, i) * pow(2, e - f, mod) * C[i]) % mod
		f += n - 1
ans = [0] * (N_max + 1)
ans[1] = 1
for n in range(2, N_max + 1):
	ans[n] = C[n]
	for i in range(1, n):
		ans[n] = (ans[n] + binomial(n - 1, i - 1) * ans[i] * C[n - i]) % mod
T = int(read_one())
for _ in range(T):
	N = int(read_one())
	print(ans[N])


mod = 10 ** 9 + 7
MAX = 1001
(l1, l2, l3) = ([[0] * MAX for i in range(MAX)], [0] * MAX, [0] * MAX)
for j in range(MAX):
	for k in range(j + 1):
		if k == 0 or k == j:
			l1[j][k] = 1
		else:
			l1[j][k] = (l1[j - 1][k - 1] + l1[j - 1][k]) % mod
	l2[j] = (pow(2, j * (j - 1), mod) - sum((l1[j][i] * pow(2, (j - 1) * (j - i), mod) * l2[i] for i in range(1, j)))) % mod
	l3[j] = (l2[j] + sum((l1[j - 1][i - 1] * l3[i] * l2[j - i] for i in range(1, j)))) % mod
for _ in range(int(input())):
	print(l3[int(input())])


l3 = [1, 1, 1, 18, 1606, 565080, 734774776, 91590907, 945029720, 225976269, 401947654, 28703024, 279348018, 91370483, 542112891, 522481903, 142946377, 200371076, 526707214, 257483430, 128606379, 727915590, 158447644, 413475262, 648547978, 859320402, 832528682, 707319559, 541681316, 592826011, 448091261, 94409847, 419697294, 557146408, 178211493, 951502908, 574767854, 128243508, 487256455, 991102558, 144217510, 64746231, 391624752, 199593820, 388986741, 159020224, 456788232, 808089556, 721173385, 31180448, 600855893, 309844723, 602022029, 843747569, 990016487, 182709112, 369026937, 453900409, 129553821, 331521765, 632368314, 271431074, 692621076, 542024721, 614535810, 857761839, 942197603, 799978878, 939754356, 510784510, 83113134, 188467406, 566900895, 755834384, 37704059, 170867788, 246366150, 627908045, 574612269, 13086718, 951536565, 23406186, 348844664, 291163301, 333373839, 342981057, 481521010, 368180542, 420621863, 255357751, 460046753, 309315737, 253606720, 400235124, 687773999, 102288186, 329579923, 602652458, 759791863, 141961538, 311807697, 532263532, 872979174, 39095052, 590683896, 728377534, 924417790, 216470318, 219837472, 679509534, 128762337, 769272743, 71963076, 557895069, 189012932, 205059625, 259793575, 847446502, 816014515, 317956889, 196179090, 444151688, 580320114, 891039183, 725241258, 179931767, 122472249, 893090419, 497306849, 248737775, 257046780, 103089850, 620598937, 612417908, 661704131, 674706414, 7158286, 451998138, 463777714, 658568376, 643745543, 573385030, 421632794, 65566156, 329446183, 856016917, 695681475, 78714881, 265025885, 466051571, 33419908, 177608289, 262221902, 780194056, 742614492, 611537497, 473004782, 423895838, 718036820, 313760625, 554300118, 714304084, 468812478, 162094237, 438980187, 344512210, 664200081, 400783271, 476585654, 998932024, 946631332, 348575069, 853025970, 637219350, 954109412, 732582276, 162752241, 689202881, 440160772, 953826177, 358456713, 832566765, 545497787, 29096722, 687608202, 677117892, 722502751, 234200296, 813755022, 504573725, 229835530, 81975531, 118562465, 134555282, 155644880, 100178563, 52796326, 301174083, 505803984, 851649805, 674065881, 391680520, 144682727, 678305283, 126362675, 507531673, 339851753, 581245955, 662801008, 797486985, 835963847, 909141003, 558546473, 268659026, 610772676, 491891519, 353349879, 975117557, 571835781, 701386198, 20627748, 563919235, 307457668, 251668654, 918711217, 13333946, 196921857, 480168049, 751856260, 321641157, 684677568, 256561709, 838316778, 372728929, 64332919, 28865631, 879470478, 912242041, 309137219, 193683838, 740024825, 448857653, 399006270, 593604098, 14069858, 906378547, 353404821, 668984344, 342472609, 450129952, 562776076, 318583552, 239911724, 778025225, 681887906, 83792931, 153432896, 977335040, 542696809, 853559022, 385463716, 83814872, 660114826, 980534916, 494444614, 605454192, 964037139, 143408797, 593198145, 573961887, 816676440, 976319338, 606190602, 798819002, 141068939, 178793135, 14440652, 563341022, 305430210, 399837515, 985789408, 647097227, 814700625, 78881469, 281396397, 562946595, 717888052, 865196423, 873344745, 733718080, 397421596, 580401807, 750896303, 907604807, 774111523, 499703095, 331425952, 724092860, 735378264, 893277040, 935339044, 265511524, 429215240, 812772903, 46012587, 706490136, 767734802, 500278271, 760418608, 982884938, 349768287, 562143235, 727517810, 144655295, 662347818, 699947771, 928979823, 678777517, 459842362, 413697126, 795472654, 750007283, 467443978, 648000319, 843403412, 225831733, 771322133, 701576796, 365689066, 854482962, 977755862, 378495224, 131648344, 234348159, 906889061, 934582005, 340406942, 682836249, 639216457, 989518998, 280923091, 891514259, 876785024, 564595874, 240120804, 473701508, 757750763, 192711647, 10143468, 262795292, 592086282, 974528050, 73272940, 960671474, 522103162, 611535898, 737058775, 728634729, 435711991, 20306955, 152649740, 773808582, 527325185, 808970156, 589611079, 187287306, 830331548, 375875230, 458117066, 244002371, 173289888, 173996567, 807826457, 3732076, 73871563, 347340678, 946497496, 340110862, 579298178, 904109555, 173482336, 875112612, 930658912, 645754901, 678101694, 708006055, 12667803, 390256125, 91642972, 514636610, 852019278, 896423431, 872307698, 97403711, 110750247, 414015550, 637036793, 957039304, 569253591, 823032346, 74659625, 378907697, 714877609, 221765707, 878461478, 646930645, 740693755, 658299813, 12964531, 166034564, 424359157, 510246727, 321416889, 239937232, 875823826, 337288678, 472749616, 29071381, 864490974, 795935034, 503202856, 948286451, 798803054, 621270478, 386308789, 770204337, 246541831, 245356732, 350063716, 289917325, 67589212, 262283792, 533640526, 135975517, 815902499, 579883719, 135751997, 134375163, 11008220, 393089965, 101104429, 286734768, 621978498, 747334170, 909474786, 728967486, 784901644, 384745276, 135649809, 471219579, 916980957, 456110490, 88868657, 571266744, 765769006, 155746540, 509484020, 922080682, 402114079, 526374651, 128311703, 947470644, 622571824, 836327861, 73252137, 649874757, 492823094, 57232049, 227438370, 99387110, 110518070, 324412953, 353970083, 932140454, 165605327, 491832168, 107054826, 894969065, 329390776, 644763417, 210039102, 412680219, 460637331, 290572842, 598676576, 659848625, 490054561, 59374299, 655263048, 105674644, 744322645, 235373792, 465990599, 167382965, 468199032, 110597259, 400761743, 802192156, 853384391, 56984252, 838933361, 153363756, 74888223, 621095960, 626266908, 709745702, 789239892, 130706776, 452788092, 439520821, 809027308, 712345663, 984040145, 987391120, 615544680, 186859536, 267969556, 187342130, 466687683, 226771410, 191412124, 618489697, 726458889, 387485372, 687566796, 250634575, 272348489, 264807683, 413685351, 940157450, 540958169, 605191078, 631827676, 261281275, 514817216, 516500931, 632500978, 340363749, 564346898, 352177695, 344989497, 317545025, 419692805, 701368656, 785032865, 427477478, 90907084, 385196203, 522690360, 910598840, 475804656, 903564474, 578875111, 476101211, 773524025, 413683176, 359219925, 235129641, 323043913, 446656159, 469448975, 301606504, 368733697, 32800129, 398193185, 87032597, 834712473, 870483475, 401243614, 266069485, 313585464, 180797646, 139986618, 61116820, 139730688, 949286806, 964935328, 755306143, 906136681, 887829621, 707637541, 4832387, 70481774, 457775786, 768533879, 543728824, 31118343, 846124102, 365849351, 677081686, 184854998, 923703383, 211357822, 15417931, 446443560, 173822085, 556166928, 259527248, 764856443, 823343375, 952721496, 873799302, 733702684, 725122872, 107080251, 849028880, 588722690, 652718753, 795084710, 740059529, 434020086, 567353337, 865613293, 240478828, 10034672, 177267057, 580663651, 482061964, 844760840, 547246695, 853796645, 518679272, 682815424, 138145638, 12308100, 702945651, 193834746, 19902371, 238330312, 186718465, 172884614, 163723018, 767870524, 939058472, 326630606, 559361174, 954831759, 882696608, 941440171, 946378704, 576796779, 174605135, 297249545, 473570461, 658363877, 348259098, 108462602, 549380646, 523593962, 409708937, 205298597, 500624241, 471238125, 894918660, 144252673, 566782091, 973439733, 125700337, 304850804, 363483819, 401929370, 875748664, 230853826, 836905534, 244769392, 388267172, 883727348, 194329226, 351390130, 414823312, 317725262, 985703145, 316363817, 237454539, 774826952, 957739950, 430899591, 562549088, 875784402, 136591303, 629947079, 817591166, 840518295, 409455153, 955882207, 62583348, 60332874, 894026769, 695202474, 918230598, 215208538, 275874111, 438580986, 139186100, 173155516, 805731318, 858693738, 595945729, 375442979, 48036845, 295101163, 742483867, 615372696, 303332551, 644487500, 19883697, 433534540, 244200871, 195294190, 233603840, 304722255, 733304461, 364546651, 802397953, 985772270, 211412016, 585991332, 361433375, 794132459, 714239432, 975957933, 168894036, 303520455, 388941666, 609679178, 328130866, 523408221, 2349369, 153001821, 490794121, 436692103, 133349077, 459968012, 923308953, 417363354, 273448538, 641232222, 580226327, 415791579, 845471789, 727525130, 363508152, 702699860, 112853391, 725515410, 96169623, 454535525, 367561738, 583878188, 119004249, 911535327, 861326161, 944608506, 203467210, 892996635, 478051338, 424313818, 334121487, 271111616, 753773711, 907436480, 684829090, 467194223, 330389191, 297218414, 985596705, 374450449, 738123564, 390647516, 509695626, 256105353, 154236439, 621072879, 689358498, 415910280, 314527468, 344448566, 956368615, 833315547, 930909373, 161305585, 880424679, 653009479, 469992846, 684515534, 984505316, 292611411, 252848418, 808601135, 601145415, 765121616, 329100593, 897194355, 982676420, 170817138, 880446804, 425204332, 120509244, 19466938, 193592089, 751428195, 887787127, 15602129, 393640745, 261492294, 831240134, 985740956, 927690504, 926656673, 658389166, 86417502, 581975475, 759197977, 760989596, 543764333, 111922546, 103391814, 174907225, 16515973, 119666718, 302129695, 428721958, 199629436, 336543702, 66652330, 1066484, 328371768, 985544500, 198907460, 673219533, 225930658, 197775496, 989668226, 249112811, 507196581, 155244150, 730948675, 251929095, 384122484, 298812843, 217966472, 91772695, 907295335, 332467742, 705467567, 743551308, 631234568, 886756118, 653444801, 679687399, 132831891, 119158677, 793391732, 794671299, 479878190, 681515369, 900740912, 68370919, 321264307, 844921072, 923366405, 168865115, 861912001, 684056728, 337254890, 583984079, 298667, 606789485, 886284059, 34216508, 191081516, 337944411, 820724010, 76245697, 155133431, 356786797, 888477728, 529120387, 549804652, 179382908, 440737516, 688491038, 75542284, 335486582, 120053457, 833894622, 146171227, 982308766, 448231328, 509529230, 807149690, 924928289, 463992356, 999590930, 75984727, 624828323, 409040018, 754005177, 974368768, 130881525, 284705929, 152605943, 915628118, 108851460, 794165240, 718130154, 197626025, 849773556, 182548124, 337814266, 882519239, 493507168, 649244603, 197646058, 539393934, 60176397, 81402656, 607655525, 496864450, 979559765, 498118185, 935556105, 489550827, 511287218, 801835977, 497584612, 607438365, 550852609, 60993405, 319779793, 240730055, 838139673, 535387368, 902659685, 840072637, 515080573, 401524828, 997254472, 819091716, 770700327, 617782442, 210396264, 139187459, 450294840, 949372253, 149607941, 99054298, 446365837, 217725723, 555140958, 673084593, 557097827, 807133578, 330288217, 873861468, 889145056, 237669438, 891318173, 843795667, 667593829, 985250727, 801874041, 196323500, 218740794, 856597768, 238407778, 87653100, 171736102, 324479384, 716119672, 997380460, 33273470, 989251732, 76930000, 574999002, 225535385, 564871662, 319109015, 79106410, 196663005, 262109571, 947052127, 139620579, 251250247, 726128408, 651708161, 93876755, 942012457, 827647554, 307148413, 775388862, 309468428, 329573926, 19363710, 38516518, 30793706, 625532857, 703763534, 550666501, 101478103, 871606913]
for _ in range(int(input())):
	print(l3[int(input())])