9 0
10 0
11 1
12 1
13 3
14 4
15 8
16 11
17 19
18 26
19 41
20 56
21 83
22 111
23 158
24 209
25 287
26 375
27 503
28 648
29 852
30 1086
31 1403
32 1770
33 2255
34 2817
35 3546
36 4393
37 5469
38 6723
39 8294
40 10120
41 12382
42 15011
43 18228
44 21965
45 26497
46 31749
47 38069
48 45383
49 54114
50 64204
51 76176
52 89975
53 106259
54 124998
55 146987
56 172247
57 201755
58 235577
59 274927
60 319950
61 372117
62 431702
63 500507
64 578938
65 669220
66 771965
67 889863
68 1023817
69 1177116
70 1350987
71 1549470
72 1774244
73 2030202
74 2319637
75 2648511
76 3019823
77 3440869
78 3915595
79 4452829
80 5057741
81 5741076
82 6509447
83 7375957
84 8349085
85 9444683
86 10673604
87 12055091
88 13602814
89 15340175
90 17284413
91 19463810
92 21900057
93 24627427
94 27672936
95 31078135
96 34876675
97 39118710
98 43846085
99 49119429
100 54990381
101 61532263
102 68808788
103 76908307
104 85909296
105 95918317
106 107031521
107 119377411
108 133073713
109 148274981
110 165125137
111 183810129
112 204505187
113 227433971
114 252809675
115 280900705
116 311966066
117 346327890
118 384299865
119 426268403
120 472613069
121 523796557
122 580277548
123 642609939
124 711346637
125 787150335
126 870686923
127 962748019
128 1064134587
129 1175791910
130 1298681477
131 1433931294
132 1582694459
133 1746315249
134 1926175000
135 2123874875
136 2341066803
137 2579656605
138 2841618006
139 3129216755
140 3444808525
141 3791085421
142 4170854903
143 4587313311
144 5043803527
145 5544116554
146 6092228859
147 6692633863
148 7350055676
149 8069816428
150 8857523570
151 9719474616
152 10662319271
153 11693504313
154 12820906552
155 14053325298
156 15400083071
157 16871568054
158 18478804092
159 20234046881
160 22150318766
161 24242068337
162 26524666375
163 29015132371
164 31731593878
165 34694085303
166 37923965547
167 41444801339
168 45281739443
169 49462479844
170 54016605465
171 58976652726
172 64377393393
173 70257018533
174 76656368590
175 83620238395
176 91196560054
177 99437839677
178 108400287526
179 118145407221
180 128739069886
181 140253267276
182 152765136384
183 166358891514
184 181124794613
185 197161293684
186 214573936728
187 233477732966
188 253996020489
189 276263071762
190 300422911652
191 326632203494
192 355059018198
193 385886025109
194 419309227204
195 455541487079
196 494811228751
197 537366347408
198 583472883046
199 633419349052
200 687515400907
201 746096627180
202 809523219682
203 878185292454
204 952501567039
205 1032925270566
206 1119942871326
207 1214080617909
208 1315903342516
209 1426021730727
210 1545091219051
211 1673820069422
212 1812968414900
213 1963357227941
214 2125867548615
215 2301450469419
216 2491126594077
217 2695997146487
218 2917243741480
219 3156140745309
220 3414055420550
221 3692461708480
222 3992940828322
223 4317196637221
224 4667056807338
225 5044489946554
226 5451607457780
227 5890682657251
228 6364153446919
229 6874643656035
230 7424966711553
231 8018149465941
232 8657437035307
233 9346319445624
234 10088537844622
235 10888114292370
236 11749359624427
237 12676906764773
238 13675720507334
239 14751134818248
240 15908864855689
241 17155048732851
242 18496262187982
243 19939565350907
244 21492520477187
245 23163244377817
246 24960429705162
247 26893403725119
248 28972153765753
249 31207393111914
250 33610591245944
251 36194047798292
252 38970928316379
253 41955347250220
254 45162410148683
255 48608306798906
256 52310360798183
257 56287134171326
258 60558485416328
259 65145687007013
260 70071493232487
261 75360272189796
262 81038084828424
263 87132833312472
264 93674352897424
265 100694578682691
266 108227652247550
267 116310109090970
268 124981002113114
269 134282112412715
270 144258092005189
271 154956700873177
272 166428971724683
273 178729476581806
274 191916516638194
275 206052422177973
276 221203771028000
277 237441725949028
278 254842285742528
279 273486664802891
280 293461581340485
281 314859684479703
282 337779884675938
283 362327834271768
284 388616305968198
285 416765733521513
286 446904644737186
287 479170269945308
288 513709036861658
289 550677255265282
290 590241682151718
291 632580292117957
292 677882922143310
293 726352138506395
294 778203971765091
295 833668892180076
296 892992646969265
297 956437357733426
298 1024282473395585
299 1096826004946975
300 1174385609230164
301 1257299977994789
302 1345930069769346
303 1440660672348046
304 1541901801942782
305 1650090460748154
306 1765692225024052
307 1889203221788590
308 2021151930387605
309 2162101405355005
310 2312651318826394
311 2473440460105404
312 2645149049739657
313 2828501549767679
314 3024269284313029
315 3233273598666528
316 3456388825268091
317 3694545834632717
318 3948735390438681
319 4220012140185839
320 4509498408728132
321 4818388682394884
322 5147953896007694
323 5499546470921829
324 5874605157360416
325 6274660693734507
326 6701341273930869
327 7156378903412661
328 7641615569169051
329 8159010377423297
330 8710646513431993
331 9298739255339150
332 9925643821852146
333 10593864368118466
334 11306062830664987
335 12065069024082905
336 12873890605834194
337 13735724406149972
338 14653967650330679
339 15632230670013601
340 16674349536529492
341 17784400319557161
342 18966713303469927
343 20225888978420455
344 21566814032421466
345 22994679281750185
346 24514997653766224
347 26133624288202448
348 27856776751220613
349 29691057565656794
350 31643476925582121
351 33721477943807923
352 35932962167222733
353 38286317863919943
354 40790448674878662
355 43454805299872180
356 46289417660784124
357 49304930387236100
358 52512638909863270
359 55924529193526824
360 59553318227652842
361 63412498505856726
362 67516383435189806
363 71880157118613279
364 76519925264581442
365 81452770893374403
366 86696811395701478
367 92271260854289541
368 98196493975521762
369 104494115796981046
370 111187033298397342
371 118299533354546658
372 125857362924345292
373 133887816205501228
374 142419824404058758
375 151484053156143514
376 161113002993568735
377 171341118219676486
378 182204899313738967
379 193743024581243784
380 205996475881709215
381 219008674523166550
382 232825621853688116
383 247496051036400655
384 263071584219299151
385 279606902010051366
386 297159919132875837
387 315791973626898013
388 335568023112322286
389 356556855963823695
390 378831310546670354
391 402468510867035690
392 427550111404114145
393 454162560018661359
394 482397371299148133
395 512351419820604914
396 544127245248482834
397 577833379381963058
398 613584686621185042
399 651502728610276776
400 691716144072283970
401 734361055290587770
402 779581491759722959
403 827529843210252083
404 878367332016612594
405 932264517989379826
406 989401825024478971
407 1049970103462665546
408 1114171217068404310
409 1182218669391108159
410 1254338257832083021
411 1330768771147255971
412 1411762718099315934
413 1497587104023680542
414 1588524242383301394
415 1684872619181758693
416 1786947796647608008
417 1895083375235295479
418 2009631999668658428
419 2130966429330499746
420 2259480658007193800
421 2395591104636736389
422 2539737859328472618
423 2692386007735417600
424 2854027017281804740
425 3025180209860336678
426 3206394303705906913
427 3398249050700651811
428 3601356950998695563
429 3816365072974370160
430 4043956959540511766
431 4284854650714086062
432 4539820802605246532
433 4809660934712482584
434 5095225784810028569
435 5397413805450564998
436 5717173780459904044
437 6055507597741026627
438 6413473155829970617
439 6792187442978816017
440 7192829765260705146
441 7616645165098314284
442 8064948005750685000
443 8539125765977063384
444 9040643019435593048
445 9571045646056103240
446 10131965248964664808
447 10725123827430285578
448 11352338678430601338
449 12015527580775921730
450 12716714233403494017
451 13458034005504146326
452 14241739969121287584
453 15070209275871366536
454 15945949847471649808
455 16871607446008590291
456 17849973092694541484
457 18883990905648033286
458 19976766324544853016
459 21131574797609540219
460 22351870897939442716
461 23641297949937955017
462 25003698132040291355
463 26443123142214698532
464 27963845391687186384
465 29570369819498545223
466 31267446292692151212
467 33060082691335953938
468 34953558642618146742
469 36953440010317715660
470 39065594103455413562
471 41296205718055294091
472 43651793975531686627
473 46139230079852204416
474 48765755956854825091
475 51539003906726257151
476 54467017233080628264
477 57558271989176380757
478 60821699804995706634
479 64266711946003844879
480 67903224567840752572
481 71741685328848435487
482 75793101325513872512
483 80069068524674482703
484 84581802658730437540
485 89344171770604829968
486 94369730376227002203
487 99672755445199461462
488 105268284169393903694
489 111172153735150000535
490 117401043071284651822
491 123972516804808197727
492 130905071399554443094
493 138218183727150521888
494 145932362049163252750
495 154069199678775578069
496 162651431305163231081
497 171702992269395856268
498 181249080780135661741
499 191316223380097555118
500 201932343657537543336
501 213126834537663273342
502 224930634155217972590
503 237376305669034453949
504 250498121027879557577
505 264332149076424670624
506 278916348019973784776
507 294290662667120166481
508 310497126479652157845
509 327579968881741672953
510 345585727869934364535
511 364563368411576577128
512 384564406687110366000
513 405643040702423475723
514 427856287342495255127
515 451264126434319747640
516 475929651908235742491
517 501919230670956766510
518 529302669299664518514
519 558153389219565690439
520 588548610497100768824
521 620569544964478315723
522 654301598833388132073
523 689834585571363540925
524 727262949227496645841
525 766685999043661046212
526 808208155570311176349
527 851939209191057731163
528 897994591311305185246
529 946495659189018799709
530 997569994703425625457
531 1051351718119884980823
532 1107981817191991126179
533 1167608492746215785052
534 1230387521140604124837
535 1296482634837407438101
536 1366065921537395672597
537 1439318243218435531719
538 1516429675588666014712
539 1597599969408458988359
540 1683039034261050563778
541 1772967446347308591753
542 1867616980961803521771
543 1967231171357415223238
544 2072065894741419132555
545 2182389987253530232533
546 2298485888763925458633
547 2420650319497453520888
548 2549194989427422858672
549 2684447342614451704487
550 2826751337550444325645
551 2976468265867265214689
552 3133977610599220678247
553 3299677946559122392789
554 3473987884159749055618
555 3657347059458177720635
556 3850217171912496443061
557 4053083072865188336910
558 4266453906416793908652
559 4490864305961767116915
560 4726875648242302140571
561 4975077368472270342368
562 5236088338599029188184
563 5510558312560155142806
564 5799169440836518427091
565 6102637858490532069453
566 6421715349248495269969
567 6757191090176837439862
568 7109893479794806460610
569 7480692054566259405763
570 7870499496925279998200
571 8280273740205828088313
572 8711020173973704464472
573 9163793955596292808381
574 9639702431926269007854
575 10139907677441155462653
576 10665629153130352915431
577 11218146493022741229137
578 11798802423103115678328
579 12409005820110465182991
580 13050234915468053323075
581 13724040652491358087756
582 14432050202674746752914
583 15175970649913823122302
584 15957592849069195181054
585 16778795468502361593437
586 17641549223653323369616
587 18547921312132957957241
588 19500080058128027543833
589 20500299777508834049278
590 21550965872236190614739
591 22654580166455856615400
592 23813766493752967715325
593 25031276549041222839736
594 26309996015519331995678
595 27652950981352392052290
596 29063314657562694770797
597 30544414413075248916870
598 32099739139555014975708
599 33732946963382863753649
600 35447873318669390645093
601 37248539400179500381742
602 39139161011448889284971
603 41124157828626274131978
604 43208163096835310123107
605 45396033781398090045206
606 47692861192369650370496
607 50103982106693475468034
608 52634990408238764529342
609 55291749272171593067233
610 58080403915902092113623
611 61007394945391464063089
612 64079472321227661132669
613 67303709975791429673859
614 70687521108290588977047
615 74238674191746329175625
616 77965309721299063358018
617 81875957740923790385604
618 85979556180752586148652
619 90285470045365839889505
620 94803511488342233783531
621 99543960816989374633698
622 104517588465923325818651
623 109735677987293384612217
624 115210050100009999678176
625 120953087849988229049004
626 126977762927793821554002
627 133297663200291727630187
628 139927021507083204168220
629 146880745783322772639207
630 154174450564503049705917
631 161824489940229461618879
632 169847992017813655057576
633 178262894968615824836047
634 187087984723683539671430
635 196342934398044834364932
636 206048345516442189136719
637 216225791126857241371819
638 226897860881418589263269
639 238088208178648069337531
640 249821599454060453776884
641 262123965721344556216799
642 275022456459234468675088
643 288545495955296481038391
644 302722842210564918983665
645 317585648526037657859718
646 333166527884584150680861
647 349499620259918155233489
648 366620662976672429675666
649 384567064264799317496390
650 403377980143760049138275
651 423094394792308967622765
652 443759204551784682302247
653 465417305732394857543369
654 488115686383968834798648
655 511903522215538253745953
656 536832276839992754285642
657 562955806544339965374568
658 590330469777906069228742
659 619015241576582747925019
660 649071833132976806437463
661 680564816749673507331332
662 713561756404545631841263
663 748133344186084290117877
664 784353542848450063970173
665 822299734766788187430602
666 862052877565110196604318
667 903697666721810705233667
668 947322705449722481397138
669 993020682182428119505864
670 1040888555990501819438995
671 1091027750288356208077519
672 1143544355184494762454865
673 1198549338867305606461695
674 1256158768410884768943812
675 1316494040427203272997361
676 1379682121983574644578145
677 1445855802248865941167557
678 1515153955324897233054780
679 1587721814766802861748204
680 1663711260289567504057825
681 1743281117208314285862481
682 1826597469153887065557474
683 1913833984658877694921187
684 2005172258203835111494319
685 2100802166370470424043388
686 2200922239743986438777308
687 2305740051267445585417125
688 2415472621747251550208701
689 2530346843273571447439776
690 2650599921316664127242359
691 2776479836329074829190426
692 2908245825681917226140027
693 3046168886836998052762793
694 3190532302656082289137046
695 3341632189826989633150486
696 3499778071387212762204310
697 3665293474409342306978791
698 3838516553915233673980290
699 4019800744175014305063286
700 4209515438551543727284876
701 4408046699146066714867061
702 4615797997507410152798144
703 4833190987768592023123561
704 5060666313583674297694745
705 5298684450346055091902249
706 5547726584180993770360795
707 5808295529320862868286912
708 6080916685486161696076903
709 6366139037018891352063167
710 6664536195532712528600408
711 6976707487976303439821846
712 7303279092027807959389894
713 7644905220879301057486208
714 8002269359495726354598165
715 8376085554583495073636494
716 8767099760533960976494441
717 9176091243768122285573373
718 9603874047943908634446667
719 10051298522659708252875316
720 10519252918328306643557387
721 11008665050079682668371728
722 11520504033597709733085887
723 12055782095992939000328087
724 12615556464866958848919181
725 13200931338934753432057046
726 13813059943632201193446407
727 14453146675361599418756149
728 15122449338096967808599107
729 15822281476312538725103638
730 16554014808275673443997837
731 17319081764004185243767799
732 18118978132275733472150043
733 18955265821354048862690578
734 19829575738195252268456577
735 20743610791194342448998738
736 21699149021642302116636190
737 22698046869382270469473875
738 23742242578276619490589304
739 24833759747437537059028766
740 25974711034311369961899928
741 27167302016072212587108935
742 28413835215933493042904505
743 29716714301377840003391196
744 31078448461475866043945656
745 32501656970884306773383271
746 33989073948302993552513018
747 35543553317620335390504854
748 37168073980186448413077016
749 38865745207135950188988344
750 40639812260914208727549349
751 42493662255678859240653966
752 44430830266504532667662510
753 46455005697874557801976972
754 48570038922226112554683104
755 50779948199911768025022688
756 53088926892252076694817878
757 55501350979994050777802983
758 58021786899833695926536337
759 60654999712347997156689120
760 63405961615059524388725280
761 66279860815094660750690522
762 69282110776311755187043290
763 72418359856567783533462647
764 75694501351248265632350134
765 79116683960036051426557063
766 82691322694395235273414337
767 86425110244160362460131907
768 90325028822170138358582753
769 94398362506866595843335169
770 98652710103382369241042546
771 103095998544693476631788690
772 107736496855073951292288488
773 112582830699221993523623083
774 117643997541148477718600276
775 122929382438136555759308173
776 128448774495869878618748332
777 134212384012135897912392366
778 140230860337372945766159486
779 146515310481736723018917480
780 153077318499303833931797207
781 159928965681542424703855336
782 167082851593208599764572911
783 174552115985453266104312223
784 182350461622046679535749828
785 190492178056376194546444408
786 198992166398097349363182722
787 207865965110198262698303800
788 217129776878572609666519297
789 226800496598217989407778662
790 236895740521631809597086966
791 247433876617150921056545379
792 258434056186566686577470213
793 269916246793685539915031749
794 281901266557231619781053140
795 294410819864003296678089517
796 307467534560074843410084890
797 321095000680540164543770752
798 335317810780340613492180136
799 350161601931629637882596344
800 365653099455351596734388673
801 381820162457843588274287143
802 398691831245688140755055844
803 416298376695413846680430023
804 434671351657270558938438942
805 453843644475930982293138464
806 473849534713827964920757018
807 494724751166737648321351790
808 516506532264322840903184421
809 539233688952548638097491202
810 562946670158253552745807641
811 587687630940676673282730410
812 613500503438401561788640084
813 640431070725038990028302649
814 668527043690943425302572296
815 697838141073490118807231381
816 728416172762750621132725878
817 760315126515035495993264667
818 793591258211449701719003043
819 828303185804666687347879861
820 864511987102199427676197943
821 902281301540969805655542999
822 941677436113477504549467820
823 982769475612890866001762278
824 1025629397370344135329259725
825 1070332190665283132056344353
826 1116955980996162925341284639
827 1165582159406936174504246895
828 1216295517071772210304134579
829 1269184385349203765220588806
830 1324340781524483017375849483
831 1381860560468354861901198022
832 1441843572448670299000343448
833 1504393827341409802852548004
834 1569619665496582271090066022
835 1637633935525388082250773134
836 1708554179284665782410267510
837 1782502824346400233515027979
838 1859607384250495063384439460
839 1940000666851669918377591854
840 2023820991082625368494081118
841 2111212412469244166285202915
842 2202324957745805514609151447
843 2297314868932857112696611657
844 2396344857253596881710306619
845 2499584367280406361101144303
846 2607209851717463352656571418
847 2719405057242359230284930406
848 2836361321845095801141632597
849 2958277884121134477836527371
850 3085362204991875916040164249
851 3217830302345645472970833021
852 3355907099110320315748824552
853 3499826785289937366577598738
854 3649833194517143638887010198
855 3806180195696174951511319720
856 3969132100332148323661432772
857 4138964086167022492189560678
858 4315962637765381161763895783
859 4500426004719640436217306250
860 4692664678168916344227879180
861 4893001886354255951368905981
862 5101774109959548007585894523
863 5319331618018071261864957414
864 5546039025193383734021530634
865 5782275871276238508201097483
866 6028437223770256043271560125
867 6284934304474583328708150874
868 6552195141005293239998787363
869 6830665244235487237370703996
870 7120808312670259188078327976
871 7423106964813803164673939061
872 7738063500625022078941138206
873 8066200693202255678837659580
874 8408062611879923419127079655
875 8764215477967513955156048606
876 9135248554406873589405314289
877 9521775070675012683749096489
878 9924433184308772160662153532
879 10343886980482864428040832202
880 10780827511125807313361433712
881 11235973875117643077199788152
882 11710074341170519706974969381
883 12203907515057104383372666078
884 12718283552913487491782231449
885 13254045422411989199769458689
886 13812070213665819339427155032
887 14393270501801523294979628023
888 14998595763206908658375242562
889 15629033847541752541885858034
890 16285612507675976145484649224
891 16969400989805625828253685192
892 17681511686080442875187470683
893 18423101852168960405306398533
894 19195375392277029140727374959
895 19999584714234823745429590649
896 20837032657364364097876496438
897 21709074495946256259502730171
898 22617120021208896523620832205
899 23562635704878138676962468833
900 24547146947438096070608005956
901 25572240414377201288052707191
902 26639566463815070679695184056
903 27750841669038519990065497937
904 28907851439605921469617587499
905 30112452744821941496099485691
906 31366576943525678143555353084
907 32672232724288870506207662362
908 34031509160272738417720090331
909 35446578883157277321451457262
910 36919701380720454023476565541
911 38453226422822499019641337600
912 40049597620726735685510246285
913 41711356124879555004079542657
914 43441144466461968535483373435
915 45241710548230762902370192807
916 47115911790371709530706718771
917 49066719437308374168295603648
918 51097223031630210997569812205
919 53210635061541374876852434024
920 55410295788468720782559783126
921 57699678261723109378783605466
922 60082393527363341859930433002
923 62562196038686933160214758974
924 65142989276046673386898634671
925 67828831583987482770065061630
926 70623942233993811960463032447
927 73532707721455603394165474980
928 76559688305779159748711322762
929 79709624802910890113672952709
930 82987445639884513218966006410
931 86398274181369556156555540529
932 89947436338567694015248307290
933 93640468471198273530535973521
934 97483125593711123253997170597
935 101481389897289132933359432989
936 105641479599629994804009256591
937 109969858134952656044463196853
938 114473243697133345002396026280
939 119158619149366321344809369405
940 124033242314238635477347046032
941 129104656658635128208952651930
942 134380702388421454893467593557
943 139869527968419234004306016459
944 145579602083759178308848047219
945 151519726059306662875009470173
946 157699046754469138652379279445
947 164127069951348799632814939366
948 170813674254865272941483867452
949 177769125524175854455616107292
950 185004091855432026353965097348
951 192529659136666095329228112802
952 200357347196366554126853032059
953 208499126568112077551019325978
954 216967435894456345969561290093
955 225775199994127541840954790912
956 234935848617490422167850835877
957 244463335916155305088274411164
958 254372160653568709752591469578
959 264677387184426368173116760891
960 275394667231770973104286395138
961 286540262491717656952059931789
962 298131068096848344188041970004
963 310184636970476879744996649587
964 322719205105167125514543945775
965 335753717800132980888888168913
966 349307856893417764917671507800
967 363402069026089465560569130028
968 378057594977051524138144806265
969 393296500108506951230494199444
970 409141705963578373509268875919
971 425617023059131044054045512323
972 442747184918419756387312593447
973 460557883389839108520334333415
974 479075805299747579586774247804
975 498328670489116789430091041064
976 518345271285574019430099256092
977 539155513464318311819215204032
978 560790458753342067430639764369
979 583282368940443204872064584289
980 606664751641609309102573064173
981 630972407792559506616976329715
982 656241480927481510908035108849
983 682509508311367757629263061330
984 709815473994772938244865169459
985 738199863862355674262007433939
986 767704722749164304312297005651
987 798373713701353784964477942128
988 830252179460809809497041104189
989 863387206256083417386336532458
990 897827689985034312577881949092
991 933624404877722932736437685378
992 970830074731307070643206992614
993 1009499446812070884071778468344
994 1049689368523166748718843783521
995 1091458866940269323787578173208
996 1134869231321047872775841581027
997 1179984098698246537773749903457
998 1226869542670141419908439419738
999 1275594165506310852060786022405
1000 1326229193690926630543671022944