0 1
1 0
2 1
3 1
4 2
5 3
6 8
7 12
8 23
9 44
10 86
11 163
12 308
13 576
14 1074
15 1991
16 3680
17 6800
18 12626
19 23644
20 44751
21 85567
22 164941
23 319694
24 621671
25 1211197
26 2362808
27 4614173
28 9018299
29 17635055
30 34486330
31 67408501
32 131642673
33 256795173
34 500346954
35 973913365
36 1894371802
37 3683559071
38 7162932291
39 13934056591
40 27122995482
41 52837914791
42 103025910182
43 201078168785
44 392840402171
45 768267754327
46 1504065160159
47 2947734744757