0 1
1 1
2 1
3 2
4 3
5 5
6 6
7 10
8 14
9 19
10 26
11 37
12 49
13 66
14 87
15 116
16 152
17 198
18 254
19 329
20 422
21 536
22 678
23 858
24 1077
25 1349
26 1681
27 2089
28 2587
29 3193
30 3927
31 4820
32 5897
33 7191
34 8749
35 10623
36 12861
37 15535
38 18724
39 22518
40 27029
41 32373
42 38697
43 46174
44 54998
45 65382
46 77601
47 91950
48 108777
49 128476
50 151522
51 178425
52 209816
53 246369
54 288904
55 338329
56 395710
57 462206
58 539240
59 628339
60 731317
61 850166
62 987255
63 1145155
64 1326929
65 1535902
66 1775995
67 2051523
68 2367520
69 2729484
70 3143897
71 3617820
72 4159474
73 4777898
74 5483580
75 6288013
76 7204520
77 8247705
78 9434419
79 10783218
80 12315392
81 14054331
82 16026930
83 18262735
84 20795496
85 23662419
86 26905902
87 30572619
88 34715704
89 39393641
90 44672805
91 50626380
92 57337171
93 64896412
94 73407286
95 82983458
96 93753055
97 105857390
98 119455486
99 134722586
100 151855665
101 171071740
102 192614259
103 216751597
104 243784223
105 274043190
106 307898836
107 345759082
108 388079381
109 435361509
110 488164989
111 547105894
112 612870493
113 686214183
114 767977260
115 859084649
116 960563878
117 1073545412
118 1199284101
119 1339159958
120 1494702886
121 1667595112
122 1859699714
123 2073064260
124 2309954466
125 2572859432
126 2864530655
127 3187990115
128 3546575210
129 3943949650
130 4384156565
131 4871632518
132 5411269006
133 6008431807
134 6669032179
135 7399551491
136 8207124819
137 9099572079
138 10085495196
139 11174318267
140 12376400115
141 13703084449
142 15166832110
143 16781282827
144 18561408765
145 20523592321
146 22685804459
147 25067700008
148 27690826490
149 30578740381
150 33757250164
151 37254559384
152 41101549004
153 45331951078
154 49982679230
155 55094038209
156 60710108246
157 66879000036
158 73653301822
159 81090385802
160 89252930490
161 98209288142
162 108034092843
163 118808702611
164 130621906374
165 143570452386
166 157759873618
167 173305117195
168 190331504550
169 208975483588
170 229385745494
171 251724118069
172 276166867704
173 302905758830
174 332149568239
175 364125343001
176 399080160495
177 437282616373
178 479024874478
179 524624423202
180 574426457839
181 628805956244
182 688170446773
183 752962452946
184 823662712736
185 900793054492
186 984920135761
187 1076658827277
188 1176676552679
189 1285697261031
190 1404506468815
191 1533955916953
192 1674969420406
193 1828548329080
194 1995778311853
195 2177835746717
196 2375995591726
197 2591638855404
198 2826261719558
199 3081484270618
200 3359061068027
201 3660891333855
202 3989031199622
203 4345705585708
204 4733322378957
205 5154486279844
206 5612015208726
207 6108956424017
208 6648605508087
209 7234525113854
210 7870566918979
211 8560893421290
212 9310003313051
213 10122756793409
214 11004404894489
215 11960618854721
216 12997523986765
217 14121733751174
218 15340388853172
219 16661196728473
220 18092476668194
221 19643205545442
222 21323069864816
223 23142518692532
224 25112823665024
225 27246140205990
226 29555576696720
227 32055265229637
228 34760441290152
229 37687525497407
230 40854215355809
231 44279579615000
232 47984163888890
233 51990099518045
234 56321225085313
235 61003211951394
236 66063703997282
237 71532462287645
238 77441525725499
239 83825377659993
240 90721130484688
241 98168717433476
242 106211104600929
243 114894511592409
244 124268654956416
245 134387001893870
246 145307049619288
247 157090616949071
248 169804164756674
249 183519130900361
250 198312297689904
251 214266176395010
252 231469428419187
253 250017306534806
254 270012137413577
255 291563827678372
256 314790416527180
257 339818655840359
258 366784642795386
259 395834484574054
260 427125022247719
261 460824592034149
262 497113853319855
263 536186660078676
264 578251007597041
265 623530029573021
266 672263080128527
267 724706874160015
268 781136723512947
269 841847840579937
270 907156750010884
271 977402778304736
272 1052949665343874
273 1134187265737315
274 1221533387790688
275 1315435735858215
276 1416374007990435
277 1524862112538197
278 1641450559945511
279 1766728991216055
280 1901328904101858
281 2045926536110443
282 2201245970619447
283 2368062422833867
284 2547205777435739
285 2739564332242824
286 2946088825898667
287 3167796701266020
288 3405776689281693
289 3661193662372320
290 3935293849351964
291 4229410358284178
292 4544969107185769
293 4883495106233616
294 5246619200023203
295 5636085210838744
296 6053757600753128
297 6501629590833573
298 6981831865538496
299 7496641797713725
300 8048493333493788
301 8639987469867885
302 9273903476236909
303 9953210790160119
304 10681081751937886
305 11460905105570476
306 12296300445287462
307 13191133532871654
308 14149532680631446
309 15175906123164204
310 16274960590087775
311 17451721000810549
312 18711551512480318
313 20060177840672795
314 21503711104413773
315 23048673114016735
316 24702023375966404
317 26471187732482433
318 28364088934776703
319 30389179067638253
320 32555474151199651
321 34872590838278842
322 37350785562823883
323 40000996059150018
324 42834885640043870
325 45864890156031648
326 49104268059204517
327 52567153497718484
328 56268612903431347
329 60224705003657900
330 64452544762382171
331 68970371188701976
332 73797619564523548
333 78954998037997837
334 84464569186320355
335 90349836504858475
336 96635836482947414
337 103349236236666577
338 110518437420802911
339 118173686406555966
340 126347191515626901
341 135073247316335231
342 144388366847669047
343 154331421800167180
344 164943791601840546
345 176269521465640718
346 188355490437695055
347 201251589534797712
348 215010911110600697
349 229689949577026270
350 245348814730119521
351 262051457851254872
352 279865911954369252
353 298864546401145091
354 319124337388636116
355 340727154590917938
356 363760065606111624
357 388315658559291831
358 414492384675090959
359 442394921249174095
360 472134557011589332
361 503829600402182574
362 537605812947976679
363 573596868367001951
364 611944839806377705
365 652800715957640487
366 696324948697563245
367 742688033133418864
368 792071122965514279
369 844666682200876902
370 900679176423720743
371 960325804831891601
372 1023837276568254580
373 1091458632756155876
374 1163450118124038369
375 1240088103855082299
376 1321666065941138584
377 1408495620932664580
378 1500907623799372964
379 1599253330083585973
380 1703905627541085292
381 1815260339779477474
382 1933737607620245985
383 2059783351063621593
384 2193870818169713521
385 2336502224152260998
386 2488210487646310178
387 2649561067916161840
388 2821153910682070764
389 3003625506859772360
390 3197651072684087121
391 3403946856105209793
392 3623272578804063575
393 3856434019383378063
394 4104285748049532564
395 4367734019090452651
396 4647739832535634944
397 4945322172144776240
398 5261561432293810668
399 5597603041847897894
400 5954661298899304613
401 6334023425514799500
402 6737053857818081700
403 7165198781734601530
404 7619990931323399412
405 8103054661346867178
406 8616111312772790081
407 9160984884338006821
408 9739608030825086324
409 10354028402835476212
410 11006415350872761376
411 11699067010367356625
412 12434417792848966863
413 13215046301959519363
414 14043683702158663228
415 14923222561116833077
416 15856726196571526389
417 16847438551210042427
418 17898794629588782711
419 19014431523513718286
420 20198200063468470766
421 21454177125705591648
422 22786678636539302788
423 24200273307010069528
424 25699797143830466465
425 27290368773738806698
426 28977405632002446074
427 30766641056602993517
428 32664142344184960919
429 34676329814202355214
430 36809996943249432994
431 39072331621460011693
432 41470938599488229159
433 44013863184017179982
434 46709616257519008249
435 49567200686950612540
436 52596139205080181113
437 55806503836611950294
438 59208946961613634450
439 62814734096728344191
440 66635778496406416250
441 70684677663870953158
442 74974751884806979830
443 79520084883732101893
444 84335566727920089704
445 89436939090205785647
446 94840843008664526455
447 100564869267107942382
448 106627611548886665607
449 113048722501926348103
450 119848972883499358121
451 127050313938166140624
452 134675943195067563068
453 142750373855190230819
454 151299507974311451750
455 160350713631286817024
456 169932906308945561268
457 180076634698353193225
458 190814171177502753724
459 202179607198557616756
460 214208953860979399871
461 226940247930526633170
462 240413663610455716413
463 254671630353541111082
464 269758957053244426871
465 285722962934333123582
466 302613615516592647925
467 320483676006980554177
468 339388852532830881453
469 359387961610227548699
470 380543098303136358498
471 402919815510286793170
472 426587312882810726039
473 451618635857021388514
474 478090885357639181008
475 506085438708235384402
476 535688182361871408800
477 566989757046595801353
478 600085816002374834142
479 635077296968071024137
480 672070708665165074841
481 711178432507480743632
482 752519040360901242594
483 796217629160351919707
484 842406173293240841396
485 891223895642761228420
486 942817658294150508886
487 997342373892391063998
488 1054961438757918434332
489 1115847188853756921359
490 1180181379824661690727
491 1248155692317465661063
492 1319972263928816137419
493 1395844249117232078721
494 1475996408564017235120
495 1560665729460845136224
496 1650102078360935309520
497 1744568888226989871935
498 1844343881480620312559
499 1949719830857724655129
500 2061005360059309637596
501 2178525786191037461523
502 2302624006184414383292
503 2433661429400993148725
504 2572018958836431767020
505 2718098023355090077430
506 2872321663618457196360
507 3035135674390724373379
508 3207009806156021839176
509 3388439029008902207246
510 3579944862051028747614
511 3782076771562120976974
512 3995413641506445064845
513 4220565319980360554893
514 4458174245523395763561
515 4708917157269867625913
516 4973506893260781423956
517 5252694281301962553900
518 5547270127125028742707
519 5858067304687204625792
520 6185962953846978788560
521 6531880790746804263137
522 6896793536668002908936
523 7281725471233885535428
524 7687755116306834779683
525 8116018057054641631717
526 8567709907169999211398
527 9044089425377512957034
528 9546481790913456671926
529 10076282045837365233823
530 10634958712631321231180
531 11224057595742817611948
532 11845205776373746734023
533 12500115810047255986069
534 13190590137185144405654
535 13918525717190187341565
536 14685918897287684885045
537 15494870527678471424364
538 16347591335379681927247
539 17246407569467779443189
540 18193766931332196888008
541 19192244803930922506931
542 20244550795009091300824
543 21353535609674348225076
544 22522198268775058198720
545 23753693690015276769496
546 25051340649882573794619
547 26418630145013784133141
548 27859234172863698701002
549 29377014952158445773279
550 30976034604961668030652
551 32660565322873305799243
552 34435100041343003876883
553 36304363646854823958663
554 38273324743328222031682
555 40347208004946659755300
556 42531507144350766740835
557 44831998526100712647434
558 47254755457187473666447
559 49806163187452348885642
560 52492934654811821614010
561 55322127011388097688514
562 58301158968860599391936
563 61437829002693198363297
564 64740334457299922606895
565 68217291595701656183673
566 71877756639844447568374
567 75731247849405477253056
568 79787768689759735369985
569 84057832141618325236214
570 88552486207945654472362
571 93283340675801548196795
572 98262595194122206162233
573 103503068730713861349653
574 109018230475396697532808
575 114822232258739790319849
576 120929942559813801355918
577 127356982179158942583819
578 134119761657502690626135
579 141235520523826725840408
580 148722368461101934726194
581 156599328481398576356310
582 164886382207214697791668
583 173604517359609323697238
584 182775777559316735518057
585 192423314551151702464851
586 202571442968099738869560
587 213245697756048230320790
588 224472894386737161570808
589 236281191991539971958110
590 248700159555894736302625
591 261760845319753413401435
592 275495849537265875902596
593 289939400755028618140285
594 305127435776773521914262
595 321097683489105541857924
596 337889752732202368551464
597 355545224406802659432384
598 374107748018940211669785
599 393623142872040206512741
600 414139504127024959108944
601 435707313960051928535807
602 458379558059518954360251
603 482211847713841513733167
604 507262547754587594852944
605 533592910630405109100465
606 561267216901421644460602
607 590352922455718146775272
608 620920812764990908735805
609 653045164509611989331577
610 686803914920192101334732
611 722278839197130358569664
612 759555736388033576127997
613 798724624118673714282897
614 839879942593188781979262
615 883120768296555933885012
616 928551037854186727449420
617 976279782522499278618902
618 1026421373808086817775902
619 1079095780733945359911610
620 1134428839297104415725005
621 1192552534684857670855421
622 1253605296844976607349316
623 1317732310030339515676394
624 1385085836969104256426736
625 1455825558339002833882092
626 1530118928257764544831316
627 1608141546531746547364733
628 1690077548441254966016367
629 1776120012873976068803342
630 1866471389657581060079765
631 1961343946978632716156541
632 2060960239818093036778863
633 2165553600373211654758776
634 2275368651482585293526270
635 2390661844114388191237153
636 2511702020028963688555305
637 2638771000774247281097258
638 2772164204228231183190791
639 2912191289954402936819884
640 3059176834696782196267103
641 3213461039397749508210133
642 3375400469187941973764719
643 3545368827859348666688643
644 3723757768404684864079693
645 3910977741273750724370176
646 4107458882075808811395120
647 4313651940530932660766978
648 4530029252558552575186031
649 4757085757472203036213210
650 4995340062342306761747610
651 5245335555677088556923453
652 5507641572672764373435219
653 5782854614380562935948203
654 6071599623248134027695364
655 6374531317598196897683776
656 6692335587727008820879542
657 7025730956420218799363583
658 7375470106813981671680392
659 7742341480654746404152959
660 8127170950152954274248243
661 8530823566762919143854463
662 8954205390375503623359520
663 9398265402559766554261841
664 9863997507657714107500090
665 10352442625699490197116949
666 10864690881289104368147990
667 11401883892788855000091372
668 11965217166329466474201952
669 12555942599367195320867993
670 13175371098725524170194802
671 13824875318270910363081646
672 14505892521607448589581926
673 15219927575406326745813623
674 15968556079242032037179543
675 16753427638059151532385673
676 17576269283672174013434310
677 18438889051975296612421608
678 19343179722842241198978171
679 20291122729995393593066938
680 21284792248453140211044059
681 22326359467490471370622386
682 23418097057406345523384985
683 24562383838746752120636966
684 25761709663022200000483781
685 27018680514345616829091537
686 28336023841840512403183384
687 29716594133091119753051586
688 31163378739367119586972788
689 32679503963815043575893017
690 34268241424309565485188952
691 35933014703158294545990568
692 37677406296398490406762961
693 39505164875969008125253195
694 41420212878633043432635377
695 43426654436120494537953411
696 45528783661602560865329330
697 47731093308257006884274850
698 50038283816382297583444387
699 52455272766221745389284208
700 54987204754419369443730908
701 57639461712794179087669144
702 60417673688946153121576311
703 63327730109039649437275223
704 66375791544008194672003070
705 69568302001330349993164543
706 72912001765502355088974743
707 76413940811318608146070010
708 80081492815131490173087313
709 83922369790333869868078559
710 87944637374459734657934396
711 92156730796464137579030719
712 96567471553995240716172536
713 101186084831738969089177828
714 106022217693276342646408472
715 111085958080272031864049281
716 116387854654289392238591049
717 121938937518025949582815088
718 127750739854367139821974422
719 133835320523285355579716693
720 140205287658353107469931733
721 146873823306410048618490921
722 153854709155814996356941737
723 161162353400638815504833458
724 168811818790207729216796185
725 176818851915498256031957011
726 185199913786114736207601543
727 193972211753853157529649547
728 203153732841275711710239094
729 212763278536189776079253428
730 222820501115552829229478980
731 233345941565007278226395945
732 244361069163101562759625548
733 255888322802167659350713976
734 267951154120921004648703101
735 280574072527013494998366553
736 293782692191130132571624277
737 307603781097656629500774544
738 322065312240591423437696013
739 337196517057107391364014271
740 353027941195124971915255556
741 369591502715310231675720068
742 386920552832204161777479670
743 405049939303588273050443516
744 424016072581848837311896647
745 443856994845877062252000467
746 464612452037094825759031900
747 486323969028378312207121914
748 509034928060132342837159788
749 532790650583392918124492947
750 557638482655779828536451078
751 583627884042224985755875996
752 610810521178849077246563533
753 639240364164982130718201467
754 668973787955315048818754490
755 700069677931354768389270232
756 732589540038937050445579700
757 766597615686346108559289030
758 802161001605810590228385007
759 839349774889601095147036672
760 878237123420866779091634154
761 918899481928519763898834274
762 961416673905137949132995826
763 1005872059636803044470248132
764 1052352690604264178886941665
765 1100949470525603144706800697
766 1151757323321929766210378226
767 1204875368299330759318650072
768 1260407102852599496438924127
769 1318460593008953535556834195
770 1379148672143281086063075576
771 1442589148210203144177609286
772 1508905019852687668190326401
773 1578224701761852033430200693
774 1650682259678246947191341215
775 1726417655441064560563763149
776 1805577002508677210436145448
777 1888312832391415604492155987
778 1974784372455873243537313745
779 2065157835578990591392351172
780 2159606722150081018950317579
781 2258312134939512166469592624
782 2361463107374321084437377852
783 2469256945783308370891915445
784 2581899586197513275204411317
785 2699605966316094725972395575
786 2822600413272938844514972232
787 2951117047865444910213378977
788 3085400205934334867844132476
789 3225704877611635878695775044
790 3372297165183647529284424473
791 3525454760346360599358330351
792 3685467441662910674017735432
793 3852637593065848257649766588
794 4027280744281777894125865523
795 4209726134091867940023996901
796 4400317297379374237086777051
797 4599412676954245227004268641
798 4807386261185622062343886612
799 5024628248515189132525864805
800 5251545739968433246054642986
801 5488563460826491009912110919
802 5736124512668996209506464296
803 5994691157047722581296230424
804 6264745632102473524735744012
805 6546791003484121682838687566
806 6841352051005599361262638357
807 7148976192499489871792461659
808 7470234446421353209660209179
809 7805722434800522619891238839
810 8156061428205548011032715232
811 8521899434459204083862393831
812 8903912332908776873682807749
813 9302805056130638481545695185
814 9719312821024704255666938772
815 10154202411333665408751053821
816 10608273513704729802296785431
817 11082360109497389158793159031
818 11577331924630329641172765941
819 12094095939853397702313290286
820 12633597963927434370936661285
821 13196824272295159644710300080
822 13784803313931079264369389175
823 14398607489166937025561118432
824 15039355001402548949119707173
825 15708211785729245950359578393
826 16406393517615670695913765646
827 17135167704932613133153534539
828 17895855866726031436896440931
829 18689835802284657471750953888
830 19518543954191786875789602238
831 20383477869199245264242303923
832 21286198760916320088273284510
833 22228334178466868695645928809
834 23211580785435134106141501317
835 24237707253594211388729775438
836 25308557276091950190506844889
837 26426052704956517055278263962
838 27592196817979282824534691419
839 28809077720235283034009902300
840 30078871885712701769961461649
841 31403847844741762209077023603
842 32786370023141623572591748620
843 34228902739240467309141543926
844 35734014365170537057261834473
845 37304381659095532417612173675
846 38942794275294160603021933659
847 40652159459299849744844112272
848 42435506935584425004806101200
849 44295993995571942648743948683
850 46236910794079761728489241031
851 48261685862606278725680264856
852 50373891848220548112791102068
853 52577251487157203751107771860
854 54875643822582775124885432178
855 57273110676375572887208808551
856 59773863385153000445593662207
857 62382289811186318601352704915
858 65102961639265862475191467852
859 67940641971018342608078268819
860 70900293228634588861785183657
861 73987085380439747723175363119
862 77206404501231080811999524911
863 80563861680819939159838987938
864 84065302294746897467364722125
865 87716815651691203285769017649
866 91524745032670461928269144659
867 95495698137722591861698185266
868 99636557956382529937833928910
869 103954494078909669825875516416
870 108456974465891719866557258114
871 113151777694545274004870566225
872 118047005700756206626974730701
873 123151097036652713210489143230
874 128472840664283903877739774339
875 134021390306785980556813625687
876 139806279379259855637434580534
877 145837436522457247209124737849
878 152125201763280673775567280249
879 158680343327045000585714654083
880 165514075127428327599180500516
881 172638074961056673394475906167
882 180064503434724385677270949126
883 187806023654349105099620463791
884 195875821705900941513207741626
885 204287627959728891377637949934
886 213055739230938192822135402085
887 222195041829748878530658623975
888 231721035537093265698777617816
889 241649858542087115556723147650
890 251998313379440995431844278568
891 262783893906363588516443460052
892 274024813360052903001426132912
893 285740033538473148417764026388
894 297949295148780361999931145104
895 310673149369487313703395977133
896 323932990674254008821874807691
897 337751090967052897107750766773
898 352150635080394244261358844706
899 367155757690305710946549606587
900 382791581703847937581631252803
901 399084258177113573375737656043
902 416061007823908022671521369130
903 433750164177644980613899314324
904 452181218471416309535643658477
905 471384866303712793412515269892
906 491393056159887949668732346619
907 512239039862170268328318885960
908 533957425023848596775411259666
909 556584229586179865189450236651
910 580156938519607048942023644581
911 604714562774027251628351596504
912 630297700566124678491866560151
913 656948601095180221105151197965
914 684711230782298550877938195672
915 713631342131654307310265195061
916 743756545316161908949964519197
917 775136382593918133023456362364
918 807822405665864262825048740380
919 841868256089364866729632597272
920 877329748866815163240171321104
921 914264959332968193359911374596
922 952734313469429374198219531309
923 992800681779699392120005066672
924 1034529476863270257644731939640
925 1077988754832593852598461575013
926 1123249320722261684499891625622
927 1170384838045459233089592304978
928 1219471942658703293884779075070
929 1270590361102036774991369847494
930 1323823033588258435520129861243
931 1379256241821406050335726435025
932 1436979741831607336045402099274
933 1497086902020564995531326595119
934 1559674846619368321596151035665
935 1624844604768025633285606927014
936 1692701265434108351848773085671
937 1763354138396190854931812403424
938 1836916921526380457179000537123
939 1913507874615161501587427833117
940 1993249999991047888895941228079
941 2076271230197152466755958002605
942 2162704622996762103266025086643
943 2252688563990357570627671175857
944 2346366977137261478902589007429
945 2443889543486239615498985576084
946 2545411928430946522258557536949
947 2651096017818099823170158752429
948 2761110163248716597838355380349
949 2875629436925654541383774977773
950 2994835896414099291847542662004
951 3118918859695533489469870987059
952 3248075190910143130241186850001
953 3382509597197569795272057406725
954 3522434937061435502184806452726
955 3668072540699158378264448881368
956 3819652542755276194039038182755
957 3977414227973810185655220320332
958 4141606390243169731096433087073
959 4312487705545729608065274238082
960 4490327119343544182324178729109
961 4675404248951708446347659380810
962 4868009801471675162526976040213
963 5068446007878403274496118523861
964 5277027073877588583802970208561
965 5494079648172427693772776651775
966 5719943308803436449027781903622
967 5954971068249800353766069578390
968 6199529898006625663791359850039
969 6454001273379303515988350499294
970 6718781739264047580342684337271
971 6994283497712537631335618713016
972 7280935018108552401383738716769
973 7579181670815526430368978953028
974 7889486385186176108633252691250
975 8212330332858733219174418317332
976 8548213637298962476479176403962
977 8897656110583048669904836945920
978 9261198018453685463780021073098
979 9639400874720310056821587014783
980 10032848266114476393065961200652
981 10442146708752875564174258993621
982 10867926537403570578685990702643
983 11310842828795647888406718103398
984 11771576360258779880572214624300
985 12250834605027178272131879271011
986 12749352765592183017425651635781
987 13267894846539315743720890262236
988 13807254768359121351207665608305
989 14368257523776570792507701917361
990 14951760378201298487693379055648
991 15558654115960547929863244267970
992 16189864334038501302448238732138
993 16846352785109726341156912359020
994 17529118771720895356227492132534
995 18239200593543774994777203035176
996 18977677049693867152239368920755
997 19745668998183064253293942343936
998 20544340974651389630121819747636
999 21374902872602394256236072923723
1000 22238611687449206395312297814981