10 1
11 0
12 1
13 1
14 2
15 2
16 4
17 4
18 7
19 8
20 13
21 15
22 22
23 26
24 37
25 45
26 61
27 74
28 99
29 120
30 158
31 192
32 247
33 300
34 382
35 463
36 582
37 705
38 877
39 1059
40 1309
41 1575
42 1931
43 2319
44 2823
45 3381
46 4094
47 4886
48 5886
49 7007
50 8401
51 9971
52 11905
53 14090
54 16756
55 19781
56 23436
57 27594
58 32586
59 38268
60 45050
61 52780
62 61947
63 72406
64 84751
65 98835
66 115383
67 134267
68 156360
69 181568
70 210958
71 244467
72 283407
73 327791
74 379198
75 437758
76 505399
77 582383
78 671079
79 771952
80 887881
81 1019612
82 1170672
83 1342157
84 1538394
85 1760969
86 2015149
87 2303171
88 2631496
89 3003157
90 3426091
91 3904386
92 4447745
93 5061636
94 5757951
95 6543862
96 7433965
97 8437632
98 9572720
99 10851390
100 12295544
101 13920782
102 15753967
103 17815079
104 20136973
105 22745118
106 25679743
107 28973074
108 32674387
109 36824353
110 41483194
111 46702069
112 52554616
113 59104872
114 66442831
115 74648484
116 83831626
117 94091905
118 105563284
119 118369416
120 132673663
121 148629176
122 166434856
123 186279993
124 208406661
125 233048128
126 260498789
127 291045616
128 325046182
129 362852835
130 404899621
131 451618136
132 503534824
133 561177562
134 625184041
135 696198810
136 774993773
137 862354382
138 959214198
139 1066529003
140 1185426570
141 1317068198
142 1462815169
143 1624076153
144 1802492793
145 1999771571
146 2217890059
147 2458912702
148 2725219779
149 3019305083
150 3344030978
151 3702406220
152 4097869343
153 4534045935
154 5015063072
155 5545283887
156 6129657410
157 6773428367
158 7482525618
159 8263246367
160 9122687171
161 10068399897
162 11108871204
163 12253148012
164 13511369810
165 14894362983
166 16414231388
167 18083916728
168 19917855316
169 21931501959
170 24142059366
171 26567965051
172 29229701091
173 32149241166
174 35350951252
175 38860994681
176 42708332808
177 46924088229
178 51542656326
179 56601024021
180 62140006973
181 68203522164
182 74839963810
183 82101431335
184 90045259261
185 98733199203
186 108233123966
187 118618163554
188 129968602287
189 142370972496
190 155920166851
191 170718490616
192 186878017465
193 204519603258
194 223775512333
195 244788401119
196 267714246524
197 292721304607
198 319993380915
199 349728772511
200 382143919794
201 417472347053
202 455968741628
203 497907906019
204 543589320632
205 593336125319
206 647500223058
207 706461318104
208 770632627136
209 840459999566
210 916428317072
211 999060729255
212 1088925825501
213 1186637032072
214 1292860652915
215 1408315475383
216 1533781796038
217 1670101293088
218 1818187160280
219 1979024322025
220 2153680817107
221 2343308436945
222 2549155527195
223 2772568146964
224 3015004468585
225 3278036581058
226 3563366695296
227 3872829725501
228 4208411544021
229 4572252499643
230 4966667987788
231 5394153101462
232 5857405821147
233 6359333014162
234 6903076599612
235 7492021151135
236 8129823427333
237 8820421884810
238 9568070021226
239 10377348140277
240 11253201027071
241 12200952364935
242 13226347317899
243 14335570075496
244 15535291998756
245 16832692826806
246 18235515146003
247 19752089879206
248 21391397923481
249 23163100652250
250 25077609686853
251 27146123234523
252 29380705105593
253 31794327839877
254 34400962211647
255 37215628257451
256 40254496685282
257 43534949060348
258 47075692745523
259 50896831693458
260 55019996742882
261 59468428698183
262 64267126059201
263 69442942291104
264 75024753366581
265 81043571412357
266 87532734738029
267 94528040384202
268 102067959680664
269 110193792554819
270 118949912096261
271 128383943901975
272 138547043561420
273 149494104807159
274 161284074368363
275 173980193197493
276 187650353764730
277 202367379241596
278 218209428954064
279 235260321118225
280 253609992944114
281 273354873262843
282 294598404670939
283 317451473281260
284 342033001241653
285 368470441877000
286 396900452035862
287 427469461988395
288 460334438345773
289 495663539375116
290 533636980614961
291 574447787765891
292 618302778739794
293 665423427892616
294 716046980097774
295 770427441969732
296 828836845553145
297 891566384343807
298 958927846510941
299 1031254915864498
300 1108904797185643
301 1192259705007936
302 1281728706524430
303 1377749424158404
304 1480790124854040
305 1591351665809426
306 1709969862762620
307 1837217712175843
308 1973708075298809
309 2120096214551651
310 2277082834933602
311 2445416977258517
312 2625899463911813
313 2819386197216305
314 3026792062527189
315 3249094686393931
316 3487338856824615
317 3742640802962507
318 4016193200103314
319 4309270040657151
320 4623232300073824
321 4959533477983057
322 5319726010938340
323 5705467572738134
324 6118528330928243
325 6560798106802916
326 7034294584838797
327 7541171445871463
328 8083727652513668
329 8664416683435832
330 9285857033486571
331 9950842693375193
332 10662355020617585
333 11423574627387993
334 12237894798109919
335 13108934968794736
336 14040555889293430
337 15036874900677900
338 16102283064870630
339 17241462472805486
340 18459405592041741
341 19761434867604216
342 21153224569568225
343 22640822981391742
344 24230677064412915
345 25929657565508977
346 27745086854842697
347 29684767325953733
348 31757012807359450
349 33970680674667613
350 36335207285983707
351 38860644277861584
352 41557698529982262
353 44437773175004091
354 47513012660286891
355 50796349067202152
356 54301552907160078
357 58043285419433851
358 62037155816800539
359 66299780312918152
360 70848846620403861
361 75703180550859474
362 80882818665810638
363 86409083395666472
364 92304664853431817
365 98593705533995346
366 105301892423166392
367 112456552467767307
368 120086756249321000
369 128223425559960481
370 136899450063345501
371 146149808472626066
372 156011699792655070
373 166524679776817706
374 177730808535833279
375 189674804152275916
376 202404208655289221
377 215969560896890729
378 230424583131214378
379 245826375508730638
380 262235625765395147
381 279716827972622126
382 298338518139984730
383 318173520172824373
384 339299210525332928
385 361797794668687932
386 385756604302666818
387 411268408029189268
388 438431745045394534
389 467351274154283441
390 498138148325158166
391 530910406660839765
392 565793394727112116
393 602920204640281238
394 642432146642865439
395 684479243081533102
396 729220757348257925
397 776825748195076267
398 827473662874773705
399 881354958993091046
400 938671769480155117
401 999638600020427547
402 1064483074374495360
403 1133446716363097947
404 1206785785047661705
405 1284772151287633753
406 1367694233389886603
407 1455857979419096699
408 1549587915153130813
409 1649228244618889945
410 1755144023555710323
411 1867722392088324893
412 1987373888420020090
413 2114533829155067503
414 2249663779634667893
415 2393253099202892561
416 2545820586478891381
417 2707916208842650889
418 2880122943029130998
419 3063058710313637839
420 3257378435140381824
421 3463776209938125419
422 3682987597081329078
423 3915792049991693857
424 4163015486604876251
425 4425532996440946523
426 4704271716944790649
427 5000213859573444220
428 5314399923926954290
429 5647932079639340685
430 6001977757159518657
431 6377773426384135622
432 6776628607327480489
433 7199930091045709738
434 7649146418295879016
435 8125832593421407830
436 8631635084498025701
437 9168297086532687233
438 9737664102585698996
439 10341689818942896333
440 10982442333350320216
441 11662110711819030611
442 12383011937484642149
443 13147598226467743873
444 13958464779052984787
445 14818357940640456646
446 15730183846011818997
447 16697017520959382855
448 17722112520468160161
449 18808911077197479182
450 19961054845562626587
451 21182396214982348177
452 22477010284205634679
453 23849207470249051419
454 25303546851014845075
455 26844850215256938201
456 28478216926717138790
457 30209039576430160924
458 32043020538418958383
459 33986189403341152393
460 36044921414408715276
461 38225956880969134937
462 40536421703938861694
463 42983848989606445856
464 45576201896700478001
465 48321897694719025122
466 51229833190027283781
467 54309411499598238312
468 57570570341508116955
469 61023811824390227048
470 64680233918646235003
471 68551563594464231520
472 72650191824306442950
473 76989210438346664687
474 81582451046672522756
475 86444526020821311987
476 91590871766021512707
477 97037794281545827367
478 102802517259633916207
479 108903232726070262303
480 115359154493636247915
481 122190574438145437694
482 129418921890869555262
483 137066826164754759908
484 145158182532815374154
485 153718221684991694292
486 162773583008620052823
487 172352391729025231950
488 182484340284526283911
489 193200773984092492328
490 204534781353681170756
491 216521289232900557195
492 229197163062616178711
493 242601312440422311059
494 256774802422293079136
495 271760970664710258647
496 287605550926672370629
497 304356803045594909801
498 322065649951315006892
499 340785821854521977051
500 360574008222700714339
501 381490017705123063752
502 403596946673287434405
503 426961356566782787549
504 451653460769155262874
505 477747321235776506056
506 505321055661789845263
507 534457055448145400148
508 565242215323111522299
509 597768174917713260094
510 632131573228166732464
511 668434316309105940184
512 706783859213320902367
513 747293502572601067182
514 790082704925671088189
515 835277411244651160491
516 883010398864645029942
517 933421641331410649111
518 986658691479466821976
519 1042877084326526658940
520 1102240761214350596697
521 1164922515861047938491
522 1231104463883604627695
523 1300978536543869429828
524 1374747000417439845535
525 1452623003836919460007
526 1534831151962754826534
527 1621608111442453558697
528 1713203246679515217899
529 1809879288794449938732
530 1911913039483053593076
531 2019596110989422794422
532 2133235704599907581209
533 2253155429025532946749
534 2379696161298950820185
535 2513216951719977396404
536 2654095975716257232387
537 2802731534337823440337
538 2959543106515133041630
539 3124972455004118425504
540 3299484789435582177698
541 3483569988619347178043
542 3677743885835285245796
543 3882549619512878622967
544 4098559053375830234569
545 4326374268731466207538
546 4566629133358255593628
547 4819990949978835072986
548 5087162189184153637705
549 5368882310136329298311
550 5665929674366947446581
551 5979123556374433067042
552 6309326256830857224312
553 6657445322517270260416
554 7024435879338084918852
555 7411303082992449443656
556 7819104694244210822295
557 8248953783874970423381
558 8702021574908653997389
559 9179540427751108853410
560 9682806976540975201648
561 10213185422972032521517
562 10772110996657835222113
563 11361093588978909588500
564 11981721570330952841779
565 12635665798464001264470
566 13324683828758574089620
567 14050624334954960369086
568 14815431752196670217815
569 15621151151814433301642
570 16469933360822485090799
571 17364040336555967545073
572 18305850810636602738546
573 19297866213799180378021
574 20342716897095952201259
575 21443168662226328427464
576 22602129617964200988396
577 23822657376767073117133
578 25107966610131598142452
579 26461436978250285728395
580 27886621454276126663839
581 29387255060367217114282
582 30967264037724219725693
583 32630775469570963596908
584 34382127381376378569414
585 36225879339222730112120
586 38166823572899715186562
587 40209996646777459164994
588 42360691707533688341556
589 44624471334148140903477
590 47007181021969549226772
591 49514963328860567198330
592 52154272718212197119541
593 54931891129679886190445
594 57854944315699127842199
595 60930918977758268060229
596 64167680744058740745720
597 67573493025971273274450
598 71157036798825204857354
599 74927431348204611954433
600 78894256031560935342786
601 83067573100446939529593
602 87457951637853790260400
603 92076492660487884163317
604 96934855445577833385864
605 102045285137018550330266
606 107420641696028428845072
607 113074430256576697281222
608 119020832956863600787793
609 125274742313085643762204
610 131851796213444366677364
611 138768414605180380015724
612 146041837959888661149796
613 153690167597074482101291
614 161732407959182503429169
615 170188510925923049988375
616 179079422269846092958597
617 188427130349602783130386
618 198254717152372739617878
619 208586411791333970191646
620 219447646580065350211376
621 230865115800093288251348
622 242866837294849326689955
623 255482217017566206484067
624 268742116678809558662763
625 282678924633560795107389
626 297326630167128786144496
627 312720901333365461265406
628 328899166519298439898915
629 345900699904495237025214
630 363766711005477436171582
631 382540438489736735265012
632 402267248467371223563897
633 422994737462658028607023
634 444772840292911442967238
635 467653943076374264405979
636 491693001617601451651868
637 516947665413335911592565
638 543478407550386434152482
639 571348660761747219199210
640 600624959937636966865134
641 631377091383106149058163
642 663678249146367444296273
643 697605198737274978135811
644 733238448590102490436747
645 770662429620407191846994
646 809965683262870380126504
647 851241058373082310007830
648 894585917415897273039101
649 940102352359583258839043
650 987897410737391081475409
651 1038083332335379978774570
652 1090777797010681600889947
653 1146104184142312234028724
654 1204191844265150653753711
655 1265176383436456000936341
656 1329199960936205626534869
657 1396411600902244725265113
658 1466967518556796776017965
659 1541031461681690045018818
660 1618775068059137952738637
661 1700378239596965945801330
662 1786029533920880733226315
663 1875926574219851901421786
664 1970276478198918265057345
665 2069296306998813456653532
666 2173213535014930518332478
667 2282266541555043459143623
668 2396705125353583044650021
669 2516791042969207961885575
670 2642798572176446254197159
671 2775015101473424587032378
672 2913741746917823545871150
673 3059293997517017120555238
674 3212002390495029068977026
675 3372213217775642705826810
676 3540289265124733197226215
677 3716610585414816428813802
678 3901575307586143666006859
679 4095600482902187690743408
680 4299122970216892233237174
681 4512600361998571366353470
682 4736511952983698008090983
683 4971359753365780609916471
684 5217669548562392570784807
685 5475992007640313688120127
686 5746903842626863427603693
687 6031009020977872570408987
688 6328940033631916856654279
689 6641359221128863771518001
690 6968960160441883770753529
691 7312469115227210094685684
692 7672646552379891196428966
693 8050288727846323892426777
694 8446229344842187070217595
695 8861341287695123697907809
696 9296538434744316785312084
697 9752777553808861487170728
698 10231060283965782784618226
699 10732435207468257318116696
700 11258000015880973376568610
701 11808903774610234788060187
702 12386349290271601029031265
703 12991595585450593392464139
704 13625960485697490243784556
705 14290823323723242849830416
706 14987627766070959825022660
707 15717884767678003558475486
708 16483175660074830523440509
709 17285155379123325455580571
710 18125555838554031042976964
711 19006189455735882623832119
712 19928952836496317001400952
713 20895830626003131476238064
714 21908899533133548592639423
715 22970332535970611776959906
716 24082403276513328577536487
717 25247490652924842398885086
718 26468083618124004395052852
719 27746786193788990325225516
720 29086322709360295751537928
721 30489543275921537300770209
722 31959429505395801273032411
723 33499100485816824272018844
724 35111819024037502969746863
725 36800998167593084340591110
726 38570208018087040632446356
727 40423182848858913498739677
728 42363828540395336212141419
729 44396230347376539909651112
730 46524661012007989396015961
731 48753589238761398050459342
732 51087688546466608436874856
733 53531846514217950281092753
734 56091174438440670786271951
735 58771017419037044821262056
736 61576964893483746409539494
737 64514861638382711542588723
738 67590819258995359976982919
739 70811228187982490476037423
740 74182770215681602089491929
741 77712431575013250850013383
742 81407516605305927241938341
743 85275662020162305638833205
744 89324851805783210524634646
745 93563432777079145748240901
746 98000130820296110518787586
747 102644067851883262309227383
748 107504779524838647581908522
749 112592233714865212865121346
750 117916849820298838119071540
751 123489518910969772974572035
752 129321624762919081308686804
753 135425065817204206273983071
754 141812278102929315767498516
755 148496259166071473636791612
756 155490593047728047275042890
757 162809476356979891329580351
758 170467745485784461629234189
759 178480905015027678200892186
760 186865157363261663163687397
761 195637433731528475172937213
762 204815426400261500384081980
763 214417622436301367923660421
764 224463338870863750082730825
765 234972759411528885488707625
766 245966972754349110548887179
767 257468012564606764226384077
768 269498899198025617099530442
769 282083683236896366577110130
770 295247490919111743495196382
771 309016571541004679613578910
772 323418346918703698912137125
773 338481462995878930713136463
774 354235843689881804387465782
775 370712747071724615444729566
776 387944823979809887292515350
777 405966179171070933567042768
778 424812435118009994184889001
779 444520798564206651231317163
780 465130129956084796059216887
781 486681015873176318096375191
782 509215844584757590269783694
783 532778884865579399575233326
784 557416368209505525529240862
785 583176574585148115085342253
786 610109921884176293827664911
787 638269059218712267771450575
788 667708964231351284388178549
789 698487044587584029434957234
790 730663243828099297028559881
791 764300151765234170397339400
792 799463119616162180444779167
793 836220380072792837513715406
794 874643172517353730683783422
795 914805873600653008034365555
796 956786133409747098216591809
797 1000665017460463141555470431
798 1046527154760740978748065667
799 1094460892200240907374919773
800 1144558455533030971431497452
801 1196916117230469261347011581
802 1251634371493685408823760622
803 1308818116726256338001337716
804 1368576845780955715801967482
805 1431024844306611038102622451
806 1496281397535462853400700668
807 1564471005864619280210706828
808 1635723609600722692687604103
809 1710174823251275389320403119
810 1787966179762851876758387920
811 1869245385121980858108756710
812 1954166583752619406038222753
813 2042890635161024684205095222
814 2135585402298436143839398639
815 2232426052130301631472815731
816 2333595368921974947975658455
817 2439284080770689685130011634
818 2549691199936522642916313624
819 2665024377546623012309225553
820 2785500273271744399102031663
821 2911344940597504497316997934
822 3042794228339559584811467429
823 3180094199077244119104782952
824 3323501565209150495718756436
825 3473284143361625193677794797
826 3629721327912418506016102350
827 3793104584421540085305740449
828 3963737963795157300235199424
829 4141938638040692280455060403
830 4328037458507784612688199749
831 4522379537544814652190282944
832 4725324854540138439507944428
833 4937248887355144104661137967
834 5158543270198876588238062853
835 5389616479035106864154597865
836 5630894545658794421661564374
837 5882821801623450363834422485
838 6145861653250691569199377793
839 6420497389001543710920828754
840 6707233020542841197359074377
841 7006594158894350047972502340
842 7319128927100357306194969247
843 7645408910926085110062246766
844 7986030149142077892197681371
845 8341614165021014240751615546
846 8712809040739230799196781239
847 9100290536441617197594085006
848 9504763255801824497463163926
849 9926961859981580059938416793
850 10367652331972066732035755578
851 10827633293378096355064862821
852 11307737375791322110852217605
853 11808832648982906037963352740
854 12331824108238426955586068870
855 12877655223248901489991861118
856 13447309551071558760845290695
857 14041812415772569180259088370
858 14662232657471681983108441581
859 15309684453615359283531430194
860 15985329215421368369076402292
861 16690377562553148722577627334
862 17426091379207947046954833922
863 18193785954927489440339805080
864 18994832213575676161912411144
865 19830659034062736026307081224
866 20702755666541827565229401822
867 21612674247950015474150507090
868 22562032420923791182618921510
869 23552516060277115633810116073
870 24585882111400816225506207650
871 25663961545112794048205615976
872 26788662433672960368568047679
873 27961973152861281819259946535
874 29185965715216458537873761992
875 30462799239732157798258587013
876 31794723563522709057347359735
877 33184083001185690127332256376
878 34633320257820902824965416249
879 36144980501898166316785695942
880 37721715604416853895198378833
881 39366288551051815510893258547
882 41081578034250702787192930544
883 42870583232519704940331489333
884 44736428784426515726594295131
885 46682369965143222757123299712
886 48711798073666740937554248596
887 50828246039171891880807104362
888 53035394255292091980595339876
889 55337076651465564657928514184
890 57737287010851735501140777702
891 60240185544692903267341496610
892 62850105733392008188015724556
893 65571561444977399290836969858
894 68409254342052481571018393553
895 71368081588760182560888701792
896 74453143869752847865264367166
897 77669753733624725468256162327
898 81023444273761187972215494175
899 84519978160062591202602948232
900 88165357035536807262813162186
901 91965831292298335193316986065
902 95927910242090231212718842027
903 100058372697032223342257745368
904 104364277976922196556166327924
905 108852977360051999457807750845
906 113532125995171362957423970350
907 118409695292917773330268853322
908 123493985815755806662171054504
909 128793640686207696187216427232
910 134317659533939492772347443764
911 140075413003063883258104260596
912 146076657841864657265488077730
913 152331552598007509524988659113
914 158850673943211878668398396235
915 165645033652286113156578006724
916 172726096262409471032253766550
917 180105797439545220169432361059
918 187796563079927028731832598791
919 195811329175640446788112905016
920 204163562474461835197351841816
921 212867281965281675914051135152
922 221937081221668762103827080489
923 231388151637387894150035445554
924 241236306589009143771483301794
925 251498006562101511160650742369
926 262190385278932493312000140205
927 273331276867056105065701802052
928 284939244109711791627602416631
929 297033607820532161950341158482
930 309634477386717124223431500658
931 322762782526530793769091697320
932 336440306308766149849912454963
933 350689719483654007954014923003
934 365534616176620332075737399478
935 380999550998270526920557687681
936 397110077626056306962377136725
937 413892788915209380175551604200
938 431375358598764093590431616534
939 449586584638785688178217210086
940 468556434293331991676511662587
941 488316090966149467932391515932
942 508898002908702244510395991802
943 530335933846798113102899728258
944 552665015606873973039107083332
945 575921802819875571950793288942
946 600144329783680971260948196332
947 625372169568112399100922964043
948 651646495449828304724844099423
949 679010144767722549658348695548
950 707507685292955120749584189483
951 737185484211332076482541445258
952 768091779819519239682128072128
953 800276756040445378894263806436
954 833792619867307259400152656125
955 868693681849759256401840551672
956 905036439740238721427150147691
957 942879665422870457904214212633
958 982284495252097694911175195606
959 1023314523933025446603108516955
960 1066035902080527161191561481201
961 1110517437599376711624929240511
962 1156830701033121133838467284137
963 1205050135035021604405862782406
964 1255253168120261240529800240148
965 1307520332864661734313933347849
966 1361935388721471258848232740917
967 1418585449634293534790850725406
968 1477561116631031662393961424169
969 1538956615590726917815429156946
970 1602869940382496208588957057911
971 1669403001583315361771807745379
972 1738661780989277902567840903532
973 1810756492143079901028945804292
974 1885801747108965064844070896286
975 1963916729735106195041021507916
976 2045225375652529099749421876194
977 2129856559269094840339958580535
978 2217944288026881166307161100447
979 2309627904201431917737382090117
980 2405052294531915396573094424421
981 2504368107982132813665341913837
982 2607731981943693493259637347642
983 2715306777204403856568115142606
984 2827261822017156404150151877584
985 2943773165617227846569480204386
986 3065023841549063088839573101595
987 3191204141177204268691355929649
988 3322511897770189486912010263069
989 3459152781560859859501917304384
990 3601340606201751505411637322735
991 3749297647049971823423494200876
992 3903254971732350119588068740709
993 4063452783458567093292834049752
994 4230140777567597216100893390536
995 4403578511810993272826244380002
996 4584035790895503120250726695609
997 4771793065827080393822337837726
998 4967141848618742189296213101972
999 5170385142945777558924491933889
1000 5381837891353739024066597803129