1 0
2 1
3 8
4 144
5 610
6 46368
7 1346269
8 14930352
9 63245986
10 165580141
11 267914296
12 2971215073
13 4807526976
14 7778742049
15 12586269025
16 139583862445
17 365435296162
18 591286729879
19 956722026041
20 1548008755920
21 2504730781961
22 4052739537881
23 6557470319842
24 17167680177565
25 27777890035288
26 190392490709135
27 308061521170129
28 498454011879264
29 806515533049393
30 1304969544928657
31 8944394323791464
32 14472334024676221
33 37889062373143906
34 61305790721611591
35 160500643816367088
36 420196140727489673
37 679891637638612258
38 1779979416004714189
39 2880067194370816120
40 19740274219868223167
41 31940434634990099905
42 51680708854858323072
43 83621143489848422977
44 135301852344706746049
45 927372692193078999176