0 1 1 1 2 7 3 25 4 61 5 121 6 211 7 337 8 505 9 721 10 991 11 1321 12 1717 13 2185 14 2731 15 3361 16 4081 17 4897 18 5815 19 6841 20 7981 21 9241 22 10627 23 12145 24 13801 25 15601 26 17551 27 19657 28 21925 29 24361 30 26971 31 29761 32 32737 33 35905 34 39271 35 42841 36 46621 37 50617 38 54835 39 59281 40 63961 41 68881 42 74047 43 79465 44 85141 45 91081 46 97291 47 103777 48 110545 49 117601 50 124951 51 132601 52 140557 53 148825 54 157411 55 166321 56 175561 57 185137 58 195055 59 205321 60 215941 61 226921 62 238267 63 249985 64 262081 65 274561 66 287431 67 300697 68 314365 69 328441 70 342931 71 357841 72 373177 73 388945 74 405151 75 421801 76 438901 77 456457 78 474475 79 492961 80 511921 81 531361 82 551287 83 571705 84 592621 85 614041 86 635971 87 658417 88 681385 89 704881 90 728911 91 753481 92 778597 93 804265 94 830491 95 857281 96 884641 97 912577 98 941095 99 970201 100 999901 101 1030201 102 1061107 103 1092625 104 1124761 105 1157521 106 1190911 107 1224937 108 1259605 109 1294921 110 1330891 111 1367521 112 1404817 113 1442785 114 1481431 115 1520761 116 1560781 117 1601497 118 1642915 119 1685041 120 1727881 121 1771441 122 1815727 123 1860745 124 1906501 125 1953001 126 2000251 127 2048257 128 2097025 129 2146561 130 2196871 131 2247961 132 2299837 133 2352505 134 2405971 135 2460241 136 2515321 137 2571217 138 2627935 139 2685481 140 2743861 141 2803081 142 2863147 143 2924065 144 2985841 145 3048481 146 3111991 147 3176377 148 3241645 149 3307801 150 3374851 151 3442801 152 3511657 153 3581425 154 3652111 155 3723721 156 3796261 157 3869737 158 3944155 159 4019521 160 4095841 161 4173121 162 4251367 163 4330585 164 4410781 165 4491961 166 4574131 167 4657297 168 4741465 169 4826641 170 4912831 171 5000041 172 5088277 173 5177545 174 5267851 175 5359201 176 5451601 177 5545057 178 5639575 179 5735161 180 5831821 181 5929561 182 6028387 183 6128305 184 6229321 185 6331441 186 6434671 187 6539017 188 6644485 189 6751081 190 6858811 191 6967681 192 7077697 193 7188865 194 7301191 195 7414681 196 7529341 197 7645177 198 7762195 199 7880401 200 7999801 201 8120401 202 8242207 203 8365225 204 8489461 205 8614921 206 8741611 207 8869537 208 8998705 209 9129121 210 9260791 211 9393721 212 9527917 213 9663385 214 9800131 215 9938161 216 10077481 217 10218097 218 10360015 219 10503241 220 10647781 221 10793641 222 10940827 223 11089345 224 11239201 225 11390401 226 11542951 227 11696857 228 11852125 229 12008761 230 12166771 231 12326161 232 12486937 233 12649105 234 12812671 235 12977641 236 13144021 237 13311817 238 13481035 239 13651681 240 13823761 241 13997281 242 14172247 243 14348665 244 14526541 245 14705881 246 14886691 247 15068977 248 15252745 249 15438001 250 15624751 251 15813001 252 16002757 253 16194025 254 16386811 255 16581121 256 16776961 257 16974337 258 17173255 259 17373721 260 17575741 261 17779321 262 17984467 263 18191185 264 18399481 265 18609361 266 18820831 267 19033897 268 19248565 269 19464841 270 19682731 271 19902241 272 20123377 273 20346145 274 20570551 275 20796601 276 21024301 277 21253657 278 21484675 279 21717361 280 21951721 281 22187761 282 22425487 283 22664905 284 22906021 285 23148841 286 23393371 287 23639617 288 23887585 289 24137281 290 24388711 291 24641881 292 24896797 293 25153465 294 25411891 295 25672081 296 25934041 297 26197777 298 26463295 299 26730601 300 26999701 301 27270601 302 27543307 303 27817825 304 28094161 305 28372321 306 28652311 307 28934137 308 29217805 309 29503321 310 29790691 311 30079921 312 30371017 313 30663985 314 30958831 315 31255561 316 31554181 317 31854697 318 32157115 319 32461441 320 32767681 321 33075841 322 33385927 323 33697945 324 34011901 325 34327801 326 34645651 327 34965457 328 35287225 329 35610961 330 35936671 331 36264361 332 36594037 333 36925705 334 37259371 335 37595041 336 37932721 337 38272417 338 38614135 339 38957881 340 39303661 341 39651481 342 40001347 343 40353265 344 40707241 345 41063281 346 41421391 347 41781577 348 42143845 349 42508201 350 42874651 351 43243201 352 43613857 353 43986625 354 44361511 355 44738521 356 45117661 357 45498937 358 45882355 359 46267921 360 46655641 361 47045521 362 47437567 363 47831785 364 48228181 365 48626761 366 49027531 367 49430497 368 49835665 369 50243041 370 50652631 371 51064441 372 51478477 373 51894745 374 52313251 375 52734001 376 53157001 377 53582257 378 54009775 379 54439561 380 54871621 381 55305961 382 55742587 383 56181505 384 56622721 385 57066241 386 57512071 387 57960217 388 58410685 389 58863481 390 59318611 391 59776081 392 60235897 393 60698065 394 61162591 395 61629481 396 62098741 397 62570377 398 63044395 399 63520801 400 63999601 401 64480801 402 64964407 403 65450425 404 65938861 405 66429721 406 66923011 407 67418737 408 67916905 409 68417521 410 68920591 411 69426121 412 69934117 413 70444585 414 70957531 415 71472961 416 71990881 417 72511297 418 73034215 419 73559641 420 74087581 421 74618041 422 75151027 423 75686545 424 76224601 425 76765201 426 77308351 427 77854057 428 78402325 429 78953161 430 79506571 431 80062561 432 80621137 433 81182305 434 81746071 435 82312441 436 82881421 437 83453017 438 84027235 439 84604081 440 85183561 441 85765681 442 86350447 443 86937865 444 87527941 445 88120681 446 88716091 447 89314177 448 89914945 449 90518401 450 91124551 451 91733401 452 92344957 453 92959225 454 93576211 455 94195921 456 94818361 457 95443537 458 96071455 459 96702121 460 97335541 461 97971721 462 98610667 463 99252385 464 99896881 465 100544161 466 101194231 467 101847097 468 102502765 469 103161241 470 103822531 471 104486641 472 105153577 473 105823345 474 106495951 475 107171401 476 107849701 477 108530857 478 109214875 479 109901761 480 110591521 481 111284161 482 111979687 483 112678105 484 113379421 485 114083641 486 114790771 487 115500817 488 116213785 489 116929681 490 117648511 491 118370281 492 119094997 493 119822665 494 120553291 495 121286881 496 122023441 497 122762977 498 123505495 499 124251001 500 124999501 501 125751001 502 126505507 503 127263025 504 128023561 505 128787121 506 129553711 507 130323337 508 131096005 509 131871721 510 132650491 511 133432321 512 134217217 513 135005185 514 135796231 515 136590361 516 137387581 517 138187897 518 138991315 519 139797841 520 140607481 521 141420241 522 142236127 523 143055145 524 143877301 525 144702601 526 145531051 527 146362657 528 147197425 529 148035361 530 148876471 531 149720761 532 150568237 533 151418905 534 152272771 535 153129841 536 153990121 537 154853617 538 155720335 539 156590281 540 157463461 541 158339881 542 159219547 543 160102465 544 160988641 545 161878081 546 162770791 547 163666777 548 164566045 549 165468601 550 166374451 551 167283601 552 168196057 553 169111825 554 170030911 555 170953321 556 171879061 557 172808137 558 173740555 559 174676321 560 175615441 561 176557921 562 177503767 563 178452985 564 179405581 565 180361561 566 181320931 567 182283697 568 183249865 569 184219441 570 185192431 571 186168841 572 187148677 573 188131945 574 189118651 575 190108801 576 191102401 577 192099457 578 193099975 579 194103961 580 195111421 581 196122361 582 197136787 583 198154705 584 199176121 585 200201041 586 201229471 587 202261417 588 203296885 589 204335881 590 205378411 591 206424481 592 207474097 593 208527265 594 209583991 595 210644281 596 211708141 597 212775577 598 213846595 599 214921201 600 215999401 601 217081201 602 218166607 603 219255625 604 220348261 605 221444521 606 222544411 607 223647937 608 224755105 609 225865921 610 226980391 611 228098521 612 229220317 613 230345785 614 231474931 615 232607761 616 233744281 617 234884497 618 236028415 619 237176041 620 238327381 621 239482441 622 240641227 623 241803745 624 242970001 625 244140001 626 245313751 627 246491257 628 247672525 629 248857561 630 250046371 631 251238961 632 252435337 633 253635505 634 254839471 635 256047241 636 257258821 637 258474217 638 259693435 639 260916481 640 262143361 641 263374081 642 264608647 643 265847065 644 267089341 645 268335481 646 269585491 647 270839377 648 272097145 649 273358801 650 274624351 651 275893801 652 277167157 653 278444425 654 279725611 655 281010721 656 282299761 657 283592737 658 284889655 659 286190521 660 287495341 661 288804121 662 290116867 663 291433585 664 292754281 665 294078961 666 295407631 667 296740297 668 298076965 669 299417641 670 300762331 671 302111041 672 303463777 673 304820545 674 306181351 675 307546201 676 308915101 677 310288057 678 311665075 679 313046161 680 314431321 681 315820561 682 317213887 683 318611305 684 320012821 685 321418441 686 322828171 687 324242017 688 325659985 689 327082081 690 328508311 691 329938681 692 331373197 693 332811865 694 334254691 695 335701681 696 337152841 697 338608177 698 340067695 699 341531401 700 342999301 701 344471401 702 345947707 703 347428225 704 348912961 705 350401921 706 351895111 707 353392537 708 354894205 709 356400121 710 357910291 711 359424721 712 360943417 713 362466385 714 363993631 715 365525161 716 367060981 717 368601097 718 370145515 719 371694241 720 373247281 721 374804641 722 376366327 723 377932345 724 379502701 725 381077401 726 382656451 727 384239857 728 385827625 729 387419761 730 389016271 731 390617161 732 392222437 733 393832105 734 395446171 735 397064641 736 398687521 737 400314817 738 401946535 739 403582681 740 405223261 741 406868281 742 408517747 743 410171665 744 411830041 745 413492881 746 415160191 747 416831977 748 418508245 749 420189001 750 421874251 751 423564001 752 425258257 753 426957025 754 428660311 755 430368121 756 432080461 757 433797337 758 435518755 759 437244721 760 438975241 761 440710321 762 442449967 763 444194185 764 445942981 765 447696361 766 449454331 767 451216897 768 452984065 769 454755841 770 456532231 771 458313241 772 460098877 773 461889145 774 463684051 775 465483601 776 467287801 777 469096657 778 470910175 779 472728361 780 474551221 781 476378761 782 478210987 783 480047905 784 481889521 785 483735841 786 485586871 787 487442617 788 489303085 789 491168281 790 493038211 791 494912881 792 496792297 793 498676465 794 500565391 795 502459081 796 504357541 797 506260777 798 508168795 799 510081601 800 511999201 801 513921601 802 515848807 803 517780825 804 519717661 805 521659321 806 523605811 807 525557137 808 527513305 809 529474321 810 531440191 811 533410921 812 535386517 813 537366985 814 539352331 815 541342561 816 543337681 817 545337697 818 547342615 819 549352441 820 551367181 821 553386841 822 555411427 823 557440945 824 559475401 825 561514801 826 563559151 827 565608457 828 567662725 829 569721961 830 571786171 831 573855361 832 575929537 833 578008705 834 580092871 835 582182041 836 584276221 837 586375417 838 588479635 839 590588881 840 592703161 841 594822481 842 596946847 843 599076265 844 601210741 845 603350281 846 605494891 847 607644577 848 609799345 849 611959201 850 614124151 851 616294201 852 618469357 853 620649625 854 622835011 855 625025521 856 627221161 857 629421937 858 631627855 859 633838921 860 636055141 861 638276521 862 640503067 863 642734785 864 644971681 865 647213761 866 649461031 867 651713497 868 653971165 869 656234041 870 658502131 871 660775441 872 663053977 873 665337745 874 667626751 875 669921001 876 672220501 877 674525257 878 676835275 879 679150561 880 681471121 881 683796961 882 686128087 883 688464505 884 690806221 885 693153241 886 695505571 887 697863217 888 700226185 889 702594481 890 704968111 891 707347081 892 709731397 893 712121065 894 714516091 895 716916481 896 719322241 897 721733377 898 724149895 899 726571801 900 728999101 901 731431801 902 733869907 903 736313425 904 738762361 905 741216721 906 743676511 907 746141737 908 748612405 909 751088521 910 753570091 911 756057121 912 758549617 913 761047585 914 763551031 915 766059961 916 768574381 917 771094297 918 773619715 919 776150641 920 778687081 921 781229041 922 783776527 923 786329545 924 788888101 925 791452201 926 794021851 927 796597057 928 799177825 929 801764161 930 804356071 931 806953561 932 809556637 933 812165305 934 814779571 935 817399441 936 820024921 937 822656017 938 825292735 939 827935081 940 830583061 941 833236681 942 835895947 943 838560865 944 841231441 945 843907681 946 846589591 947 849277177 948 851970445 949 854669401 950 857374051 951 860084401 952 862800457 953 865522225 954 868249711 955 870982921 956 873721861 957 876466537 958 879216955 959 881973121 960 884735041 961 887502721 962 890276167 963 893055385 964 895840381 965 898631161 966 901427731 967 904230097 968 907038265 969 909852241 970 912672031 971 915497641 972 918329077 973 921166345 974 924009451 975 926858401 976 929713201 977 932573857 978 935440375 979 938312761 980 941191021 981 944075161 982 946965187 983 949861105 984 952762921 985 955670641 986 958584271 987 961503817 988 964429285 989 967360681 990 970298011 991 973241281 992 976190497 993 979145665 994 982106791 995 985073881 996 988046941 997 991025977 998 994010995 999 997002001 1000 999999001