1 1
2 1
3 1
4 2
5 2
6 3
7 7
8 7
9 12
10 26
11 45
12 70
13 113
14 215
15 355
16 666
17 1153
18 2071
19 3785
20 6965
21 12495
22 22643
23 41608
24 76371
25 140944
26 261752
27 484968
28 904799
29 1689477
30 3160113
31 5928904
32 11139071
33 20970782
34 39535081
35 74697745
36 141342490
37 267812262
38 508194094
39 965623233
40 1837147717
41 3499726481
42 6674251373
43 12742529417
44 24353749263
45 46592216046
46 89224226322
47 171022101920