1 1 2 4 3 11 4 25 5 49 6 86 7 139 8 211 9 305 10 424 11 571 12 749 13 961 14 1210 15 1499 16 1831 17 2209 18 2636 19 3115 20 3649 21 4241 22 4894 23 5611 24 6395 25 7249 26 8176 27 9179 28 10261 29 11425 30 12674 31 14011 32 15439 33 16961 34 18580 35 20299 36 22121 37 24049 38 26086 39 28235 40 30499 41 32881 42 35384 43 38011 44 40765 45 43649 46 46666 47 49819 48 53111 49 56545 50 60124 51 63851 52 67729 53 71761 54 75950 55 80299 56 84811 57 89489 58 94336 59 99355 60 104549 61 109921 62 115474 63 121211 64 127135 65 133249 66 139556 67 146059 68 152761 69 159665 70 166774 71 174091 72 181619 73 189361 74 197320 75 205499 76 213901 77 222529 78 231386 79 240475 80 249799 81 259361 82 269164 83 279211 84 289505 85 300049 86 310846 87 321899 88 333211 89 344785 90 356624 91 368731 92 381109 93 393761 94 406690 95 419899 96 433391 97 447169 98 461236 99 475595 100 490249 101 505201 102 520454 103 536011 104 551875 105 568049 106 584536 107 601339 108 618461 109 635905 110 653674 111 671771 112 690199 113 708961 114 728060 115 747499 116 767281 117 787409 118 807886 119 828715 120 849899 121 871441 122 893344 123 915611 124 938245 125 961249 126 984626 127 1008379 128 1032511 129 1057025 130 1081924 131 1107211 132 1132889 133 1158961 134 1185430 135 1212299 136 1239571 137 1267249 138 1295336 139 1323835 140 1352749 141 1382081 142 1411834 143 1442011 144 1472615 145 1503649 146 1535116 147 1567019 148 1599361 149 1632145 150 1665374 151 1699051 152 1733179 153 1767761 154 1802800 155 1838299 156 1874261 157 1910689 158 1947586 159 1984955 160 2022799 161 2061121 162 2099924 163 2139211 164 2178985 165 2219249 166 2260006 167 2301259 168 2343011 169 2385265 170 2428024 171 2471291 172 2515069 173 2559361 174 2604170 175 2649499 176 2695351 177 2741729 178 2788636 179 2836075 180 2884049 181 2932561 182 2981614 183 3031211 184 3081355 185 3132049 186 3183296 187 3235099 188 3287461 189 3340385 190 3393874 191 3447931 192 3502559 193 3557761 194 3613540 195 3669899 196 3726841 197 3784369 198 3842486 199 3901195 200 3960499 201 4020401 202 4080904 203 4142011 204 4203725 205 4266049 206 4328986 207 4392539 208 4456711 209 4521505 210 4586924 211 4652971 212 4719649 213 4786961 214 4854910 215 4923499 216 4992731 217 5062609 218 5133136 219 5204315 220 5276149 221 5348641 222 5421794 223 5495611 224 5570095 225 5645249 226 5721076 227 5797579 228 5874761 229 5952625 230 6031174 231 6110411 232 6190339 233 6270961 234 6352280 235 6434299 236 6517021 237 6600449 238 6684586 239 6769435 240 6854999 241 6941281 242 7028284 243 7116011 244 7204465 245 7293649 246 7383566 247 7474219 248 7565611 249 7657745 250 7750624 251 7844251 252 7938629 253 8033761 254 8129650 255 8226299 256 8323711 257 8421889 258 8520836 259 8620555 260 8721049 261 8822321 262 8924374 263 9027211 264 9130835 265 9235249 266 9340456 267 9446459 268 9553261 269 9660865 270 9769274 271 9878491 272 9988519 273 10099361 274 10211020 275 10323499 276 10436801 277 10550929 278 10665886 279 10781675 280 10898299 281 11015761 282 11134064 283 11253211 284 11373205 285 11494049 286 11615746 287 11738299 288 11861711 289 11985985 290 12111124 291 12237131 292 12364009 293 12491761 294 12620390 295 12749899 296 12880291 297 13011569 298 13143736 299 13276795 300 13410749 301 13545601 302 13681354 303 13818011 304 13955575 305 14094049 306 14233436 307 14373739 308 14514961 309 14657105 310 14800174 311 14944171 312 15089099 313 15234961 314 15381760 315 15529499 316 15678181 317 15827809 318 15978386 319 16129915 320 16282399 321 16435841 322 16590244 323 16745611 324 16901945 325 17059249 326 17217526 327 17376779 328 17537011 329 17698225 330 17860424 331 18023611 332 18187789 333 18352961 334 18519130 335 18686299 336 18854471 337 19023649 338 19193836 339 19365035 340 19537249 341 19710481 342 19884734 343 20060011 344 20236315 345 20413649 346 20592016 347 20771419 348 20951861 349 21133345 350 21315874 351 21499451 352 21684079 353 21869761 354 22056500 355 22244299 356 22433161 357 22623089 358 22814086 359 23006155 360 23199299 361 23393521 362 23588824 363 23785211 364 23982685 365 24181249 366 24380906 367 24581659 368 24783511 369 24986465 370 25190524 371 25395691 372 25601969 373 25809361 374 26017870 375 26227499 376 26438251 377 26650129 378 26863136 379 27077275 380 27292549 381 27508961 382 27726514 383 27945211 384 28165055 385 28386049 386 28608196 387 28831499 388 29055961 389 29281585 390 29508374 391 29736331 392 29965459 393 30195761 394 30427240 395 30659899 396 30893741 397 31128769 398 31364986 399 31602395 400 31840999 401 32080801 402 32321804 403 32564011 404 32807425 405 33052049 406 33297886 407 33544939 408 33793211 409 34042705 410 34293424 411 34545371 412 34798549 413 35052961 414 35308610 415 35565499 416 35823631 417 36083009 418 36343636 419 36605515 420 36868649 421 37133041 422 37398694 423 37665611 424 37933795 425 38203249 426 38473976 427 38745979 428 39019261 429 39293825 430 39569674 431 39846811 432 40125239 433 40404961 434 40685980 435 40968299 436 41251921 437 41536849 438 41823086 439 42110635 440 42399499 441 42689681 442 42981184 443 43274011 444 43568165 445 43863649 446 44160466 447 44458619 448 44758111 449 45058945 450 45361124 451 45664651 452 45969529 453 46275761 454 46583350 455 46892299 456 47202611 457 47514289 458 47827336 459 48141755 460 48457549 461 48774721 462 49093274 463 49413211 464 49734535 465 50057249 466 50381356 467 50706859 468 51033761 469 51362065 470 51691774 471 52022891 472 52355419 473 52689361 474 53024720 475 53361499 476 53699701 477 54039329 478 54380386 479 54722875 480 55066799 481 55412161 482 55758964 483 56107211 484 56456905 485 56808049 486 57160646 487 57514699 488 57870211 489 58227185 490 58585624 491 58945531 492 59306909 493 59669761 494 60034090 495 60399899 496 60767191 497 61135969 498 61506236 499 61877995 500 62251249 501 62626001 502 63002254 503 63380011 504 63759275 505 64140049 506 64522336 507 64906139 508 65291461 509 65678305 510 66066674 511 66456571 512 66847999 513 67240961 514 67635460 515 68031499 516 68429081 517 68828209 518 69228886 519 69631115 520 70034899 521 70440241 522 70847144 523 71255611 524 71665645 525 72077249 526 72490426 527 72905179 528 73321511 529 73739425 530 74158924 531 74580011 532 75002689 533 75426961 534 75852830 535 76280299 536 76709371 537 77140049 538 77572336 539 78006235 540 78441749 541 78878881 542 79317634 543 79758011 544 80200015 545 80643649 546 81088916 547 81535819 548 81984361 549 82434545 550 82886374 551 83339851 552 83794979 553 84251761 554 84710200 555 85170299 556 85632061 557 86095489 558 86560586 559 87027355 560 87495799 561 87965921 562 88437724 563 88911211 564 89386385 565 89863249 566 90341806 567 90822059 568 91304011 569 91787665 570 92273024 571 92760091 572 93248869 573 93739361 574 94231570 575 94725499 576 95221151 577 95718529 578 96217636 579 96718475 580 97221049 581 97725361 582 98231414 583 98739211 584 99248755 585 99760049 586 100273096 587 100787899 588 101304461 589 101822785 590 102342874 591 102864731 592 103388359 593 103913761 594 104440940 595 104969899 596 105500641 597 106033169 598 106567486 599 107103595 600 107641499 601 108181201 602 108722704 603 109266011 604 109811125 605 110358049 606 110906786 607 111457339 608 112009711 609 112563905 610 113119924 611 113677771 612 114237449 613 114798961 614 115362310 615 115927499 616 116494531 617 117063409 618 117634136 619 118206715 620 118781149 621 119357441 622 119935594 623 120515611 624 121097495 625 121681249 626 122266876 627 122854379 628 123443761 629 124035025 630 124628174 631 125223211 632 125820139 633 126418961 634 127019680 635 127622299 636 128226821 637 128833249 638 129441586 639 130051835 640 130663999 641 131278081 642 131894084 643 132512011 644 133131865 645 133753649 646 134377366 647 135003019 648 135630611 649 136260145 650 136891624 651 137525051 652 138160429 653 138797761 654 139437050 655 140078299 656 140721511 657 141366689 658 142013836 659 142662955 660 143314049 661 143967121 662 144622174 663 145279211 664 145938235 665 146599249 666 147262256 667 147927259 668 148594261 669 149263265 670 149934274 671 150607291 672 151282319 673 151959361 674 152638420 675 153319499 676 154002601 677 154687729 678 155374886 679 156064075 680 156755299 681 157448561 682 158143864 683 158841211 684 159540605 685 160242049 686 160945546 687 161651099 688 162358711 689 163068385 690 163780124 691 164493931 692 165209809 693 165927761 694 166647790 695 167369899 696 168094091 697 168820369 698 169548736 699 170279195 700 171011749 701 171746401 702 172483154 703 173222011 704 173962975 705 174706049 706 175451236 707 176198539 708 176947961 709 177699505 710 178453174 711 179208971 712 179966899 713 180726961 714 181489160 715 182253499 716 183019981 717 183788609 718 184559386 719 185332315 720 186107399 721 186884641 722 187664044 723 188445611 724 189229345 725 190015249 726 190803326 727 191593579 728 192386011 729 193180625 730 193977424 731 194776411 732 195577589 733 196380961 734 197186530 735 197994299 736 198804271 737 199616449 738 200430836 739 201247435 740 202066249 741 202887281 742 203710534 743 204536011 744 205363715 745 206193649 746 207025816 747 207860219 748 208696861 749 209535745 750 210376874 751 211220251 752 212065879 753 212913761 754 213763900 755 214616299 756 215470961 757 216327889 758 217187086 759 218048555 760 218912299 761 219778321 762 220646624 763 221517211 764 222390085 765 223265249 766 224142706 767 225022459 768 225904511 769 226788865 770 227675524 771 228564491 772 229455769 773 230349361 774 231245270 775 232143499 776 233044051 777 233946929 778 234852136 779 235759675 780 236669549 781 237581761 782 238496314 783 239413211 784 240332455 785 241254049 786 242177996 787 243104299 788 244032961 789 244963985 790 245897374 791 246833131 792 247771259 793 248711761 794 249654640 795 250599899 796 251547541 797 252497569 798 253449986 799 254404795 800 255361999 801 256321601 802 257283604 803 258248011 804 259214825 805 260184049 806 261155686 807 262129739 808 263106211 809 264085105 810 265066424 811 266050171 812 267036349 813 268024961 814 269016010 815 270009499 816 271005431 817 272003809 818 273004636 819 274007915 820 275013649 821 276021841 822 277032494 823 278045611 824 279061195 825 280079249 826 281099776 827 282122779 828 283148261 829 284176225 830 285206674 831 286239611 832 287275039 833 288312961 834 289353380 835 290396299 836 291441721 837 292489649 838 293540086 839 294593035 840 295648499 841 296706481 842 297766984 843 298830011 844 299895565 845 300963649 846 302034266 847 303107419 848 304183111 849 305261345 850 306342124 851 307425451 852 308511329 853 309599761 854 310690750 855 311784299 856 312880411 857 313979089 858 315080336 859 316184155 860 317290549 861 318399521 862 319511074 863 320625211 864 321741935 865 322861249 866 323983156 867 325107659 868 326234761 869 327364465 870 328496774 871 329631691 872 330769219 873 331909361 874 333052120 875 334197499 876 335345501 877 336496129 878 337649386 879 338805275 880 339963799 881 341124961 882 342288764 883 343455211 884 344624305 885 345796049 886 346970446 887 348147499 888 349327211 889 350509585 890 351694624 891 352882331 892 354072709 893 355265761 894 356461490 895 357659899 896 358860991 897 360064769 898 361271236 899 362480395 900 363692249 901 364906801 902 366124054 903 367344011 904 368566675 905 369792049 906 371020136 907 372250939 908 373484461 909 374720705 910 375959674 911 377201371 912 378445799 913 379692961 914 380942860 915 382195499 916 383450881 917 384709009 918 385969886 919 387233515 920 388499899 921 389769041 922 391040944 923 392315611 924 393593045 925 394873249 926 396156226 927 397441979 928 398730511 929 400021825 930 401315924 931 402612811 932 403912489 933 405214961 934 406520230 935 407828299 936 409139171 937 410452849 938 411769336 939 413088635 940 414410749 941 415735681 942 417063434 943 418394011 944 419727415 945 421063649 946 422402716 947 423744619 948 425089361 949 426436945 950 427787374 951 429140651 952 430496779 953 431855761 954 433217600 955 434582299 956 435949861 957 437320289 958 438693586 959 440069755 960 441448799 961 442830721 962 444215524 963 445603211 964 446993785 965 448387249 966 449783606 967 451182859 968 452585011 969 453990065 970 455398024 971 456808891 972 458222669 973 459639361 974 461058970 975 462481499 976 463906951 977 465335329 978 466766636 979 468200875 980 469638049 981 471078161 982 472521214 983 473967211 984 475416155 985 476868049 986 478322896 987 479780699 988 481241461 989 482705185 990 484171874 991 485641531 992 487114159 993 488589761 994 490068340 995 491549899 996 493034441 997 494521969 998 496012486 999 497505995 1000 499002499