0 3 1 4 2 11 3 30 4 67 5 128 6 219 7 346 8 515 9 732 10 1003 11 1334 12 1731 13 2200 14 2747 15 3378 16 4099 17 4916 18 5835 19 6862 20 8003 21 9264 22 10651 23 12170 24 13827 25 15628 26 17579 27 19686 28 21955 29 24392 30 27003 31 29794 32 32771 33 35940 34 39307 35 42878 36 46659 37 50656 38 54875 39 59322 40 64003 41 68924 42 74091 43 79510 44 85187 45 91128 46 97339 47 103826 48 110595 49 117652 50 125003 51 132654 52 140611 53 148880 54 157467 55 166378 56 175619 57 185196 58 195115 59 205382 60 216003 61 226984 62 238331 63 250050 64 262147 65 274628 66 287499 67 300766 68 314435 69 328512 70 343003 71 357914 72 373251 73 389020 74 405227 75 421878 76 438979 77 456536 78 474555 79 493042 80 512003 81 531444 82 551371 83 571790 84 592707 85 614128 86 636059 87 658506 88 681475 89 704972 90 729003 91 753574 92 778691 93 804360 94 830587 95 857378 96 884739 97 912676 98 941195 99 970302 100 1000003 101 1030304 102 1061211 103 1092730 104 1124867 105 1157628 106 1191019 107 1225046 108 1259715 109 1295032 110 1331003 111 1367634 112 1404931 113 1442900 114 1481547 115 1520878 116 1560899 117 1601616 118 1643035 119 1685162 120 1728003 121 1771564 122 1815851 123 1860870 124 1906627 125 1953128 126 2000379 127 2048386 128 2097155 129 2146692 130 2197003 131 2248094 132 2299971 133 2352640 134 2406107 135 2460378 136 2515459 137 2571356 138 2628075 139 2685622 140 2744003 141 2803224 142 2863291 143 2924210 144 2985987 145 3048628 146 3112139 147 3176526 148 3241795 149 3307952 150 3375003 151 3442954 152 3511811 153 3581580 154 3652267 155 3723878 156 3796419 157 3869896 158 3944315 159 4019682 160 4096003 161 4173284 162 4251531 163 4330750 164 4410947 165 4492128 166 4574299 167 4657466 168 4741635 169 4826812 170 4913003 171 5000214 172 5088451 173 5177720 174 5268027 175 5359378 176 5451779 177 5545236 178 5639755 179 5735342 180 5832003 181 5929744 182 6028571 183 6128490 184 6229507 185 6331628 186 6434859 187 6539206 188 6644675 189 6751272 190 6859003 191 6967874 192 7077891 193 7189060 194 7301387 195 7414878 196 7529539 197 7645376 198 7762395 199 7880602 200 8000003 201 8120604 202 8242411 203 8365430 204 8489667 205 8615128 206 8741819 207 8869746 208 8998915 209 9129332 210 9261003 211 9393934 212 9528131 213 9663600 214 9800347 215 9938378 216 10077699 217 10218316 218 10360235 219 10503462 220 10648003 221 10793864 222 10941051 223 11089570 224 11239427 225 11390628 226 11543179 227 11697086 228 11852355 229 12008992 230 12167003 231 12326394 232 12487171 233 12649340 234 12812907 235 12977878 236 13144259 237 13312056 238 13481275 239 13651922 240 13824003 241 13997524 242 14172491 243 14348910 244 14526787 245 14706128 246 14886939 247 15069226 248 15252995 249 15438252 250 15625003 251 15813254 252 16003011 253 16194280 254 16387067 255 16581378 256 16777219 257 16974596 258 17173515 259 17373982 260 17576003 261 17779584 262 17984731 263 18191450 264 18399747 265 18609628 266 18821099 267 19034166 268 19248835 269 19465112 270 19683003 271 19902514 272 20123651 273 20346420 274 20570827 275 20796878 276 21024579 277 21253936 278 21484955 279 21717642 280 21952003 281 22188044 282 22425771 283 22665190 284 22906307 285 23149128 286 23393659 287 23639906 288 23887875 289 24137572 290 24389003 291 24642174 292 24897091 293 25153760 294 25412187 295 25672378 296 25934339 297 26198076 298 26463595 299 26730902 300 27000003 301 27270904 302 27543611 303 27818130 304 28094467 305 28372628 306 28652619 307 28934446 308 29218115 309 29503632 310 29791003 311 30080234 312 30371331 313 30664300 314 30959147 315 31255878 316 31554499 317 31855016 318 32157435 319 32461762 320 32768003 321 33076164 322 33386251 323 33698270 324 34012227 325 34328128 326 34645979 327 34965786 328 35287555 329 35611292 330 35937003 331 36264694 332 36594371 333 36926040 334 37259707 335 37595378 336 37933059 337 38272756 338 38614475 339 38958222 340 39304003 341 39651824 342 40001691 343 40353610 344 40707587 345 41063628 346 41421739 347 41781926 348 42144195 349 42508552 350 42875003 351 43243554 352 43614211 353 43986980 354 44361867 355 44738878 356 45118019 357 45499296 358 45882715 359 46268282 360 46656003 361 47045884 362 47437931 363 47832150 364 48228547 365 48627128 366 49027899 367 49430866 368 49836035 369 50243412 370 50653003 371 51064814 372 51478851 373 51895120 374 52313627 375 52734378 376 53157379 377 53582636 378 54010155 379 54439942 380 54872003 381 55306344 382 55742971 383 56181890 384 56623107 385 57066628 386 57512459 387 57960606 388 58411075 389 58863872 390 59319003 391 59776474 392 60236291 393 60698460 394 61162987 395 61629878 396 62099139 397 62570776 398 63044795 399 63521202 400 64000003 401 64481204 402 64964811 403 65450830 404 65939267 405 66430128 406 66923419 407 67419146 408 67917315 409 68417932 410 68921003 411 69426534 412 69934531 413 70445000 414 70957947 415 71473378 416 71991299 417 72511716 418 73034635 419 73560062 420 74088003 421 74618464 422 75151451 423 75686970 424 76225027 425 76765628 426 77308779 427 77854486 428 78402755 429 78953592 430 79507003 431 80062994 432 80621571 433 81182740 434 81746507 435 82312878 436 82881859 437 83453456 438 84027675 439 84604522 440 85184003 441 85766124 442 86350891 443 86938310 444 87528387 445 88121128 446 88716539 447 89314626 448 89915395 449 90518852 450 91125003 451 91733854 452 92345411 453 92959680 454 93576667 455 94196378 456 94818819 457 95443996 458 96071915 459 96702582 460 97336003 461 97972184 462 98611131 463 99252850 464 99897347 465 100544628 466 101194699 467 101847566 468 102503235 469 103161712 470 103823003 471 104487114 472 105154051 473 105823820 474 106496427 475 107171878 476 107850179 477 108531336 478 109215355 479 109902242 480 110592003 481 111284644 482 111980171 483 112678590 484 113379907 485 114084128 486 114791259 487 115501306 488 116214275 489 116930172 490 117649003 491 118370774 492 119095491 493 119823160 494 120553787 495 121287378 496 122023939 497 122763476 498 123505995 499 124251502 500 125000003 501 125751504 502 126506011 503 127263530 504 128024067 505 128787628 506 129554219 507 130323846 508 131096515 509 131872232 510 132651003 511 133432834 512 134217731 513 135005700 514 135796747 515 136590878 516 137388099 517 138188416 518 138991835 519 139798362 520 140608003 521 141420764 522 142236651 523 143055670 524 143877827 525 144703128 526 145531579 527 146363186 528 147197955 529 148035892 530 148877003 531 149721294 532 150568771 533 151419440 534 152273307 535 153130378 536 153990659 537 154854156 538 155720875 539 156590822 540 157464003 541 158340424 542 159220091 543 160103010 544 160989187 545 161878628 546 162771339 547 163667326 548 164566595 549 165469152 550 166375003 551 167284154 552 168196611 553 169112380 554 170031467 555 170953878 556 171879619 557 172808696 558 173741115 559 174676882 560 175616003 561 176558484 562 177504331 563 178453550 564 179406147 565 180362128 566 181321499 567 182284266 568 183250435 569 184220012 570 185193003 571 186169414 572 187149251 573 188132520 574 189119227 575 190109378 576 191102979 577 192100036 578 193100555 579 194104542 580 195112003 581 196122944 582 197137371 583 198155290 584 199176707 585 200201628 586 201230059 587 202262006 588 203297475 589 204336472 590 205379003 591 206425074 592 207474691 593 208527860 594 209584587 595 210644878 596 211708739 597 212776176 598 213847195 599 214921802 600 216000003 601 217081804 602 218167211 603 219256230 604 220348867 605 221445128 606 222545019 607 223648546 608 224755715 609 225866532 610 226981003 611 228099134 612 229220931 613 230346400 614 231475547 615 232608378 616 233744899 617 234885116 618 236029035 619 237176662 620 238328003 621 239483064 622 240641851 623 241804370 624 242970627 625 244140628 626 245314379 627 246491886 628 247673155 629 248858192 630 250047003 631 251239594 632 252435971 633 253636140 634 254840107 635 256047878 636 257259459 637 258474856 638 259694075 639 260917122 640 262144003 641 263374724 642 264609291 643 265847710 644 267089987 645 268336128 646 269586139 647 270840026 648 272097795 649 273359452 650 274625003 651 275894454 652 277167811 653 278445080 654 279726267 655 281011378 656 282300419 657 283593396 658 284890315 659 286191182 660 287496003 661 288804784 662 290117531 663 291434250 664 292754947 665 294079628 666 295408299 667 296740966 668 298077635 669 299418312 670 300763003 671 302111714 672 303464451 673 304821220 674 306182027 675 307546878 676 308915779 677 310288736 678 311665755 679 313046842 680 314432003 681 315821244 682 317214571 683 318611990 684 320013507 685 321419128 686 322828859 687 324242706 688 325660675 689 327082772 690 328509003 691 329939374 692 331373891 693 332812560 694 334255387 695 335702378 696 337153539 697 338608876 698 340068395 699 341532102 700 343000003 701 344472104 702 345948411 703 347428930 704 348913667 705 350402628 706 351895819 707 353393246 708 354894915 709 356400832 710 357911003 711 359425434 712 360944131 713 362467100 714 363994347 715 365525878 716 367061699 717 368601816 718 370146235 719 371694962 720 373248003 721 374805364 722 376367051 723 377933070 724 379503427 725 381078128 726 382657179 727 384240586 728 385828355 729 387420492 730 389017003 731 390617894 732 392223171 733 393832840 734 395446907 735 397065378 736 398688259 737 400315556 738 401947275 739 403583422 740 405224003 741 406869024 742 408518491 743 410172410 744 411830787 745 413493628 746 415160939 747 416832726 748 418508995 749 420189752 750 421875003 751 423564754 752 425259011 753 426957780 754 428661067 755 430368878 756 432081219 757 433798096 758 435519515 759 437245482 760 438976003 761 440711084 762 442450731 763 444194950 764 445943747 765 447697128 766 449455099 767 451217666 768 452984835 769 454756612 770 456533003 771 458314014 772 460099651 773 461889920 774 463684827 775 465484378 776 467288579 777 469097436 778 470910955 779 472729142 780 474552003 781 476379544 782 478211771 783 480048690 784 481890307 785 483736628 786 485587659 787 487443406 788 489303875 789 491169072 790 493039003 791 494913674 792 496793091 793 498677260 794 500566187 795 502459878 796 504358339 797 506261576 798 508169595 799 510082402 800 512000003 801 513922404 802 515849611 803 517781630 804 519718467 805 521660128 806 523606619 807 525557946 808 527514115 809 529475132 810 531441003 811 533411734 812 535387331 813 537367800 814 539353147 815 541343378 816 543338499 817 545338516 818 547343435 819 549353262 820 551368003 821 553387664 822 555412251 823 557441770 824 559476227 825 561515628 826 563559979 827 565609286 828 567663555 829 569722792 830 571787003 831 573856194 832 575930371 833 578009540 834 580093707 835 582182878 836 584277059 837 586376256 838 588480475 839 590589722 840 592704003 841 594823324 842 596947691 843 599077110 844 601211587 845 603351128 846 605495739 847 607645426 848 609800195 849 611960052 850 614125003 851 616295054 852 618470211 853 620650480 854 622835867 855 625026378 856 627222019 857 629422796 858 631628715 859 633839782 860 636056003 861 638277384 862 640503931 863 642735650 864 644972547 865 647214628 866 649461899 867 651714366 868 653972035 869 656234912 870 658503003 871 660776314 872 663054851 873 665338620 874 667627627 875 669921878 876 672221379 877 674526136 878 676836155 879 679151442 880 681472003 881 683797844 882 686128971 883 688465390 884 690807107 885 693154128 886 695506459 887 697864106 888 700227075 889 702595372 890 704969003 891 707347974 892 709732291 893 712121960 894 714516987 895 716917378 896 719323139 897 721734276 898 724150795 899 726572702 900 729000003 901 731432704 902 733870811 903 736314330 904 738763267 905 741217628 906 743677419 907 746142646 908 748613315 909 751089432 910 753571003 911 756058034 912 758550531 913 761048500 914 763551947 915 766060878 916 768575299 917 771095216 918 773620635 919 776151562 920 778688003 921 781229964 922 783777451 923 786330470 924 788889027 925 791453128 926 794022779 927 796597986 928 799178755 929 801765092 930 804357003 931 806954494 932 809557571 933 812166240 934 814780507 935 817400378 936 820025859 937 822656956 938 825293675 939 827936022 940 830584003 941 833237624 942 835896891 943 838561810 944 841232387 945 843908628 946 846590539 947 849278126 948 851971395 949 854670352 950 857375003 951 860085354 952 862801411 953 865523180 954 868250667 955 870983878 956 873722819 957 876467496 958 879217915 959 881974082 960 884736003 961 887503684 962 890277131 963 893056350 964 895841347 965 898632128 966 901428699 967 904231066 968 907039235 969 909853212 970 912673003 971 915498614 972 918330051 973 921167320 974 924010427 975 926859378 976 929714179 977 932574836 978 935441355 979 938313742 980 941192003 981 944076144 982 946966171 983 949862090 984 952763907 985 955671628 986 958585259 987 961504806 988 964430275 989 967361672 990 970299003 991 973242274 992 976191491 993 979146660 994 982107787 995 985074878 996 988047939 997 991026976 998 994011995 999 997003002 1000 1000000003