1 1
2 6
3 21
4 44
5 85
6 138
7 217
8 312
9 441
10 590
11 781
12 996
13 1261
14 1554
15 1905
16 2288
17 2737
18 3222
19 3781
20 4380
21 5061
22 5786
23 6601
24 7464
25 8425
26 9438
27 10557
28 11732
29 13021
30 14370
31 15841
32 17376
33 19041
34 20774
35 22645
36 24588
37 26677
38 28842
39 31161
40 33560
41 36121
42 38766
43 41581
44 44484
45 47565
46 50738
47 54097
48 57552
49 61201
50 64950
51 68901
52 72956
53 77221
54 81594
55 86185
56 90888
57 95817
58 100862
59 106141
60 111540
61 117181
62 122946
63 128961
64 135104
65 141505
66 148038
67 154837
68 161772
69 168981
70 176330
71 183961
72 191736
73 199801
74 208014
75 216525
76 225188
77 234157
78 243282
79 252721
80 262320
81 272241
82 282326
83 292741
84 303324
85 314245
86 325338
87 336777
88 348392
89 360361
90 372510
91 385021
92 397716
93 410781
94 424034
95 437665
96 451488
97 465697
98 480102
99 494901
100 509900
101 525301
102 540906
103 556921
104 573144
105 589785
106 606638
107 623917
108 641412
109 659341
110 677490
111 696081
112 714896
113 734161
114 753654
115 773605
116 793788
117 814437
118 835322
119 856681
120 878280
121 900361
122 922686
123 945501
124 968564
125 992125
126 1015938
127 1040257
128 1064832
129 1089921
130 1115270
131 1141141
132 1167276
133 1193941
134 1220874
135 1248345
136 1276088
137 1304377
138 1332942
139 1362061
140 1391460
141 1421421
142 1451666
143 1482481
144 1513584
145 1545265
146 1577238
147 1609797
148 1642652
149 1676101
150 1709850
151 1744201
152 1778856
153 1814121
154 1849694
155 1885885
156 1922388
157 1959517
158 1996962
159 2035041
160 2073440
161 2112481
162 2151846
163 2191861
164 2232204
165 2273205
166 2314538
167 2356537
168 2398872
169 2441881
170 2485230
171 2529261
172 2573636
173 2618701
174 2664114
175 2710225
176 2756688
177 2803857
178 2851382
179 2899621
180 2948220
181 2997541
182 3047226
183 3097641
184 3148424
185 3199945
186 3251838
187 3304477
188 3357492
189 3411261
190 3465410
191 3520321
192 3575616
193 3631681
194 3688134
195 3745365
196 3802988
197 3861397
198 3920202
199 3979801
200 4039800
201 4100601
202 4161806
203 4223821
204 4286244
205 4349485
206 4413138
207 4477617
208 4542512
209 4608241
210 4674390
211 4741381
212 4808796
213 4877061
214 4945754
215 5015305
216 5085288
217 5156137
218 5227422
219 5299581
220 5372180
221 5445661
222 5519586
223 5594401
224 5669664
225 5745825
226 5822438
227 5899957
228 5977932
229 6056821
230 6136170
231 6216441
232 6297176
233 6378841
234 6460974
235 6544045
236 6627588
237 6712077
238 6797042
239 6882961
240 6969360
241 7056721
242 7144566
243 7233381
244 7322684
245 7412965
246 7503738
247 7595497
248 7687752
249 7781001
250 7874750
251 7969501
252 8064756
253 8161021
254 8257794
255 8355585
256 8453888
257 8553217
258 8653062
259 8753941
260 8855340
261 8957781
262 9060746
263 9164761
264 9269304
265 9374905
266 9481038
267 9588237
268 9695972
269 9804781
270 9914130
271 10024561
272 10135536
273 10247601
274 10360214
275 10473925
276 10588188
277 10703557
278 10819482
279 10936521
280 11054120
281 11172841
282 11292126
283 11412541
284 11533524
285 11655645
286 11778338
287 11902177
288 12026592
289 12152161
290 12278310
291 12405621
292 12533516
293 12662581
294 12792234
295 12923065
296 13054488
297 13187097
298 13320302
299 13454701
300 13589700
301 13725901
302 13862706
303 14000721
304 14139344
305 14279185
306 14419638
307 14561317
308 14703612
309 14847141
310 14991290
311 15136681
312 15282696
313 15429961
314 15577854
315 15727005
316 15876788
317 16027837
318 16179522
319 16332481
320 16486080
321 16640961
322 16796486
323 16953301
324 17110764
325 17269525
326 17428938
327 17589657
328 17751032
329 17913721
330 18077070
331 18241741
332 18407076
333 18573741
334 18741074
335 18909745
336 19079088
337 19249777
338 19421142
339 19593861
340 19767260
341 19942021
342 20117466
343 20294281
344 20471784
345 20650665
346 20830238
347 21011197
348 21192852
349 21375901
350 21559650
351 21744801
352 21930656
353 22117921
354 22305894
355 22495285
356 22685388
357 22876917
358 23069162
359 23262841
360 23457240
361 23653081
362 23849646
363 24047661
364 24246404
365 24446605
366 24647538
367 24849937
368 25053072
369 25257681
370 25463030
371 25669861
372 25877436
373 26086501
374 26296314
375 26507625
376 26719688
377 26933257
378 27147582
379 27363421
380 27580020
381 27798141
382 28017026
383 28237441
384 28458624
385 28681345
386 28904838
387 29129877
388 29355692
389 29583061
390 29811210
391 30040921
392 30271416
393 30503481
394 30736334
395 30970765
396 31205988
397 31442797
398 31680402
399 31919601
400 32159600
401 32401201
402 32643606
403 32887621
404 33132444
405 33378885
406 33626138
407 33875017
408 34124712
409 34376041
410 34628190
411 34881981
412 35136596
413 35392861
414 35649954
415 35908705
416 36168288
417 36429537
418 36691622
419 36955381
420 37219980
421 37486261
422 37753386
423 38022201
424 38291864
425 38563225
426 38835438
427 39109357
428 39384132
429 39660621
430 39937970
431 40217041
432 40496976
433 40778641
434 41061174
435 41345445
436 41630588
437 41917477
438 42205242
439 42494761
440 42785160
441 43077321
442 43370366
443 43665181
444 43960884
445 44258365
446 44556738
447 44856897
448 45157952
449 45460801
450 45764550
451 46070101
452 46376556
453 46684821
454 46993994
455 47304985
456 47616888
457 47930617
458 48245262
459 48561741
460 48879140
461 49198381
462 49518546
463 49840561
464 50163504
465 50488305
466 50814038
467 51141637
468 51470172
469 51800581
470 52131930
471 52465161
472 52799336
473 53135401
474 53472414
475 53811325
476 54151188
477 54492957
478 54835682
479 55180321
480 55525920
481 55873441
482 56221926
483 56572341
484 56923724
485 57277045
486 57631338
487 57987577
488 58344792
489 58703961
490 59064110
491 59426221
492 59789316
493 60154381
494 60520434
495 60888465
496 61257488
497 61628497
498 62000502
499 62374501
500 62749500
501 63126501
502 63504506
503 63884521
504 64265544
505 64648585
506 65032638
507 65418717
508 65805812
509 66194941
510 66585090
511 66977281
512 67370496
513 67765761
514 68162054
515 68560405
516 68959788
517 69361237
518 69763722
519 70168281
520 70573880
521 70981561
522 71390286
523 71801101
524 72212964
525 72626925
526 73041938
527 73459057
528 73877232
529 74297521
530 74718870
531 75142341
532 75566876
533 75993541
534 76421274
535 76851145
536 77282088
537 77715177
538 78149342
539 78585661
540 79023060
541 79462621
542 79903266
543 80346081
544 80789984
545 81236065
546 81683238
547 82132597
548 82583052
549 83035701
550 83489450
551 83945401
552 84402456
553 84861721
554 85322094
555 85784685
556 86248388
557 86714317
558 87181362
559 87650641
560 88121040
561 88593681
562 89067446
563 89543461
564 90020604
565 90500005
566 90980538
567 91463337
568 91947272
569 92433481
570 92920830
571 93410461
572 93901236
573 94394301
574 94888514
575 95385025
576 95882688
577 96382657
578 96883782
579 97387221
580 97891820
581 98398741
582 98906826
583 99417241
584 99928824
585 100442745
586 100957838
587 101475277
588 101993892
589 102514861
590 103037010
591 103561521
592 104087216
593 104615281
594 105144534
595 105676165
596 106208988
597 106744197
598 107280602
599 107819401
600 108359400
601 108901801
602 109445406
603 109991421
604 110538644
605 111088285
606 111639138
607 112192417
608 112746912
609 113303841
610 113861990
611 114422581
612 114984396
613 115548661
614 116114154
615 116682105
616 117251288
617 117822937
618 118395822
619 118971181
620 119547780
621 120126861
622 120707186
623 121290001
624 121874064
625 122460625
626 123048438
627 123638757
628 124230332
629 124824421
630 125419770
631 126017641
632 126616776
633 127218441
634 127821374
635 128426845
636 129033588
637 129642877
638 130253442
639 130866561
640 131480960
641 132097921
642 132716166
643 133336981
644 133959084
645 134583765
646 135209738
647 135838297
648 136468152
649 137100601
650 137734350
651 138370701
652 139008356
653 139648621
654 140290194
655 140934385
656 141579888
657 142228017
658 142877462
659 143529541
660 144182940
661 144838981
662 145496346
663 146156361
664 146817704
665 147481705
666 148147038
667 148815037
668 149484372
669 150156381
670 150829730
671 151505761
672 152183136
673 152863201
674 153544614
675 154228725
676 154914188
677 155602357
678 156291882
679 156984121
680 157677720
681 158374041
682 159071726
683 159772141
684 160473924
685 161178445
686 161884338
687 162592977
688 163302992
689 164015761
690 164729910
691 165446821
692 166165116
693 166886181
694 167608634
695 168333865
696 169060488
697 169789897
698 170520702
699 171254301
700 171989300
701 172727101
702 173466306
703 174208321
704 174951744
705 175697985
706 176445638
707 177196117
708 177948012
709 178702741
710 179458890
711 180217881
712 180978296
713 181741561
714 182506254
715 183273805
716 184042788
717 184814637
718 185587922
719 186364081
720 187141680
721 187922161
722 188704086
723 189488901
724 190275164
725 191064325
726 191854938
727 192648457
728 193443432
729 194241321
730 195040670
731 195842941
732 196646676
733 197453341
734 198261474
735 199072545
736 199885088
737 200700577
738 201517542
739 202337461
740 203158860
741 203983221
742 204809066
743 205637881
744 206468184
745 207301465
746 208136238
747 208973997
748 209813252
749 210655501
750 211499250
751 212346001
752 213194256
753 214045521
754 214898294
755 215754085
756 216611388
757 217471717
758 218333562
759 219198441
760 220064840
761 220934281
762 221805246
763 222679261
764 223554804
765 224433405
766 225313538
767 226196737
768 227081472
769 227969281
770 228858630
771 229751061
772 230645036
773 231542101
774 232440714
775 233342425
776 234245688
777 235152057
778 236059982
779 236971021
780 237883620
781 238799341
782 239716626
783 240637041
784 241559024
785 242484145
786 243410838
787 244340677
788 245272092
789 246206661
790 247142810
791 248082121
792 249023016
793 249967081
794 250912734
795 251861565
796 252811988
797 253765597
798 254720802
799 255679201
800 256639200
801 257602401
802 258567206
803 259535221
804 260504844
805 261477685
806 262452138
807 263429817
808 264409112
809 265391641
810 266375790
811 267363181
812 268352196
813 269344461
814 270338354
815 271335505
816 272334288
817 273336337
818 274340022
819 275346981
820 276355580
821 277367461
822 278380986
823 279397801
824 280416264
825 281438025
826 282461438
827 283488157
828 284516532
829 285548221
830 286581570
831 287618241
832 288656576
833 289698241
834 290741574
835 291788245
836 292836588
837 293888277
838 294941642
839 295998361
840 297056760
841 298118521
842 299181966
843 300248781
844 301317284
845 302389165
846 303462738
847 304539697
848 305618352
849 306700401
850 307784150
851 308871301
852 309960156
853 311052421
854 312146394
855 313243785
856 314342888
857 315445417
858 316549662
859 317657341
860 318766740
861 319879581
862 320994146
863 322112161
864 323231904
865 324355105
866 325480038
867 326608437
868 327738572
869 328872181
870 330007530
871 331146361
872 332286936
873 333431001
874 334576814
875 335726125
876 336877188
877 338031757
878 339188082
879 340347921
880 341509520
881 342674641
882 343841526
883 345011941
884 346184124
885 347359845
886 348537338
887 349718377
888 350901192
889 352087561
890 353275710
891 354467421
892 355660916
893 356857981
894 358056834
895 359259265
896 360463488
897 361671297
898 362880902
899 364094101
900 365309100
901 366527701
902 367748106
903 368972121
904 370197944
905 371427385
906 372658638
907 373893517
908 375130212
909 376370541
910 377612690
911 378858481
912 380106096
913 381357361
914 382610454
915 383867205
916 385125788
917 386388037
918 387652122
919 388919881
920 390189480
921 391462761
922 392737886
923 394016701
924 395297364
925 396581725
926 397867938
927 399157857
928 400449632
929 401745121
930 403042470
931 404343541
932 405646476
933 406953141
934 408261674
935 409573945
936 410888088
937 412205977
938 413525742
939 414849261
940 416174660
941 417503821
942 418834866
943 420169681
944 421506384
945 422846865
946 424189238
947 425535397
948 426883452
949 428235301
950 429589050
951 430946601
952 432306056
953 433669321
954 435034494
955 436403485
956 437774388
957 439149117
958 440525762
959 441906241
960 443288640
961 444674881
962 446063046
963 447455061
964 448849004
965 450246805
966 451646538
967 453050137
968 454455672
969 455865081
970 457276430
971 458691661
972 460108836
973 461529901
974 462952914
975 464379825
976 465808688
977 467241457
978 468676182
979 470114821
980 471555420
981 472999941
982 474446426
983 475896841
984 477349224
985 478805545
986 480263838
987 481726077
988 483190292
989 484658461
990 486128610
991 487602721
992 489078816
993 490558881
994 492040934
995 493526965
996 495014988
997 496506997
998 498001002
999 499499001
1000 500999000