1 1
2 1
3 1
4 1
5 2
6 2
7 6
8 30
9 69
10 230
11 662
12 2244
13 6197
14 20782
15 57963
16 185236
17 534294
18 1636436
19 4788888
20 14148505
21 41505698
22 119551191
23 347802192
24 984873101
25 2823972122
26 7899999963
27 22281193586
28 61710573450
29 171287868395
30 469925476292
31 1285821121591
32 3493758280981
33 9441195012781
34 25400631652960
35 67893074450681
36 180852721497419
37 478659409344539
38 1262663092888764
39 3311459912474059
40 8653594973767684