0 1
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 1
9 1
10 2
11 2
12 3
13 3
14 4
15 4
16 5
17 5
18 7
19 7
20 9
21 10
22 12
23 13
24 16
25 17
26 20
27 22
28 26
29 28
30 33
31 36
32 42
33 46
34 53
35 58
36 67
37 73
38 83
39 91
40 104
41 113
42 128
43 140
44 158
45 173
46 194
47 212
48 238
49 260
50 290
51 317
52 353
53 385
54 428
55 467
56 517
57 564
58 623
59 679
60 750
61 816
62 898
63 978
64 1075
65 1169
66 1283
67 1394
68 1527
69 1659
70 1815
71 1969
72 2152
73 2333
74 2545
75 2759
76 3006
77 3255
78 3543
79 3834
80 4168
81 4508
82 4895
83 5290
84 5740
85 6199
86 6717
87 7251
88 7851
89 8468
90 9161
91 9875
92 10672
93 11498
94 12416
95 13368
96 14425
97 15521
98 16733
99 17996
100 19388
101 20837
102 22433
103 24097
104 25923
105 27832
106 29920
107 32104
108 34493
109 36991
110 39715
111 42571
112 45679
113 48936
114 52478
115 56193
116 60223
117 64456
118 69039
119 73854
120 79065
121 84538
122 90450
123 96670
124 103378
125 110433
126 118037
127 126036
128 134645
129 143709
130 153451
131 163707
132 174725
133 186324
134 198767
135 211878
136 225927
137 240726
138 256577
139 273275
140 291141
141 309968
142 330092
143 351299
144 373957
145 397830
146 423311
147 450171
148 478817
149 509006
150 541189
151 575103
152 611228
153 649304
154 689833
155 732545
156 777990
157 825876
158 876790
159 930448
160 987464
161 1047539
162 1111349
163 1178577
164 1249941
165 1325131
166 1404900
167 1488933
168 1578054
169 1671922
170 1771419
171 1876219
172 1987249
173 2104174
174 2228007
175 2358398
176 2496424
177 2641753
178 2795525
179 2957406
180 3128638
181 3308866
182 3499421
183 3699980
184 3911946
185 4134997
186 4370661
187 4618612
188 4880482
189 5155980
190 5446836
191 5752774
192 6075677
193 6415265
194 6773554
195 7150322
196 7547704
197 7965503
198 8406043
199 8869143
200 9357290
201 9870371
202 10411034
203 10979218
204 11577793
205 12206728
206 12869100
207 13564986
208 14297660
209 15067265
210 15877359
211 16728146
212 17623442
213 18563586
214 19552647
215 20591078
216 21683287
217 22829821
218 24035416
219 25300808
220 26631052
221 28027032
222 29494232
223 31033691
224 32651295
225 34348324
226 36131073
227 38001051
228 39965075
229 42024860
230 44187738
231 46455756
232 48836761
233 51333100
234 53953273
235 56699935
236 59582221
237 62603217
238 65772718
239 69094226
240 72578342
241 76228979
242 80057549
243 84068543
244 88274195
245 92679547
246 97297838
247 102134692
248 107204357
249 112513192
250 118076499
251 123901381
252 130004390
253 136393391
254 143086209
255 150091689
256 157428971
257 165107873
258 173149100
259 181563500
260 190373369
261 199590802
262 209239773
263 219333670
264 229898403
265 240948703
266 252512486
267 264606118
268 277259617
269 290491012
270 304332751
271 318804637
272 333941629
273 349765616
274 366314208
275 383611474
276 401698041
277 420600275
278 440361961
279 461012154
280 482597968
281 505151244
282 528722881
283 553347713
284 579080577
285 605959729
286 634044194
287 663375842
288 694018402
289 726017569
290 759442025
291 794341844
292 830790956
293 868844036
294 908580889
295 950061123
296 993370719
297 1038574839
298 1085766052
299 1135015406
300 1186422785
301 1240065508
302 1296051199
303 1354464243
304 1415420491
305 1479011789
306 1545363111
307 1614574319
308 1686780035
309 1762089023
310 1840646210
311 1922569842
312 2008016195
313 2097113652
314 2190030534
315 2286906493
316 2387922689
317 2493230741
318 2603025945
319 2717472760
320 2836781479
321 2961130709
322 3090746786
323 3225823427
324 3366604513
325 3513299932
326 3666172242
327 3825449146
328 3991413157
329 4164310943
330 4344446831
331 4532087853
332 4727561551
333 4931157252
334 5143227329
335 5364084942
336 5594109506
337 5833639707
338 6083083807
339 6342808411
340 6613252615
341 6894812814
342 7187961655
343 7493127525
344 7810818820
345 8141498757
346 8485714004
347 8843965041
348 9216840056
349 9604879442
350 10008715714
351 10428932700
352 10866210328
353 11321178842
354 11794569545
355 12287062482
356 12799443777
357 13332447486
358 13886918430
359 14463648454
360 15063545847
361 15687464359
362 16336380083
363 17011213882
364 17713014370
365 18442774148
366 19201620187
367 19990622027
368 20810990317
369 21663877747
370 22550584534
371 23472352354
372 24430578021
373 25426598531
374 26461913908
375 27537964127
376 28656359614
377 29818650456
378 31026566079
379 32281774559
380 33586132428
381 34941434974
382 36349674737
383 37812783125
384 39332899036
385 40912099608
386 42552680132
387 44256874791
388 46027146143
389 47865896255
390 49775767585
391 51759341997
392 53819454120
393 55958879257
394 58180657567
395 60487771251
396 62883481252
397 65370991167
398 67953797845
399 70635342939
400 73419375488
401 76309591591
402 79310011064
403 82424602328
404 85657674375
405 89013488065
406 92496661539
407 96111768301
408 99863758100
409 103757538779
410 107798414275
411 111991651302
412 116342932277
413 120857907373
414 125542664742
415 130403264638
416 135446228428
417 140678056067
418 146105731817
419 151736225447
420 157577017060
421 163635578547
422 169919919419
423 176438049736
424 183198544409
425 190209988239
426 197481561499
427 205022463209
428 212842519764
429 220951587863
430 229360183877
431 238078866845
432 247118891359
433 256491566636
434 266208935082
435 276283108850
436 286726971286
437 297553491618
438 308776452545
439 320409738561
440 332468091828
441 344966375734
442 357920356417
443 371345942037
444 385259993130
445 399679533031
446 414622589630
447 430107378490
448 446153172886
449 462779460247
450 480006844351
451 497856169933
452 516349459500
453 535509007938
454 555358350934
455 575921330148
456 597223096990
457 619289143063
458 642146342323
459 665821948443
460 690344671952
461 715743645245
462 742049539130
463 769293489578
464 797508256541
465 826727114537
466 856985050417
467 888317618345
468 920762180922
469 954356722406
470 989141136782
471 1025156001137
472 1062443906834
473 1101048193822
474 1141014330021
475 1182388599865
476 1225219535300
477 1269556560841
478 1315451472544
479 1362957040106
480 1412128539009
481 1463022302647
482 1515697311805
483 1570213698967
484 1626634390805
485 1685023565606
486 1745448354739
487 1807977245451
488 1872681845378
489 1939635233195
490 2008913782215
491 2080595459491
492 2154761714535
493 2231495718873
494 2310884324657
495 2393016247173
496 2477984088665
497 2565882464725
498 2656810100293
499 2750867891031
500 2848161076365
501 2948797238656
502 3052888548905
503 3160549704404
504 3271900254063
505 3387062465465
506 3506163735510
507 3629334389605
508 3756710172513
509 3888429980641
510 4024638441290
511 4165483567942
512 4311119433582
513 4461703752193
514 4617400641311
515 4778378130533
516 4944811021523
517 5116878313137
518 5294766165581
519 5478665245150
520 5668773787121
521 5865294861188
522 6068439542563
523 6278424086690
524 6495473215189
525 6719817203540
526 6951695276700
527 7191352610616
528 7439043847164
529 7695029997578
530 7959582084725
531 8232977951897
532 8515506026527
533 8807462035604
534 9109152901813
535 9420893352725
536 9743009957288
537 10075837632901
538 10419723816820
539 10775024871984
540 11142110404742
541 11521359556052
542 11913165474886
543 12317931498761
544 12736075776503
545 13168027339651
546 13614230887496
547 14075142734766
548 14551235768435
549 15042995276280
550 15550924069840
551 16075538194973
552 16617372234308
553 17176974884739
554 17754914450344
555 18351774291503
556 18968158501760
557 19604687230265
558 20262002557777
559 20940763675962
560 21641652973958
561 22365371079858
562 23112643152041
563 23884213784269
564 24680853517372
565 25503353591210
566 26352532689842
567 27229231545689
568 28134319911563
569 29068691019023
570 30033268795255
571 31029002157251
572 32056872487133
573 33117887768430
574 34213090313950
575 35343550746088
576 36510375995797
577 37714703108142
578 38957707528065
579 40240596737375
580 41564618820889
581 42931055937435
582 44341233187475
583 45796511897814
584 47298298806902
585 48848039170730
586 50447226260307
587 52097394291189
588 53800128255170
589 55557056652523
590 57369861676862
591 59240271757566
592 61170072091665
593 63161096999850
594 65215240830276
595 67334450105886
596 69520734819762
597 71776160382633
598 74102859304942
599 76503022947713
600 78978913617750
601 81532856098993
602 84167250183524
603 86884561992521
604 89687336937627
605 92578190836141
606 95559823332431
607 98635008782961
608 101806610161623
609 105077569725199
610 108450923399087
611 111929791227739
612 115517392272237
613 119217034820929
614 123032131826161
615 126966190886497
616 131022830218617
617 135205768417213
618 139518840997647
619 143965989907054
620 148551280666954
621 153278891648775
622 158153131814662
623 163178429763831
624 168359352109229
625 173700592268382
626 179206989509226
627 184883517499509
628 190735304020108
629 196767619281199
630 202985896345939
631 209395719185400
632 216002843848279
633 222813186271168
634 229832844195199
635 237068084740858
636 244525367117205
637 252211329933451
638 260132814741524
639 268296853102149
640 276710690962594
641 285381775488685
642 294317780329431
643 303526592185967
644 313016337006761
645 322795366314683
646 332872284338008
647 343255934108389
648 353955425583150
649 364980121485612
650 376339666469037
651 388043972722209
652 400103250181604
653 412527991918259
654 425329005460784
655 438517397934453
656 452104608549333
657 466102393518664
658 480522859723352
659 495378449427448
660 510681975187054
661 526446604334903
662 542685895195752
663 559413781369966
664 576644609268805
665 594393122219441
666 612674499396826
667 631504339722101
668 650898702258661
669 670874089938916
670 691447491444428
671 712636364786255
672 734458680752616
673 756932906316970
674 780078049730292
675 803913643796287
676 828459792631577
677 853737154839068
678 879766992030459
679 906571151872604
680 934172118457161
681 962592995265971
682 991857557419276
683 1021990234595535
684 1053016165261232
685 1084961179523990
686 1117851855440545
687 1151715501855004
688 1186580216822000
689 1222474870472916
690 1259429165671241
691 1297473620887690
692 1336639633194285
693 1376959461209204
694 1418466290476872
695 1461194216532267
696 1505178312795328
697 1550454613741233
698 1597060185430770
699 1645033108855289
700 1694412553158920
701 1745238759217678
702 1797553115699047
703 1851398142866223
704 1906817571609487
705 1963856327556588
706 2022560613145325
707 2082977892108877
708 2145156974750190
709 2209148002801285
710 2275002538053470
711 2342773547682438
712 2412515496315509
713 2484284331904781
714 2558137581413353
715 2634134337243338
716 2712335356712103
717 2792803049142808
718 2875601579229919
719 2960796854887286
720 3048456634705233
721 3138650516574596
722 3231450049430855
723 3326928722777145
724 3425162082830823
725 3526227723058885
726 3630205404956293
727 3737177049623865
728 3847226863396675
729 3960441330607942
730 4076909344207314
731 4196722199841866
732 4319973731719755
733 4446760308055352
734 4577180972427480
735 4711337440753738
736 4849334248305318
737 4991278748365827
738 5137281265193029
739 5287455094426031
740 5441916662273935
741 5600785527863686
742 5764184548849223
743 5932239885880021
744 6105081174955116
745 6282841534100555
746 6465657742787829
747 6653670251041285
748 6847023366145428
749 7045865264394232
750 7250348185456768
751 7460628446881145
752 7676866646478099
753 7899227679837109
754 8127880950993649
755 8363000393203818
756 8604764688309340
757 8853357290916587
758 9108966656870403
759 9371786271133608
760 9642014885677743
761 9919856551351968
762 10205520865662291
763 10499223008811000
764 10801184001827801
765 11111630747125012
766 11430796297342987
767 11758919900756080
768 12096247281362956
769 12443030689369641
770 12799529193055252
771 13166008734729177
772 13542742434791312
773 13930010653555645
774 14328101308109099
775 14737309940277850
776 15157940046884296
777 15590303154317713
778 16034719162680280
779 16491516427416284
780 16961032118029477
781 17443612307108691
782 17939612344302348
783 18449396953272318
784 18973340621492097
785 19511827705659917
786 20065252838097937
787 20634021041030916
788 21218548150363443
789 21819260939441119
790 22436597560867651
791 23071007680362852
792 23722952937498713
793 24392907090144681
794 25081356495011252
795 25788800263394067
796 26515750762287819
797 27262733782145007
798 28030289059562869
799 28818970457640346
800 29629346511247335
801 30462000620804086
802 31317531621020149
803 32196553988924277
804 33099698437208768
805 34027612137207677
806 34980959338000561
807 35960421605288942
808 36966698467281825
809 38000507670432527
810 39062585853402804
811 40153688820484340
812 41274592244953405
813 42426091961276503
814 43609004699041123
815 44824168395058436
816 46072442959341076
817 47354710608079885
818 48671876663169543
819 50024869907325558
820 51414643418523158
821 52842174948545070
822 54308467794013135
823 55814551199515161
824 57361481266936737
825 58950341384631827
826 60582243176634433
827 62258326959363313
828 63979762732621675
829 65747750665187987
830 67563522129557741
831 69428340218106306
832 71343500823389657
833 73310333186605223
834 75330201025630095
835 77404503117362751
836 79534674475723684
837 81722186969824919
838 83968550554031607
839 86275313923950103
840 88644065801029203
841 91076435628220867
842 93574094911666434
843 96138757958270616
844 98772183276883609
845 101476174360091053
846 104252581147722250
847 107103300855017915
848 110030279501365186
849 113035512787427060
850 116121047691885159
851 119288983400183991
852 122541472972503383
853 125880724326640430
854 129309001980528704
855 132828628092230685
856 136441984280196167
857 140151512723428544
858 143959718063162143
859 147869168566134088
860 151882498111463718
861 156002407420454311
862 160231666132350350
863 164573114104196309
864 169029663579662559
865 173604300562371866
866 178300087082119277
867 183120162645602483
868 188067746604252880
869 193146139686435870
870 198358726471680526
871 203708977008302701
872 209200449398966640
873 214836791508260908
874 220621743664440582
875 226559140461634305
876 232652913583221416
877 238907093703254649
878 245325813437112056
879 251913309347337936
880 258673925027129440
881 265612113215981819
882 272732439022238971
883 280039582153844973
884 287538340286391626
885 295233631414958874
886 303130497374043733
887 311234106316679884
888 319549756393347920
889 328082878364507297
890 336839039445841158
891 345823946061066424
892 355043447860827890
893 364503540622905540
894 374210370452864356
895 384170236838739012
896 394389597041827028
897 404875069313736957
898 415633437485716324
899 426671654356236934
900 437996846488099484
901 449616317774728512
902 461537554454636849
903 473768228865474780
904 486316204685460759
905 499189540884575651
906 512396497203509326
907 525945538311416256
908 539845339533309601
909 554104791224756192
910 568733004758728921
911 583739317128013087
912 599133297203543596
913 614924750575372346
914 631123726094974351
915 647740520966671078
916 664785687586501955
917 682270038896465436
918 700204655533681185
919 718600891459929148
920 737470381435342574
921 756825046936880833
922 776677103970976667
923 797039069295111347
924 817923768585060779
925 839344342973930320
926 861314257590255725
927 883847308430113426
928 906957631282566684
929 930659708951093646
930 954968380584229112
931 979898849262801469
932 1005466691754307254
933 1031687866483843667
934 1058578723731080601
935 1086156014003490468
936 1114436898696260971
937 1143438958886763940
938 1173180206478562251
939 1203679093437585046
940 1234954523441784458
941 1267025861580320974
942 1299912946532071578
943 1333636100749554870
944 1368216143190404920
945 1403674400009461348
946 1440032717867847661
947 1477313475157603199
948 1515539595914803086
949 1554734561601655478
950 1594922425651169979
951 1636127825833505168
952 1678375999460319231
953 1721692796363261048
954 1766104694788142010
955 1811638815014129678
956 1858322935969087319
957 1906185509520099100
958 1955255677842111351
959 2005563288411679340
960 2057138912163243980
961 2110013859218816096
962 2164220197867626988
963 2219790771066747341
964 2276759216280779333
965 2335159982789870266
966 2395028352428570762
967 2456400457738687842
968 2519313303648022911
969 2583804786508050671
970 2649913716754388657
971 2717679838870953183
972 2787143855076714309
973 2858347446259176121
974 2931333296733811136
975 3006145116192522757
976 3082827665583485358
977 3161426780122167165
978 3241989396342325697
979 3324563576218579532
980 3409198535441392473
981 3495944668703319931
982 3584853579252415101
983 3675978105396462066
984 3769372351392573418
985 3865091715225409053
986 3963192920893139809
987 4063734047519126520
988 4166774563096286113
989 4272375354994220398
990 4380598765227759057
991 4491508622423500607
992 4605170278681027891
993 4721650643066711049
994 4841018220138299668
995 4963343145036699405
996 5088697223748783214
997 5217153969870183386
998 5348788646684296409
999 5483678305673450056
1000 5621901830494634556