9 1
10 0
11 1
12 1
13 2
14 2
15 4
16 4
17 7
18 10
19 14
20 16
21 25
22 30
23 42
24 53
25 71
26 88
27 121
28 148
29 195
30 241
31 312
32 384
33 494
34 605
35 765
36 943
37 1179
38 1441
39 1796
40 2181
41 2694
42 3273
43 4011
44 4849
45 5922
46 7130
47 8652
48 10398
49 12552
50 15021
51 18072
52 21558
53 25816
54 30729
55 36649
56 43480
57 51705
58 61163
59 72476
60 85528
61 101029
62 118902
63 140081
64 164444
65 193174
66 226279
67 265115
68 309811
69 362140
70 422244
71 492380
72 572959
73 666618
74 774096
75 898783
76 1041634
77 1206917
78 1396181
79 1614549
80 1864280
81 2151933
82 2480407
83 2857921
84 3288684
85 3782643
86 4345596
87 4990124
88 5723671
89 6561992
90 7515207
91 8602581
92 9837533
93 11244275
94 12839953
95 14654761
96 16711311
97 19046652
98 21690102
99 24688026
100 28077541
101 31916361
102 36252384
103 41156519
104 46690003
105 52941093
106 59986873
107 67936748
108 76888737
109 86977345
110 98326367
111 111102579
112 125460714
113 141606785
114 159735467
115 180099714
116 202943247
117 228578300
118 257307683
119 289515836
120 325580353
121 365972448
122 411161236
123 461726003
124 518246563
125 581433562
126 652004951
127 730829517
128 818793586
129 916961270
130 1026422400
131 1148477969
132 1284469162
133 1435982111
134 1604663526
135 1792448901
136 2001353822
137 2233736385
138 2492063979
139 2779203248
140 3098168710
141 3452446259
142 3845709822
143 4282192123
144 4766369725
145 5303372685
146 5898646307
147 6558407583
148 7289266568
149 8098747849
150 8994871366
151 9986729910
152 11084039601
153 12297783952
154 13639713871
155 15123081033
156 16762088036
157 18572700878
158 20572062313
159 22779398382
160 25215369894
161 27903103111
162 30867480498
163 34136284805
164 37739446744
165 41710321865
166 46084865958
167 50903083831
168 56208135089
169 62047945136
170 68474263252
171 75544463504
172 83320521101
173 91871054349
174 101270225711
175 111600015931
176 122949080044
177 135415291860
178 149104516686
179 164133494746
180 180628540955
181 198728763947
182 218584733685
183 240362089635
184 264240136371
185 290415931117
186 319102827123
187 350535046017
188 384966225719
189 422674554709
190 463961283687
191 509156544910
192 558617861498
193 612736673016
194 671936924690
195 736682407726
196 807475394883
197 884864963129
198 969445733152
199 1061867224230
200 1162832814472
201 1273110286018
202 1393530988059
203 1525001803891
204 1668504614530
205 1825109780282
206 1995976077596
207 2182365924391
208 2385645805283
209 2607303565755
210 2848949483035
211 3112335794759
212 3399358670936
213 3712080312000
214 4052731899312
215 4423738718674
216 4827724345356
217 5267539071084
218 5746265705139
219 6267251799112
220 6834117242817
221 7450790939024
222 8121520601403
223 8850914332535
224 9643953199587
225 10506038441265
226 11443007173545
227 12461186161553
228 13567411298092
229 14769088666237
230 16074218654377
231 17491465385607
232 19030186097762
233 20700510292590
234 22513375388840
235 24480616727195
236 26615010801965
237 28930377714938
238 31441633051275
239 34164904752647
240 37117595196283
241 40318514252764
242 43787953535433
243 47547838004956
244 51621814139792
245 56035422958971
246 60816204516722
247 65993895053487
248 71600550777796
249 77670772652097
250 84241852257488
251 91354028421742
252 99050658840242
253 107378512674531
254 116387972387344
255 126133367504062
256 136673211059257
257 148070580690180
258 160393395277339
259 173714849620835
260 188113737952666
261 203674949889323
262 220489847629357
263 238656832237369
264 258281782968611
265 279478703279288
266 302370232266371
267 327088381779108
268 353775130416330
269 382583265037564
270 413677070001454
271 447233287139237
272 483441915119288
273 522507304673376
274 564649083948964
275 610103408494851
276 659124031581934
277 711983729888237
278 768975540901539
279 830414389045524
280 896638514054071
281 968011326139714
282 1044923053603171
283 1127792858092640
284 1217070734201035
285 1313239921176498
286 1416819090264550
287 1528365094736807
288 1648475486886920
289 1777791652238487
290 1917001704523634
291 2066844057400466
292 2228110750605764
293 2401651520366821
294 2588377618624472
295 2789266449605179
296 3005365953214564
297 3237799885784594
298 3487772846349659
299 3756576290821081
300 4045594292185266
301 4356310387025087
302 4690314173886171
303 5049309105984835
304 5435120043672501
305 5849702123225860
306 6295149396843278
307 6773704922051059
308 7287770641589258
309 7839918859130920
310 8432903529027838
311 9069673306993920
312 9753384444574123
313 10487415625292918
314 11275382685827595
315 12121155478142745
316 13028874665590810
317 14002970884356409
318 15048183898095119
319 16169584364320641
320 17372595669976013
321 18663018651013023
322 20047056470007157
323 21531342683982711
324 23122969575515490
325 24829520011193512
326 26659099693053757
327 28620373310568743
328 30722601235895403
329 32975680539004704
330 35390186721723759
331 37977420234513661
332 40749453923312517
333 43719185772273510
334 46900392819720796
335 50307790946104683
336 53957096116884196
337 57865092134620415
338 62049700179084999
339 66530055564037547
340 71326586663729823
341 76461101849801299
342 81956879037268439
343 87838764120382550
344 94133272531034383
345 100868700664554340
346 108075241014296398
347 115785108269664576
348 124032669794370502
349 132854588284425889
350 142289969584185054
351 152380524035350737
352 163170733869345294
353 174708035649127209
354 187043009764401981
355 200229586661139070
356 214325261286787111
357 229391326145757727
358 245493113890093915
359 262700260621667316
360 281086980230010743
361 300732361778570304
362 321720679644180313
363 344141729308441416
364 368091177847819733
365 393670942990380272
366 420989589077613589
367 450162754836906377
368 481313600574103259
369 514573290792376762
370 550081499074217181
371 587986952435855413
372 628448001161553048
373 671633232616069760
374 717722114191004422
375 766905685252642798
376 819387282347065007
377 875383319025572007
378 935124103583369852
379 998854717678128970
380 1066835938135279951
381 1139345226612961130
382 1216677768395133561
383 1299147586848004703
384 1387088713701593409
385 1480856443690180657
386 1580828652584399821
387 1687407209278739610
388 1801019459783309544
389 1922119816107174724
390 2051191426625767672
391 2188747963415976734
392 2335335501875948459
393 2491534530778117118
394 2657962066742124008
395 2835273914182030311
396 3024167043310430812
397 3225382130379041585
398 3439706231322600128
399 3667975636327639500
400 3911078875026129084
401 4169959923479157879
402 4445621581113054911
403 4739129072696166271
404 5051613841982865914
405 5384277596315378144
406 5738396567233430039
407 6115326050963562482
408 6516505192200730671
409 6943462079992521379
410 7397819117525356262
411 7881298739922554403
412 8395729440219153695
413 8943052183401170201
414 9525327166999191452
415 10144741014359922802
416 10803614357470361098
417 11504409902161696579
418 12249740930964768367
419 13042380343754017088
420 13885270189843802359
421 14781531799573721172
422 15734476467552712949
423 16747616804105513878
424 17824678705663206670
425 18969614069920323337
426 20186614205124997042
427 21480124069365077253
428 22854857288036123017
429 24315812096185223800
430 25868288152884198368
431 27517904386144618677
432 29270617814637885479
433 31132743517537953959
434 33110975698172350632
435 35212410026635776020
436 37444567206745582979
437 39815417967598038594
438 42333409425074540508
439 45007493029943413484
440 47847154048358941893
441 50862442809139452820
442 54064007664529205059
443 57463129918196837767
444 61071760668551299596
445 64902559842169425548
446 68968937367517204764
447 73285096786568930105
448 77866081257316423235
449 82727822269697979485
450 87887191031506110540
451 93362052873911875307
452 99171324637798052824
453 105335035419969852635
454 111874390646144886951
455 118811839881968493337
456 126171148355826657446
457 133977472639738139360
458 142257440470512824413
459 151039235195549206776
460 160352684835465637757
461 170229356289606937162
462 180702654688358669724
463 191807928463730226769
464 203582580156085169624
465 216066183577925495616
466 229300607368868819823
467 243330145616842551560
468 258201655598419648759
469 273964703372368893372
470 290671717301255825878
471 308378150299528054837
472 327142650908146532428
473 347027244064673847812
474 368097521697733873342
475 390422844091724756773
476 414076552183940211103
477 439136191823967658624
478 465683750195450403988
479 493805905522093720276
480 523594290301080133502
481 555145769286347918676
482 588562732514090382217
483 623953404702778782389
484 661432171375839059235
485 701119923159680768447
486 743144418668209364097
487 787640667558218670365
488 834751334238263363186
489 884627163959376610058
490 937427431850858999743
491 993320416787354935235
492 1052483900741138226550
493 1115105695678607378260
494 1181384198757272088211
495 1251528978071256100122
496 1325761389816619811433
497 1404315229331847391451
498 1487437417013754507399
499 1575388721791223498021
500 1668444523301965752326
501 1766895615703284249576
502 1871049054424388131770
503 1981229049063931204817
504 2097777903921838284651
505 2221057009667901850426
506 2351447887839556867382
507 2489353291998604826472
508 2635198367466456761833
509 2789431873826810432761
510 2952527472368711021503
511 3124985083052600546963
512 3307332313455378069457
513 3500125964708481682169
514 3703953617200534559203
515 3919435301532040908146
516 4147225257844911622117
517 4388013789533488176065
518 4642529214851330793360
519 4911539922989567100381
520 5195856538576588039874
521 5496334201799588674453
522 5813874968581728403367
523 6149430338700583832402
524 6504003916820044403896
525 6878654215072623619119
526 7274497602762267983126
527 7692711412649355619965
528 8134537210051437220766
529 8601284235126126548027
530 9094333025306448716277
531 9615139229247284874862
532 10165237620070276447695
533 10746246320355049956808
534 11359871247569524098090
535 12007910793582169960076
536 12692260747952876031374
537 13414919479956076153449
538 14177993390144644968689
539 14983702647847110806282
540 15834387226637285680641
541 16732513255747592737198
542 17680679700827831115219
543 18681625393752475550225
544 19738236426385672140305
545 20853553929907988281141
546 22030782256280683942747
547 23273297585537279282261
548 24584656977321422131341
549 25968607892648845357953
550 27429098206349344607611
551 28970286738677817675055
552 30596554328800106232122
553 32312515481397894038714
554 34123030611583982170894
555 36033218922394559571357
556 38048471942793917799268
557 40174467763775065066108
558 42417186003519877247058
559 44782923542841007667927
560 47278311065211462439363
561 49910330446595373428757
562 52686333033072550243253
563 55614058855849862972837
564 58701656825716954988347
565 61957705961343370960952
566 65391237697957131553733
567 69011759336070744283624
568 72829278681735093223212
569 76854329943767543741619
570 81098000944877781127020
571 85571961718477428164939
572 90288494554094316940933
573 95260525570129660721199
574 100501657883483974881944
575 106026206462415497580208
576 111849234739428714976158
577 117986593078918696483619
578 124454959184375017146087
579 131271880549039233650492
580 138455819043630776456665
581 146026197755089192442608
582 154003450179641617897203
583 162409071895166170964573
584 171265674826825667630888
585 180597044243025622419849
586 190428198607400961782158
587 200785452437132844175847
588 211696482306197244799812
589 223190396158367440728552
590 235297806082752408631785
591 248050904732607631456137
592 261483545555786242342347
593 275631327035010218502811
594 290531681123456023654634
595 306223966092949675437941
596 322749563999084253558261
597 340151983001499739756204
598 358476964764309893876967
599 377772597197867003216949
600 398089432789551123824774
601 419480612809919232306759
602 442001997666831133522262
603 465712303721431974995220
604 490673246865977918613787
605 516949693207559013906164
606 544609817187747158376329
607 573725267515272615584772
608 604371341274728562085114
609 636627166624601308777838
610 670575894483804165748553
611 706304899659651022283802
612 743905991856136818078934
613 783475637058864441670471
614 825115189779022509743041
615 868931136700273912502386
616 915035352258706869549264
617 963545366751735508236448
618 1014584647558456032978447
619 1068282894124298107921125
620 1124776347349878553034638
621 1184208114099233894535192
622 1246728507530259454609135
623 1312495404030759939534161
624 1381674617531897533010794
625 1454440292057108238640307
626 1530975313353841027437935
627 1611471740547891362325904
628 1696131258750479332025647
629 1785165653647239113823250
630 1878797309089968276414179
631 1977259728818103944392001
632 2080798083430119941858477
633 2189669783838795107354105
634 2304145082439343637228586
635 2424507703341379964025138
636 2551055503012836347834927
637 2684101162814791764760240
638 2823972914905756029394935
639 2971015303134328496596878
640 3125589980541545505809946
641 3288076545244882584723985
642 3458873416481483932241054
643 3638398752749919159803272
644 3827091413999042942833212
645 4025411969986191498143382
646 4233843756940399055243832
647 4452893984852843017635891
648 4683094897734898430269275
649 4925004989384585382754166
650 5179210277225707375821459
651 5446325636999342147583911
652 5726996201116885486170876
653 6021898823715357015502377
654 6331743615491983544627823
655 6657275551644007819766662
656 6999276156283578235877379
657 7358565266965304123320783
658 7736002883016486015327881
659 8132491101648056463458221
660 8548976145886206666453394
661 8986450488674618202874219
662 9445955077569787730666575
663 9928581664785536967122220
664 10435475247427220167644774
665 10967836623115308587198280
666 11526925066295634517535041
667 12114061130920363901979054
668 12730629585296033630315889
669 13378082485311608679131070
670 14057942392388068405566145
671 14771805742939897646503881
672 15521346376285467743822673
673 16308319228427017548588488
674 17134564199287568527956053
675 18002010201513505440262786
676 18912679399140337934264166
677 19868691644981295486134534
678 20872269125811688723223445
679 21925741225028165509091942
680 23031549612702349406034336
681 24192253573602180841723000
682 25410535584024543316754958
683 26689207148988126149109176
684 28031214911638716054174367
685 29439647047480235384230894
686 30917739956384454541384982
687 32468885266153742698249664
688 34096637161790904540365239
689 35804720055516857512115042
690 37597036613000696044695166
691 39477676152224034848867875
692 41450923431873860874265609
693 43521267847191906368012957
694 45693413051734283911931777
695 47972287024611654201027679
696 50363052603364591725411485
697 52871118503834923070688232
698 55502150849042663736054066
699 58262085230381252087111881
700 61157139325163406082300684
701 64193826095957995233668749
702 67378967597955600531660461
703 70719709422122193871774347
704 74223535802782839996240469
705 77898285419922178110897634
706 81752167927464322998469752
707 85793781240572998389801425
708 90032129616090952838339138
709 94476642562160274018589800
710 99137194614255598711579794
711 104024126016941150658559643
712 109148264351975731668331506
713 114520947155638111296647228
714 120154045569592869067937269
715 126059989072048547952714636
716 132251791337554686800660498
717 138743077276414842394489679
718 145548111306448336860423856
719 152681826912679318170997845
720 160159857552463285227414394
721 167998568966640341881305462
722 176215092959428351353028689
723 184827362713100961244066851
724 193854149705829577099349842
725 203315102304673942320305983
726 213230786108269701592685343
727 223622726117663539649475184
728 234513450816560994325698828
729 245926538246475625601303087
730 257886664165356556621815636
731 270419652382843204514724795
732 283552527368683215984056193
733 297313569235798732446152752
734 311732371203199458156150912
735 326839899649298907394753377
736 342668556870259382154136636
737 359252246663792097104075318
738 376626442863296106638413359
739 394828260953500533089407324
740 413896532903655005008754249
741 433871885361114105750221287
742 454796821353503376065264972
743 476715805655018824687753751
744 499675353978256419619503355
745 523724126160943052038992798
746 548913023523332861684493488
747 575295290580669414823920677
748 602926621302103504037568573
749 631865270116809812573977920
750 662172167875685042597695188
751 693911042987140336161166023
752 727148547953848112009457523
753 761954391548275250817161361
754 798401476873952629389739486
755 836566045571314684261765990
756 876527828436899719144019198
757 918370202737573347190237670
758 962180356512307583058913999
759 1008049460167990175360931935
760 1056072845687602451200762555
761 1106350193784205746015501722
762 1158985729347121029176352024
763 1214088425543044594560173006
764 1271772216948962918328612597
765 1332156222111449202473379729
766 1395364975942322967389519358
767 1461528672379848098630169590
768 1530783417761433828348722914
769 1603271495374594656565346023
770 1679141641671225720956459494
771 1758549334652772098927038296
772 1841657094953813927092528355
773 1928634800175985713566794431
774 2019660013045877061127511117
775 2114918323996988987591078016
776 2214603708799489014946186555
777 2318918901890134425762354665
778 2428075786080509965987704393
779 2542295799352734578650645286
780 2661810359479858356804307005
781 2786861307241759175057610480
782 2917701369037902033021246541
783 3054594639734706506047873022
784 3197817086618522056903188435
785 3347657075364619292696074648
786 3504415918968792078629732924
787 3668408450630850665709163375
788 3839963621618656510358370017
789 4019425125187583126782154939
790 4207152047673113761748197643
791 4403519547924362699927774920
792 4608919566292884285964631554
793 4823761564445370178228080726
794 5048473297319483100257831470
795 5283501618600816253044076278
796 5529313321154032038653669461
797 5786396013904851509210023731
798 6055259036729422164278176279
799 6336434414976489227934725440
800 6630477855312849759222055253
801 6937969784657181951096791376
802 7259516434038034197289823794
803 7595750969292558527422745769
804 7947334670599379586306192045
805 8314958162926487398032540530
806 8699342699558479012457703787
807 9101241500962219784800192041
808 9521441151340620726414521377
809 9960763055326819293057621854
810 10420064957369470032945558434
811 10900242526470932999014247612
812 11402231009047014796597295349
813 11927006952797186862504401519
814 12475590004590228848798782705
815 13049044785500457564284979310
816 13648482846255648030470930019
817 14275064706498724547639177308
818 14930001981401998236811537827
819 15614559599325339634798788604
820 16330058114358023599587467458
821 17077876117749190417580677849
822 17859452752392836815490554397
823 18676290334712082746595940772
824 19529957088462101411971686984
825 20422089995164672017270435064
826 21354397766076764580210503777
827 22328663940805082707843164132
828 23346750117883977314725646778
829 24410599322860907433866865354
830 25522239519656477945809896486
831 26683787271211500787095152089
832 27897451555675184035192651858
833 29165537744654144260151742202
834 30490451750303953758492177685
835 31874704348332342750165055924
836 33320915684267231885334174314
837 34831819970653771686202231178
838 36410270383152476747123892040
839 38059244163847055004090697133
840 39781847940404263374527177790
841 41581323270092217283345933862
842 43461052418025255358171991563
843 45424564379397379237905415096
844 47475541155858199452512111721
845 49617824296611477997920511554
846 51855421715240985924965532297
847 54192514793729407248020639614
848 56633465785596044431709191374
849 59182825530577768260037461044
850 61845341493775970362841485825
851 64625966142731685958778856569
852 67529865676430789229793950242
853 70562429120824585370138642983
854 73729277806035657012709762614
855 77036275241049809761099515488
856 80489537402327944513372773694
857 84095443453454073421796133748
858 87860646913621071384049690186
859 91792087293493688614268978249
860 95897002217730375727265176987
861 100182940054243422745604769796
862 104657773071080189342191516051
863 109329711142670997714213994850
864 114207316028058751635115241479
865 119299516244658194675400609918
866 124615622562033791756014937582
867 130165344141193747582151161601
868 135958805345916115733785164229
869 142006563253713232451952426878
870 148319625895142769045544543181
871 154909471251352279752388710379
872 161788067040936549396925859401
873 168967891328461000695585725811
874 176461953988294499991562689662
875 184283819058771857636887414940
876 192447628023101910900972992455
877 200968124054925268492137235373
878 209860677267935384869757159258
879 219141311010584938572531637043
880 228826729248532231540211938334
881 238934345079220328927281772305
882 249482310424747435185078225708
883 260489546951065037330792863989
884 271975778263449816815906132834
885 283961563430224548192438942021
886 296468331888767869192309577443
887 309518419790045231128959185810
888 323135107840125608683624533873
889 337342660699517150060308354842
890 352166368003568207561416416268
891 367632587069738955427032127354
892 383768787360157487505155136283
893 400603596770638303012333673662
894 418166849820160772585305260273
895 436489637817790706411164251125
896 455604361087075622509868487860
897 475544783331168893593356340256
898 496346088225231330125129919914
899 518044938326141296247321845889
900 540679536393103265725953653854
901 564289689216505606805592714089
902 588916874056223683290800984673
903 614604307794625557041660221805
904 641397018913692065478912989202
905 669341922410048247982535645453
906 698487897766191247236536824793
907 728885870100934544349542188781
908 760588894626936585508598275371
909 793652244548293638274247343767
910 828133502536413399481166549150
911 864092655927904358263870653547
912 901592195793871737261637866386
913 940697220035967973101996614765
914 981475540670653686796367478787
915 1023997795469555322015219266847
916 1068337564130401388428003136698
917 1114571489159959665109021545761
918 1162779401657519608918969236051
919 1213044452194954793724071753845
920 1265453246997089561808402925647
921 1320095989634177875867698667911
922 1377066628446603716107920933135
923 1436463009930635790525239484996
924 1498387038323030662230783462218
925 1562944841631691408332383689457
926 1630246944369261927403026638526
927 1700408447256693433146007091758
928 1773549214174260017712169225070
929 1849794066648457968360294064613
930 1929272986174491179544790836501
931 2012121324685866613123519911174
932 2098480023494783320160999375659
933 2188495841039751188686678105588
934 2282321589789996605248274365715
935 2380116382669968304112669339780
936 2482045889381414071528614488366
937 2588282603015336443681370623688
938 2699006117361409962197856848980
939 2814403415338445332813708684674
940 2934669168985964140073387451659
941 3060006051474206217663190852649
942 3190625061607667470055953264026
943 3326745861315877320997335304167
944 3468597126644298717553455920516
945 3616416912778302634633801966612
946 3770453033653849204486517334953
947 3930963456730146949347307496272
948 4098216713521864852000896661620
949 4272492326511802990614707795620
950 4454081253088979355969819354945
951 4643286347182243645191208722473
952 4840422839285464488117942618397
953 5045818835597452412975591305426
954 5259815837027745722031140398324
955 5482769278848616152627049522610
956 5715049091803801769451239658030
957 5957040285515980763759609939599
958 6209143555067504519226392181781
959 6471775911662866085692153431096
960 6745371338316420201264941962772
961 7030381471545468643107468798220
962 7327276310086594959407915616063
963 7636544951692572713170308178458
964 7958696359107881655633122846806
965 8294260156363366687198403658107
966 8643787456574450397287212814536
967 9007851722473105188831432001497
968 9387049660951075283817738531390
969 9782002152941181025934199535211
970 10193355220014491607865982467877
971 10621781029124312550268202640680
972 11067978936982838176212890476607
973 11532676575613589239456500164964
974 12016630980681911964845973203742
975 12520629764267508007250270039836
976 13045492333806697865886835026226
977 13592071158998574112574725022748
978 14161253088537859962816916012088
979 14753960718608865729102340686121
980 15371153815148896498617936172178
981 16013830791966554450447530380721
982 16683030246880045387548029806499
983 17379832558123621351518272124907
984 18105361543356096756392749929549
985 18860786183694780599812543417282
986 19647322415290578913234261561038
987 20466234991056293953998831601223
988 21318839415259665893761065471784
989 22206503953796362990539523220703
990 23130651723065292318079104905150
991 24092762860480210885563865360716
992 25094376779767009442053711957679
993 26137094514316198019581516174954
994 27222581151984363976158278446824
995 28352568364867725462953624117260
996 29528857037704663590549751598380
997 30753319998703358777980425876080
998 32027904856734655119138293239992
999 33354636948980155288770828589425
1000 34735622403280557854082894299890