8 1
9 0
10 1
11 1
12 2
13 2
14 4
15 4
16 8
17 9
18 13
19 16
20 24
21 28
22 40
23 49
24 67
25 82
26 110
27 133
28 176
29 215
30 276
31 338
32 432
33 524
34 661
35 804
36 1001
37 1214
38 1502
39 1812
40 2228
41 2683
42 3270
43 3928
44 4766
45 5699
46 6879
47 8208
48 9855
49 11724
50 14020
51 16624
52 19804
53 23423
54 27788
55 32781
56 38770
57 45603
58 53762
59 63091
60 74146
61 86803
62 101736
63 118811
64 138890
65 161849
66 188707
67 219433
68 255260
69 296183
70 343767
71 398102
72 461051
73 532897
74 615915
75 710547
76 819648
77 943907
78 1086770
79 1249370
80 1435920
81 1647964
82 1890774
83 2166519
84 2481589
85 2839067
86 3246795
87 3708859
88 4235014
89 4830684
90 5507769
91 6273592
92 7142752
93 8124705
94 9237560
95 10493595
96 11914939
97 13517594
98 15328737
99 17368773
100 19671273
101 22262238
102 25182741
103 28466059
104 32162560
105 36314145
106 40982853
107 46221480
108 52105871
109 58702593
110 66104527
111 74394811
112 83687439
113 94086110
114 105730031
115 118748649
116 133312033
117 149580587
118 167762388
119 188056054
120 210715144
121 235985461
122 264176033
123 295589613
124 330602999
125 369588577
126 413004449
127 461308437
128 515057282
129 574811657
130 641248245
131 715052944
132 797046222
133 888066395
134 989107779
135 1101192101
136 1225523970
137 1363347065
138 1516117971
139 1685349260
140 1872800938
141 2080308241
142 2309996780
143 2564090812
144 2845153238
145 3155877089
146 3499350194
147 3878827050
148 4298025494
149 4760874030
150 5271842738
151 5835669250
152 6457723637
153 7143709921
154 7900074808
155 8733678652
156 9652250803
157 10664034289
158 11778288640
159 13004904477
160 14354965914
161 15840328223
162 17474244596
163 19270912083
164 21246164067
165 23416980608
166 25802262932
167 28422300132
168 31299632052
169 34458479461
170 37925699108
171 41730173164
172 45903876863
173 50481218832
174 55500231575
175 61001871947
176 67031340356
177 73637337963
178 80873542361
179 88797812594
180 97473835509
181 106970291910
182 117362684654
183 128732463670
184 141169071631
185 154769020172
186 169638175323
187 185890803312
188 203652112755
189 223057271401
190 244254254274
191 267402825953
192 292677726257
193 320267645354
194 350378775568
195 383233786169
196 419075806776
197 458167402701
198 500795038233
199 547268092132
200 597923844251
201 653126549086
202 713273037126
203 778791857542
204 850149564251
205 927849987661
206 1012441274701
207 1104515324518
208 1204715707693
209 1313737296339
210 1432335168294
211 1561324520990
212 1701590665146
213 1854089286901
214 2019857708441
215 2200015559436
216 2395777459726
217 2608454236019
218 2839467188527
219 3090349962570
220 3362764648086
221 3658504418815
222 3979511697298
223 4327881766568
224 4705883243838
225 5115962847485
226 5560768536964
227 6043155627277
228 6566212937888
229 7133270566237
230 7747929415474
231 8414070920929
232 9135890467105
233 9917909386004
234 10765012774792
235 11682464235765
236 12675948647387
237 13751590112932
238 14916000424561
239 16176300731897
240 17540176453701
241 19015903376653
242 20612409845257
243 22339308018237
244 24206964404468
245 26226537084790
246 28410055714202
247 30770465775752
248 33321719283817
249 36078827193554
250 39057962360127
251 42276521356331
252 45753241338497
253 49508272873372
254 53563312549668
255 57941688527865
256 62668511155318
257 67770773162623
258 73277520721084
259 79219970675079
260 85631704760611
261 92548806470934
262 100010081728803
263 108057218305346
264 116735036529533
265 126091674818699
266 136178874444152
267 147052195075355
268 158771338391530
269 171400398040811
270 185008227364924
271 199668729046928
272 215461272857569
273 232471030823116
274 250789451972023
275 270514649603070
276 291751940741352
277 314614293299995
278 339222938921293
279 365707888690538
280 394208629504878
281 424874718123034
282 457866572333675
283 493356154808666
284 531527871755063
285 572579359369915
286 616722504714792
287 664184349230398
288 715208248255929
289 770054908425538
290 829003704341580
291 892353868672155
292 960425987342679
293 1033563363603068
294 1112133715622488
295 1196530739108177
296 1287176034214158
297 1384520894274262
298 1489048492957875
299 1601275930251258
300 1721756714487756
301 1851083101387617
302 1989888910000551
303 2138852194999446
304 2298698441208680
305 2470203614547244
306 2654197785239055
307 2851568609389538
308 3063265437325436
309 3290303284212593
310 3533767487930438
311 3794818234650774
312 4074695838507310
313 4374725897370005
314 4696325275734338
315 5041007975247907
316 5410391913436185
317 5806205604367905
318 6230295837208483
319 6684635275557242
320 7171331152934584
321 7692633912803081
322 8250947053900252
323 8848836948479026
324 9489043986724231
325 10174493729325615
326 10908309518987485
327 11693825142809463
328 12534599101148299
329 13434428977482269
330 14397367578288033
331 15427739234268272
332 16530158051615197
333 17709546396204427
334 18971155527990843
335 20320586551380720
336 21763813737848526
337 23307208262655284
338 24957564558743710
339 26722127199472329
340 28608620670962947
341 30625279805419897
342 32780883406522792
343 35084788689916643
344 37546969249977230
345 40178054020176711
346 42989370131599108
347 45992986969433171
348 49201764540739316
349 52629403276469845
350 56290498601923276
351 60200597213110301
352 64376258630383380
353 68835118767695594
354 73595959344723675
355 78678779670219420
356 84104874894865414
357 89896917042007933
358 96079043205531251
359 102676946987566709
360 109717977879148046
361 117231244408350088
362 125247726091775135
363 133800389754263205
364 142924315609964802
365 152656828392150106
366 163037639310109682
367 174108993828775924
368 185915831458295555
369 198505952244461192
370 211930196586276171
371 226242632746637523
372 241500759155747668
373 257765715532385138
374 275102510425581490
375 293580258846471463
376 313272438133064692
377 334257155339858397
378 356617434877394592
379 380441519298192979
380 405823192573685054
381 432862118347330239
382 461664203174164937
383 492341976795953825
384 525015000179857258
385 559810292914803244
386 596862791457848531
387 636315829352970825
388 678321651736233372
389 723041954751435618
390 770648463076241364
391 821323535664664477
392 875260813850865464
393 932665901384941331
394 993757091561972469
395 1058766130451934166
396 1127939032488091850
397 1201536936838611385
398 1279837021989790891
399 1363133466366565667
400 1451738473678741721
401 1545983350191638860
402 1646219653969449957
403 1752820402644626244
404 1866181361215838699
405 1986722395768899188
406 2114888916189436767
407 2251153393076534922
408 2396016973617390512
409 2550011180932415512
410 2713699723462084434
411 2887680398196690044
412 3072587116272720256
413 3269092034007108579
414 3477907820002628697
415 3699790040658106310
416 3935539696979339520
417 4186005894287455089
418 4452088680161733688
419 4734742031463569841
420 5034977028418195698
421 5353865195855091760
422 5692542052419076890
423 6052210847122346014
424 6434146527111551368
425 6839699915291192650
426 7270302144991042367
427 7727469329612921756
428 8212807518009464434
429 8728017912861905904
430 9274902406663410956
431 9855369411931501100
432 10471440044430167483
433 11125254635433657447
434 11819079636309961018
435 12555314890935574180
436 13336501344086767724
437 14165329160858906996
438 15044646330535323813
439 15977467729591593322
440 16966984722950474026
441 18016575277928156286
442 19129814676155515705
443 20310486797782538882
444 21562596069942752137
445 22890380053809670856
446 24298322769455543057
447 25791168733059344322
448 27373937813519316971
449 29051940883420978836
450 30830796379936112085
451 32716447751252239455
452 34715181913329542992
453 36833648693525031053
454 39078881395892577894
455 41458318465936548339
456 43979826400511170571
457 46651723882251033827
458 49482807296020440475
459 52482377608807316224
460 55660268783369153014
461 59026877709548223815
462 62593195837512263471
463 66370842499873809809
464 70372100122082038024
465 74609951311705645022
466 79098118042468875969
467 83851102927989921047
468 88884232819018076299
469 94213704724236841731
470 99856634307916250729
471 105831106970500487202
472 112156231786633949812
473 118852198313693166414
474 125940336568455629169
475 133443180193075800605
476 141384533133158402986
477 149789539858476641699
478 158684759476545806902
479 168098243780348160907
480 178059619610328642934
481 188600175584285592167
482 199752953607845783128
483 211552845233260891355
484 224036693314740535795
485 237243399044102144043
486 251214034853730385519
487 265991963288874147853
488 281622962378541204225
489 298155357627745391878
490 315640161206503626156
491 334131218481755484153
492 353685362517995236306
493 374362576719259989809
494 396226166293237823364
495 419342938740029864205
496 443783394106376509569
497 469621925241495070188
498 496937028860960739425
499 525811527692590910897
500 556332804582405965297
501 588593048877128543361
502 622689516039590301717
503 658724800861125844477
504 696807125312931136200
505 737050641453828548073
506 779575750529937255291
507 824509438743450584228
508 871985630928277925443
509 922145562676502605201
510 975138172265269816674
511 1031120513002625346769
512 1090258187464182465297
513 1152725804322395645401
514 1218707459374059670446
515 1288397241560574874423
516 1361999765732942408104
517 1439730733059391448786
518 1521817520987636459704
519 1608499803774780841908
520 1700030205671982816485
521 1796674987904881869182
522 1898714771728577245487
523 2006445298840449763779
524 2120178231639301840456
525 2240241994772243656354
526 2366982660687308450249
527 2500764880808715465053
528 2641972865304027909157
529 2791011413254873212068
530 2948306996475424424475
531 3114308899006347130413
532 3289490415829419341816
533 3474350113069892267757
534 3669413153561394764154
535 3875232690305647540646
536 4092391332062537446447
537 4321502683896538395589
538 4563212967310021072191
539 4818202723114415696643
540 5087188602102319517106
541 5370925247031052491821
542 5670207271454259273020
543 5985871339309711691035
544 6318798351318409946884
545 6669915742542557159675
546 7040199897725336970147
547 7430678689245605393435
548 7842434144932084865447
549 8276605251106509971488
550 8734390898781067091979
551 9217052978971590172763
552 9725919635797383105338
553 10262388683982533481846
554 10827931200245822151766
555 11424095295915058280545
556 12052510081146763289274
557 12714889828882034278853
558 13413038349898341453906
559 14148853587964632177314
560 14924332447531153695868
561 15741575863927573989868
562 16602794129674274759415
563 17510312487944840598695
564 18466577008069596207591
565 19474160755290747419718
566 20535770271065746631302
567 21654252377420730627789
568 22832601323190926034471
569 24073966287071251848887
570 25381659257000483329395
571 26759163302366585998064
572 28210141260402738557137
573 29738444854983039578102
574 31348124271208534850129
575 33043438205885885285907
576 34828864419501962463878
577 36709110811878860393817
578 38689127049534478313222
579 40774116769222534248102
580 42969550388328165920097
581 45281178549109197630102
582 47715046230360982587147
583 50277507556260075829910
584 52975241339140304157168
585 55815267388994655972309
586 58804963629932064309209
587 61952084059719456482374
588 65264777596441684306315
589 68751607852074333504070
590 72421573881163868463786
591 76284131948433829173318
592 80349218368065460755069
593 84627273462888109245553
594 89129266701210483762203
595 93866723064375342389651
596 98851750708219737008524
597 104097069976842232742140
598 109616043837822535278686
599 115422709803129664818287
600 121531813411387457155288
601 127958843342133286422478
602 134720068244873719985575
603 141832575360591294839897
604 149314311026309773067044
605 157184123148066683891963
606 165461805741435016337739
607 174168145633377846925160
608 183324971433910253083879
609 192955204880597337192814
610 203082914674567395720633
611 213733372921199535860384
612 224933114305322397587723
613 236709998125182514064927
614 249093273327216849331050
615 262113646678046725734025
616 275803354229062150014065
617 290196236223330063620408
618 305327815614771398217210
619 321235380363922688496488
620 337958069696157863662238
621 355536964502651992078986
622 374015182087373136799634
623 393437975457861633803045
624 413852837382109222350720
625 435309609428426974572089
626 457860596231403739076677
627 481560685221778818996548
628 506467472086044775829106
629 532641392216509921633153
630 560145858442451603452011
631 589047405328149077854426
632 619415840355534290341439
633 651324402304660460973740
634 684849927179335570416716
635 720073022021098916997275
636 757078246991226222447713
637 795954306096723115692980
638 836794246975307796866162
639 879695670151184872339748
640 924760948215174508111532
641 972097455380180581619305
642 1021817807907668282164920
643 1074040115898961791473854
644 1128888246993001779624486
645 1186492102511178295219480
646 1246987906641061379485449
647 1310518509250789111140165
648 1377233702980712435033133
649 1447290555259935098412253
650 1520853755954133145611008
651 1598095981353335538382595
652 1679198275271295867889241
653 1764350448031811614016091
654 1853751494184818877979299
655 1947610029800436180542099
656 2046144750261469778397149
657 2149584909482068972627010
658 2258170821557798494027351
659 2372154385861632254245168
660 2491799636683594917417943
661 2617383318523331213080234
662 2749195488234182552186631
663 2887540145231502971436176
664 3032735891073792930507345
665 3185116619742289803461171
666 3345032240047556221616881
667 3512849431611916016549404
668 3688952435987093148559263
669 3873743884490342032576756
670 4067645664461058996868849
671 4271099825667832732440592
672 4484569528723430857928041
673 4708540037397674593441011
674 4943519756855222275627588
675 5190041319882721822011504
676 5448662723317138798341827
677 5719968516930033723943853
678 6004571047180997878538629
679 6303111758302547654985380
680 6616262553349176439921242
681 6944727217899133197578105
682 7289242909280805348281757
683 7650581714258948054395847
684 8029552278313245585008127
685 8427001509713332836427865
686 8843816361806689790882967
687 9280925697016601996072915
688 9739302236275903171124552
689 10219964597713071528863505
690 10723979428653310361435742
691 11252463635099199947340489
692 11806586713120502827464025
693 12387573186696886131074066
694 12996705156842771278782053
695 13635324966971152594801516
696 14304837989760767298580849
697 15006715540933418616018090
698 15742497925679662217761630
699 16513797623629738116352622
700 17322302618623825824678752
701 18169779879712219685229343
702 19058079000201084464484909
703 19989136001755558735190421
704 20964977310987150927232344
705 21987723916169971457070754
706 23059595712178068126976757
707 24182916041977292182178438
708 25360116443488028113500544
709 26593741610902100912400921
710 27886454580058109297635370
711 29241042147774700172064903
712 30660420535603345916438754
713 32147641308788420839284778
714 33705897561828870568620641
715 35338530382395893892092589
716 37049035606015613979633945
717 38841070874322920332045375
718 40718463010399187095904037
719 42685215725144322015745100
720 44745517669396323789172763
721 46903750846993592651902281
722 49164499404798736244168180
723 51532558816233110548512810
724 54012945475760558817328475
725 56610906722342208545519540
726 59331931310844499492227458
727 62181760351023775526827020
728 65166398734747974407686048
729 68292127072820166565764459
730 71565514163889060543690038
731 74993430018704617961502799
732 78583059464187250494493004
733 82341916352627159486777576
734 86277858402638020919163557
735 90399102699419173912089618
736 94714241883293380583754877
737 99232261056506435933575488
738 103962555439801697566602588
739 108914948811399101416100665
740 114099712762658215962857345
741 119527586805927399357840112
742 125209799371864385589710379
743 131158089734851628449479474
744 137384730907057182597594621
745 143902553543155687099189839
746 150724970899807456495490174
747 157866004895594437063255638
748 165340313319363984880648511
749 173163218236681274257287137
750 181350735646525926727967337
751 189919606442280574950112677
752 198887328733691387020107895
753 208272191588569277263217599
754 218093310255846543490380984
755 228370662933884460903248100
756 239125129151004583808490491
757 250378529827706220905923540
758 262153669093359904282946296
759 274474377932883582257155202
760 287365559742506230471577622
761 300853237876687489268659760
762 314964605272152667334491187
763 329728076238234854507191053
764 345173340506923343033776531
765 361331419639541755974313942
766 378234725891529377381525984
767 395917123640640434141026438
768 414413993488796852774358292
769 433762299152015712116155327
770 454000657258154375669623315
771 475169410176776122065382122
772 497310702011194629292777091
773 520468557887721810840389614
774 544688966683368277341628544
775 570019967338653013306420528
776 596511738908911208846784361
777 624216694513375463602846777
778 653189579348586962704921443
779 683487572939099388551801546
780 715170395806313583767973032
781 748300420743251367433431892
782 782942788891594490560003254
783 819165530824897358602400818
784 857039692851094464591306071
785 896639468755670377136052482
786 938042337216823835054243750
787 981329205132924976705381186
788 1026584557113341066569528417
789 1073896611393455121645571537
790 1123357482446356998845244724
791 1175063350574283118401611039
792 1229114638775486546179732058
793 1285616197193734804687822414
794 1344677495471266053335763666
795 1406412823338546316303573788
796 1470941499788915014878587368
797 1538388091199798192183799913
798 1608882638778115049256681869
799 1682560895722266216667181696
800 1759564574510337682056959525
801 1840041604740185796588875238
802 1924146401965719028067235578
803 2012040147991098359498808040
804 2103891083104747216711865527
805 2199874810753957474759168363
806 2300174615182688959950428825
807 2404981792575669054664215069
808 2514495996275484807709458111
809 2628925596661616854824910263
810 2748488056305868926233078352
811 2873410321042796452055056003
812 3003929227621316187456908626
813 3140291928629878284844455742
814 3282756335417402307032498166
815 3431591579760597615093157972
816 3587078495060531457279964608
817 3749510117882129889526692847
818 3919192210685158024867273774
819 4096443806628649084102249533
820 4281597777368442862024656136
821 4475001424803732693274724440
822 4677017097769269122793385836
823 4888022834709154096342775222
824 5108413033412212982379158126
825 5338599148931514844697970372
826 5579010420858235311968637352
827 5830094631166207500653570284
828 6092318893894988084669195318
829 6366170477989277000372113217
830 6652157664668178746711890309
831 6950810640751980718886773231
832 7262682429434276121248394063
833 7588349860045963688394609161
834 7928414578422672620580397835
835 8283504099550751508243172003
836 8654272904237230370008965623
837 9041403581618038996163534950
838 9445608019394710370334318864
839 9867628643764385525001329014
840 10308239711090011455606131881
841 10768248653438388977968476898
842 11248497480202422782680300127
843 11749864238111370100932643750
844 12273264532028729084656981139
845 12819653109032072199617505752
846 13390025508372695015860844694
847 13985419780015419228677167239
848 14606918274570790365931600514
849 15255649507542814034747700569
850 15932790100936277481129196826
851 16639566805387722324246627197
852 17377258606114755735333731586
853 18147198916108256859546148322
854 18950777860133148804366307271
855 19789444653243919479333479568
856 20664710077673514721493053873
857 21578149062106239240402396470
858 22531403367509967825931479172
859 23526184383867403855531607208
860 24564276042323986587657970869
861 25647537847447902107942102751
862 26777908034489761742720186141
863 27957406856721858740765774752
864 29188140008144396527293231757
865 30472302187054081928206759093
866 31812180806194550248431651638
867 33210159855432993064967297778
868 34668723923149336751779742837
869 36190462382767476648853683962
870 37778073751119367945216589814
871 39434370225595639121937178760
872 41162282407318534762310425449
873 42964864217857136299632100492
874 44845298017309439892038752068
875 46806899931882981336265108403
876 48853125399434591309670509426
877 50987574941761768296440555870
878 53214000172793223805541656329
879 55536310052184818930691419646
880 57958577394210412236478723680
881 60485045642224684334107623225
882 63120135919388759073264485151
883 65868454366768153562775570684
884 68734799780359189689223703123
885 71724171559052343115688212532
886 74841777976023029955576702578
887 78093044786528961489812809664
888 81483624185613422968199783566
889 85019404129741611895031988336
890 88706518036958591045875159325
891 92551354880727424675881901427
892 96560569693211904639086721028
893 100741094494383844110286275170
894 105100149663988646743669765111
895 109645255774067569347090025017
896 114384245900440459765466479897
897 119325278432270460015797558643
898 124476850399593192027329090678
899 129847811339467806968525666187
900 135447377722228311020447931179
901 141285147960150077710747274573
902 147371118021732168372910281595
903 153715697675699037187678038181
904 160329727389780622911137896354
905 167224495910304437747366827399
906 174411758549663825250601163349
907 181903756209778416942972922241
908 189713235170774352277951543469
909 197853467675246960395223374771
910 206338273339667396100165027246
911 215182041425719621974946350939
912 224399754005646948812537202319
913 234007010057008999606660565364
914 244020050523644094160081179252
915 254455784381057981913248899465
916 265331815745963136460047652815
917 276666472071231133563667904516
918 288478833469141516225032046496
919 300788763207469956848613689568
920 313616939424706090373357243305
921 326984888112481284080337422067
922 340915017415170634939728909031
923 355430653298563966714569582702
924 370556076641531610011299747815
925 386316561806692694567203658655
926 402738416748283005450082886344
927 419849024717664570066047417997
928 437676887629278963672207762992
929 456251671152267201071193627169
930 475604251595522514503544265652
931 495766764656552516459857787171
932 516772656107268398491827742295
933 538656734492632918775277793408
934 561455225921052982099922901358
935 585205831028436312121201686338
936 609947784201014993956201250331
937 635721915145308837702150380620
938 662570712897031583785252379217
939 690538392364267781160893303562
940 719670963503943925042558921435
941 750016303234416424658605218669
942 781624230190980733467387242516
943 814546582435200145497023204929
944 848837298233242384550019632967
945 884552500022824073261138231282
946 921750581692984156440771813409
947 960492299305661409959903702686
948 1000840865393028792588790913118
949 1042862046969659692306406165206
950 1086624267403962560359146929491
951 1132198712298839067995368087426
952 1179659439537295399138001919096
953 1229083493654681507342634192794
954 1280551024705452097135726014169
955 1334145411798747377120143325861
956 1389953391483788792648761048582
957 1448065191172983245662985495407
958 1508574667797841006968793682284
959 1571579451900242400956443042758
960 1637181097369353607242536084276
961 1705485237042493752270483374567
962 1776601744396616246555505481526
963 1850644901565684509366144750005
964 1927733573928223612779036002253
965 2007991391518608572443390192285
966 2091546937525340469004867992458
967 2178533944149552928592079339359
968 2269091496107423090656246794911
969 2363364242070918570079918752897
970 2461502614352540625070340487441
971 2563663057151305061252668027239
972 2670008263689288343827709106565
973 2780707422580533872171105722000
974 2895936473787121158774369028436
975 3015878374530621158756178911436
976 3140723375541160045318446255017
977 3270669308040759085932796168140
978 3405921881872683159651592592290
979 3546694995204077844263641624902
980 3693211056245385836259150323041
981 3845701317446765790029574545231
982 4004406222649179501185082517563
983 4169575767685819675739867987746
984 4341469874948317803845608892428
985 4520358782451547628045203842083
986 4706523447951030690560211315026
987 4900255968687798816696229267740
988 5101860017357289728186713885847
989 5311651294921283104235030682236
990 5529958000905250593478448565403
991 5757121321847625664183503939909
992 5993495938592633177240870143376
993 6239450553144279473523049673812
994 6495368435826137612555313886513
995 6761647993519488483645678673152
996 7038703359781453974652107018474
997 7326965007674796374980319711925
998 7626880386172327484574329968535
999 7938914581031178338220558578199
1000 8263551001065806994715558957084