0 1
1 1
2 1
3 3
4 3
5 5
6 8
7 10
8 13
9 18
10 26
11 31
12 42
13 52
14 68
15 89
16 110
17 136
18 173
19 212
20 262
21 330
22 398
23 487
24 592
25 720
26 864
27 1050
28 1262
29 1508
30 1804
31 2152
32 2550
33 3037
34 3584
35 4236
36 5011
37 5880
38 6901
39 8095
40 9472
41 11048
42 12899
43 14996
44 17436
45 20261
46 23460
47 27128
48 31385
49 36189
50 41713
51 48020
52 55209
53 63359
54 72708
55 83298
56 95299
57 108960
58 124401
59 141887
60 161737
61 184108
62 209351
63 237948
64 270079
65 306331
66 347222
67 393090
68 444660
69 502715
70 567739
71 640722
72 722567
73 814206
74 916681
75 1031571
76 1159721
77 1303027
78 1463159
79 1641599
80 1840601
81 2062626
82 2309640
83 2584696
84 2890862
85 3231120
86 3609253
87 4029479
88 4495722
89 5013056
90 5587183
91 6223271
92 6927797
93 7708411
94 8572082
95 9527531
96 10584447
97 11752132
98 13042341
99 14467282
100 16039846
101 17774660
102 19688613
103 21797641
104 24121819
105 26682361
106 29500808
107 32602461
108 36015571
109 39767931
110 43893086
111 48426348
112 53405113
113 58871780
114 64873026
115 71456549
116 78677448
117 86595519
118 95273045
119 104780569
120 115195535
121 126596997
122 139076843
123 152733100
124 167669196
125 184001534
126 201856065
127 221365149
128 242677527
129 265954242
130 291364715
131 319098591
132 349360226
133 382367223
134 418359161
135 457598100
136 500358834
137 546946809
138 597692798
139 652947895
140 713098247
141 778562713
142 849784804
143 927254964
144 1011500075
145 1103083797
146 1202621156
147 1310779968
148 1428268584
149 1555864162
150 1694404638
151 1844783861
152 2007977219
153 2185039214
154 2377089294
155 2585355754
156 2811155651
157 3055899278
158 3321118130
159 3608465820
160 3919705005
161 4256752295
162 4621670023
163 5016664325
164 5444125254
165 5906626963
166 6406918181
167 6947978461
168 7533013515
169 8165444553
170 8848979968
171 9587602300
172 10385565988
173 11247474567
174 12178271011
175 13183239154
176 14268084480
177 15438930094
178 16702326223
179 18065332796
180 19535532603
181 21121021694
182 22830532608
183 24673428280
184 26659716797
185 28800171044
186 31106343638
187 33590577981
188 36266155739
189 39147303717
190 42249233232
191 45588276771
192 49181950932
193 53048950284
194 57209365777
195 61684700675
196 66497930038
197 71673698844
198 77238401528
199 83220207311
200 89649341275
201 96558124039
202 103981076578
203 111955186942
204 120520016994
205 129717789949
206 139593732331
207 150196188075
208 161576751023
209 173790642507
210 186896879883
211 200958404581
212 216042578757
213 232221339555
214 249571413425
215 268174845358
216 288119230064
217 309497969762
218 332410887017
219 356964516397
220 383272427062
221 411455925470
222 441644434854
223 473975880918
224 508597519683
225 545666402895
226 585349838286
227 627826386343
228 673286401749
229 721932630787
230 773981347009
231 829663027537
232 889223061464
233 952923142014
234 1021042007399
235 1093876401187
236 1171742561607
237 1254977301122
238 1343939010649
239 1439009539747
240 1540595366732
241 1649128960667
242 1765070849109
243 1888911166943
244 2021171158233
245 2162405770759
246 2313205324532
247 2474197533524
248 2646050349902
249 2829474168675
250 3025224095579
251 3234103384063
252 3456966022093
253 3694719546677
254 3948328939942
255 4218819904334
256 4507282030109
257 4814873625420
258 5142825353240
259 5492444288841
260 5865119366951
261 6262325916027
262 6685630371423
263 7136696773837
264 7617292072770
265 8129291912253
266 8674688056036
267 9255594901820
268 9874256224011
269 10533054048151
270 11234516255134
271 11981324699931
272 12776325561961
273 13622538508040
274 14523166192844
275 15481606554901
276 16501463526384
277 17586558499569
278 18740944657913
279 19968919664359
280 21275039395720
281 22664134507713
282 24141325778123
283 25712040111287
284 27382030186499
285 29157392442904
286 31044586177291
287 33050456413081
288 35182255382471
289 37447664893333
290 39854823407916
291 42412351015228
292 45129376361508
293 48015567910557
294 51081163851263
295 54337003485161
296 57794564161203
297 61465996324550
298 65364160780065
299 69502671623997
300 73895937927763
301 78559207135951
302 83508615982041
303 88761238854790
304 94335139637454
305 100249430507321
306 106524329531359
307 113181221081770
308 120242725155102
309 127732764472144
310 135676636207321
311 144101092184099
312 153034418576828
313 162506519355630
314 172549010738368
315 183195314061381
316 194480754283007
317 206442669780201
318 219120521913393
319 232556009813783
320 246793199397241
321 261878650773005
322 277861553954625
323 294793878213160
324 312730522468863
325 331729473169671
326 351851979211954
327 373162727647063
328 395730028688424
329 419626019401599
330 444926869372944
331 471712996853511
332 500069306601092
333 530085429753057
334 561855976876335
335 595480814732681
336 631065346548681
337 668720807643030
338 708564587540231
339 750720557419453
340 795319414859867
341 842499058793623
342 892404971578628
343 945190621230657
344 1001017897355784
345 1060057556926826
346 1122489692574009
347 1188504240343555
348 1258301498342119
349 1332092672755131
350 1410100467692000
351 1492559689367775
352 1579717881490988
353 1671836011138955
354 1769189170951215
355 1872067319787567
356 1980776077282098
357 2095637542696657
358 2216991154226783
359 2345194613205356
360 2480624834099147
361 2623678944528746
362 2774775356469687
363 2934354871349576
364 3102881839879814
365 3280845406038826
366 3468760788057459
367 3667170627640355
368 3876646429010234
369 4097790048215611
370 4331235255817714
371 4577649406917953
372 4837735165923817
373 5112232321190150
374 5401919716482457
375 5707617253446471
376 6030187991008993
377 6370540385306155
378 6729630605774933
379 7108464970763224
380 7508102536177754
381 7929657779877212
382 8374303419701688
383 8843273409443514
384 9337866043412880
385 9859447220088186
386 10409453902329066
387 10989397712739205
388 11600868704753531
389 12245539363944753
390 12925168762808832
391 13641606922070118
392 14396799431105969
393 15192792250458765
394 16031736750059277
395 16915895045433070
396 17847645542483446
397 18829488758945774
398 19864053480079150
399 20954103162811109
400 22102542653597891
401 23312425290280795
402 24586960291976669
403 25929520511184678
404 27343650621026113
405 28833075640695442
406 30401709873747614
407 32053666346143157
408 33793266634538697
409 35625051169733786
410 37553790110521736
411 39584494667670988
412 41722428978666907
413 43973122626840723
414 46342383687129204
415 48836312400826912
416 51461315586674260
417 54224121660579231
418 57131796378945069
419 60191759417886255
420 63411801661739190
421 66800103313611946
422 70365252969199531
423 74116267499053068
424 78062612883806974
425 82214226137314418
426 86581538172046814
427 91175497749453962
428 96007596677634546
429 101089896085894630
430 106435053955379618
431 112056354054352348
432 117967736134944995
433 124183827546159912
434 130719976469859894
435 137592286587123466
436 144817653385785862
437 152413802300907734
438 160399328515701790
439 168793738624993163
440 177617494403157216
441 186892058463042761
442 196639942066583093
443 206884755309456479
444 217651259501250206
445 228965421984393382
446 240854473676059429
447 253346969113664757
448 266472849305116113
449 280263507660816713
450 294751858819221160
451 309972410652850971
452 325961339810308079
453 342756570548636750
454 360397857223633362
455 378926870781793442
456 398387289043081018
457 418824891144237949
458 440287656551592539
459 462825868396752969
460 486492221582547307
461 511341936063711492
462 537432875105095218
463 564825668949093652
464 593583844403830307
465 623773960094713265
466 655465747908755993
467 688732261158011471
468 723650029229947163
469 760299219286795642
470 798763805616547623
471 839131746383732463
472 881495168432778722
473 925950560770102242
474 972598976516227755
475 1021546244015603327
476 1072903187825004399
477 1126785859364459566
478 1183315777999832809
479 1242620183349636566
480 1304832298621524861
481 1370091605817819832
482 1438544133704799339
483 1510342758349655855
484 1585647517173266579
485 1664625937501850122
486 1747453379436320878
487 1834313394113653351
488 1925398098418171957
489 2020908566024667159
490 2121055235926972160
491 2226058339661482956
492 2336148347120241793
493 2451566432257351653
494 2572564959994502116
495 2699407994319363130
496 2832371828955329496
497 2971745542140025344
498 3117831575466769368
499 3270946338417893883
500 3431420840213036900
501 3599601349060589258
502 3775850080564268302
503 3960545917140247995
504 4154085158560259449
505 4356882305637441334
506 4569370879030397374
507 4792004273484129353
508 5025256649624751538
509 5269623865639159080
510 5525624449143791138
511 5793800611729791721
512 6074719308665290536
513 6368973344291138852
514 6677182525766808107
515 6999994868052824111
516 7338087850695802353
517 7692169729525174061
518 8062980906307803941
519 8451295357271838205
520 8857922123804532916
521 9283706868869225420
522 9729533500131306398
523 10196325863616671058
524 10685049511710291343
525 11196713546891024290
526 11732372545266943578
527 12293128564394623388
528 12880133236820297735
529 13494589954126948835
530 14137756146261439241
531 14810945658087779606
532 15515531228349832433
533 16252947076502933305
534 17024691599612897212
535 17832330185254972721
536 18677498146334193641
537 19561903780664570499
538 20487331561689194327
539 21455645467194329698
540 22468792449148221591
541 23528806051990014145
542 24637810186853400614
543 25798023065561713697
544 27011761302444487429
545 28281444192481133428
546 29609598170100114984
547 30998861457823662707
548 32451988914056782025
549 33971857085280908549
550 35561469472740396866
551 37223962024168538191
552 38962608856565763493
553 40780828221381395389
554 42682188723816057841
555 44670415803304728668
556 46749398487783635497
557 48923196434944492041
558 51196047268537126013
559 53572374223891456289
560 56056794117394399946
561 58654125649205464067
562 61369398055134598295
563 64207860124063121575
564 67174989591684206976
565 70276502928331508461
566 73518365539209238141
567 76906802389472317573
568 80448309073957782653
569 84149663352086165729
570 88017937162243621989
571 92060509137698385058
572 96285077647175075885
573 100699674376254978908
574 105312678474507686039
575 110132831294002661610
576 115169251737885575358
577 120431452246738503895
578 125929355451527502601
579 131673311514359462940
580 137674116188220048507
581 143943029627691255092
582 150491795975153482933
583 157332663757006822724
584 164478407126051302412
585 171942347977604690942
586 179738378978318115567
587 187880987547821667648
588 196385280824880247431
589 205267011661302052294
590 214542605688913567387
591 224229189495117916388
592 234344619955990100301
593 244907514776956433961
594 255937284282060523596
595 267454164505937179693
596 279479251645058708152
597 292034537914284437778
598 305142948869680153268
599 318828382260435011596
600 333115748462558080903
601 348031012561971756439
602 363601238157967636661
603 379854632945903368297
604 396820596155573822300
605 414529767923856600795
606 433014080668987486954
607 452306812551319488764
608 472442643109040434738
609 493457711144424521219
610 515389674956183632235
611 538277775016099948664
612 562162899176207068853
613 587087650512444071272
614 613096417915533334161
615 640235449525582574227
616 668552929129667174747
617 698099055645515025947
618 728926125800870776070
619 761088620141181813174
620 794643292503984222976
621 829649263082790734123
622 866168115229646336352
623 904263996150122450782
624 944003721630032527175
625 985456884959838869355
626 1028695970229330928035
627 1073796470148901700848
628 1120837008583380531710
629 1169899467990893623770
630 1221069121943234081827
631 1274434772934986390469
632 1330088895697237177075
633 1388127786213610836171
634 1448651716671075681698
635 1511765096585932168908
636 1577576640328006696729
637 1646199541302335884488
638 1717751653057247053323
639 1792355677569307440536
640 1870139360995064162402
641 1951235697189647524907
642 2035783139274201198277
643 2123925819575350338347
644 2215813778272508063658
645 2311603201069185166009
646 2411456666249691709851
647 2515543401496103643766
648 2624039550820385063421
649 2737128452015346939307
650 2855000925043063190531
651 2977855571758905915889
652 3105899087422104365260
653 3239346584460057781245
654 3378421928933174584812
655 3523358090203611137246
656 3674397504329371537600
657 3831792451685115426932
658 3995805449371024099032
659 4166709658992413876792
660 4344789310371402234898
661 4530340141817707076342
662 4723669857608538989139
663 4925098603306787871004
664 5134959459616814121111
665 5353598955503893465581
666 5581377601281026602595
667 5818670442444678736297
668 6065867635068073773162
669 6323375043541345406434
670 6591614861529192595496
671 6871026257049294855053
672 7162066042553880721681
673 7465209370986488659149
674 7780950458820512653329
675 8109803337067920568484
676 8452302631340749780487
677 8809004372089872113629
678 9180486836124356213507
679 9567351420620861159394
680 9970223550874746965895
681 10389753623028627246513
682 10826617983124983213144
683 11281519943880003871572
684 11755190840558099119969
685 12248391127450242822502
686 12761911516511359402576
687 13296574159700752107907
688 13853233876698062496053
689 14432779429731042987860
690 15036134847237100560543
691 15664260798225094652804
692 16318156019269766870386
693 16998858796064109289553
694 17707448501606988790105
695 18445047193181631828191
696 19212821270271522519305
697 20011983195731180361350
698 20843793282609726698509
699 21709561549026407679627
700 22610649643676260510204
701 23548472844639489078169
702 24524502134169348444759
703 25540266352331749855177
704 26597354432471774146960
705 27697417721493459641274
706 28842172388149144442348
707 30033401922654548182466
708 31272959730956135819481
709 32562771827213249231724
710 33904839628182881528763
711 35301242853219442411204
712 36754142533852081827971
713 38265784137046866458797
714 39838500806289468173542
715 41474716724900939895877
716 43176950606154561671705
717 44947819314805935214363
718 46790041624942605586760
719 48706442119239620494186
720 50699955234756121601057
721 52773629460734512641451
722 54930631694058262197619
723 57174251758090281406323
724 59507907090964872487785
725 61935147609626926343365
726 64459660755987606637018
727 67085276731953881475586
728 69815973930327744157958
729 72655884568669547944102
730 75609300533636697093883
731 78680679443578799341938
732 81874650937284409960990
733 85196023197231436779944
734 88649789715990705433219
735 92241136314569924784389
736 95975448421980619914225
737 99858318625644549832295
738 103895554502413851608983
739 108093186740523600158689
740 112457477563163145171165
741 116994929464538748174423
742 121712294269894637760963
743 126616582531365739401476
744 131715073271754498673972
745 137015324088971616954151
746 142525181634331805859280
747 148252792478150370982054
748 154206614376791694241459
749 160395427955822986950461
750 166828348824220132062136
751 173514840135341788919529
752 180464725610948144781134
753 187688203044873151363302
754 195195858303805970637808
755 202998679843252428331742
756 211108073757134256781666
757 219535879380405112623909
758 228294385464748171847538
759 237396346947858524732200
760 246855002337826213783778
761 256684091734889110519841
762 266897875513333796396351
763 277511153687419746522799
764 288539285986048634356006
765 299998212661468187756449
766 311904476058510992772143
767 324275242971797422226956
768 337128327818985034513233
769 350482216659463425519356
770 364356092088932928411740
771 378769859041033310938766
772 393744171528645240598274
773 409300460358621234570391
774 425460961854544466647902
775 442248747623692172454397
776 459687755405651799833210
777 477802821040974915982973
778 496619711599994645054756
779 516165159713329273250211
780 536466899146663577346504
781 557553701664292388298593
782 579455415227475329309466
783 602203003574834280941142
784 625828587234122912227721
785 650365486016406095090859
786 675848263045039883670830
787 702312770374122189926687
788 729796196252993746281100
789 758337114094870972307339
790 787975533210210455948560
791 818752951367497150454933
792 850712409245857908135884
793 883898546846637350856738
794 918357661933415458908731
795 954137770571836188769772
796 991288669843642157683524
797 1029862002811878230235098
798 1069911325816365251883229
799 1111492178181844053660082
800 1154662154424052682124443
801 1199480979041367179292864
802 1246010583983284492495109
803 1294315188890161470220787
804 1344461384201302479016820
805 1396518217232461891449510
806 1450557281327322375038823
807 1506652808190477824330456
808 1564881763513833471347619
809 1625323946012177355830811
810 1688062089987014195385213
811 1753181971542539220553628
812 1820772518581905671492639
813 1890925924715628859463581
814 1963737767219258541389450
815 2039307129182146083809494
816 2117736725993273568237620
817 2199133036315896538161577
818 2283606437707957801345399
819 2371271347049827685492744
820 2462246365947294158501031
821 2556654431283459748024024
822 2654622971098343537502197
823 2756284065981954261925904
824 2861774616172963304227126
825 2971236514560798530878435
826 3084816825796659123666519
827 3202667971725957968919573
828 3324947923361045447119351
829 3451820399621489890808299
830 3583455073076940996253170
831 3720027782934643179054719
832 3861720755522934974912809
833 4008722832530608259835969
834 4161229707269843775085200
835 4319444169240605935972583
836 4483576357283818096727227
837 4653844021619340860886569
838 4830472795075947973781579
839 5013696473830913149705385
840 5203757307986479839800175
841 5400906302322757524116506
842 5605403527578094048639491
843 5817518442618679165398357
844 6037530227872628921629979
845 6265728130416490334697124
846 6502411821113978606675926
847 6747891764221594807998625
848 7002489599889758855017775
849 7266538540001271448650765
850 7540383777805203286372524
851 7824382911819755307338480
852 8118906384492226847994123
853 8424337936122128312941178
854 8741075074570507426263508
855 9069529561294729683712857
856 9410127914267611824100156
857 9763311928358610070149139
858 10129539213772643714096032
859 10509283753163769628528940
860 10903036478061625266808599
861 11311305865268375201482170
862 11734618553907647997811368
863 12173519983829795138005770
864 12628575056099709983617895
865 13100368816319572565103394
866 13589507161564035115505910
867 14096617571729638321388725
868 14622349866128908086227819
869 15167376986187357555597107
870 15732395805128407499401174
871 16318127965562783358627620
872 16925320745929510667882256
873 17554747956765284058025625
874 18207210867813608203224808
875 18883539167018833934884564
876 19584591952482926913108927
877 20311258758500918121840780
878 21064460616828064650815987
879 21845151154367972182048277
880 22654317728512731014477450
881 23492982601407034979739577
882 24362204154448193820638848
883 25263078144379940130970463
884 26196739002382939183338665
885 27164361177609076694259371
886 28167160526657057530639240
887 29206395750536500408868779
888 30283369880716368311790796
889 31399431815909118859235371
890 32555977911296525052676657
891 33754453621956913523201538
892 34996355202314499302285472
893 36283231463491653919521038
894 37616685590504218246418107
895 38998377021306996143411056
896 40430023389762695111760665
897 41913402534673063102500538
898 43450354577084491288657341
899 45042784068153252794194853
900 46692662209927648087432857
901 48402029151485196212461985
902 50172996362943140860705300
903 52007749089940119028161578
904 53908548891275586268827868
905 55877736262481852416402096
906 57917733348191195525028254
907 60031046746258118085856348
908 62220270406693779495467796
909 64488088628566327814807420
910 66837279158127914240701381
911 69270716391535963412312576
912 71791374685642700183682826
913 74402331780444599809543908
914 77106772336900800952516915
915 79907991593946846399003873
916 82809399148659233660964571
917 85814522863655449912619343
918 88927012905943252090915920
919 92150645921574867355253768
920 95489329350603721642664398
921 98947105886983553946713687
922 102528158088205502395695089
923 106236813139624874057431534
924 110077547778585837443084510
925 114054993383623332647118953
926 118173941234193036979132901
927 122439347946552605600339642
928 126856341091605089732639631
929 131430225000704101089210847
930 136166486765609881372239701
931 141070802438991560279000670
932 146149043442078156634789653
933 151407283186269528136472329
934 156851803915744687092442827
935 162489103778332709863397884
936 168325904132140934873410266
937 174369157095683503333348683
938 180626053349503510321535114
939 187104030197534498527075532
940 193810779896719523779809385
941 200754258263680958980447506
942 207942693567511786391917672
943 215384595718058185104365103
944 223088765759365209626360724
945 231064305678262562754675647
946 239320628538395591031750709
947 247867468950338354099476255
948 256714893888761056046677013
949 265873313867984211262566505
950 275353494487616159091937220
951 285166568360339221801294065
952 295324047434304876124209185
953 305837835722998199811642916
954 316720242455837054576877009
955 327983995663204815542552466
956 339642256210054526934371479
957 351708632292667538658733414
958 364197194413625030508181525
959 377122490850532807647221586
960 390499563634528804736563564
961 404343965055124070253360472
962 418671774708457089676089182
963 433499617106578351761956842
964 448844679865953940225359385
965 464724732493957461852940556
966 481158145792709502857701101
967 498163911900250837666448131
968 515761664989672722106105558
969 533971702647475208562962480
970 552815007953112072954363852
971 572313272282379831281017826
972 592488918858019454504624683
973 613365127071653136698535326
974 634965857601945397838720900
975 657315878354658175430733364
976 680440791251096084467201345
977 704367059892279104336744300
978 729122038127036563068534791
979 754733999553122164950518057
980 781232167981372460366174240
981 808646748893870934790760122
982 837008961928073071671240212
983 866351074419859260522151123
984 896706436039513837877283075
985 928109514555716748525763908
986 960595932763743730384145670
987 994202506615202153081343582
988 1028967284587822389534888774
989 1064929588335040720887292042
990 1102130054656350803615337880
991 1140610678830707423278798570
992 1180414859356599746633535172
993 1221587444143771947023160465
994 1264174778203001163542500880
995 1308224752881804004215181715
996 1353786856695435210662043470
997 1400912227804110671554220457
998 1449653708188988781257795975
999 1500065899581080101714372446
1000 1552205221198973871536503349