8 1
9 0
10 1
11 1
12 2
13 2
14 4
15 4
16 9
17 10
18 14
19 18
20 27
21 32
22 46
23 57
24 80
25 99
26 134
27 163
28 219
29 270
30 350
31 433
32 561
33 686
34 875
35 1074
36 1349
37 1652
38 2062
39 2509
40 3116
41 3783
42 4650
43 5633
44 6893
45 8305
46 10108
47 12153
48 14709
49 17630
50 21243
51 25371
52 30452
53 36271
54 43335
55 51478
56 61311
57 72598
58 86169
59 101785
60 120408
61 141867
62 167338
63 196637
64 231318
65 271194
66 318120
67 372124
68 435458
69 508202
70 593278
71 690954
72 804747
73 935328
74 1087028
75 1260860
76 1462354
77 1693013
78 1959580
79 2264528
80 2616173
81 3017831
82 3480087
83 4007580
84 4613246
85 5303716
86 6095003
87 6995922
88 8026659
89 9198890
90 10537462
91 12058316
92 13792171
93 15759665
94 17999359
95 20538170
96 23423622
97 26691050
98 30399294
99 34593690
100 39347661
101 44719239
102 50798982
103 57661790
104 65419571
105 74167144
106 84043623
107 95169233
108 107715314
109 121834570
110 137738378
111 155618664
112 175737035
113 198334264
114 223732154
115 252233474
116 284234117
117 320111537
118 360353859
119 405431373
120 455942994
121 512474629
122 575761162
123 646528765
124 725679877
125 814113046
126 912932682
127 1023250764
128 1146418174
129 1283804806
130 1437063662
131 1607880686
132 1798272741
133 2010313168
134 2246461383
135 2509259300
136 2801705481
137 3126911907
138 3488526349
139 3890356413
140 4336835987
141 4832611274
142 5383069708
143 5993874364
144 6671558818
145 7423019021
146 8256171987
147 9179397905
148 10202284264
149 11335002328
150 12589144157
151 13977044160
152 15512705418
153 17211058309
154 19089006844
155 21164604224
156 23458227299
157 25991683956
158 28789515610
159 31878026306
160 35286750316
161 39047379894
162 43195413639
163 47769000970
164 52810770635
165 58366582105
166 64487586140
167 71228855153
168 78651695264
169 86822180616
170 95813724411
171 105705506121
172 116585365592
173 128548093470
174 141698681575
175 156150508990
176 172028959990
177 189469497613
178 208621739271
179 229647384891
180 252724794169
181 278046816270
182 305825896986
183 336291805163
184 369697385326
185 406316150459
186 446448752130
187 490420503955
188 538588612530
189 591339639385
190 649097655228
191 712321614952
192 781514535809
193 857220880793
194 940036842581
195 1030607760622
196 1129639725776
197 1237897024938
198 1356215224666
199 1485498780672
200 1626735726179
201 1780995508731
202 1949445589869
203 2133349533292
204 2334085743382
205 2553146013090
206 2792156613519
207 3052877420354
208 3337225773639
209 3647276269183
210 3985287740747
211 4353704026002
212 4755184395029
213 5192605510821
214 5669095907411
215 6188039330410
216 6753113780915
217 7368296708411
218 8037909140640
219 8766623102324
220 9559511678283
221 10422059017032
222 11360217114779
223 12380419116169
224 13489643610291
225 14695431855479
226 16005960820493
227 17430064961200
228 18977319171503
229 20658066201377
230 22483510749563
231 24465753536025
232 26617898303719
233 28954093611133
234 31489654506334
235 34241113688291
236 37226359715196
237 40464699159443
238 43977013939654
239 47785836205408
240 51915527410708
241 56392368437376
242 61244763259760
243 66503346855405
244 72201217219478
245 78374063850038
246 85060432045685
247 92301875755777
248 100143258442979
249 108632934270814
250 117823091060126
251 127769964190370
252 138534227489324
253 150181245580305
254 162781519173016
255 176410981965112
256 191151508416769
257 207091262012007
258 224325274237995
259 242955852820558
260 263093241566663
261 284856097916617
262 308372245547296
263 333779231683587
264 361225185379885
265 390869467520679
266 422883649229786
267 457452268713655
268 494773947232050
269 535062268696270
270 578547052375160
271 625475374555127
272 676113019428064
273 730745664151593
274 789680533547858
275 853247772587432
276 921802333191420
277 995725562901041
278 1075427355605172
279 1161347988344726
280 1253960573499136
281 1353773179793273
282 1461331627693748
283 1577221937270018
284 1702073513744905
285 1836561969838796
286 1981412756483924
287 2137404413440212
288 2305372706497736
289 2486214369432314
290 2680891816853892
291 2890437448116040
292 3115959016167100
293 3358644573253997
294 3619768585744172
295 3900697614505848
296 4202897277116842
297 4527938767200298
298 4877506781327774
299 5253406995193767
300 5657575086692212
301 6092085305308746
302 6559160739790009
303 7061183134050750
304 7600704570160760
305 8180458704110719
306 8803374055909275
307 9472586864715607
308 10191456202423220
309 10963578672703772
310 11792805596172128
311 12683259807124873
312 13639355189104795
313 14665815860310484
314 15767698374279772
315 16950413621587140
316 18219752055129987
317 19581908678314929
318 21043511699388020
319 22611651029063683
320 24293910820114056
321 26098401950848920
322 28033798969832545
323 30109377103197608
324 32335054189336213
325 34721432823021875
326 37279847939774069
327 40022414787158600
328 42962082908550391
329 46112690720833140
330 49489026741289009
331 53106891657284315
332 56983167747313971
333 61135889439996343
334 65584322008103953
335 70349041741716886
336 75452025128936592
337 80916739918990175
338 86768246157213858
339 93033299574312856
340 99740466023884599
341 106920238816669767
342 114605168302275598
343 122829994980975928
344 131631796190662645
345 141050137058404788
346 151127236509487732
347 161908138381382843
348 173440899247384184
349 185776782318095043
350 198970469884667871
351 213080282960267031
352 228168421508924347
353 244301213149977909
354 261549384730970736
355 279988343845132427
356 299698485749847256
357 320765511912639614
358 343280776786204501
359 367341648123703221
360 393051898677446853
361 420522113626612469
362 449870132894142281
363 481221511689279528
364 514710019854128471
365 550478162266513476
366 588677742414388909
367 629470450252092499
368 673028498086068297
369 719535284409212787
370 769186111189357418
371 822188933254364921
372 878765167183803820
373 939150537008314415
374 1003595986151836328
375 1072368631521217119
376 1145752791359955558
377 1224051061278544582
378 1307585472441002240
379 1396698704755997902
380 1491755391568311062
381 1593143487075355201
382 1701275735675652098
383 1816591212744508681
384 1939556978980161512
385 2070669816008939532
386 2210458088523721374
387 2359483698774337378
388 2518344182059539892
389 2687674907055550393
390 2868151433286549110
391 3060491987507407438
392 3265460115207847075
393 3483867466881022125
394 3716576779476230396
395 3964505010431596086
396 4228626689267778239
397 4509977441811705554
398 4809657756909204954
399 5128836948310705180
400 5468757386853533728
401 5830738953120489290
402 6216183791402959702
403 6626581312570882821
404 7063513532787904821
405 7528660693052609717
406 8023807253103361264
407 8550848201933654582
408 9111795785609557505
409 9708786591847725991
410 10344089099719569970
411 11020111631132329702
412 11739410820747977646
413 12504700538091753028
414 13318861387508282739
415 14184950716796126311
416 15106213269845280760
417 16086092411212463136
418 17128242068416901499
419 18236539316943059854
420 19415097765082993981
421 20668281660691078914
422 22000720889197603752
423 23417326782133957033
424 24923308918742768935
425 26524192837121988529
426 28225838851840265499
427 30034461891791228705
428 31956652570706498523
429 33999399401615280897
430 36170112384453232015
431 38476647875752150449
432 40927334987852660830
433 43531003424473794631
434 46297013019772296821
435 49235284885988433197
436 52356334458177865257
437 55671306339679496737
438 59192011260057666051
439 62930965048180295144
440 66901429957298982258
441 71117458244400291444
442 75593938367988425978
443 80346643706711961034
444 85392284192704900130
445 90748560762951069893
446 96434223054715519044
447 102469130250180662546
448 108874315531314942824
449 115672054052837424225
450 122885934932417377429
451 130540937169870368628
452 138663510035822396779
453 147281657846916368095
454 156425029713020763098
455 166125014180239740065
456 176414839404234887475
457 187329678786153944592
458 198906762758946794399
459 211185496666951120598
460 224207585484567418505
461 238017165329639336422
462 252660942580688653915
463 268188340568963250871
464 284651654723316658696
465 302106216157260217294
466 320610564651311211899
467 340226631041534346530
468 361019930049414007319
469 383059763589291656887
470 406419435677802841918
471 431176479011239050996
472 457412894432737570975
473 485215403389523984358
474 514675714708622079943
475 545890805830954124160
476 578963219948348320013
477 614001379229245734386
478 651119915704452745470
479 690440020051189136435
480 732089809985468204225
481 776204718561148450780
482 822927904237025985113
483 872410683079057007590
484 924812985124518712391
485 980303835353264114824
486 1039061861473900366757
487 1101275829058796937111
488 1167145206433459006687
489 1236880759954990526096
490 1310705182301460911277
491 1388853754520760767744
492 1471575044697541031522
493 1559131644115536094025
494 1651800944032679928860
495 1749875954091728615701
496 1853666165767095156025
497 1963498462034147755812
498 2079718076971978133851
499 2202689606669940821677
500 2332798075488389865618
501 2470450059250946420722
502 2616074869790440065735
503 2770125802657903636762
504 2933081452824083822962
505 3105447100443071248998
506 3287756171953327226980
507 3480571778877405002323
508 3684488340084092360841
509 3900133290200302623713
510 4128168880471860219297
511 4369294075125051297042
512 4624246550114411445115
513 4893804797716079051767
514 5178790344494815320424
515 5480070086558368230450
516 5798558750331908038694
517 6135221483272990602425
518 6491076583531724338631
519 6867198373541661990795
520 7264720227392416077403
521 7684837757598357406902
522 8128812172042571820607
523 8597973807410368832382
524 9093725850908722523049
525 9617548257364772011189
526 10171001874615218162391
527 10755732785144971758508
528 11373476878110429333544
529 12026064660667052785961
530 12715426324077878954816
531 13443597074590412792532
532 14212722746029567592374
533 15025065705278536355197
534 15883011069209002886523
535 16789073245546476663210
536 17745902818001495705796
537 18756293789609621621206
538 19823191206551713536884
539 20949699178011558377897
540 22139089316471481305851
541 23394809615791132075887
542 24720493793804782847197
543 26119971118762664628128
544 27597276748912695092329
545 29156662606739217243976
546 30802608819964746130208
547 32539835753255573928925
548 34373316665818364626250
549 36308291021510136419036
550 38350278490028553392109
551 40505093668768639997411
552 42778861567620618621939
553 45178033889570412665908
554 47709406153443625509155
555 50380135695273643730603
556 53197760599094727769909
557 56170219597636734501182
558 59305872998614846697343
559 62613524681502783446617
560 66102445225848035996055
561 69782396220887500238502
562 73663655823406538530827
563 77757045618972026738098
564 82073958859936788385743
565 86626390141271760199112
566 91426966594700681439303
567 96488980668728740287661
568 101826424582801515306969
569 107454026530388786356167
570 113387288727741575950970
571 119642527391055703606068
572 126236914748122851669830
573 133188523175950097103774
574 140516371580662207708509
575 148240474120802118861622
576 156381891401564802434577
577 164962784251689972365030
578 174006470222849766391989
579 183537482934939000514898
580 193581634420589853859202
581 204166080605175761810372
582 215319390090410779780600
583 227071616391957974329436
584 239454373815357754537917
585 252500917136256989430476
586 266246225287011764861174
587 280727089232766164108896
588 295982204258548249076283
589 312052266869314358946677
590 328980076545817273372882
591 346810642578931840724716
592 365591296248693185474893
593 385371808593436088315491
594 406204514060910405295006
595 428144440311769026654510
596 451249444495372615430703
597 475580356295786820985801
598 501201128098669208157771
599 528178992607107016548138
600 556584628290794433195551
601 586492333029764501517777
602 617980206373968568193287
603 651130340816326897619030
604 686029022540965794560987
605 722766942084236186925869
606 761439415414502353030564
607 802146615912172929794401
608 844993817804446032929534
609 890091651584397625676180
610 937556372021976267870653
611 987510139349374112615492
612 1040081314286470720723579
613 1095404767546792143112556
614 1153622204553326335559542
615 1214882506068230265122533
616 1279342085535444431371575
617 1347165263909991831875283
618 1418524662849247503823788
619 1493601617116430780803771
620 1572586607155084504542382
621 1655679712768639288287090
622 1743091088955188744653900
623 1835041464923480865116817
624 1931762667440233142125267
625 2033498169635506951805534
626 2140503666525648111906754
627 2253047678490913440032821
628 2371412184086986412699383
629 2495893283548440596151323
630 2626801894494304979215518
631 2764464481326275502734551
632 2909223819972971306726965
633 3061439799615893973518901
634 3221490263207168738633313
635 3389771888573641566895852
636 3566701112088772605879658
637 3752715096880907756339066
638 3948272747746762091866927
639 4153855774929203472836283
640 4369969809133078818653186
641 4597145570146703497389184
642 4835940091666797067939511
643 5086938004922720246019588
644 5350752883942723693370627
645 5628028655307827468909715
646 5919441075503780709906966
647 6225699278989998093175846
648 6547547400388570145933625
649 6885766274211211817386219
650 7241175215847079276447062
651 7614633887556348543291665
652 8007044253541999323386329
653 8419352628202363947969062
654 8852551822018796184763934
655 9307683389572145094891822
656 9785839984559649672330589
657 10288167826733597609182136
658 10815869286089205508852143
659 11370205589690594723879464
660 11952499656960260746602495
661 12564139069331969011440512
662 13206579180636336920790432
663 13881346374677602161699517
664 14590041476964800493413745
665 15334343327666254504007138
666 16116012523399212423852688
667 16936895335590503827222941
668 17798927813728264537366962
669 18704140081969276599344193
670 19654660838195189367114640
671 20652722064778156752187308
672 21700663960993252237607382
673 22800940107207610140134156
674 23956122871705022621678268
675 25168909071225434070207639
676 26442125897083680184807098
677 27778737118983719196634570
678 29181849579490163620476716
679 30654719992405374301310265
680 32200762059211480296580239
681 33823553918061402151398553
682 35526845940784893802625872
683 37314568893742636100812185
684 39190842479419939996250519
685 41159984276065374531943308
686 43226519093820953976073304
687 45395188766255891553876407
688 47670962397446768284387156
689 50059047085269270881306874
690 52564899142894321581885000
691 55194235841066484953472690
692 57953047695174923032307586
693 60847611321781381676118968
694 63884502890815346866220242
695 67070612200376836625735882
696 70413157402755505180548767
697 73919700411088801045210639
698 77598163017882719331976846
699 81456843757524845500802683
700 85504435546863649655250996
701 89750044138935338812397251
702 94203207427019105638452946
703 98873915637320098460190274
704 103772632450846999183567671
705 108910317096291606227318452
706 114298447458167246093993863
707 119949044245837225071637225
708 125874696271710838368741044
709 132088586888405663520277557
710 138604521637534285941292533
711 145436957164455786125705828
712 152601031456422454339659301
713 160112595463410753771041285
714 167988246164265503228704227
715 176245361142837983507985201
716 184902134742409093802856909
717 193977615868951946741134228
718 203491747517691578059847533
719 213465408099914203979805606
720 223920454651198907059157197
721 234879768004992650651802852
722 246367300020013415559524486
723 258408122952991283064231618
724 271028481073193118874354922
725 284255844618504382607269089
726 298118966198180259860530741
727 312647939751037162327552256
728 327874262173630599148878120
729 343830897736985924020626453
730 360552345416695952144691313
731 378074709265614942787934035
732 396435771965137775033001754
733 415675071695899953185910733
734 435833982476047796313783784
735 456955798120545830944421045
736 479085819982902616064634547
737 502271448646527728254750101
738 526562279741497330428215221
739 552010204068897844545033347
740 578669512224186540171048706
741 606597003918011449885069202
742 635852102202965543936616267
743 666496972822420496354926104
744 698596648908444691752270937
745 732219161264207457862010319
746 767435674478026424592064584
747 804320629125404599348122855
748 842951890328128808847293730
749 883410902949554238785910287
750 925782853718975807876964497
751 970156840588980798008707707
752 1016626049644591570270794273
753 1065287939895025430229109431
754 1116244436295046261756130298
755 1169602131356016456848617730
756 1225472495724241046042773064
757 1283972098118544512405221506
758 1345222835037951101702911766
759 1409352170666010258616500760
760 1476493387418806473946674024
761 1546785847600802615418697906
762 1620375266654861214358530758
763 1697413998511463692024384323
764 1778061333566181809513788832
765 1862483809834834520694366271
766 1950855537861789478446461832
767 2043358539979100059855507130
768 2140183104542352212378712692
769 2241528155793341844190625089
770 2347601640030223497954524949
771 2458620928792208223201785921
772 2574813239798939213079084416
773 2696416076413492511197281162
774 2823677686433741543171311601
775 2956857541048231545622531428
776 3096226834831469640207348221
777 3242069007687756815753932912
778 3394680289694662200162713815
779 3554370269834517228015090471
780 3721462489647762473517267993
781 3896295062882577939162232107
782 4079221322264452268259915804
783 4270610494553551591568256031
784 4470848405111055156424652152
785 4680338213243747767944262631
786 4899501179653885294664110061
787 5128777467373726531259037208
788 5368626977626636422834718838
789 5619530222113661691953210130
790 5881989233292172884229721859
791 6156528514275177157716842729
792 6443696030053208735243688285
793 6744064241808156880002604615
794 7058231186167766836587356669
795 7386821601322908979359085799
796 7730488102015661352405451397
797 8089912405486020249686487856
798 8465806610558120318843949859
799 8858914532133569499793827226
800 9270013093460274624846833690
801 9699913778639401790819209915
802 10149464147942224599576881749
803 10619549418611065045726896697
804 11111094113936666040511984329
805 11625063783515661587446860361
806 12162466797719712714882084873
807 12724356219528828990227025571
808 13311831757019868656231665259
809 13926041799932597989067533525
810 14568185543885603631938742987
811 15239515205957053207435714114
812 15941338335507591978033130065
813 16675020224277629545519261667
814 17441986419966958167491155631
815 18243725347672903952101636688
816 19081791043753393387277646516
817 19957806006863984227922098416
818 20873464171123772058465465133
819 21830534006563362295832589307
820 22830861752230924642267795578
821 23876374787547540959603266316
822 24969085147744237773597774410
823 26111093189446614541103053843
824 27304591412734012276867200690
825 28551868446253538995956591934
826 29855313202251776754463757113
827 31217419208661869296779803385
828 32640789125689425363278810086
829 34128139454638834436753136420
830 35682305447052449649549213626
831 37306246222558472559063947687
832 39003050104181401372023853936
833 40775940180219590116660790661
834 42628280102181874253551955619
835 44563580128655467476153993594
836 46585503425396513650132740254
837 48697872632346931291903029742
838 50904676708734720803758678154
839 53210078067861800837223330081
840 55618420013674116749248104439
841 58134234491693155207406762679
842 60762250167418833312238484101
843 63507400845838699764206198498
844 66374834246252633413510341318
845 69369921147191103693705270344
846 72498264916826235674397302953
847 75765711444891312473398071539
848 79178359492796254674452314116
849 82742571479294408498130319688
850 86464984719782712195719043784
851 90352523138040708526558956342
852 94412409469999869928653105805
853 98652177979918249946620054107
854 103079687710185517884402315876
855 107703136286832036453035857042
856 112531074303734895507118780433
857 117572420309432774208130793954
858 122836476421455544334405603067
859 128332944594069568482890823106
860 134071943566414495177731190768
861 140064026519084659485047940206
862 146320199468370353680419780028
863 152851940428540482387945800023
864 159671219373804596785372630454
865 166790519032854706603072418850
866 174222856550245646258090028402
867 181981806050239116205415483341
868 190081522140204969561596173172
869 198536764392152005647645977545
870 207362922842547874304518107619
871 216576044552187808501534135664
872 226192861269587658003259519316
873 236230818243108029459465315490
874 246708104228870779304668008896
875 257643682743402231639433537907
876 269057324611941704738259735625
877 280969641865380261740293544950
878 293402123040960542164715698536
879 306377169944060386313603696760
880 319918135930723537612560803885
881 334049365772971378484166595820
882 348796237171458779306118631594
883 364185203982600968000355437447
884 380243841230031016796534195536
885 397000891973020003280865577098
886 414486316107444351564086284557
887 432731341177882647718397507527
888 451768515282613899270892969787
889 471631762156530335226189443276
890 492356438520423583077062970757
891 513979393788606952785649209504
892 536539032230558676460277707701
893 560075377686058568139755802753
894 584630140937310971551887525946
895 610246789845640802659316462236
896 636970622364691801510461840805
897 664848842546480744663840444141
898 693930639661351047512307285666
899 724267270557650804451854729703
900 755912145392024818703243840253
901 788920916866377115825022886368
902 823351573113029361667999820664
903 859264534375183429879219039228
904 896722753635701617872705882204
905 935791821353249661682576358992
906 976540074471223670305527461544
907 1019038709871398094784196807528
908 1063361902451115597971519002494
909 1109586928009878313824125672663
910 1157794291138631461343145656355
911 1208067858312632795226607919774
912 1260494996396823624558055636498
913 1315166716780828017886014485858
914 1372177825369366221468546997004
915 1431627078662735507463336792193
916 1493617346171358217795383066947
917 1558255779417971915635620808241
918 1625653987791124097856533214573
919 1695928221523972683377457163438
920 1769199562083280043091123722168
921 1845594120264650685740563765865
922 1925243242301810774864347205502
923 2008283724309778200090324747006
924 2094858035394448823542849877186
925 2185114549774132877748736987880
926 2279207788272253744722887861724
927 2377298669554462493856727112407
928 2479554771498179272939234377885
929 2586150603097727356532288276385
930 2697267887324146957615780185797
931 2813095855375131175785901563423
932 2933831552767701932748416674829
933 3059680157743893265811433938712
934 3190855312478236555372259038205
935 3327579467594886936619251399400
936 3470084240522214120526091887617
937 3618610788233229333709192069417
938 3773410194941773928112419653467
939 3934743875346564504758498938249
940 4102883994038434866771982829979
941 4278113901710031189664306207209
942 4460728588832284982335139572898
943 4651035157487786887315562894466
944 4849353312078216377772588389580
945 5056015869650809290884980047439
946 5271369290617992860658901632739
947 5495774230674330370711497842953
948 5729606114746344471873513330752
949 5973255733843155417502450785270
950 6227129865709752547771880977478
951 6491651920219621400173888615227
952 6767262610479975415485700117404
953 7054420650660478061517909491865
954 7353603481595716077268265244310
955 7665308025252265096592870768869
956 7990051469193631349314379980476
957 8328372082220104343224407860015
958 8680830062406301357920214019154
959 9048008418806350633099685820049
960 9430513888145963390089538717512
961 9828977887871488466951484961289
962 10244057506979177021195561938980
963 10676436536102688666127607317036
964 11126826538394128278014885205959
965 11595967962792971000519873788906
966 12084631301338931060340632921151
967 12593618292248489811480951271593
968 13123763170541276645676214629819
969 13675933968071099612497240395198
970 14251033864888046544356843703051
971 14850002593932002574171846024776
972 15473817901135092814257187534830
973 16123497063090213008742723687807
974 16800098464525935630747482383071
975 17504723237913899665688755402742
976 18238516967624333468419483293622
977 19002671461137818346774176391369
978 19798426589917847097283708354683
979 20627072202648333695041263932223
980 21489950113644108049194431815606
981 22388456169349719722235564559656
982 23324042395953748567712024607250
983 24298219231261383442830604859950
984 25312557844088508197880816977840
985 26368692544564999706906402102344
986 27468323288864677952040936912983
987 28613218282013392439594017364154
988 29805216682566423836997895581661
989 31046231413090729717580130416103
990 32338252080537972002512208322502
991 33683348010749700885204281995602
992 35083671401498003993507357666988
993 36541460598632293864572339205357
994 38059043500077237838795680342331
995 39638841092607028618345332003316
996 41283371126508858711939114407164
997 42995251933442456044104763571042
998 44777206393004543692401529602253
999 46632066053715923157039941771490
1000 48562775414366308754856725771978