1 1
2 1
3 2
4 5
5 14
6 38
7 120
8 353
9 1148
10 3527
11 11622
12 36627
13 121622
14 389560
15 1301140
16 4215748
17 14146335
18 46235800
19 155741571
20 512559195
21 1732007938
22 5732533570
23 19423092113
24 64590165281
25 219349187968
26 732358098471
27 2492051377341
28 8349072895553
29 28459491475593
30 95632390173152
31 326482748703999
32 1099952564143246
33 3760291809049416
34 12698087239648594
35 43462640562005209
36 147070289751324061
37 503941612931723170
38 1708391899249131306
39 5859696262000756532
40 19897618166731615449
41 68309651603081955628
42 232304872236332885771
43 798176289858611935664
44 2718104498099497818482
45 9346232311986692725748