110 1
111 0
112 2
113 0
114 5
115 0
116 10
117 0
118 20
119 0
120 36
121 0
122 65
123 0
124 110
125 0
126 185
127 0
128 300
129 0
130 481
131 0
132 740
133 1
134 1141
135 4
136 1710
137 11
138 2546
139 26
140 3718
141 57
142 5396
143 114
144 7703
145 218
146 10938
147 400
148 15323
149 707
150 21344
151 1214
152 29411
153 2036
154 40305
155 3336
156 54787
157 5354
158 74049
159 8435
160 99377
161 13072
162 132714
163 19955
164 176167
165 30037
166 232782
167 44654
168 306009
169 65600
170 400600
171 95317
172 522096
173 137113
174 677891
175 195369
176 876753
177 275888
178 1130120
179 386378
180 1451817
181 536825
182 1859044
183 740386
184 2373713
185 1014058
186 3022163
187 1379747
188 3837829
189 1865544
190 4860982
191 2507677
192 6143021
193 3351781
194 7744817
195 4456267
196 9744854
197 5894836
198 12235124
199 7760170
200 15334407
201 10168756
202 19181726
203 13267114
204 23956127
205 17236800
206 29866084
207 22305511
208 37180824
209 28755048
210 46214271
211 36934485
212 57366513
213 47275000
214 71107401
215 60310100
216 88033969
217 76692874
218 108845227
219 97227656
220 134426445
221 122899703
222 165816368
223 154912652
224 204321938
225 194735102
226 251481626
227 244161571
228 309218514
229 305366591
230 379798779
231 380997758
232 466044555
233 474263815
234 571284875
235 589046969
236 699639151
237 730040435
238 855977549
239 902917378
240 1046293449
241 1114504894
242 1277684517
243 1373032162
244 1558838279
245 1688392634
246 1900048904
247 2072465625
248 2313862468
249 2539499583
250 2815155550
251 3106577395
252 3421973279
253 3794126653
254 4155718367
255 4626584335
256 5042253318
257 5633130370
258 6112252295
259 6848571294
260 7402631691
261 8314396184
262 8957170416
263 10080011364
264 10828377005
265 12204173270
266 13078490123
267 14756721779
268 15781915930
269 17820586774
270 19026789989
271 21494132613
272 22918176286
273 25893966194
274 27580409696
275 31158180039
276 33161307833
277 37450171899
278 39835633066
279 44963139971
280 47810639771
281 53925337171
282 57331099429
283 64606187307
284 68686602581
285 77323525270
286 82218773935
287 92451930898
288 98330939524
289 110432645533
290 117498299399
291 131784903690
292 140280750278
293 157119449539
294 167337151340
295 187153987423
296 199442328494
297 222731481833
298 237506881767
299 264841149109
300 282599805959
301 314643305253
302 335975767753
303 373497702717
304 399105256967
305 442997104828
306 473711877033
307 525005661326
308 561812592195
309 621704126199
310 665768404541
311 735641425218
312 788338080749
313 869795706638
314 932746725451
315 1027643567026
316 1102757481182
317 1213241747920
318 1302763903524
319 1431320430009
320 1537885643431
321 1687392340053
322 1814092261849
323 1987877335462
324 2138331051588
325 2340248769288
326 2518692352927
327 2753199497854
328 2964579906744
329 3236836597268
330 3486931159998
331 3802903442390
332 4098444094644
333 4465038086194
334 4813869572305
335 5239068172634
336 5650313350611
337 6143354950169
338 6627622932580
339 7199184084737
340 7768788773751
341 8431220485621
342 9100455402074
343 9868027246240
344 10653453380781
345 11542666395113
346 12463472587884
347 13493383686970
348 14571767195631
349 15764402994579
350 17026040630386
351 18406828824113
352 19881377012426
353 21479690969177
354 23201403012057
355 25051135468624
356 27059517295621
357 29199795908104
358 31540410938337
359 34016357790608
360 36741687694034
361 39605360047726
362 42775852189112
363 46087245238461
364 49772438992861
365 53600718245543
366 57880608266790
367 62305433153114
368 67271940473057
369 72385075500531
370 78143816448316
371 84050872692246
372 90723080419292
373 97545619926648
374 105270437934651
375 113148258670607
376 122085242092161
377 131179120686984
378 141511209192024
379 152005896493665
380 163942667226852
381 176050453407481
382 189831965442447
383 203796595782085
384 219697617280297
385 235798925034324
386 254133900942388
387 272692910924582
388 293821443802874
389 315206380253875
390 339539644470438
391 364172574883347
392 392180415622404
393 420545023923333
394 452764224827696
395 485414442858980
396 522457909740568
397 560027963076764
398 602595376069756
399 645810967029104
400 694700635987874
401 744391910385731
402 800514483154322
403 857630497707105
404 922024256593145
405 987649677057915
406 1061498152317200
407 1136871938033252
408 1221523612283860
409 1308060499243770
410 1405051428773767
411 1504366001983700
412 1615445155563523
413 1729379449709549
414 1856537728468500
415 1987192198316621
416 2132694991049418
417 2282463904536521
418 2448888263062281
419 2620499487897923
420 2810775896704265
421 3007336232070116
422 3224796199224036
423 3449842377775250
424 3698271941095063
425 3955828629765716
426 4239529206208709
427 4534174294173851
428 4858031162182879
429 5194969837822106
430 5564529837444244
431 5949678053811961
432 6371237105757585
433 6811316084995407
434 7292018335146056
435 7794661081843332
436 8342610591016799
437 8916482316217182
438 9540869410593635
439 10195803280582174
440 10907046942218311
441 11654197307984515
442 12464105999764480
443 13316121188026211
444 14238074138982422
445 15209291199865158
446 16258442927822889
447 17365107231957517
448 18558618044517666
449 19819130543379830
450 21176426304364528
451 22611622273315592
452 24154687179825423
453 25788149714723590
454 27541855853994352
455 29400269280642135
456 31392748010561393
457 33506294944908753
458 35769354577356714
459 38172163388236125
460 40741759713513124
461 43472406881739205
462 46389171915246537
463 49491247932837493
464 52801085392385550
465 56323829592292130
466 60078583490821158
467 64077598941349026
468 68335806290646236
469 72873861163023856
470 77701596519641105
471 82849526132988406
472 88321351929249748
473 94159069315947583
474 100359101462568495
475 106976734310627409
476 113999840739804322
477 121499004378969969
478 129452148096051134
479 137947376981568380
480 146951125914512789
481 156571475544926635
482 166761693500405268
483 177652540819997604
484 189182287415533294
485 201507344604252478
486 214549001944807342
487 228492578472000179
488 243240239353775019
489 259009771010379424
490 275681910783705070
491 293510798868594949
492 312353274192650228
493 332504058433555598
494 353793460555866826
495 376561379165829221
496 400608795344896767
497 426325761876977474
498 453480979548402792
499 482520042400982921
500 513176262297600014
501 545956584475602854
502 580555686235969451
503 617548126100036994
504 656586567870553415
505 698319908723068151
506 742355315451053866
507 789423242970763999
508 839081783788202451
509 892150671649997205
510 948135295003621434
511 1007952920240325911
512 1071052569898436086
513 1138457834467887862
514 1209557733063102853
515 1285491539770500872
516 1365584690601031209
517 1451102070651481949
518 1541302086488333992
519 1637585759540329918
520 1739141203388133606
521 1847516692602711653
522 1961827066707577090
523 2083779589886849495
524 2212413198893478782
525 2349606490485902038
526 2494320350479873839
527 2648617683054170171
528 2811379751832227740
529 2984867353036316826
530 3167881296750785339
531 3362894488710584771
532 3568627321675912183
533 3787779628608082549
534 4018992494932924675
535 4265208117800610814
536 4524990625329349023
537 4801540592383471989
538 5093349035918210947
539 5403891512778116016
540 5731591485834230973
541 6080216633883324265
542 6448130449561135492
543 6839410420458199756
544 7252369950555911193
545 7691414501931694969
546 8154819957677972354
547 8647338405879617674
548 9167223801436678484
549 9719593917289568661
550 10302699869068712772
551 10922044584398339498
552 11575899346548349369
553 12270172029135822323
554 13003181576720597860
555 13781260927294349126
556 14602809184024343036
557 15474604696336781212
558 16395164912149037278
559 17371734177479168617
560 18402992789672173040
561 19496671815070146596
562 20651666040520776470
563 21876214133768758804
564 23169484911571587775
565 24540245585590298571
566 25988007413478860511
567 27522087195395041084
568 29142416830124511725
569 30858883770486223597
570 32671929696622164267
571 34592033869744384152
572 36620248930508162137
573 38767667145547300769
574 41036066687611026512
575 43437174186970537499
576 45973622624313658015
577 48657794511699310668
578 51493323205893302386
579 54493268973633084384
580 57662428961305233809
581 61014563491854916803
582 64555816620715771988
583 68300671754026915794
584 72256824515167947162
585 76439505334512483443
586 80858189768876987428
587 85528880564802323979
588 90463087445613362166
589 95677612462894924137
590 101186282126849914036
591 107006727111515198008
592 113155404254296748288
593 119650805058467629960
594 126512364075349497851
595 133759469620918707545
596 141414918157237498394
597 149499035427090897516
598 158038404195704106234
599 167054334100184412454
600 176577662260205515081
601 186630735765725852931
602 197249161715592373850
603 208456386964526709418
604 220293355822489653863
605 232784687710998942386
606 245977287512570622643
607 259897032733649351499
608 274597473016780388018
609 290105844569473127758
610 306483092023843740949
611 323757928945546507358
612 341999516691299117155
613 361238186087517143240
614 381552214474614228468
615 402973714939595718719
616 425591063938703049776
617 449438351159061016056
618 474615126122634216547
619 501157683790129483408
620 529177918900569406416
621 558714600240125343522
622 589893246133323349154
623 622755414041396367460
624 657441639045614781094
625 693996635600488663160
626 732577472787791301838
627 773232452024930613497
628 816136827703647611256
629 861342989010905233509
630 909046171748797419605
631 959303434886764269387
632 1012331948182512189767
633 1068194115265932446135
634 1127131161281426162493
635 1189211615314350145464
636 1254703061812124222773
637 1323681056734240154423
638 1396442044702709597486
639 1473069646917216507047
640 1553891881912562581350
641 1639001629863990849201
642 1728761426683677915997
643 1823274780955864420944
644 1922941937826458463176
645 2027878602344769607817
646 2138526188856691973652
647 2255014390741924032075
648 2377829541548666284826
649 2507117367067704129923
650 2643413183232276288856
651 2786881075579875131128
652 2938109744642422219813
653 3097284281317787855367
654 3265051539202763449955
655 3441620616582531922740
656 3627701685409839171023
657 3823531252752187904488
658 4029888403197292190759
659 4247040900025867781384
660 4475842799942728235961
661 4716597468431145025900
662 4970240497137188536281
663 5237115755162123638950
664 5518247478323747423546
665 5814025560156653348065
666 6125570581615960062601
667 6453324670013394154852
668 6798513095499985130143
669 7161637194651724681073
670 7544035968059911868839
671 7946277786967870800906
672 8369825182185323140885
673 8815322328882412079503
674 9284365911159156266173
675 9777685722401180661281
676 10297024119887863300232
677 10843207487911564310715
678 11418136351297410580216
679 12022745938304221559473
680 12659108498463127327420
681 13328281773819768715390
682 14032524452010817453188
683 14773032022121905762022
684 15552265585737559301898
685 16371575339470646472921
686 17233642149815783732008
687 18139989784554261926268
688 19093537729196247573491
689 20096004285766145059323
690 21150568052050559744630
691 22259165137515599018021
692 23425255539192284916028
693 24651018991958206788761
694 25940221137278355526565
695 27295313950054694215528
696 28720395106274886137560
697 30218220512249258088609
698 31793248612709824889892
699 33448574314034716097373
700 35189048133839060271917
701 37018142758390426183296
702 38941134893586457526997
703 40961917854703378195299
704 43086231735842213270259
705 45318437796964927535397
706 47664780097467796723059
707 50130140050468502850733
708 52721309965628593092151
709 55443748982697912994728
710 58304846009392417868367
711 61310701357144842295743
712 64469353342760857091688
713 67787613326627332993581
714 71274226739306219586773
715 74936792901175402457391
716 78784827439670931807204
717 82826802244822557201703
718 87073072124401071477897
719 91533074560054897776472
720 96218079010408296050145
721 101138590770882511462027
722 106306876541179932965620
723 111734621698747962353090
724 117435180604176765554571
725 123421541964271863916951
726 129708246816256125998250
727 136309722424795414061436
728 143241804973874059343526
729 150520508599663834221889
730 158163083485254501608655
731 166187293223517896667890
732 174611932268521923493100
733 183456691832335103989410
734 192742053453848852894928
735 202489831107971440643287
736 212722350026860010476900
737 223463760616779361614703
738 234738403562813125290666
739 246572999556549260609951
740 258994093158217570118456
741 272031231208540398882368
742 285713368865836308768801
743 300073158957283538759222
744 315142194084759898286039
745 330956539028279949620263
746 347550672777440797040914
747 364964406482009378986253
748 383235378756141135956460
749 402407512533206028012931
750 422521905962766057919384
751 443626992916592573406191
752 465767660304107509116332
753 488997288838967159964483
754 513364915594994554993553
755 538929344023005047578265
756 565744158118353272567756
757 593874103508453393738541
758 623377746666525685947817
759 654326342213027851838510
760 686783917263527714368270
761 720828853820545060976659
762 756531164554327033666349
763 793977033340586294751356
764 833243034632663941784107
765 874423889728236622138024
766 917603367374622544109585
767 962885528250891293648131
768 1010362029665060354664696
769 1060147145900835469045244
770 1112341184800992021793842
771 1167069587067665990092981
772 1224442147310449741383423
773 1284596510968311812381628
774 1347652877032187995454897
775 1413762226978481813877345
776 1483056171008306964672933
777 1555700259086721749955450
778 1631838617187064906071826
779 1711652706203482625749898
780 1795300379531282755190034
781 1882980471074139639515443
782 1974865890562074927944893
783 2071174437077518697993100
784 2172095534022234614048611
785 2277867679319024817089157
786 2388698407944523404891381
787 2504848804168365220386742
788 2626546266315187938227539
789 2754076519829879631175632
790 2887688746500872905010991
791 3027695549703095572140864
792 3174369998990769042015417
793 3328054010278180794878083
794 3489046846607418867501335
795 3657722386165098136532531
796 3834408611472568707452787
797 4019514246672515432824243
798 4213398760529541423936489
799 4416508861196832461947039
800 4629238533623595502493430
801 4852075884655292575660429
802 5085452732913394574292499
803 5329902299391744691235457
804 5585897868027069028836938
805 5854021816502925597002043
806 6134792868806968705347730
807 6428846957495605508870864
808 6736752596009602594294608
809 7059204056708473996241005
810 7396824400889073861451433
811 7750371446160868465903304
812 8120528006514919564636800
813 8508121107549997538975461
814 8913899007926521795970325
815 9338764101198170744711505
816 9783536314156856082059823
817 10249200108980400539925427
818 10736653883753364947585534
819 11246971457873927162137915
820 11781137136080622816298256
821 12340322022914146585684631
822 12925604454395269272837476
823 13538261443292106821545948
824 14179474232908478112787172
825 14850635123250144139499854
826 15553037959773161520608801
827 16288200530672230936096644
828 17057539870712359991028140
829 17862710350991866325996028
830 18705263754804004942353280
831 19587003102672375943212378
832 20509627544433617160015077
833 21475101873251282209607421
834 22485286376545153632520190
835 23542321892271715090681866
836 24648244871895457462658867
837 25805387719571725903546808
838 27015979443920189681395949
839 28282560894967377155089584
840 29607571519068408548923661
841 30993778968582516643704708
842 32443852626863040286650448
843 33960806910660030133808316
844 35547562400744158726958746
845 37207401985920761704631971
846 38943520620657601949969203
847 40759493271242657595569466
848 42658814525896813654555510
849 44645377096940074856690311
850 46723002732476654502972961
851 48895929802225257684425745
852 51168337204179814594291890
853 53544839314886724608407336
854 56030004850813559551911747
855 58628857194991071756880394
856 61346390462409835731077203
857 64188072922941417464972369
858 67159362834358428429203011
859 70266212364854041541842274
860 73514586097519494800604226
861 76910962513455762840082927
862 80461858439270083988692814
863 84174324782156476377740420
864 88055480588485869612623036
865 92112999324190827659717932
866 96354656639453507096803196
867 100788803059615573478764364
868 105423930009581555560156194
869 110269124321202960060624095
870 115333657563048035938664870
871 120627417278030119045427905
872 126160525190871659128821386
873 131943739563672214191402921
874 137988108416515542106788919
875 144305336826882563778016027
876 150907481899567434834336928
877 157807278237460189457701678
878 165017882037112689901312364
879 172553147321589121667400890
880 180427427218665856922569647
881 188655792870477792534327665
882 197253900674353821406349114
883 206238145066986894276165746
884 215625601274130339810257949
885 225434102408541901857892830
886 235682268086089178327502336
887 246389495474893803928617495
888 257576084992414815181884384
889 269263134097899390796195926
890 281472772189588066587108771
891 294227945041966403882289715
892 307552771974634516656215615
893 321472207900192928167793126
894 336012536838318047680922730
895 351200897557716190865075108
896 367065928560416464540379121
897 383637142272828148473570477
898 400945737727824034824294077
899 419023807184030717707248889
900 437905333886304427449746248
901 457625213870300590034127657
902 478220457386850531394412098
903 499729007479351530667735989
904 522191164913093370797787541
905 545648183898134885190091194
906 570143941671920583918000753
907 595723290479164882899265452
908 622433994313163148073342119
909 650324814959707134773568538
910 679447739810057451972086610
911 709855778427614391224890033
912 741605506800717143550996098
913 774754549502636622318671407
914 809364467255436157826459647
915 845497898325953824758812223
916 883221817818995552108612548
917 922604310489481434879781072
918 963718231773856161526858670
919 1006637582702316173205674098
920 1051441604306393891250781235
921 1098210723791699919866838715
922 1147031115626032203644401823
923 1197990186584049891762231368
924 1251181638517418857976302618
925 1306700458316461025188676747
926 1364648519089739004712921554
927 1425129039506698353920365882
928 1488252761860536750055810424
929 1554131843670226611232191267
930 1622886652864370927818667533
931 1694639052934710510177062536
932 1769519857249887194080453068
933 1847661467477761817220544586
934 1929206030812211196432853682
935 2014297389823697686114107461
936 2103089988147190240057044989
937 2195740088394059132776713450
938 2292415473599096028876752318
939 2393285888338976589140341161
940 2498533584956547402372899580
941 2608342941599178145800102205
942 2722911903921405955301857407
943 2842440732389481391637220798
944 2967144391791784980603621783
945 3097240378874169131305046586
946 3232962113551823397986574879
947 3374545796754829945420794403
948 3522244858714917687175343995
949 3676315795835911724157859243
950 3837033732812438057474574949
951 4004677186409296515361529636
952 4179544799432900230426826802
953 4361938978534818588657411443
954 4552183859186372308426756812
955 4750607764031224371557522083
956 4957562458981612086000138918
957 5173404378264865493450003871
958 5398515232549393576742310341
959 5633281946680098375557151524
960 5878118681321742906078841821
961 6133445429495151914862375249
962 6399711513575095361981295057
963 6677372787146065945017770367
964 6966916669275221315264811421
965 7268837898945297452300192736
966 7583665168317131033991347778
967 7911935378095067234815365656
968 8254221930957173269783947795
969 8611107437712706016325016376
970 8983213731184475561528981036
971 9371172974960006177255320224
972 9775659456713257107458192680
973 10197359053784635184893811189
974 10637002863197657121390864363
975 11095334981263939532742629710
976 11573148025332543169925470316
977 12071249188164634402706031078
978 12590497703714033217282495796
979 13131769141193634883693094317
980 13695994863867266586699427759
981 14284124532603187244099342285
982 14897167602720278725067584824
983 15536154012439703601747586473
984 16202177758208388227135111318
985 16896355749892890168819978726
986 17619873499655909461970662190
987 18373942133038949476727280438
988 19159846220322483039598518443
989 19978898940898672686472230357
990 20832492079053558051206210379
991 21722049348296690210087086189
992 22649078565586741075076250853
993 23615123152652083534174353928
994 24621816493785483653687560202
995 25670831642723707451525885538
996 26763937859177663416237671455
997 27902948562639603275647094135
998 29089780031733120559762574581
999 30326397660455259183369718013
1000 31614876792134559317946775823