0 1
1 0
2 1
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 5
11 6
12 7
13 9
14 10
15 12
16 14
17 17
18 19
19 23
20 26
21 30
22 35
23 40
24 46
25 52
26 60
27 67
28 77
29 87
30 98
31 111
32 124
33 140
34 157
35 175
36 197
37 219
38 244
39 272
40 302
41 336
42 372
43 413
44 456
45 504
46 557
47 614
48 677
49 744
50 819
51 899
52 987
53 1083
54 1186
55 1298
56 1420
57 1552
58 1695
59 1850
60 2018
61 2198
62 2394
63 2605
64 2833
65 3079
66 3344
67 3630
68 3936
69 4268
70 4624
71 5007
72 5419
73 5861
74 6336
75 6845
76 7393
77 7979
78 8608
79 9282
80 10003
81 10776
82 11603
83 12488
84 13435
85 14445
86 15527
87 16681
88 17914
89 19232
90 20636
91 22134
92 23732
93 25436
94 27251
95 29186
96 31246
97 33439
98 35772
99 38257
100 40899
101 43709
102 46696
103 49871
104 53243
105 56826
106 60631
107 64671
108 68957
109 73506
110 78331
111 83447
112 88874
113 94625
114 100719
115 107175
116 114014
117 121255
118 128923
119 137038
120 145627
121 154709
122 164320
123 174482
124 185225
125 196583
126 208585
127 221265
128 234658
129 248807
130 263745
131 279516
132 296161
133 313727
134 332258
135 351808
136 372427
137 394170
138 417088
139 441250
140 466711
141 493538
142 521804
143 551573
144 582925
145 615933
146 650686
147 687262
148 725757
149 766262
150 808872
151 853692
152 900827
153 950393
154 1002502
155 1057278
156 1114849
157 1175344
158 1238904
159 1305679
160 1375815
161 1449471
162 1526812
163 1608014
164 1693247
165 1782712
166 1876598
167 1975108
168 2078460
169 2186867
170 2300576
171 2419812
172 2544843
173 2675925
174 2813326
175 2957342
176 3108265
177 3266409
178 3432097
179 3605666
180 3787467
181 3977861
182 4177239
183 4385994
184 4604537
185 4833306
186 5072740
187 5323313
188 5585505
189 5859833
190 6146816
191 6447003
192 6760967
193 7089299
194 7432618
195 7791567
196 8166824
197 8559069
198 8969035
199 9397474
200 9845164
201 10312927
202 10801607
203 11312080
204 11845265
205 12402104
206 12983601
207 13590769
208 14224686
209 14886458
210 15577234
211 16298212
212 17050639
213 17835813
214 18655065
215 19509801
216 20401462
217 21331548
218 22301629
219 23313328
220 24368324
221 25468365
222 26615264
223 27810910
224 29057246
225 30356317
226 31710220
227 33121140
228 34591339
229 36123177
230 37719090
231 39381607
232 41113365
233 42917077
234 44795565
235 46751763
236 48788713
237 50909557
238 53117571
239 55416136
240 57808759
241 60299078
242 62890875
243 65588056
244 68394674
245 71314927
246 74353172
247 77513908
248 80801816
249 84221750
250 87778708
251 91477898
252 95324698
253 99324684
254 103483632
255 107807529
256 112302573
257 116975172
258 121831963
259 126879839
260 132125912
261 137577558
262 143242423
263 149128391
264 155243647
265 161596652
266 168196183
267 175051297
268 182171385
269 189566161
270 197245661
271 205220288
272 213500804
273 222098343
274 231024409
275 240290920
276 249910190
277 259894960
278 270258409
279 281014186
280 292176374
281 303759545
282 315778780
283 328249663
284 341188297
285 354611368
286 368536090
287 382980254
288 397962282
289 413501182
290 429616642
291 446328963
292 463659174
293 481628967
294 500260763
295 519577753
296 539603890
297 560363918
298 581883402
299 604188762
300 627307270
301 651267109
302 676097420
303 701828265
304 728490702
305 756116825
306 784739743
307 814393691
308 845113982
309 876937136
310 909900797
311 944043865
312 979406503
313 1016030162
314 1053957650
315 1093233153
316 1133902290
317 1176012119
318 1219611227
319 1264749789
320 1311479543
321 1359853920
322 1409928054
323 1461758805
324 1515404880
325 1570926828
326 1628387172
327 1687850356
328 1749382916
329 1813053459
330 1878932770
331 1947093861
332 2017612069
333 2090565098
334 2166033046
335 2244098581
336 2324846927
337 2408365961
338 2494746358
339 2584081585
340 2676468020
341 2772005038
342 2870795095
343 2972943856
344 3078560206
345 3187756471
346 3300648385
347 3417355260
348 3538000089
349 3662709662
350 3791614657
351 3924849742
352 4062553753
353 4204869720
354 4351945048
355 4503931680
356 4660986168
357 4823269812
358 4990948837
359 5164194494
360 5343183207
361 5528096761
362 5719122459
363 5916453220
364 6120287790
365 6330830882
366 6548293385
367 6772892496
368 7004851940
369 7244402184
370 7491780495
371 7747231279
372 8011006231
373 8283364528
374 8564573070
375 8854906699
376 9154648402
377 9464089514
378 9783530032
379 10113278821
380 10453653859
381 10804982493
382 11167601731
383 11541858454
384 11928109730
385 12326723138
386 12738077038
387 13162560803
388 13600575239
389 14052532822
390 14518858034
391 14999987747
392 15496371554
393 16008472095
394 16536765381
395 17081741284
396 17643903794
397 18223771491
398 18821877937
399 19438772103
400 20075018700
401 20731198708
402 21407909806
403 22105766830
404 22825402203
405 23567466511
406 24332628911
407 25121577598
408 25935020489
409 26773685630
410 27638321797
411 28529699031
412 29448609267
413 30395866824
414 31372309122
415 32378797268
416 33416216742
417 34485477942
418 35587516965
419 36723296266
420 37893805322
421 39100061431
422 40343110498
423 41624027665
424 42943918173
425 44303918199
426 45705195606
427 47148950878
428 48636417929
429 50168865097
430 51747595850
431 53373949919
432 55049304201
433 56775073739
434 58552712735
435 60383715632
436 62269618110
437 64211998173
438 66212477321
439 68272721754
440 70394443396
441 72579401227
442 74829402501
443 77146303903
444 79532012984
445 81988489466
446 84517746633
447 87121852599
448 89802931922
449 92563166927
450 95404799294
451 98330131602
452 101341528955
453 104441420542
454 107632301239
455 110916733487
456 114297348927
457 117776850169
458 121358012800
459 125043687114
460 128836800015
461 132740357102
462 136757444655
463 140891231740
464 145144972269
465 149522007327
466 154025767216
467 158659773825
468 163427643029
469 168333087074
470 173379917038
471 178572045280
472 183913488189
473 189408368613
474 195060918717
475 200875482836
476 206856520188
477 213008607821
478 219336443628
479 225844849410
480 232538773942
481 239423296309
482 246503629209
483 253785122155
484 261273265048
485 268973691706
486 276892183450
487 285034672876
488 293407247599
489 302016154282
490 310867802322
491 319968768174
492 329325799531
493 338945819496
494 348835931031
495 359003421488
496 369455767105
497 380200637648
498 391245901476
499 402599630302
500 414270104287
501 426265817197
502 438595481732
503 451268034861
504 464292643429
505 477678709915
506 491435878243
507 505574039526
508 520103338445
509 535034179285
510 550377232375
511 566143440724
512 582344026706
513 598990498817
514 616094658626
515 633668608213
516 651724757246
517 670275830689
518 689334876477
519 708915273400
520 729030738981
521 749695337946
522 770923490619
523 792729981581
524 815129968436
525 838138991049
526 861772980591
527 886048269038
528 910981599049
529 936590133846
530 962891467286
531 989903634283
532 1017645121572
533 1046134878274
534 1075392327381
535 1105437377022
536 1136290432179
537 1167972406450
538 1200504734402
539 1233909383996
540 1268208869345
541 1303426263832
542 1339585213619
543 1376709951026
544 1414825308627
545 1453956733694
546 1494130302670
547 1535372736248
548 1577711414729
549 1621174393679
550 1665790419712
551 1711588947172
552 1758600154825
553 1806854963021
554 1856385051179
555 1907222875877
556 1959401688995
557 2012955556495
558 2067919377790
559 2124328905386
560 2182220764760
561 2241632475020
562 2302602469926
563 2365170119166
564 2429375750481
565 2495260672214
566 2562867196175
567 2632238660927
568 2703419456100
569 2776455046698
570 2851391998248
571 2928278002633
572 3007161904245
573 3088093726747
574 3171124700410
575 3256307290381
576 3343695225246
577 3433343526298
578 3525308537721
579 3619647957080
580 3716420866431
581 3815687764627
582 3917510600050
583 4021952803954
584 4129079324733
585 4238956662992
586 4351652907041
587 4467237769489
588 4585782624803
589 4707360547374
590 4832046350559
591 4959916626418
592 5091049786760
593 5225526104413
594 5363427756096
595 5504838866064
596 5649845550403
597 5798535962428
598 5951000339263
599 6107331049325
600 6267622640718
601 6431971891087
602 6600477858295
603 6773241931933
604 6950367886347
605 7131961934911
606 7318132785055
607 7508991694989
608 7704652531279
609 7905231827993
610 8110848846498
611 8321625637413
612 8537687103560
613 8759161064079
614 8986178320161
615 9218872722260
616 9457381238460
617 9701844024362
618 9952404495170
619 10209209398535
620 10472408889169
621 10742156605295
622 11018609746547
623 11301929153434
624 11592279389001
625 11889828821851
626 12194749711239
627 12507218293266
628 12827414869999
629 13155523899720
630 13491734089345
631 13836238489109
632 14189234589005
633 14550924417065
634 14921514639922
635 15301216666029
636 15690246750223
637 16088826101235
638 16497180991231
639 16915542867584
640 17344148466806
641 17783239931613
642 18233064930016
643 18693876777058
644 19165934558907
645 19649503260122
646 20144853892808
647 20652263629127
648 21172015936674
649 21704400716568
650 22249714444139
651 22808260312896
652 23380348381827
653 23966295724829
654 24566426584568
655 25181072528946
656 25810572610722
657 26455273530522
658 27115529803623
659 27791703929926
660 28484166567644
661 29193296710728
662 29919481870066
663 30663118257864
664 31424610976411
665 32204374211034
666 33002831426598
667 33820415568300
668 34657569266913
669 35514745047931
670 36392405544730
671 37291023717275
672 38211083074649
673 39153077902249
674 40117513493870
675 41104906388604
676 42115784612366
677 43150687924574
678 44210168070543
679 45294789038505
680 46405127321806
681 47541772186948
682 48705325947068
683 49896404240745
684 51115636317113
685 52363665326890
686 53641148618883
687 54948758042495
688 56287180257345
689 57657117048479
690 59059285648265
691 60494419065449
692 61963266420307
693 63466593286684
694 65005182041137
695 66579832219821
696 68191360881924
697 69840602981005
698 71528411743900
699 73255659057175
700 75023235861131
701 76832052552686
702 78683039396376
703 80577146943077
704 82515346457765
705 84498630356121
706 86528012649246
707 88604529398048
708 90729239177373
709 92903223548632
710 95127587542417
711 97403460150684
712 99731994829448
713 102114370010791
714 104551789626226
715 107045483640433
716 109596708595332
717 112206748165001
718 114876913722648
719 117608544918460
720 120403010269005
721 123261707759282
722 126186065456311
723 129177542134595
724 132237627914781
725 135367844915599
726 138569747917929
727 141844925043019
728 145194998443936
729 148621625010955
730 152126497090356
731 155711343219055
732 159377928873191
733 163128057231579
734 166963569954496
735 170886347978338
736 174898312325507
737 179001424930636
738 183197689484353
739 187489152292764
740 191877903153899
741 196366076252339
742 200955851071289
743 205649453322277
744 210449155894605
745 215357279822809
746 220376195273425
747 225508322550649
748 230756133123258
749 236122150670846
750 241608952151194
751 247219168888925
752 252955487685623
753 258820651951004
754 264817462857062
755 270948780515800
756 277217525178805
757 283626678461325
758 290179284590515
759 296878451677522
760 303727353014528
761 310729228398457
762 317887385479970
763 325205201138946
764 332686122886710
765 340333670296518
766 348151436460781
767 356143089477829
768 364312373968102
769 372663112619435
770 381199207762147
771 389924642975310
772 398843484724870
773 407959884032354
774 417278078177770
775 426802392435342
776 436537241842018
777 446487133000792
778 456656665919825
779 467050535886602
780 477673535378665
781 488530556012078
782 499626590527112
783 510966734811752
784 522556189965294
785 534400264402210
786 546504375996147
787 558874054265503
788 571514942601628
789 584432800539717
790 597633506072464
791 611123058010755
792 624907578388660
793 638993314914289
794 653386643468763
795 668094070652779
796 683122236381942
797 698477916532171
798 714168025637168
799 730199619636324
800 746579898675387
801 763316209961318
802 780416050671893
803 797887070920425
804 815737076778305
805 833974033355397
806 852606067938337
807 871641473188648
808 891088710403514
809 910956412837564
810 931253389088277
811 951988626546960
812 973171294914353
813 994810749782952
814 1016916536287922
815 1039498392828697
816 1062566254859514
817 1086130258753327
818 1110200745738671
819 1134788265910900
820 1159903582319171
821 1185557675132166
822 1211761745882737
823 1238527221791851
824 1265865760174766
825 1293789252931405
826 1322309831119805
827 1351439869617259
828 1381191991870577
829 1411579074734150
830 1442614253399780
831 1474310926419426
832 1506682760823228
833 1539743697332415
834 1573507955672496
835 1607990039985374
836 1643204744342725
837 1679167158362659
838 1715892672933149
839 1753396986042209
840 1791696108717126
841 1830806371076165
842 1870744428493045
843 1911527267875312
844 1953172214061950
845 1995696936341086
846 2039119455088013
847 2083458148528457
848 2128731759627697
849 2174959403108022
850 2222160572595940
851 2270355147905426
852 2319563402455204
853 2369806010824137
854 2421104056447220
855 2473479039455202
856 2526952884658843
857 2581547949682147
858 2637287033247981
859 2694193383616078
860 2752290707176762
861 2811603177205375
862 2872155442778530
863 2933972637854446
864 2997080390523401
865 3061504832428506
866 3127272608359678
867 3194410886024664
868 3262947366002363
869 3332910291878122
870 3404328460567012
871 3477231232827520
872 3551648543968665
873 3627610914753015
874 3705149462501387
875 3784295912403226
876 3865082609032978
877 3947542528078787
878 4031709288287417
879 4117617163626673
880 4205301095670916
881 4294796706216035
882 4386140310124252
883 4479368928403790
884 4574520301528214
885 4671632903000008
886 4770745953160575
887 4871899433253987
888 4975134099748649
889 5080491498919027
890 5188013981692858
891 5297744718769869
892 5409727716016706
893 5524007830140448
894 5640630784649943
895 5759643186107216
896 5881092540672546
897 6005027270950820
898 6131496733145469
899 6260551234522767
900 6392242051193026
901 6526621446215959
902 6663742688032675
903 6803660069230691
904 6946428925650449
905 7092105655838195
906 7240747740849538
907 7392413764411863
908 7547163433450920
909 7705057598988029
910 7866158277412792
911 8030528672143249
912 8198233195675464
913 8369337492028921
914 8543908459597867
915 8722014274413723
916 8903724413825076
917 9089109680604445
918 9278242227490669
919 9471195582169338
920 9668044672702323
921 9868865853414219
922 10073736931243429
923 10282737192564728
924 10495947430494422
925 10713449972684266
926 10935328709611711
927 11161669123375439
928 11392558317009043
929 11628085044316632
930 11868339740241664
931 12113414551780045
932 12363403369442749
933 12618401859279201
934 12878507495472445
935 13143819593517410
936 13414439343986958
937 13690469846901122
938 13972016146707429
939 14259185267882193
940 14552086251164305
941 14850830190435401
942 15155530270253972
943 15466301804054642
944 15783262273025030
945 16106531365673416
946 16436231018094874
947 16772485454952436
948 17115421231185756
949 17465167274455037
950 17821854928335306
951 18185617996275140
952 18556592786332809
953 18934918156699593
954 19320735562031009
955 19714189100593054
956 20115425562238700
957 20524594477229874
958 20941848165921068
959 21367341789317016
960 21801233400519640
961 22243683997081049
962 22694857574276428
963 23154921179309862
964 23624044966475276
965 24102402253286455
966 24590169577589367
967 25087526755677506
968 25594656941425636
969 26111746686458389
970 26638986001370899
971 27176568418025575
972 27724691052935866
973 28283554671757824
974 28853363754908947
975 29434326564333425
976 30026655211431514
977 30630565726175256
978 31246278127431958
979 31874016494511080
980 32514009039956193
981 33166488183606900
982 33831690627949373
983 34509857434776495
984 35201234103183681
985 35906070648920056
986 36624621685115494
987 37357146504409080
988 38103909162506730
989 38865178563184895
990 39641228544769746
991 40432337968115894
992 41238790806107177
993 42060876234705903
994 42898888725578756
995 43753128140327406
996 44623899826345169
997 45511514714330818
998 46416289417487630
999 47338546332432533
1000 48278613741845757