0 1 1 5 2 29 3 109 4 305 5 701 6 1405 7 2549 8 4289 9 6805 10 10301 11 15005 12 21169 13 29069 14 39005 15 51301 16 66305 17 84389 18 105949 19 131405 20 161201 21 195805 22 235709 23 281429 24 333505 25 392501 26 459005 27 533629 28 617009 29 709805 30 812701 31 926405 32 1051649 33 1189189 34 1339805 35 1504301 36 1683505 37 1878269 38 2089469 39 2318005 40 2564801 41 2830805 42 3116989 43 3424349 44 3753905 45 4106701 46 4483805 47 4886309 48 5315329 49 5772005 50 6257501 51 6773005 52 7319729 53 7898909 54 8511805 55 9159701 56 9843905 57 10565749 58 11326589 59 12127805 60 12970801 61 13857005 62 14787869 63 15764869 64 16789505 65 17863301 66 18987805 67 20164589 68 21395249 69 22681405 70 24024701 71 25426805 72 26889409 73 28414229 74 30003005 75 31657501 76 33379505 77 35170829 78 37033309 79 38968805 80 40979201 81 43066405 82 45232349 83 47478989 84 49808305 85 52222301 86 54723005 87 57312469 88 59992769 89 62766005 90 65634301 91 68599805 92 71664689 93 74831149 94 78101405 95 81477701 96 84962305 97 88557509 98 92265629 99 96089005 100 100030001 101 104091005 102 108274429 103 112582709 104 117018305 105 121583701 106 126281405 107 131113949 108 136083889 109 141193805 110 146446301 111 151844005 112 157389569 113 163085669 114 168935005 115 174940301 116 181104305 117 187429789 118 193919549 119 200576405 120 207403201 121 214402805 122 221578109 123 228932029 124 236467505 125 244187501 126 252095005 127 260193029 128 268484609 129 276972805 130 285660701 131 294551405 132 303648049 133 312953789 134 322471805 135 332205301 136 342157505 137 352331669 138 362731069 139 373359005 140 384218801 141 395313805 142 406647389 143 418222949 144 430043905 145 442113701 146 454435805 147 467013709 148 479850929 149 492951005 150 506317501 151 519954005 152 533864129 153 548051509 154 562519805 155 577272701 156 592313905 157 607647149 158 623276189 159 639204805 160 655436801 161 671976005 162 688826269 163 705991469 164 723475505 165 741282301 166 759415805 167 777879989 168 796678849 169 815816405 170 835296701 171 855123805 172 875301809 173 895834829 174 916727005 175 937982501 176 959605505 177 981600229 178 1003970909 179 1026721805 180 1049857201 181 1073381405 182 1097298749 183 1121613589 184 1146330305 185 1171453301 186 1196987005 187 1222935869 188 1249304369 189 1276097005 190 1303318301 191 1330972805 192 1359065089 193 1387599749 194 1416581405 195 1446014701 196 1475904305 197 1506254909 198 1537071229 199 1568358005 200 1600120001 201 1632362005 202 1665088829 203 1698305309 204 1732016305 205 1766226701 206 1800941405 207 1836165349 208 1871903489 209 1908160805 210 1944942301 211 1982253005 212 2020097969 213 2058482269 214 2097411005 215 2136889301 216 2176922305 217 2217515189 218 2258673149 219 2300401405 220 2342705201 221 2385589805 222 2429060509 223 2473122629 224 2517781505 225 2563042501 226 2608911005 227 2655392429 228 2702492209 229 2750215805 230 2798568701 231 2847556405 232 2897184449 233 2947458389 234 2998383805 235 3049966301 236 3102211505 237 3155125069 238 3208712669 239 3262980005 240 3317932801 241 3373576805 242 3429917789 243 3486961549 244 3544713905 245 3603180701 246 3662367805 247 3722281109 248 3782926529 249 3844310005 250 3906437501 251 3969315005 252 4032948529 253 4097344109 254 4162507805 255 4228445701 256 4295163905 257 4362668549 258 4430965789 259 4500061805 260 4569962801 261 4640675005 262 4712204669 263 4784558069 264 4857741505 265 4931761301 266 5006623805 267 5082335389 268 5158902449 269 5236331405 270 5314628701 271 5393800805 272 5473854209 273 5554795429 274 5636631005 275 5719367501 276 5803011505 277 5887569629 278 5973048509 279 6059454805 280 6146795201 281 6235076405 282 6324305149 283 6414488189 284 6505632305 285 6597744301 286 6690831005 287 6784899269 288 6879955969 289 6976008005 290 7073062301 291 7171125805 292 7270205489 293 7370308349 294 7471441405 295 7573611701 296 7676826305 297 7781092309 298 7886416829 299 7992807005 300 8100270001 301 8208813005 302 8318443229 303 8429167909 304 8540994305 305 8653929701 306 8767981405 307 8883156749 308 8999463089 309 9116907805 310 9235498301 311 9355242005 312 9476146369 313 9598218869 314 9721467005 315 9845898301 316 9971520305 317 10098340589 318 10226366749 319 10355606405 320 10486067201 321 10617756805 322 10750682909 323 10884853229 324 11020275505 325 11156957501 326 11294907005 327 11434131829 328 11574639809 329 11716438805 330 11859536701 331 12003941405 332 12149660849 333 12296702989 334 12445075805 335 12594787301 336 12745845505 337 12898258469 338 13052034269 339 13207181005 340 13363706801 341 13521619805 342 13680928189 343 13841640149 344 14003763905 345 14167307701 346 14332279805 347 14498688509 348 14666542129 349 14835849005 350 15006617501 351 15178856005 352 15352572929 353 15527776709 354 15704475805 355 15882678701 356 16062393905 357 16243629949 358 16426395389 359 16610698805 360 16796548801 361 16983954005 362 17172923069 363 17363464669 364 17555587505 365 17749300301 366 17944611805 367 18141530789 368 18340066049 369 18540226405 370 18742020701 371 18945457805 372 19150546609 373 19357296029 374 19565715005 375 19775812501 376 19987597505 377 20201079029 378 20416266109 379 20633167805 380 20851793201 381 21072151405 382 21294251549 383 21518102789 384 21743714305 385 21971095301 386 22200255005 387 22431202669 388 22663947569 389 22898499005 390 23134866301 391 23373058805 392 23613085889 393 23854956949 394 24098681405 395 24344268701 396 24591728305 397 24841069709 398 25092302429 399 25345436005 400 25600480001 401 25857444005 402 26116337629 403 26377170509 404 26639952305 405 26904692701 406 27171401405 407 27440088149 408 27710762689 409 27983434805 410 28258114301 411 28534811005 412 28813534769 413 29094295469 414 29377103005 415 29661967301 416 29948898305 417 30237905989 418 30529000349 419 30822191405 420 31117489201 421 31414903805 422 31714445309 423 32016123829 424 32319949505 425 32625932501 426 32934083005 427 33244411229 428 33556927409 429 33871641805 430 34188564701 431 34507706405 432 34829077249 433 35152687589 434 35478547805 435 35806668301 436 36137059505 437 36469731869 438 36804695869 439 37141962005 440 37481540801 441 37823442805 442 38167678589 443 38514258749 444 38863193905 445 39214494701 446 39568171805 447 39924235909 448 40282697729 449 40643568005 450 41006857501 451 41372577005 452 41740737329 453 42111349309 454 42484423805 455 42859971701 456 43238003905 457 43618531349 458 44001564989 459 44387115805 460 44775194801 461 45165813005 462 45558981469 463 45954711269 464 46353013505 465 46753899301 466 47157379805 467 47563466189 468 47972169649 469 48383501405 470 48797472701 471 49214094805 472 49633379009 473 50055336629 474 50479979005 475 50907317501 476 51337363505 477 51770128429 478 52205623709 479 52643860805 480 53084851201 481 53528606405 482 53975137949 483 54424457389 484 54876576305 485 55331506301 486 55789259005 487 56249846069 488 56713279169 489 57179570005 490 57648730301 491 58120771805 492 58595706289 493 59073545549 494 59554301405 495 60037985701 496 60524610305 497 61014187109 498 61506728029 499 62002245005 500 62500750001 501 63002255005 502 63506772029 503 64014313109 504 64524890305 505 65038515701 506 65555201405 507 66074959549 508 66597802289 509 67123741805 510 67652790301 511 68184960005 512 68720263169 513 69258712069 514 69800319005 515 70345096301 516 70893056305 517 71444211389 518 71998573949 519 72556156405 520 73116971201 521 73681030805 522 74248347709 523 74818934429 524 75392803505 525 75969967501 526 76550439005 527 77134230629 528 77721355009 529 78311824805 530 78905652701 531 79502851405 532 80103433649 533 80707412189 534 81314799805 535 81925609301 536 82539853505 537 83157545269 538 83778697469 539 84403323005 540 85031434801 541 85663045805 542 86298168989 543 86936817349 544 87579003905 545 88224741701 546 88874043805 547 89526923309 548 90183393329 549 90843467005 550 91507157501 551 92174478005 552 92845441729 553 93520061909 554 94198351805 555 94880324701 556 95565993905 557 96255372749 558 96948474589 559 97645312805 560 98345900801 561 99050252005 562 99758379869 563 100470297869 564 101186019505 565 101905558301 566 102628927805 567 103356141589 568 104087213249 569 104822156405 570 105560984701 571 106303711805 572 107050351409 573 107800917229 574 108555423005 575 109313882501 576 110076309505 577 110842717829 578 111613121309 579 112387533805 580 113165969201 581 113948441405 582 114734964349 583 115525551989 584 116320218305 585 117118977301 586 117921843005 587 118728829469 588 119539950769 589 120355221005 590 121174654301 591 121998264805 592 122826066689 593 123658074149 594 124494301405 595 125334762701 596 126179472305 597 127028444509 598 127881693629 599 128739234005 600 129601080001 601 130467246005 602 131337746429 603 132212595709 604 133091808305 605 133975398701 606 134863381405 607 135755770949 608 136652581889 609 137553828805 610 138459526301 611 139369689005 612 140284331569 613 141203468669 614 142127115005 615 143055285301 616 143987994305 617 144925256789 618 145867087549 619 146813501405 620 147764513201 621 148720137805 622 149680390109 623 150645285029 624 151614837505 625 152589062501 626 153567975005 627 154551590029 628 155539922609 629 156532987805 630 157530800701 631 158533376405 632 159540730049 633 160552876789 634 161569831805 635 162591610301 636 163618227505 637 164649698669 638 165686039069 639 166727264005 640 167773388801 641 168824428805 642 169880399389 643 170941315949 644 172007193905 645 173078048701 646 174153895805 647 175234750709 648 176320628929 649 177411546005 650 178507517501 651 179608559005 652 180714686129 653 181825914509 654 182942259805 655 184063737701 656 185190363905 657 186322154149 658 187459124189 659 188601289805 660 189748666801 661 190901271005 662 192059118269 663 193222224469 664 194390605505 665 195564277301 666 196743255805 667 197927556989 668 199117196849 669 200312191405 670 201512556701 671 202718308805 672 203929463809 673 205146037829 674 206368047005 675 207595507501 676 208828435505 677 210066847229 678 211310758909 679 212560186805 680 213815147201 681 215075656405 682 216341730749 683 217613386589 684 218890640305 685 220173508301 686 221462007005 687 222756152869 688 224055962369 689 225361452005 690 226672638301 691 227989537805 692 229312167089 693 230640542749 694 231974681405 695 233314599701 696 234660314305 697 236011841909 698 237369199229 699 238732403005 700 240101470001 701 241476417005 702 242857260829 703 244244018309 704 245636706305 705 247035341701 706 248439941405 707 249850522349 708 251267101489 709 252689695805 710 254118322301 711 255552998005 712 256993739969 713 258440565269 714 259893491005 715 261352534301 716 262817712305 717 264289042189 718 265766541149 719 267250226405 720 268740115201 721 270236224805 722 271738572509 723 273247175629 724 274762051505 725 276283217501 726 277810691005 727 279344489429 728 280884630209 729 282431130805 730 283984008701 731 285543281405 732 287108966449 733 288681081389 734 290259643805 735 291844671301 736 293436181505 737 295034192069 738 296638720669 739 298249785005 740 299867402801 741 301491591805 742 303122369789 743 304759754549 744 306403763905 745 308054415701 746 309711727805 747 311375718109 748 313046404529 749 314723805005 750 316407937501 751 318098820005 752 319796470529 753 321500907109 754 323212147805 755 324930210701 756 326655113905 757 328386875549 758 330125513789 759 331871046805 760 333623492801 761 335382870005 762 337149196669 763 338922491069 764 340702771505 765 342490056301 766 344284363805 767 346085712389 768 347894120449 769 349709606405 770 351532188701 771 353361885805 772 355198716209 773 357042698429 774 358893851005 775 360752192501 776 362617741505 777 364490516629 778 366370536509 779 368257819805 780 370152385201 781 372054251405 782 373963437149 783 375879961189 784 377803842305 785 379735099301 786 381673751005 787 383619816269 788 385573313969 789 387534263005 790 389502682301 791 391478590805 792 393462007489 793 395452951349 794 397451441405 795 399457496701 796 401471136305 797 403492379309 798 405521244829 799 407557752005 800 409601920001 801 411653768005 802 413713315229 803 415780580909 804 417855584305 805 419938344701 806 422028881405 807 424127213749 808 426233361089 809 428347342805 810 430469178301 811 432598887005 812 434736488369 813 436882001869 814 439035447005 815 441196843301 816 443366210305 817 445543567589 818 447728934749 819 449922331405 820 452123777201 821 454333291805 822 456550894909 823 458776606229 824 461010445505 825 463252432501 826 465502587005 827 467760928829 828 470027477809 829 472302253805 830 474585276701 831 476876566405 832 479176142849 833 481484025989 834 483800235805 835 486124792301 836 488457715505 837 490799025469 838 493148742269 839 495506886005 840 497873476801 841 500248534805 842 502632080189 843 505024133149 844 507424713905 845 509833842701 846 512251539805 847 514677825509 848 517112720129 849 519556244005 850 522008417501 851 524469261005 852 526938794929 853 529417039709 854 531904015805 855 534399743701 856 536904243905 857 539417536949 858 541939643389 859 544470583805 860 547010378801 861 549559049005 862 552116615069 863 554683097669 864 557258517505 865 559842895301 866 562436251805 867 565038607789 868 567649984049 869 570270401405 870 572899880701 871 575538442805 872 578186108609 873 580842899029 874 583508835005 875 586183937501 876 588868227505 877 591561726029 878 594264454109 879 596976432805 880 599697683201 881 602428226405 882 605168083549 883 607917275789 884 610675824305 885 613443750301 886 616221075005 887 619007819669 888 621804005569 889 624609654005 890 627424786301 891 630249423805 892 633083587889 893 635927299949 894 638780581405 895 641643453701 896 644515938305 897 647398056709 898 650289830429 899 653191281005 900 656102430001 901 659023299005 902 661953909629 903 664894283509 904 667844442305 905 670804407701 906 673774201405 907 676753845149 908 679743360689 909 682742769805 910 685752094301 911 688771356005 912 691800576769 913 694839778469 914 697888983005 915 700948212301 916 704017488305 917 707096832989 918 710186268349 919 713285816405 920 716395499201 921 719515338805 922 722645357309 923 725785576829 924 728936019505 925 732096707501 926 735267663005 927 738448908229 928 741640465409 929 744842356805 930 748054604701 931 751277231405 932 754510259249 933 757753710589 934 761007607805 935 764271973301 936 767546829505 937 770832198869 938 774128103869 939 777434567005 940 780751610801 941 784079257805 942 787417530589 943 790766451749 944 794126043905 945 797496329701 946 800877331805 947 804269072909 948 807671575729 949 811084863005 950 814508957501 951 817943882005 952 821389659329 953 824846312309 954 828313863805 955 831792336701 956 835281753905 957 838782138349 958 842293512989 959 845815900805 960 849349324801 961 852893808005 962 856449373469 963 860016044269 964 863593843505 965 867182794301 966 870782919805 967 874394243189 968 878016787649 969 881650576405 970 885295632701 971 888951979805 972 892619641009 973 896298639629 974 899988999005 975 903690742501 976 907403893505 977 911128475429 978 914864511709 979 918612025805 980 922371041201 981 926141581405 982 929923669949 983 933717330389 984 937522586305 985 941339461301 986 945167979005 987 949008163069 988 952860037169 989 956723625005 990 960598950301 991 964486036805 992 968384908289 993 972295588549 994 976218101405 995 980152470701 996 984098720305 997 988056874109 998 992026956029 999 996008990005 1000 1000003000001