1 360287471 2 526059563 3 132328627 4 862794349 5 573834187 6 383418793 7 879307021 8 154089149 9 675092447 10 509244761 11 234544243 12 907774499 13 744992069 14 551702761 15 860626133 16 331384583 17 297606737 18 976067371 19 113200709 20 704723069 21 108657463 22 865746377 23 112523897 24 695369677 25 536967707 26 468644549 27 931636889 28 300987931 29 482208269 30 509443117 31 173012381 32 819706841 33 397019837 34 648042953 35 981945581 36 301756717 37 181881593 38 988885193 39 879228499 40 444363463 41 235304369 42 146314093 43 640546253 44 690888707 45 887070167 46 635490613 47 375051011 48 510115747 49 965521267 50 154688957 51 788023519 52 419957777 53 366041699 54 622684471 55 471625607 56 921236677 57 527867539 58 697096409 59 722836489 60 486363721 61 740238893 62 832627793 63 318641551 64 186415519 65 324425869 66 869829469 67 982946959 68 695930801 69 639644791 70 479101459 71 496791287 72 128740687 73 858671747 74 573205681 75 220001137 76 455606881 77 256613527 78 135278369 79 836951177 80 951177883 81 863874439 82 234281899 83 818997077 84 178392803 85 425863987 86 258639877 87 962953741 88 703023647 89 693811513 90 428123149 91 281831521 92 818315219 93 527944951 94 610852639 95 398139559 96 981395599 97 955990067 98 559900673 99 482922443 100 829224437 101 718462457 102 626039033 103 150974827 104 482798777 105 827987779 106 886778227 107 138360577 108 360577297 109 561190717 110 856647097 111 988218559 112 862002353 113 220005031 114 734392073 115 392073211 116 139080329 117 936344797 118 783793421 119 632399149 120 239914907 121 580489669 122 896690629 123 669062951 124 119432473 125 943247309 126 432473099 127 226029983 128 538155841 129 718692553 130 961294603 131 573158029 132 290958631 133 458459251 134 459251269 135 465572483 136 459937691 137 691704197 138 171016343 139 101634349 140 163434907 141 907696423 142 642372229 143 189087401 144 543663271 145 712549639 146 574760819 147 206602433 148 390397177 149 719518069 150 502260149 151 149291011 152 605651183 153 842242201 154 542649463 155 426494639 156 768816359 157 136011649 158 995076629 159 646005851 160 907615321 161 699251827 162 275687989 163 254935649 164 379804583 165 120162437 166 137285593 167 707416181 168 696724949 169 499254527 170 452790337 171 361626589 172 658976039 173 767413973 174 359441023 175 715858733 176 897571211 177 105002561 178 149239151 179 946342841 180 634284139 181 662818811 182 256425347 183 470879089 184 879089137 185 722828611 186 861151591 187 254406337 188 598267609 189 170187817 190 306067213 191 360460003 192 417185777 193 857770141 194 180606443 195 533160877 196 317444081 197 422975599 198 706553833 199 441475631 200 414756313 201 399972217 202 461709289 203 622607407 204 147378233 205 359475643 206 594756433 207 564334129 208 485023573 209 573221459 210 142168487 211 878721673 212 787216733 213 512722373 214 805371439 215 714396127 216 930387727 217 792868409 218 684093253 219 311483351 220 500478271 221 640260353 222 305583737 223 971928047 224 767069777 225 184877047 226 263844037 227 638440379 228 840363893 229 403638931 230 638931313 231 137688841 232 102681121 233 886059667 234 686274079 235 791285657 236 128565769 237 389962421 238 996242183 239 312965879 240 447634703 241 482860837 242 656803073 243 769634953 244 532884683 245 468000151 246 777519329 247 775193299 248 360871583 249 871583483 250 626961661 251 166198057 252 454395301 253 495614857 254 614857249 255 572492573 256 353373253 257 546658859 258 466588597 259 441370331 260 584072443 261 407244323 262 972531983 263 192821711 264 382031981 265 684941273 266 314921879 267 187959271 268 866986837 269 730220047 270 753143381 271 962850611 272 132900259 273 837093419 274 648805669 275 765620627 276 206278463 277 490346293 278 116482411 279 824114969 280 555390113 281 943316681 282 876069611 283 386272553 284 627255353 285 535388309 286 646809671 287 281493907 288 907222601 289 722260111 290 387317617 291 108846343 292 634349983 293 434998351 294 376257767 295 257767571 296 201962623 297 234162881 298 173254777 299 365653903 300 474137441 301 441921013 302 133617299 303 856948991 304 294785807 305 103967819 306 195942983 307 367955149 308 966364489 309 655929481 310 785178403 311 773326247 312 265255213 313 231060979 314 159936001 315 199462379 316 434210687 317 134973469 318 624695861 319 984178079 320 547079017 321 513186809 322 368275631 323 962358563 324 563126183 325 710165129 326 129666367 327 880204603 328 483649591 329 212810419 330 342284951 331 995960531 332 531446053 333 885289729 334 765987601 335 601666781 336 932372453 337 372453857 338 277178483 339 181294559 340 276713779 341 487586753 342 614076119 343 119311259 344 112595851 345 585126557 346 575973457 347 345730153 348 642630767 349 767985443 350 679854433 351 346232527 352 572005303 353 689465599 354 452878051 355 191097343 356 958265447 357 426325321 358 418039943 359 895171709 360 266203031 361 557769637 362 560544571 363 445711337 364 557441603 365 416030837 366 242587223 367 287083799 368 523364087 369 874295911 370 747453419 371 455842679 372 477560879 373 564063413 374 764491573 375 915739001 376 725919989 377 649505147 378 713793991 379 942906163 380 423115349 381 394466621 382 759878813 383 788136491 384 881364919 385 833287937 386 793771571 387 416426783 388 678309949 389 360431317 390 604313179 391 915754241 392 157542419 393 139230617 394 104089409 395 996608947 396 836299367 397 729846421 398 910798843 399 955526227 400 751862983 401 379378607 402 786072107 403 781966511 404 819665117 405 653602591 406 445271657 407 452716577 408 614560043 409 562708609 410 943244261 411 225648893 412 696550091 413 425266847 414 725949143 415 259491431 416 344608427 417 339762209 418 901626983 419 162698351 420 245140589 421 780735457 422 496653457 423 644832499 424 665639411 425 941148961 426 204284299 427 102582911 428 856451303 429 842926741 430 776558417 431 165263207 432 876845701 433 701782303 434 731016581 435 870148291 436 291674197 437 281490241 438 842696339 439 398856841 440 841681003 441 387238921 442 212364367 443 557332801 444 280182977 445 798873659 446 761619893 447 144805571 448 599051987 449 378548323 450 832370687 451 237068701 452 309189191 453 918919181 454 128032327 455 392219687 456 283405169 457 761467397 458 396048253 459 177292613 460 292613543 461 449728459 462 497284597 463 786771157 464 567030787 465 101472799 466 555083317 467 317078239 468 390156419 469 883801327 470 564885533 471 482069713 472 971372621 473 162237679 474 767904149 475 483518813 476 188137463 477 374638871 478 544767623 479 476762357 480 914530327 481 705855677 482 749481373 483 385762823 484 940056653 485 998145877 486 343586311 487 596436067 488 760902217 489 688354813 490 813164399 491 439974377 492 836524223 493 642619597 494 449064767 495 677918867 496 918867203 497 672030641 498 138466487 499 183829799 500 999018931 501 101646641 502 460320853 503 540581471 504 213664081 505 662193193 506 386162383 507 238360691 508 383606911 509 819996523 510 199965239 511 945063323 512 504965173 513 571898969 514 302885449 515 290527631 516 514066229 517 229171223 518 293758061 519 375806143 520 399348491 521 799357673 522 993576737 523 557928751 524 697338197 525 466848337 526 668483377 527 730006483 528 382602211 529 552212467 530 588727333 531 402686833 532 581699543 533 519572159 534 637361269 535 596424217 536 424217659 537 217659289 538 896862383 539 139754473 540 625506803 541 997001729 542 700172939 543 939073033 544 820770697 545 986477417 546 780687977 547 806879771 548 771659111 549 343556659 550 566595427 551 194408833 552 441370823 553 413708233 554 391788611 555 822865753 556 846214073 557 173662549 558 221503351 559 647185387 560 354822289 561 228916663 562 527857853 563 785785393 564 606110249 565 802273093 566 363674021 567 674021351 568 643517321 569 215470109 570 154701091 571 788236367 572 368311873 573 562755397 574 755397683 575 397683401 576 957506243 577 439964527 578 964527257 579 220508089 580 351290231 581 312247597 582 441056783 583 361870877 584 877172333 585 252149507 586 112162121 587 627452291 588 291612889 589 161288917 590 814160639 591 597535039 592 412476451 593 518508091 594 809163911 595 391145929 596 145929607 597 563442043 598 335447209 599 914060629 600 747575977 601 595357097 602 222409219 603 224092199 604 701292607 605 260780197 606 629233681 607 233681543 608 431249941 609 338548909 610 686851307 611 642428191 612 424281917 613 420855823 614 936649849 615 366498497 616 674118587 617 671855309 618 185530931 619 319756081 620 822937243 621 293724359 622 884445701 623 701001157 624 356126321 625 599326463 626 176052287 627 152410021 628 195937349 629 166155673 630 461954063 631 954063697 632 616858273 633 341222171 634 588587081 635 544642177 636 535227389 637 232374673 638 764554303 639 151296121 640 458594443 641 859444321 642 150749051 643 637996487 644 203809769 645 497565493 646 691892389 647 309054253 648 129491671 649 650313283 650 313283521 651 495813407 652 581340713 653 132180533 654 888281393 655 259509721 656 721433149 657 604248511 658 145884283 659 687134311 660 542470417 661 247041733 662 233693821 663 821660107 664 601070287 665 651938143 666 844532639 667 504657493 668 262228843 669 363835019 670 835019371 671 805403821 672 488708317 673 594930209 674 456967859 675 859585183 676 183934913 677 408842743 678 287080433 679 280913299 680 913299307 681 248240911 682 116951587 683 169515877 684 903525773 685 525773459 686 593824823 687 248232053 688 142318529 689 253126693 690 970994693 691 709946933 692 656189797 693 350431513 694 504315139 695 832803187 696 318786707 697 259219733 698 986552141 699 163677127 700 677127001 701 568975961 702 383721577 703 157726831 704 502020877 705 921820007 706 329027603 707 965498921 708 803845633 709 337233119 710 943446247 711 362420159 712 556889899 713 255433729 714 298073561 715 699861101 716 720966007 717 868425049 718 620280223 719 986429173 720 291738367 721 303365567 722 441099691 723 969141827 724 435853189 725 847292909 726 468559163 727 855916379 728 676598399 729 183120023 730 147646451 731 426447821 732 671326697 733 671446177 734 111414983 735 379091369 736 706497637 737 430544929 738 921102733 739 337467001 740 871524083 741 356615221 742 106649401 743 670141943 744 933359731 745 973109537 746 515382053 747 382053383 748 338326511 749 687529211 750 220265681 751 418260827 752 900024079 753 616743773 754 125342029 755 202918139 756 898683901 757 576244351 758 551805547 759 338118863 760 118863817 761 868256009 762 560092739 763 776669563 764 695633501 765 790272487 766 595883669 767 726504487 768 284530109 769 453010991 770 837683159 771 120244517 772 540185213 773 802901249 774 972818089 775 180895021 776 160430923 777 562874591 778 448724413 779 813849763 780 497637971 781 119639279 782 794106961 783 300636443 784 419577859 785 333484633 786 494652923 787 875139337 788 698024557 789 436190501 790 145875923 791 566883769 792 431252321 793 252321353 794 321353093 795 243969149 796 966231011 797 487677299 798 299160941 799 627524237 800 355499267 801 567545287 802 310574933 803 300601979 804 378819263 805 933875021 806 387502163 807 193891441 808 914416277 809 960285941 810 199134293 811 374538503 812 314163809 813 412750033 814 275003353 815 634602169 816 216923507 817 921611101 818 828189539 819 676286509 820 718262117 821 262117003 822 140003377 823 414909323 824 149093237 825 294205523 826 770560093 827 560093063 828 913481627 829 458607689 830 309703301 831 722771087 832 705649129 833 278244203 834 244203341 835 645996823 836 682369661 837 611887841 838 446299877 839 487375331 840 873753313 841 533130181 842 814276391 843 796519907 844 165277661 845 480280123 846 801234493 847 308948279 848 829494577 849 449312077 850 493120777 851 199560509 852 708652339 853 358964057 854 153174013 855 116404777 856 481263907 857 770305177 858 305177903 859 123934091 860 153392401 861 422065097 862 978108529 863 764553247 864 324752707 865 936642001 866 947457023 867 822637957 868 808631893 869 981808117 870 818081171 871 645186943 872 483366019 873 938489197 874 210394663 875 180134351 876 134351593 877 930442853 878 123852059 879 347636231 880 630750691 881 663548917 882 882964741 883 953370227 884 277836283 885 977992993 886 896978333 887 484244107 888 232495841 889 981064673 890 468937543 891 543016787 892 301678781 893 605404361 894 404361871 895 436187183 896 633026899 897 586235821 898 582145643 899 667337243 900 230915771 901 928270391 902 966426911 903 691115533 904 115533359 905 685782817 906 635874847 907 255098479 908 509847973 909 275460161 910 546016127 911 661480163 912 148016387 913 944054827 914 440548271 915 362809261 916 125675071 917 496707763 918 469000163 919 729730801 920 431325347 921 313253477 922 325347713 923 786075229 924 752298137 925 522981373 926 912677281 927 205242899 928 242899913 929 289991371 930 299912741 931 177149279 932 927960883 933 279608831 934 161908949 935 838494793 936 566830067 937 585912013 938 167811041 939 413444411 940 110309033 941 488296909 942 202624771 943 427962259 944 358589767 945 240474397 946 688388003 947 459816089 948 469838377 949 460400429 950 241401907 951 754681607 952 977920579 953 838953781 954 847409929 955 222654727 956 238548733 957 854873351 958 845842433 959 219128627 960 662670991 961 913190237 962 319023703 963 370311779 964 927866231 965 231126613 966 266133767 967 767117851 968 732543731 969 499827899 970 834983873 971 235456843 972 567114797 973 973065077 974 197310881 975 973108811 976 115751677 977 777005071 978 635460191 979 460800451 980 728504641 981 969949061 982 632434541 983 454128229 984 822996827 985 132862451 986 710564957 987 105649571 988 283769357 989 769357009 990 700995419 991 151033187 992 949854397 993 618128557 994 622654129 995 800408971 996 261564643 997 321595609 998 292580611 999 140918881 1000 208858207