0 1
1 1
2 0
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 3
12 4
13 3
14 4
15 5
16 6
17 6
18 6
19 8
20 9
21 10
22 10
23 12
24 14
25 15
26 16
27 19
28 21
29 22
30 24
31 27
32 31
33 34
34 36
35 40
36 46
37 48
38 52
39 58
40 64
41 69
42 74
43 82
44 91
45 98
46 104
47 115
48 127
49 136
50 145
51 159
52 174
53 186
54 200
55 218
56 238
57 254
58 272
59 296
60 322
61 343
62 366
63 398
64 430
65 460
66 492
67 531
68 572
69 612
70 652
71 703
72 757
73 806
74 860
75 925
76 993
77 1058
78 1128
79 1208
80 1296
81 1380
82 1468
83 1571
84 1681
85 1787
86 1900
87 2031
88 2170
89 2306
90 2448
91 2613
92 2786
93 2958
94 3138
95 3342
96 3562
97 3776
98 4004
99 4262
100 4532
101 4800
102 5088
103 5405
104 5742
105 6080
106 6434
107 6830
108 7247
109 7666
110 8110
111 8599
112 9110
113 9633
114 10182
115 10783
116 11415
117 12058
118 12736
119 13474
120 14254
121 15046
122 15880
123 16785
124 17738
125 18710
126 19736
127 20840
128 22003
129 23198
130 24448
131 25799
132 27220
133 28674
134 30200
135 31846
136 33569
137 35342
138 37203
139 39194
140 41288
141 43442
142 45700
143 48116
144 50652
145 53257
146 55996
147 58916
148 61974
149 65128
150 68436
151 71956
152 75643
153 79454
154 83442
155 87679
156 92114
157 96698
158 101498
159 106590
160 111913
161 117420
162 123188
163 129287
164 135671
165 142280
166 149188
167 156485
168 164128
169 172030
170 180296
171 189021
172 198134
173 207580
174 217452
175 227853
176 238726
177 249992
178 261748
179 274139
180 287077
181 300481
182 314478
183 329201
184 344572
185 360504
186 377138
187 394610
188 412844
189 431746
190 451472
191 472174
192 493776
193 516166
194 539520
195 564023
196 589560
197 616050
198 643674
199 672610
200 702770
201 734066
202 766666
203 800809
204 836384
205 873274
206 911720
207 951942
208 993835
209 1037294
210 1082556
211 1129865
212 1179142
213 1230252
214 1283460
215 1339053
216 1396929
217 1456956
218 1519430
219 1584676
220 1652563
221 1722977
222 1796236
223 1872694
224 1952232
225 2034730
226 2120522
227 2210013
228 2303096
229 2399608
230 2499974
231 2604613
232 2713390
233 2826182
234 2943452
235 3065627
236 3192620
237 3324292
238 3461118
239 3603637
240 3751724
241 3905244
242 4064746
243 4230799
244 4403266
245 4582074
246 4767790
247 4961032
248 5161716
249 5369732
250 5585724
251 5810389
252 6043651
253 6285386
254 6536336
255 6797252
256 7068078
257 7348714
258 7639976
259 7942679
260 8256796
261 8582272
262 8919950
263 9270800
264 9634798
265 10011861
266 10402984
267 10809241
268 11230572
269 11667002
270 12119607
271 12589511
272 13076794
273 13581448
274 14104664
275 14647740
276 15210746
277 15793700
278 16398012
279 17025043
280 17674920
281 18347764
282 19045062
283 19768366
284 20517862
285 21293744
286 22097624
287 22931246
288 23794868
289 24688742
290 25614680
291 26574623
292 27568863
293 28597778
294 29663412
295 30767817
296 31911501
297 33094890
298 34320188
299 35589771
300 36904248
301 38264090
302 39671856
303 41130132
304 42639598
305 44200996
306 45817062
307 47490681
308 49222744
309 51014092
310 52867748
311 54787019
312 56772899
313 58826405
314 60950974
315 63150195
316 65425294
317 67777522
318 70210712
319 72728778
320 75333250
321 78025598
322 80810060
323 83691041
324 86670330
325 89749634
326 92933716
327 96227491
328 99632962
329 103152298
330 106790716
331 110553609
332 114443442
333 118462754
334 122617248
335 126913049
336 131352999
337 135939944
338 140680428
339 145581138
340 150645372
341 155876556
342 161281872
343 166868716
344 172641086
345 178602830
346 184761928
347 191126725
348 197701709
349 204491394
350 211504698
351 218750889
352 226235077
353 233962556
354 241943200
355 250187318
356 258700837
357 267489850
358 276565290
359 285938662
360 295616844
361 305606666
362 315920490
363 326571039
364 337566058
365 348913571
366 360627320
367 372721286
368 385204560
369 398086242
370 411381458
371 425106060
372 439270217
373 453884348
374 468965422
375 484530911
376 500592398
377 517161966
378 534258324
379 551900910
380 570103048
381 588878344
382 608247676
383 628232694
384 648848566
385 670110640
386 692042248
387 714667432
388 738003368
389 762067584
390 786886024
391 812485311
392 838885024
393 866105098
394 894174158
395 923122107
396 952970971
397 983743174
398 1015470804
399 1048187053
400 1081916653
401 1116685252
402 1152528408
403 1189482845
404 1227576862
405 1266839202
406 1307309422
407 1349028487
408 1392028186
409 1436340898
410 1482010876
411 1529083455
412 1577594424
413 1627580542
414 1679090780
415 1732175570
416 1786875328
417 1843231448
418 1901298198
419 1961131792
420 2022777626
421 2086282265
422 2151706146
423 2219111669
424 2288549778
425 2360072956
426 2433748416
427 2509645196
428 2587820895
429 2668334326
430 2751259952
431 2836674740
432 2924643324
433 3015231464
434 3108522224
435 3204600946
436 3303539841
437 3405413196
438 3510312938
439 3618333782
440 3729556941
441 3844065440
442 3961961236
443 4083349884
444 4208322025
445 4336970646
446 4469409237
447 4605754593
448 4746108312
449 4890574574
450 5039279296
451 5192351906
452 5349906222
453 5512058720
454 5678949068
455 5850720970
456 6027501658
457 6209421152
458 6396634550
459 6589301354
460 6787563280
461 6991566124
462 7201481672
463 7417486475
464 7639739226
465 7868402620
466 8103666772
467 8345727926
468 8594762938
469 8850953018
470 9114509592
471 9385649697
472 9664570589
473 9951474676
474 10246595936
475 10550174789
476 10862431578
477 11183591528
478 11513913872
479 11853665302
480 12203090920
481 12562441729
482 12932005012
483 13312076175
484 13702927810
485 14104839694
486 14518129880
487 14943125347
488 15380129721
489 15829454264
490 16291450882
491 16766481829
492 17254884892
493 17757005796
494 18273234764
495 18803972379
496 19349593844
497 19910484052
498 20487074732
499 21079808713
500 21689103534
501 22315386656
502 22959135282
503 23620840109
504 24300964370
505 24999982790
506 25718423622
507 26456829165
508 27215713514
509 27995604386
510 28797085444
511 29620756187
512 30467187655
513 31336964906
514 32230733320
515 33149155823
516 34092865750
517 35062511688
518 36058807376
519 37082485199
520 38134247288
521 39214813032
522 40324970968
523 41465530025
524 42637268624
525 43840984174
526 45077547138
527 46347851833
528 47652760275
529 48993155292
530 50369998948
531 51784278746
532 53236948591
533 54728986964
534 56261455792
535 57835444614
536 59452010528
537 61112235826
538 62817292664
539 64568384210
540 66366679538
541 68213375994
542 70109768028
543 72057182551
544 74056912606
545 76110283159
546 78218721650
547 80383692089
548 82606624381
549 84888983410
550 87232343200
551 89638318838
552 92108490558
553 94644477186
554 97248014816
555 99920884162
556 102664830715
557 105481643426
558 108373236420
559 111341571694
560 114388578273
561 117516231360
562 120726639932
563 124021967229
564 127404342796
565 130875946566
566 134439103520
567 138096196503
568 141849575185
569 145701646866
570 149654971736
571 153712174478
572 157875848213
573 162148648178
574 166533393704
575 171032976185
576 175650254934
577 180388158228
578 185249791122
579 190238336034
580 195356945742
581 200608849210
582 205997464282
583 211526293051
584 217198811358
585 223018577746
586 228989353256
587 235114992130
588 241399324098
589 247846269570
590 254459967074
591 261244656820
592 268204556330
593 275343985294
594 282667495088
595 290179748501
596 297885391016
597 305789178952
598 313896116340
599 322211331571
600 330739938122
601 339487170690
602 348458532464
603 357659659926
604 367096180381
605 376773855428
606 386698732848
607 396877006835
608 407314870054
609 418018659880
610 428995021668
611 440250762589
612 451792692522
613 463627781631
614 475763330936
615 488206817844
616 500965729431
617 514047730122
618 527460838284
619 541213265623
620 555313242759
621 569769194002
622 584589923278
623 599784447427
624 615361811492
625 631331271108
626 647702492950
627 664485374021
628 681689850112
629 699326090626
630 717404704672
631 735936552279
632 754932547830
633 774403859000
634 794362125438
635 814819265044
636 835787260140
637 857278372050
638 879305370852
639 901881328301
640 925019397004
641 948733037348
642 973036253400
643 997943380372
644 1023468853376
645 1049627441742
646 1076434501120
647 1103905749375
648 1132057023389
649 1160904524872
650 1190465088340
651 1220755942631
652 1251794457518
653 1283598403532
654 1316186230728
655 1349576819321
656 1383789217068
657 1418842909200
658 1454758110188
659 1491555508738
660 1529255984871
661 1567880897012
662 1607452391820
663 1647993131305
664 1689525997997
665 1732074401350
666 1775662596079
667 1820315399136
668 1866057885908
669 1912915702928
670 1960915408604
671 2010084176864
672 2060449474622
673 2112039393722
674 2164883011064
675 2219010071399
676 2274450654892
677 2331235526946
678 2389396510360
679 2448966158716
680 2509977407541
681 2572463939570
682 2636460575642
683 2702002936970
684 2769127074832
685 2837869856879
686 2908269378870
687 2980364607794
688 3054194995910
689 3129800889036
690 3207223955460
691 3286506811439
692 3367692624759
693 3450825534366
694 3535951104340
695 3623115936656
696 3712367249846
697 3803753320576
698 3897323966948
699 3993130134598
700 4091223459164
701 4191656736898
702 4294484419704
703 4399762190669
704 4507546507351
705 4617895089142
706 4730867441876
707 4846524417286
708 4964927726218
709 5086140457590
710 5210227629916
711 5337255723376
712 5467292178692
713 5600405939834
714 5736668030534
715 5876151065915
716 6018928733346
717 6165076356214
718 6314671501784
719 6467793472791
720 6624522761524
721 6784941642266
722 6949134813250
723 7117188861630
724 7289191691127
725 7465233154082
726 7645405712694
727 7829803885305
728 8018523655300
729 8211663124498
730 8409323209238
731 8611607070891
732 8818619486823
733 9030467540982
734 9247261362160
735 9469113514559
736 9696138352381
737 9928452744310
738 10166176840392
739 10409433442577
740 10658347334580
741 10913046031202
742 11173660591300
743 11440324962674
744 11713175274253
745 11992350630658
746 12277993963510
747 12570251345326
748 12869271251373
749 13175205399986
750 13488209637336
751 13808443225928
752 14136068078089
753 14471249631692
754 14814157780092
755 15164966135967
756 15523851226118
757 15890993408822
758 16266577861388
759 16650793797588
760 17043833635728
761 17445893967953
762 17857176584560
763 18277887661851
764 18708236905058
765 19148438551534
766 19598712450410
767 20059283226822
768 20530379371324
769 21012234304780
770 21505087511856
771 22009183661137
772 22524771664056
773 23052105797730
774 23591446879070
775 24143061359668
776 24707220349027
777 25284200780066
778 25874286652180
779 26477768087590
780 27094940310109
781 27726104869424
782 28371570952360
783 29031654390884
784 29706676605316
785 30396965891620
786 31102858790040
787 31824699055910
788 32562836566461
789 33317628664766
790 34089441592864
791 34878649436679
792 35685632971115
793 36510781077822
794 37354492257992
795 38217173521470
796 39099239189067
797 40001112393846
798 40923226649630
799 41866024703302
800 42829957304036
801 43815484754488
802 44823078572724
803 45853220301719
804 46906400217356
805 47983118966872
806 49083889318108
807 50209234904887
808 51359688899998
809 52535795736578
810 53738112928598
811 54967209782869
812 56223666018306
813 57508073567982
814 58821038489666
815 60163179638859
816 61535127224078
817 62937524703608
818 64371030794892
819 65836318089478
820 67334071556481
821 68864990542480
822 70429790869848
823 72029203398090
824 73663972491601
825 75334858094248
826 77042637941836
827 78788106082976
828 80572071271798
829 82395359150940
830 84258814588908
831 86163300124911
832 88109694312987
833 90098894029054
834 92131816894762
835 94209399687722
836 96332596627202
837 98502381780892
838 100719751620716
839 102985723384711
840 105301333280642
841 107667639029065
842 110085722549762
843 112556688249048
844 115081661176908
845 117661789695460
846 120298248291124
847 122992235804781
848 125744973538802
849 128557708041806
850 131431714069092
851 134368292759585
852 137368769666322
853 140434497685832
854 143566860175658
855 146767269058886
856 150037162787237
857 153378009439866
858 156791309967270
859 160278596247619
860 163841428996448
861 167481400999232
862 171200140522660
863 174999309328898
864 178880600490800
865 182845741797354
866 186896499356208
867 191034675510675
868 195262106609687
869 199580666588248
870 203992270730016
871 208498873535557
872 213102466433840
873 217805081514758
874 222608795502196
875 227515727564151
876 232528036930587
877 237647926837592
878 242877648697230
879 248219499834220
880 253675821036379
881 259249000713200
882 264941479256016
883 270755746721498
884 276694340316785
885 282759848756346
886 288954916847188
887 295282243121015
888 301744577234482
889 308344724543970
890 315085550952572
891 321969980443471
892 329000992423298
893 336181626550278
894 343514987797824
895 351004243931003
896 358652622805028
897 366463417404658
898 374439991179950
899 382585775484989
900 390904266761504
901 399399031869602
902 408073713698076
903 416932028516937
904 425977763110806
905 435214780395352
906 444647025280250
907 454278521987624
908 464113371122231
909 474155755550134
910 484409946588380
911 494880301262027
912 505571259296921
913 516487349305072
914 527633195311852
915 539013513932369
916 550633111310382
917 562496889635520
918 574609853988004
919 586977109466295
920 599603858080802
921 612495405590242
922 625657168697422
923 639094672161656
924 652813545586646
925 666819530635607
926 681118488621936
927 695716397538784
928 710619348799823
929 725833554861466
930 741365357165579
931 757221223142714
932 773407742927740
933 789931637329416
934 806799766224632
935 824019125526238
936 841596843820598
937 859540190779530
938 877856586009764
939 896553595944500
940 915638930466816
941 935120451776338
942 955006183665946
943 975304308415869
944 996023163377098
945 1017171250291972
946 1038757245064244
947 1060789994655335
948 1083278513603280
949 1106231993856934
950 1129659815073050
951 1153571541475445
952 1177976918357995
953 1202885882462700
954 1228308572798516
955 1254255327492013
956 1280736680314930
957 1307763371564096
958 1335346359479576
959 1363496817125263
960 1392226128867728
961 1421545901851692
962 1451467978064812
963 1482004431180976
964 1513167563060517
965 1544969915883918
966 1577424284793678
967 1610543714807339
968 1644341497339189
969 1678831182949832
970 1714026594696584
971 1749941825105417
972 1786591232664645
973 1823989455308296
974 1862151424494842
975 1901092362187963
976 1940827777430570
977 1981373480556982
978 2022745598013886
979 2064960569415356
980 2108035144199554
981 2151986396580238
982 2196831741190332
983 2242588930236286
984 2289276050201326
985 2336911537626030
986 2385514195628432
987 2435103191133797
988 2485698051664204
989 2537318682042304
990 2589985381743912
991 2643718842282029
992 2698540144143864
993 2754470774360298
994 2811532644825010
995 2869748089873624
996 2929139863289913
997 2989731156876490
998 3051545619826152
999 3114607356393341
1000 3178940923117197