0 1
1 1
2 2
3 3
4 5
5 9
6 17
7 30
8 54
9 98
10 179
11 330
12 614
13 1150
14 2162
15 4072
16 7678
17 14496
18 27418
19 51979
20 98800
21 188309
22 359889
23 689649
24 1325006
25 2552031
26 4926589
27 9529551
28 18463098
29 35815293
30 69534171
31 135069124
32 262448803
33 510047416
34 991381433
35 1927317745
36 3747885517
37 7290999105
38 14190660743
39 27635876765
40 53855281619
41 105023118532
42 204950328191
43 400235323899
44 782121992125
45 1529365107427
46 2992330276506
47 5858068612098