9 1
10 0
11 1
12 1
13 2
14 2
15 4
16 4
17 7
18 9
19 13
20 15
21 23
22 27
23 38
24 47
25 63
26 77
27 104
28 126
29 165
30 202
31 259
32 316
33 403
34 489
35 614
36 748
37 929
38 1125
39 1391
40 1676
41 2055
42 2475
43 3012
44 3613
45 4379
46 5233
47 6306
48 7521
49 9018
50 10717
51 12805
52 15171
53 18050
54 21337
55 25288
56 29806
57 35221
58 41400
59 48760
60 57184
61 67147
62 78551
63 91998
64 107367
65 125408
66 146052
67 170166
68 197742
69 229874
70 266564
71 309178
72 357842
73 414159
74 478415
75 552616
76 637166
77 734554
78 845466
79 972877
80 1117832
81 1284047
82 1472909
83 1689018
84 1934387
85 2214557
86 2532326
87 2894579
88 3304955
89 3771971
90 4300552
91 4901042
92 5579982
93 6350181
94 7220025
95 8205322
96 9317062
97 10574504
98 11991865
99 13592939
100 15395733
101 17429563
102 19717515
103 22295362
104 25192489
105 28452943
106 32113613
107 36228620
108 40844572
109 46027537
110 51836088
111 58351349
112 65646267
113 73820241
114 82964454
115 93200121
116 104640782
117 117434782
118 131722566
119 147685398
120 165497331
121 185379054
122 207545618
123 232266243
124 259805418
125 290491087
126 324648772
127 362676843
128 404974949
129 452027536
130 504323527
131 562451266
132 627008949
133 698709466
134 778283236
135 866594417
136 964532436
137 1073143531
138 1193510357
139 1326897262
140 1474619843
141 1638205982
142 1819250795
143 2019598467
144 2241181947
145 2486223685
146 2757062460
147 3056375754
148 3386988147
149 3752121818
150 4155185632
151 4600051940
152 5090829233
153 5632168866
154 6229014779
155 6886948299
156 7611914062
157 8410601063
158 9290148406
159 10258567720
160 11324420859
161 12497294217
162 13787447535
163 15206338654
164 16766248210
165 18480861563
166 20364860381
167 22434575355
168 24707544061
169 27203233858
170 29942572097
171 32948748729
172 36246708616
173 39864051450
174 43830486434
175 48178830206
176 52944432196
177 58166283659
178 63886402563
179 70151077111
180 77010211527
181 84518707375
182 92735781694
183 101726504529
184 111561078157
185 122316561481
186 134076114405
187 146930916621
188 160979393281
189 176329354357
190 193097191018
191 211410276995
192 231406143977
193 253235159155
194 277059703339
195 303057161726
196 331419097262
197 362354610642
198 396089524581
199 432870138316
200 472962457197
201 516656394989
202 564265047709
203 616129420713
204 672617774712
205 734130919201
206 801101682222
207 874000847110
208 953336756967
209 1039662001758
210 1133573204450
211 1235718526157
212 1346797711157
213 1467570521608
214 1598857073952
215 1741547352941
216 1896601917140
217 2065062599143
218 2248053696647
219 2446794021991
220 2662598646030
221 2896892509097
222 3151212843071
223 3427224510465
224 3726723281084
225 4051653137053
226 4404110528606
227 4786363947580
228 5200859361354
229 5650242311793
230 6137364793452
231 6665310227273
232 7237401997432
233 7857231733732
234 8528669819603
235 9255897374881
236 10043419137094
237 10896099657079
238 11819178908049
239 12818313320880
240 13899594604420
241 15069596213869
242 16335395988081
243 17704628804197
244 19185513602075
245 20786913131962
246 22518366108952
247 24390154946720
248 26413343951904
249 28599856150996
250 30962518421321
251 33515148728739
252 36272609326175
253 39250905738226
254 42467249390657
255 45940169967428
256 49689588861065
257 53736946818221
258 58105289920973
259 62819414511953
260 67905967740069
261 73393612150853
262 79313142923737
263 85697674917361
264 92582779168138
265 100006695341643
266 108010490517141
267 116638300541289
268 125937514321249
269 135959048142872
270 146757559309946
271 158391757786974
272 170924653665319
273 184423911245397
274 198962135172555
275 214617272869514
276 231472945044856
277 249618902891111
278 269151409580433
279 290173759699241
280 312796718953556
281 337139114434283
282 363328340965237
283 391501031607049
284 421803640378151
285 454393203883225
286 489438011114776
287 527118468684610
288 567627870120293
289 611173378450292
290 657976909256060
291 708276246442188
292 762326054828726
293 820399147194665
294 882787644611304
295 949804414790921
296 1021784400992555
297 1099086254642839
298 1182093855969017
299 1271218167066587
300 1366898970835163
301 1469606973587265
302 1579845792613275
303 1698154341572728
304 1825109100502573
305 1961326821785443
306 2107467121265537
307 2264235546924019
308 2432386535107297
309 2612726889904267
310 2806119153660139
311 3013485551517152
312 3235811832264603
313 3474151738871358
314 3729631383325334
315 4003454312280726
316 4296906487123906
317 4611362023034768
318 4948288855262609
319 5309255239182312
320 5695936194566607
321 6110120865944426
322 6553719847697679
323 7028773517037272
324 7537460356556453
325 8082106385568772
326 8665194612081616
327 9289375704813770
328 9957478722514830
329 10672523187396027
330 11437731259245795
331 12256541390332207
332 13132622133486925
333 14069887581928238
334 15072513023435265
335 16144952394572130
336 17291956020652873
337 18518590341513997
338 19830258007687845
339 21232720167851704
340 22732119224449852
341 24335004009679957
342 26048355542702395
343 27879615460460187
344 29836715161971188
345 31928107906700834
346 34162801778174300
347 36550395914369395
348 39101117777648687
349 41825864037628073
350 44736242695499800
351 47844619205080441
352 51164164065896053
353 54708904840866337
354 58493779909490071
355 62534697119825401
356 66848594478960549
357 71453506268495493
358 76368631543186775
359 81614408641236048
360 87212592469956208
361 93186338453845107
362 99560289706550547
363 106360671587917797
364 113615389993533856
365 121354137834924789
366 129608505829102722
367 138412102373073924
368 147800678384395990
369 157812262220383557
370 168487300306067312
371 179868808948346143
372 192002532698924865
373 204937115133700663
374 218724277133768888
375 233419008950396597
376 249079770846798261
377 265768709047843061
378 283551881479793195
379 302499500511501978
380 322686186857622768
381 344191242366283529
382 367098935513869966
383 391498807882284110
384 417485995083251250
385 445161570997189163
386 474632908421743108
387 506014065628297000
388 539426191534571041
389 574997959674050296
390 612866023261728147
391 653175502268359956
392 696080494382580618
393 741744621553292316
394 790341603553389337
395 842055871101313101
396 897083209520706449
397 955631446380155478
398 1017921173621746808
399 1084186518587599823
400 1154675953963629337
401 1229653162096236213
402 1309397943189278147
403 1394207183960769804
404 1484395875746081415
405 1580298199829059950
406 1682268668450994252
407 1790683340579801354
408 1905941100331716063
409 2028465018526248614
410 2158703784704405989
411 2297133231588870690
412 2444257938741341947
413 2600612939017651361
414 2766765513984290806
415 2943317103642251880
416 3130905316032565640
417 3330206063941750362
418 3541935813686755640
419 3766853975225897868
420 4005765417971285786
421 4259523143734346132
422 4529031100589325128
423 4815247171434099554
424 5119186320448530510
425 5441923933774463728
426 5784599337036303201
427 6148419528771059041
428 6534663111836107555
429 6944684464817166604
430 7379918134978099930
431 7841883497978680198
432 8332189665398480214
433 8852540688752715669
434 9404741040590995307
435 9990701425093382379
436 10612444898358955625
437 11272113354848362331
438 11971974359833108647
439 12714428388689079461
440 13502016452638192152
441 14337428176498986741
442 15223510307892979053
443 16163275728598270356
444 17159912947437960009
445 18216796150949366792
446 19337495791309719485
447 20525789793768581575
448 21785675363300859647
449 23121381479257922406
450 24537382058131014702
451 26038409880279583121
452 27629471261362679626
453 29315861571985061211
454 31103181587153320206
455 32997354777386401629
456 35004645524186923502
457 37131678380760435175
458 39385458362130914638
459 41773392395342250796
460 44303311915686091471
461 46983496750319193143
462 49822700277385872388
463 52830176013604746788
464 56015705621090581676
465 59389628498957269082
466 62962872953641534697
467 66746989127208870669
468 70754183681313519461
469 74997356430991174081
470 79490138930374709387
471 84246935220723180401
472 89282964748012549781
473 94614307678156658576
474 100257952623078103068
475 106231847024944022282
476 112554950218727414255
477 119247289441349197356
478 126330018815553319429
479 133825481599620730254
480 141757275740222383092
481 150150323044417873523
482 159030942018604975534
483 168426924717546812535
484 178367617663263193818
485 188884007206526155091
486 200008809404352916599
487 211776564818533775973
488 224223738324079306375
489 237388824367833291545
490 251312457783682182803
491 266037530643075716551
492 281609315267099568332
493 298075593920801513046
494 315486795338421039584
495 333896138646033592936
496 353359784855508632951
497 373936996546369081317
498 395690305937828984685
499 418685692022290404814
500 442992766994517609547
501 468684972707486445542
502 495839787424968121884
503 524538943667153991399
504 554868657459517019856
505 586919869852588219567
506 620788501067842110836
507 656575718215345597183
508 694388216988688658016
509 734338518368162364960
510 776545280793891671387
511 821133628933165960499
512 868235499566467624176
513 917990005818405320496
514 970543820328084117184
515 1026051578696710634722
516 1084676303884966401031
517 1146589853020010079844
518 1211973387371577501601
519 1281017867090529007990
520 1353924571566047166526
521 1430905647140966311687
522 1512184683148953847957
523 1597997318172922895537
524 1688591877607959006540
525 1784230044603070067074
526 1885187565597818608599
527 1991754992719682070389
528 2104238464405512124746
529 2222960526722574100662
530 2348260996916038509412
531 2480497871887813490675
532 2620048283314851214591
533 2767309502363040396897
534 2922699995905607617943
535 3086660537477156380979
536 3259655375094750684192
537 3442173459478191607679
538 3634729735047177308267
539 3837866497557170748378
540 4052154821024107075642
541 4278196058160713665965
542 4516623417276011438655
543 4768103620255904905763
544 5033338644909671768332
545 5313067556733028881416
546 5608068433740769448278
547 5919160389893507505635
548 6247205701178367005059
549 6593112040386936096719
550 6957834825099564555309
551 7342379685487521484924
552 7747805056937889920383
553 8175224904734878064217
554 8625811586349648090503
555 9100798859253514063035
556 9601485040410222335388
557 10129236326108185929462
558 10685490278953891312424
559 11271759491504210458646
560 11889635434092606559860
561 12540792497221292075454
562 13226992236882930428405
563 13950087834163330671866
564 14712028778379430408653
565 15514865786176346981352
566 16360755966818935476253
567 17251968247275591106858
568 18190889068409989762899
569 19180028367163982797249
570 20222025857236284418879
571 21319657624547500645434
572 22475843051304675827774
573 23693652086496473021412
574 24976312878071722567037
575 26327219786319135200179
576 27749941795284090134371
577 29248231343586627536265
578 30826033593217598307829
579 32487496159697977781076
580 34236979324092232668917
581 36079066752472928008394
582 38018576745430833879774
583 40060574045648920758430
584 42210382228445913111040
585 44473596705957476893469
586 46856098372399885712863
587 49364067923984213532252
588 52004000883714520542101
589 54782723367811496167294
590 57707408627057368542885
591 60785594403275813885033
592 64025201137604587223182
593 67434551074574077356331
594 71022388302339366384284
595 74797899777235896346463
596 78770737377055771620140
597 82951041035762266234461
598 87349463008482419780171
599 91977193324470162982194
600 96845986481753204187854
601 101968189446597810285252
602 107356771016849764400107
603 113025352618237313579703
604 118988240598555318834530
605 125260460095325932404983
606 131857790548280222769963
607 138796802939374747293514
608 146094898838730601887044
609 153770351346992958910785
610 161842348020217254958190
611 170331035876291486020310
612 179257568577458005420594
613 188644155897249938100382
614 198514115575671149007494
615 208891927681107765398294
616 219803291592949101578828
617 231275185734526644223700
618 243335930181463328314638
619 256015252287196961407362
620 269344355462940407594294
621 283355991267126952094825
622 298084534954927483434653
623 313566064657406225568966
624 329838444355486057076514
625 346941410834154837734949
626 364916664798046012530509
627 383807966351158985083167
628 403661235039319458814698
629 424524654677083873574230
630 446448783176798337148461
631 469486667622205418747202
632 493693964825214927486034
633 519129067630831293559685
634 545853237231719543478165
635 573930741782086669074988
636 603429001597366110531236
637 634418741256340431701774
638 666974148919532652874525
639 701173043209940066988381
640 737097047999834131633783
641 774831775481845636517295
642 814467017900735048131599
643 856096948359164005307889
644 899820331109582417954744
645 945740741783862226251761
646 993966798011821290057736
647 1044612400922094014321061
648 1097796988019136891674942
649 1153645797975477993909982
650 1212290147879588648426731
651 1273867723528310499963383
652 1338522883355108795040340
653 1406406976637458093572644
654 1477678676630215736751355
655 1552504329327619724745611
656 1631058318561468359459670
657 1713523448202851357685077
658 1800091342241270765889699
659 1890962863579143342326325
660 1986348552387885364289304
661 2086469084940609549492085
662 2191555753846628394104483
663 2301850970686821767779976
664 2417608792061282527645432
665 2539095470139942876855807
666 2666590028821689190293831
667 2800384866692609085274607
668 2940786387991554528193935
669 3088115662882641573467645
670 3242709118354896183785826
671 3404919261167485994174303
672 3575115434282958155108899
673 3753684608336459695200672
674 3941032209716667317625272
675 4137582986947608930866514
676 4343781917092494995755931
677 4560095154022654735057171
678 4787011020431246219561032
679 5025041045602580455137425
680 5274721050989611106330614
681 5536612285793231576167504
682 5811302614784416759245993
683 6099407760762042767854841
684 6401572604092893550009615
685 6718472541943715717532814
686 7050814909875794108239943
687 7399340468648346647401509
688 7764824959145300560648567
689 8148080728529307186340735
690 8549958430803549437616014
691 8971348805165736589321489
692 9413184535624668652190635
693 9876442195569300010310739
694 10362144281076446844655816
695 10871361336979797205431900
696 11405214179830344706968544
697 11964876222133210774857806
698 12551575902365647647803152
699 13166599225555659042666623
700 13811292419334087606628147
701 14487064710669059586536216
702 15195391228640002206345912
703 15937816038927613196013595
704 16715955315860852985044721
705 17531500658206180834083395
706 18386222555066897548021208
707 19281974008631616684072933
708 20220694320713201713628968
709 21204413050419861331488415
710 22235254150523968833799725
711 23315440290526084419686677
712 24447297374659143643220394
713 25633259263543808185220005
714 26875872708479302367258745
715 28177802507856983275727279
716 29541836895485499257935359
717 30970893171159202550206334
718 32468023584134021133273422
719 34036421480760939129757082
720 35679427727893590677479922
721 37400537424319062292420686
722 39203406912864315455837897
723 41091861106513673860767544
724 43069901142316519023678966
725 45141712377601928113421809
726 47311672743504787471409524
727 49584361471604514946529755
728 51964568210013474644355342
729 54457302546112589748270367
730 57067803953720164591342100
731 59801552183409386591942544
732 62664278115335822868827886
733 65661975094940365537932073
734 68800910772601469964937002
735 72087639469395449540357908
736 75529015091900185856672122
737 79132204620149921122598584
738 82904702193699744012166371
739 86854343822025226771182917
740 90989322746414648045939966
741 95318205481880352060306885
742 99849948568636062739890422
743 104593916064166730208478895
744 109559897808033924502326858
745 114758128493159251554197652
746 120199307578549437022286473
747 125894620080155680051486170
748 131855758277895079659321344
749 138094944378730995688974083
750 144624954177168522945386991
751 151459141756541893198563843
752 158611465276065009240523625
753 166096513890800934630992169
754 173929535853447514666354618
755 182126467849198338549088462
756 190703965616839460862278935
757 199679435911796278979328150
758 209071069868920026307957747
759 218897877825564973243953042
760 229179725667771530252429516
761 239937372765356736650033570
762 251192511564183221245965786
763 262967808907107058475102372
764 275286949157797908270297571
765 288174679205117097774374502
766 301656855428674995930669337
767 315760492709965752077907838
768 330513815576676878191828983
769 345946311571855595546733712
770 362088786943099753099925083
771 378973424751358444985165698
772 396633845502724488804156855
773 415105170411378344734102932
774 434424087405977963136373243
775 454628919996955997734477062
776 475759699126687575096063427
777 497858238130080108150333907
778 520968210938036629678520433
779 545135233662288182582031840
780 570406949705423019586344507
781 596833118546477399460361639
782 624465708358254045397199133
783 653358992619604557952477642
784 683569650892222308432353533
785 715156873939139253478998772
786 748182473368982488629269132
787 782710995998316980499656214
788 818809843131862217832100073
789 856549394969315665383587225
790 896003140355626773798484152
791 937247812101239907745603109
792 980363528107639805196409354
793 1025433938543996639540903629
794 1072546379330286735984123465
795 1121792032193581471760518688
796 1173266091574603828227461734
797 1227067938673890928808715165
798 1283301322938205288370328449
799 1342074551301073715795024370
800 1403500685503609872064054809
801 1467697747836091043622830576
802 1534788935654090797097462178
803 1604902845038449614272375541
804 1678173703982838779179357717
805 1754741615509413673593796847
806 1834752811128763110802830184
807 1918359915078464839502462121
808 2005722219791608126367361822
809 2097005973066220841447522956
810 2192384677425040930300089834
811 2292039402176240941788673350
812 2396159108705788889653710141
813 2504940989555018585017418640
814 2618590821858759589264645096
815 2737323335744127020675866188
816 2861362598313691671231773087
817 2990942413863511489072968618
818 3126306741012121161069144406
819 3267710127445509940081718378
820 3415418163010893562347283364
821 3569707951923367616356420860
822 3730868604879643298083978839
823 3899201751906885400778306310
824 4075022076807316070514262346
825 4258657874095808545775059706
826 4450451629363076626403050612
827 4650760624036588776174332196
828 4859957565549679577620465157
829 5078431243972055162726257560
830 5306587216196437869444672141
831 5544848518822277240274925333
832 5793656410922469920627976848
833 6053471147928948539647542247
834 6324772787921764914210901135
835 6608062031660245854386820189
836 6903861097747620633992652331
837 7212714634378831061514102501
838 7535190669178441573411886890
839 7871881598698586786348686115
840 8223405219208842675559227924
841 8590405800478012574632663151
842 8973555204314895210201844585
843 9373554049708698701747444539
844 9791132926482383506900372882
845 10227053659451744569034835705
846 10682110625161653837446623133
847 11157132123356815707040628331
848 11652981805429475277087725115
849 12170560162179365696674154748
850 12710806073313267732338451595
851 13274698421211867273081559850
852 13863257771591247433515828032
853 14477548123794725352424194986
854 15118678733558568166829015452
855 15787806011212198357540298282
856 16486135498390154088102935462
857 17214923926459540062602081690
858 17975481359992900482742421016
859 18769173428753056041476437094
860 19597423651792949263623431606
861 20461715857421098125405799133
862 21363596702930892681911782461
863 22304678298151338290778073856
864 23286640937036507428261310636
865 24311235941683080163340476166
866 25380288623337996775907298085
867 26495701365144122485102254156
868 27659456831558489692178111586
869 28873621309578406205598209062
870 30140348187112523804535012817
871 31461881574050704327902202806
872 32840560071804673063083186469
873 34278820697325476525795267548
874 35779202967839561799686652035
875 37344353152797969806947576596
876 38977028699787985047205108710
877 40680102841429377042993020745
878 42456569390552781339764983494
879 44309547731252262065923275577
880 46242288013701703613289253703
881 48258176560942581802070501037
882 50360741496172221097558709202
883 52553658599404795707021000631
884 54840757402724734026197114316
885 57226027533722568186500770293
886 59713625317078559866452765372
887 62307880644659183193028066994
888 65013304124896923898886373512
889 67834594522655272797644335463
890 70776646501218631174213618814
891 73844558678512413774681175211
892 77043642010131492210665039945
893 80379428512257510656884018536
894 83857680338056235020795176954
895 87484399221688184974593832826
896 91265836304617167723729980725
897 95208502359486219990294763325
898 99319178427425772019651943819
899 103604926885289873779098266816
900 108073102959959013466857383574
901 112731366707528820156042385362
902 117587695475897725811126039348
903 122650396870001032286124535020
904 127928122239687702861383190118
905 133429880711028348120265249283
906 139165053782651145455299249481
907 145143410509556853213566835996
908 151375123297736381994099199873
909 157870784333835915036601879106
910 164641422675055896151333483772
911 171698522025464047883297131013
912 179054039225918310598394352106
913 186720423485867358187523840985
914 194710636386392264720676928083
915 203038172685008617029745265186
916 211717081953930710425575226705
917 220761991084745637395662945342
918 230188127693720555162543729618
919 240011344463310035161468898356
920 250248144456806231025000822401
921 260915707444523189444117171999
922 272031917281390595072071208809
923 283615390377393898967171570764
924 295685505303898249521997611320
925 308262433580577090580997360186
926 321367171689392271429110980844
927 335021574363887126620713785190
928 349248389203915168379977458047
929 364071292667882908460319418043
930 379514927496592148015857027503
931 395604941624875069007932528620
932 412368028639379144817359413278
933 429831969843130687447699565244
934 448025677989838473730071746073
935 466979242753347067230837375200
936 486723978000164013484265249185
937 507292470935623156904707272529
938 528718633196956805010934211498
939 551037753969391977742027531608
940 574286555204307412716892543894
941 598503249021550595558663707760
942 623727597381162650700686838539
943 650000974113058438815163906402
944 677366429396602307105893264664
945 705868756785574457824655757836
946 735554562877679249043253099847
947 766472339731575729560226706721
948 798672540138350433809944610622
949 832207655858476845288259523291
950 867132298939550680364693490431
951 903503286234532422450423394735
952 941379727244801573199031721036
953 980823115417111453403146192531
954 1021897423028459741187389226176
955 1064669199798042398519609958596
956 1109207675370765216203492723022
957 1155584865822335729620196842185
958 1203875684341673987166523940823
959 1254158056252355291897906276084
960 1306513038540954013325768445763
961 1361024944066590630554957559915
962 1417781470632613818126880902809
963 1476873835108275602822925659888
964 1538396912795396873433390650320
965 1602449382242477218649884912267
966 1669133875716390542983897419900
967 1738557135549835191656271152359
968 1810830176590984514802160237424
969 1886068454990424775311616986719
970 1964392043569378831135203824093
971 2045925814022515009069792565830
972 2130799626218234370013404180043
973 2219148524869340333871598764200
974 2311112943857322173161106180035
975 2406838918504257908419385948245
976 2506478306097458773147996991977
977 2610189014983572146318470612465
978 2718135242560825030655037652667
979 2830487722510567309892869091568
980 2947423981622151614146177421756
981 3069128606578612501501233782306
982 3195793521084466287871873003274
983 3327618273731398676282312253327
984 3464810337012520690144795256345
985 3607585417911415666946548585656
986 3756167780508247315260404665920
987 3910790581061919677227089335201
988 4071696216044546003087625295505
989 4239136683622471201820432654374
990 4413373959096668928351633558761
991 4594680384834683593794599830146
992 4783339075246272276315508955437
993 4979644337375714049677573504275
994 5183902107705252535622641088074
995 5396430405786522588941651157143
996 5617559805339936982209854071332
997 5847633923486083923692482467828
998 6087009928798059273832914325194
999 6336059068889548092916314057506
1000 6595167218280221602388688197051