0 1
1 1
2 1
3 1
4 1
5 1
6 2
7 2
8 3
9 4
10 6
11 8
12 13
13 18
14 31
15 47
16 75
17 115
18 199
19 312
20 533
21 888
22 1536
23 2535
24 4608
25 7694
26 13894
27 24491
28 44278
29 78040
30 147863
31 260376
32 489921
33 906783
34 1701068
35 3139340
36 6130726
37 11328526
38 22059386
39 42281301
40 82180670
41 157539076
42 317031631
43 606850891
44 1217662195
45 2413169272
46 4836923613