1 1
2 1
3 2
4 5
5 13
6 36
7 102
8 295
9 864
10 2557
11 7624
12 22868
13 68920
14 208527
15 632987
16 1926752
17 5878738
18 17973523
19 55050690
20 168881464
21 518818523
22 1595878573
23 4914522147
24 15150038699
25 46747391412
26 144370209690
27 446214862158
28 1380161749537
29 4271808447154
30 13230257155092
31 40999697820032
32 127125277962276
33 394372621278896
34 1224027903109004
35 3800782366178016
36 11807020794193895
37 36692964262887809
38 114075081792561953
39 354776999455994700
40 1103744752170689950
41 3434969224111688043
42 10693283693671410931
43 33298671757346685850
44 103720431801775331993
45 323160091718258161686