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 157
31 192
32 247
33 299
34 381
35 462
36 580
37 703
38 874
39 1055
40 1303
41 1569
42 1921
43 2309
44 2808
45 3363
46 4070
47 4859
48 5848
49 6964
50 8342
51 9903
52 11817
53 13988
54 16623
55 19626
56 23240
57 27363
58 32297
59 37930
60 44627
61 52286
62 61338
63 71690
64 83879
65 97813
66 114138
67 132813
68 154606
69 179513
70 208492
71 241588
72 279965
73 323779
74 374427
75 432196
76 498820
77 574726
78 662044
79 761461
80 875550
81 1005303
82 1153913
83 1322748
84 1515718
85 1734751
86 1984611
87 2267908
88 2590533
89 2955935
90 3371352
91 3841388
92 4374899
93 4977903
94 5661345
95 6432993
96 7306296
97 8291336
98 9404591
99 10658978
100 12074836
101 13668564
102 15465137
103 17485475
104 19760175
105 22315661
106 25189594
107 28415176
108 32038591
109 36101609
110 40660751
111 45768278
112 51493548
113 57901618
114 65077385
115 73101915
116 82078919
117 92108940
118 103318881
119 115833043
120 129806350
121 145392427
122 162780138
123 182158750
124 203758592
125 227812227
126 254600053
127 284407695
128 317576023
129 354454860
130 395458632
131 441014917
132 491626708
133 547816229
134 610193216
135 679394075
136 756157735
137 841258342
138 935590085
139 1040093902
140 1155850543
141 1284001517
142 1425852448
143 1582786024
144 1756377446
145 1948300000
146 2160451936
147 2394855051
148 2653795463
149 2939712609
150 3255356409
151 3603667529
152 3987950214
153 4411744357
154 4879017408
155 5394025340
156 5961526597
157 6586633196
158 7275046529
159 8032899259
160 8867017301
161 9784749255
162 10794258861
163 11904343765
164 13124758264
165 14466022717
166 15939782777
167 17558605669
168 19336381378
169 21288108821
170 23430339677
171 25780956402
172 28359666791
173 31187770186
174 34288710624
175 37687835414
176 41413008562
177 45494365399
178 49964997370
179 54860699205
180 60220736012
181 66087589341
182 72507810564
183 79531771637
184 87214619836
185 95616031042
186 104801281291
187 114841012247
188 125812426879
189 137799076320
190 150892201141
191 165190539966
192 180801837690
193 197842690946
194 216440236348
195 236732047594
196 258868033617
197 283010392231
198 309335749446
199 338035192883
200 369316673276
201 403405141350
202 440545255072
203 481001632259
204 525061908319
205 573037140602
206 625265251471
207 682111621687
208 743972980498
209 811278213662
210 884492766824
211 964119722715
212 1050704772596
213 1144837621799
214 1247157618943
215 1358355536303
216 1479179953191
217 1610439495156
218 1753010058514
219 1907837599400
220 2075946329498
221 2258442135752
222 2456521889491
223 2671477624462
224 2904707093934
225 3157718847762
226 3432144228511
227 3729743480415
228 4052419393761
229 4402224640488
230 4781377274112
231 5192269507221
232 5637485347084
233 6119811028701
234 6642255095923
235 7208060785377
236 7820728867718
237 8484032311131
238 9202042295317
239 9979145491413
240 10820073706200
241 11729924223534
242 12714193556776
243 13778801350142
244 14930128844585
245 16175046862995
246 17520959667713
247 18975837697384
248 20548267534640
249 22247490146441
250 24083457854400
251 26066878882864
252 28209282331077
253 30523070029514
254 33021590592508
255 35719199709236
256 38631344587918
257 41774633906338
258 45166934121997
259 48827450572769
260 52776837259811
261 57037290781615
262 61632675517860
263 66588632242663
264 71932720878387
265 77694546003916
266 83905919564023
267 90601005774287
268 97816506614490
269 105591828894822
270 113969295721508
271 122994339001714
272 132715740407159
273 143185853022618
274 154460875950362
275 166601109217442
276 179671266692861
277 193740769085347
278 208884100367413
279 225181144327239
280 242717590551407
281 261585320624533
282 281882870503669
283 303715873462949
284 327197586479569
285 352449397949689
286 379601426912948
287 408793104517125
288 440173856043318
289 473903766510373
290 510154356646794
291 549109344380466
292 590965527595580
293 635933654675383
294 684239428538306
295 736124501394787
296 791847616301978
297 851685743267624
298 915935376957554
299 984913833375566
300 1058960724749145
301 1138439438837514
302 1223738814587565
303 1315274828973701
304 1413492500392345
305 1518867811012415
306 1631909868334614
307 1753163095019010
308 1883209682770128
309 2022672085728285
310 2172215805617293
311 2332552229255624
312 2504441788873292
313 2688697189943776
314 2886186995992987
315 3097839298871755
316 3324645784123811
317 3567665902290918
318 3828031478033072
319 4106951449038204
320 4405717089894221
321 4725707393653806
322 5068394990989992
323 5435352258785601
324 5828258025277121
325 6248904501318225
326 6699204873428493
327 7181201165482245
328 7697072835029359
329 8249145686516543
330 8839901600746698
331 9471988636667880
332 10148232039849357
333 10871645687099182
334 11645444538818848
335 12473057599769499
336 13358142000748332
337 14304597671290645
338 15316583258921684
339 16398532734022685
340 17555173381637229
341 18791544585839548
342 20113018158241097
343 21525319580826891
344 23034550967662922
345 24647215079765965
346 26370241254108193
347 28211012542500709
348 30177394983185312
349 32277768260181699
350 34521058738535183
351 36916774089398702
352 39475040562784637
353 42206642077939901
354 45123062265498572
355 48236528585108099
356 51560059733436657
357 55107515419736136
358 58893649810149912
359 62934167668367413
360 67245784588253647
361 71846290294172598
362 76754616504755290
363 81990908283964968
364 87576600482346157
365 93534498137327566
366 99888862552679563
367 106665501868789775
368 113891867968387480
369 121597158472692779
370 129812425806071255
371 138570692024454341
372 147907071531575284
373 157858900316656269
374 168465873993022774
375 179770193210937428
376 191816718890950763
377 204653135788079937
378 218330127015553500
379 232901557974148653
380 248424672510579447
381 264960299689160391
382 282573074209547953
383 301331668791095003
384 321309041785565694
385 342582698274885812
386 365234968160583237
387 389353299441975987
388 415030570453536306
389 442365419198362982
390 471462593836668541
391 502433322407714200
392 535395706153410725
393 570475134470409165
394 607804726192607216
395 647525795180973246
396 689788345287680948
397 734751592625971832
398 782584520605042565
399 833466465626587643
400 887587739326299931
401 945150285227293246
402 1006368376152750051
403 1071469350243707598
404 1140694392429040167
405 1214299359188677504
406 1292555653998165584
407 1375751151301017950
408 1464191176989280780
409 1558199543258948857
410 1658119646460020572
411 1764315625851923984
412 1877173592577451680
413 1997102926827930586
414 2124537653272128350
415 2259937892807279926
416 2403791401526140938
417 2556615195078927132
418 2718957270216252591
419 2891398421841224686
420 3074554168334407726
421 3269076783665504760
422 3475657450115034100
423 3695028530355527786
424 3927965973868222963
425 4175291856724885277
426 4437877070974343666
427 4716644162997755859
428 5012570338444284132
429 5326690633516731255
430 5660101271713640082
431 6013963206269294095
432 6389505869037593185
433 6788031126612469603
434 7210917466214054097
435 7659624412784812015
436 8135697201770166236
437 8640771709776463375
438 9176579669715294236
439 9744954173489737161
440 10347835491156872291
441 10987277210625314511
442 11665452729361800848
443 12384662103308411863
444 13147339287272346299
445 13956059773294740891
446 14813548664301865839
447 15722689191045460650
448 16686531712960908447
449 17708303212648678399
450 18791417328259442669
451 19939484935414947129
452 21156325326933816790
453 22445978004191308543
454 23812715132747523471
455 25261054678548926378
456 26795774282133001712
457 28421925889934890385
458 30144851205369458250
459 31970197981953749876
460 33903937226886664078
461 35952381340905799011
462 38122203269149215448
463 40420456692837896992
464 42854597343414026068
465 45432505473456925259
466 48162509573582790882
467 51053411374694498416
468 54114512233108697549
469 57355640943578267062
470 60787183086852127013
471 64420111963139058737
472 68266021228113888023
473 72337159289922370395
474 76646465594811740435
475 81207608867765410941
476 86035027447813544466
477 91143971793268536483
478 96550549309773079012
479 102271771586295300609
480 108325604206488194584
481 114731019231569441338
482 121508050538073411635
483 128677852118939708795
484 136262759548780680719
485 144286354735484291272
486 152773534178225125705
487 161750580869276505041
488 171245240080795442940
489 181286799190950569345
490 191906171813730690439
491 203135986405660502467
492 215010679639231761669
493 227566594737225353419
494 240842085085687146512
495 254877623343030333333
496 269715916393726468221
497 285402026389898521543
498 301983498263030741235
499 319510493977775220149
500 338035933947122679493
501 357615645912744535740
502 378308521750469550689
503 400176682539960657498
504 423285652403295394978
505 447704541490579825250
506 473506238666421269734
507 500767614318697743776
508 529569733897404122426
509 559998082652937393900
510 592142802240911278365
511 626098939715898755801
512 661966709646316857952
513 699851769931574277218
514 739865512125227187285
515 782125366910180395773
516 826755125608299137465
517 873885278442234875538
518 923653370518158054961
519 976204376326569588210
520 1031691093824699581711
521 1090274558985325928308
522 1152124481979714943594
523 1217419705976335392299
524 1286348689837451845730
525 1359110015802212407546
526 1435912923563976317320
527 1516977871948536100726
528 1602537129739018432032
529 1692835396984376494200
530 1788130458488809441612
531 1888693870962793061224
532 1994811685699469638687
533 2106785208415615760800
534 2224931798303730010500
535 2349585708109263749760
536 2481098967480198396897
537 2619842311595765004307
538 2766206157541809204706
539 2920601630652009981330
540 3083461643524381443949
541 3255242030166303265246
542 3436422738243038043624
543 3627509082140869842355
544 3829033060111278542991
545 4041554738491252785693
546 4265663706586139370167
547 4501980605522791507017
548 4751158735010545872129
549 5013885741662060421352
550 5290885393196872917497
551 5582919442558552470988
552 5890789586691230262839
553 6215339524423225540311
554 6557457118667545086103
555 6918076667845642815619
556 7298181292253272451400
557 7698805440779240793903
558 8121037524254453098299
559 8566022681396736289389
560 9034965684241474924629
561 9529133989633487062781
562 10049860944342138074825
563 10598549151045509673215
564 11176674003482706998619
565 11785787398756871780188
566 12427521635896226628076
567 13103593509465378762291
568 13815808608220458719001
569 14566065828489730841386
570 15356362113245085345426
571 16188797427522950857075
572 17065579982225393406670
573 17989031718032898073183
574 18961594062627434473200
575 19985833974135314777996
576 21064450285268645413413
577 22200280362368085489306
578 23396307095228699466545
579 24655666233331196549801
580 25981654085897817770255
581 27377735602952939992972
582 28847552856492509749124
583 30394933940651601812546
584 32023902311820105647237
585 33738686589471104558232
586 35543730840674149694782
587 37443705371114809363841
588 39443518047808002441814
589 41548326178582163099177
590 43763548975948036189770
591 46094880632902699413857
592 48548304040939796813025
593 51130105180528303192978
594 53846888217240757902064
595 56705591336765759628056
596 59713503355171743119777
597 62878281140914843313179
598 66207967888446014779625
599 69711012283480289281422
600 73396288603602010670058
601 77273117798180486251137
602 81351289595449572598614
603 85641085685010939228000
604 90153304028188966028322
605 94899284349190683507976
606 99890934864504905745021
607 105140760308634280345631
608 110661891319072081353274
609 116468115244246394262371
610 122573908443336556873369
611 128994470147847148899872
612 135745757960400847489798
613 142844525067381589717233
614 150308359248060932675197
615 158155723764223212892841
616 166406000220766081407703
617 175079533489372899078379
618 184197678794311725873724
619 193782851061299660159617
620 203858576637867102997859
621 214449547495835104756145
622 225581678034595844577521
623 237282164606392242284238
624 249579547893498715155086
625 262503778270074270729247
626 276086284290845662045333
627 290360044452051057462857
628 305359662380197278975727
629 321121445607903458242416
630 337683488107023839047297
631 355085756753456871289417
632 373370181909830518533077
633 392580752317015925151185
634 412763614498138220598967
635 433967176884120765672632
636 456242218883527681661809
637 479642005125505119666757
638 504222405119445984039603
639 530042018581776454945078
640 557162306696273320935285
641 585647729581908453198280
642 615565890259513414407524
643 646987685417040800424284
644 679987463291888673961788
645 714643188998225994990711
646 751036617647455756227087
647 789253475620511293270720
648 829383650372516215136780
649 871521389162092678394492
650 915765507121210777774201
651 962219605094541431257075
652 1010992297702804521746860
653 1062197452099118844519990
654 1115954437914973477518503
655 1172388388908541753673441
656 1231630476857930783615153
657 1293818198259804044363058
658 1359095674426134621881367
659 1427613965591603672103851
660 1499531399679134416051802
661 1575013916392906004336256
662 1654235427346046776157821
663 1737378192954360759227325
664 1824633216868418353917675
665 1916200658743017239572466
666 2012290266187383463826803
667 2113121826768918727804419
668 2218925640991336697599225
669 2329943017200492076528776
670 2446426789423225928290690
671 2568641859180322804335720
672 2696865762371016355027080
673 2831389262365875096865448
674 2972516970505928187008708
675 3120567995249250940338584
676 3275876621272341436940312
677 3438793019881315399017591
678 3609683992159573870300840
679 3788933746331033895133592
680 3976944710895622848261496
681 4174138385151354897327479
682 4380956228801408267525024
683 4597860592407901972480080
684 4825335690545212726683179
685 5063888619575137167474788
686 5314050422064985572288057
687 5576377199945913301567619
688 5851451278615863612981011
689 6139882424275091021905359
690 6442309116898293147753554
691 6759399881339024155409040
692 7091854679187875731260881
693 7440406364106342838300214
694 7805822203494685234723667
695 8188905469462112349478050
696 8590497102215493656394416
697 9011477449103267449232237
698 9452768082711550098499421
699 9915333701541320985977393
700 10400184116969397786437227
701 10908376330340221038812746
702 11441016704223964985041963
703 11999263232034345170162123
704 12584327910403892718312452
705 13197479218887087023805224
706 13840044711783386587917239
707 14513413727060910401065896
708 15219040217601883408524865
709 15958445710197199894636689
710 16733222397978118282348532
711 17545036372198434003286737
712 18395630999563153631232467
713 19286830451545817329481447
714 20220543392443177233896453
715 21198766833184697803269037
716 22223590158246810087201523
717 23297199333315251993098630
718 24421881301699388513592141
719 25600028577822624577369271
720 26834144046504060242800057
721 28126845977095938470096782
722 29480873261965523666079413
723 30899090889191202311231793
724 32384495659802526942578066
725 33940222160309618076215858
726 35569549001766140715286810
727 37275905337063330859659874
728 39062877668693501931321671
729 40934216959715574124333777
730 42893846061241830739865704
731 44945867470303638509061561
732 47094571432590093384795991
733 49344444405140374318463382
734 51700177894760550673651503
735 54166677688574900903025474
736 56749073493870024890385658
737 59452729005086390707008406
738 62283252416623349323990634
739 65246507400881996150318468
740 68348624571850130085027821
741 71596013455359258159217951
742 74995374988097697061893569
743 78553714568362686184045970
744 82278355682568999130435255
745 86176954132509873430142783
746 90257512889487871093674902
747 94528397602497926509828718
748 98998352788861162955593482
749 103676518736866426181385030
750 108572449151295265513902147
751 113696129573966217449884598
752 119057996612864063091010645
753 124668958014790328433294651
754 130540413618021433860929915
755 136684277222951410570985155
756 143112999420376623127655635
757 149839591418700591770226391
758 156877649913158803165885525
759 164241383041925288335862603
760 171945637475937602889320955
761 180005926691191982514636547
762 188438460474401133838569596
763 197260175714988518272451291
764 206488768538713320285961060
765 216142727840482052876305265
766 226241370276417686053516397
767 236804876777714579050761261
768 247854330651533222030496288
769 259411757336858357308024925
770 271500165886198084247090907
771 284143592246901202378940570
772 297367144419071344801839175
773 311197049570205583280753924
774 325660703190154267592987079
775 340786720373418464725307726
776 356604989319560422986582482
777 373146727146215302490442875
778 390444538113265461919530622
779 408532474360769228226989452
780 427446099267649100151955630
781 447222553542519425691187905
782 467900624162814695965176315
783 489520816283127975061789498
784 512125428238848560916080005
785 535758629776340833054730936
786 560466543646517178980904684
787 586297330704248989189317645
788 613301278662137565242079545
789 641530894653232654724850602
790 671041001763869550593108694
791 701888839704375847651079194
792 734134169792529133764732202
793 767839384431784077772669526
794 803069621274009483012203346
795 839892882264216337314261311
796 878380157773120527329245508
797 918605556031777634441386527
798 960646438091582961237084208
799 1004583558542031055913456574
800 1050501212228434639703882654
801 1098487387221669827942636662
802 1148633924302631485079932554
803 1201036683234778647112821281
804 1255795716109644593417302749
805 1313015448061779722084134835
806 1372804865662039465942022363
807 1435277713310694469886856492
808 1500552697965311288101754606
809 1568753702551968161185393503
810 1640010008422952212447276402
811 1714456527238838389356808186
812 1792234042668633515341381753
813 1873489462317653853634105723
814 1958376080309886680201180867
815 2047053850968903333878507504
816 2139689674059878037402043267
817 2236457692074024702375504368
818 2337539600056769628439858404
819 2443124968501294686380870423
820 2553411579850733434461854172
821 2668605779174305327800175220
822 2788922839606096391291568501
823 2914587343159020959343742678
824 3045833577551841478187361829
825 3182905949712921667841511029
826 3326059416651805240254354059
827 3475559934417643174954241847
828 3631684925893151713461401695
829 3794723768203019817215441152
830 3964978300547767373091258584
831 4142763353306784949560296474
832 4328407299288987375076569243
833 4522252628044937952563903699
834 4724656544191831666895180050
835 4935991590741063515927050008
836 5156646298458697632627568479
837 5387025862330639497775474834
838 5627552846248207098239284954
839 5878667917074686741251633379
840 6140830609300922390808879073
841 6414520121546555060057992891
842 6700236146214848168836226735
843 6998499733661576687074656692
844 7309854192293942798630167320
845 7634866026072316906372638789
846 7974125910947587079869715612
847 8328249711828375592675045663
848 8697879541737225038510384681
849 9083684864881344176940672949
850 9486363645433595699127423979
851 9906643543891309986755523069
852 10345283162956268506402259286
853 10803073344956950454062205370
854 11280838522916015718183233072
855 11779438127450063437847344093
856 12299768051777192736650127759
857 12842762177198779682700506404
858 13409393961517506064114031574
859 14000678092951929092127885044
860 14617672212211204636180681631
861 15261478705499783858882961816
862 15933246571333540840792319660
863 16634173364163583630624516189
864 17365507217924613439863408003
865 18128548952748762720153561219
866 18924654268216141737858344465
867 19755236026647397693260657543
868 20621766630084343649753976178
869 21525780494749592344509559842
870 22468876626928165331051955425
871 23452721304370586243047647296
872 24479050867481176951202918468
873 25549674624724398467834859695
874 26666477876859425109734419049
875 27831425064795844602819965657
876 29046563046054897253074921094
877 30314024505018026632270016313
878 31636031502351326289338855379
879 33014899169207639283039488711
880 34453039552031375804778528462
881 35952965614021347307593176135
882 37517295399548018916934089307
883 39148756368070220844608473109
884 40850189904356657022255191550
885 42624556012086043388410148489
886 44474938198180707663566960720
887 46404548555518393855359378809
888 48416733051970340701405245683
889 50514977034026714852485579695
890 52702910953597882509664894106
891 54984316326917928411784303341
892 57363131934830196659787422069
893 59843460274099420287483039113
894 62429574269776366241201864338
895 65125924259034686732091890827
896 67937145257311210068904083461
897 70868064518005907462663056569
898 73923709397441853772206632651
899 77109315537244184654177008080
900 80430335376776211958721327192
901 83892447008765855004747451409
902 87501563391772516514911582308
903 91263841933678671804149555698
904 95185694460948166765420758397
905 99273797588969554535041082261
906 103535103509404453698320639793
907 107976851211082724599787272236
908 112606578151635252746787076897
909 117432132397725958380544193798
910 122461685252444658219430507146
911 127703744389146059984908652129
912 133167167511775148337360415274
913 138861176562499799778536391786
914 144795372498285672400705696869
915 150979750658890333211460130447
916 157424716749631609140952020818
917 164141103463193153519955623880
918 171140187765676993170381167004
919 178433708873092029472740337088
920 186033886945488301415277182574
921 193953442527002733326301472300
922 202205616761182701995913977810
923 210804192412092302414849577152
924 219763515722892732112235204200
925 229098519144815762768371406575
926 238824744970728356496799701668
927 248958369908809896385384568686
928 259516230633242259773080507006
929 270515850350239618947497571173
930 281975466419230946027121356999
931 293914059070546039829402793038
932 306351381262557561953670318955
933 319307989722889138374998712180
934 332805277220025698456899766660
935 346865506113448710839025783911
936 361511843232279077793373116743
937 376768396134335741809683425254
938 392660250799522408626439438010
939 409213510813529521614845128350
940 426455338099998258337174420612
941 444413995261528926552097229002
942 463118889592242928739032102809
943 482600618827016246929130451466
944 502891018695009112863501018783
945 524023212347711715673707755235
946 546031661734426161287481303681
947 568952221000900714051854948498
948 592822191989741122633569341085
949 617680381924235572903762699958
950 643567163360362862374555464786
951 670524536494997501237637930969
952 698596193921699840322318345838
953 727827587928973487383801755255
954 758266000439506355858517932393
955 789960615692674909624913724891
956 822962595776504657082056315954
957 857325159119332658605208212993
958 893103662055631905247294603786
959 930355683584821592175667701651
960 969141113446424791962605472299
961 1009522243639634260552973668249
962 1051563863520232465661867505252
963 1095333358612871589584455321482
964 1140900813281978807610604008999
965 1188339117409999507566181716873
966 1237724077237353139042738060697
967 1289134530524340749775698883298
968 1342652466201338153994662180015
969 1398363148679921538431963824993
970 1456355247004132718087414061332
971 1516720969027886439388624505448
972 1579556200811583139477762037711
973 1644960651438304431078141631280
974 1713038003457567892910504201782
975 1783896069172489334917483223834
976 1857646952994378812929391756807
977 1934407220097267939448556627036
978 2014298071613666439156230761010
979 2097445526621961920257196129875
980 2183980611185346259047533869290
981 2274039554711961177536366135640
982 2367763993916144234672277271209
983 2465301184671210789417133770080
984 2566804222055169254914032596395
985 2672432268902122299313857398781
986 2782350793183899422713151314639
987 2896731814558682647322827506951
988 3015754160436073015234293169409
989 3139603731921187270090054176233
990 3268473780014020000146553330823
991 3402565192454442732630718332255
992 3542086791617888999056034165196
993 3687255643881979389994565709169
994 3838297380900126743441297407143
995 3995446533234515122462771282193
996 4158946876817823593758001848480
997 4329051792730653437550248705431
998 4506024640799874718309963196740
999 4690139147542021761095180977478
1000 4881679808995499553226362868309