0 -2
1 3
2 20
3 55
4 114
5 203
6 328
7 495
8 710
9 979
10 1308
11 1703
12 2170
13 2715
14 3344
15 4063
16 4878
17 5795
18 6820
19 7959
20 9218
21 10603
22 12120
23 13775
24 15574
25 17523
26 19628
27 21895
28 24330
29 26939
30 29728
31 32703
32 35870
33 39235
34 42804
35 46583
36 50578
37 54795
38 59240
39 63919
40 68838
41 74003
42 79420
43 85095
44 91034
45 97243
46 103728
47 110495
48 117550
49 124899
50 132548
51 140503
52 148770
53 157355
54 166264
55 175503
56 185078
57 194995
58 205260
59 215879
60 226858
61 238203
62 249920
63 262015
64 274494
65 287363
66 300628
67 314295
68 328370
69 342859
70 357768
71 373103
72 388870
73 405075
74 421724
75 438823
76 456378
77 474395
78 492880
79 511839
80 531278
81 551203
82 571620
83 592535
84 613954
85 635883
86 658328
87 681295
88 704790
89 728819
90 753388
91 778503
92 804170
93 830395
94 857184
95 884543
96 912478
97 940995
98 970100
99 999799
100 1030098
101 1061003
102 1092520
103 1124655
104 1157414
105 1190803
106 1224828
107 1259495
108 1294810
109 1330779
110 1367408
111 1404703
112 1442670
113 1481315
114 1520644
115 1560663
116 1601378
117 1642795
118 1684920
119 1727759
120 1771318
121 1815603
122 1860620
123 1906375
124 1952874
125 2000123
126 2048128
127 2096895
128 2146430
129 2196739
130 2247828
131 2299703
132 2352370
133 2405835
134 2460104
135 2515183
136 2571078
137 2627795
138 2685340
139 2743719
140 2802938
141 2863003
142 2923920
143 2985695
144 3048334
145 3111843
146 3176228
147 3241495
148 3307650
149 3374699
150 3442648
151 3511503
152 3581270
153 3651955
154 3723564
155 3796103
156 3869578
157 3943995
158 4019360
159 4095679
160 4172958
161 4251203
162 4330420
163 4410615
164 4491794
165 4573963
166 4657128
167 4741295
168 4826470
169 4912659
170 4999868
171 5088103
172 5177370
173 5267675
174 5359024
175 5451423
176 5544878
177 5639395
178 5734980
179 5831639
180 5929378
181 6028203
182 6128120
183 6229135
184 6331254
185 6434483
186 6538828
187 6644295
188 6750890
189 6858619
190 6967488
191 7077503
192 7188670
193 7300995
194 7414484
195 7529143
196 7644978
197 7761995
198 7880200
199 7999599
200 8120198
201 8242003
202 8365020
203 8489255
204 8614714
205 8741403
206 8869328
207 8998495
208 9128910
209 9260579
210 9393508
211 9527703
212 9663170
213 9799915
214 9937944
215 10077263
216 10217878
217 10359795
218 10503020
219 10647559
220 10793418
221 10940603
222 11089120
223 11238975
224 11390174
225 11542723
226 11696628
227 11851895
228 12008530
229 12166539
230 12325928
231 12486703
232 12648870
233 12812435
234 12977404
235 13143783
236 13311578
237 13480795
238 13651440
239 13823519
240 13997038
241 14172003
242 14348420
243 14526295
244 14705634
245 14886443
246 15068728
247 15252495
248 15437750
249 15624499
250 15812748
251 16002503
252 16193770
253 16386555
254 16580864
255 16776703
256 16974078
257 17172995
258 17373460
259 17575479
260 17779058
261 17984203
262 18190920
263 18399215
264 18609094
265 18820563
266 19033628
267 19248295
268 19464570
269 19682459
270 19901968
271 20123103
272 20345870
273 20570275
274 20796324
275 21024023
276 21253378
277 21484395
278 21717080
279 21951439
280 22187478
281 22425203
282 22664620
283 22905735
284 23148554
285 23393083
286 23639328
287 23887295
288 24136990
289 24388419
290 24641588
291 24896503
292 25153170
293 25411595
294 25671784
295 25933743
296 26197478
297 26462995
298 26730300
299 26999399
300 27270298
301 27543003
302 27817520
303 28093855
304 28372014
305 28652003
306 28933828
307 29217495
308 29503010
309 29790379
310 30079608
311 30370703
312 30663670
313 30958515
314 31255244
315 31553863
316 31854378
317 32156795
318 32461120
319 32767359
320 33075518
321 33385603
322 33697620
323 34011575
324 34327474
325 34645323
326 34965128
327 35286895
328 35610630
329 35936339
330 36264028
331 36593703
332 36925370
333 37259035
334 37594704
335 37932383
336 38272078
337 38613795
338 38957540
339 39303319
340 39651138
341 40001003
342 40352920
343 40706895
344 41062934
345 41421043
346 41781228
347 42143495
348 42507850
349 42874299
350 43242848
351 43613503
352 43986270
353 44361155
354 44738164
355 45117303
356 45498578
357 45881995
358 46267560
359 46655279
360 47045158
361 47437203
362 47831420
363 48227815
364 48626394
365 49027163
366 49430128
367 49835295
368 50242670
369 50652259
370 51064068
371 51478103
372 51894370
373 52312875
374 52733624
375 53156623
376 53581878
377 54009395
378 54439180
379 54871239
380 55305578
381 55742203
382 56181120
383 56622335
384 57065854
385 57511683
386 57959828
387 58410295
388 58863090
389 59318219
390 59775688
391 60235503
392 60697670
393 61162195
394 61629084
395 62098343
396 62569978
397 63043995
398 63520400
399 63999199
400 64480398
401 64964003
402 65450020
403 65938455
404 66429314
405 66922603
406 67418328
407 67916495
408 68417110
409 68920179
410 69425708
411 69933703
412 70444170
413 70957115
414 71472544
415 71990463
416 72510878
417 73033795
418 73559220
419 74087159
420 74617618
421 75150603
422 75686120
423 76224175
424 76764774
425 77307923
426 77853628
427 78401895
428 78952730
429 79506139
430 80062128
431 80620703
432 81181870
433 81745635
434 82312004
435 82880983
436 83452578
437 84026795
438 84603640
439 85183119
440 85765238
441 86350003
442 86937420
443 87527495
444 88120234
445 88715643
446 89313728
447 89914495
448 90517950
449 91124099
450 91732948
451 92344503
452 92958770
453 93575755
454 94195464
455 94817903
456 95443078
457 96070995
458 96701660
459 97335079
460 97971258
461 98610203
462 99251920
463 99896415
464 100543694
465 101193763
466 101846628
467 102502295
468 103160770
469 103822059
470 104486168
471 105153103
472 105822870
473 106495475
474 107170924
475 107849223
476 108530378
477 109214395
478 109901280
479 110591039
480 111283678
481 111979203
482 112677620
483 113378935
484 114083154
485 114790283
486 115500328
487 116213295
488 116929190
489 117648019
490 118369788
491 119094503
492 119822170
493 120552795
494 121286384
495 122022943
496 122762478
497 123504995
498 124250500
499 124998999
500 125750498
501 126505003
502 127262520
503 128023055
504 128786614
505 129553203
506 130322828
507 131095495
508 131871210
509 132649979
510 133431808
511 134216703
512 135004670
513 135795715
514 136589844
515 137387063
516 138187378
517 138990795
518 139797320
519 140606959
520 141419718
521 142235603
522 143054620
523 143876775
524 144702074
525 145530523
526 146362128
527 147196895
528 148034830
529 148875939
530 149720228
531 150567703
532 151418370
533 152272235
534 153129304
535 153989583
536 154853078
537 155719795
538 156589740
539 157462919
540 158339338
541 159219003
542 160101920
543 160988095
544 161877534
545 162770243
546 163666228
547 164565495
548 165468050
549 166373899
550 167283048
551 168195503
552 169111270
553 170030355
554 170952764
555 171878503
556 172807578
557 173739995
558 174675760
559 175614879
560 176557358
561 177503203
562 178452420
563 179405015
564 180360994
565 181320363
566 182283128
567 183249295
568 184218870
569 185191859
570 186168268
571 187148103
572 188131370
573 189118075
574 190108224
575 191101823
576 192098878
577 193099395
578 194103380
579 195110839
580 196121778
581 197136203
582 198154120
583 199175535
584 200200454
585 201228883
586 202260828
587 203296295
588 204335290
589 205377819
590 206423888
591 207473503
592 208526670
593 209583395
594 210643684
595 211707543
596 212774978
597 213845995
598 214920600
599 215998799
600 217080598
601 218166003
602 219255020
603 220347655
604 221443914
605 222543803
606 223647328
607 224754495
608 225865310
609 226979779
610 228097908
611 229219703
612 230345170
613 231474315
614 232607144
615 233743663
616 234883878
617 236027795
618 237175420
619 238326759
620 239481818
621 240640603
622 241803120
623 242969375
624 244139374
625 245313123
626 246490628
627 247671895
628 248856930
629 250045739
630 251238328
631 252434703
632 253634870
633 254838835
634 256046604
635 257258183
636 258473578
637 259692795
638 260915840
639 262142719
640 263373438
641 264608003
642 265846420
643 267088695
644 268334834
645 269584843
646 270838728
647 272096495
648 273358150
649 274623699
650 275893148
651 277166503
652 278443770
653 279724955
654 281010064
655 282299103
656 283592078
657 284888995
658 286189860
659 287494679
660 288803458
661 290116203
662 291432920
663 292753615
664 294078294
665 295406963
666 296739628
667 298076295
668 299416970
669 300761659
670 302110368
671 303463103
672 304819870
673 306180675
674 307545524
675 308914423
676 310287378
677 311664395
678 313045480
679 314430639
680 315819878
681 317213203
682 318610620
683 320012135
684 321417754
685 322827483
686 324241328
687 325659295
688 327081390
689 328507619
690 329937988
691 331372503
692 332811170
693 334253995
694 335700984
695 337152143
696 338607478
697 340066995
698 341530700
699 342998599
700 344470698
701 345947003
702 347427520
703 348912255
704 350401214
705 351894403
706 353391828
707 354893495
708 356399410
709 357909579
710 359424008
711 360942703
712 362465670
713 363992915
714 365524444
715 367060263
716 368600378
717 370144795
718 371693520
719 373246559
720 374803918
721 376365603
722 377931620
723 379501975
724 381076674
725 382655723
726 384239128
727 385826895
728 387419030
729 389015539
730 390616428
731 392221703
732 393831370
733 395445435
734 397063904
735 398686783
736 400314078
737 401945795
738 403581940
739 405222519
740 406867538
741 408517003
742 410170920
743 411829295
744 413492134
745 415159443
746 416831228
747 418507495
748 420188250
749 421873499
750 423563248
751 425257503
752 426956270
753 428659555
754 430367364
755 432079703
756 433796578
757 435517995
758 437243960
759 438974479
760 440709558
761 442449203
762 444193420
763 445942215
764 447695594
765 449453563
766 451216128
767 452983295
768 454755070
769 456531459
770 458312468
771 460098103
772 461888370
773 463683275
774 465482824
775 467287023
776 469095878
777 470909395
778 472727580
779 474550439
780 476377978
781 478210203
782 480047120
783 481888735
784 483735054
785 485586083
786 487441828
787 489302295
788 491167490
789 493037419
790 494912088
791 496791503
792 498675670
793 500564595
794 502458284
795 504356743
796 506259978
797 508167995
798 510080800
799 511998399
800 513920798
801 515848003
802 517780020
803 519716855
804 521658514
805 523605003
806 525556328
807 527512495
808 529473510
809 531439379
810 533410108
811 535385703
812 537366170
813 539351515
814 541341744
815 543336863
816 545336878
817 547341795
818 549351620
819 551366359
820 553386018
821 555410603
822 557440120
823 559474575
824 561513974
825 563558323
826 565607628
827 567661895
828 569721130
829 571785339
830 573854528
831 575928703
832 578007870
833 580092035
834 582181204
835 584275383
836 586374578
837 588478795
838 590588040
839 592702319
840 594821638
841 596946003
842 599075420
843 601209895
844 603349434
845 605494043
846 607643728
847 609798495
848 611958350
849 614123299
850 616293348
851 618468503
852 620648770
853 622834155
854 625024664
855 627220303
856 629421078
857 631626995
858 633838060
859 636054279
860 638275658
861 640502203
862 642733920
863 644970815
864 647212894
865 649460163
866 651712628
867 653970295
868 656233170
869 658501259
870 660774568
871 663053103
872 665336870
873 667625875
874 669920124
875 672219623
876 674524378
877 676834395
878 679149680
879 681470239
880 683796078
881 686127203
882 688463620
883 690805335
884 693152354
885 695504683
886 697862328
887 700225295
888 702593590
889 704967219
890 707346188
891 709730503
892 712120170
893 714515195
894 716915584
895 719321343
896 721732478
897 724148995
898 726570900
899 728998199
900 731430898
901 733869003
902 736312520
903 738761455
904 741215814
905 743675603
906 746140828
907 748611495
908 751087610
909 753569179
910 756056208
911 758548703
912 761046670
913 763550115
914 766059044
915 768573463
916 771093378
917 773618795
918 776149720
919 778686159
920 781228118
921 783775603
922 786328620
923 788887175
924 791451274
925 794020923
926 796596128
927 799176895
928 801763230
929 804355139
930 806952628
931 809555703
932 812164370
933 814778635
934 817398504
935 820023983
936 822655078
937 825291795
938 827934140
939 830582119
940 833235738
941 835895003
942 838559920
943 841230495
944 843906734
945 846588643
946 849276228
947 851969495
948 854668450
949 857373099
950 860083448
951 862799503
952 865521270
953 868248755
954 870981964
955 873720903
956 876465578
957 879215995
958 881972160
959 884734079
960 887501758
961 890275203
962 893054420
963 895839415
964 898630194
965 901426763
966 904229128
967 907037295
968 909851270
969 912671059
970 915496668
971 918328103
972 921165370
973 924008475
974 926857424
975 929712223
976 932572878
977 935439395
978 938311780
979 941190039
980 944074178
981 946964203
982 949860120
983 952761935
984 955669654
985 958583283
986 961502828
987 964428295
988 967359690
989 970297019
990 973240288
991 976189503
992 979144670
993 982105795
994 985072884
995 988045943
996 991024978
997 994009995
998 997001000
999 999997999
1000 1003000998