0 4
1 10
2 40
3 130
4 340
5 754
6 1480
7 2650
8 4420
9 6970
10 10504
11 15250
12 21460
13 29410
14 39400
15 51754
16 66820
17 84970
18 106600
19 132130
20 162004
21 196690
22 236680
23 282490
24 334660
25 393754
26 460360
27 535090
28 618580
29 711490
30 814504
31 928330
32 1053700
33 1191370
34 1342120
35 1506754
36 1686100
37 1881010
38 2092360
39 2321050
40 2568004
41 2834170
42 3120520
43 3428050
44 3757780
45 4110754
46 4488040
47 4890730
48 5319940
49 5776810
50 6262504
51 6778210
52 7325140
53 7904530
54 8517640
55 9165754
56 9850180
57 10572250
58 11333320
59 12134770
60 12978004
61 13864450
62 14795560
63 15772810
64 16797700
65 17871754
66 18996520
67 20173570
68 21404500
69 22690930
70 24034504
71 25436890
72 26899780
73 28424890
74 30013960
75 31668754
76 33391060
77 35182690
78 37045480
79 38981290
80 40992004
81 43079530
82 45245800
83 47492770
84 49822420
85 52236754
86 54737800
87 57327610
88 60008260
89 62781850
90 65650504
91 68616370
92 71681620
93 74848450
94 78119080
95 81495754
96 84980740
97 88576330
98 92284840
99 96108610
100 100050004
101 104111410
102 108295240
103 112603930
104 117039940
105 121605754
106 126303880
107 131136850
108 136107220
109 141217570
110 146470504
111 151868650
112 157414660
113 163111210
114 168961000
115 174966754
116 181131220
117 187457170
118 193947400
119 200604730
120 207432004
121 214432090
122 221607880
123 228962290
124 236498260
125 244218754
126 252126760
127 260225290
128 268517380
129 277006090
130 285694504
131 294585730
132 303682900
133 312989170
134 322507720
135 332241754
136 342194500
137 352369210
138 362769160
139 373397650
140 384258004
141 395353570
142 406687720
143 418263850
144 430085380
145 442155754
146 454478440
147 467056930
148 479894740
149 492995410
150 506362504
151 519999610
152 533910340
153 548098330
154 562567240
155 577320754
156 592362580
157 607696450
158 623326120
159 639255370
160 655488004
161 672027850
162 688878760
163 706044610
164 723529300
165 741336754
166 759470920
167 777935770
168 796735300
169 815873530
170 835354504
171 855182290
172 875360980
173 895894690
174 916787560
175 938043754
176 959667460
177 981662890
178 1004034280
179 1026785890
180 1049922004
181 1073446930
182 1097365000
183 1121680570
184 1146398020
185 1171521754
186 1197056200
187 1223005810
188 1249375060
189 1276168450
190 1303390504
191 1331045770
192 1359138820
193 1387674250
194 1416656680
195 1446090754
196 1475981140
197 1506332530
198 1537149640
199 1568437210
200 1600200004
201 1632442810
202 1665170440
203 1698387730
204 1732099540
205 1766310754
206 1801026280
207 1836251050
208 1871990020
209 1908248170
210 1945030504
211 1982342050
212 2020187860
213 2058573010
214 2097502600
215 2136981754
216 2177015620
217 2217609370
218 2258768200
219 2300497330
220 2342802004
221 2385687490
222 2429159080
223 2473222090
224 2517881860
225 2563143754
226 2609013160
227 2655495490
228 2702596180
229 2750320690
230 2798674504
231 2847663130
232 2897292100
233 2947566970
234 2998493320
235 3050076754
236 3102322900
237 3155237410
238 3208825960
239 3263094250
240 3318048004
241 3373692970
242 3430034920
243 3487079650
244 3544832980
245 3603300754
246 3662488840
247 3722403130
248 3783049540
249 3844434010
250 3906562504
251 3969441010
252 4033075540
253 4097472130
254 4162636840
255 4228575754
256 4295294980
257 4362800650
258 4431098920
259 4500195970
260 4570098004
261 4640811250
262 4712341960
263 4784696410
264 4857880900
265 4931901754
266 5006765320
267 5082477970
268 5159046100
269 5236476130
270 5314774504
271 5393947690
272 5474002180
273 5554944490
274 5636781160
275 5719518754
276 5803163860
277 5887723090
278 5973203080
279 6059610490
280 6146952004
281 6235234330
282 6324464200
283 6414648370
284 6505793620
285 6597906754
286 6690994600
287 6785064010
288 6880121860
289 6976175050
290 7073230504
291 7171295170
292 7270376020
293 7370480050
294 7471614280
295 7573785754
296 7677001540
297 7781268730
298 7886594440
299 7992985810
300 8100450004
301 8208994210
302 8318625640
303 8429351530
304 8541179140
305 8654115754
306 8768168680
307 8883345250
308 8999652820
309 9117098770
310 9235690504
311 9355435450
312 9476341060
313 9598414810
314 9721664200
315 9846096754
316 9971720020
317 10098541570
318 10226569000
319 10355809930
320 10486272004
321 10617962890
322 10750890280
323 10885061890
324 11020485460
325 11157168754
326 11295119560
327 11434345690
328 11574854980
329 11716655290
330 11859754504
331 12004160530
332 12149881300
333 12296924770
334 12445298920
335 12595011754
336 12746071300
337 12898485610
338 13052262760
339 13207410850
340 13363938004
341 13521852370
342 13681162120
343 13841875450
344 14004000580
345 14167545754
346 14332519240
347 14498929330
348 14666784340
349 14836092610
350 15006862504
351 15179102410
352 15352820740
353 15528025930
354 15704726440
355 15882930754
356 16062647380
357 16243884850
358 16426651720
359 16610956570
360 16796808004
361 16984214650
362 17173185160
363 17363728210
364 17555852500
365 17749566754
366 17944879720
367 18141800170
368 18340336900
369 18540498730
370 18742294504
371 18945733090
372 19150823380
373 19357574290
374 19565994760
375 19776093754
376 19987880260
377 20201363290
378 20416551880
379 20633455090
380 20852082004
381 21072441730
382 21294543400
383 21518396170
384 21744009220
385 21971391754
386 22200553000
387 22431502210
388 22664248660
389 22898801650
390 23135170504
391 23373364570
392 23613393220
393 23855265850
394 24098991880
395 24344580754
396 24592041940
397 24841384930
398 25092619240
399 25345754410
400 25600800004
401 25857765610
402 26116660840
403 26377495330
404 26640278740
405 26905020754
406 27171731080
407 27440419450
408 27711095620
409 27983769370
410 28258450504
411 28535148850
412 28813874260
413 29094636610
414 29377445800
415 29662311754
416 29949244420
417 30238253770
418 30529349800
419 30822542530
420 31117842004
421 31415258290
422 31714801480
423 32016481690
424 32320309060
425 32626293754
426 32934445960
427 33244775890
428 33557293780
429 33872009890
430 34188934504
431 34508077930
432 34829450500
433 35153062570
434 35478924520
435 35807046754
436 36137439700
437 36470113810
438 36805079560
439 37142347450
440 37481928004
441 37823831770
442 38168069320
443 38514651250
444 38863588180
445 39214890754
446 39568569640
447 39924635530
448 40283099140
449 40643971210
450 41007262504
451 41372983810
452 41741145940
453 42111759730
454 42484836040
455 42860385754
456 43238419780
457 43618949050
458 44001984520
459 44387537170
460 44775618004
461 45166238050
462 45559408360
463 45955140010
464 46353444100
465 46754331754
466 47157814120
467 47563902370
468 47972607700
469 48383941330
470 48797914504
471 49214538490
472 49633824580
473 50055784090
474 50480428360
475 50907768754
476 51337816660
477 51770583490
478 52206080680
479 52644319690
480 53085312004
481 53529069130
482 53975602600
483 54424923970
484 54877044820
485 55331976754
486 55789731400
487 56250320410
488 56713755460
489 57180048250
490 57649210504
491 58121253970
492 58596190420
493 59074031650
494 59554789480
495 60038475754
496 60525102340
497 61014681130
498 61507224040
499 62002743010
500 62501250004
501 63002757010
502 63507276040
503 64014819130
504 64525398340
505 65039025754
506 65555713480
507 66075473650
508 66598318420
509 67124259970
510 67653310504
511 68185482250
512 68720787460
513 69259238410
514 69800847400
515 70345626754
516 70893588820
517 71444745970
518 71999110600
519 72556695130
520 73117512004
521 73681573690
522 74248892680
523 74819481490
524 75393352660
525 75970518754
526 76550992360
527 77134786090
528 77721912580
529 78312384490
530 78906214504
531 79503415330
532 80103999700
533 80707980370
534 81315370120
535 81926181754
536 82540428100
537 83158122010
538 83779276360
539 84403904050
540 85032018004
541 85663631170
542 86298756520
543 86937407050
544 87579595780
545 88225335754
546 88874640040
547 89527521730
548 90183993940
549 90844069810
550 91507762504
551 92175085210
552 92846051140
553 93520673530
554 94198965640
555 94880940754
556 95566612180
557 96255993250
558 96949097320
559 97645937770
560 98346528004
561 99050881450
562 99759011560
563 100470931810
564 101186655700
565 101906196754
566 102629568520
567 103356784570
568 104087858500
569 104822803930
570 105561634504
571 106304363890
572 107051005780
573 107801573890
574 108556081960
575 109314543754
576 110076973060
577 110843383690
578 111613789480
579 112388204290
580 113166642004
581 113949116530
582 114735641800
583 115526231770
584 116320900420
585 117119661754
586 117922529800
587 118729518610
588 119540642260
589 120355914850
590 121175350504
591 121998963370
592 122826767620
593 123658777450
594 124495007080
595 125335470754
596 126180182740
597 127029157330
598 127882408840
599 128739951610
600 129601800004
601 130467968410
602 131338471240
603 132213322930
604 133092537940
605 133976130754
606 134864115880
607 135756507850
608 136653321220
609 137554570570
610 138460270504
611 139370435650
612 140285080660
613 141204220210
614 142127869000
615 143056041754
616 143988753220
617 144926018170
618 145867851400
619 146814267730
620 147765282004
621 148720909090
622 149681163880
623 150646061290
624 151615616260
625 152589843754
626 153568758760
627 154552376290
628 155540711380
629 156533779090
630 157531594504
631 158534172730
632 159541528900
633 160553678170
634 161570635720
635 162592416754
636 163619036500
637 164650510210
638 165686853160
639 166728080650
640 167774208004
641 168825250570
642 169881223720
643 170942142850
644 172008023380
645 173078880754
646 174154730440
647 175235587930
648 176321468740
649 177412388410
650 178508362504
651 179609406610
652 180715536340
653 181826767330
654 182943115240
655 184064595754
656 185191224580
657 186323017450
658 187459990120
659 188602158370
660 189749538004
661 190902144850
662 192059994760
663 193223103610
664 194391487300
665 195565161754
666 196744142920
667 197928446770
668 199118089300
669 200313086530
670 201513454504
671 202719209290
672 203930366980
673 205146943690
674 206368955560
675 207596418754
676 208829349460
677 210067763890
678 211311678280
679 212561108890
680 213816072004
681 215076583930
682 216342661000
683 217614319570
684 218891576020
685 220174446754
686 221462948200
687 222757096810
688 224056909060
689 225362401450
690 226673590504
691 227990492770
692 229313124820
693 230641503250
694 231975644680
695 233315565754
696 234661283140
697 236012813530
698 237370173640
699 238733380210
700 240102450004
701 241477399810
702 242858246440
703 244245006730
704 245637697540
705 247036335754
706 248440938280
707 249851522050
708 251268104020
709 252690701170
710 254119330504
711 255554009050
712 256994753860
713 258441582010
714 259894510600
715 261353556754
716 262818737620
717 264290070370
718 265767572200
719 267251260330
720 268741152004
721 270237264490
722 271739615080
723 273248221090
724 274763099860
725 276284268754
726 277811745160
727 279345546490
728 280885690180
729 282432193690
730 283985074504
731 285544350130
732 287110038100
733 288682155970
734 290260721320
735 291845751754
736 293437264900
737 295035278410
738 296639809960
739 298250877250
740 299868498004
741 301492689970
742 303123470920
743 304760858650
744 306404870980
745 308055525754
746 309712840840
747 311376834130
748 313047523540
749 314724927010
750 316409062504
751 318099948010
752 319797601540
753 321502041130
754 323213284840
755 324931350754
756 326656256980
757 328388021650
758 330126662920
759 331872198970
760 333624648004
761 335384028250
762 337150357960
763 338923655410
764 340703938900
765 342491226754
766 344285537320
767 346086888970
768 347895300100
769 349710789130
770 351533374504
771 353363074690
772 355199908180
773 357043893490
774 358895049160
775 360753393754
776 362618945860
777 364491724090
778 366371747080
779 368259033490
780 370153602004
781 372055471330
782 373964660200
783 375881187370
784 377805071620
785 379736331754
786 381674986600
787 383621055010
788 385574555860
789 387535508050
790 389503930504
791 391479842170
792 393463262020
793 395454209050
794 397452702280
795 399458760754
796 401472403540
797 403493649730
798 405522518440
799 407559028810
800 409603200004
801 411655051210
802 413714601640
803 415781870530
804 417856877140
805 419939640754
806 422030180680
807 424128516250
808 426234666820
809 428348651770
810 430470490504
811 432600202450
812 434737807060
813 436883323810
814 439036772200
815 441198171754
816 443367542020
817 445544902570
818 447730273000
819 449923672930
820 452125122004
821 454334639890
822 456552246280
823 458777960890
824 461011803460
825 463253793754
826 465503951560
827 467762296690
828 470028848980
829 472303628290
830 474586654504
831 476877947530
832 479177527300
833 481485413770
834 483801626920
835 486126186754
836 488459113300
837 490800426610
838 493150146760
839 495508293850
840 497874888004
841 500249949370
842 502633498120
843 505025554450
844 507426138580
845 509835270754
846 512252971240
847 514679260330
848 517114158340
849 519557685610
850 522009862504
851 524470709410
852 526940246740
853 529418494930
854 531905474440
855 534401205754
856 536905709380
857 539419005850
858 541941115720
859 544472059570
860 547011858004
861 549560531650
862 552118101160
863 554684587210
864 557260010500
865 559844391754
866 562437751720
867 565040111170
868 567651490900
869 570271911730
870 572901394504
871 575539960090
872 578187629380
873 580844423290
874 583510362760
875 586185468754
876 588869762260
877 591563264290
878 594265995880
879 596977978090
880 599699232004
881 602429778730
882 605169639400
883 607918835170
884 610677387220
885 613445316754
886 616222645000
887 619009393210
888 621805582660
889 624611234650
890 627426370504
891 630251011570
892 633085179220
893 635928894850
894 638782179880
895 641645055754
896 644517543940
897 647399665930
898 650291443240
899 653192897410
900 656104050004
901 659024922610
902 661955536840
903 664895914330
904 667846076740
905 670806045754
906 673775843080
907 676755490450
908 679745009620
909 682744422370
910 685753750504
911 688773015850
912 691802240260
913 694841445610
914 697890653800
915 700949886754
916 704019166420
917 707098514770
918 710187953800
919 713287505530
920 716397192004
921 719517035290
922 722647057480
923 725787280690
924 728937727060
925 732098418754
926 735269377960
927 738450626890
928 741642187780
929 744844082890
930 748056334504
931 751278964930
932 754511996500
933 757755451570
934 761009352520
935 764273721754
936 767548581700
937 770833954810
938 774129863560
939 777436330450
940 780753378004
941 784081028770
942 787419305320
943 790768230250
944 794127826180
945 797498115754
946 800879121640
947 804270866530
948 807673373140
949 811086664210
950 814510762504
951 817945690810
952 821391471940
953 824848128730
954 828315684040
955 831794160754
956 835283581780
957 838783970050
958 842295348520
959 845817740170
960 849351168004
961 852895655050
962 856451224360
963 860017899010
964 863595702100
965 867184656754
966 870784786120
967 874396113370
968 878018661700
969 881652454330
970 885297514504
971 888953865490
972 892621530580
973 896300533090
974 899990896360
975 903692643754
976 907405798660
977 911130384490
978 914866424680
979 918613942690
980 922372962004
981 926143506130
982 929925598600
983 933719262970
984 937524522820
985 941341401754
986 945169923400
987 949010111410
988 952861989460
989 956725581250
990 960600910504
991 964488000970
992 968386876420
993 972297560650
994 976220077480
995 980154450754
996 984100704340
997 988058862130
998 992028948040
999 996010986010
1000 1000005000004