1 1 2 2 3 3 4 10 5 29 6 66 7 127 8 218 9 345 10 514 11 731 12 1002 13 1333 14 1730 15 2199 16 2746 17 3377 18 4098 19 4915 20 5834 21 6861 22 8002 23 9263 24 10650 25 12169 26 13826 27 15627 28 17578 29 19685 30 21954 31 24391 32 27002 33 29793 34 32770 35 35939 36 39306 37 42877 38 46658 39 50655 40 54874 41 59321 42 64002 43 68923 44 74090 45 79509 46 85186 47 91127 48 97338 49 103825 50 110594 51 117651 52 125002 53 132653 54 140610 55 148879 56 157466 57 166377 58 175618 59 185195 60 195114 61 205381 62 216002 63 226983 64 238330 65 250049 66 262146 67 274627 68 287498 69 300765 70 314434 71 328511 72 343002 73 357913 74 373250 75 389019 76 405226 77 421877 78 438978 79 456535 80 474554 81 493041 82 512002 83 531443 84 551370 85 571789 86 592706 87 614127 88 636058 89 658505 90 681474 91 704971 92 729002 93 753573 94 778690 95 804359 96 830586 97 857377 98 884738 99 912675 100 941194 101 970301 102 1000002 103 1030303 104 1061210 105 1092729 106 1124866 107 1157627 108 1191018 109 1225045 110 1259714 111 1295031 112 1331002 113 1367633 114 1404930 115 1442899 116 1481546 117 1520877 118 1560898 119 1601615 120 1643034 121 1685161 122 1728002 123 1771563 124 1815850 125 1860869 126 1906626 127 1953127 128 2000378 129 2048385 130 2097154 131 2146691 132 2197002 133 2248093 134 2299970 135 2352639 136 2406106 137 2460377 138 2515458 139 2571355 140 2628074 141 2685621 142 2744002 143 2803223 144 2863290 145 2924209 146 2985986 147 3048627 148 3112138 149 3176525 150 3241794 151 3307951 152 3375002 153 3442953 154 3511810 155 3581579 156 3652266 157 3723877 158 3796418 159 3869895 160 3944314 161 4019681 162 4096002 163 4173283 164 4251530 165 4330749 166 4410946 167 4492127 168 4574298 169 4657465 170 4741634 171 4826811 172 4913002 173 5000213 174 5088450 175 5177719 176 5268026 177 5359377 178 5451778 179 5545235 180 5639754 181 5735341 182 5832002 183 5929743 184 6028570 185 6128489 186 6229506 187 6331627 188 6434858 189 6539205 190 6644674 191 6751271 192 6859002 193 6967873 194 7077890 195 7189059 196 7301386 197 7414877 198 7529538 199 7645375 200 7762394 201 7880601 202 8000002 203 8120603 204 8242410 205 8365429 206 8489666 207 8615127 208 8741818 209 8869745 210 8998914 211 9129331 212 9261002 213 9393933 214 9528130 215 9663599 216 9800346 217 9938377 218 10077698 219 10218315 220 10360234 221 10503461 222 10648002 223 10793863 224 10941050 225 11089569 226 11239426 227 11390627 228 11543178 229 11697085 230 11852354 231 12008991 232 12167002 233 12326393 234 12487170 235 12649339 236 12812906 237 12977877 238 13144258 239 13312055 240 13481274 241 13651921 242 13824002 243 13997523 244 14172490 245 14348909 246 14526786 247 14706127 248 14886938 249 15069225 250 15252994 251 15438251 252 15625002 253 15813253 254 16003010 255 16194279 256 16387066 257 16581377 258 16777218 259 16974595 260 17173514 261 17373981 262 17576002 263 17779583 264 17984730 265 18191449 266 18399746 267 18609627 268 18821098 269 19034165 270 19248834 271 19465111 272 19683002 273 19902513 274 20123650 275 20346419 276 20570826 277 20796877 278 21024578 279 21253935 280 21484954 281 21717641 282 21952002 283 22188043 284 22425770 285 22665189 286 22906306 287 23149127 288 23393658 289 23639905 290 23887874 291 24137571 292 24389002 293 24642173 294 24897090 295 25153759 296 25412186 297 25672377 298 25934338 299 26198075 300 26463594 301 26730901 302 27000002 303 27270903 304 27543610 305 27818129 306 28094466 307 28372627 308 28652618 309 28934445 310 29218114 311 29503631 312 29791002 313 30080233 314 30371330 315 30664299 316 30959146 317 31255877 318 31554498 319 31855015 320 32157434 321 32461761 322 32768002 323 33076163 324 33386250 325 33698269 326 34012226 327 34328127 328 34645978 329 34965785 330 35287554 331 35611291 332 35937002 333 36264693 334 36594370 335 36926039 336 37259706 337 37595377 338 37933058 339 38272755 340 38614474 341 38958221 342 39304002 343 39651823 344 40001690 345 40353609 346 40707586 347 41063627 348 41421738 349 41781925 350 42144194 351 42508551 352 42875002 353 43243553 354 43614210 355 43986979 356 44361866 357 44738877 358 45118018 359 45499295 360 45882714 361 46268281 362 46656002 363 47045883 364 47437930 365 47832149 366 48228546 367 48627127 368 49027898 369 49430865 370 49836034 371 50243411 372 50653002 373 51064813 374 51478850 375 51895119 376 52313626 377 52734377 378 53157378 379 53582635 380 54010154 381 54439941 382 54872002 383 55306343 384 55742970 385 56181889 386 56623106 387 57066627 388 57512458 389 57960605 390 58411074 391 58863871 392 59319002 393 59776473 394 60236290 395 60698459 396 61162986 397 61629877 398 62099138 399 62570775 400 63044794 401 63521201 402 64000002 403 64481203 404 64964810 405 65450829 406 65939266 407 66430127 408 66923418 409 67419145 410 67917314 411 68417931 412 68921002 413 69426533 414 69934530 415 70444999 416 70957946 417 71473377 418 71991298 419 72511715 420 73034634 421 73560061 422 74088002 423 74618463 424 75151450 425 75686969 426 76225026 427 76765627 428 77308778 429 77854485 430 78402754 431 78953591 432 79507002 433 80062993 434 80621570 435 81182739 436 81746506 437 82312877 438 82881858 439 83453455 440 84027674 441 84604521 442 85184002 443 85766123 444 86350890 445 86938309 446 87528386 447 88121127 448 88716538 449 89314625 450 89915394 451 90518851 452 91125002 453 91733853 454 92345410 455 92959679 456 93576666 457 94196377 458 94818818 459 95443995 460 96071914 461 96702581 462 97336002 463 97972183 464 98611130 465 99252849 466 99897346 467 100544627 468 101194698 469 101847565 470 102503234 471 103161711 472 103823002 473 104487113 474 105154050 475 105823819 476 106496426 477 107171877 478 107850178 479 108531335 480 109215354 481 109902241 482 110592002 483 111284643 484 111980170 485 112678589 486 113379906 487 114084127 488 114791258 489 115501305 490 116214274 491 116930171 492 117649002 493 118370773 494 119095490 495 119823159 496 120553786 497 121287377 498 122023938 499 122763475 500 123505994 501 124251501 502 125000002 503 125751503 504 126506010 505 127263529 506 128024066 507 128787627 508 129554218 509 130323845 510 131096514 511 131872231 512 132651002 513 133432833 514 134217730 515 135005699 516 135796746 517 136590877 518 137388098 519 138188415 520 138991834 521 139798361 522 140608002 523 141420763 524 142236650 525 143055669 526 143877826 527 144703127 528 145531578 529 146363185 530 147197954 531 148035891 532 148877002 533 149721293 534 150568770 535 151419439 536 152273306 537 153130377 538 153990658 539 154854155 540 155720874 541 156590821 542 157464002 543 158340423 544 159220090 545 160103009 546 160989186 547 161878627 548 162771338 549 163667325 550 164566594 551 165469151 552 166375002 553 167284153 554 168196610 555 169112379 556 170031466 557 170953877 558 171879618 559 172808695 560 173741114 561 174676881 562 175616002 563 176558483 564 177504330 565 178453549 566 179406146 567 180362127 568 181321498 569 182284265 570 183250434 571 184220011 572 185193002 573 186169413 574 187149250 575 188132519 576 189119226 577 190109377 578 191102978 579 192100035 580 193100554 581 194104541 582 195112002 583 196122943 584 197137370 585 198155289 586 199176706 587 200201627 588 201230058 589 202262005 590 203297474 591 204336471 592 205379002 593 206425073 594 207474690 595 208527859 596 209584586 597 210644877 598 211708738 599 212776175 600 213847194 601 214921801 602 216000002 603 217081803 604 218167210 605 219256229 606 220348866 607 221445127 608 222545018 609 223648545 610 224755714 611 225866531 612 226981002 613 228099133 614 229220930 615 230346399 616 231475546 617 232608377 618 233744898 619 234885115 620 236029034 621 237176661 622 238328002 623 239483063 624 240641850 625 241804369 626 242970626 627 244140627 628 245314378 629 246491885 630 247673154 631 248858191 632 250047002 633 251239593 634 252435970 635 253636139 636 254840106 637 256047877 638 257259458 639 258474855 640 259694074 641 260917121 642 262144002 643 263374723 644 264609290 645 265847709 646 267089986 647 268336127 648 269586138 649 270840025 650 272097794 651 273359451 652 274625002 653 275894453 654 277167810 655 278445079 656 279726266 657 281011377 658 282300418 659 283593395 660 284890314 661 286191181 662 287496002 663 288804783 664 290117530 665 291434249 666 292754946 667 294079627 668 295408298 669 296740965 670 298077634 671 299418311 672 300763002 673 302111713 674 303464450 675 304821219 676 306182026 677 307546877 678 308915778 679 310288735 680 311665754 681 313046841 682 314432002 683 315821243 684 317214570 685 318611989 686 320013506 687 321419127 688 322828858 689 324242705 690 325660674 691 327082771 692 328509002 693 329939373 694 331373890 695 332812559 696 334255386 697 335702377 698 337153538 699 338608875 700 340068394 701 341532101 702 343000002 703 344472103 704 345948410 705 347428929 706 348913666 707 350402627 708 351895818 709 353393245 710 354894914 711 356400831 712 357911002 713 359425433 714 360944130 715 362467099 716 363994346 717 365525877 718 367061698 719 368601815 720 370146234 721 371694961 722 373248002 723 374805363 724 376367050 725 377933069 726 379503426 727 381078127 728 382657178 729 384240585 730 385828354 731 387420491 732 389017002 733 390617893 734 392223170 735 393832839 736 395446906 737 397065377 738 398688258 739 400315555 740 401947274 741 403583421 742 405224002 743 406869023 744 408518490 745 410172409 746 411830786 747 413493627 748 415160938 749 416832725 750 418508994 751 420189751 752 421875002 753 423564753 754 425259010 755 426957779 756 428661066 757 430368877 758 432081218 759 433798095 760 435519514 761 437245481 762 438976002 763 440711083 764 442450730 765 444194949 766 445943746 767 447697127 768 449455098 769 451217665 770 452984834 771 454756611 772 456533002 773 458314013 774 460099650 775 461889919 776 463684826 777 465484377 778 467288578 779 469097435 780 470910954 781 472729141 782 474552002 783 476379543 784 478211770 785 480048689 786 481890306 787 483736627 788 485587658 789 487443405 790 489303874 791 491169071 792 493039002 793 494913673 794 496793090 795 498677259 796 500566186 797 502459877 798 504358338 799 506261575 800 508169594 801 510082401 802 512000002 803 513922403 804 515849610 805 517781629 806 519718466 807 521660127 808 523606618 809 525557945 810 527514114 811 529475131 812 531441002 813 533411733 814 535387330 815 537367799 816 539353146 817 541343377 818 543338498 819 545338515 820 547343434 821 549353261 822 551368002 823 553387663 824 555412250 825 557441769 826 559476226 827 561515627 828 563559978 829 565609285 830 567663554 831 569722791 832 571787002 833 573856193 834 575930370 835 578009539 836 580093706 837 582182877 838 584277058 839 586376255 840 588480474 841 590589721 842 592704002 843 594823323 844 596947690 845 599077109 846 601211586 847 603351127 848 605495738 849 607645425 850 609800194 851 611960051 852 614125002 853 616295053 854 618470210 855 620650479 856 622835866 857 625026377 858 627222018 859 629422795 860 631628714 861 633839781 862 636056002 863 638277383 864 640503930 865 642735649 866 644972546 867 647214627 868 649461898 869 651714365 870 653972034 871 656234911 872 658503002 873 660776313 874 663054850 875 665338619 876 667627626 877 669921877 878 672221378 879 674526135 880 676836154 881 679151441 882 681472002 883 683797843 884 686128970 885 688465389 886 690807106 887 693154127 888 695506458 889 697864105 890 700227074 891 702595371 892 704969002 893 707347973 894 709732290 895 712121959 896 714516986 897 716917377 898 719323138 899 721734275 900 724150794 901 726572701 902 729000002 903 731432703 904 733870810 905 736314329 906 738763266 907 741217627 908 743677418 909 746142645 910 748613314 911 751089431 912 753571002 913 756058033 914 758550530 915 761048499 916 763551946 917 766060877 918 768575298 919 771095215 920 773620634 921 776151561 922 778688002 923 781229963 924 783777450 925 786330469 926 788889026 927 791453127 928 794022778 929 796597985 930 799178754 931 801765091 932 804357002 933 806954493 934 809557570 935 812166239 936 814780506 937 817400377 938 820025858 939 822656955 940 825293674 941 827936021 942 830584002 943 833237623 944 835896890 945 838561809 946 841232386 947 843908627 948 846590538 949 849278125 950 851971394 951 854670351 952 857375002 953 860085353 954 862801410 955 865523179 956 868250666 957 870983877 958 873722818 959 876467495 960 879217914 961 881974081 962 884736002 963 887503683 964 890277130 965 893056349 966 895841346 967 898632127 968 901428698 969 904231065 970 907039234 971 909853211 972 912673002 973 915498613 974 918330050 975 921167319 976 924010426 977 926859377 978 929714178 979 932574835 980 935441354 981 938313741 982 941192002 983 944076143 984 946966170 985 949862089 986 952763906 987 955671627 988 958585258 989 961504805 990 964430274 991 967361671 992 970299002 993 973242273 994 976191490 995 979146659 996 982107786 997 985074877 998 988047938 999 991026975 1000 994011994