0 1
1 1
2 2
3 2
4 4
5 5
6 7
7 9
8 13
9 16
10 22
11 27
12 36
13 44
14 57
15 70
16 89
17 108
18 135
19 163
20 202
21 243
22 297
23 355
24 431
25 513
26 617
27 731
28 874
29 1031
30 1225
31 1439
32 1701
33 1991
34 2341
35 2731
36 3197
37 3717
38 4333
39 5022
40 5834
41 6741
42 7803
43 8991
44 10375
45 11923
46 13716
47 15723
48 18038
49 20628
50 23603
51 26930
52 30739
53 34996
54 39852
55 45278
56 51449
57 58338
58 66150
59 74866
60 84726
61 95716
62 108117
63 121930
64 137483
65 154791
66 174236
67 195858
68 220104
69 247039
70 277187
71 310649
72 348039
73 389501
74 435753
75 486999
76 544077
77 607261
78 677531
79 755251
80 841570
81 936954
82 1042749
83 1159556
84 1288951
85 1431692
86 1589620
87 1763694
88 1956069
89 2167934
90 2401812
91 2659177
92 2942982
93 3255037
94 3598795
95 3976479
96 4392124
97 4848435
98 5350131
99 5900499
100 6505055
101 7167766
102 7895078
103 8691778
104 9565393
105 10521670
106 11569392
107 12715452
108 13970099
109 15341562
110 16841795
111 18480609
112 20271942
113 22227453
114 24363381
115 26693569
116 29236923
117 32009832
118 35034298
119 38329700
120 41921631
121 45832942
122 50093388
123 54729891
124 59777020
125 65266425
126 71238240
127 77729635
128 84787182
129 92454446
130 100785438
131 109831162
132 119654217
133 130314223
134 141883681
135 154432213
136 168043734
137 182799423
138 198796349
139 216129070
140 234909803
141 255248534
142 277274907
143 301116744
144 326923722
145 354844205
146 385050883
147 417715812
148 453038113
149 491217080
150 532482167
151 577064015
152 625226864
153 677237355
154 733399591
155 794021576
156 859453063
157 930049488
158 1006212861
159 1088353017
160 1176931746
161 1272421166
162 1375351407
163 1486265922
164 1605772917
165 1734497415
166 1873136762
167 2022409260
168 2183113987
169 2356075756
170 2542209668
171 2742462155
172 2957880564
173 3189550041
174 3438668572
175 3706479486
176 3994352266
177 4303710423
178 4636118591
179 4993205472
180 5376757633
181 5788637217
182 6230883042
183 6705622778
184 7215181789
185 7761989488
186 8348696568
187 8978075235
188 9653145364
189 10377068258
190 11153282509
191 11985390923
192 12877306749
193 13833133398
194 14857321896
195 15954543061
196 17129856904
197 18388576908
198 19736452375
199 21179524409
200 22724322109
201 24377709834
202 26147098430
203 28040283383
204 30065672070
205 32232112434
206 34549137572
207 37026784557
208 39675857562
209 42507736397
210 45534659753
211 48769523028
212 52226183133
213 55919245219
214 59864390793
215 64078153011
216 68578269743
217 73383447096
218 78513739492
219 83990301057
220 89835794712
221 96074131077
222 102730909014
223 109833141772
224 117409731259
225 125491181216
226 134110108000
227 143300940647
228 153100470870
229 163547539847
230 174683630754
231 186552542205
232 199201026555
233 212678450014
234 227037480524
235 242333734716
236 258626519123
237 275978464263
238 294456323665
239 314130595419
240 335076383556
241 357373007559
242 381104931393
243 406361361683
244 433237249674
245 461832879033
246 492254946875
247 524616142383
248 559036313200
249 595642036205
250 634567876615
251 675955952577
252 719957294504
253 766731405491
254 816447729433
255 869285209745
256 925433875089
257 985094399268
258 1048479814710
259 1115815076810
260 1187338915777
261 1263303409225
262 1343975984442
263 1429639003683
264 1520591929364
265 1617150927241
266 1719651208716
267 1828446657840
268 1943912365669
269 2066444287780
270 2196461987595
271 2334408332059
272 2480752461789
273 2635989533640
274 2800643937642
275 2975269096445
276 3160450950226
277 3356807824278
278 3564994205664
279 3785700691593
280 4019658083209
281 4267637428972
282 4530454463952
283 4808969764317
284 5104093562262
285 5416786029762
286 5748062502763
287 6098993914581
288 6470712465388
289 6864412227931
290 7281355302529
291 7722872620506
292 8190370627821
293 8685332314664
294 9209324475461
295 9763998996500
296 10351100743686
297 10972469143701
298 11630046756502
299 12325881189455
300 13062134416108
301 13841085067199
302 14665138563762
303 15536829833926
304 16458834333708
305 17433971244009
306 18465215460176
307 19555701329637
308 20708735697950
309 21927802253942
310 23216575729179
311 24578926924810
312 26018938169361
313 27540909109520
314 29149373541767
315 30849106058307
316 32645140377724
317 34542776946933
318 36547602908823
319 38665500771618
320 40902670163304
321 43265637691504
322 45761280649488
323 48396838202636
324 51179937224780
325 54118604961612
326 57221297193852
327 60496912543507
328 63954823177467
329 67604890939362
330 71457500828340
331 75523579158024
332 79814630065689
333 84342755920383
334 89120697142410
335 94161855105391
336 99480335570546
337 105090974352063
338 111009384700259
339 117251986026533
340 123836055599061
341 130779760653202
342 138102214798332
343 145823513872158
344 153964797492335
345 162548289048762
346 171597362875118
347 181136588812101
348 191191805516257
349 201790170069444
350 212960237991601
351 224732018418309
352 237137061434514
353 250208519393034
354 263981242244214
355 278491845624101
356 293778814915165
357 309882580793667
358 326845632825620
359 344712603229191
360 363530390881986
361 383348254126914
362 404217946148580
363 426193817730590
364 449332965043974
365 473695343350714
366 499343928343938
367 526344841887156
368 554767528147677
369 584684892564003
370 616173494128802
371 649313698889726
372 684189889859052
373 720890636476265
374 759508923756967
375 800142339279978
376 842893323331697
377 887869375126745
378 935183325864722
379 984953566052729
380 1037304343562117
381 1092366014095170
382 1150275366519417
383 1211175898710512
384 1275218172643608
385 1342560118051205
386 1413367419975822
387 1487813852906703
388 1566081703737829
389 1648362139292124
390 1734855667894737
391 1825772543460487
392 1921333269176199
393 2021769041617845
394 2127322300349305
395 2238247215852471
396 2354810289185788
397 2477290887854910
398 2605981900045266
399 2741190322935404
400 2883237976415501
401 3032462148753245
402 3189216375147868
403 3353871146102199
404 3526814756631194
405 3708454083176455
406 3899215509804648
407 4099545780025410
408 4309913006870112
409 4530807606544003
410 4762743399885042
411 5006258635401187
412 5261917190264064
413 5530309690956214
414 5812054822671806
415 6107800556531196
416 6418225577033761
417 6744040625592423
418 7085990056529592
419 7444853307548109
420 7821446595672691
421 8216624526212115
422 8631281941044444
423 9066355678644662
424 9522826588185003
425 10001721454308841
426 10504115191689707
427 11031132949433361
428 11583952502003271
429 12163806549435843
430 12771985321919414
431 13409839093422330
432 14078781018700020
433 14780289879470591
434 15515913174245357
435 16287270117852132
436 17096055006234167
437 17944040491927308
438 18833081247877617
439 19765117543436874
440 20742179233306055
441 21766389660737424
442 22839969999948669
443 23965243515522775
444 25144640289053022
445 26380701866228104
446 27676086401095065
447 29033573725022553
448 30456070944805422
449 31946617970629974
450 33508393607326509
451 35144721581637106
452 36859077169250634
453 38655093765114979
454 40536570092502950
455 42507477363838959
456 44571967121947648
457 46734379042901895
458 48999249463842774
459 51371319883726944
460 53855546236682210
461 56457108151265610
462 59181419033281827
463 62034136149287755
464 65021171588160322
465 68148703240130081
466 71423186712196248
467 74851367279974641
468 78440292838333692
469 82197326909836928
470 86130162718775059
471 90246837347011379
472 94555747026929106
473 99065662543091106
474 103785745847576164
475 108725566814089012
476 113895121287749040
477 119304849307180646
478 124965654710118751
479 130888924948627087
480 137086552381926969
481 143570955820290246
482 150355103647365936
483 157452537239537535
484 164877396071754148
485 172644443171294656
486 180769092373803726
487 189267435983539746
488 198156274360018150
489 207453145971012865
490 217176359505028399
491 227345026518661248
492 237979096286115267
493 249099391259098886
494 260727644881887928
495 272886540099833866
496 285599750387136787
497 298891981559371977
498 312789016281301056
499 327317759459701758
500 342506286520303014
501 358383892679747370
502 374981145304241924
503 392329937383824776
504 410463544310680914
505 429416681905162242
506 449225567979105551
507 469927985291420724
508 491563348291288692
509 514172771411745168
510 537799141419532747
511 562487191488144890
512 588283579615502583
513 615236968953571194
514 643398112792158921
515 672819941660680116
516 703557655416404235
517 735668817675428358
518 769213455586903417
519 804254162195029736
520 840856204527355849
521 879087634537875774
522 919019406187732599
523 960725495671544708
524 1004283028222991604
525 1049772408382617388
526 1097277457319172864
527 1146885553957649643
528 1198687783670181893
529 1252779091148287170
530 1309258441384982518
531 1368228985245511697
532 1429798233735432828
533 1494078237299880851
534 1561185774451182456
535 1631242545908354218
536 1704375378742683303
537 1780716436557139665
538 1860403440399836031
539 1943579896277817712
540 2030395334186833054
541 2121005554356072861
542 2215572885848823552
543 2314266453044713611
544 2417262455380110929
545 2524744455692889285
546 2636903682794536589
547 2753939343430017999
548 2876058949506093067
549 3003478655556207771
550 3136423612592237562
551 3275128333112227110
552 3419837073696391659
553 3570804229754728376
554 3728294749153491740
555 3892584559071072913
556 4063961013119142481
557 4242723352859641122
558 4429183191076352120
559 4623665010704345456
560 4826506687113858192
561 5038060027417133317
562 5258691334848290058
563 5488781991642323343
564 5728729068833243661
565 5978945956147256998
566 6239863020798157424
567 6511928288102684595
568 6795608153128239348
569 7091388116024502263
570 7399773550675513591
571 7721290499049324459
572 8056486501325813232
573 8405931453897024583
574 8770218505785503410
575 9149964985283769027
576 9545813367847144056
577 9958432276743343757
578 10388517528000728205
579 10836793210850229175
580 11304012815736628321
581 11790960400777106844
582 12298451809301803053
583 12827335929028415011
584 13378496006091187692
585 13952851004141647713
586 14551357022354898520
587 15175008762215316921
588 15824841057558208253
589 16501930457388928030
590 17207396876629525735
591 17942405303953259361
592 18708167582562844854
593 19505944252702899162
594 20337046472502199825
595 21202838005557649282
596 22104737292631002210
597 23044219595483154075
598 24022819231029990332
599 25042131883449095940
600 26103817013273703036
601 27209600350699504742
602 28361276493034564942
603 29560711593106306204
604 30809846159493273711
605 32110697954976377553
606 33465365015060658807
607 34876028772535667706
608 36344957310957119647
609 37874508732584413166
610 39467134664739103859
611 41125383889678938334
612 42851906123088447954
613 44649455925834833823
614 46520896775282345363
615 48469205280362686085
616 50497475567946122969
617 52608923824255052112
618 54806893020178596551
619 57094857803770351254
620 59476429590167510739
621 61955361831750924069
622 64535555500233256206
623 67221064763030228134
624 70016102887124060089
625 72925048352308670732
626 75952451208624638886
627 79103039659408377711
628 82381726906443512621
629 85793618238175528601
630 89344018399243180417
631 93038439221827498342
632 96882607558927565334
633 100882473499608524424
634 105044218908281787573
635 109374266267614155046
636 113879287869176941326
637 118566215330991749163
638 123442249488240974994
639 128514870635870429836
640 133791849171620868536
641 139281256617799822637
642 144991477072717165296
643 150931219069695651220
644 157109527897090980804
645 163535798356851260959
646 170219788017692969188
647 177171630940063777131
648 184401851931750700935
649 191921381310969754415
650 199741570238723552766
651 207874206596957848313
652 216331531477386316732
653 225126256257242489079
654 234271580330074672404
655 243781209467608116897
656 253669374884209733446
657 263950852979787285582
658 274640985836260610175
659 285755702443291870191
660 297311540732207880821
661 309325670393709697559
662 321815916562302304398
663 334800784343006901265
664 348299484267504466748
665 362331958655306212119
666 376918908971543926247
667 392081824157081808852
668 407843010027228803099
669 424225619714939659416
670 441253685259725456556
671 458952150318437345629
672 477346904104356515979
673 496464816531127666437
674 516333774673467569228
675 536982720521667149099
676 558441690147620280180
677 580741854259997048017
678 603915560272417068702
679 627996375862969324806
680 653019134155396108051
681 679019980501157881536
682 706036420999518243687
683 734107372735890821067
684 763273215882789656690
685 793575847644818813090
686 825058738199648437079
687 857766988617790872060
688 891747390921156932688
689 927048490264784198039
690 963720649410202869168
691 1001816115476627186054
692 1041389089147402868601
693 1082495796319931571461
694 1125194562385975806895
695 1169545889132855379405
696 1215612534462450186967
697 1263459594921089447979
698 1313154591247824253717
699 1364767556937034777706
700 1418371130034055958949
701 1474040648162971743768
702 1531854247017089837036
703 1591892962314800138757
704 1654240835463836747274
705 1718985022940583181478
706 1786215909640669409180
707 1856027226211851106422
708 1928516170639412741490
709 2003783534099883345726
710 2081933831368110116327
711 2163075435798760341585
712 2247320719182959989992
713 2334786196506942599118
714 2425592675929991796666
715 2519865414014916573467
716 2617734276545884811450
717 2719333904973825972744
718 2824803888842796653781
719 2934288944245144811183
720 3047939098678523111555
721 3165909882360915600135
722 3288362526397539844056
723 3415464167864874284797
724 3547388062227710142145
725 3684313803164378000139
726 3826427550239386017205
727 3973922264509396593562
728 4126997952526496057780
729 4285861918836403213949
730 4450729027461753541843
731 4621821972480836500626
732 4799371558219659415998
733 4983616989181535076018
734 5174806170261453110910
735 5373196017384420410429
736 5579052779146168554166
737 5792652369611656298280
738 6014280712882762047834
739 6244234099608183616450
740 6482819556081910686699
741 6730355226122321398625
742 6987170766415334113224
743 7253607755534249585033
744 7530020117359004564471
745 7816774559129717832701
746 8114251024898901267750
747 8422843164641244239544
748 8742958819829502954048
749 9075020525761339847313
750 9419466031492466079412
751 9776748837688914828934
752 10147338753303446891210
753 10531722471419090509515
754 10930404165217467308029
755 11343906104447427412698
756 11772769293407483697240
757 12217554130852602384165
758 12678841092898063121400
759 13157231439368669691944
760 13653347944728842505423
761 14167835654082476709163
762 14701362665444732751948
763 15254620938818325871127
764 15828327133347171359439
765 16423223473126929639854
766 17040078643020303817494
767 17679688715107135048311
768 18342878107196717128012
769 19030500574086645066024
770 19743440233080044509286
771 20482612624503794419839
772 21248965808829173519874
773 22043481501200146437739
774 22867176245065782139242
775 23721102625789225545237
776 24606350526030595572456
777 25524048423848352266176
778 26475364735423566860213
779 27461509203429011591627
780 28483734333061127500002
781 29543336876839771568898
782 30641659370314397350479
783 31780091719870546266461
784 32960072844903304195212
785 34183092375646973909131
786 35450692409063482963873
787 36764469324180980695476
788 38126075659429361984438
789 39537222053473664964225
790 40999679252245170364032
791 42515280183788423714727
792 44085922103786521192776
793 45713568813508457238492
794 47400252953213396128258
795 49148078372890100999199
796 50959222583549533768224
797 52835939291092745180817
798 54780561016166509641544
799 56795501802182789687454
800 58883260015120916893685
801 61046421237453290087554
802 63287661260032645096197
803 65609749174457876344803
804 68015550569989157661877
805 70508030837717744756884
806 73090258586308264841784
807 75765409172220308020686
808 78536768348989440185896
809 81407736038689773624513
810 84381830230436731742281
811 87462691009282268776520
812 90654084720656904602592
813 93959908273956735713061
814 97384193590743779810797
815 100931112201420524574428
816 104604979996180441369026
817 108410262134375953154061
818 112351578118459628864359
819 116433707036939790490501
820 120661592982882201019348
821 125040350652719038408449
822 129575271132295958772765
823 134271827875260116603397
824 139135682881143757385226
825 144172693078610962597297
826 149388916921672178262780
827 154790621204723362499386
828 160384288104692222857398
829 166176622456563766124951
830 172174559271075014528124
831 178385271501294317654557
832 184816178067413865837231
833 191474952146943654708575
834 198369529740207564168229
835 205508118518834141737557
836 212899206967750172412216
837 220551573828907511300187
838 228474297857896222934988
839 236676767902248088057576
840 245168693313268341444156
841 253960114700811271521970
842 263061415043564679456084
843 272483331164910813036798
844 282236965587700828095006
845 292333798778705373266735
846 302785701796898092460502
847 313604949357075358297314
848 324804233323839393430880
849 336396676648237459512921
850 348395847763008367437368
851 360815775449570096163660
852 373670964193680907466402
853 386976410043803876916288
854 400747616990148902967908
855 415000613879376759864252
856 429751971884045188468828
857 445018822542798451813143
858 460818876391554482235342
859 477170442202774054711695
860 494092446854312628801419
861 511604455846092622673209
862 529726694487420095976339
863 548480069774411685540331
864 567886192981760628739645
865 587967402989615254725969
866 608746790371290150174678
867 630248222263975363851237
868 652496368049747034289605
869 675516725870526536317430
870 699335650005972126479109
871 723980379139527285228095
872 749479065543393701263614
873 775860805209331537391329
874 803155668957948569075586
875 831394734555166948721732
876 860610119870539204848317
877 890835017108002735569227
878 922103728145877891055086
879 954451701018720933146289
880 987915567580101442654128
881 1022533182381066578832124
882 1058343662805765203535822
883 1095387430501282503211262
884 1133706254145708984835273
885 1173343293593928333808956
886 1214343145447855258946625
887 1256751890093196323583498
888 1300617140252338024560025
889 1345988091098187864192717
890 1392915571981621773700743
891 1441452099820290772764193
892 1491651934204675956922935
893 1543571134272257005122228
894 1597267617409116985009354
895 1652801219833157549125767
896 1710233759121890931712022
897 1769629098742500449786535
898 1831053214651002207625996
899 1894574264021938875010874
900 1960262656179540655894605
901 2028191125795758662855364
902 2098434808430458634959762
903 2171071318483404178973174
904 2246180829637935823058934
905 2323846157870463958310395
906 2404152847110581868379923
907 2487189257630686978881939
908 2573046657255114981569970
909 2661819315472743387809978
910 2753604600548584159757988
911 2848503079723706999214953
912 2946618622604863539923823
913 3048058507838874981185818
914 3152933533179359808150933
915 3261358129046941512357120
916 3373450475697096557288779
917 3489332624103238007283324
918 3609130620676178530982376
919 3732974635934424837960468
920 3860999097253854604070120
921 3993342825818510100390987
922 4130149177908916236685467
923 4271566190657390738566236
924 4417746732415087073880548
925 4568848657868450071462608
926 4725034968058662532794692
927 4886473975450482721428864
928 5053339474213423713119064
929 5225810915870932873560358
930 5404073590490462127341989
931 5588318813579916652205153
932 5778744118873913229505326
933 5975553457185770713611197
934 6178957401519841190732523
935 6389173358631181097274757
936 6606425787239022978944124
937 6830946423092804626815597
938 7062974511109783388188258
939 7302757044795471478722069
940 7550549013179244816262566
941 7806613655489605304061834
942 8071222723815576514828266
943 8344656753992767760955895
944 8627205344975564391352310
945 8919167446948893970118958
946 9220851658456905074163526
947 9532576532817834166952748
948 9854670894119230701440349
949 10187474163079607396255367
950 10531336693088530417975604
951 10886620116729031343335575
952 11253697703113271335744814
953 11632954726354238934367270
954 12024788845524462175759840
955 12429610496444565303252707
956 12847843295673902822119833
957 13279924457067367879508124
958 13726305221293132605379412
959 14187451298697974529932454
960 14663843325938819664340578
961 15155977336791080701522446
962 15664365247577721561430317
963 16189535357654999562319743
964 16732032865425629015692914
965 17292420400342224861673138
966 17871278571400183799320505
967 18469206532611394418477655
968 19086822565988042856281801
969 19724764682558160281918520
970 20383691241974083018061769
971 21064281591267550268241930
972 21767236723346415355068111
973 22493279955820705868578195
974 23243157630788826252282179
975 24017639836207694585767657
976 24817521149515555425012762
977 25643621404169483545535679
978 26496786479806524517819018
979 27377889116731004576561013
980 28287829755479547768563442
981 29227537402209280201369729
982 30197970520705879312479408
983 31200117951802468128551991
984 32234999861053808216409328
985 33303668715505035550801313
986 34407210290450021130949745
987 35546744707069729001570298
988 36723427501899279508669548
989 37938450729068272365888357
990 39193044096319876278419637
991 40488476135810654191758201
992 41826055410756787868563032
993 43207131758989507332988320
994 44633097574549099644013290
995 46105389128444761306990040
996 47625487929777140351399846
997 49194922128419125299545649
998 50815267960523178314984148
999 52488151238123120843036433
1000 54215248884174331424690571