1 1
2 9
3 31
4 107
5 501
6 2339
7 10303
8 44523
9 198695
10 888601
11 3941855
12 18017983
13 83483541
14 389450325
15 1838319253
16 8707491533
17 41316656737
18 196349474191
19 934444664373
20 4453775875859
21 21254863852755
22 101613183769703
23 486794625431383
24 2336462749914239
25 11234510810496219
26 54112346147076479
27 261022053424348083
28 1260712616268317833
29 6096306094790683673
30 29510702674168799999
31 142993522072129749307
32 693513762856842616007
33 3366497118654779881009
34 16355650722143657557127
35 79525580817384943281021
36 386971940808802654412499
37 1884380283652864804959501
38 9182413742264393718662069
39 44774280072559899890374583
40 218458499210321000647752325