0 1
1 1
2 0
3 1
4 1
5 2
6 2
7 1
8 3
9 3
10 3
11 3
12 4
13 5
14 5
15 7
16 8
17 8
18 9
19 10
20 13
21 15
22 14
23 17
24 20
25 23
26 24
27 26
28 31
29 34
30 38
31 41
32 46
33 52
34 55
35 62
36 70
37 75
38 82
39 90
40 103
41 112
42 118
43 131
44 145
45 161
46 172
47 185
48 208
49 225
50 244
51 265
52 288
53 316
54 339
55 370
56 404
57 435
58 469
59 507
60 557
61 601
62 640
63 696
64 755
65 818
66 876
67 939
68 1022
69 1100
70 1181
71 1269
72 1368
73 1474
74 1575
75 1698
76 1828
77 1956
78 2097
79 2246
80 2423
81 2595
82 2762
83 2965
84 3182
85 3411
86 3636
87 3881
88 4167
89 4450
90 4750
91 5069
92 5416
93 5789
94 6160
95 6579
96 7028
97 7480
98 7965
99 8485
100 9061
101 9645
102 10240
103 10907
104 11619
105 12370
106 13130
107 13946
108 14855
109 15779
110 16753
111 17790
112 18896
113 20071
114 21275
115 22586
116 23978
117 25416
118 26936
119 28550
120 30304
121 32103
122 33962
123 35991
124 38135
125 40392
126 42720
127 45188
128 47866
129 50631
130 53532
131 56602
132 59860
133 63294
134 66848
135 70660
136 74682
137 78859
138 83264
139 87910
140 92877
141 98029
142 103376
143 109106
144 115150
145 121484
146 128060
147 135007
148 142417
149 150115
150 158188
151 166683
152 175648
153 185069
154 194855
155 205241
156 216170
157 227545
158 239492
159 252058
160 265359
161 279195
162 293608
163 308881
164 324930
165 341738
166 359220
167 377603
168 397057
169 417295
170 438477
171 460714
172 484066
173 508539
174 534020
175 560867
176 589030
177 618380
178 649106
179 681325
180 715242
181 750552
182 787348
183 826106
184 866703
185 909135
186 953326
187 999629
188 1048335
189 1099060
190 1152042
191 1207506
192 1265600
193 1326317
194 1389550
195 1455902
196 1525304
197 1597618
198 1673179
199 1752190
200 1835023
201 1921275
202 2011110
203 2105311
204 2203774
205 2306505
206 2413466
207 2525278
208 2642398
209 2764328
210 2891512
211 3024338
212 3163110
213 3307908
214 3458615
215 3616233
216 3780782
217 3952082
218 4130742
219 4317205
220 4512063
221 4714850
222 4925934
223 5146538
224 5376665
225 5616436
226 5865890
227 6126105
228 6397898
229 6680635
230 6975117
231 7282115
232 7602184
233 7935590
234 8282375
235 8644134
236 9021104
237 9413227
238 9821512
239 10246860
240 10690368
241 11151495
242 11631032
243 12131029
244 12651675
245 13193401
246 13756554
247 14342920
248 14953983
249 15589120
250 16249723
251 16937275
252 17652920
253 18397279
254 19170787
255 19976146
256 20814010
257 21684665
258 22589985
259 23531643
260 24511645
261 25529683
262 26587256
263 27687812
264 28832170
265 30021309
266 31256298
267 32540300
268 33875875
269 35262745
270 36703501
271 38200836
272 39757054
273 41373671
274 43051930
275 44796432
276 46608884
277 48490325
278 50444202
279 52473794
280 54582677
281 56771271
282 59042644
283 61402521
284 63853063
285 66396635
286 69035670
287 71775765
288 74621659
289 77573935
290 80637440
291 83817288
292 87117838
293 90542494
294 94094385
295 97781272
296 101607040
297 105574584
298 109690126
299 113959955
300 118390717
301 122984523
302 127747420
303 132689288
304 137814901
305 143129405
306 148638250
307 154351214
308 160277011
309 166418650
310 172784949
311 179385480
312 186228762
313 193321730
314 200671370
315 208291211
316 216189224
317 224372210
318 232851713
319 241639400
320 250747606
321 260182411
322 269955330
323 280083542
324 290577230
325 301446860
326 312703752
327 324365420
328 336447678
329 348958741
330 361915057
331 375334143
332 389232278
333 403623610
334 418522389
335 433952316
336 449929570
337 466468435
338 483590247
339 501316865
340 519670762
341 538666236
342 558325280
343 578677677
344 599744050
345 621545359
346 644103912
347 667451050
348 691615829
349 716616830
350 742484412
351 769250883
352 796946628
353 825599441
354 855237801
355 885903104
356 917626948
357 950438486
358 984376534
359 1019481495
360 1055794702
361 1093346205
362 1132177346
363 1172340530
364 1213875610
365 1256823359
366 1301226970
367 1347142098
368 1394621809
369 1443705225
370 1494447655
371 1546908078
372 1601143052
373 1657205499
374 1715150350
375 1775050649
376 1836966184
377 1900953985
378 1967084914
379 2035432438
380 2106071846
381 2179063688
382 2254484064
383 2332425198
384 2412962922
385 2496174104
386 2582140342
387 2670960895
388 2762731447
389 2857529965
390 2955457030
391 3056618877
392 3161119372
393 3269057916
394 3380537450
395 3495686673
396 3614617162
397 3737436904
398 3864274003
399 3995261495
400 4130534928
401 4270211290
402 4414429780
403 4563351990
404 4717118925
405 4875873685
406 5039766742
407 5208974175
408 5383668129
409 5563997510
410 5750143525
411 5942296760
412 6140644960
413 6345371454
414 6556666225
415 6774754810
416 6999841734
417 7232127762
418 7471841911
419 7719222540
420 7974512450
421 8237930665
422 8509728406
423 8790188963
424 9079569285
425 9378130931
426 9686147980
427 10003930323
428 10331784752
429 10669989165
430 11018866165
431 11378754407
432 11749990600
433 12132906664
434 12527847277
435 12935207149
436 13355354674
437 13788656059
438 14235518108
439 14696362950
440 15171621468
441 15661695624
442 16167032920
443 16688127593
444 17225441950
445 17779446237
446 18350632126
447 18939542725
448 19546719199
449 20172668560
450 20817961183
451 21483192619
452 22168959820
453 22875856903
454 23604499109
455 24355573281
456 25129735670
457 25927642477
458 26750009636
459 27597579142
460 28471107604
461 29371319100
462 30299003462
463 31255017222
464 32240180895
465 33255329983
466 34301334270
467 35379138661
468 36489690717
469 37633898125
470 38812759621
471 40027314895
472 41278610390
473 42567695677
474 43895656635
475 45263680045
476 46672920470
477 48124539263
478 49619783760
479 51159946029
480 52746344517
481 54380261919
482 56063077862
483 57796269281
484 59581273618
485 61419557286
486 63312642722
487 65262160575
488 67269755254
489 69337028970
490 71465713590
491 73657608250
492 75914531124
493 78238313938
494 80630850575
495 83094179961
496 85630309814
497 88241269460
498 90929215052
499 93696375340
500 96545027093
501 99477414320
502 102495921952
503 105603079381
504 108801379575
505 112093366114
506 115481675210
507 118969102050
508 122558474128
509 126252582450
510 130054405805
511 133967029848
512 137993583928
513 142137232982
514 146401243805
515 150789094736
516 155304243858
517 159950196045
518 164730645869
519 169649407485
520 174710377375
521 179917433878
522 185274664546
523 190786369606
524 196456828540
525 202290411062
526 208291635000
527 214465255377
528 220816096025
529 227348960234
530 234068927723
531 240981250165
532 248091263794
533 255404383185
534 262926190790
535 270662576820
536 278619440896
537 286802776860
538 295218861032
539 303874166765
540 312775309987
541 321928920044
542 331341940810
543 341021634796
544 350975277665
545 361210304301
546 371734389150
547 382555559077
548 393681976349
549 405121824220
550 416883691818
551 428976446223
552 441409113326
553 454190868792
554 467331165204
555 480839909793
556 494727075960
557 509002816890
558 523677712385
559 538762659830
560 554268802505
561 570207364422
562 586590041640
563 603429013165
564 620736543625
565 638525168725
566 656807811750
567 675597927336
568 694909216247
569 714755485900
570 735151148849
571 756111059797
572 777650361524
573 799784473473
574 822529262150
575 845901274078
576 869917232946
577 894594183261
578 919949821073
579 946002355751
580 972770408735
581 1000272811606
582 1028529112750
583 1057559591663
584 1087384752342
585 1118025558246
586 1149503591670
587 1181841243812
588 1215061342714
589 1249186977140
590 1284242147339
591 1320251559985
592 1357240421758
593 1395234433165
594 1434260017700
595 1474344617169
596 1515516052282
597 1557802705535
598 1601233952595
599 1645839997680
600 1691651733777
601 1738700487984
602 1787018685610
603 1836639869622
604 1887598048293
605 1939928002456
606 1993665502166
607 2048847548766
608 2105511901642
609 2163696857462
610 2223442088405
611 2284788394745
612 2347777431630
613 2412451703369
614 2478854879455
615 2547032170091
616 2617029506648
617 2688893784045
618 2762673424021
619 2838418170425
620 2916178909429
621 2996007352205
622 3077956890862
623 3162082637170
624 3248440587630
625 3337088012871
626 3428083763208
627 3521488577208
628 3617364471662
629 3715774479186
630 3816783725073
631 3920459121287
632 4026869019390
633 4136083207609
634 4248173333198
635 4363213390696
636 4481278677620
637 4602446104234
638 4726794938471
639 4854406555765
640 4985364197882
641 5119752592090
642 5257659054450
643 5399173544700
644 5544387615645
645 5693394908885
646 5846291567506
647 6003176643905
648 6164151319425
649 6329318582475
650 6498784623952
651 6672658462495
652 6851051493520
653 7034077507720
654 7221853254256
655 7414499062459
656 7612137531718
657 7814893928830
658 8022897157661
659 8236279470675
660 8455176151324
661 8679725048723
662 8910068010770
663 9146350965915
664 9388722593100
665 9637334967879
666 9892344121440
667 10153910563590
668 10422198306239
669 10697374475690
670 10979611100236
671 11269084673174
672 11565975574054
673 11870468106225
674 12182751264590
675 12503019528786
676 12831471211910
677 13168308990002
678 13513741163063
679 13867981314537
680 14231247916208
681 14603763766479
682 14985757833358
683 15377465393595
684 15779126360023
685 16190986108267
686 16613296248880
687 17046315303402
688 17490307472882
689 17945542195405
690 18412296436955
691 18890854172219
692 19381505668300
693 19884547558090
694 20400283862650
695 20929027026017
696 21471095847738
697 22026816169554
698 22596522536202
699 23180557803150
700 23779272633164
701 24393024849217
702 25022181803200
703 25667120583766
704 26328225946421
705 27005891375746
706 27700520128462
707 28412526131355
708 29142332442437
709 29890370740193
710 30657084277640
711 31442927280581
712 32248364050500
713 33073869118578
714 33919928611280
715 34787041580140
716 35675717452052
717 36586476929199
718 37519854150157
719 38476396276965
720 39456662867865
721 40461225125214
722 41490668965610
723 42545595332931
724 43626617631320
725 44734363122228
726 45869474333650
727 47032610234380
728 48224444353059
729 49445664207425
730 50696975089534
731 51979099411155
732 53292775598682
733 54638758352127
734 56017820494303
735 57430754691568
736 58878370306670
737 60361494612052
738 61880975609442
739 63437681598535
740 65032500440151
741 66666338709156
742 68340125644722
743 70054813652666
744 71811375150025
745 73610804380777
746 75454119352050
747 77342363381616
748 79276602795663
749 81257926350870
750 83287450088176
751 85366316629995
752 87495693872500
753 89676775412694
754 91910783023719
755 94198968922939
756 96542611922408
757 98943019044644
758 101401529236095
759 103919512962337
760 106498371340588
761 109139535253250
762 111844470442610
763 114614678266389
764 117451691887975
765 120357078657273
766 123332442732848
767 126379427172448
768 129499711154484
769 132695009418470
770 135967078533954
771 139317716198221
772 142748759693212
773 146262086613598
774 149859618187805
775 153543322250309
776 157315208614854
777 161177331246890
778 165131793128585
779 169180745989642
780 173326389331301
781 177570969535824
782 181916786484600
783 186366194701355
784 190921598769475
785 195585456514126
786 200360282567320
787 205248651168741
788 210253192904927
789 215376594261005
790 220621605688446
791 225991041033127
792 231487775774104
793 237114748175627
794 242874963798990
795 248771499428293
796 254807497538228
797 260986169285643
798 267310800903212
799 273784753668525
800 280411462917394
801 287194437257947
802 294137267146832
803 301243626657984
804 308517268051671
805 315962026014299
806 323581822559290
807 331380670818895
808 339362671258244
809 347532011533017
810 355892976907513
811 364449949936806
812 373207408591990
813 382169928070577
814 391342186886755
815 400728972148169
816 410335173044750
817 420165784944254
818 430225917877562
819 440520796956075
820 451055761460138
821 461836264394423
822 472867883639840
823 484156324614168
824 495707414002500
825 507527105457404
826 519621486298134
827 531996782737762
828 544659355617208
829 557615700786450
830 570872462652480
831 584436434376602
832 598314555986726
833 612513917244675
834 627041765906561
835 641905514807852
836 657112734404336
837 672671158436009
838 688588695167847
839 704873428644450
840 721533618072965
841 738577697988825
842 756014292876580
843 773852221167470
844 792100488127225
845 810768293648512
846 829865041440940
847 849400346226625
848 869384029191329
849 889826119288155
850 910736870863802
851 932126764837664
852 954006507062506
853 976387032733407
854 999279517695304
855 1022695388045474
856 1046646311762088
857 1071144206661174
858 1096201255367981
859 1121829907881556
860 1148042881686596
861 1174853163028805
862 1202274026092760
863 1230319039064031
864 1259002056340935
865 1288337229191440
866 1318339018478760
867 1349022204647892
868 1380401883146067
869 1412493467339775
870 1445312711555541
871 1478875713837316
872 1513198915075640
873 1548299105741629
874 1584193441347485
875 1620899455637779
876 1658435051556380
877 1696818512413304
878 1736068521995930
879 1776204169244125
880 1817244949651830
881 1859210768494640
882 1902121966125582
883 1945999327026846
884 1990864071795964
885 2036737871848496
886 2083642867000854
887 2131601679512093
888 2180637410029422
889 2230773643015595
890 2282034477110353
891 2334444530452630
892 2388028941273784
893 2442813378201307
894 2498824061491375
895 2556087781191514
896 2614631888050868
897 2674484309294290
898 2735673575685298
899 2798228829596265
900 2862179828679461
901 2927556952178027
902 2994391234558578
903 3062714379003502
904 3132558749827260
905 3203957392996194
906 3276944060526702
907 3351553230229680
908 3427820103215616
909 3505780613285233
910 3585471467049857
911 3666930153407623
912 3750194946811070
913 3835304922792120
914 3922299987348170
915 4011220902134225
916 4102109276212010
917 4195007588550580
918 4289959224645504
919 4387008489728745
920 4486200616330622
921 4587581775476059
922 4691199121548666
923 4797100812439842
924 4905336003643995
925 5015954876955518
926 5129008674542016
927 5244549726870005
928 5362631453248394
929 5483308377451534
930 5606636181065172
931 5732671719288575
932 5861473028872094
933 5993099351400287
934 6127611173984333
935 6265070264543142
936 6405539666032220
937 6549083728518584
938 6695768159118715
939 6845660043042045
940 6998827857311907
941 7155341489664420
942 7315272298754286
943 7478693143991601
944 7645678383481700
945 7816303914390002
946 7990647220539000
947 8168787412191630
948 8350805232098562
949 8536783080505605
950 8726805086632279
951 8920957134156461
952 9119326876651688
953 9322003772450730
954 9529079141231790
955 9740646213531570
956 9956800130237846
957 10177637988479327
958 10403258909916467
959 10633764073729125
960 10869256740061438
961 11109842280552392
962 11355628259749398
963 11606724479166316
964 11863242982247315
965 12125298111550223
966 12393006575442262
967 12666487504791029
968 12945862468466735
969 13231255512511525
970 13522793256335714
971 13820604932965950
972 14124822416413276
973 14435580273432960
974 14753015842626550
975 15077269304268850
976 15408483689164586
977 15746804944598493
978 16092382028210423
979 16445366958674645
980 16805914854355246
981 17174183981421192
982 17550335864378660
983 17934535351090833
984 18326950629858988
985 18727753310521068
986 19137118518325814
987 19555224974932995
988 19982255029088530
989 20418394717129130
990 20863833893218521
991 21318766291525810
992 21783389572323354
993 22257905398512121
994 22742519546339650
995 23237442004401017
996 23742886998348244
997 24259073085592569
998 24786223285101262
999 25324565154339160
1000 25874330850965114