1 1
2 8
3 14
4 36
5 63
6 112
7 172
8 260
9 365
10 504
11 666
12 868
13 1099
14 1376
15 1688
16 2052
17 2457
18 2920
19 3430
20 4004
21 4631
22 5328
23 6084
24 6916
25 7813
26 8792
27 9842
28 10980
29 12195
30 13504
31 14896
32 16388
33 17969
34 19656
35 21438
36 23332
37 25327
38 27440
39 29660
40 32004
41 34461
42 37048
43 39754
44 42596
45 45563
46 48672
47 51912
48 55300
49 58825
50 62504
51 66326
52 70308
53 74439
54 78736
55 83188
56 87812
57 92597
58 97560
59 102690
60 108004
61 113491
62 119168
63 125024
64 131076
65 137313
66 143752
67 150382
68 157220
69 164255
70 171504
71 178956
72 186628
73 194509
74 202616
75 210938
76 219492
77 228267
78 237280
79 246520
80 256004
81 265721
82 275688
83 285894
84 296356
85 307063
86 318032
87 329252
88 340740
89 352485
90 364504
91 376786
92 389348
93 402179
94 415296
95 428688
96 442372
97 456337
98 470600
99 485150
100 500004
101 515151
102 530608
103 546364
104 562436
105 578813
106 595512
107 612522
108 629860
109 647515
110 665504
111 683816
112 702468
113 721449
114 740776
115 760438
116 780452
117 800807
118 821520
119 842580
120 864004
121 885781
122 907928
123 930434
124 953316
125 976563
126 1000192
127 1024192
128 1048580
129 1073345
130 1098504
131 1124046
132 1149988
133 1176319
134 1203056
135 1230188
136 1257732
137 1285677
138 1314040
139 1342810
140 1372004
141 1401611
142 1431648
143 1462104
144 1492996
145 1524313
146 1556072
147 1588262
148 1620900
149 1653975
150 1687504
151 1721476
152 1755908
153 1790789
154 1826136
155 1861938
156 1898212
157 1934947
158 1972160
159 2009840
160 2048004
161 2086641
162 2125768
163 2165374
164 2205476
165 2246063
166 2287152
167 2328732
168 2370820
169 2413405
170 2456504
171 2500106
172 2544228
173 2588859
174 2634016
175 2679688
176 2725892
177 2772617
178 2819880
179 2867670
180 2916004
181 2964871
182 3014288
183 3064244
184 3114756
185 3165813
186 3217432
187 3269602
188 3322340
189 3375635
190 3429504
191 3483936
192 3538948
193 3594529
194 3650696
195 3707438
196 3764772
197 3822687
198 3881200
199 3940300
200 4000004
201 4060301
202 4121208
203 4182714
204 4244836
205 4307563
206 4370912
207 4434872
208 4499460
209 4564665
210 4630504
211 4696966
212 4764068
213 4831799
214 4900176
215 4969188
216 5038852
217 5109157
218 5180120
219 5251730
220 5324004
221 5396931
222 5470528
223 5544784
224 5619716
225 5695313
226 5771592
227 5848542
228 5926180
229 6004495
230 6083504
231 6163196
232 6243588
233 6324669
234 6406456
235 6488938
236 6572132
237 6656027
238 6740640
239 6825960
240 6912004
241 6998761
242 7086248
243 7174454
244 7263396
245 7353063
246 7443472
247 7534612
248 7626500
249 7719125
250 7812504
251 7906626
252 8001508
253 8097139
254 8193536
255 8290688
256 8388612
257 8487297
258 8586760
259 8686990
260 8788004
261 8889791
262 8992368
263 9095724
264 9199876
265 9304813
266 9410552
267 9517082
268 9624420
269 9732555
270 9841504
271 9951256
272 10061828
273 10173209
274 10285416
275 10398438
276 10512292
277 10626967
278 10742480
279 10858820
280 10976004
281 11094021
282 11212888
283 11332594
284 11453156
285 11574563
286 11696832
287 11819952
288 11943940
289 12068785
290 12194504
291 12321086
292 12448548
293 12576879
294 12706096
295 12836188
296 12967172
297 13099037
298 13231800
299 13365450
300 13500004
301 13635451
302 13771808
303 13909064
304 14047236
305 14186313
306 14326312
307 14467222
308 14609060
309 14751815
310 14895504
311 15040116
312 15185668
313 15332149
314 15479576
315 15627938
316 15777252
317 15927507
318 16078720
319 16230880
320 16384004
321 16538081
322 16693128
323 16849134
324 17006116
325 17164063
326 17322992
327 17482892
328 17643780
329 17805645
330 17968504
331 18132346
332 18297188
333 18463019
334 18629856
335 18797688
336 18966532
337 19136377
338 19307240
339 19479110
340 19652004
341 19825911
342 20000848
343 20176804
344 20353796
345 20531813
346 20710872
347 20890962
348 21072100
349 21254275
350 21437504
351 21621776
352 21807108
353 21993489
354 22180936
355 22369438
356 22559012
357 22749647
358 22941360
359 23134140
360 23328004
361 23522941
362 23718968
363 23916074
364 24114276
365 24313563
366 24513952
367 24715432
368 24918020
369 25121705
370 25326504
371 25532406
372 25739428
373 25947559
374 26156816
375 26367188
376 26578692
377 26791317
378 27005080
379 27219970
380 27436004
381 27653171
382 27871488
383 28090944
384 28311556
385 28533313
386 28756232
387 28980302
388 29205540
389 29431935
390 29659504
391 29888236
392 30118148
393 30349229
394 30581496
395 30814938
396 31049572
397 31285387
398 31522400
399 31760600
400 32000004
401 32240601
402 32482408
403 32725414
404 32969636
405 33215063
406 33461712
407 33709572
408 33958660
409 34208965
410 34460504
411 34713266
412 34967268
413 35222499
414 35478976
415 35736688
416 35995652
417 36255857
418 36517320
419 36780030
420 37044004
421 37309231
422 37575728
423 37843484
424 38112516
425 38382813
426 38654392
427 38927242
428 39201380
429 39476795
430 39753504
431 40031496
432 40310788
433 40591369
434 40873256
435 41156438
436 41440932
437 41726727
438 42013840
439 42302260
440 42592004
441 42883061
442 43175448
443 43469154
444 43764196
445 44060563
446 44358272
447 44657312
448 44957700
449 45259425
450 45562504
451 45866926
452 46172708
453 46479839
454 46788336
455 47098188
456 47409412
457 47721997
458 48035960
459 48351290
460 48668004
461 48986091
462 49305568
463 49626424
464 49948676
465 50272313
466 50597352
467 50923782
468 51251620
469 51580855
470 51911504
471 52243556
472 52577028
473 52911909
474 53248216
475 53585938
476 53925092
477 54265667
478 54607680
479 54951120
480 55296004
481 55642321
482 55990088
483 56339294
484 56689956
485 57042063
486 57395632
487 57750652
488 58107140
489 58465085
490 58824504
491 59185386
492 59547748
493 59911579
494 60276896
495 60643688
496 61011972
497 61381737
498 61753000
499 62125750
500 62500004
501 62875751
502 63253008
503 63631764
504 64012036
505 64393813
506 64777112
507 65161922
508 65548260
509 65936115
510 66325504
511 66716416
512 67108868
513 67502849
514 67898376
515 68295438
516 68694052
517 69094207
518 69495920
519 69899180
520 70304004
521 70710381
522 71118328
523 71527834
524 71938916
525 72351563
526 72765792
527 73181592
528 73598980
529 74017945
530 74438504
531 74860646
532 75284388
533 75709719
534 76136656
535 76565188
536 76995332
537 77427077
538 77860440
539 78295410
540 78732004
541 79170211
542 79610048
543 80051504
544 80494596
545 80939313
546 81385672
547 81833662
548 82283300
549 82734575
550 83187504
551 83642076
552 84098308
553 84556189
554 85015736
555 85476938
556 85939812
557 86404347
558 86870560
559 87338440
560 87808004
561 88279241
562 88752168
563 89226774
564 89703076
565 90181063
566 90660752
567 91142132
568 91625220
569 92110005
570 92596504
571 93084706
572 93574628
573 94066259
574 94559616
575 95054688
576 95551492
577 96050017
578 96550280
579 97052270
580 97556004
581 98061471
582 98568688
583 99077644
584 99588356
585 100100813
586 100615032
587 101131002
588 101648740
589 102168235
590 102689504
591 103212536
592 103737348
593 104263929
594 104792296
595 105322438
596 105854372
597 106388087
598 106923600
599 107460900
600 108000004
601 108540901
602 109083608
603 109628114
604 110174436
605 110722563
606 111272512
607 111824272
608 112377860
609 112933265
610 113490504
611 114049566
612 114610468
613 115173199
614 115737776
615 116304188
616 116872452
617 117442557
618 118014520
619 118588330
620 119164004
621 119741531
622 120320928
623 120902184
624 121485316
625 122070313
626 122657192
627 123245942
628 123836580
629 124429095
630 125023504
631 125619796
632 126217988
633 126818069
634 127420056
635 128023938
636 128629732
637 129237427
638 129847040
639 130458560
640 131072004
641 131687361
642 132304648
643 132923854
644 133544996
645 134168063
646 134793072
647 135420012
648 136048900
649 136679725
650 137312504
651 137947226
652 138583908
653 139222539
654 139863136
655 140505688
656 141150212
657 141796697
658 142445160
659 143095590
660 143748004
661 144402391
662 145058768
663 145717124
664 146377476
665 147039813
666 147704152
667 148370482
668 149038820
669 149709155
670 150381504
671 151055856
672 151732228
673 152410609
674 153091016
675 153773438
676 154457892
677 155144367
678 155832880
679 156523420
680 157216004
681 157910621
682 158607288
683 159305994
684 160006756
685 160709563
686 161414432
687 162121352
688 162830340
689 163541385
690 164254504
691 164969686
692 165686948
693 166406279
694 167127696
695 167851188
696 168576772
697 169304437
698 170034200
699 170766050
700 171500004
701 172236051
702 172974208
703 173714464
704 174456836
705 175201313
706 175947912
707 176696622
708 177447460
709 178200415
710 178955504
711 179712716
712 180472068
713 181233549
714 181997176
715 182762938
716 183530852
717 184300907
718 185073120
719 185847480
720 186624004
721 187402681
722 188183528
723 188966534
724 189751716
725 190539063
726 191328592
727 192120292
728 192914180
729 193710245
730 194508504
731 195308946
732 196111588
733 196916419
734 197723456
735 198532688
736 199344132
737 200157777
738 200973640
739 201791710
740 202612004
741 203434511
742 204259248
743 205086204
744 205915396
745 206746813
746 207580472
747 208416362
748 209254500
749 210094875
750 210937504
751 211782376
752 212629508
753 213478889
754 214330536
755 215184438
756 216040612
757 216899047
758 217759760
759 218622740
760 219488004
761 220355541
762 221225368
763 222097474
764 222971876
765 223848563
766 224727552
767 225608832
768 226492420
769 227378305
770 228266504
771 229157006
772 230049828
773 230944959
774 231842416
775 232742188
776 233644292
777 234548717
778 235455480
779 236364570
780 237276004
781 238189771
782 239105888
783 240024344
784 240945156
785 241868313
786 242793832
787 243721702
788 244651940
789 245584535
790 246519504
791 247456836
792 248396548
793 249338629
794 250283096
795 251229938
796 252179172
797 253130787
798 254084800
799 255041200
800 256000004
801 256961201
802 257924808
803 258890814
804 259859236
805 260830063
806 261803312
807 262778972
808 263757060
809 264737565
810 265720504
811 266705866
812 267693668
813 268683899
814 269676576
815 270671688
816 271669252
817 272669257
818 273671720
819 274676630
820 275684004
821 276693831
822 277706128
823 278720884
824 279738116
825 280757813
826 281779992
827 282804642
828 283831780
829 284861395
830 285893504
831 286928096
832 287965188
833 289004769
834 290046856
835 291091438
836 292138532
837 293188127
838 294240240
839 295294860
840 296352004
841 297411661
842 298473848
843 299538554
844 300605796
845 301675563
846 302747872
847 303822712
848 304900100
849 305980025
850 307062504
851 308147526
852 309235108
853 310325239
854 311417936
855 312513188
856 313611012
857 314711397
858 315814360
859 316919890
860 318028004
861 319138691
862 320251968
863 321367824
864 322486276
865 323607313
866 324730952
867 325857182
868 326986020
869 328117455
870 329251504
871 330388156
872 331527428
873 332669309
874 333813816
875 334960938
876 336110692
877 337263067
878 338418080
879 339575720
880 340736004
881 341898921
882 343064488
883 344232694
884 345403556
885 346577063
886 347753232
887 348932052
888 350113540
889 351297685
890 352484504
891 353673986
892 354866148
893 356060979
894 357258496
895 358458688
896 359661572
897 360867137
898 362075400
899 363286350
900 364500004
901 365716351
902 366935408
903 368157164
904 369381636
905 370608813
906 371838712
907 373071322
908 374306660
909 375544715
910 376785504
911 378029016
912 379275268
913 380524249
914 381775976
915 383030438
916 384287652
917 385547607
918 386810320
919 388075780
920 389344004
921 390614981
922 391888728
923 393165234
924 394444516
925 395726563
926 397011392
927 398298992
928 399589380
929 400882545
930 402178504
931 403477246
932 404778788
933 406083119
934 407390256
935 408700188
936 410012932
937 411328477
938 412646840
939 413968010
940 415292004
941 416618811
942 417948448
943 419280904
944 420616196
945 421954313
946 423295272
947 424639062
948 425985700
949 427335175
950 428687504
951 430042676
952 431400708
953 432761589
954 434125336
955 435491938
956 436861412
957 438233747
958 439608960
959 440987040
960 442368004
961 443751841
962 445138568
963 446528174
964 447920676
965 449316063
966 450714352
967 452115532
968 453519620
969 454926605
970 456336504
971 457749306
972 459165028
973 460583659
974 462005216
975 463429688
976 464857092
977 466287417
978 467720680
979 469156870
980 470596004
981 472038071
982 473483088
983 474931044
984 476381956
985 477835813
986 479292632
987 480752402
988 482215140
989 483680835
990 485149504
991 486621136
992 488095748
993 489573329
994 491053896
995 492537438
996 494023972
997 495513487
998 497006000
999 498501500
1000 500000004