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 103
28 126
29 165
30 201
31 258
32 315
33 401
34 487
35 611
36 743
37 924
38 1118
39 1382
40 1664
41 2041
42 2455
43 2989
44 3583
45 4340
46 5185
47 6248
48 7446
49 8930
50 10604
51 12668
52 15002
53 17848
54 21083
55 24987
56 29435
57 34776
58 40860
59 48119
60 56398
61 66221
62 77430
63 90667
64 105771
65 123523
66 143790
67 167507
68 194573
69 226145
70 262138
71 303990
72 351695
73 406974
74 469942
75 542712
76 625532
77 720997
78 829568
79 954398
80 1096228
81 1258960
82 1443673
83 1655143
84 1894982
85 2168991
86 2479461
87 2833529
88 3234298
89 3690534
90 4206451
91 4792780
92 5455165
93 6206769
94 7055018
95 8016044
96 9099635
97 10325502
98 11706356
99 13266401
100 15021953
101 17002713
102 19229647
103 21739019
104 24557632
105 27729888
106 31289764
107 35291596
108 39778379
109 44816462
110 50459981
111 56790111
112 63874684
113 71812796
114 80689382
115 90625212
116 101726266
117 114139850
118 127997582
119 143478975
120 160747285
121 180020967
122 201501981
123 225456069
124 252132373
125 281853827
126 314927355
127 351744904
128 392683622
129 438219117
130 488813660
131 545043849
132 607475606
133 676806900
134 753729270
135 839087225
136 933724065
137 1038660629
138 1154923828
139 1283746256
140 1426376319
141 1584301410
142 1759036588
143 1952374720
144 2166152355
145 2402528234
146 2663725275
147 2952340960
148 3271061599
149 3623009616
150 4011427499
151 4440064933
152 4912830619
153 5434223709
154 6008949722
155 6642402051
156 7340239242
157 8108920421
158 8955241662
159 9886932296
160 10912144626
161 12040119664
162 13280626442
163 14644702609
164 16144041687
165 17791816624
166 19602008874
167 21590326075
168 23773468454
169 26170149364
170 28800295799
171 31686184216
172 34851567477
173 38322940544
174 42128590275
175 46300002028
176 50870829627
177 55878459328
178 61362891358
179 67368482518
180 73942733871
181 81138229214
182 89011325986
183 97624312113
184 107043992811
185 117344092632
186 128603734256
187 140910109957
188 154356850384
189 169046998307
190 185091258598
191 202611313286
192 221737949635
193 242614750610
194 265396104053
195 290251312051
196 317362475793
197 346929076844
198 379165738248
199 414307329247
200 452606608270
201 494339914555
202 539804691723
203 589325839912
204 643253130567
205 701968289670
206 765882320647
207 835443407717
208 911134155044
209 993480416113
210 1083048469847
211 1180454881374
212 1286363647057
213 1401497212263
214 1526633614589
215 1662618804415
216 1810363831284
217 1970858618128
218 2145169249702
219 2334453383815
220 2539957696788
221 2763035142554
222 3005142635430
223 3267860375333
224 3552889875004
225 3862075608676
226 4197403490281
227 4561025145612
228 4955256980255
229 5382607396326
230 5845776622188
231 6347687249575
232 6891485007901
233 7480573050799
234 8118613912378
235 8809568003832
236 9557697035863
237 10367607265501
238 11244254690026
239 12192993667828
240 13219584259573
241 14330246899021
242 15531672332035
243 16831083118203
244 18236246669884
245 19755544476491
246 21397988845747
247 23173300832862
248 25091931391070
249 27165149143725
250 29405066730372
251 31824739719716
252 34438199088568
253 37260562703897
254 40308075039781
255 43598232869844
256 47149833455119
257 50983116322665
258 55119821370931
259 59583348823190
260 64398828931566
261 69593302495579
262 75195804058819
263 81237565709636
264 87752115990152
265 94775510004752
266 102346446603180
267 110506528262346
268 119300399427396
269 128776040114048
270 138984928751730
271 149982373916715
272 161827705531541
273 174584649752352
274 188321552890922
275 203111805159997
276 219034102348387
277 236172924822498
278 254618842721091
279 274469057506636
280 295827757199592
281 318806728748715
282 343525770800679
283 370113386165020
284 398707260709326
285 429455046456743
286 462514916316343
287 498056449765985
288 536261274527480
289 577324068277917
290 621453299948265
291 668872362713343
292 719820429260690
293 774553733315652
294 833346555278620
295 896492671690997
296 964306489903901
297 1037124687485856
298 1115307517019235
299 1199240660351443
300 1289336727545295
301 1386037353983705
302 1489814920787871
303 1601174926468719
304 1720657959706486
305 1848842381362195
306 1986346584718811
307 2133832028168085
308 2292005822725141
309 2461624160985053
310 2643495276882882
311 2838483322396568
312 3047511750576423
313 3271567697904759
314 3511705848419830
315 3769053387131057
316 4044814410499118
317 4340275524702491
318 4656810876369727
319 4995888478743473
320 5359075946251835
321 5748047642252412
322 6164591211740549
323 6610615656261351
324 7088158771415711
325 7599396267686861
326 8146650233220762
327 8732399434431477
328 9359288939830827
329 10030141751206407
330 10747969741822310
331 11515986787684779
332 12337621193117806
333 13216530512986897
334 14156615660524997
335 15162037635311339
336 16237233533110692
337 17386935420987169
338 18616188496810566
339 19930372383115546
340 21335221714953912
341 22836850157899536
342 24441773738191405
343 26156937927844889
344 27989744070560385
345 29948079919466990
346 32040349556208336
347 34275507814515499
348 36663094139633248
349 39213271383973017
350 41936864109769552
351 44845402302957149
352 47951164684041423
353 51267227953323006
354 54807515745127411
355 58586854092111526
356 62621026736424923
357 66926837584966138
358 71522173178454410
359 76426073003588733
360 81658800019510246
361 87241919797557409
362 93198380114792694
363 99552600009860670
364 106330559576115884
365 113559900153767491
366 121270025593205249
367 129492214950380601
368 138259736645241847
369 147607975192110305
370 157574559850176205
371 168199507104639513
372 179525365599359794
373 191597376289534339
374 204463635662394511
375 218175275712066003
376 232786647694606609
377 248355524332349412
378 264943306619015924
379 282615250946797934
380 301440701778102668
381 321493346708684433
382 342851478157817761
383 365598279737856807
384 389822120489902331
385 415616876327887690
386 443082260765347158
387 472324185646945852
388 503455132778174986
389 536594558653229742
390 571869311920685076
391 609414087368776595
392 649371894741289903
393 691894567858018352
394 737143290942304620
395 785289169441725815
396 836513820751279594
397 891010014064369469
398 948982333180717916
399 1010647893571416233
400 1076237085856768977
401 1145994379219747394
402 1220179155138683722
403 1299066607341026030
404 1382948676489071701
405 1472135058044925395
406 1566954249845788455
407 1667754680563334343
408 1774905883485174028
409 1888799759711237909
410 2009851892993900587
411 2138502963439309007
412 2275220219966501119
413 2420499062089474862
414 2574864688457461323
415 2738873866303040835
416 2913116776640573401
417 3098218993202180298
418 3294843547221706536
419 3503693140166637916
420 3725512453650095280
421 3961090623028652226
422 4211263820891481475
423 4476918021665405833
424 4758991890359035998
425 5058479871728649982
426 5376435419544465497
427 5713974447659971967
428 6072278939054312079
429 6452600800358230692
430 6856265894352749427
431 7284678344179735164
432 7739325037894398454
433 8221780433776523070
434 8733711590993125533
435 9276883533187564600
436 9853164865365403591
437 10464533759331747704
438 11113084223637281483
439 11801032781525519217
440 12530725468235795843
441 13304645279991136678
442 14125419981227875910
443 14995830411881794261
444 15918819196292258083
445 16897500005719094540
446 17935167270845423633
447 19035306507187166049
448 20201605144397887032
449 21437964034125313962
450 22748509521826790859
451 24137606269803945501
452 25609870711095091297
453 27170185335022772806
454 28823713678080895378
455 30575916235507417902
456 32432567161093031617
457 34399771986206844806
458 36483986219291164067
459 38692035073611663583
460 41031134178059695810
461 43508911536868026488
462 46133430586437729361
463 48913214634577297010
464 51857272523635784452
465 54975125823740804830
466 58276837390808602044
467 61773041618042421679
468 65474976208697017919
469 69394515823049824331
470 73544207420431891269
471 77937307675338179248
472 82587822281542898646
473 87510547551331368237
474 92721114116886019651
475 98236033171199021961
476 104072745048760805365
477 110249670616001359020
478 116786265265097278167
479 123703076016271676847
480 131021801515779380691
481 138765355472603231793
482 146957933314937247488
483 155625082650352238047
484 164793777304989998834
485 174492495569778204634
486 184751302423767511165
487 195601936410167525169
488 207077900930548577062
489 219214560684146889690
490 232049243013837295838
491 245621344941176958801
492 259972445649056825737
493 275146425254270813924
494 291189589626566929549
495 308150802161206579648
496 326081622260857870029
497 345036451503796257950
498 365072687254938944314
499 386250884772300520636
500 408634927567784272698
501 432292207156656425378
502 457293811958949335618
503 483714726575585413181
504 511634041209035739474
505 541135172546995702385
506 572306095888043016056
507 605239589931315959508
508 640033494021270901687
509 676790979381673865122
510 715620834145327374371
511 756637763835095258174
512 799962707121995018462
513 845723168647418561561
514 894053568758848649079
515 945095612088614330729
516 998998674853544805839
517 1055920212959478079276
518 1116026190822521687235
519 1179491533158404259222
520 1246500599692089080282
521 1317247685220497505825
522 1391937545027799343598
523 1470785948282979443936
524 1554020259474325260274
525 1641880050724101088293
526 1734617745102091490298
527 1832499294013027797412
528 1935804888850523889171
529 2044829710244070108167
530 2159884715176760868293
531 2281297465573372479270
532 2409412998733911736899
533 2544594743508786643199
534 2687225482701996802380
535 2837708365920564007423
536 2996467973483329514805
537 3163951435957209344602
538 3340629610077957333724
539 3526998316003710003771
540 3723579636821413234166
541 3930923285667589645918
542 4149608041567898373719
543 4380243259806075171639
544 4623470458134708275442
545 4879964985126759673868
546 5150437772214543606247
547 5435637176246083417693
548 5736350914368972266418
549 6053408098649187632290
550 6387681372530701699696
551 6740089157171601531862
552 7111598010094060216752
553 7503225104867414475445
554 7916040834632850066974
555 8351171548932736737024
556 8809802427068141258193
557 9293180498257064246765
558 9802617812280459781342
559 10339494771769715626722
560 10905263630339835659299
561 11501452168681222431244
562 12129667553390735397758
563 12791600391699329202404
564 13489028987518802209296
565 14223823813102227178425
566 14997952202454701698710
567 15813483282027512846005
568 16672593145626140551045
569 17577570290414190808853
570 18530821321825319479102
571 19534876945734687981369
572 20592398256680532788597
573 21706183342088193619098
574 22879174212372426220579
575 24114464078614456813673
576 25415304988892378432729
577 26785115846861732323416
578 28227490824997097137935
579 29746208198162352891744
580 31345239611395092687270
581 33028759809829630127736
582 34801156846275408379272
583 36667042796834829129099
584 38631265001881024512751
585 40698917865460328431036
586 42875355232433176747769
587 45166203379340231560959
588 47577374640508908855021
589 50115081708572303349133
590 52785852633346006720596
591 55596546561707029966758
592 58554370245101993952266
593 61666895361114135616154
594 64942076678673954568347
595 68388271117469854518909
596 72014257734404317609099
597 75829258692151191336847
598 79842961246252881581018
599 84065540810718519048158
600 88507685142519980010845
601 93180619710295352963498
602 98096134292015083362096
603 103266610872752063262336
604 108705052892108139546538
605 114425115918796969660190
606 120441139807214092360100
607 126768182420427453349731
608 133422054980225107693073
609 140419359136213285251429
610 147777525820985333358421
611 155514855991598080499278
612 163650563331393072859575
613 172204819021387721229538
614 181198798662984345251667
615 190654731471023082171721
616 200595951827396664190838
617 211046953324939876938124
618 222033445401113196569053
619 233582412702846088468364
620 245722177292271196721445
621 258482463847420501772336
622 271894467978822492399337
623 285990927829924975555577
624 300806199094580242054039
625 316376333634622053901359
626 332739161844261201654325
627 349934378960797866269981
628 368003635483171603274452
629 386990631915802720977069
630 406941218015465895179001
631 427903496778225691624936
632 449927933361954018109009
633 473067469202800968394389
634 497377641540622528923823
635 522916708635002940305494
636 549745780908221232013703
637 577928958322163144075230
638 607533474248909445989168
639 638629846169650311680086
640 671292033487261953736621
641 705597602817333429471636
642 741627901071014041776929
643 779468236727320000411083
644 819208069638958052593034
645 860941209805110459167846
646 904766025488823328998199
647 950785661151467482800947
648 999108265618661096265996
649 1049847230992654385191200
650 1103121442765765738203990
651 1159055541696219560822059
652 1217780197944944014415906
653 1279432398085188214093436
654 1344155745531598471315721
655 1412100775055651828550351
656 1483425281986655437788413
657 1558294666825180825622138
658 1636882295925606175369436
659 1719369879039976953371085
660 1805947864442662627870759
661 1896815852499208125018452
662 1992183028467486621417957
663 2092268615472106059388119
664 2197302348515155900123703
665 2307524970548729735410550
666 2423188751554214815313647
667 2544558031745809950524624
668 2671909789932716570286270
669 2805534238257699621038649
670 2945735444444145343212308
671 3092831982878482513284464
672 3247157615766744334222254
673 3409062005811030293218418
674 3578911461761067976104320
675 3757089718416106612580050
676 3943998752559412929176753
677 4140059636541585072299788
678 4345713431133625558803174
679 4561422119519496941581242
680 4787669584200407117783334
681 5024962628847680211830732
682 5273832047041527579424531
683 5534833740114527577757384
684 5808549886217182498635670
685 6095590163022433807140859
686 6396593026382875984668551
687 6712227047573154274303508
688 7043192311645423983314238
689 7390221879765026752524238
690 7754083318287737727594672
691 8135580297701141365596445
692 8535554264446015665233974
693 8954886189018227119882795
694 9394498393644450217715826
695 9855356463234666949956535
696 10338471243207122152662233
697 10844900928217786934806189
698 11375753245719490986331676
699 11932187738740835084455539
700 12515418152169036670872515
701 13126714927316359279715889
702 13767407809445367949330287
703 14438888573456414678267914
704 15142613872838596303698160
705 15880108217548523606671444
706 16652967086382110622764455
707 17462860180005061225920550
708 18311534820712513026989168
709 19200819505628754183016463
710 20132627619967612150064652
711 21108961317657364079741379
712 22131915576549706565089227
713 23203682436161383504924837
714 24326555425819994964256330
715 25502934191863619295869856
716 26735329332475413552606128
717 28026367449564992190650760
718 29378796427050051630336699
719 30795490945778605105104013
720 32279458245285688523685260
721 33833844143525571148268842
722 35461939325687708976959090
723 37167185914216441176507673
724 38953184332137422492544227
725 40823700472874772842404383
726 42782673189744007093668417
727 44834222119461005831500228
728 46982655854029001569977903
729 49232480476600319494647366
730 51588408476954763185624981
731 54055368063556628573694975
732 56638512889224011295656432
733 59343232208855689027871064
734 62175161487762480654056784
735 65140193480659786705452145
736 68244489801513324452395282
737 71494493006045227459657421
738 74896939208880800184484449
739 78458871259044439324987762
740 82187652497728697666281771
741 86090981124110047540856693
742 90176905195247683566952446
743 94453838288081573382415946
744 98930575851861524290591769
745 103616312281458797605540242
746 108520658742386124350710252
747 113653661780621973780610709
748 119025822750774569953606440
749 124648118098552513560794764
750 130532020534021014231617204
751 136689521134727446149377062
752 143133152418372454675272963
753 149876012427493793169506871
754 156931789869311551960954440
755 164314790356874525458575017
756 172039963798427317317909163
757 180122932985123955089734080
758 188580023428102288388302565
759 197428294499370807261316131
760 206685571931967894760369206
761 216370481738539425957667440
762 226502485608621133512364023
763 237101917848865274095516140
764 248190023931737145447600354
765 259789000722447453694338762
766 271922038455332646497611566
767 284613364535444787345631687
768 297888289242734674565155678
769 311773253421093726735981092
770 326295878236335643027134057
771 341485017092438176087602080
772 357370809797393101544752582
773 373984739075636408848699410
774 391359689526291331225580154
775 409530009132494583439628808
776 428531573429592034554009342
777 448401852446473064021295248
778 469179980537108376615474833
779 490906829226318244297758266
780 513625083196899892716820783
781 537379319552720645221253316
782 562216090495820297751620913
783 588184009563599161156345687
784 615333841575971595617245524
785 643718596450995317603503013
786 673393627051690830984120503
787 704416731236039002812643392
788 736848258286786684575854422
789 770751219907656434870005658
790 806191405977676430194482486
791 843237505266058398954982010
792 881961231315693417725072661
793 922437453714849987948393848
794 964744334982870385193167515
795 1008963473308040372258531650
796 1055180051382640191428364781
797 1103482991593494863419267248
798 1153965117833851993503743571
799 1206723324216728079642981708
800 1261858750978112725058260733
801 1319476967873812881721626967
802 1379688165382771956729744969
803 1442607354046254532877515216
804 1508354572282216122163476336
805 1577055103031986235511542482
806 1648839699607275409216024990
807 1723844821124675376821948865
808 1802212877926741905852433766
809 1884092487409362327303600993
810 1969638740688159462372559790
811 2059013480558862518515518688
812 2152385591220853592501583723
813 2249931300256964796546749988
814 2351834493378214812027914986
815 2458287042467858155512588806
816 2569489147476186248059750022
817 2685649692745162722356431885
818 2806986618360619212861251655
819 2933727307159491802601897779
820 3066108988039936572728729921
821 3204379156254190753348990422
822 3348796011386266479734726727
823 3499628913751042605139403031
824 3657158859975562762270336915
825 3821678978560466696551455288
826 3993495046245920082432735673
827 4172926026046372027986613819
828 4360304627847290588242682427
829 4555977892500056476650255871
830 4760307800382602103324009390
831 4973671905439716691041305515
832 5196463995751150526517089366
833 5429094781725545161649316015
834 5671992613055471570211090946
835 5925604225622588470410823190
836 6190395519582488029484780516
837 6466852369916660604369786748
838 6755481470783142878246232528
839 7056811215059733349468906763
840 7371392610521670037735312164
841 7699800234162785878558036326
842 8042633226221371311254305929
843 8400516325544267879670963152
844 8774100947979485099161069284
845 9164066309565502491831413571
846 9571120596347121234707128735
847 9996002182731607630723270488
848 10439480900365917660157439280
849 10902359359606144089987068917
850 11385474325723162672643661969
851 11889698152085783127827892431
852 12415940272641812873028737357
853 12965148756122288988135994300
854 13538311924480021130765585398
855 14136460038186537331628415611
856 14760667051104756081907766318
857 15412052437776387519294925660
858 16091783096064246353352076860
859 16801075328220745854062340859
860 17541196903563622841360661734
861 18313469206081167039489360738
862 19119269470408314086680294061
863 19960033109767107488481800822
864 20837256139594186748472438727
865 21752497700741873999138860463
866 22707382686279470693714820063
867 23703604476097971957554627071
868 24742927783673219283139587274
869 25827191619532771449097349333
870 26958312376136317390656610604
871 28138287039084435041096985832
872 29369196529748807527149798204
873 30653209184637848939853682075
874 31992584377004877258947353963
875 33389676286443900596676704337
876 34846937822427348808738610375
877 36366924707996420503618537292
878 37952299730041359307561335042
879 39605837162885143912371645386
880 41330427372129497840216831746
881 43129081606019660911028266260
882 45004936981850073134285574213
883 46961261675253673602441757085
884 49001460320505141398394500119
885 51129079630313750293864926406
886 53347814243892805273806966542
887 55661512812464680030274515265
888 58074184331697336358018365093
889 60590004730969023950570398118
890 63213323729722328298070461343
891 65948671971600536337780408360
892 68800768447453567552619806722
893 71774528218765892267620084951
894 74875070453485318986928962895
895 78107726786732649151738890257
896 81478050019333398001233825442
897 84991823167652606103992045480
898 88655068878712463894929200623
899 92474059225153985022321269884
900 96455325895143131108862176454
901 100605670792948197164416398280
902 104932177066498104973713930003
903 109442220578906001674042994865
904 114143481841572520634272864197
905 119043958427209867979758526818
906 124151977881808697515444036625
907 129476211155352595272249649793
908 135025686571820639045018905107
909 140809804359861709024501755195
910 146838351766319029091981315703
911 153121518775691608406597677791
912 159669914459477863137010735716
913 166494583980324846280477350019
914 173607026276833936029114505416
915 181019212455927296032467413425
916 188743604920681046478271778485
917 196793177262665625853003014505
918 205181434948915456997296722654
919 213922436834871850291865167955
920 223030817535810969574465614835
921 232521810690584453859168857379
922 242411273152761169882503172849
923 252715710145675461146332625937
924 263452301419248375940737620872
925 274638928447974088315644359280
926 286294202710932877673159482693
927 298437495096334905974022582787
928 311088966474684614239679091788
929 324269599486424503134289756478
930 338001231591628113052132473520
931 352306589431216633713138889382
932 367209324551019817864792404733
933 382734050542052485438425853833
934 398906381652369809772963105314
935 415752972928072290140067651732
936 433301561943180143676412780478
937 451581012180473602948558705844
938 470621358127713476655080713624
939 490453852156214962344658868251
940 511111013251247652375644902448
941 532626677666488986660204713234
942 555036051577454466393062545336
943 578375765811792775512600738127
944 602683932737241215254101381979
945 628000205391228162748648934127
946 654365838939243952435518376535
947 681823754552536506653294826642
948 710418605799067616668914191007
949 740196847645362758716200891679
950 771206808170530567408848535800
951 803498763097706941490282132591
952 837125013252105849294923619280
953 872139965059140918707765196789
954 908600214200314556203306806205
955 946564632549179408766229717827
956 986094458514238556364521243962
957 1027253390920609539643738113892
958 1070107686567192917155667206635
959 1114726261601421842275157261252
960 1161180796858965742031367531554
961 1209545847321502456179487105013
962 1259898955851379800414647378067
963 1312320771368164790865435267077
964 1366895171638226571164374206886
965 1423709390855145141814685665247
966 1482854152195360513894712303738
967 1544423805540626978940149848972
968 1608516470565970453625980909256
969 1675234185399538782477518752528
970 1744683061068417610779357415728
971 1816973441952758872086694661687
972 1892220072478842733051446940982
973 1970542270290594446347665958962
974 2052064106147987139429009606067
975 2136914590810335255290295197371
976 2225227869172076756213124570940
977 2317143421928939348114248064096
978 2412806275062714809359748766481
979 2512367217443940217913996518193
980 2615983026862904578469383663128
981 2723816704811309729474715124460
982 2836037720348884566949538030359
983 2952822263402060065253389115718
984 3074353507854697167727846336164
985 3200821884804633130105418613064
986 3332425366373679656803425986159
987 3469369760473516689185962550952
988 3611869016944850443782331515191
989 3760145545503129069204941495559
990 3914430545940170288190685841667
991 4074964351048177342730775690083
992 4241996782749901951878935704245
993 4415787521937121152765425730400
994 4596606492538190100886186667058
995 4784734260355222847466341388231
996 4980462447231459293344361707940
997 5184094161130650830394996115819
998 5395944442731819733987945495390
999 5616340729165616167014883506699
1000 5845623335541648731988352365773