1000 867 298 45261544 494 298 881075881 733 867 576986308 548 733 205525565 232 494 443015505 650 494 920615656 28 298 239708789 665 28 654041057 745 494 65487207 438 650 277986654 775 665 253636294 819 775 311608405 991 494 117485826 906 28 622796216 475 494 597641057 249 733 789638685 194 906 763418244 676 232 689835098 540 745 801597746 503 438 632371975 799 745 143318893 222 819 602357809 116 494 433014681 65 249 203090703 145 494 801548685 956 438 850012163 772 28 376049235 223 298 332179197 19 775 984925267 678 867 295319106 328 733 243710355 186 678 784754663 630 328 275942326 472 540 958677334 9 28 983727058 786 249 246557662 812 9 534445167 801 222 320930490 447 867 269163631 864 494 43799889 376 867 681234162 851 9 259338902 524 376 119538012 440 249 206096450 611 630 767341694 133 232 387521274 57 194 163966900 350 676 607356876 909 611 977592775 114 611 605561722 284 775 891532101 768 447 514018282 387 812 956186771 621 650 619296226 403 650 743849905 640 851 780657960 326 440 934535916 27 403 141926646 974 650 716938199 239 812 770020315 716 403 635561965 388 650 116322201 175 630 736329266 744 232 817224448 881 145 158897845 304 328 968848475 664 388 347091648 87 650 858809939 229 326 794959802 492 298 797264182 459 772 523890529 766 249 306473334 311 492 396892007 499 376 911960154 436 239 63192125 777 175 8875585 853 472 750373225 831 19 532223809 215 786 374597680 235 664 159693532 391 229 360456775 761 744 220218168 168 524 882378051 91 676 932467460 861 145 632835549 820 716 621592873 544 881 303667183 986 503 678401957 868 766 914250308 920 403 119380306 52 229 601413889 431 447 394340955 482 168 226449008 994 906 695418876 950 867 226550157 137 503 626837507 192 906 238047579 873 819 693937111 681 145 100525879 782 991 819129808 581 611 109941901 791 194 471650103 445 665 63523660 82 133 596286118 105 194 509526049 360 881 649820395 50 801 121571777 654 782 97971112 135 388 29264166 261 867 476505161 668 65 210849121 421 881 71621690 22 494 922812477 379 499 972557856 170 9 591930737 491 640 561816420 854 19 378541765 455 27 72299462 79 867 93895581 844 376 871582496 726 812 475179177 15 391 460037537 855 459 776336065 823 215 291908548 35 630 734055208 429 873 492525944 109 611 424881524 259 379 679054431 85 831 542701927 406 812 55496656 537 782 739514275 41 406 304652597 481 455 433377493 649 492 484639497 692 650 69131774 61 482 321960450 976 786 735143654 898 854 607957808 825 350 811243235 271 50 1784204 767 786 178486890 268 360 358627251 570 259 532080474 244 745 918804904 151 851 431623657 397 22 629616384 101 79 140455709 11 654 311245346 507 799 434762873 327 376 809951305 720 611 615778040 32 429 983570475 378 726 793672624 209 429 367567639 408 766 19580152 993 621 501144556 98 868 302174169 602 192 297000606 143 986 515553617 742 406 511660333 662 761 798876554 363 664 914576956 988 772 705876870 897 621 441313294 653 175 336597212 642 472 222518669 198 209 739655448 54 133 976133460 711 507 526678819 916 991 749008947 162 438 740507284 81 766 300130782 985 761 768726835 634 906 309425667 542 209 189463705 208 711 93777658 978 868 206734106 828 897 477299767 765 79 471087338 671 581 134888127 780 311 650953135 159 232 574908845 124 406 755770991 301 820 902376290 303 170 841666027 953 403 701363858 468 950 163525633 501 801 828305013 267 170 244193180 655 744 581403955 658 133 981835162 697 772 903547605 743 655 657066469 616 445 655584905 708 825 254168275 849 828 523625371 562 22 925588175 262 726 666083685 682 544 386608493 39 57 113738177 117 301 923980217 959 831 413575472 86 387 355667315 911 162 856022069 970 268 599281571 173 537 576763619 580 668 531478954 177 653 596482172 578 765 994795461 723 634 478303100 147 911 364590419 228 186 193945511 999 682 292176295 46 363 474168447 103 209 105088081 344 192 941449586 33 642 89894083 152 986 871482714 608 499 628762203 270 726 701346934 706 270 37195139 119 777 206657774 347 767 817247378 106 229 958035055 670 103 933142775 126 347 550253657 428 194 462775921 764 664 995773556 607 159 916201850 398 326 587084539 169 235 472402536 21 494 342128685 346 956 489520055 756 733 805717586 824 109 396664325 779 28 865402209 183 101 885567205 18 630 32981013 859 183 695886958 55 974 92404219 638 61 803735113 981 649 962194879 341 268 274815616 869 378 254913778 874 175 272434699 487 101 622541043 887 655 913172446 383 103 542213408 66 861 211146249 469 126 908475756 571 950 690016045 150 981 40952859 891 440 968274528 947 764 676980822 561 976 950982590 132 239 547424085 45 232 556571069 72 271 410426529 619 304 361206678 1 777 521928719 703 562 852658558 841 431 549666219 528 239 339056228 949 947 526474912 730 561 218916821 305 232 32989543 910 743 896275207 609 363 998595772 370 681 11752147 734 124 7143288 253 801 964265163 467 580 520860335 478 11 567733340 813 855 870847192 334 491 948076752 382 703 314289224 865 708 806314223 454 861 135238010 987 813 157048468 817 19 631918730 704 382 271711191 291 874 228756232 938 475 784399879 546 209 432415722 174 682 913011196 2 429 871016670 411 650 529990497 587 398 433263805 800 887 887333507 792 608 183834780 515 638 886306230 490 678 58729951 597 994 566211291 141 66 170184024 937 578 974632182 352 431 710132492 290 562 700864585 872 655 762051728 962 767 373071144 236 328 549772766 796 734 668822927 230 403 354424417 302 208 463356979 996 57 492626389 157 524 601142137 349 328 905941927 139 438 27049 702 370 565811111 815 581 746754653 879 39 418309549 131 742 367219125 552 408 103437615 958 692 946177052 111 864 236594799 24 831 60502388 806 571 938411836 535 702 876783860 821 716 320970660 476 291 597843065 848 239 787923305 154 103 198163462 547 440 785685228 197 772 191420938 359 780 26406269 913 467 372197539 600 436 267371304 543 169 963170005 523 820 584869935 753 1 863305963 632 891 617136094 70 524 882872180 534 239 649011946 47 692 395512137 840 209 378635343 639 855 887413844 939 101 117679594 713 61 754809384 883 632 105239970 560 235 308237361 908 664 981883481 623 761 490161515 353 561 557073169 802 18 229848657 969 259 56237979 659 676 351787847 402 244 119176056 732 403 373909474 661 864 815132056 276 524 537050381 808 949 267278005 936 869 532210472 210 639 647707638 563 98 963817695 842 906 292160597 615 429 531490561 585 849 342493077 292 808 251158467 247 154 648726257 306 999 185768729 977 145 287992976 737 913 746396902 641 639 543435274 566 327 615692364 557 383 376747947 456 780 652890982 901 775 247959453 963 753 659038405 946 639 524352772 983 534 621048599 915 2 426839036 96 398 493493514 63 938 461838214 399 585 907021900 921 638 52413515 731 978 365799326 590 135 764268613 329 920 857955314 188 742 163123960 827 398 369002381 354 939 381690992 219 854 613441660 923 143 80338520 120 817 336877219 269 772 312874771 118 406 51027670 860 706 344042885 144 873 405784498 532 232 25986767 902 649 621782547 567 808 781560995 990 959 486284063 75 597 717072097 340 262 996878833 884 581 172786702 338 676 893050328 576 429 179776547 778 602 910790117 62 359 906643974 60 428 912559541 16 406 809242776 554 884 920189184 178 621 929202151 944 91 838415058 393 487 629311716 519 168 782485689 205 249 313650732 705 560 586079482 294 571 359113286 759 801 934108475 460 482 616468835 918 723 512111114 337 692 370782505 905 341 338358018 374 828 507535229 568 923 954892812 58 301 484218412 64 950 173685403 310 990 417518083 4 996 344374261 886 391 6484990 233 4 880409013 709 303 622042573 684 58 509118652 529 944 111169748 166 382 133502753 750 11 997419513 227 301 460446575 161 658 653990582 890 978 833731102 158 235 210984927 441 61 883862601 115 261 675320580 470 578 970302806 809 731 175726961 718 806 320400236 435 383 903337451 463 658 753503439 155 600 47192495 635 186 449058528 163 86 452904194 365 247 987665978 356 921 617650573 351 578 156653504 758 470 560390647 48 481 823060030 527 169 553504093 694 249 582133401 559 780 973104206 876 341 815257257 807 455 699475433 437 399 401197827 430 638 255956913 195 842 409026673 843 567 288394704 818 876 566608964 30 82 463933217 423 632 643487797 643 387 633089982 880 222 829064689 539 898 998087623 296 983 313101967 966 161 389302552 196 2 917528483 627 363 120255809 448 720 970942477 160 503 752420990 29 374 297947520 31 66 164853486 520 155 724923103 172 920 629809094 43 890 930315021 484 115 392369698 679 718 58233922 738 338 236683981 138 15 3263017 926 616 137805060 770 921 597539441 617 195 847701430 71 963 52752260 803 456 545482553 740 481 985619657 930 41 115718196 793 844 907859120 410 807 441009979 108 585 69546959 13 31 231381845 424 22 452422615 513 46 345002326 526 750 237017065 875 469 278629128 748 859 608678845 7 906 263488864 933 999 782021004 505 109 675416083 595 435 628904775 710 828 587374217 583 494 147298748 826 864 502347623 856 981 180880838 626 21 289696497 367 133 341026537 701 117 954194051 696 990 355013530 480 702 816395568 136 902 300699182 997 60 212042285 102 391 429664219 488 72 240998200 100 906 453299920 629 828 793958198 755 793 449023712 99 581 577412137 771 57 561205553 975 208 473668619 315 490 269426585 395 874 659939911 25 55 325684337 992 552 546981231 104 247 898240882 618 177 384515884 695 344 777026980 832 997 781287598 272 799 876085427 837 552 961225840 462 581 403343384 369 526 570314891 17 111 986044729 433 370 330689361 917 806 938878989 797 492 948834932 836 949 550779227 413 608 369620537 392 360 362168549 415 723 386854464 725 890 406648164 620 920 805057431 935 571 431264425 422 82 922763480 512 18 106095568 474 695 320354981 804 523 104895007 314 640 228208632 307 205 362337728 252 902 163404036 358 45 61219323 164 507 403101506 752 284 667182103 589 413 481413482 432 21 990021508 12 397 616359188 914 454 617430103 979 786 116496242 550 626 555884154 418 567 609352850 722 566 562376458 76 354 885106481 405 970 371354245 345 547 140364945 714 393 516913654 179 345 620724850 321 777 24427223 588 235 249000631 464 170 925845564 221 874 487397420 200 306 552051952 368 918 677200629 283 886 957616225 231 186 954674798 603 589 271896586 483 359 810823776 835 456 136253747 746 901 731815798 489 239 524490363 128 843 482156878 610 884 188923847 717 977 987512584 277 659 680339451 213 98 322758298 871 869 775627009 739 435 833608193 652 523 407395331 6 568 618410343 497 717 570024407 599 676 146193598 322 25 163110283 266 379 280719604 53 62 981115338 814 430 630308502 502 249 526482599 180 481 585089064 877 640 481692915 265 164 519307797 688 345 176533303 805 875 249487084 646 739 786058278 846 28 899569314 386 831 11190625 774 658 203366178 193 859 814717207 574 865 992928475 686 524 555858901 724 546 43316074 508 18 209099018 264 476 130189849 735 748 539907843 458 222 74289565 493 748 695203308 525 819 254466061 822 252 379751571 787 723 23015733 389 618 10050505 943 881 641887646 798 208 999304160 509 711 955488932 254 618 143442340 514 926 369690565 288 713 755730762 788 4 744834980 736 464 741803582 657 353 263885958 904 986 433037187 555 269 460352851 146 734 22265738 707 304 651774795 573 787 107563142 625 581 585376752 698 46 935332924 940 659 102292876 693 532 412380857 331 987 624073787 954 777 458607748 312 91 584061350 362 327 505136194 190 192 986292740 989 136 733248415 948 938 593335068 965 574 772478443 518 290 15788935 323 821 736679549 73 897 590344290 951 908 684123677 729 262 923077655 90 585 274366689 400 271 325972812 396 840 377217636 669 791 518538633 651 555 484485771 907 722 67861816 769 16 174980618 372 948 171260235 295 655 673921024 281 668 202445695 536 72 736926558 785 803 773918081 839 831 482977402 260 891 224389553 882 581 851217821 240 766 66997922 553 232 168366021 754 111 352774836 945 732 376360281 257 413 179182028 790 363 617452871 715 938 118098238 148 646 684329795 763 539 74316640 450 406 147828782 181 722 737306998 299 986 837877152 952 956 817032836 258 30 36868729 211 470 335345760 250 310 780437558 511 597 591303740 279 124 409439173 26 933 891216433 20 393 893005553 538 853 69481077 242 33 80090120 457 914 822766718 417 846 730835384 342 304 42371373 680 538 675154492 171 959 234051641 185 478 18404783 234 722 725231179 982 266 168268838 202 875 263203972 313 800 523869511 471 109 870134791 214 898 254164923 866 538 564327420 348 164 547811454 107 986 177559024 789 417 473368826 572 686 942302544 517 866 472944318 728 192 62528662 593 482 621546823 451 349 824464100 495 985 674019706 251 985 740298633 77 428 336966931 67 195 422342033 377 481 567884868 207 518 542888495 551 812 594946590 899 979 609367412 521 27 573343612 380 440 210476745 416 616 18410268 286 629 148674669 319 81 2452815 727 822 465410591 274 141 260704588 624 337 14374176 407 382 719892931 687 851 592363696 968 693 952582227 545 527 694545416 122 421 7565008 206 756 487685241 324 72 789304186 245 578 305256770 56 778 790328452 371 98 935634642 84 323 923972145 80 290 845172972 833 629 7321105 10 497 169346379 224 185 297655652 663 956 794756386 1000 470 37313948 343 268 611964954 852 378 819337918 834 454 170476028 781 343 586755907 510 4 439637363 238 939 963061833 142 671 393145250 942 563 607850194 928 132 653529327 381 249 307968582 156 11 834688907 605 965 359857957 903 337 815035221 516 901 23234900 673 35 914597869 586 481 760124024 275 503 809657729 656 77 300606332 810 748 950249730 412 467 38599776 922 707 151035359 647 803 714497818 606 508 445286360 8 389 330464285 243 22 874912385 317 490 170823488 691 586 666537581 38 173 212578147 375 213 166862470 500 661 61730379 127 265 568140451 579 18 541821069 549 315 690426457 123 727 489152805 134 532 891914809 967 30 161967457 394 758 808397466 541 879 490586997 747 753 14136387 293 25 226884777 68 615 79493615 683 321 767877510 201 67 735710946 390 910 47554693 857 761 70677834 504 164 342912821 784 13 86872779 285 756 107593319 318 936 603100445 420 398 214512337 465 306 799418591 225 168 834833983 384 555 710490311 980 686 819067288 452 587 426007827 485 796 356244731 248 744 599880971 361 881 704737904 776 597 600294894 110 438 588654489 751 635 887963477 409 85 154758225 628 338 667300365 74 448 33174910 165 136 405563475 892 413 442845094 924 627 651986344 59 832 290572588 125 208 865309025 955 891 371623247 601 922 660235103 69 763 134882552 741 430 969923638 97 27 823292881 995 647 742517625 453 639 970631187 89 243 422905907 598 509 64669481 184 899 447210743 191 831 154886622 373 619 693614815 88 864 882081913 932 284 374935417 316 948 427875397 278 995 109048387 129 708 553034498 92 318 645145959 256 128 572648593 604 196 528013550 699 124 373628404 984 274 456556632 220 918 273202076 355 646 832288102 577 728 388677878 42 701 409249831 443 729 23175782 44 504 900904992 309 279 13054192 961 491 695073118 894 268 301540250 565 359 409426930 845 319 106684728 712 810 485880293 176 924 71432814 3 861 227655033 896 324 603741631 282 652 161264993 667 92 894158673 496 769 789796025 645 423 319348996 153 670 902982498 357 119 632643420 888 752 421605186 870 581 395045365 473 561 449825449 530 209 887362873 325 846 413367774 78 284 677964472 644 362 492471230 927 251 430876241 556 751 173452110 677 950 267818915 660 828 593839680 442 808 811230803 971 679 350748861 762 782 556156330 773 381 71830162 246 306 686799976 94 916 124428676 339 920 40659746 675 55 691409027 929 396 154376416 893 323 342899733 121 883 717822649 366 523 747547829 241 301 824149254 749 337 784577793 308 27 205408840 757 121 352287563 426 755 540713024 889 422 415497916 575 688 276536482 140 684 524635410 297 121 93062861 5 12 357284272 95 59 429261408 83 872 895356569 584 290 41623131 182 706 262822918 385 481 281021658 273 680 712397635 36 944 354280622 427 329 914197722 203 139 124439541 40 873 587035330 811 159 439962821 858 800 257955062 333 706 270490897 564 36 865605277 199 896 340647961 216 814 523977051 637 554 809591757 795 928 969552694 998 995 32658051 237 825 478768373 690 521 928818212 533 153 408451839 280 29 414567905 479 488 562278000 218 756 624945452 847 244 174504659 112 601 91664032 964 473 673662182 531 811 273026414 23 784 385001238 912 155 266015682 648 232 244856249 931 316 134694689 506 806 106500531 760 227 334330689 498 105 773349684 34 714 624308783 434 697 287281161 289 163 324554173 895 229 256855018 335 938 925192163 425 482 213109804 719 488 744633550 596 101 29885940 263 694 851291099 592 391 555932991 226 451 289036494 320 980 884184169 486 15 662064967 700 780 316854315 614 902 26742644 878 949 709305417 783 426 934146437 187 271 377004867 149 893 322491812 255 35 645497136 336 67 97115624 919 756 794825747 217 990 736751561 419 560 966157197 404 553 544407397 838 395 400496732 167 178 274708387 850 114 915329146 477 188 692029937 522 185 572988286 449 43 395991296 829 985 705550935 444 71 759063570 113 429 711701296 960 774 335902826 332 371 996977921 558 911 338996004 594 436 507131737 830 296 464308268 794 191 317180965 287 877 900039972 414 760 546594336 941 808 706209716 631 673 449310765 49 749 831450819 204 95 513524051 439 809 317370655 401 65 20020078 816 525 649394893 446 572 640127183 613 290 757310138 591 681 27934608 862 995 446009394 636 291 444860907 972 371 155252216 925 264 688353509 900 246 670237416 612 859 869150507 582 168 492228771 461 436 483266723 957 351 579507904 674 532 126045767 666 382 551471705 300 52 914819506 189 312 39825738 633 755 100739303 689 673 394647621 973 843 214205369 330 4 389931879 130 198 585622262 934 311 826395723 885 331 421016053 622 952 453209168 569 880 415233380 51 67 157419933 685 262 372830715 212 354 154464729 466 844 392516732 721 67 46598411 364 874 31556343 93 110 963555107 863 622 947875898 14 534 90155625 37 236 467847719 672 341 81166219