1 1
2 1
3 2
4 4
5 10
6 24
7 66
8 174
9 504
10 1406
11 4210
12 12198
13 37378
14 111278
15 346846
16 1053874
17 3328188
18 10274466
19 32786630
20 102511418
21 329903058
22 1042277722
23 3377919260
24 10765024432
25 35095839848
26 112670468128
27 369192702554
28 1192724674590
29 3925446804750
30 12750985286162
31 42126805350798
32 137494070309894
33 455792943581400
34 1493892615824866
35 4967158911871358
36 16341143303881194
37 54480174340453578
38 179830726231355326
39 600994488311709056
40 1989761816656666392
41 6664356253639465480
42 22124273546267785420
43 74248957195109578520
44 247100408917982623532
45 830776205506531894760