0 0
1 1
2 0
3 1
4 1
5 1
6 2
7 2
8 3
9 3
10 5
11 5
12 7
13 8
14 10
15 12
16 15
17 17
18 21
19 25
20 29
21 35
22 41
23 48
24 56
25 66
26 76
27 89
28 103
29 119
30 137
31 159
32 181
33 209
34 239
35 273
36 312
37 356
38 404
39 460
40 522
41 591
42 669
43 757
44 853
45 963
46 1085
47 1219
48 1371
49 1539
50 1725
51 1933
52 2164
53 2418
54 2702
55 3016
56 3362
57 3746
58 4171
59 4637
60 5155
61 5725
62 6351
63 7043
64 7805
65 8639
66 9561
67 10571
68 11679
69 12897
70 14233
71 15694
72 17298
73 19054
74 20972
75 23074
76 25372
77 27878
78 30621
79 33613
80 36875
81 40437
82 44319
83 48545
84 53153
85 58169
86 63623
87 69561
88 76017
89 83029
90 90653
91 98933
92 107915
93 117670
94 128250
95 139718
96 152156
97 165632
98 180224
99 196032
100 213142
101 231651
102 251679
103 273337
104 296741
105 322043
106 349375
107 378885
108 410755
109 445151
110 482255
111 522289
112 565455
113 611983
114 662135
115 716169
116 774359
117 837029
118 904492
119 977086
120 1055204
121 1139228
122 1229572
123 1326712
124 1431114
125 1543286
126 1663800
127 1793227
128 1932183
129 2081361
130 2241455
131 2413215
132 2597473
133 2795077
134 3006931
135 3234043
136 3477437
137 3738207
138 4017569
139 4316757
140 4637099
141 4980051
142 5347105
143 5739863
144 6160071
145 6609531
146 7090168
147 7604076
148 8153426
149 8740526
150 9367892
151 10038124
152 10753996
153 11518516
154 12334802
155 13206180
156 14136241
157 15128719
158 16187595
159 17317151
160 18521857
161 19806463
162 21176077
163 22636033
164 24191999
165 25850057
166 27616567
167 29498277
168 31502427
169 33636581
170 35908777
171 38327607
172 40902069
173 43641713
174 46556733
175 49657817
176 52956297
177 56464252
178 60194364
179 64160058
180 68375644
181 72856136
182 77617432
183 82676456
184 88050968
185 93759776
186 99822866
187 106261230
188 113097085
189 120354013
190 128056803
191 136231659
192 144906389
193 154110219
194 163874037
195 174230593
196 185214311
197 196861557
198 209210865
199 222302737
200 236179951
201 250887795
202 266473875
203 282988461
204 300484723
205 319018573
206 338649011
207 359438413
208 381452373
209 404760073
210 429434627
211 455552902
212 483195950
213 512449386
214 543403204
215 576152284
216 610796772
217 647441948
218 686198762
219 727184264
220 770521504
221 816340102
222 864776750
223 915975133
224 970086551
225 1027270505
226 1087694615
227 1151535345
228 1218978641
229 1290219887
230 1365464721
231 1444929733
232 1528842479
233 1617442391
234 1710981545
235 1809724759
236 1913950567
237 2023952121
238 2140037337
239 2262529987
240 2391770719
241 2528117273
242 2671945703
243 2823651545
244 2983650087
245 3152377787
246 3330293535
247 3517879069
248 3715640550
249 3924109972
250 4143845740
251 4375434388
252 4619492214
253 4876665994
254 5147634896
255 5433112368
256 5733846970
257 6050624578
258 6384270486
259 6735650442
260 7105673140
261 7495292565
262 7905509291
263 8337373269
264 8791986475
265 9270504499
266 9774139647
267 10304163973
268 10861911163
269 11448780029
270 12066237955
271 12715823115
272 13399148425
273 14117905457
274 14873867029
275 15668891709
276 16504928195
277 17384018405
278 18308302555
279 19280024087
280 20301533353
281 21375293271
282 22503884969
283 23690012063
284 24936507031
285 26246337641
286 27622611881
287 29068585203
288 30587667784
289 32183430240
290 33859611848
291 35620128706
292 37469080414
293 39410759330
294 41449659806
295 43590485944
296 45838161996
297 48197842872
298 50674923066
299 53275048390
300 56004127908
301 58868344156
302 61874166451
303 65028364365
304 68338019483
305 71810540447
306 75453678171
307 79275539365
308 83284603525
309 87489740117
310 91900224125
311 96525755179
312 101376477033
313 106462995357
314 111796399299
315 117388283571
316 123250768715
317 129396525493
318 135838799859
319 142591436045
320 149668904179
321 157086328395
322 164859513269
323 173004974923
324 181539972799
325 190482539809
326 199851517363
327 209666591327
328 219948326305
329 230718205145
330 241998669587
331 253813159172
332 266186155868
333 279143229924
334 292711084066
335 306917603852
336 321791909364
337 337364405424
338 353666838346
339 370732354230
340 388595555970
341 407292567140
342 426861097800
343 447340509090
344 468771885180
345 491198107524
346 514663927937
347 539216049695
348 564903211223
349 591776268747
350 619888287707
351 649294636941
352 680053082249
353 712223889271
354 745869929545
355 781056786323
356 817852870255
357 856329538893
358 896561216179
359 938625522573
360 982603409643
361 1028579294835
362 1076641207937
363 1126880942473
364 1179394207737
365 1234280793541
366 1291644740405
367 1351594511083
368 1414243175701
369 1479708603121
370 1548113654287
371 1619586390193
372 1694260287055
373 1772274454063
374 1853773866985
375 1938909610007
376 2027839120787
377 2120726452872
378 2217742547334
379 2319065508474
380 2424880898502
381 2535382042466
382 2650770338398
383 2771255588038
384 2897056339054
385 3028400233810
386 3165524380284
387 3308675736196
388 3458111500868
389 3614099531196
390 3776918772658
391 3946859699278
392 4124224780166
393 4309328962781
394 4502500166833
395 4704079807317
396 4914423336107
397 5133900796337
398 5362897408399
399 5601814176881
400 5851068512463
401 6111094888243
402 6382345519757
403 6665291062241
404 6960421345567
405 7268246135871
406 7589295916923
407 7924122712961
408 8273300941321
409 8637428287807
410 9017126627623
411 9413042979481
412 9825850486035
413 10256249444173
414 10704968372403
415 11172765108557
416 11660427961931
417 12168776907217
418 12698664812861
419 13250978729195
420 13826641223445
421 14426611753707
422 15051888108821
423 15703507900531
424 16382550099853
425 17090136646101
426 17827434113996
427 18595655431258
428 19396061675878
429 20229963938268
430 21098725240732
431 22003762544274
432 22946548828186
433 23928615234148
434 24951553306524
435 26017017313956
436 27126726643504
437 28282468301008
438 29486099501872
439 30739550343674
440 32044826595846
441 33404012589946
442 34819274202254
443 36292861965203
444 37827114290877
445 39424460798441
446 41087425783287
447 42818631811277
448 44620803429521
449 46496771033333
450 48449474872651
451 50481969188877
452 52597426524193
453 54799142185951
454 57090538857121
455 59475171397215
456 61956731815329
457 64539054407103
458 67226121101545
459 70022066999237
460 72931186094139
461 75957937226501
462 79106950248975
463 82383032397617
464 85791174917933
465 89336559928019
466 93024567510175
467 96860783084349
468 100851005044675
469 105001252651069
470 109317774231965
471 113807055678919
472 118475829226041
473 123331082572545
474 128380068329357
475 133630313783339
476 139089631039893
477 144766127525537
478 150668216844066
479 156804630050302
480 163184427323436
481 169817010033620
482 176712133269848
483 183879918810792
484 191330868533154
485 199075878329376
486 207126252516120
487 215493718729644
488 224190443383158
489 233229047668106
490 242622624096892
491 252384753665412
492 262529523618760
493 273071545818178
494 284025975791992
495 295408532455048
496 307235518495261
497 319523841515527
498 332291035915649
499 345555285514677
500 359335447007115
501 373651074237909
502 388522443299435
503 403970578548203
504 420017279527947
505 436685148804411
506 453997620814533
507 471978991719067
508 490654450265445
509 510050109769883
510 530193041209701
511 551111307434669
512 572833998613491
513 595391268907859
514 618814374385973
515 643135712298709
516 668388861712683
517 694608625516057
518 721831073927085
519 750093589502397
520 779434913665049
521 809895194889263
522 841516038543057
523 874340558412079
524 908413430050195
525 943780945962091
526 980491072644795
527 1018593509643885
528 1058139750632851
529 1099183146547821
530 1141778970943649
531 1185984487583465
532 1231859020300771
533 1279464025309580
534 1328863165980340
535 1380122390127284
536 1433310009993206
537 1488496784956394
538 1545756007011400
539 1605163589222264
540 1666798157179784
541 1730741143521464
542 1797076885727060
543 1865892727227738
544 1937279121896496
545 2011329742147280
546 2088141590688280
547 2167815116007652
548 2250454331833628
549 2336166940624028
550 2425064461174326
551 2517262360602058
552 2612880190773903
553 2712041729275499
554 2814875125199957
555 2921513049833337
556 3032092852349159
557 3146756720808473
558 3265651848555699
559 3388930606136717
560 3516750719057469
561 3649275451486205
562 3786673796043095
563 3929120670017193
564 4076797118129881
565 4229890522006529
566 4388594816719871
567 4553110714543105
568 4723645936092503
569 4900415449250247
570 5083641716025233
571 5273554947551673
572 5470393367646779
573 5674403485105287
574 5885840374954617
575 6104967969123719
576 6332059356725945
577 6567397094206895
578 6811273525843185
579 7063991114819133
580 7325862785160835
581 7597212275049827
582 7878374501773225
583 8169695938620055
584 8471535004286481
585 8784262465079023
586 9108261850258705
587 9443929881133815
588 9791676914224405
589 10151927398879243
590 10525120350001141
591 10911709836240922
592 11312165484083706
593 11726972998533830
594 12156634700801338
595 12601670083459906
596 13062616383837064
597 13540029176088124
598 14034482982472132
599 14546571904652100
600 15076910275522812
601 15626133332137918
602 16194897910626492
603 16783883163657366
604 17393791301083498
605 18025348354729110
606 18679304967938474
607 19356437210586290
608 20057547420589134
609 20783465072605548
610 21535047674697364
611 22313181694075541
612 23118783512694603
613 23952800413545845
614 24816211598865821
615 25710029241106613
616 26635299567603487
617 27593103980258789
618 28584560211177179
619 29610823515283237
620 30673087901350299
621 31772587402473061
622 32910597387120443
623 34088435912315575
624 35307465120083785
625 36569092678419639
626 37874773268448017
627 39226010119040381
628 40624356590260399
629 42071417807455275
630 43568852347384605
631 45118373977895289
632 46721753453114503
633 48380820365693017
634 50097465057756673
635 51873640592706057
636 53711364789550197
637 55612722321597323
638 57579866881822535
639 59615023416769191
640 61720490430985579
641 63898642364512911
642 66151932045469809
643 68482893219927439
644 70894143161807473
645 73388385365052047
646 75968412320470897
647 78637108380234223
648 81397452712481189
649 84252522348682147
650 87205495326978589
651 90259653934212525
652 93418388049538800
653 96685198593120298
654 100063701082883950
655 103557629302508658
656 107170839084445318
657 110907312211239290
658 114771160438627014
659 118766629644535866
660 122898104107575684
661 127170110918821516
662 131587324531376500
663 136154571451647778
664 140876835076495292
665 145759260681132426
666 150807160562087158
667 156026019339778826
668 161421499426010638
669 166999446661099668
670 172765896125628690
671 178727078132578222
672 184889424405013318
673 191259574444774259
674 197844382098431225
675 204650922326169295
676 211686498179559985
677 218958647995027087
678 226475152809206295
679 234244044002710871
680 242273611179704489
681 250572410290062679
682 259149272001242761
683 268013310327905837
684 277173931526709725
685 286640843264052681
686 296424064065510711
687 306533933055083721
688 316981119992746519
689 327776635619810815
690 338931842320970241
691 350458465112305009
692 362368602965583951
693 374674740478557873
694 387389759901373461
695 400526953530348285
696 414100036479695899
697 428123159842260965
698 442610924251483277
699 457578393856157331
700 473041110720059245
701 489015109659722799
702 505516933532998831
703 522563648991567089
704 540172862711841551
705 558362738118063409
706 577152012611945089
707 596560015324569083
708 616606685405594117
709 637312590865435897
710 658698947987495687
711 680787641326859403
712 703601244312555177
713 727163040471927127
714 751497045295042921
715 776628028757765665
716 802581538523661834
717 829383923844290934
718 857062360178181944
719 885644874550425288
720 915160371674194658
721 945638660856325214
722 977110483710787822
723 1009607542703293714
724 1043162530551140078
725 1077809160504209848
726 1113582197532448118
727 1150517490446085002
728 1188652004976766816
729 1228023857847191684
730 1268672351857864458
731 1310638012021574894
732 1353962622775669534
733 1398689266303276796
734 1444862361996744984
735 1492527707096050800
736 1541732518536102800
737 1592525476039086324
738 1644956766487523111
739 1699078129614978383
740 1754942905053693743
741 1812606080777986871
742 1872124342983622325
743 1933556127445826571
744 1996961672398234613
745 2062403072976522787
746 2129944337273086339
747 2199651444048795521
748 2271592402149435701
749 2345837311677195147
750 2422458426967299483
751 2501530221421580901
752 2583129454253694659
753 2667335239200491899
754 2754229115255882661
755 2843895119486617389
756 2936419861989285009
757 3031892603049798511
758 3130405332569908899
759 3232052851825248605
760 3336932857621531393
761 3445146028918996479
762 3556796115995248129
763 3671990032218926389
764 3790837948510317665
765 3913453390565186015
766 4039953338920563745
767 4170458331945143907
768 4305092571837202077
769 4443984033715628933
770 4587264577893800045
771 4735070065426420681
772 4887540477022355011
773 5044820035420841557
774 5207057331329060421
775 5374405453022115067
776 5547022119711152901
777 5725069818786084499
778 5908715947042692461
779 6098132956008882835
780 6293498501485747093
781 6494995597422691447
782 6702812774251176841
783 6917144241802717118
784 7138190056940661348
785 7366156296040911268
786 7601255232458042492
787 7843705519117491396
788 8093732376380449660
789 8351567785329671458
790 8617450686628922730
791 8891627185115167382
792 9174350760284419990
793 9465882482837068524
794 9766491237455260044
795 10076453951987066484
796 10396055833217402786
797 10725590609412917602
798 11065360779830509214
799 11415677871384796898
800 11776862702677610102
801 12149245655595330954
802 12533166954686063612
803 12928976954536846162
804 13337036435374278448
805 13757716907118565584
806 14191400922129770067
807 14638482396888648133
808 15099366942861588755
809 15574472206808571629
810 16064228220797097625
811 16569077762192748985
812 17089476723907089735
813 17625894495188137555
814 18178814353246962605
815 18748733866024714667
816 19336165306409433565
817 19941636078220995943
818 20565689154294030375
819 21208883526994282013
820 21871794671513620995
821 22555015022301162647
822 23259154462994267593
823 23984840830223664887
824 24732720431680083135
825 25503458578836771583
826 26297740134733597159
827 27116270077242480601
828 27959774078241681447
829 28828999099138652121
830 29724714003196255163
831 30647710185125703557
832 31598802218422777223
833 32578828520940003961
834 33588652039196962261
835 34629160951945107819
836 35701269393520805563
837 36805918197530705417
838 37944075661428966225
839 39116738332564358661
840 40324931816286795451
841 41569711606719417919
842 42852163940822241441
843 44173406676386018007
844 45534590194612881643
845 46936898327961653013
846 48381549313949575403
847 49869796775621599125
848 51402930729421174111
849 52982278621211769191
850 54609206391219218073
851 56285119568689490279
852 58011464397073225881
853 59789728990570899318
854 61621444522898774218
855 63508186449154143854
856 65451575761682660212
857 67453280280878790028
858 69515015981870482036
859 71638548358065376130
860 73825693822566193834
861 76078321148484858072
862 78398352949213230684
863 80787767199740884388
864 83248598800134267132
865 85782941182322203396
866 88392947961367599676
867 91080834632431368096
868 93848880314667578142
869 96699429543326362178
870 99634894111369622020
871 102657754961940183036
872 105770564133065354756
873 108975946756006934134
874 112276603108708110730
875 115675310725831043382
876 119174926566912724032
877 122778389244208219657
878 126488721311836903943
879 130309031617884150201
880 134242517721155708517
881 138292468374331971709
882 142462266075309460495
883 146755389688565124223
884 151175417138432781251
885 155726028176224662635
886 160411007223183084757
887 165234246291305042087
888 170199747984129931673
889 175311628579636795977
890 180574121197459563959
891 185991579052680286025
892 191568478798520969399
893 197309423960321357713
894 203219148463245957377
895 209302520256228988671
896 215564545034737683403
897 222010370064995111989
898 228645288112374218941
899 235474741476751895403
900 242504326137677850259
901 249739796012289060911
902 257187067328983558489
903 264852223119938803221
904 272741517835641894989
905 280861382084688091507
906 289218427502181622733
907 297819451750161219159
908 306671443653568710217
909 315781588475363079095
910 325157273334477709679
911 334806092770421728159
912 344735854458417408813
913 354954585079068397715
914 365470536346664476013
915 376292191200327225349
916 387428270162311757169
917 398887737867899037387
918 410679809771420128757
919 422813959033073128587
920 435299923591321969525
921 448147713425781841035
922 461367618015624772009
923 474970213998676991241
924 488966373036504784877
925 503367269890924376083
926 518184390717519859486
927 533429541581888586714
928 549114857204482978854
929 565252809940077494424
930 581856218998035887176
931 598938259909715075768
932 616512474249513802312
933 634592779616232546646
934 653193479881584869088
935 672329275712885209436
936 692015275377109275514
937 712267005833710340970
938 733100424123773592214
939 754531929063275601258
940 776578373248417679294
941 799257075381215713058
942 822585832923728933138
943 846582935089527316206
944 871267176181227356626
945 896657869283141833262
946 922774860318323215890
947 949638542479527807470
948 977269871043860864530
949 1005690378581115024302
950 1034922190566080529048
951 1064988041405357475385
952 1095911290889471851815
953 1127715941081383383805
954 1160426653652744992003
955 1194068767679566103573
956 1228668317909239930477
957 1264252053511188207507
958 1300847457323691775413
959 1338482765609806540789
960 1377186988335580942765
961 1416989929984130118609
962 1457922210919478132015
963 1500015289314421198289
964 1543301483657029924475
965 1587813995850791634565
966 1633586934923762307451
967 1680655341362490729513
968 1729055212086889390777
969 1778823526082624070351
970 1829998270708017209073
971 1882618468692903140647
972 1936724205847301837209
973 1992356659498233295719
974 2049558127673471061163
975 2108372059051495478121
976 2168843083697397487055
977 2231017044604996054535
978 2294941030065930444537
979 2360663406887016155861
980 2428233854477704184309
981 2497703399830020140043
982 2569124453413927576309
983 2642550846011652128075
984 2718037866515081642835
985 2795642300710968503469
986 2875422471079297090387
987 2957438277630802779313
988 3041751239810286282061
989 3128424539493051736755
990 3217523065102468616165
991 3309113456877364804237
992 3403264153318694208883
993 3500045438845645748521
994 3599529492692121455729
995 3701790439075302668705
996 3806904398668802457183
997 3914949541413720962497
998 4026006140701770837677
999 4140156628965479061587
1000 4257485654711351820239