1 0
2 1
3 0
4 0
5 1
6 1
7 1
8 2
9 1
10 2
11 3
12 4
13 5
14 7
15 7
16 9
17 12
18 15
19 17
20 23
21 27
22 34
23 42
24 50
25 60
26 75
27 87
28 106
29 128
30 154
31 182
32 222
33 260
34 311
35 369
36 437
37 515
38 613
39 716
40 845
41 993
42 1166
43 1361
44 1599
45 1861
46 2176
47 2534
48 2950
49 3422
50 3983
51 4605
52 5339
53 6174
54 7136
55 8227
56 9500
57 10928
58 12584
59 14460
60 16612
61 19048
62 21856
63 25009
64 28630
65 32727
66 37394
67 42662
68 48682
69 55446
70 63154
71 71843
72 81694
73 92786
74 105374
75 119502
76 135502
77 153493
78 173792
79 196584
80 222313
81 251139
82 283621
83 320032
84 360955
85 406787
86 458288
87 515857
88 580459
89 652682
90 733569
91 823906
92 925037
93 1037830
94 1163940
95 1304557
96 1461538
97 1636424
98 1831548
99 2048663
100 2290652
101 2559811
102 2859422
103 3192386
104 3562786
105 3974017
106 4431049
107 4938192
108 5501221
109 6125502
110 6818122
111 7585405
112 8435961
113 9377684
114 10420639
115 11574536
116 12851647
117 14263493
118 15824879
119 17549982
120 19456249
121 21560964
122 23885225
123 26449579
124 29279406
125 32399769
126 35840614
127 39632271
128 43810804
129 48412294
130 53479939
131 59057376
132 65195692
133 71947419
134 79373747
135 87537127
136 96510631
137 106369352
138 117199685
139 129091560
140 142148129
141 156476154
142 172198382
143 189442526
144 208353679
145 229084199
146 251806632
147 276701514
148 303973648
149 333838092
150 366536618
151 402324799
152 441489327
153 484332471
154 531193522
155 582431201
156 638445519
157 699661411
158 766551784
159 839618120
160 919418755
161 1006546874
162 1101659569
163 1205457401
164 1318715222
165 1442258084
166 1576998468
167 1723909364
168 1884062850
169 2058604918
170 2248796578
171 2455984505
172 2681650366
173 2927378035
174 3194905010
175 3486092035
176 3802978097
177 4147745233
178 4522783825
179 4930653745
180 5374153034
181 5856281893
182 6380316493
183 6949767802
184 7568468574
185 8240528161
186 8970424455
187 9762962825
188 10623375446
189 11557274561
190 12570768687
191 13670412037
192 14863328352
193 16157165785
194 17560231132
195 19081439398
196 20730469883
197 22517712335
198 24454434212
199 26552734884
200 28825727917
201 31287490376
202 33953273691
203 36839451196
204 39963745562
205 43345187856
206 47004366139
207 50963381948
208 55246136689
209 59878288891
210 64887564870
211 70303733198
212 76158945953
213 82487714056
214 89327298743
215 96717693134
216 104702049156
217 113326684629
218 122641553740
219 132700262024
220 143560604705
221 155284595969
222 167939058966
223 181595693745
224 196331729841
225 212230013080
226 229379750039
227 247876623487
228 267823612154
229 289331163699
230 312518104204
231 337511848448
232 364449435670
233 393477789882
234 424754864702
235 458449990696
236 494745149082
237 533835384648
238 575930253574
239 621254320629
240 670048765492
241 722572009428
242 779101506805
243 839934481811
244 905389962285
245 975809651897
246 1051560192928
247 1133034232605
248 1220652952239
249 1314867309947
250 1416160908453
251 1525051451363
252 1642093942517
253 1767882430048
254 1903053588214
255 2048288739105
256 2204317910226
257 2371922185342
258 2551938240251
259 2745261120444
260 2952849326849
261 3175728019745
262 3414994775142
263 3671823290146
264 3947469828853
265 4243277556257
266 4560683773052
267 4901224897390
268 5266544647947
269 5658399778559
270 6078669253339
271 6529360904705
272 7012621740723
273 7530745573468
274 8086184668736
275 8681558496783
276 9319666807290
277 10003499729427
278 10736252468271
279 11521336847089
280 12362397907582
281 13263327108511
282 14228280969746
283 15261696236739
284 16368310844774
285 17553181207376
286 18821705880244
287 20179645281066
288 21633148279246
289 23188774765917
290 24853525557692
291 26634868075691
292 28540770079734
293 30579728891003
294 32760809305459
295 35093676937076
296 37588640857510
297 40256691460902
298 43109548533959
299 46159704261428
300 49420477255754
301 52906061494063
302 56631587075688
303 60613175703491
304 64868009135586
305 69414392085125
306 74271829150569
307 79461096229582
308 85004327009441
309 90925093804375
310 97248504934840
311 104001296227071
312 111211940432559
313 118910750903368
314 127130004568262
315 135904059124296
316 145269491403727
317 155265229825637
318 165932709822055
319 177316023651631
320 189462095013617
321 202420848166634
322 216245404263849
323 230992272235757
324 246721569246790
325 263497236255622
326 281387285571535
327 300464043895009
328 320804430480833
329 342490231107060
330 365608410270855
331 390251420134704
332 416517550921204
333 444511278838108
334 474343659523484
335 506132719787217
336 540003898971417
337 576090490123492
338 614534135084968
339 655485320784954
340 699103934775746
341 745559823404779
342 795033414666008
343 847716346046373
344 903812162793669
345 963537023470671
346 1027120482933032
347 1094806285026115
348 1166853239934947
349 1243536114822881
350 1325146616817905
351 1411994392897491
352 1504408131365766
353 1602736684113450
354 1707350300115703
355 1818641885027525
356 1937028382341328
357 2062952186146286
358 2196882687702961
359 2339317859610695
360 2490785986687959
361 2651847442228446
362 2823096624853841
363 3005163948958438
364 3198718012042980
365 3404467824630730
366 3623165234359257
367 3855607423935810
368 4102639621955805
369 4365157899630978
370 4644112202113476
371 4940509478978339
372 5255417072510917
373 5589966221327805
374 5945355846991118
375 6322856473401942
376 6723814458239483
377 7149656376408619
378 7601893746741264
379 8082127933727152
380 8592055426472775
381 9133473317668393
382 9708285198709883
383 10318507282428419
384 10966274983982275
385 11653849761876781
386 12383626463001842
387 13158140963273543
388 13980078364522758
389 14852281526214794
390 15777760210014140
391 16759700604857920
392 17801475526786017
393 18906655049271530
394 20079017878482205
395 21322563214380963
396 22641523433045210
397 24040377318629626
398 25523864200152217
399 27096998707954220
400 28765086529343440
401 30533740861441124
402 32408899966083512
403 34396845510649832
404 36504222123830964
405 38738057834873935
406 41105785854726775
407 43615267348692855
408 46274815689698166
409 49093221825902612
410 52079781281322516
411 55244322406054731
412 58597236430380550
413 62149508918238235
414 65912753211603805
415 69899245443683244
416 74121961748658756
417 78594617226980108
418 83331707337189083
419 88348551250039367
420 93661337881234326
421 99287174119356689
422 105244136009785724
423 111551322390654772
424 118228911794276927
425 125298222084892854
426 132781773701504415
427 140703355956166041
428 149088097311207964
429 157962539063973882
430 167354713426825829
431 177294225404214685
432 187812339522281046
433 198942070791511031
434 210718281025437471
435 223177779873482513
436 236359431769630485
437 250304268127326676
438 265055606065431117
439 280659172974446555
440 297163238291373912
441 314618751770322902
442 333079489713954588
443 352602208425366630
444 373246806447875771
445 395076494832559149
446 418157977104657889
447 442561638148509235
448 468361743801325652
449 495636650349829526
450 524469025846598575
451 554946082423831343
452 587159821650354073
453 621207292093517500
454 657190861279316853
455 695218501191103055
456 735404089657087450
457 777867726757079714
458 822736068759651544
459 870142678711552730
460 920228396373681077
461 973141726612119471
462 1029039249133761772
463 1088086048675663419
464 1150456168739170743
465 1216333087981442310
466 1285910222583569387
467 1359391453707735545
468 1436991683606324467
469 1518937419512445145
470 1605467389127896337
471 1696833186860156804
472 1793299954909645240
473 1895147098378957512
474 2002669038810667612
475 2116176005367008289
476 2235994868376780431
477 2362470014512604326
478 2495964268681701431
479 2636859861943729225
480 2785559450922623236
481 2942487188103332233
482 3108089848883100875
483 3282838014858092616
484 3467227319665375710
485 3661779756955395970
486 3867045057298900512
487 4083602133731901305
488 4312060603252686822
489 4553062384121391280
490 4807283376844830136
491 5075435228853981003
492 5358267191368874064
493 5656568068658533388
494 5971168268838544947
495 6302941956640758532
496 6652809318017865302
497 7021738937261912771
498 7410750297275864174
499 7820916403977340039
500 8253366546298363550
501 8709289193097846558
502 9189935039365279079
503 9696620203398460038
504 10230729588321049442
505 10793720410060158033
506 11387125906202164561
507 12012559228336676106
508 12671717533471305842
509 13366386277660135261
510 14098443728687294320
511 14869865701573363775
512 15682730535091703294
513 16539224313759272062
514 17441646354975234638
515 18392414966532207601
516 19394073495781680726
517 20449296676557465003
518 21560897296862662505
519 22731833194401382344
520 23965214604861337414
521 25264311871096435869
522 26632563540174482725
523 28073584857660776376
524 29591176688314875629
525 31189334873926279114
526 32872260059901633067
527 34644368002811150432
528 36510300393147335364
529 38474936207185046056
530 40543403625038869294
531 42721092530667744910
532 45013667634048279306
533 47427082233303080880
534 49967592660397088417
535 52641773430483649816
536 55456533142171151253
537 58419131151327893688
538 61537195069712957367
539 64818739113826701750
540 68272183359630350567
541 71906373931640792150
542 75730604186761614198
543 79754636924789814978
544 83988727691127921338
545 88443649207399515640
546 93130717001113590256
547 98061816274271878112
548 103249430088138501285
549 108706668908688331408
550 114447301596610880149
551 120485787891446048043
552 126837312480965032496
553 133517820711001514708
554 140544056034682287681
555 147933599262455379381
556 155704909720446478710
557 163877368385319983383
558 172471323112507291193
559 181508136033496503273
560 191010233249160204460
561 201001156903077680488
562 211505619772897239804
563 222549562472736138445
564 234160213416703883999
565 246366151646548663112
566 259197372686572381750
567 272685357539795912788
568 286863145002803481643
569 301765407425261512594
570 317428530107081366689
571 333890694472483565182
572 351191965230800044964
573 369374381677820028353
574 388482053365953194999
575 408561260312925751349
576 429660557997346052347
577 451830887328386217377
578 475125689859703534994
579 499601028454062754100
580 525315713692585381007
581 552331436256093267453
582 580712905598377142316
583 610527995161966455033
584 641847894484373132095
585 674747268470694997294
586 709304424211281645490
587 745601485648007764368
588 783724576501302827718
589 823764011791867399915
590 865814498405571656155
591 909975345068721372300
592 956350682221858308820
593 1005049692195609042199
594 1056186850219927742555
595 1109882176710106930031
596 1166261501407835421659
597 1225456739864273390152
598 1287606182894629131370
599 1352854799538814822178
600 1421354554213396754104
601 1493264738641594556229
602 1568752319307132647538
603 1647992301075731097124
604 1731168107796114555249
605 1818471980586582785146
606 1910105394690932843302
607 2006279495677941968579
608 2107215555946386931716
609 2213145452384274455951
610 2324312166229493810175
611 2440970306061820766325
612 2563386655066239187758
613 2691840743586397617020
614 2826625448209020098251
615 2968047618495139235663
616 3116428732708876834818
617 3272105583765497888950
618 3435430996869052506379
619 3606774580177041638637
620 3786523510092450374117
621 3975083352646854617172
622 4172878922716597212196
623 4380355182673415436347
624 4597978182365626730618
625 4826236042181634315915
626 5065639981259417338983
627 5316725392757790173220
628 5580052968435568935073
629 5856209874633201245947
630 6145810982101488779325
631 6449500151967094776154
632 6767951580495260104579
633 7101871205152159724198
634 7451998174862249948888
635 7819106387194820383625
636 8204006095630605173385
637 8607545589895509982528
638 9030612952790057108156
639 9474137896777133075207
640 9939093684058917261645
641 10426499133705655278685
642 10937420719895846640804
643 11472974765157668097872
644 12034329733028460847104
645 12622708624378459408023
646 13239391482204277643686
647 13885718009526299118757
648 14563090305618054503678
649 15272975725624484508144
650 16016909869256395809413
651 16796499704078298785777
652 17613426829576403496496
653 18469450888024906641378
654 19366413128880236019824
655 20306240133266964658223
656 21290947705874945508648
657 22322644941425165364277
658 23403538473665253940821
659 24535936914698150210844
660 25722255493301850043177
661 26965020900746966848341
662 28266876353527210881930
663 29630586882274588436533
664 31059044857097468177297
665 32555275759445376501109
666 34122444211632857066202
667 35763860275031617812018
668 37482986029034518857103
669 39283442442785229758185
670 41169016552832494000544
671 43143668959773284303163
672 45211541658190130356050
673 47376966214111161057471
674 49644472305542978743342
675 52018796641570607889104
676 54504892276926954357680
677 57107938338901616629590
678 59833350184960000636571
679 62686790009438110300245
680 65674177919278304145758
681 68801703498796648179991
682 72075837885178654991909
683 75503346376459834774843
684 79091301595567662953269
685 82847097234100384393935
686 86778462401459676299896
687 90893476605097322482725
688 95200585389708241562503
689 99708616663394289699370
690 104426797741035660820676
691 109364773135354092158436
692 114532623128513999079533
693 119940883157417076484250
694 125600564048368658255823
695 131523173137171830709736
696 137720736313400815493303
697 144205821028059386151118
698 150991560306710053572586
699 158091677810699305200621
700 165520513992182620786872
701 173293053389286210939067
702 181424953111034135169839
703 189932572562407028628936
704 198833004463418327899399
705 208144107216947171638462
706 217884538683832140455090
707 228073791424710090540421
708 238732229472113051019269
709 249881126697456819386034
710 261542706841865769062042
711 273740185281054315986738
712 286497812599100106972773
713 299840920047389779294209
714 313795966969959387947254
715 328390590278084950456146
716 343653656062269589841484
717 359615313431613619321742
718 376307050676221543255789
719 393761753850365380299984
720 412013767880196459727470
721 431098960302111573314721
722 451054787744386297631772
723 471920365267274682420793
724 493736538683748988840066
725 516545959985936967302789
726 540393166009791753144446
727 565324660473739795717665
728 591388999535069423404976
729 618636881011390736952136
730 647121237423095871584222
731 676897333016706571091878
732 708022864938219863202899
733 740558068729947534992167
734 774565828334240265080162
735 810111790792339123602163
736 847264485837215425683467
737 886095450584620050513131
738 926679359537960069000116
739 969094160128536358418787
740 1013421214024908560157100
741 1059745444451676263130089
742 1108155489771098536348512
743 1158743863588156241150445
744 1211607121653764456978869
745 1266846035848744838357240
746 1324565775546312416675071
747 1384876096659518972653620
748 1447891538696362225587690
749 1513731630154810823013494
750 1582521102607470974231963
751 1654390113836091200530670
752 1729474480394876742752214
753 1807915919993068290423497
754 1889862304107414632861502
755 1975467921247751306215745
756 2064893751320579956734096
757 2158307751549322390199009
758 2255885154433227074276682
759 2357808778241986758437737
760 2464269350568176517783433
761 2575465845476114755282078
762 2691605834812681947299458
763 2812905854263660939296767
764 2939591784768118651843913
765 3071899249923046814556962
766 3210074030041616190316825
767 3354372493549905983581828
768 3505062046440456176046214
769 3662421600524463486302131
770 3826742061260455085531870
771 3998326835962881152675964
772 4177492363232804261894267
773 4364568664480783153675304
774 4559899918453719295377616
775 4763845059707864282381234
776 4976778402015014117900490
777 5199090287722068856136583
778 5431187764132366149539704
779 5673495288013298751528121
780 5926455459386621159811522
781 6190529785797150447620763
782 6466199478311406002441320
783 6753966280540499644249187
784 7054353332041677738948359
785 7367906067499436728660220
786 7695193153151802741011833
787 8036807461977953116504426
788 8393367089232955803335186
789 8765516409970395720763201
790 9153927180268566256174262
791 9559299683935664557267929
792 9982363926550059831392869
793 10423880878756627576993542
794 10884643770826932307278723
795 11365479440561554709860988
796 11867249736706285007947335
797 12390852980130463046064087
798 12937225485116320378147663
799 13507343143191281820387567
800 14102223072043454845645996
801 14722925332150717317033431
802 15370554713870376762277468
803 16046262597834210350689273
804 16751248891619189456991440
805 17486764045770308469344994
806 18254111152387048255989650
807 19054648129600074546070724
808 19889789995410241673377567
809 20761011234486717917609028
810 21669848261677677478735197
811 22617901986122211823241236
812 23606840480020755140219424
813 24638401756267834784847674
814 25714396659332540350379857
815 26836711873930836533940338
816 28007313056229365714953958
817 29228248092492319014218865
818 30501650490293480542256828
819 31829742907601745485950949
820 33214840825275100769980839
821 34659356368699654284766841
822 36165802284554392822076922
823 37736796078900583082147775
824 39375064323057562359525728
825 41083447133962867219905954
826 42864902835997661387435904
827 44722512811514020237815171
828 46659486547605373871320963
829 48679166886937948637525096
830 50785035490789185000872005
831 52980718522738255047686399
832 55269992561807132367606872
833 57656790754174207214492011
834 60145209212962893821025561
835 62739513675957547443254444
836 65444146431508659274890412
837 68263733523267582363117469
838 71203092244832128847753428
839 74267238935793314464518476
840 77461397091148458384666041
841 80791005796487852554237669
842 84261728501873574097598812
843 87879462147806695328364857
844 91650346657229722136934066
845 95580774808027243134002637
846 99677402501080563953607939
847 103947159439489745897582154
848 108397260235214692489684754
849 113035215959989317982109083
850 117868846158049960944669023
851 122906291338869834273155065
852 128156025968831069482051557
853 133626871981468551469558387
854 139328012826716148383279088
855 145269008080344648370804542
856 151459808635638085574590720
857 157910772500174271809053102
858 164632681221498326893072046
859 171636756966362266274470909
860 178934680279197269786765112
861 186538608546439713475792935
862 194461195194401572904128370
863 202715609649405891389395830
864 211315558090059268811478074
865 220275305022644901595689985
866 229609695711858898973020020
867 239334179500311971205243560
868 249464834051552390320147881
869 260018390552660061607996063
870 271012259913897136110527635
871 282464560004296400299565272
872 294394143963613760313059342
873 306820629632576663341520925
874 319764430145023165711956786
875 333246785727150032682672527
876 347289796750877822789776819
877 361916458090091820914747054
878 377150694830443521057075315
879 393017399385285275011533427
880 409542470072383131153755519
881 426752851208088296014335909
882 444676574777877699327081681
883 463342803744368343329970205
884 482781877056309684894495688
885 503025356424423435426164363
886 524106074932542037194695594
887 546058187555046188286080379
888 568917223654379703695685136
889 592720141535167131167540327
890 617505385134448239291146914
891 643312942930503733201765949
892 670184409155961896448500300
893 698163047404065403832177888
894 727293856720436573787586800
895 757623640276115619697272081
896 789201076721367447589218588
897 822076794323454318133900939
898 856303447995574307671019863
899 891935799328152867753195475
900 929030799737980147016799521
901 967647676854981337233202602
902 1007848024271038081316551600
903 1049695894779904058926846998
904 1093257897242238420438889531
905 1138603297214761253615290106
906 1185804121487891767464510986
907 1234935266681592664491031291
908 1286074612054904696251241459
909 1339303136690429282700963954
910 1394705041221211802855421960
911 1452367874273694090593900615
912 1512382663807066001627370122
913 1574844053536037148259718655
914 1639850444631212603547508653
915 1707504142898458632432495182
916 1777911511646345943678909507
917 1851183130458509576686029210
918 1927433960096044807585758603
919 2006783513763400646031698011
920 2089356034980134625357331245
921 2175280682309869580651254600
922 2264691721207363321895136930
923 2357728723254261380130420966
924 2454536773064390906239978131
925 2555266683149846356339870898
926 2660075217050176407686782243
927 2769125321038162139084983070
928 2882586364727563382156169636
929 3000634390920237524790745655
930 3123452375042811315784165721
931 3251230494536023479741386651
932 3384166408573587404867420538
933 3522465548501338035116383893
934 3666341419402184374652723535
935 3816015913207354147716197173
936 3971719633790276045461052580
937 4133692234495538410153073210
938 4302182768572404995209824436
939 4477450052999673860160200654
940 4659763046206977401873173083
941 4849401240216228749887940845
942 5046655067746595453182164181
943 5251826324846386821873889449
944 5465228609636381125279334915
945 5687187777770625922337434702
946 5918042415243456501233495273
947 6158144329194597049087077038
948 6407859057388608279378052940
949 6667566397069796511838706817
950 6937660953919909605811928546
951 7218552711872655743565606940
952 7510667624567235692430526699
953 7814448229251786046174149960
954 8130354283977872355158411273
955 8458863428958021142271398195
956 8800471872990760819239590423
957 9155695105890792410561745467
958 9525068637896795557263139017
959 9909148767064995938356523075
960 10308513375694084138907407106
961 10723762756865347686724819221
962 11155520472222109626248938687
963 11604434242153684074086231691
964 12071176869592260683324376851
965 12556447198675300757994242611
966 13060971109572415716649265836
967 13585502550823146612672265899
968 14130824610581870047841579976
969 14697750628217020582660929305
970 15287125347765294013835480944
971 15899826114796234194307258500
972 16536764118300014833864318519
973 17198885679270014891199429137
974 17887173587713415405987502753
975 18602648489886176784162938637
976 19346370327614911834279198699
977 20119439831635961290681926257
978 20923000070952990438541404965
979 21758238060287216225117060810
980 22626386427770593752029969322
981 23528725145110444513305769545
982 24466583322535813196386769093
983 25441341070919745390127874042
984 26454431433559472227871311054
985 27507342390186562886676014963
986 28601618935873321906983639302
987 29738865237598399707956134637
988 30920746871335687209906896250
989 32148993142634352456915288250
990 33425399493766363399428063484
991 34751830000629236891256082143
992 36130219962708156575912510196
993 37562578589521157100351076453
994 39050991787095961712376516293
995 40597625048155363024332573929
996 42204726449822024583879444337
997 43874629762791262718845847474
998 45609757676064108861028194567
999 47412625141480689513432973223
1000 49285842842448155882261576268