1000 10000 839 179 246052087 178 972 293139868 888 336 928567967 777 775 210155573 889 488 963657897 995 257 638804894 237 13 203799781 400 638 336388716 171 184 273077507 508 144 817586631 685 85 901553565 805 67 941349195 956 823 57896227 616 307 522775474 749 975 81547797 708 237 765081801 530 116 764646038 120 16 600451786 782 473 398601331 407 274 724775880 88 991 136236225 604 148 307114680 994 336 769012736 844 383 405195266 390 267 401422025 738 625 774709571 332 410 962409857 13 250 4735472 506 904 551955411 360 989 868211173 468 622 630521104 270 842 614673425 21 196 955111693 386 101 911037855 671 788 997419964 212 398 691416002 190 690 464849889 851 374 919867830 826 786 850950846 523 996 62222774 34 686 505725396 294 53 608038621 401 534 481474676 169 628 27298203 651 73 890594490 156 437 892933805 578 654 310436858 38 889 226579745 224 175 917493995 597 775 848397065 136 281 89142344 516 332 652673425 316 957 154067168 897 503 265499538 42 122 427510667 830 849 741195319 535 316 127408696 554 982 559658048 825 860 614716366 780 312 279479628 690 270 209520487 249 264 878517165 908 84 272533573 70 808 702241837 812 526 598223427 232 968 725791926 599 144 970870338 218 452 634741858 991 523 258363939 816 967 76690061 946 859 418211242 265 511 469783063 456 135 233978857 25 658 392750850 780 836 889869478 496 253 616153095 680 66 936469241 599 590 716280415 381 329 745316211 53 677 146905114 583 953 859368849 75 552 3225243 364 746 42918959 708 302 647439874 245 253 60756336 390 988 817829364 707 282 231280177 815 776 799671145 574 512 346165874 102 349 276282336 349 479 437126319 818 130 470497859 407 882 118337501 228 701 135577244 923 127 961251382 175 878 226218311 303 646 925978828 720 562 560932859 918 303 996439491 317 860 181009574 14 126 474482005 408 835 170796161 6 862 268520821 613 343 342582082 810 812 766742437 695 535 371262548 185 567 995443241 570 152 442009993 361 704 207750541 180 542 312887166 835 727 15982355 700 847 505392350 134 363 585067484 765 248 419746007 452 905 426437952 58 45 353846155 601 965 155845951 981 881 21507520 478 712 37594483 556 336 74056745 584 564 797044422 644 692 45133262 698 654 609301399 884 398 608994085 875 109 772420088 185 522 690186715 731 349 456341501 745 865 963685191 887 9 602664858 196 644 903998886 143 802 590210206 871 43 665957593 516 792 519595893 438 464 117194079 241 771 91092115 800 500 293437454 262 684 52317642 125 1 618789254 607 437 334932965 482 893 433102768 945 665 650057193 85 191 673065978 799 708 35504244 71 81 261140219 817 956 208904066 472 901 760196612 342 809 648832403 124 518 797697481 556 136 224026432 495 197 440623310 54 592 606745858 139 893 340392759 675 771 600425239 980 215 924333013 435 772 934710143 671 386 833257996 911 946 983474873 999 255 401833911 815 837 780064337 265 423 515721126 550 78 405093719 310 508 371409959 480 25 190116141 689 25 483216177 162 552 77655214 575 803 18453299 692 753 539217892 626 901 211810954 644 483 15963887 544 704 97331408 270 992 509955178 728 319 18602516 240 683 817580403 76 605 455688420 608 410 824529885 186 431 796123927 126 1000 822284145 625 317 619393261 794 274 809978167 235 869 427302540 100 722 26928985 317 383 528843046 420 695 885904922 104 205 909654960 273 748 610950126 566 207 84937199 19 866 301059346 222 467 942065098 474 574 290254850 826 259 585101776 416 166 390522707 988 16 599109101 83 612 495672539 382 905 28305619 90 376 57162727 507 571 437655127 975 245 597067761 184 587 307965231 293 340 689844890 499 862 611198926 540 905 234575964 633 808 269237469 843 254 770753748 819 410 529467268 915 919 344752976 396 296 278770289 747 73 698479731 753 705 32441435 879 977 384710127 696 539 641045434 974 581 776822701 76 942 95650037 982 913 99033003 472 867 345290914 410 248 679988160 843 942 524315213 224 881 844353275 622 353 242965360 85 617 982475963 509 658 45147058 153 414 156167536 670 840 280468170 690 152 678514319 159 737 140726013 835 622 989837846 68 835 125230254 894 111 946436865 120 787 854587441 689 197 597956224 91 993 419031175 965 389 360152236 596 35 879653721 620 575 583397407 710 530 949553291 739 672 34537603 5 638 214115022 471 405 187946555 847 220 671096803 7 789 180532134 411 438 701422560 899 750 356066898 45 124 326187894 512 157 997290346 595 968 745855185 774 800 662524789 960 566 882957386 244 256 415471173 108 267 393112955 638 104 875405307 624 354 635047319 766 194 589383344 586 456 485460899 219 367 766742171 727 169 433335903 229 855 445603975 81 506 691297397 242 934 945939346 651 166 605256883 259 751 999843969 871 879 233509755 892 802 76048656 671 450 435236132 306 257 891604634 919 332 880500626 698 171 22953473 926 693 117316923 86 438 800224952 248 417 648996736 277 839 350118470 262 660 55266907 418 456 274785873 519 748 463289949 356 239 975997338 420 504 997620163 499 118 657984924 912 280 283174555 433 611 986078097 761 665 235120781 317 242 667757956 79 156 39669381 970 108 139708210 610 406 617638894 262 744 353082859 885 441 579116576 356 872 373734971 23 334 843018071 485 866 760275377 598 458 573798519 137 897 338470151 20 60 133358678 77 737 72029873 65 189 145967075 910 722 992268252 336 8 452756244 45 709 739271685 848 528 246740293 454 2 405895228 789 867 905424501 822 434 418572869 723 1 744350687 730 464 594464994 636 631 441037715 606 608 784523125 644 491 115919182 710 455 739023805 789 254 692267986 469 147 869676799 336 630 722842969 1000 627 584197881 386 9 970850440 58 173 895554898 318 438 935324505 496 966 948028093 781 386 50805479 65 714 232688378 284 816 868389711 815 126 921162116 148 485 437913713 58 738 683068125 405 996 808513675 650 538 63419965 828 455 720951474 257 652 70694283 913 927 85339609 922 824 515414504 48 844 521271285 483 880 51662666 305 569 941250746 519 259 697834684 399 379 572226708 513 827 45749575 390 285 437174047 431 592 648116291 950 224 623054115 58 267 785096842 854 382 53477451 339 454 367454078 195 542 509533538 360 106 832732600 403 468 602268556 837 486 315887442 546 979 971727322 96 183 925493564 465 325 45501643 489 322 98013261 359 246 730212593 772 742 407705109 208 783 442269253 745 95 240920648 621 527 816972725 396 9 523147378 840 826 275487016 229 712 488524327 55 6 291454964 134 116 245233453 898 52 61311822 900 710 51749698 629 417 302649852 899 443 307512464 295 133 363116120 166 289 704815173 530 609 434252927 558 320 644347534 568 201 960566098 967 227 1352439 933 303 300393921 135 83 751002137 703 278 887358309 131 869 69489995 369 606 669227599 299 739 241854065 780 355 321392081 279 88 39644567 806 783 793655022 758 547 729933960 767 843 581686906 756 37 713138195 971 882 210129616 649 190 330550801 529 922 640065510 964 106 529703302 919 157 804305766 509 653 936540986 267 999 452275958 810 669 647306517 404 799 911494823 171 846 606617899 955 427 568247811 882 447 829711667 535 597 162448564 456 862 693210672 320 598 925159993 702 313 14765263 308 60 377721252 520 929 647259000 17 556 360437573 104 114 121722580 645 241 178468586 447 753 897828379 956 811 324524563 825 578 386425148 774 706 149232614 594 300 299431162 323 604 309557230 424 906 513521742 10 775 643913641 987 47 904991614 811 651 402110568 377 487 111922922 824 117 554153910 799 152 604634096 815 196 182173953 60 125 845767010 798 168 751995846 4 412 405179632 845 904 531849610 723 985 123429542 160 814 679612548 104 811 675502595 8 528 101542387 38 691 727132555 786 710 130344035 274 36 1495876 640 117 270213461 438 938 938162412 748 170 788662508 222 850 186144186 804 443 801501648 70 651 614712214 710 485 172517236 530 722 113180421 502 684 864383145 809 128 173432980 299 461 937002502 785 631 840928754 395 381 584802159 163 715 618722609 900 198 556391661 101 577 754945746 922 892 679200515 778 570 223095244 932 845 144919779 321 45 39138503 516 920 252557210 616 640 661105125 362 541 319365514 230 109 488565364 940 726 568560985 552 753 442605746 680 204 740389264 113 786 80673802 280 645 77818369 495 266 933125104 920 464 740764093 580 309 777381462 532 801 249138615 112 688 148331188 464 646 778333036 568 986 241765552 331 667 666431629 441 490 573100948 17 36 570718851 889 674 902144573 840 183 317145497 290 593 284820771 101 533 975058976 69 140 104186102 595 693 288569084 901 9 949408620 330 164 379838754 298 116 28944419 330 515 602148258 42 762 815936889 547 277 957183298 932 130 582786514 554 212 391270299 992 940 61352740 634 874 234772780 604 657 958791864 249 105 759109688 799 675 894207752 201 740 737665796 825 866 71042768 936 951 216324454 580 230 64807603 661 874 886180542 740 39 678297073 995 799 36788217 305 149 260465726 407 636 525095789 260 695 525246523 491 889 704909942 232 108 262647833 265 131 229194796 714 22 514421928 853 542 865326282 628 397 638606237 41 273 273107128 180 249 875256983 908 226 887137844 341 382 948833054 30 121 648442489 786 148 498056296 788 165 645213886 556 538 573738483 891 232 712931266 452 836 438828139 574 936 830704075 833 262 542746846 662 947 337275365 657 822 346742747 121 202 153133249 791 190 467631804 166 512 274323278 406 710 685321956 341 62 884439605 114 425 532570623 684 239 677520645 778 953 245935143 814 509 885372531 116 274 786321528 669 428 59500780 312 139 888574420 855 244 337787158 544 108 568237250 795 811 226876055 250 655 306487023 501 631 41315601 674 951 370026571 72 54 1558953 532 387 26073735 802 69 984935564 957 288 624000394 80 943 451157703 936 251 501549694 292 289 503999119 747 283 295552539 452 4 461587585 525 642 936931583 741 438 936566388 394 184 33397572 737 98 925447805 621 224 181242128 167 171 202213787 719 104 15964584 888 408 920842060 223 605 446841162 727 697 838576198 906 414 735895040 447 14 489358046 423 78 581403765 778 637 433660771 973 909 827793727 533 260 867821313 494 163 280911456 883 895 185358717 775 474 929737446 940 545 567530882 759 26 782316306 755 854 691410843 868 45 195998867 220 302 252973694 7 892 45225120 815 886 549016832 67 818 552417653 924 75 627408248 456 917 967856059 18 934 714747583 258 726 608265564 762 468 877288330 877 49 465517895 713 544 969211814 468 266 862159018 933 924 497658349 567 847 543090102 26 901 502348676 50 743 988015934 453 92 889164053 791 502 977474265 794 147 459046726 215 289 315473513 333 123 126429386 434 17 609955278 300 545 733645345 318 817 722338365 854 796 593470757 205 999 454843660 433 827 327730070 331 271 466614671 223 292 418303880 62 431 299774727 294 647 358396897 903 740 458376490 776 310 102423078 637 395 937909589 784 366 397788431 747 75 742514290 887 731 896160680 337 919 463200726 835 590 904126780 557 947 851513502 500 233 613624039 66 334 491666999 448 523 744998418 437 880 864350490 423 414 276116015 618 969 328826020 186 308 345198344 682 907 752517118 273 852 473020033 620 838 215755392 281 468 327822765 254 489 709012853 360 770 860864526 524 718 619931025 347 638 382396231 988 580 336364845 335 388 17722931 562 693 952281013 100 889 236888622 651 499 861680884 210 425 89945001 824 666 480562217 567 340 503860867 789 44 656595415 345 561 931481105 154 820 923794906 450 807 852810934 736 679 746995958 92 901 479422115 135 470 398664645 181 513 488018854 233 24 167989172 177 4 561334316 278 358 407804510 64 539 264534008 984 136 928512509 873 923 373934612 73 905 756789927 125 417 220232939 975 451 347307030 826 197 942514626 429 261 180895987 905 106 843140220 267 64 801020803 950 338 19845803 506 575 414397590 162 510 192485858 302 918 79403424 197 753 129599565 778 996 22947009 644 528 758058386 633 869 135932247 785 768 990006477 696 70 856593455 632 106 222679247 552 314 71661798 882 351 860936439 780 482 129025807 235 989 840848547 359 163 406265935 896 742 98779260 920 296 70911422 890 414 353460798 262 63 305101682 621 336 583443842 658 511 682266957 935 374 794919670 267 728 744053388 694 168 598365198 654 131 415917055 787 594 772652607 118 321 277009541 774 971 481972190 184 831 890156196 386 635 33630077 344 653 221078767 237 63 104284608 59 957 754041442 329 981 77062979 373 744 819193733 991 408 135200481 317 342 1858497 945 692 739022908 756 364 255880269 14 385 704958589 79 670 266113949 842 313 156250556 107 9 575764959 995 425 352640184 431 123 251025913 770 136 390429421 572 458 390974975 463 270 426303366 349 359 511324538 864 618 652580020 509 737 969813365 7 403 36308424 150 719 783445319 752 634 212473293 550 824 50371960 779 121 202081947 697 685 570846179 32 204 726073681 267 88 843385959 735 427 830464371 121 649 312155837 171 605 669817234 370 514 218960844 42 489 427160612 627 436 570184370 423 991 702424291 412 657 963251153 163 407 902536625 623 73 303696474 30 545 118339688 115 532 29792108 288 878 538141933 406 260 860823029 428 448 816244029 310 697 590823081 431 30 137680754 31 78 578612822 963 15 396268079 701 409 368660234 56 978 397350839 809 675 987018787 477 590 591293125 665 615 739601773 496 796 478299868 983 776 492873076 331 109 510839794 930 405 318248054 352 505 642439592 698 991 369741170 854 841 529299280 567 715 710739544 624 360 607572922 9 531 351377082 749 327 176275724 288 328 694453159 458 935 632745940 996 682 465901697 961 810 455404107 262 723 84627165 336 494 692196250 107 875 646087695 998 16 461980246 35 979 659040208 960 194 11526645 330 587 117471618 224 167 647045734 951 993 310114549 550 125 590854239 989 689 719370014 616 500 966750503 929 578 890743294 769 842 845722018 289 55 617179992 871 769 116444036 200 746 910500998 536 922 883049193 984 148 455965955 595 810 666385635 960 572 213219226 378 277 425511331 9 202 22235050 82 743 581756616 358 894 549574359 459 189 320596122 595 837 757147698 726 97 973471162 297 851 298779641 862 382 13005455 60 79 614265286 574 998 435655226 3 759 138988817 669 460 263960061 884 282 631438733 755 531 704460745 892 156 28683674 471 162 606096698 406 841 396456500 435 424 257228069 591 198 245157657 680 98 620261180 66 487 742370962 606 61 698492602 443 767 129086406 217 382 504686505 373 922 512892037 535 348 949300533 53 985 196576762 905 173 576470591 509 569 496218255 937 192 901304475 910 657 273050717 478 329 224700207 259 204 610846526 187 863 631122420 262 841 976244835 208 572 579555956 70 922 231681098 696 496 485020963 603 644 799158878 279 771 216496097 929 124 254715721 385 16 252198353 723 919 685264553 912 252 189580894 281 187 492121344 596 536 596012382 729 539 910915200 392 75 375006324 208 741 586023467 71 311 315861639 32 378 333978579 764 476 742840986 8 988 968557206 596 642 767339667 68 57 428058775 833 318 665759616 156 69 436414251 300 265 391301789 3 854 895377985 434 659 891214576 989 741 916871702 369 139 375150728 360 148 509146679 102 552 34465753 948 443 457831450 270 231 688484523 149 75 581935345 660 222 847308769 263 243 747671038 764 697 47698687 599 570 436746878 708 510 494072729 511 411 741061875 402 547 560183702 978 386 498598233 541 869 222021078 26 512 742866690 8 955 202834942 828 575 522400862 345 339 736215174 963 928 230296343 826 635 619188440 483 555 840941588 987 468 23784042 620 201 563984431 424 605 850168440 922 127 963750956 489 835 279974670 872 851 283359971 306 49 686699943 170 77 293924307 82 956 88860049 553 32 170259635 890 169 431509586 971 168 12579328 927 753 203066799 469 844 507486899 904 957 80301582 520 202 737152502 123 651 687588556 302 850 526937579 214 130 148817960 699 735 753335802 709 881 914722778 897 842 207796804 717 325 432433736 567 254 709345249 188 97 913277027 693 892 630302424 933 88 515796432 955 392 780837176 224 34 974467851 407 40 696809978 861 177 743948974 918 810 221410751 943 628 755570131 611 270 925202022 323 186 733856217 304 242 201208324 8 866 984745501 764 721 832664423 760 220 542273477 30 273 21280820 882 454 548896540 478 218 34576729 896 836 427971471 626 719 363621119 158 752 915086606 192 241 881233180 735 484 905095231 505 14 218137157 165 107 733413049 290 442 16236356 931 905 507822190 14 902 733312101 731 837 839910997 515 498 636248168 271 799 96411270 358 357 552213509 170 824 173430133 242 327 337175388 228 135 254144533 184 695 476071685 934 2 545833356 310 508 986431808 892 607 336380611 104 375 841222024 98 411 316777776 327 534 6627382 944 474 559621074 387 334 392498356 133 731 404164838 765 186 308161139 817 839 50624174 848 586 894996626 676 172 181778098 932 244 260694599 146 934 46362578 651 162 386117359 857 738 819641878 795 80 741196464 656 578 565804628 446 391 969282810 871 471 212196136 904 188 287940064 949 212 369941982 477 280 534114362 884 85 544299199 807 503 284819889 977 840 433292312 927 936 958151502 195 230 468656737 99 203 547622482 847 239 139326295 323 533 264150803 911 437 425128787 37 74 535219887 559 418 630549764 387 310 821395574 924 483 454534121 506 515 844872170 140 673 61089552 675 151 847695682 513 878 740191325 986 865 724396646 573 458 822171415 906 115 189473736 793 898 132688401 886 417 830816888 755 325 542064175 656 552 798977420 758 904 591051170 405 964 592660907 554 386 956010790 268 302 222251357 996 736 372872421 616 60 125207943 853 658 188473894 741 581 515645720 113 511 683031111 201 194 654322087 621 566 978659402 375 448 302483274 444 521 750774122 699 415 617235063 704 934 810417788 164 681 566204374 867 486 585508769 609 225 797175166 353 569 565742746 706 300 418215054 124 12 467259059 321 49 440502212 286 640 892657895 752 29 366935189 962 124 60638904 998 595 539981980 599 569 142558777 147 441 134267979 202 95 554780680 708 168 537919769 623 57 341963244 7 671 490939056 296 186 172728378 58 637 495083237 440 720 727483815 680 52 246781232 892 862 726209029 681 393 577978712 781 614 934715782 76 832 288648698 166 574 485847657 842 908 170071848 992 233 435905101 17 182 617487494 539 241 112704882 436 451 726571868 958 919 495728699 295 639 305619849 721 606 648871385 203 215 937049450 273 695 324242365 746 310 739625554 47 332 275884735 228 7 422205232 291 942 53657364 531 128 298734503 379 40 604342825 655 702 929342374 844 626 904398395 957 923 693516908 528 408 651015103 112 697 447302532 259 415 530942219 474 168 35575883 449 927 60014570 769 668 239954169 175 448 778325412 230 433 872482178 719 475 835226016 567 837 504862904 391 718 373570538 9 981 745105224 455 24 596778065 479 457 934146421 899 935 390466012 30 620 906118160 217 646 938770491 369 273 206575705 937 415 626315417 768 610 706266091 284 529 198244861 319 730 521808830 177 511 991804477 786 698 496883620 602 856 92305214 41 152 864238522 652 444 418366447 655 959 481250568 778 333 285630056 727 597 238979319 88 44 121692871 618 29 210377371 649 386 117906034 184 511 309873997 959 868 131332175 940 199 337409437 855 246 708976827 870 828 96255640 202 419 292029220 649 143 438670718 25 128 733113467 313 445 218197793 600 312 930097467 465 676 109142468 176 597 208741561 333 632 328520303 595 532 87658290 182 844 361387521 158 447 561283468 698 724 410450539 58 569 746896922 860 815 973051567 843 874 927297066 190 165 613159926 967 925 619410732 214 342 852979328 820 655 557764624 347 299 850554351 989 99 169703660 219 956 64826900 492 840 625955907 437 737 743875596 302 379 234700605 460 542 850077284 621 299 25332827 665 65 303945318 277 988 122277757 473 899 201099538 86 368 857977359 848 151 514602206 791 891 37998302 951 829 395271416 540 289 878351205 431 226 812295251 968 607 264591282 336 867 78060540 678 411 511186223 742 107 339612611 807 405 139359807 434 960 521131520 817 797 434244166 956 665 810903509 199 165 575706004 324 104 769538120 642 200 983800800 825 606 726643995 831 158 910473127 722 380 475467222 551 848 138935310 449 828 659046938 696 76 735324796 837 764 997475156 120 657 14933636 533 126 304477081 86 124 299954340 126 287 95828476 255 737 398345188 969 510 889031189 851 480 29201413 725 649 892411919 174 521 255369216 890 191 307372251 601 750 239883212 615 728 632967227 575 307 382733388 428 107 819583282 21 836 349485101 617 983 604130784 427 31 404848152 539 669 348307960 387 561 672139183 257 649 615885644 308 158 7997402 396 753 641841974 699 341 699999174 730 62 601521452 533 137 99511714 747 796 888816054 151 767 194734839 556 256 26977272 43 820 699131976 756 737 672597887 900 716 309067482 300 653 251923407 852 380 635364508 502 604 245334484 769 826 160447718 982 206 329662781 492 800 351820193 285 437 873325151 487 196 757756940 997 493 504715959 524 208 92727184 611 346 773142203 645 738 92845929 150 14 677319979 957 589 224703273 51 848 789747189 162 817 652397196 749 639 377968727 814 57 479767133 157 372 139080139 346 826 996113582 22 337 542405351 27 271 869846263 578 461 625288751 621 374 679833281 339 974 268034761 909 561 705199460 455 461 123379773 191 38 956756281 54 23 862962787 260 64 12256598 320 45 92738818 115 803 824279631 451 399 903054842 662 203 968527894 247 269 796503129 967 238 835564028 531 850 745481651 645 87 26618562 287 252 844596775 318 213 109677783 580 862 206327594 702 219 373792335 768 655 37101038 585 898 420619697 563 172 933484245 942 88 585913482 999 168 67436318 624 124 811756341 90 457 75057283 472 322 41625307 414 912 61333162 51 261 263247616 628 497 671505882 975 565 871797232 299 313 117725654 248 76 313351213 565 316 151091898 443 572 833222942 912 682 590189829 336 161 87644907 858 386 903609432 569 96 302386690 22 49 852096292 137 659 875404563 540 190 1917034 860 210 14924834 975 480 614652743 250 528 255405489 168 712 707067855 724 372 868790097 186 697 604443357 440 789 693977439 953 210 46645805 431 960 399030268 33 708 347029191 892 108 200287916 155 913 760259710 188 760 274953289 486 458 779330289 282 568 134021756 344 911 25031165 927 799 544596764 915 557 67513129 673 515 938026937 896 780 40441044 714 978 932666554 460 385 24936270 100 744 777342052 714 709 883214691 222 606 622840254 680 725 230345201 181 454 197364790 222 253 182457254 281 659 837651252 621 712 886559374 511 405 357078090 683 335 858000126 445 775 615691089 438 610 658108878 448 453 159000014 664 215 669797090 782 645 120037225 130 170 595681314 570 996 54786978 585 473 461565503 981 53 637609854 855 870 887955369 390 605 755395552 141 960 217077867 629 523 308252458 47 631 886095705 272 480 507663769 340 524 232149119 660 198 770620644 926 701 785413842 220 945 226792608 300 954 379692382 948 26 723845619 605 263 368866957 108 681 601587530 712 830 635306560 992 172 419678201 699 823 782760160 354 349 741495503 440 147 365749986 678 115 890148277 902 850 383209351 914 902 827428215 786 139 39208198 208 29 370744179 873 180 403936849 502 444 447265191 119 717 492479662 593 56 643962117 396 871 527534124 636 524 663423346 726 549 514387731 496 389 520714764 29 972 222016107 653 558 58086690 377 20 677674217 832 902 211470066 187 650 936173176 706 688 555610227 686 258 697434411 735 48 109992099 295 342 250580047 460 614 345763637 669 643 487752512 866 748 37993397 265 268 114139104 249 460 804347047 305 784 568390235 704 837 304351241 376 66 131041387 160 130 62836671 556 352 599869530 626 415 150420242 313 776 446683091 65 147 294140487 945 962 986893914 735 640 800254591 836 584 68365512 85 466 367426348 640 860 67821227 963 727 771999273 691 945 923572823 408 495 211648166 17 815 724816602 504 671 572190595 715 657 55837499 458 324 865983976 520 449 251068864 506 58 102199431 902 403 98139491 925 346 805263243 449 610 304253567 404 854 893314153 25 24 804335664 52 223 35086876 107 97 822528016 929 409 576478936 147 295 994991235 942 34 722838274 368 749 435476996 70 845 786966449 505 395 402276685 143 235 431716460 900 599 966067279 476 22 732494805 605 17 130943646 308 419 119065611 972 505 292951020 668 5 630520960 136 337 9440710 465 401 17962548 561 203 665669317 364 333 349549580 920 751 162073097 990 24 761176847 526 735 175789305 890 932 819485358 894 725 872491029 931 639 729046347 958 997 934727594 873 672 493797966 526 333 194086581 113 688 305624741 511 814 145188391 467 783 77970446 773 124 919045728 344 270 220166383 331 535 778023591 212 183 842429085 858 805 44396082 385 102 708498061 837 387 201787176 692 724 355043690 208 811 229565484 779 293 181397430 141 122 427796685 376 757 835292879 857 89 7939703 274 47 533359028 394 589 595571750 146 90 780691584 340 914 919447960 385 709 522952335 547 86 851015638 801 398 516519584 268 44 296967533 513 684 20127101 587 938 197182592 602 29 101850755 388 258 258901624 262 134 115196164 614 675 226987716 193 723 588414682 99 749 16427488 425 847 871896328 491 729 86062588 713 532 308231056 279 441 366191476 131 877 579745717 73 697 692705382 417 872 327246951 397 547 840039781 457 610 327830201 1000 147 239242636 571 625 731353032 298 940 182311405 643 573 529848163 729 425 79443302 380 483 511293386 704 967 760658956 546 792 982649685 718 92 80533653 607 672 54531545 486 894 200842928 861 677 129410163 603 691 554987402 497 28 418288227 470 832 172329877 338 730 211967041 683 92 718191502 917 721 273415090 282 335 890144355 370 722 864317120 611 986 146561895 518 740 271806050 935 833 442174380 170 22 562775538 711 80 915408226 926 629 581363279 548 651 722043722 459 47 619176132 230 47 653428599 773 360 153039095 951 504 194572990 812 990 916301087 88 759 960857598 239 651 88394581 648 833 973480970 151 518 189199101 586 650 462092237 111 6 496378678 463 373 716688219 750 429 805964602 484 862 889476177 296 528 688983243 625 54 582980286 574 209 579900749 747 538 434963891 519 766 740066898 92 623 583587994 247 736 383856958 173 276 745839378 289 819 509133412 919 126 20550104 481 756 977134910 945 375 701507609 146 280 108894891 302 959 152736753 965 301 375484379 566 467 949735027 14 62 438418687 869 313 170471073 443 273 584662902 856 796 210142702 795 265 397016722 449 603 407961782 657 256 407403884 687 770 405870987 377 422 85327692 199 41 48563429 60 674 326575897 885 689 996319254 569 843 318217947 261 242 534714271 14 346 984108739 227 652 543265643 892 697 977773497 827 296 479261819 373 888 372744558 569 720 482855311 838 201 841163514 73 229 179351467 538 649 630252809 179 167 507978206 339 25 838999667 737 675 318616116 207 66 850825233 654 353 89058068 150 414 369929141 881 109 590466791 550 893 962140319 505 917 666598396 416 966 615527099 137 486 568962124 412 816 457023143 982 209 337625836 317 794 90949476 54 28 529373319 266 2 961890533 805 449 182199804 195 219 867782413 292 258 566914729 433 215 396259859 137 801 225226139 131 113 125779749 477 78 360929728 701 186 413374357 946 709 241938668 64 753 78812787 477 113 678582051 13 948 776156608 53 940 366787351 779 474 296712000 280 923 290063939 560 227 16313587 92 996 609363024 546 262 770118530 280 25 462977276 117 53 545485202 766 608 536389741 285 422 582984584 283 949 84763867 333 674 770136991 200 919 870366014 869 3 319191430 436 538 913640897 290 573 487707793 698 70 674634739 612 556 773604694 289 541 175163619 38 339 439112722 599 807 144525068 398 340 231842658 723 953 645393408 618 55 867149185 77 261 272673186 573 969 787555588 939 687 954281301 81 394 348062836 413 259 702619667 869 391 86122566 824 158 646368525 797 830 876193703 161 341 347279735 415 164 340762155 667 620 504897507 118 419 963338007 654 560 751763880 32 516 914521684 527 439 60346190 900 96 23712718 24 829 871725026 999 624 994133697 547 935 748114408 182 24 260122064 677 987 578215990 709 141 700518172 227 442 227877124 39 374 200849038 863 561 364598805 517 388 931998368 950 831 820612186 360 482 616183556 787 587 830590837 304 455 438272985 34 526 939314686 513 57 390085753 277 429 72853111 202 908 44726275 491 777 989559230 50 223 239749957 347 138 93420437 704 497 220012125 102 496 916951079 622 66 106617925 704 459 928536435 779 568 923412902 264 285 705982133 807 378 121139314 518 348 484265081 794 184 758027333 228 291 987581414 844 572 733967805 771 218 432841998 850 707 259930422 638 772 390661046 235 802 176957573 771 159 443366778 680 535 248815241 772 813 628210406 606 339 861687026 165 991 797371251 233 460 883214093 157 817 236807957 437 409 983204483 235 632 255209957 604 87 669068029 35 132 770057710 46 311 352261682 423 799 784975095 129 14 480110474 639 951 22975273 415 690 95402075 696 847 416018399 527 622 34457565 364 777 480817045 759 113 363489674 480 354 542981410 190 464 368649221 323 556 730660647 123 962 879896594 122 951 832915486 932 221 125451712 975 790 125495560 517 94 115769004 798 954 897046824 442 688 595376892 619 608 823997718 924 884 194666558 963 987 781267830 24 302 265404533 998 150 397689411 165 761 183152070 343 418 966254656 630 994 369692129 944 582 657549428 285 48 717999976 825 437 328670807 880 642 614187240 441 171 38225305 486 124 81402487 570 772 913600705 678 735 939733460 30 149 469136479 434 97 780757012 363 189 458657329 278 838 973085155 921 222 954685119 32 687 354693930 358 871 212544540 673 546 496999770 289 208 760965364 252 976 246779919 839 270 43711923 605 187 624597088 598 641 473079947 918 696 483963682 266 663 299054910 226 685 680335653 678 300 817139842 480 327 975275248 648 953 271521022 197 89 638510126 816 538 478116991 241 111 702595648 739 52 784817829 594 497 364228855 178 429 967292873 645 661 872471125 470 371 879899237 148 984 319087516 75 446 17288015 675 913 170009217 665 391 532704293 272 381 788456039 987 754 227619989 382 146 437362761 537 761 213435865 341 534 744364659 829 437 762261006 602 207 604864723 459 594 716833688 956 288 346399896 394 67 189108858 665 62 251244871 280 98 266522612 228 246 393711683 621 536 551886352 170 884 537932435 554 504 93366152 582 888 214428191 895 475 209663991 933 625 715806390 348 281 709841864 269 502 496469324 100 346 645255490 274 34 577292523 53 136 188328053 44 73 183212173 53 325 876088562 986 551 916537850 230 743 388124378 345 545 476191237 203 485 19596883 891 953 389710683 957 465 493283929 104 255 265657283 171 684 579376640 115 854 704845292 178 343 919118447 985 649 458331411 527 754 110782183 150 157 354553872 128 916 722499096 799 775 421703674 8 724 334712100 737 128 533197582 867 968 394165634 552 725 83025495 299 477 346295343 222 740 500826347 131 203 285973838 953 879 843513784 482 931 726911433 417 855 844395642 970 812 928440438 629 37 552008627 922 825 832874689 56 199 580159314 802 519 566947103 142 463 937962295 497 884 174731627 558 762 484651639 119 13 62983709 154 981 332165493 447 250 873689162 61 441 65955190 159 928 144729156 422 353 418104724 327 277 620280586 437 258 980683533 107 78 95863498 473 977 969931209 49 477 633203450 605 934 695770620 695 77 47061228 505 2 391788414 386 301 984267021 322 232 349428596 240 215 925690302 436 554 643878957 639 503 788448078 73 795 408729915 798 24 951672276 903 650 765011797 565 625 196020987 717 102 151025647 242 791 484063896 345 977 412909088 96 594 684943929 502 376 595100451 431 79 820054638 282 724 330639074 743 730 371020506 662 669 433254226 920 761 989908202 536 340 192632746 404 368 245425789 646 918 361125483 796 429 873352590 498 144 818465728 914 869 289087759 16 596 617841587 879 324 323572172 390 837 633592835 977 128 763095115 10 162 395155624 72 273 817359123 10 999 368091696 746 259 48482194 824 766 422956444 586 555 720306107 617 676 276449970 106 92 191969640 66 54 751953625 561 932 724693264 784 803 621798353 850 69 650361779 908 508 821104233 668 876 335087710 136 369 985866786 749 261 277128729 910 522 918631941 332 16 844023507 957 791 813794321 301 203 661127218 870 626 995356506 509 996 789943901 632 310 902130964 968 51 457764136 432 188 790275149 50 563 835790522 906 892 830404221 557 184 342744442 588 390 868790406 496 58 831610368 491 289 686771771 188 941 729791559 309 347 60796010 136 610 701839253 313 692 881487568 296 158 176119946 73 112 391105942 637 395 214728607 919 798 829906891 462 629 767883509 58 936 978755480 773 81 325854085 653 200 747331034 257 921 626816147 782 681 257721011 792 298 509577880 890 163 702338720 59 883 50925041 25 116 14548715 4 426 610722718 212 801 879310105 907 339 222629813 157 360 808883640 936 714 377651068 470 721 681919048 348 982 572781753 54 222 433336048 238 698 869591194 583 232 93440099 656 756 755354730 836 534 560393945 451 914 749847343 777 327 900942238 829 290 695603593 252 365 579797125 692 402 714379063 833 487 337507224 940 177 739778210 478 410 717287660 887 508 428160581 674 388 681777345 821 684 23443939 626 683 920643075 993 142 313664860 524 386 440338506 215 633 712790159 51 78 540024277 416 694 141439756 230 753 746426539 768 35 704354134 458 990 839360770 854 901 564005811 982 515 752752992 169 997 951872400 911 28 914173748 458 999 441389527 120 32 173183791 785 434 737076426 502 805 949483448 925 767 288180548 359 181 1616138 685 592 949328020 268 978 595825401 146 380 547660518 642 496 367255821 870 722 372918810 216 55 543620957 832 315 663271640 596 741 542844559 13 496 690309914 808 151 436130933 840 99 371455171 640 103 804608353 932 426 655165149 723 548 956944045 982 445 788365878 593 176 481289670 780 328 856911336 751 971 161444662 246 503 736261551 950 119 276065308 579 135 909995483 435 43 292787271 637 435 559583122 93 143 657835690 441 744 612101564 553 354 211663422 637 46 250070878 806 824 491434507 224 822 789962617 202 413 994541637 825 828 573266141 79 835 97788714 743 60 843147767 521 421 442151662 31 926 702598984 49 107 670958749 472 161 397023498 938 436 95864105 855 916 124555194 354 329 299883852 941 712 339619866 22 150 356508736 620 799 955431538 540 168 679872246 193 745 181877639 183 641 204322988 226 693 105237586 181 732 375697883 403 766 263288142 341 314 960085009 105 881 515549690 880 354 958188998 258 588 495506427 884 238 21346025 662 525 237060977 386 329 45427471 702 300 946451392 254 733 789458535 333 136 489485195 86 393 570143803 672 727 671741343 298 188 253105064 375 464 826409789 180 64 43192602 500 894 24653028 18 480 900699056 565 578 115389791 278 754 376342094 673 654 538222495 492 67 91481594 519 38 870770172 803 912 538226712 291 818 895872163 582 193 574874089 112 936 534285769 979 683 93627315 143 456 220816558 474 619 515830191 572 270 578079917 755 828 442384701 283 889 594621384 57 552 559157656 896 30 369231649 370 427 2259778 743 323 430305912 254 689 406050190 503 469 176475104 182 978 674873472 574 870 668850446 362 219 506939517 874 739 667037334 663 971 243268350 413 21 234239861 482 949 45364311 347 10 776647278 329 584 935627911 555 839 825573617 833 27 343608509 754 364 266295807 511 548 494797190 690 355 64265196 102 389 607300707 375 437 162693121 415 287 753176226 969 79 927867419 741 93 375031596 119 509 587219037 8 417 873033940 160 570 859386467 318 33 802489692 32 979 186424134 963 268 399970609 866 93 891701796 981 69 326839875 688 663 281100574 240 553 760935692 714 242 24041717 315 588 981552297 14 56 844172418 775 768 234219952 360 58 823362014 835 604 922893909 337 776 379144625 541 473 502613408 408 249 342852863 670 540 763721158 256 965 930964191 174 7 40694602 194 860 738411180 71 353 198808641 848 926 880858651 507 850 447747215 614 779 601254643 404 111 627428867 123 181 759489544 954 421 228184311 697 785 910281305 11 502 913308044 147 546 649848928 862 961 697993979 580 61 240992291 304 509 78655732 209 25 301210457 122 5 702852865 918 545 94549320 512 922 751585565 124 56 942169271 269 772 504600402 584 370 693072843 120 406 155640119 95 893 410857591 33 561 242656787 966 883 790089301 274 304 431042812 517 259 483977180 539 632 367090529 677 108 502680837 994 140 91896155 690 189 520481719 795 736 421551499 788 557 348549519 674 134 657103971 272 893 541802189 488 291 88723345 481 25 927950473 359 469 991863227 402 875 987376318 651 386 316565299 840 331 680980335 611 43 421691353 28 637 301801357 419 619 641732450 159 422 417552458 845 344 898223506 523 722 368646292 139 241 832474048 565 416 78698519 432 273 442860775 752 154 79626352 175 226 16773253 96 94 162094860 246 189 604874819 19 413 250297360 900 302 258094079 942 151 197847287 679 670 954085515 564 565 228000209 485 452 693148495 737 612 110843935 881 702 98561597 453 460 757238494 282 158 797103778 932 613 868281583 482 545 437532830 662 428 419059679 150 291 115257201 616 377 145573279 678 814 224663671 616 423 134775745 317 877 1994878 706 543 240031763 861 306 4855477 225 909 255192130 329 801 890576865 450 686 11269171 931 713 679333298 59 246 142248975 664 68 643816377 750 384 124237186 369 488 524584559 351 868 152909823 21 796 155763575 36 413 721019587 661 172 178187584 939 90 141794429 563 548 492064825 501 955 295556565 414 297 605144470 562 218 723820143 777 381 703315153 771 869 103221194 806 143 660459825 399 695 963235685 505 468 902850096 293 152 603015005 168 109 634934072 865 848 101946647 882 38 420468596 578 136 308492311 164 4 163599012 919 810 600547034 491 994 965525122 867 166 531041110 850 752 350543888 787 558 784453769 777 647 39810726 375 520 154458966 954 353 115973138 291 304 133975681 576 108 208680090 426 314 798363922 884 441 631870752 672 891 938265487 603 97 911281473 91 131 189674916 211 998 163417099 257 817 315229527 319 729 186651333 346 369 228005513 961 38 84903846 99 64 290208001 976 605 279923810 600 863 280724845 759 279 920185540 459 321 837051317 252 380 308170502 333 785 514628204 730 913 469604409 699 179 706057348 747 667 452235 226 380 640077177 791 453 301710356 296 975 331901176 553 310 426231340 97 753 259962692 737 182 866106067 462 229 925787119 5 892 361399704 30 872 299083987 564 866 930501978 919 439 908068176 83 131 139363767 84 296 110128740 71 599 681031623 214 942 245583785 980 940 376238129 445 406 571278886 667 58 133215832 77 159 855757500 657 622 44758968 707 781 343094987 814 736 568389412 282 427 834609172 756 64 708342943 503 563 782864691 766 148 737728426 648 588 158530944 610 690 902079654 443 51 754238289 236 580 411322555 17 353 652263927 203 383 138035551 69 299 903810308 561 92 283733055 185 957 2148553 690 732 738621395 942 85 627140622 220 508 841900768 962 33 446470363 524 710 868335254 134 167 60044694 361 390 46366617 716 738 27885427 922 624 781131312 181 104 662237236 372 671 813960168 223 664 585770985 183 547 886767511 391 910 218395964 738 929 430856354 488 940 324567330 858 246 241413883 29 577 631609506 606 479 565308458 32 536 730747590 308 154 9628051 771 622 751835523 740 538 779303784 942 837 900639540 369 672 702865807 822 473 723595710 525 648 653895938 141 288 812078941 149 359 442155280 904 470 275686544 935 611 635978384 947 472 742069039 800 236 339066291 342 952 204547622 413 989 200581658 512 943 176406417 111 400 213630276 733 369 913622083 576 510 636568272 972 153 106076340 280 413 710750634 697 820 227665625 944 48 416251913 161 791 579029469 807 404 101444046 437 848 482150790 613 499 731743213 706 928 43141520 306 279 618251590 240 286 327177239 899 276 448504793 795 671 325172438 667 893 437536771 952 774 353348830 936 807 308784102 515 789 637896904 984 652 669031242 590 925 497282294 164 645 326070572 692 807 657451389 154 200 689130349 80 21 331274563 950 735 520559690 739 408 51648839 384 994 398468605 742 35 697600795 451 993 958047282 955 415 251452569 436 502 391086560 957 52 469593669 507 948 600320587 822 56 121598042 64 193 317236013 212 168 91709512 829 124 782338700 6 414 190023511 89 580 891616932 189 763 446518502 344 592 668523580 484 288 641600623 210 57 5010001 860 655 646875983 209 878 70386105 420 580 979234931 60 625 442255369 314 959 928965807 457 206 976147972 190 994 75331032 508 200 466458569 650 952 598667604 378 184 377954594 350 367 934277447 499 879 877679585 435 18 415471837 913 930 114643048 274 622 613808609 19 117 214536373 667 400 945141856 142 438 301276057 195 774 521697253 794 938 495928432 303 332 136562575 865 838 991810632 597 242 960152247 268 367 743291839 71 842 704636320 61 50 348409536 98 67 36213715 251 637 847712356 578 647 615415211 364 706 332547830 853 565 945804849 70 178 720013054 261 256 541127560 146 543 96347526 4 332 276563369 394 809 555020071 474 585 548206135 571 218 266675346 842 14 827261367 341 773 554920991 155 764 706776999 806 309 775370360 969 455 536060237 958 345 364560467 721 815 787320310 15 75 377658688 523 682 733826095 317 962 38516436 188 732 752842573 333 720 29897794 701 798 495269090 404 409 411040061 229 72 845964720 144 892 856809243 43 494 57289202 684 227 434722235 430 601 406300743 863 691 71233197 583 54 422327082 388 315 33787027 614 32 207968444 470 56 236479109 248 984 656315679 172 289 870065631 109 933 939877148 369 417 737953740 353 739 229187256 605 325 282618993 397 675 776073110 440 51 929832302 267 836 303348515 101 600 398419040 557 567 510003650 630 483 965663379 416 571 63488322 29 97 113859262 617 899 114479503 426 820 200968549 311 543 395260977 926 739 335780758 475 532 409577409 260 125 178325644 219 229 390403446 599 931 206197006 944 182 635940036 803 275 140101955 750 199 164212477 544 725 706998707 46 840 180863029 618 476 890791402 545 190 593202606 229 562 954076765 363 744 76555233 692 107 132426261 896 989 536862719 203 513 335926507 250 360 726447490 419 232 483423619 245 254 461146735 422 86 991562999 407 117 510434101 953 183 291694569 263 869 585374003 573 213 245074164 413 558 647436017 383 622 295451916 419 165 787279257 543 562 63541559 456 918 481969664 643 199 387262557 312 317 264330159 239 400 678129841 831 660 987638678 559 634 761187078 35 176 198057761 375 855 879835119 851 500 585611098 685 739 407961689 335 79 277469237 287 251 698239276 158 265 71638792 821 349 465273239 359 534 110132706 34 723 169224005 750 631 837609580 402 530 898517174 648 93 670662797 22 651 232859318 223 987 821180716 896 470 108025967 102 125 631283564 494 55 514828017 584 418 754726550 495 993 342003922 640 802 211373697 606 202 829837541 791 869 729020610 557 183 240498726 171 350 400937729 234 813 409281439 811 465 146090782 583 597 740157730 767 440 365862859 709 852 626697526 181 786 956673728 341 900 659137421 532 576 76697633 176 810 462369473 781 421 171109756 292 662 6737796 651 97 800430913 693 580 299082167 54 11 116024423 281 814 458397930 735 43 582550633 770 240 932205451 401 508 755822747 407 861 855744440 965 568 679463039 626 122 619034140 262 200 906120527 409 917 677445699 387 90 511905586 531 388 200091551 872 225 135763466 251 456 67610443 644 81 533538681 270 944 383022173 169 426 769498960 500 652 605353444 723 770 80823488 631 273 122659680 229 381 452444849 258 856 57719826 239 168 503111447 316 148 132473801 545 100 939073814 991 600 335112914 32 246 252082799 459 541 161143081 777 180 626458134 844 31 174415969 852 881 172907835 629 90 57314270 158 731 522208562 662 559 538158161 838 716 992305682 152 437 568334044 410 909 174712730 395 273 239118657 593 172 729864478 143 989 244990831 531 735 681423115 462 612 100824825 668 764 82628232 73 17 829697239 372 442 128915464 642 541 554159319 607 566 807564327 45 555 922397802 166 609 457962943 338 450 895066531 305 280 144310605 642 367 404407531 406 770 280299253 310 97 299413783 621 418 777660947 801 680 781156208 533 625 750364179 555 137 337896529 261 914 762649651 826 724 252329918 294 510 409888455 614 374 270927528 6 871 414354411 336 584 364628728 826 799 518401729 703 417 92305434 922 848 302439611 891 630 749217760 618 380 699523462 223 871 687154281 849 424 644092870 14 144 936684549 246 467 94426454 538 71 69314970 201 676 494546833 615 311 164296152 904 796 752033135 659 425 140112881 941 673 998405137 488 837 721115556 406 198 911353080 129 296 605480203 454 662 196538394 927 828 714904483 640 588 944475837 45 435 782183827 50 72 71692347 710 558 190672726 570 980 385942499 11 787 514580439 898 405 195832095 674 826 394813648 976 41 839681828 228 516 9509829 288 761 79682131 195 813 369570729 922 967 371902005 846 979 914772921 101 501 645120669 865 521 111388668 770 795 265890828 348 843 903167998 375 667 32911109 316 903 136726265 742 101 85259427 626 486 77674662 850 975 284872101 729 633 986083937 165 157 555612583 574 432 372525150 141 686 649118119 232 28 497295162 236 265 613442165 941 728 589667775 825 685 734823154 664 325 894183806 416 645 338893768 65 909 53401413 522 722 64542713 833 303 555215303 787 219 227460477 420 568 470733132 538 988 896614911 753 904 551717566 960 360 971821158 70 327 384356774 186 956 986477158 387 146 141371602 954 370 895365250 902 67 114986161 461 806 272711173 73 312 548613546 218 878 549930611 257 607 961631328 836 341 573866562 627 188 421728980 676 608 209522796 81 512 559783326 961 327 583578889 667 105 221054955 120 151 374033361 442 708 367478508 591 508 631379879 413 826 471342307 365 674 927103474 666 689 39895240 273 988 362074693 630 641 550802682 267 979 67685806 458 551 510469688 434 112 470028667 785 801 653213200 767 815 739455884 108 990 936992685 618 559 346384559 857 4 609543437 553 834 542010083 947 488 712132276 757 515 300886727 547 324 529671767 871 349 790489711 925 270 508602900 36 181 762455911 169 363 232093381 981 453 355766464 195 772 58339388 166 229 638939188 380 790 771980669 493 261 957714760 94 998 496616654 577 182 319275062 155 464 322122435 24 878 895837682 344 684 746691595 71 850 667273133 674 581 545536824 285 391 803082605 539 25 178565762 40 800 305526199 754 446 749623557 956 536 579844847 27 880 406230742 49 522 501116827 538 657 525780312 560 393 340829653 982 883 623876014 346 498 946212729 986 577 636473376 36 520 128692564 553 780 505431077 439 752 318089733 43 659 49459142 304 479 775825391 541 792 851823806 488 764 289174698 415 423 908335792 199 405 741565551 749 100 182316427 578 215 579577079 766 668 610829558 981 128 674080541 97 453 960373706 615 953 91865958 672 341 376025305 729 268 744849446 898 581 386005449 619 857 546131142 636 450 72730782 768 933 540524875 636 167 509050392 941 518 380823003 911 112 706314238 886 933 890309420 221 114 44876785 246 797 720106926 205 222 392957237 820 801 38886449 879 608 141617069 541 5 2639934 174 665 806164749 881 111 348845367 970 18 232290818 507 731 257489650 137 433 905918844 617 747 7557647 346 26 466156543 714 642 376955073 178 598 680455189 409 354 512475704 514 520 659651302 507 481 182530021 383 752 315590829 133 868 775083338 383 406 235175679 570 306 711166068 309 917 832439165 620 76 703942909 644 864 710588424 892 485 856098537 852 304 515645104 34 348 739147286 705 888 594165691 860 235 480327732 431 982 216696140 355 474 488167957 523 741 267303065 998 692 728775136 318 276 69695560 248 146 880656080 932 201 760686512 897 723 89000839 582 246 201712656 147 281 421667373 92 966 991390170 844 35 282662994 40 22 99851599 652 306 78411740 783 778 37405479 138 554 276433612 92 302 610288265 508 12 214388901 119 171 966697645 682 317 550620643 397 641 306014200 533 892 886111130 112 548 77401037 668 176 517831901 127 989 991872046 801 961 737893622 930 508 976128796 626 916 834711435 322 424 49153650 14 466 980815293 146 486 747153561 367 987 7955217 131 385 310101733 439 371 770465286 976 223 556853118 168 346 662734811 461 94 427587797 377 912 463363691 468 378 810809656 748 628 176481160 12 669 784033222 730 319 940107550 126 989 148350808 7 525 613304040 732 525 900701774 470 357 83458434 10 80 925197732 956 638 355318007 21 163 806470924 391 972 208512723 562 129 165855426 86 523 350413903 337 354 965627009 989 655 426862624 882 871 209919322 199 170 484282155 188 493 888091832 56 865 363267026 222 674 900497492 690 14 704184050 452 836 872186222 843 984 273990648 16 280 787380854 730 188 635376958 910 752 256178358 333 760 464671262 549 282 57523529 398 118 425915277 276 709 56668960 240 218 63731599 564 673 705695215 720 736 826094864 803 779 320708240 656 681 805135950 241 125 456721906 492 577 760829597 754 447 799622576 706 886 925344746 641 245 190968107 227 563 28090289 25 844 838415749 408 850 899075225 140 103 333622146 331 13 923191648 620 827 697501973 675 597 516097818 772 554 45434316 523 108 271806072 192 272 780763835 592 999 887109514 65 760 700513210 300 442 334808603 181 474 464707085 538 416 745728420 567 324 217919563 591 232 375210126 43 58 978674261 56 481 52510537 854 709 193832170 55 68 941407062 111 905 494601647 866 212 634070452 204 150 240121180 751 910 741865335 613 828 94501165 639 473 53239272 187 152 75192522 387 245 302733776 655 742 892293559 942 96 861031158 262 227 723249274 449 178 777345500 382 564 221420123 280 33 92954126 162 495 714489120 347 164 31089395 538 252 364325623 968 433 756985458 213 474 985462558 379 11 825476551 685 264 261026163 862 428 395976571 599 411 792725690 263 542 35009777 463 830 780331644 129 33 11957552 995 716 640683145 491 292 791428192 637 509 172053455 970 178 230217649 554 947 436116290 664 465 614434742 59 432 184741774 335 334 93688913 432 212 531862 180 22 603540663 582 455 932133965 812 992 141429664 287 540 417200702 263 4 458303758 466 749 843192806 884 588 599352948 752 363 993756880 94 383 106438920 200 528 645789325 452 810 211822201 773 768 309086833 200 601 810584454 6 860 827363931 164 761 455196180 689 145 939790665 822 778 60075709 45 825 722900569 250 881 50577903 184 824 896412864 690 327 221517333 964 935 988689830 962 155 289948952 36 417 73459503 453 433 419546556 83 901 546725706 701 354 589110307 679 716 773711485 36 509 611660117 322 166 110923859 474 163 157197588 369 923 269507744 81 595 888730339 380 728 82731102 739 459 589433583 610 440 492464662 481 425 55486852 502 155 199279276 902 194 758525971 898 561 39225201 652 561 823003386 563 600 251369825 585 33 162979718 890 610 747369465 251 197 52674113 46 34 147970405 261 786 120176075 786 783 124082200 48 95 42978276 463 895 141724954 500 795 751724494 259 739 250643734 156 118 490123777 973 319 246913626 597 385 908995508 7 882 349296017 527 654 244605334 796 715 66582953 646 497 840067561 419 127 594545476 601 289 152296675 1000 512 252580143 560 42 934728911 581 186 204898766 721 938 280820644 58 542 444038783 730 540 955524801 788 179 238801751 179 902 850615199 273 725 325376910 841 946 341972499 222 177 56007494 852 581 283729923 139 53 379881552 154 313 334808955 349 517 540086991 711 939 80172772 363 986 670704182 506 931 172710195 174 355 356335015 422 386 103680238 486 550 757517455 843 155 824668378 230 922 255560045 298 372 480146555 763 301 892823844 827 955 581301597 741 543 193651967 876 256 778873710 930 502 273889357 334 358 821610334 61 475 257842215 19 625 873064901 39 655 4137240 444 793 795228215 397 493 516087772 141 931 93571230 302 855 95020860 864 831 258279335 786 287 891142096 876 917 915734324 92 316 588341815 504 164 686853372 855 357 144870911 223 284 99291237 713 107 896932689 807 836 249147189 793 719 424573053 448 163 340747717 905 940 785835638 918 388 359542804 360 876 412205377 39 786 283974261 185 302 107556058 878 496 60105343 186 539 771876964 133 810 113303186 373 266 307066392 265 806 513150522 427 117 459935721 178 907 210718170 648 554 573857967 445 400 481183062 229 722 138092741 529 229 192190921 659 96 471400189 585 1000 183279585 869 817 741918099 284 473 824418174 333 309 439928121 237 22 782302254 58 450 83234953 334 686 457513330 923 106 792289450 825 714 413281350 430 924 613778699 68 621 634822639 399 177 867759399 857 327 386027928 416 575 686092751 496 760 503349123 591 258 97086388 541 347 84498071 909 958 671592513 375 539 658348836 903 42 126609595 385 97 676266693 681 75 129496856 244 7 965362849 421 287 531322545 188 166 1427901 387 829 393479735 782 80 788979663 404 775 37132479 209 444 448646961 96 790 390028647 155 931 121173318 987 377 201505577 134 786 921166405 732 745 546652370 344 773 563812944 283 69 71024113 164 624 927302876 358 520 549447419 288 481 359908665 211 364 158872744 250 94 805167509 724 351 474505621 823 304 375886107 546 809 375097473 14 611 418649385 335 154 514421110 704 899 561776244 458 985 390842570 200 257 17345621 58 979 272981777 788 637 49594433 469 153 458229605 399 413 543539691 526 795 861512040 426 901 64450482 648 226 659537838 854 274 102927676 39 124 171185690 797 404 401308492 635 39 669945748 791 440 893051484 177 405 875501822 263 638 350911844 239 269 65920828 385 145 156591380 936 361 64504791 897 622 90770401 872 229 669145965 769 237 573354318 504 86 485500251 193 123 590072618 499 571 408535648 444 357 221860082 66 807 466486618 856 898 877119115 974 890 579344772 454 431 640124928 70 780 528783250 652 498 849382122 673 113 122853493 596 77 171741743 497 725 523384082 249 588 411454726 292 241 348682089 957 363 326098060 86 1 140127763 988 391 61079624 15 248 196226025 112 518 448243537 475 550 542563318 727 27 924108656 140 133 603315045 556 201 917865885 227 103 382114740 925 455 92141158 565 475 476472884 51 66 713176374 874 990 597022432 918 483 304941901 320 134 422864722 610 261 620494577 215 933 688031258 705 492 424473361 623 895 673326332 304 872 805391766 1000 779 547270109 171 861 134062902 595 675 143174363 195 561 839623757 703 382 18500026 344 571 126904706 177 51 475602396 619 581 902857874 514 896 84246337 474 547 591297764 465 358 31337355 75 675 730782176 550 948 11919796 660 803 205982811 628 737 688613090 261 659 912955783 854 180 97628150 388 108 28836198 200 69 532751094 121 730 680432971 893 981 7871165 654 586 611466047 497 489 163654841 685 471 175162407 597 532 584899437 488 326 560579525 694 720 367419064 857 869 273703185 218 396 3938856 832 323 697572953 20 740 940687849 119 461 255277296 782 887 189170687 337 893 107102231 607 813 425252739 131 367 91466880 530 186 378422057 932 744 220758951 409 535 759771783 387 176 18551257 129 492 13811539 515 806 555877055 557 402 304353417 71 516 774659487 954 10 553635279 878 858 205519300 547 839 359450703 520 934 928846901 912 26 455135636 304 714 454238617 105 679 928106156 497 149 291037687 747 985 282060107 949 669 141687697 628 619 995743424 305 127 826447317 39 679 546551316 684 152 267738117 293 284 765891729 515 60 508030588 320 947 809891004 459 159 747650866 543 879 86108899 434 622 398966949 375 661 495338294 34 338 24774834 418 333 372950489 239 483 574919032 623 262 225235813 299 685 11375533 666 139 139310657 104 669 449498829 173 900 790692500 276 274 936504450 482 820 434442083 941 602 70628140 50 131 83316729 665 877 795162107 582 760 741907034 881 234 507409924 184 592 627990968 550 775 686477334 666 908 99263001 825 575 513371228 118 8 595764101 113 992 810853283 601 61 382393112 617 849 48801618 126 983 382286482 498 944 881342127 637 569 108400087 954 254 893328000 203 929 768031192 827 567 451421478 344 805 587670048 790 699 17632416 638 706 739585834 644 443 836772311 232 425 25472467 230 70 970386898 241 406 835342150 845 968 570118051 845 71 502077340 203 102 832629961 533 220 462602079 659 174 118896245 197 435 660826050 393 538 459598570 881 211 776595376 445 777 652418993 65 263 95359176 310 627 935802713 145 106 430431882 247 40 190588611 930 3 293318074 149 137 597681955 418 811 21199033 512 975 235399660 15 545 656572998 383 800 803869924 287 478 612040618 601 553 22807511 745 585 321360692 249 107 770265307 892 1 671513898 212 518 789387495 648 915 772253221 661 81 663617913 256 517 912790131 96 242 666099160 774 744 910740157 612 23 74502912 645 851 903597760 644 840 237561102 296 456 293605534 362 778 559827315 764 702 117890590 977 72 294361878 744 845 693936763 356 765 748134196 450 532 507671267 555 999 323638373 148 835 76811428 723 185 967955356 998 491 702770569 45 265 829451468 116 666 245184437 502 856 631422948 709 693 164464757 721 936 984611439 476 931 216198096 875 995 662309553 637 948 100189900 473 615 530897347 41 945 634929902 993 9 938160527 95 943 325876540 872 51 621981487 410 751 231832586 238 659 629951786 879 972 73595099 645 801 710915399 364 263 709368624 685 124 653916647 380 749 305730169 888 601 479184329 900 545 9805462 774 481 844759858 443 306 318271572 634 936 111662566 566 173 756087901 828 814 848752528 877 580 484495604 462 967 410185197 70 131 573813090 820 797 253588430 237 307 516352188 884 183 822415610 92 51 707415375 501 444 672168646 304 697 157240909 55 232 603575277 32 847 47436687 583 69 64679003 771 698 753664036 284 524 680764431 122 536 872914009 523 70 836256713 273 610 812327813 997 891 384244263 257 517 776500097 255 232 710693285 397 315 950204318 561 913 919785164 54 530 605914395 472 313 489056217 974 658 757792250 82 779 843109462 760 737 547668082 824 836 965222815 376 174 836473917 492 785 249342828 676 483 358399502 181 333 895662334 737 784 391179875 938 973 908196473 936 638 6737061 727 721 954510661 425 696 11581299 382 747 304548934 76 175 115139111 476 774 934122151 719 619 226767171 724 671 660242014 608 393 679036192 946 492 41070424 388 151 3364250 706 349 237210203 857 544 264910283 598 996 822320328 782 461 357339645 620 69 384792845 294 290 702411100 991 583 353193623 681 79 538288455 326 139 297501856 441 526 71202829 630 263 750855027 662 286 975519307 963 881 710075898 970 275 136663227 869 868 182219244 92 340 71799430 330 248 941927941 532 935 400615052 813 75 687199563 409 634 572227300 473 226 997135407 7 579 142003824 791 529 820257428 799 868 188139077 908 3 985661298 425 667 183352764 843 898 741135063 174 195 998630629 433 661 715231526 187 861 751846957 791 932 176525916 119 417 644401897 272 417 522731546 246 773 561479145 732 831 70290510 544 398 733843161 103 958 624651403 121 958 464790609 91 434 407677717 406 657 958190517 905 998 380757180 923 321 226690482 55 901 371274645 761 771 735808925 159 776 375591854 29 765 646881046 867 796 962481078 799 751 433555784 894 305 582834870 858 277 142061467 354 350 854221880 326 970 459064675 24 755 547213311 547 946 619610389 589 341 898397490 222 739 731528600 910 704 503607294 262 603 610891907 637 197 383484522 52 101 129576282 990 265 146131799 692 244 164697954 569 789 173402113 215 44 999175626 686 839 908687924 285 630 752441598 98 481 3334478 969 312 728786814 192 932 54473406 512 474 801836025 375 274 287513129 903 640 977637808 425 174 862609732 316 881 295300214 307 658 810692307 701 903 645295722 550 411 321966095 934 337 582227774 694 293 907564873 355 185 445249402 183 705 19619804 773 79 664434799 964 112 888935818 78 711 162624207 6 259 139435563 20 612 155589235 499 51 554362489 963 426 39409166 468 165 503569467 205 139 109072979 219 92 391081361 337 369 426123471 174 667 58193922 656 934 738970520 479 542 303800505 641 376 884095295 688 925 313119667 869 719 74515220 653 784 553505508 514 596 838171856 365 716 827807319 167 48 950031821 157 120 204184069 318 973 981415811 193 875 170226144 735 707 461637602 704 941 568010729 731 846 877542832 897 916 484667437 602 794 296439064 459 359 501028606 110 104 913146937 414 718 616858322 592 74 391779172 356 323 266848096 999 178 733792345 645 23 180456112 844 955 245275888 196 130 800113888 464 107 581967950 215 831 275110772 860 217 532078318 996 20 294590640 99 528 700407341 850 455 994501931 566 230 475779199 771 335 939958083 861 209 256870109 857 652 950348673 143 654 553479085 861 91 927000201 342 617 86502965 398 477 178294140 266 435 931249677 852 170 398744360 295 170 405864083 795 774 859279571 617 953 340398054 743 164 905806969 207 948 850018393 383 806 659131792 253 816 600476109 662 504 394285217 234 165 597417622 918 342 407019324 155 196 858476681 251 967 277705942 719 794 513038318 296 637 448265094 708 304 995127315 84 820 733700425 396 882 776544941 472 312 432647111 444 197 567298799 673 974 780096713 500 485 803602593 551 734 680286872 781 388 28282721 930 544 79499425 457 747 916315254 51 273 724515680 307 930 323531626 497 345 739923754 689 859 610972933 60 664 533506868 979 445 318689176 79 939 799954540 338 824 319942869 363 157 160706577 809 935 700484919 445 510 278914288 921 116 353600377 5 702 696667076 659 161 531666644 520 441 54283620 787 236 751778168 627 646 637439398 637 125 787684517 201 703 584391786 294 314 263192560 494 425 37434908 912 306 897920860 3 425 252975325 979 152 719590171 124 895 13445193 764 329 204388195 796 398 194684514 105 463 892989616 192 658 34806502 194 489 667614382 539 667 219018500 848 665 920400509 309 713 990644593 558 394 632414730 690 914 66843982 136 715 156496857 439 27 366644591 668 484 254019941 649 630 564941204 798 551 115184158 816 513 379018738 154 462 501642625 994 180 950579872 827 372 443831799 821 997 780434242 995 980 50516436 482 325 264740518 901 752 862488743 404 617 95035131 813 531 34532687 194 617 53225839 697 400 415648153 892 240 853874682 984 628 976760763 356 867 63194472 380 1000 260510401 73 101 517933626 878 100 395118370 671 608 191414254 831 897 173834744 872 811 40678533 889 622 221759366 874 72 859690170 61 57 813100604 246 366 908089562 619 954 188600017 806 53 711136865 600 306 231159159 634 383 734938637 402 671 299389992 271 412 169362821 764 426 61060079 359 195 513337791 876 724 364985969 856 950 778839337 365 728 806392970 365 965 264393184 505 506 24570496 631 399 765082721 125 539 74744888 110 448 431363926 567 543 60294185 993 469 412180173 176 848 416518636 135 327 997843330 439 154 595393870 269 575 467930833 64 869 231247182 195 309 368114097 659 232 394231886 77 868 12021871 299 943 774344276 769 715 962872483 629 973 795206412 935 194 692637990 406 519 645004463 522 808 429588111 145 417 152672964 622 239 491648225 799 694 994437838 670 666 155446409 950 100 872067490 55 86 921287908 186 619 480793177 403 813 351959750 851 102 18992509 445 397 448058247 544 862 623129553 728 456 130370826 848 473 51861511 988 684 291783153 671 789 710826696 802 262 113264988 429 916 462733630 120 584 143207680 526 520 325919352 734 385 2149203 822 940 655310219 181 954 309735375 183 9 519052402 910 161 514462017 739 118 109845589 637 456 187509204 845 743 682536182 222 396 540626873 548 602 97377910 741 519 380682451 689 163 773104809 101 348 961758681 917 482 859499425 63 36 889337036 134 473 341887056 766 750 842053183 241 883 79023957 837 378 592109801 936 165 751052222 284 853 212830456 852 472 955274277 479 656 367352392 105 803 535574090 47 154 873757878 833 421 550980832 455 436 985869974 707 514 321146928 698 902 781470980 892 994 862640550 589 315 692659862 482 681 310073774 30 149 252931197 607 505 767503609 736 73 714495128 57 209 95879300 771 180 329717353 277 570 815261730 321 848 292574038 694 925 30713226 980 864 48985299 193 327 476878533 678 570 910352899 654 324 823098828 191 478 282244707 642 820 65263232 810 866 506355821 94 982 848556465 179 252 286806799 441 739 685872804 570 890 816919497 819 377 701879277 71 945 75094597 587 15 15397472 804 797 529963258 265 448 942243883 239 418 566054576 547 557 328434686 245 664 257527512 213 352 21343807 329 907 453042570 54 812 250961966 847 170 701856964 506 420 767347385 84 70 286538108 50 112 571158837 865 931 138211387 653 884 438779294 446 727 561341870 520 474 731364274 256 657 484543710 749 519 116210647 820 194 692791428 536 225 124439201 640 983 645846481 788 791 612163184 942 844 260993519 422 571 285216026 895 525 809143722 15 56 441999788 643 754 652151074 868 685 182440058 34 12 748045301 769 459 694415965 104 357 876103803 982 2 898077716 869 43 206089772 546 628 364507072 840 366 502927989 959 116 399211230 275 927 132959568 271 540 830291137 374 24 458517946 98 516 547861782 987 779 149182561 171 259 740053293 281 933 141139919 131 215 841871015 686 420 668084351 548 475 810993688 346 16 889547566 427 273 290323374 597 30 550550147 455 580 668048225 911 288 363077950 933 903 377774110 586 295 526203307 966 414 485805295 546 6 98763348 930 238 504710337 33 422 660992831 233 763 548761377 70 156 722684156 962 112 709917899 2 932 260610980 271 962 420539103 565 510 330509532 56 582 736869270 373 814 818275735 823 107 770805721 620 92 629257442 166 821 980691058 383 443 811667523 772 782 47609545 617 368 694863980 678 639 120268006 272 871 444720883 961 907 376064791 157 498 354824388 815 475 16456453 269 534 923836978 575 462 342120895 370 977 90944517 521 855 436154682 960 156 707729266 340 139 981343393 179 793 134692741 63 167 91671102 391 855 334452416 626 367 907829732 325 77 246500875 539 82 530177375 295 68 556880085 811 576 12931702 505 806 456793425 96 512 582373069 382 10 201540331 551 321 107540676 495 843 689793584 890 217 201263511 347 764 726875425 701 111 512278965 267 282 499489480 644 842 685311948 230 241 908999399 548 773 487060950 887 313 928807356 422 143 859695157 834 653 938764177 566 100 359601219 395 815 151116499 860 210 41227578 644 917 679244377 113 100 164647369 34 928 447308028 87 656 126897427 608 752 673423451 448 534 924264136 782 246 153447679 342 936 228191832 78 507 863431167 144 875 154010383 717 612 502444781 156 93 351728408 39 427 582249987 1000 342 580294168 498 292 100652516 706 675 115542447 777 362 201779450 456 89 456359278 508 239 266361909 202 978 346711668 207 248 453774388 860 739 704971307 768 604 503848389 804 880 167038989 132 916 397414461 326 280 781534200 440 103 277011339 387 988 767166018 940 888 770097813 442 359 934528091 99 256 398583128 627 798 508522236 753 698 242519884 6 634 584177160 567 420 869741453 299 557 772074435 922 728 627510863 968 660 520989093 592 994 655486743 356 826 677852512 988 685 35303491 106 471 737481269 749 953 460148175 302 733 758310632 327 123 328333296 555 424 758972221 144 568 193673893 18 286 967274356 857 828 798075054 432 597 678416468 704 798 622894363 294 367 998959195 926 701 724409544 323 69 718286090 534 416 899434222 658 322 993690673 597 359 709981285 205 766 980858941 97 212 166692845 120 348 843772303 503 625 485875568 752 257 603065780 801 478 813005701 141 534 846398084 963 604 502977931 674 898 182656678 764 661 343401705 261 195 645509811 323 218 688565553 137 721 95138686 97 707 221620755 530 416 702357399 617 587 904126762 868 863 129972479 869 498 762632429 538 394 330665577 229 835 431459875 737 682 950974438 995 934 18701804 578 785 836113244 377 315 599474767 256 39 988953453 899 981 764461314 389 699 549857987 806 905 447590036 397 417 106126963 705 61 244764976 262 273 103562908 180 809 208782318 534 26 832384500 945 364 693060354 316 995 357555603 640 771 941689702 232 376 102736940 683 719 797159281 407 737 277711512 884 986 392765588 770 506 290936779 978 315 378155368 604 560 898833058 33 350 266473760 43 578 483970615 36 802 865949448 424 647 312201478 527 399 527862762 707 847 838613947 89 962 165195090 616 878 739108588 142 261 586439340 987 114 299870167 825 82 598450329 43 376 821870236 999 259 905501853 23 442 237709814 788 716 186467737 618 602 485087457 273 149 901121034 103 990 265939040 63 673 750594611 759 216 342089156 708 380 278118536 392 455 493378813 414 895 620791393 839 487 588662551 396 691 70929258 334 348 755197852 138 858 485492672 166 16 112327553 603 537 630111552 241 56 168494873 475 269 588976624 568 826 804487609 722 655 683279575 475 66 934074453 751 362 421132053 196 19 831363274 677 778 610949003 278 361 563585594 781 513 863267085 14 235 236746868 227 351 693735675 513 150 290125846 996 574 319991509 90 71 718017620 590 35 240217919 744 899 984578875 61 235 550407696 620 954 164945956 76 303 672289548 786 304 515494697 825 147 656997648 631 577 840238167 444 196 150032442 623 640 621006078 564 980 956646805 319 18 881551156 265 290 697947904 159 559 653228031 355 13 177648762 734 495 12168823 980 937 531160839 748 51 649790134 92 40 283944756 418 97 29893918 169 39 800419642 911 82 910304393 45 481 147837361 167 355 997917129 577 927 789220369 705 701 214915753 915 367 430923577 409 439 266827137 63 653 415472338 642 297 20654863 470 979 974304131 119 622 216078348 9 640 932074772 373 255 885053194 40 320 324883780 929 850 70533502 773 226 796144795 421 516 845988322 282 808 527616099 154 469 125191803 731 184 36906326 514 285 113316997 141 261 341646098 682 909 629654926 721 572 777738716 75 357 532143838 17 607 430996983 473 470 398723671 650 801 621766501 950 147 399831737 70 71 323248298 842 373 339961121 793 27 81473921 650 491 641800584 87 798 198479692 950 613 166509690 893 993 811835765 554 433 200835594 626 354 30075548 80 734 217641851 717 312 781393704 698 251 845391217 182 604 770138840 259 52 397501725 671 394 467245401 854 636 669678715 603 436 167802021 697 361 117027652 847 796 162273032 591 501 422075751 47 733 376831080 754 787 536213932 860 491 488607557 956 975 548229511 872 563 962672530 215 55 458700656 414 421 433234521 1000 317 878415890 54 379 737207102 452 720 9748657 79 221 640865797 536 909 354859337 673 1000 819272639 635 879 422888201 229 658 507632401 301 862 357688634 650 948 330054406 7 37 652288355 49 306 348285471 220 591 410487655 64 493 633594298 814 457 287625320 651 201 897639753 865 805 787716293 549 846 186825006 298 707 74234404 486 664 511186305 56 736 630783673 819 570 221632300 205 864 76389596 942 952 209614321 239 611 996598265 521 157 4839467 117 181 264820622 45 219 873186123 662 947 526472241 164 805 304829168 744 365 803093168 13 396 730709124 229 463 455061158 682 316 552819743 427 590 450876249 204 632 731099072 754 443 94478362 71 492 643467875 719 5 38640724 373 57 788819187 958 289 498528805 488 349 710177724 155 39 664019190 710 906 339771573 622 119 391419521 98 486 679720803 980 696 592773930 896 422 839516344 728 322 643591833 9 64 569688210 126 866 149970144 122 628 57791062 901 686 206980694 817 23 617566936 141 69 24344860 471 1 755426110 977 513 215994801 492 268 393383092 480 121 187361280 166 135 759878607 176 660 178796662 300 431 679874953 568 635 140839581 37 944 527151338 742 326 26807877 103 547 164554466 140 234 839110908 713 158 270108235 780 462 134888953 673 360 208708481 167 18 445879870 45 228 468634361 659 959 358849547 658 907 515622130 777 362 289720765 587 805 440091610 825 744 112740698 412 227 582037225 537 579 865266669 361 443 258010106 923 921 196731501 358 956 577017054 19 537 842565195 462 800 612173288 780 506 298935716 852 393 37120967 239 931 526395079 200 497 918205018 50 112 751099686 74 679 268386331 595 954 473443986 682 995 935055748 889 662 256377390 203 965 39465077 363 838 378450091 385 3 274394702 437 861 812549423 517 738 876064895 497 433 528599474 178 801 367507077 484 877 705668389 409 52 340341192 68 856 415509426 772 713 908310421 371 8 829274484 888 580 991871245 965 981 918251872 906 867 219881445 928 141 348066269 591 266 5190678 329 642 536971462 142 64 727887096 520 319 776412305 965 22 992923778 554 587 657415737 1000 578 896592712 660 944 654090860 147 948 938251271 761 178 557032981 564 755 639996335 228 642 884259380 6 94 791279004 868 863 418032143 90 63 389562174 137 183 893164195 61 888 149791309 67 836 874481149 559 425 95837642 180 228 855663969 194 970 378764708 260 640 751031678 742 227 87147422 378 887 40295169 421 441 678925017 94 558 234190191 836 898 101305816 553 567 978371388 334 627 867848422 410 935 200897131 811 367 52376564 25 430 242527399 630 18 85121966 971 696 252194657 746 441 528984627 790 718 130371667 568 941 949081273 312 220 910777593 513 318 537745830 334 221 155920484 911 311 351176585 632 595 513743514 749 446 298936611 388 644 684962866 153 259 829578266 160 797 815059733 464 227 907216323 377 22 291375295 328 306 793737245 952 646 641152326 116 662 380703143 856 42 801143663 731 474 219333014 367 329 734284469 73 679 676856325 776 838 833647421 470 440 922289948 712 8 354025920 680 867 605689216 256 829 429475561 307 846 595601200 50 550 792024204 599 907 477351315 294 928 486131037 924 561 25003213 23 226 412975739 932 354 316128363 245 55 354470740 20 73 552888110 787 24 532098658 164 44 302559802 732 935 129958695 670 584 53236231 957 281 701456714 390 961 895897567 60 860 270656283 555 772 561673070 417 171 403453450 856 53 485474039 702 507 507895839 228 340 862418713 759 460 902032086 966 728 563498225 715 113 413769140 990 29 953893248 823 319 734341826 64 372 312471254 803 941 471959294 897 131 967568134 737 699 42669088 171 667 18152719 520 571 244394181 865 685 117381306 479 900 932610278 760 617 228077538 583 5 954966326 637 299 297861676 308 99 356631135 211 635 623418956 369 414 882066998 47 25 951355017 606 722 569130717 674 549 714851431 75 366 355695818 289 548 627052972 627 101 295151467 505 550 425832072 779 884 371255824 755 377 827865592 827 114 448838249 641 349 311094022 34 199 838299656 848 418 855478182 52 358 773434547 857 799 303648759 439 954 918858610 209 690 7198249 175 14 138469517 343 439 461717488 661 568 263293553 325 579 95561529 226 395 706932428 979 448 145857890 505 285 218798768 273 732 367945024 956 783 85942819 141 267 479863687 437 133 872502349 820 483 167360484 841 617 352167608 284 463 650158251 234 465 476380853 560 377 276779529 741 839 208157784 408 203 543782779 223 221 795672038 448 169 400051138 744 662 333344399 597 309 656214547 47 91 739819775 743 572 990192302 239 32 296332559 908 675 975521278 452 698 306965370 86 538 268528724 530 76 350199871 75 635 496771513 10 560 128568479 610 78 470695457 1000 619 557014566 532 201 385003543 804 682 651104099 488 102 333607360 523 331 406775635 601 272 633147680 916 85 227926234 135 867 198193578 698 548 684128068 271 371 499719904 628 871 599543290 810 957 355138392 671 139 538935114 900 706 663635832 413 173 866586900 598 283 163653820 453 526 691674425 730 310 237672017 559 148 282106134 488 171 610011555 553 550 71652490 171 780 91669108 422 506 973701720 549 539 958450217 654 901 824932258 291 748 516847218 303 464 937622614 780 764 990764843 471 983 870835895 979 711 743151714 264 325 908136243 948 905 914810349 412 56 708684659 629 110 544370144 793 528 816913319 681 566 717771352 223 17 24305242 807 269 739163207 751 714 589368950 292 697 684992437 185 575 27679187 216 207 190223076 981 197 309912072 779 926 62731182 875 170 459200632 396 780 927803211 71 264 524004141 218 149 490382283 305 625 131217326 582 997 366602613 115 805 889760744 467 3 110849914 695 833 785725283 823 836 341177919 996 863 153562797 453 638 680970434 756 884 337652896 849 607 658551972 155 445 799823884 521 24 344812783 687 658 377109615 920 97 76039666 868 727 947034749 432 691 763544392 143 808 520521548 306 975 44061372 415 500 217300256 349 977 182716151 237 504 783339567 762 257 275187966 792 718 87120540 232 757 236570834 349 299 291788362 106 816 771637429 475 61 254304603 219 488 457144402 795 767 318910478 786 789 603640099 12 849 44066884 417 719 322753254 935 841 644344001 979 736 808085831 995 141 464147911 737 925 313654668 943 911 895808747 101 765 832648645 990 432 123027081 374 331 94377732 252 111 702925371 922 561 424620875 607 398 81656344 401 925 640576924 239 145 283966733 716 53 89864888 652 812 135259031 106 267 959132163 336 485 242886842 463 322 41442600 528 538 208114047 698 123 79744467 979 992 746373318 88 447 14424176 227 130 91459491 247 585 923883067 619 624 795245249 236 532 833028921 195 831 79178054 533 237 868598809 483 286 807187649 545 858 713142 745 373 816036697 510 177 912443112 988 930 651785905 300 345 926982636 500 611 706222063 576 270 602567335 857 616 92484434 33 783 295515217 928 756 495132892 929 744 237094524 81 153 230002286 900 342 730175367 444 696 707233907 368 136 531113193 994 305 617159394 909 14 797381584 913 520 161094980 137 709 253572608 948 594 916122513 832 879 199702906 732 360 862215844 943 729 516277806 492 387 351745765 700 824 288550439 709 514 543705666 199 829 622483160 632 124 211067263 881 889 6620866 515 7 27380544 245 714 533778203 243 14 490337439 787 841 814906284 685 482 907444232 887 546 303187016 424 443 995402187 578 64 695439636 43 884 27250166 747 27 709952823 650 136 987318759 240 85 92319718 142 841 145746394 830 899 450016182 164 446 391778904 391 790 86476073 620 654 482925243 729 165 13533436 620 290 210362640 809 390 32984516 39 6 752873054 3 720 895338983 196 433 707698760 353 227 154432631 935 840 123170359 740 399 286134845 674 483 376065780 885 790 705492795 639 3 875057780 470 166 659640144 243 767 843432604 805 606 956087017 367 909 229154361 923 272 832554977 647 585 106415480 163 405 541596609 664 820 840437819 294 163 835490653 641 338 818000501 18 256 604898752 935 169 500105100 231 58 197002426 555 261 472596265 843 400 277049542 408 5 9347446 60 950 703028155 453 114 109082119 797 356 253543871 869 934 658263884 724 260 977295773 324 908 540071530 302 551 91835571 379 62 802564601 396 932 266457640 420 801 413541891 674 214 227591059 494 580 387722074 238 371 617707312 107 763 46362372 463 831 644310812 637 450 991660046 417 862 674983557 245 949 89561882 472 869 172509240 60 829 5888659 717 163 757589681 438 315 881780032 836 235 645302295 976 950 5370212 283 876 159764397 541 383 467705584 568 273 465556695 494 871 327293752 386 623 380285196 221 767 306329613 625 740 394010590 423 839 187316732 94 45 281553269 109 666 273293201 745 968 604609610 650 130 690301168 607 463 535337109 657 898 740516970 874 236 21398536 971 713 526573715 406 33 982417842 949 75 971091274 705 258 207481133 334 414 630129744 162 179 350272336 146 222 836846818 833 458 698030158 951 885 376252697 432 810 583021163 793 79 438990673 929 846 298453085 335 197 646658892 445 338 398494011 276 354 966360353 732 503 555888638 587 760 694022694 921 706 667889276 180 212 20588217 729 820 170257270 410 1000 686703902 12 956 69580043 397 515 616150825 931 416 789038142 250 312 666555057 358 777 65853443 314 464 252511912 743 676 730911486 493 818 393593555 5 100 22017742 701 963 692694896 646 263 553725808 36 69 201823873 390 538 566557688 207 34 963547788 995 119 180450177 99 686 502001917 565 961 457612561 771 852 817788007 736 895 40367657 96 273 750978232 44 599 803015429 966 961 208538759 704 797 814669061 976 427 790037388 255 511 609219015 414 441 290681017 194 481 688614977 926 728 746551781 798 549 303211934 865 899 961662263 450 598 905926521 6 722 890393843 676 759 577429010 262 818 859609675 147 885 324493877 631 269 45205886 173 865 42638668 585 117 121068589 268 928 377195572 486 613 751254480 121 746 496903392 32 546 348116006 608 78 203787740 622 236 4947991 376 835 77864831 766 239 272377539 141 824 124311654 348 713 242187041 983 145 867146720 86 882 999111875 546 641 534458136 148 930 542601090 886 953 595289880 800 731 668600776 43 590 585957245 249 297 500955983 193 727 335340146 289 782 762107432 405 128 480813882 121 54 512990089 145 16 149228065 123 774 861535979 984 320 763295060 244 505 156525122 974 785 421434899 697 479 32250524 707 439 168322336 394 614 525898940 912 438 499950375 287 582 147442097 938 905 920121602 404 515 964670509 292 659 999892954 729 74 664663834 938 574 27250501 36 542 876377472 846 348 287435493 593 734 416823923 669 100 304967653 606 756 672021241 94 241 726097436 208 348 607544733 963 342 181679054 787 546 395075734 284 926 505875716 273 556 853256243 259 879 291234467 403 696 313488833 300 104 297308537 637 499 305397503 301 363 407556790 29 949 312840856 120 240 873805932 984 725 854231829 596 185 168167432 440 624 803451452 893 197 824162772 812 265 683302918 282 74 964307984 42 572 628584163 356 61 270267852 998 751 821809029 966 296 770725571 597 89 737926413 435 669 425284716 365 674 248151444 45 617 349747727 491 662 785013251 992 74 253390043 290 773 587627813 185 122 280546402 957 273 603205112 663 761 809431265 986 344 29644112 79 204 460606880 669 468 931631433 188 252 998948285 334 220 164876921 461 558 952582193 426 905 305912088 645 689 868322641 371 447 494650505 388 524 73837622 348 151 565418973 853 843 247825864 697 478 792394327 933 899 987856692 958 640 592076257 655 781 700950279 875 470 894286062 632 663 193646529 573 368 489074014 958 813 81739347 4 854 283732694 353 71 501634303 193 894 704225085 477 60 171378462 784 479 346314644 867 591 585344106 939 116 856796700 110 451 60094672 822 269 57831965 247 767 520655642 125 97 892345982 569 864 985598270 212 722 163302616 942 191 869783034 532 614 710241521 731 644 932902629 495 588 340775377 358 209 81705299 413 23 790146829 94 510 209747291 236 129 343924932 23 765 57591913 493 805 521050983 883 605 561745579 567 413 927420398 331 757 71607134 745 517 385813599 981 427 750729903 406 299 907171303 976 632 76816407 996 661 752395083 618 966 193515724 976 85 657328243 25 207 284185574 528 982 837300463 469 39 451728341 353 807 879683607 127 26 749659459 559 847 822409747 329 736 866984757 943 814 374605037 638 410 774374494 883 712 82140378 412 733 128542658 664 874 764169539 515 711 667294708 496 80 606227126 822 208 612115843 995 356 822269336 749 619 727266143 209 872 208245948 926 34 169831302 338 648 98304117 955 758 859809651 781 526 644428739 197 224 809570480 800 818 822469607 297 339 622707381 410 250 580720394 32 312 955839975 96 202 288451175 745 555 763810757 586 306 487542299 841 61 767759249 198 446 438727946 980 143 391474103 276 243 336978339 77 668 747221140 415 634 971744141 970 225 397805542 766 259 730547457 317 923 405529848 641 69 988383412 765 99 896276343 113 377 574711596 675 91 10732732 834 890 906666870 930 14 251160437 337 351 261388062 63 458 104273711 360 610 137167692 439 803 475203058 630 746 508560301 667 893 445500850 651 169 292887394 494 85 986069651 500 287 931572444 503 733 460714191 429 966 808599796 280 227 731844191 697 663 224783594 162 582 385931115 154 150 635162928 433 341 422286475 657 413 159365064 594 63 802464094 220 22 575314155 91 598 281253587 33 443 464590012 667 869 564883918 15 21 508406896 414 967 337054532 880 73 551848899 925 707 992659384 431 561 523737835 288 90 465892600 630 262 828603337 393 790 208945586 32 18 834384525 201 557 631450465 156 713 924682438 817 979 219686018 290 594 697806185 34 648 543860118 236 516 641463727 170 251 165262428 649 269 120461701 814 322 69421483 326 824 810742324 449 812 171320021 139 178 853319372 599 169 106747531 349 79 106556637 533 95 263815591 174 267 280190373 890 978 657656379 790 565 215718146 936 475 547855023 456 281 364874319 559 709 912948530 134 250 855195184 341 757 395497343 566 642 93887478 334 108 545414281 610 581 967682711 952 850 674196855 957 377 506088994 549 160 925960404 59 284 60130331 421 934 846192535 128 934 5244082 377 603 516297538 238 142 576699841 182 724 653499617 947 399 519727162 833 85 690096593 683 771 301086174 646 583 456576576 860 53 125602420 336 688 356008323 515 606 328945639 972 662 911854777 446 935 415581884 162 425 795756161 555 567 674032742 794 498 716228131 178 216 735238801 627 611 769135745 814 217 891400419 387 390 174187631 686 736 511822673 186 67 9138739 438 870 646740788 877 289 620709242 742 964 305390723 518 379 462569987 818 903 698821106 672 742 763895030 138 983 612215836 920 876 733033723 238 387 587453524 266 888 233890866 475 996 224067958 314 663 921748942 689 301 32253017 838 173 529343848 485 458 725025198 479 959 361792069 45 327 815862342 789 537 836573664 825 816 417340465 560 998 866777458 450 746 25137611 154 565 453050303 464 113 268842951 443 130 213929896 497 394 852064695 819 556 211770904 368 830 291994468 790 295 14822213 188 294 195398465 691 312 587482698 973 904 277180092 204 790 882029077 891 999 343949471 992 715 380308443 351 328 84642397 822 538 213336607 268 699 303715723 326 315 364806493 677 419 334294181 57 293 792230801 300 452 282434371 321 613 507369887 600 361 483328217 560 19 659254544 180 528 776684662 325 294 902354788 89 656 57608585 742 827 54112197 664 277 768471518 52 369 606702416 852 21 296205915 831 598 202850512 230 545 860429218 652 518 515029695 420 714 176047376 174 948 462081628 843 306 584534608 230 429 586584969 652 141 588154279 425 200 428140957 654 646 18616657 518 457 786168460 261 433 329790667 753 965 328658278 379 597 109211930 57 809 499732604 777 211 383540908 920 496 495046129 501 658 497422686 321 571 723288286 800 746 830236107 42 951 666966963 754 117 144831647 421 918 809174690 47 90 166276864 314 418 969186507 494 873 387361579 709 409 964376615 593 17 898092726 33 184 668228389 740 846 754742638 712 733 282577040 239 833 335472329 258 38 129677929 412 278 119064852 526 733 249255055 432 87 464804523 455 120 200590107 9 918 371367436 120 190 78747670 196 815 603958115 253 618 202319952 259 529 434313113 879 104 42630671 555 722 585544634 759 195 498942225 218 787 213247155 116 249 296444525 783 36 691077056 216 924 177453680 353 390 289238142 470 524 861417697 959 765 549504616 201 522 21082088 935 135 547880105 696 873 342972394 679 492 173378420 890 909 879242252 27 105 65215325 997 788 917838992 622 120 592697057 416 192 609760093 684 703 354368852 780 424 21945781 861 112 201561421 327 239 761490657 1000 916 239741305 148 534 533002375 739 512 776616719 993 712 226313748 825 650 640302310 968 548 928179005 554 561 443721386 633 650 299043424 840 388 182122275 757 371 857623505 475 705 989296862 836 447 409405436 146 53 372729245 187 61 983702580 88 217 44434180 547 342 425807280 636 217 805070366 594 832 60506170 399 71 999064677 956 495 646732264 112 805 767178336 654 11 732963476 934 625 576521955 616 390 421721608 751 157 614853250 556 251 606638706 41 684 429475412 214 679 672484828 22 329 469609994 522 247 294373986 903 449 531258076 626 25 284727169 448 960 600045038 372 924 235967090 955 575 731428717 535 200 232675565 114 313 869321760 955 335 868712125 163 515 200964013 666 832 786243758 289 995 883880989 575 849 824161711 786 567 332830760 754 982 766601872 257 657 862956661 601 564 323914801 23 7 953491028 5 334 305097725 174 999 434113871 292 55 617800341 801 382 867849952 46 987 411606079 184 442 814177438 342 909 248736682 595 243 754861921 599 669 948164976 890 725 834080338 198 563 795129811 174 65 332756910 488 614 741432342 130 579 866773188 721 591 998443432 844 333 710275010 874 69 7155423 514 150 23248247 1 6 606602856 781 362 701060512 415 99 469748421 256 540 611392002 653 107 35168180 295 386 81706847 383 760 518064473 87 559 104175102 713 53 267915582 603 756 403426634 290 275 871402517 763 293 247921666 1000 869 279824514 815 276 707956922 186 185 411696854 665 809 935331688 781 71 514117576 506 79 977326857 829 886 753143926 594 535 246580336 296 687 118706188 164 915 283125094 710 616 1204693 490 441 997697495 277 501 840705585 736 68 946254247 648 578 511333927 270 72 169084347 576 577 235975441 544 813 175307460 413 670 53580864 760 773 888734340 547 501 368944066 861 845 337022371 599 923 536287588 929 105 574794025 725 900 134480445 585 43 379465013 605 5 238485677 81 19 317723890 158 866 545387834 49 437 113687588 583 606 438488359 214 392 25307509 350 210 159673926 918 702 66315018 767 717 489676515 736 369 108046736 526 988 535388913 952 15 166521787 943 6 918357841 28 473 155903103 799 434 495123284 819 172 881265622 351 743 73708281 731 928 982204583 961 99 555725829 576 657 137158133 753 268 410998735 457 331 716928240 262 69 133249482 43 97 401910865 947 57 946063590 172 541 973473245 667 80 283809930 191 692 180297897 669 915 348722657 129 607 142529769 384 760 592624553 942 218 73047426 884 512 701715843 227 132 630205820 576 371 122822144 274 606 111419869 524 925 171952534 569 83 362933407 632 143 920230611 811 143 584346678 6 49 202554861 564 393 204092569 673 292 854238829 35 250 445611167 649 92 44348186 778 814 19710531 73 62 690511027 285 24 232990331 666 638 123606271 119 420 44542605 767 156 215188182 369 554 691755559 313 315 76305182 884 643 409342545 628 626 795797904 646 179 780872971 905 212 684779690 873 704 315785289 692 160 584478235 662 403 2722096 996 276 613102269 793 173 365214066 316 64 60761061 235 812 115962393 291 770 818889871 44 699 873869992 745 173 295695907 900 233 561961934 608 338 895940128 184 516 698382033 684 410 700053468 267 651 997955464 758 143 414590251 811 417 26922253 167 44 989687395 826 531 768265831 706 853 432303757 413 80 270189098 848 26 429153500 872 953 370770223 599 668 963740470 782 843 502703124 192 925 798729035 141 193 348488254 84 341 752950946 314 357 779544724 512 95 247943485 331 813 392839267 278 358 523916572 993 750 617615175 921 961 419855403 52 497 432598096 747 424 579127113 414 600 288767011 532 274 351689891 581 431 104388077 897 265 764151143 452 463 221863306 162 603 522472603 192 60 606039153 991 333 488487435 236 413 261067648 49 494 308236889 979 13 733965021 660 180 879889964 128 847 219439 575 200 982134600 545 751 390578077 349 656 585843151 995 714 282257972 924 980 773585922 907 246 897447858 308 267 395192678 757 610 398708235 861 33 196348788 760 55 434466129 968 166 345101753 873 613 208915540 45 439 917747744 418 203 698185946 625 153 95818494 894 528 848658356 509 686 642517797 672 176 442518383 992 243 200620820 626 893 831425743 210 327 823815710 582 954 815149932 131 738 364580346 338 564 894888195 951 541 893462733 652 958 23424443 192 688 520063757 887 450 131987976 366 365 710692481 85 139 992715730 514 677 277253008 990 535 211486865 817 922 63568502 500 65 822291388 364 934 737442982 54 28 516789162 736 207 941032127 958 929 890292815 487 830 898329317 497 540 454123279 598 870 671436621 839 632 360490819 594 454 357603085 999 76 127895960 732 709 716759605 319 174 826285003 630 322 866519436 231 155 73125551 840 40 482792562 303 685 262661239 418 599 443207551 707 118 710931465 819 7 369009583 642 443 82360549 593 109 775889865 859 332 934555884 731 821 865111240 738 401 427177619 235 759 136402966 732 637 322264623 997 119 569095904 587 593 632552103 96 860 81455171 447 2 636319403 815 554 918874256 359 222 644466029 332 275 49400765 61 266 306184693 853 799 209386834 207 953 965710838 379 786 503233779 734 264 33340763 559 255 815292771 301 358 364637967 372 553 210799507 16 487 319867914 468 326 202916770 145 77 821486480 247 487 512580518 25 301 82438707 267 875 453411332 767 713 448813013 82 929 396645790 119 122 637025112 865 482 480527600 302 318 427497071 858 415 730905928 117 378 42061531 611 80 93762195 979 338 11626437 413 231 488210505 975 481 871588724 611 291 349511905 741 658 925458122 522 421 747325580 813 325 918439179 920 535 720236287 16 748 103775497 60 870 605392871 969 1 348731592 173 614 31554177 43 175 163005633 276 491 114793037 637 481 992497359 831 453 705438333 502 438 614954527 499 148 624327763 927 841 73322555 718 146 195207746 914 890 847477287 314 919 117363381 128 5 514350130 257 349 853581063 649 284 826264490 253 663 709812069 734 653 786503137 590 166 722083317 218 880 48037501 331 123 185046644 154 411 884484010 337 605 216606798 995 740 107716811 682 452 347780880 762 622 285073266 65 346 508586549 280 495 490410856 743 536 557024842 301 818 958814866 640 827 738336137 249 812 836785825 648 851 990613068 655 381 189518502 322 701 354665870 278 664 89871649 618 653 954414426 473 107 506737486 978 242 266418472 313 843 189442767 118 743 898227704 817 138 523972786 608 661 785934943 766 176 900815698 985 692 849029776 582 743 486014847 364 192 750885802 753 511 748513945 363 668 337041305 155 694 381725767 536 462 184405012 342 382 879126089 198 359 260789931 583 503 781877829 555 725 945696310 976 837 605832759 402 779 429413113 921 888 789429835 85 451 121765041 397 156 996665325 600 344 67615197 949 681 117548101 877 280 351323716 314 165 753888495 137 899 162435815 66 736 462077675 972 384 534537425 726 63 260036117 539 824 117064921 628 540 968216522 549 147 947146652 308 939 128391585 91 702 713974714 135 677 689804772 478 62 546470719 905 593 417303654 223 470 47558409 211 241 792299336 62 225 165214401 557 520 125394926 915 535 281263253 677 928 743909422 605 577 54618324 779 380 446875484 596 902 858515939 444 782 622434136 709 808 273177852 740 86 621435587 439 18 631361364 71 114 356027468 717 55 671102037 306 16 389149627 710 354 922034409 444 768 27333085 658 990 547039769 402 310 13642061 919 317 151523768 821 184 610339117 433 971 169853812 869 92 721660600 451 128 638750128 92 589 705948903 66 601 752959223 504 686 866242162 758 772 280893837 804 969 214304169 62 327 306562146 856 331 155604890 106 915 911015157 606 39 306955629 149 869 151530438 754 978 319421139 432 19 673173824 445 283 656727031 347 352 555999707 826 477 293049226 31 383 331512659 273 67 404419963 307 816 773066695 396 471 248671647 611 116 95190223 818 750 29925045 295 634 224786152 603 212 868705048 683 284 887413773 880 29 563469415 782 858 676861415 798 605 124809412 694 556 11221101 201 886 775387510 247 135 974603605 95 941 417587802 1 432 163090582 389 573 84709397 617 629 945031912 955 263 422352285 74 92 881962641 658 673 749532801 30 401 552375806 168 414 956564787 428 901 550098332 632 211 596671494 169 483 451608057 223 523 566327560 751 142 462339202 831 103 159481726 275 151 701970915 98 985 76714836 791 402 887941665 325 586 87782491 874 378 617845271 509 493 482593667 468 198 762026540 519 523 362829241 462 77 706781481 133 456 159587726 346 158 273808246 922 290 914882182 891 222 928214141 923 886 653836557 398 142 913736531 948 520 876128169 853 816 7996958 93 666 404378334 81 544 555597191 800 474 631821170 502 158 345019260 252 118 583920610 709 688 331523981 223 40 813216136 52 94 756655258 35 947 551052038 569 248 736822586 557 685 900320897 414 388 526117831 796 590 258247257 944 128 610073886 933 231 867336802 154 561 1293442 649 891 812223355 535 937 331120493 826 455 466276769 923 103 415827790 570 386 891984760 430 912 446137664 374 95 846177628 878 737 761025387 179 668 839161521 237 598 864370107 502 327 28976402 115 907 885102076 601 208 652423643 196 776 325281894 693 11 677347567 735 572 669062291 398 821 183151253 82 608 691448376 561 813 171157553 977 152 747913361 321 594 657429616 349 848 689563415 578 603 866263438 405 285 117359949 992 686 592964690 911 363 383271789 273 513 688293744 370 102 10434559 844 832 906715363 893 171 839338730 706 752 883833069 943 559 429837118 997 702 153990399 881 597 861511797 358 715 164133129 660 401 435248963 517 424 723100543 765 857 397698037 273 39 534326185 160 912 161531320 474 930 120654557 808 709 931955378 411 752 51899238 56 22 557799915 471 470 364429733 809 577 278385759 227 102 599917955 51 157 238521679 844 389 815089840 497 601 694344146 295 269 814987160 772 63 513803804 43 690 971782966 542 116 109385904 280 61 628458483 525 802 995421211 294 381 666415700 559 497 138841214 646 283 926084174 957 996 318046097 546 80 463578434 245 572 534267442 803 917 293836904 231 10 130508219 445 26 182838846 989 186 989141567 148 576 334107867 52 100 732902092 184 437 235264068 863 710 618556862 874 408 558158909 195 164 896858524 576 617 817914859 618 511 3709417 287 367 750657 682 848 571455304 135 896 926933621 64 471 443540725 435 454 876266095 706 924 336982444 998 361 237665581 329 883 403643782 960 994 134422745 98 876 867934506 319 854 909280633 619 264 999832819 82 303 562023595 35 952 719186131 68 461 611873515 986 414 61939119 305 891 154090103 728 251 882479848 233 820 864662296 223 396 821288590 605 618 285313756 959 980 191589697 465 837 803318278 408 12 384544512 506 7 607502024 38 864 884973646 869 66 911087294 413 217 917789978 568 200 931491022 794 945 758879751 737 612 108204823 556 948 356294519 627 51 803519850 546 641 61025456 222 998 350416776 403 981 739290813 192 661 64984043 942 950 779233901 8 968 451482992 673 474 922235757 197 183 919418691 573 764 242693947 204 451 686279040 161 131 69253129 700 766 931868139 663 342 894118910 613 191 309616135 2 340 2954116 103 561 978926766 693 493 528894852 899 540 261309216 930 568 339465038 291 329 11693469 419 522 229954417 299 201 797092314 947 994 666888901 885 129 56695477 781 131 530675277 706 78 116204842 903 671 246261035 348 399 63680930 427 557 584118796 23 252 157153620 305 961 178430240 809 209 54396597 379 542 962306096 922 364 912073014 886 143 339468303 753 554 3165354 750 42 199262380 588 867 20485210 210 417 363052045 805 184 900974441 557 2 678251198 314 627 809695357 69 508 674305085 597 359 184948526 280 131 472513142 471 542 278034491 65 492 992302238 816 841 791176812 583 834 369580006 649 300 937315417 815 991 994802554 996 824 466596041 444 439 788349647 18 307 880439543 437 209 978440861 749 852 43409399 333 229 135379376 401 843 342471556 127 219 432184266 775 831 953981476 687 792 489017848 250 839 476161354 970 447 752949380 582 542 765536184 219 24 165401738 815 603 975694619 552 64 828900588 176 709 130057806 285 701 255869657 390 813 88325549 691 629 429814431 518 933 880362417 253 246 412297004 599 385 74539389 879 850 281741521 860 517 638914906 145 760 427138462 110 521 962629568 194 700 405332661 206 590 227725223 589 669 745572706 777 187 22123488 541 206 734915944 26 783 835671098 981 994 816859588 808 588 588846227 981 350 190669647 431 808 847309510 954 668 796309529 518 123 421978653 592 495 750207834 568 533 935144999 173 673 539234347 905 673 943450965 59 874 211889994 297 197 593104855 758 524 738724133 170 660 287280006 306 760 216113635 147 277 662820305 460 903 373263763 190 803 775385424 182 266 26075723 901 934 164043791 376 566 874475081 283 15 872674222 945 902 573771319 128 985 305696143 519 558 35649690 905 480 856558792 407 478 257056152 986 830 588821645 375 887 511889959 570 692 672727178 684 416 461546620 76 732 573227778 380 252 954210602 150 502 676832779 567 509 646422933 764 174 253307516 489 777 964838403 929 576 445544169 730 847 912104226 396 235 369080129 282 444 831815535 514 789 89445728 158 791 864770626 543 309 361516933 807 800 529015316 735 32 771585867 981 930 800899997 744 766 356495846 997 434 620454215 329 979 883745403 987 248 898116323 928 944 83301391 220 932 356341143 104 825 53980752 916 724 557899550 519 315 492063601 490 427 887874091 491 95 718523909 96 529 844801046 42 215 599343864 495 556 922401977 711 14 59159476 29 288 204495358 984 244 941802678 317 257 547300386 763 516 669594248 304 80 890704019 688 830 565139455 922 420 621073948 713 301 190474663 540 844 764718649 483 96 324860896 393 483 128912087 454 307 977740228 367 156 6979866 494 282 738801238 371 578 8963573 923 892 844149249 527 246 17287234 235 730 75322742 656 828 193654109 628 606 347329678 811 807 371701955 294 28 362951304 887 826 918793615 728 408 436846766 437 161 711391262 947 551 2352479 760 612 654370690 641 503 320258485 882 442 53477174 699 467 139992054 203 245 782563963 75 450 352157543 557 32 289254537 3 324 263427784 388 314 382131500 37 864 746753023 562 306 172570962 625 277 21616112 261 112 387829297 358 666 343113297 269 409 264955607 907 933 387585721 235 64 725694805 617 860 418636781 562 443 638251813 950 123 499377543 165 480 597162248 540 166 813046300 433 189 536357203 653 644 315286463 121 775 197808449 98 1000 83672415 94 849 138080997 528 336 41729521 993 618 821682607 138 835 271984387 396 511 415520708 960 193 528697897 876 786 857459335 888 356 876707679 216 567 58950030 778 314 82516433 407 987 874469145 329 316 788031951 303 706 208234625 671 143 335155270 736 530 332751875 611 714 379458103 485 954 293902928 15 153 282609159 1 13 575643729 221 528 893082635 934 837 608582722 173 417 324352671 162 196 843745496 654 771 495770337 119 377 946391369 127 98 903825028 970 27 449573829 790 482 414603557 873 566 658049462 893 748 153422707 889 942 269699039 419 183 529397356 55 530 973557872 271 299 607304770 868 4 817913224 857 219 490748533 976 556 398914471 101 239 127229454 750 901 191529471 596 440 788580874 516 212 782333422 848 653 218658925 702 604 668806177 570 377 275494397 605 128 929169615 267 156 508744865 778 637 569704739 297 493 604574670 887 284 770803620 108 602 555809751 857 670 757799523 132 806 551252001 273 647 228224309 742 883 150868541 319 199 242556054 523 244 9943964 188 556 41263368 783 226 396640960 452 541 403430512 323 154 431396053 422 442 539725084 765 533 895810937 224 933 933532998 41 486 319315225 982 886 732629721 508 591 722517928 4 150 975520955 862 491 224419001 494 575 449830998 306 758 725106209 30 581 192851561 284 248 712748354 23 396 167975556 751 942 449659939 550 531 89330714 297 239 537523174 758 566 542810410 885 839 882478231 210 862 565326480 560 412 418776830 873 567 531935136 307 461 80337107 949 841 234389370 3 648 755930627 104 259 206045642 386 857 174349654 780 43 419337799 911 793 330467771 857 1 909985698 878 957 533001588 653 341 474215251 295 510 10853838 896 448 262703326 237 898 843375218 109 788 368549156 863 732 285507120 85 526 240241718 59 307 651674971 686 582 396159089 141 442 642373395 896 981 326471156 424 648 482846031 408 75 295188020 148 944 845192157 782 271 542282750 867 207 754533409 360 346 587744470 712 675 391081017 749 908 331138952 12 875 84944813 983 641 987733983 797 11 472946139 189 853 775300323 9 251 164364784 885 755 623845381 264 401 742659507 760 137 353536173 906 918 820303804 707 104 679891445 209 719 973312498 222 76 54646634 948 809 712406745 460 891 643492725 174 346 385714862 312 7 970696996 644 294 257554650 718 319 834304145 352 925 629155138 226 412 642408706 947 579 604544283 718 63 549484440 837 643 114392561 717 574 545717219 581 957 492004079 581 120 409026296 824 268 401724768 973 718 380077406 618 84 377954213 806 670 743199938 748 600 716703019 753 452 963529140 663 926 237471503 261 281 155011381 810 828 873986458 481 171 91627034 325 425 741149708 432 73 225793012 164 528 484080099 656 45 178905838 507 766 1711429 882 706 355641915 78 939 530195415 608 8 390510785 607 443 563711444 150 772 890869095 951 750 259061703 344 350 298818056 565 928 969870098 671 79 272811878 352 543 183231312 98 743 683858290 927 123 562959913 866 906 608287446 439 239 225059697 586 103 740696272 171 357 833174306 125 912 435551174 873 44 303003645 489 304 433085374 741 171 882955520 160 154 107032024 723 652 884687609 291 180 863320905 155 248 439020060 41 299 529519657 881 461 116966477 176 461 309356314 234 996 935542324 482 301 666259388 873 38 246248932 797 505 176109344 272 532 793010426 623 266 384486156 81 577 581771235 912 981 868699139 464 575 848592314 509 178 515933224 199 136 870298272 140 41 358180473 270 945 589170495 426 209 768315703 9 133 847152417 876 444 890515794 529 524 549715504 164 501 832493855 566 214 124289332 293 754 454103599 775 500 201948827 931 54 494846198 724 139 175640389 408 847 702880101 587 957 250003540 960 884 241705621 349 207 825867151 692 164 312574294 281 111 69169018 278 778 437065818 509 955 171729342 302 344 981418208 663 100 582390845 595 345 782348008 111 937 657818009 84 621 635907345 922 187 392478870 375 182 600160941 12 196 994452660 83 898 366841795 979 855 448804658 83 296 622504372 409 375 285108619 476 350 894422326 813 291 83934147 429 887 356456775 361 580 424844706 814 11 547482441 701 311 838534382 962 575 378485395 333 856 42878067 526 463 502148455 875 166 925217992 106 262 645799581 87 35 198592587 596 355 609647761 226 660 311583321 69 759 86443137 230 284 543766042 820 510 904658101 287 497 173434424 974 228 53563385 928 652 366868310 818 298 690706852 185 893 688088895 718 581 220997406 527 652 400851875 101 662 755429590 336 904 368050103 603 612 421914958 50 431 612335551 771 308 267901304 23 625 78844560 325 795 47827593 278 226 197350478 47 42 113367675 552 372 365257645 613 744 399688246 312 669 976580643 499 392 298945488 496 645 90425606 579 831 179445587 418 521 842848141 828 989 143034300 240 338 5592380 334 214 718062122 218 636 155382545 621 183 995398990 358 907 2543266 238 909 831487160 639 953 701546028 347 327 389082269 274 566 857830710 859 386 964419179 453 690 898715150 64 28 112141069 642 16 744067533 247 883 135519544 558 991 368760302 748 232 251324145 923 893 709162342 932 612 924883936 29 685 590613085 983 672 431525643 569 700 495351439 834 423 766816045 179 494 568950722 391 634 967946480 323 226 641371086 264 257 401867331 722 503 595561362 630 929 497224729 904 143 111090550 617 675 130488190 340 378 698885164 551 959 727709792 558 399 373080433 662 250 877650957 98 627 153859668 370 628 117271547 268 941 69458446 717 411 951490538 777 736 51831250 344 380 280008173 270 516 823406452 177 287 400141687 688 928 608620590 739 641 499193828 585 408 383870047 638 11 732813820 678 440 715047024 25 514 734165073 925 238 669712924 33 487 821319190 182 820 477094346 45 622 251886592 696 300 242086210 206 340 959611318 587 873 232957928 56 85 287850853 47 963 172455885 712 884 824248649 37 948 568085111 207 355 105559516 749 406 964621286 884 654 190984580 267 243 234904174 783 129 19549696 572 401 610569182 186 458 590239006 927 93 820187435 877 608 759459807 604 15 388908598 457 211 271718436 15 561 63390182 6 548 334890870 313 749 155085172 696 374 93790217 152 394 461517475 336 19 814909287 849 936 594628280 85 243 578151139 841 866 495066158 657 889 537910676 343 208 700407177 200 437 552485953 441 751 832087296 498 248 482707587 892 320 222987573 388 480 304379714 501 802 919048662 252 469 143099400 487 338 368719849 951 536 107786658 717 105 194228145 819 786 274022073 545 783 298084690 926 405 525095882 283 352 454538347 924 284 684722249 19 322 773006028 637 451 243765609 581 46 3450520 629 718 160307648 312 399 703717548 479 699 380276344 221 916 510846841 699 384 938166341 344 510 334832630 698 361 924106459 590 2 514195182 607 950 588292293 891 369 900130068 680 411 482039016 682 193 638373360 760 685 467967386 499 679 226604381 845 285 997675919 666 670 178904096 679 508 603664772 647 826 521411066 194 80 945097203 769 618 122683503 917 850 581441666 983 404 469728219 751 335 960952969 736 766 115474766 447 595 178261706 270 793 588058754 354 178 146750736 985 715 14474146 599 28 830418400 725 351 591660571 949 959 965243531 734 336 98892376 492 155 309166594 555 686 182066085 399 227 940427598 413 792 845973881 631 33 728810243 920 176 112446216 148 538 962123970 273 698 204237141 247 887 689159666 431 427 404171239 676 502 641098037 474 723 122657504 97 985 323304820 563 754 730433747 981 459 355234990 799 536 723976207 595 617 210667838 277 682 755995870 533 694 439669175 519 785 440659487 218 639 676703449 212 119 484807467 512 801 943815801 999 906 86957801 910 922 854118566 919 688 871883175 748 349 43155742 4 918 131394444 465 342 307389970 800 475 202936113 235 894 143225841 688 315 853001703 12 410 73472432 378 563 95430560 703 206 10930144 694 683 257505020 595 158 828159340 402 596 40270855 913 696 743979605 181 320 627023763 557 554 113336021 213 89 571773053 541 482 300443545 895 264 296858384 545 497 522653931 605 213 848052037 207 637 728921 950 144 574130784 565 645 114080867 490 270 124082528 43 366 881986633 270 478 468768133 352 188 477136992 846 33 434093968 723 640 476522979 995 40 193793420 970 227 139248044 811 571 915184719 27 114 777457123 359 650 554773649 243 97 724905992 665 922 941726093 339 475 51959037 754 415 526728749 359 722 956153193 869 602 662842048 990 363 881382364 995 81 447811873 175 330 385676636 198 839 503496959 490 817 665978679 562 775 512903143 848 471 650761340 954 429 852586780 910 402 796640059 865 838 50040656 503 620 20809845 418 892 742921500 172 273 190684490 47 612 418179841 145 231 815339613 426 957 809800799 974 558 573942094 574 110 4983904 605 537 126159358 527 60 824477404 494 194 447322933 816 262 385339304 580 378 183463010 952 619 269814447 834 373 163748240 164 833 137807526 953 960 400513385 86 755 602006062 393 858 317470578 394 619 82627822 547 912 126632828 284 990 578317169 559 864 67705209 237 488 112024009 953 324 892314395 914 125 681843730 463 196 46914805 518 876 101806008 600 414 75825953 720 296 757007303 609 906 126155849 574 447 133426133 804 906 921267017 811 329 489919161 223 97 753276456 1000 58 563491480 275 228 163617302 488 515 446439187 458 51 661860144 947 693 988878443 100 324 534725022 763 878 986773614 42 719 578078709 929 261 881447201 547 411 778188478 859 712 884851996 832 30 570686237 118 472 55738863 474 726 978180236 601 449 50985360 429 45 310464054 960 551 792225415 847 576 197899758 793 846 967047451 261 122 210137764 727 699 416313942 517 955 166301431 630 340 408543437 596 698 88646845 38 557 138396015 693 319 389788338 404 929 471926420 333 235 428108041 171 77 246376146 889 210 32582190 110 101 719586121 681 23 600379873 355 167 220043015 795 451 886323330 896 78 552480581 622 555 166923379 991 289 924088280 744 46 128871102 993 850 130321898 429 709 173029475 110 838 916232303 559 150 26421584 604 127 827162919 358 27 439713134 244 540 605749030 305 338 970296708 153 35 575643808 639 139 440535529 304 294 430682391 859 121 65148202 236 987 143694756 882 737 18764040 842 437 685742534 421 772 174005082 254 192 465248046 961 859 467736576 333 84 276205093 175 497 697171362 452 625 932750406 778 883 256587368 185 236 279746765 667 645 481078556 631 822 731489284 3 955 618366127 109 855 587555997 86 769 260526972 257 786 946256260 684 40 349659728 531 527 134660949 661 61 807030963 639 951 507944878 936 273 95771672 594 866 737989667 188 532 206393146 788 175 685390238 437 651 622715780 101 128 762460071 357 386 411439626 593 285 743176690 29 786 419449681 177 154 362543035 5 649 437214090 270 475 543857467 530 974 381557604 407 540 677980911 336 326 102491719 426 201 462202734 408 562 145740418 842 76 850535299 640 558 840009899 322 537 8650359 587 673 308595003 740 902 513306467 193 55 977982119 687 47 477766852 197 491 786860886 503 311 936014835 560 487 466808254 899 101 648047662 754 143 70369979 302 868 844268104 916 896 401237818 874 284 87643022 760 414 271200386 713 926 105035535 527 318 571705898 275 469 409674375 295 153 691095220 890 495 961829614 834 319 367890010 727 911 297346898 924 626 280996056 879 427 714653234 319 737 514703846 724 562 585541278 762 468 632315932 927 858 51828787 270 277 95589512 804 386 899686749 83 39 778994255 930 612 990410376 478 870 323078935 442 206 508327093 499 206 121119629 336 630 904094548 630 441 552746102 50 140 888275473 887 998 266588369 543 865 766055872 272 812 459133346 503 337 417275514 886 328 880832056 21 57 765270664 711 448 832130811 377 773 957332026 493 584 532373362 61 642 847339895 685 434 456200313 213 582 868546187 462 211 847802432 612 533 765486875 838 13 771549688 774 838 731912631 324 884 825359952 801 293 705617917 101 792 740060164 862 771 946631588 289 803 69616829 875 850 765789686 811 663 516390932 941 890 495301825 941 52 712769544 390 351 197284060 362 521 613278538 174 430 944699575 212 612 910735234 250 361 528053249 1000 675 641731311 753 874 7957948 54 364 383513176 367 868 2384805 549 114 786894596 24 808 96500130 350 49 303779857 409 979 349876539 807 371 778149026 550 59 846148715 734 175 745315483 162 880 61667084 655 274 739384080 965 753 672424177 891 889 183444910 199 714 692199110 2 552 614207100 997 169 981389428 326 150 698695290 825 992 139921795 180 199 240570722 196 27 318650341 411 251 4298766 268 224 517474327 96 682 480527684 304 73 367254923 671 306 174351121 523 207 51148521 249 123 105328699 1 320 2775888 332 465 752712089 866 928 489186563 366 319 967065570 266 993 98985321 208 786 236442385 288 943 612169656 841 510 588083773 745 151 430751430 857 383 822901347 301 655 286264194 960 158 836092982 859 135 658755224 928 523 968773613 72 216 230635976 23 589 711616123 273 480 409725448 984 803 227178099 701 832 777414885 78 6 468934189 706 920 267557372 705 513 447087992 135 147 77994655 413 732 577032634 462 59 242017416 932 674 405939183 593 597 95345374 186 940 416389463 383 865 997675681 381 567 576399446 248 145 990167459 528 458 420125887 90 642 172372150 790 976 513886762 76 21 267028303 826 427 859676002 85 731 710449328 191 121 640270684 163 670 675399654 805 571 13425159 540 415 280245920 287 667 879417727 95 167 438887438 413 552 341049299 940 161 744933166 799 511 857524592 731 114 828846770 711 721 864720282 428 948 546540780 885 806 221930018 894 971 374038941 85 24 277637606 262 346 575025012 98 313 425298643 214 469 543234234 175 469 899977908 652 10 704415960 4 593 369064039 496 994 810989960 599 646 665192659 493 785 75166836 392 375 302671532 897 360 208580191 99 857 222534972 88 906 994110942 13 363 543519089 874 446 257408212 234 129 381069036 86 284 798668127 149 337 408858157 841 753 539214539 593 44 202791767 379 114 360409550 295 558 909117486 119 424 386339657 535 174 120001390 23 47 638623092 807 755 454392427 348 387 690115282 680 108 447406917 909 110 629086280 263 684 614879829 769 229 37209129 542 99 784736378 460 428 338587512 157 892 39611101 339 995 326594505 734 224 651207426 304 33 148037679 128 93 614478522 225 679 418238228 411 674 784928542 90 345 973876024 246 951 993431994 473 461 437927151 990 251 254783615 649 213 716959897 970 455 199977463 710 909 888798985 158 675 126299016 960 333 224845426 973 859 735667193 341 883 895502395 213 357 348601634 549 787 573876164 553 570 863951596 270 960 412426887 790 680 53290030 912 970 62278869 903 202 852789704 412 693 170248068 316 985 398310244 262 385 720507915 441 597 652154292 290 615 995303189 330 461 991060750 654 434 954957426 193 128 693624645 141 247 268210689 213 119 511182587 122 95 870887475 522 477 347708197 883 787 594473717 611 95 85141836 521 343 494165565 858 745 128830773 387 103 422763829 498 82 752956366 163 878 797596697 732 455 738309742 113 137 64596714 939 218 602443998 5 832 858454016 475 575 40607883 507 675 271459016 336 300 266138324 57 380 364585863 609 429 870652520 791 326 29238994 457 651 37421047 52 326 475133265 471 349 980501979 390 725 90992629 549 522 622213955 630 1000 692024534 52 655 461305624 543 74 945681562 537 805 234207815 960 921 904183079 673 472 129184114 64 594 729966595 76 990 45622046 43 836 849480880 100 756 969039575 653 211 285218606 209 976 90630854 84 355 84780362 177 60 186014285 943 27 637044003 57 990 962913022 389 856 324357007 706 743 366861273 910 532 829146173 868 558 590732847 579 486 614285111 837 969 825029189 268 491 833319820 976 220 708902239 746 457 249350749 777 298 410972859 423 785 771781105 845 50 951908117 444 458 861447730 58 392 775966919 984 884 884447662 144 652 322530029 366 990 249157984 921 195 200229532 7 469 855830013 733 57 460692642 768 680 21127061 932 299 446961396 249 257 405401417 125 161 906586279 966 862 964416750 1000 315 350134063 465 630 566285454 683 747 882297198 630 869 141924666 228 836 858763083 140 728 404153109 79 417 760203235 274 723 315102744 731 67 334203008 617 611 737650565 803 664 549452501 190 305 919889500 368 183 62238518 38 158 196767970 312 211 561938843 472 870 946593084 649 614 633134250 919 744 325422241 479 420 93272546 795 178 181884271 387 589 455690055 378 263 262608023 843 627 872189237 560 873 753403219 237 786 906114149 978 1000 702065259 67 229 129515749 663 170 960423766 561 16 321507018 407 46 963427556 863 43 528518019 978 380 769537376 895 354 819708960 725 361 388868718 961 494 38909989 578 601 9985702 47 111 246167036 335 95 466911779 263 19 681720916 257 292 316817984 830 406 459558523 952 802 4253792 306 419 732444092 625 133 550983695 416 397 63920470 113 69 597464137 387 490 938662907 66 859 614561232 587 286 578588262 928 354 339670942 471 668 368715864 701 576 905967105 885 965 289047332 592 682 511269554 213 988 177654425 223 517 779048929 176 378 505422182 291 453 273456823 468 152 438394723 853 97 214034389 181 653 633521952 582 434 459281364 840 330 150708250 220 740 388145384 426 267 93070761 463 320 95234640 689 834 970782836 288 776 951133320 275 112 802704797 152 186 31943003 429 310 844693175 638 379 222544987 739 732 588432677 796 421 176422780 68 112 915442103 717 257 515035735 257 624 277629793 65 487 778217499 215 997 327975371 563 209 580942039 153 752 669605424 363 116 806734675 485 368 229134755 797 620 491176122 426 297 110837389 470 42 549414066 939 423 264663412 25 24 750545974 230 669 735415035 508 107 754678839 410 955 314364688 592 164 257792756 671 228 438980692 22 149 277046512 246 749 943715352 732 985 86137070 987 677 960542442 362 412 469675007 752 29 139573357 933 262 497199426 253 243 700205742 80 479 681502177 631 500 164759914 229 550 987931567 822 853 335784168 483 467 730832541 671 546 472223753 642 958 659404373 861 204 849006649 186 586 791968383 600 279 112025966 961 463 35043007 823 453 919761272 88 760 355486173 259 648 321702010 554 214 217579755 4 366 728610440 249 205 507384481 511 205 835027380 285 175 576061617 76 157 902967517 264 704 3478257 358 290 599909990 255 141 482040275 702 649 906115043 440 778 252171403 458 553 55925460 99 265 253340140 563 157 325394557 664 447 174259831 888 293 96744405 195 702 360548598 711 258 928605805 767 505 288927526 982 249 832433622 852 249 924995924 869 925 778894945 741 263 946169302 86 133 886628396 376 951 550158014 248 289 49028691 493 18 817430588 218 789 673347706 879 840 217161131 96 640 938977006 754 967 404433608 964 679 705401959 902 745 261427045 656 475 605722109 110 978 76236608 773 458 483096006 175 270 729162369 889 201 207851735 949 221 873705497 997 857 72914089 1000 259 842762077 658 924 801885615 438 553 818699435 602 374 53702011 224 199 767757302 207 237 426933718 381 91 367553547 918 348 108915382 122 145 729311795 797 340 762065658 880 920 492312387 563 366 176709958 396 978 537325651 579 413 173347629 507 149 241117904 440 239 769520665 704 162 25809154 838 991 667094329 427 762 481490611 539 92 411637265 145 508 982125533 25 688 633905572 243 828 544977940 797 460 477766387 216 138 884981253 63 614 959304997 597 548 437655250 28 720 326634819 871 84 380393758 948 25 961613835 285 172 917671491 287 813 504394614 471 30 889186625 138 692 94913282 960 83 963932175 273 920 792456988 214 400 447429349 879 365 948265020 289 682 531883521 478 321 653224766 293 859 511247449 614 705 326979907 312 576 314546495 123 338 919752169 487 249 208664629 199 885 742981153 209 242 657886270 167 635 991858840 164 691 781791434 113 202 107022164 13 666 27067355 212 87 752136396 442 71 12885781 493 419 651417491 827 363 268569291 558 422 550679598 128 332 192534722 374 594 340379729 589 670 894877035 935 102 709499963 175 867 734491085 985 415 968225362 296 21 585787966 849 792 574813875 896 839 217385511 59 360 625286362 364 909 992347446 222 992 495686911 599 397 383104675 856 908 112693881 883 187 286298322 644 912 806000657 978 994 841952476 481 513 366794840 841 925 441567930 206 819 685788925 263 921 230043391 480 809 463169329 878 379 352624428 620 913 513457256 507 945 803794968 563 675 40617088 798 157 863176380 406 550 589647512 860 157 501988669 512 637 684183340 971 565 13285273 318 38 360014983 578 890 418130709 495 34 264684446 248 664 383566848 861 204 668611789 880 952 797231442 767 580 673372963 372 985 963954522 514 479 587183261 215 579 703712901 206 285 566635672 824 531 604567117 991 647 178166569 346 490 612874338 338 224 217289408 130 439 29533702 723 767 107719235 454 301 530972902 574 599 682419215 74 449 868645136 139 981 658690247 801 499 355218253 427 570 765501007 889 624 114039233 434 705 393645455 829 475 91632545 729 669 481017470 894 228 373608939 729 42 988942738 472 801 392938798 379 835 6650347 178 599 995130770 451 179 90107141 573 487 135903581 901 360 520227034 473 29 798861630 932 882 473298339 678 349 733051076 337 677 423627413 779 512 673950749 608 148 126230599 742 912 202035378 411 511 285189377 828 889 956448607 437 143 197854478 982 449 9882319 506 685 831261267 692 698 264613469 278 239 470639073 140 980 870444675 433 606 322720079 889 115 234450539 105 255 240791764 519 636 691292399 470 764 469126969 607 471 720766476 329 624 187090754 995 802 841461475 510 460 708405781 704 401 43845075 3 370 471532306 907 130 671203894 504 293 443493242 156 299 365798219 780 231 662514627 144 454 439578464 784 401 991376166 689 534 5234629 234 644 260915979 196 147 885412368 231 54 716021797 607 773 32434459 180 262 14512895 832 22 113355660 707 764 614015416 322 340 397165460 420 520 894821344 719 504 123663705 169 765 5180512 909 357 171869424 255 107 569682238 612 661 729438880 877 626 991489209 298 152 712121855 350 106 518464788 879 563 296276953 988 772 57314575 397 653 534597641 267 183 570280598 644 757 664497883 611 698 244039643 971 739 294035574 997 505 544050450 53 794 956543519 894 826 447528001 845 496 749120784 489 868 290762677 35 179 433626140 446 261 282803273 757 895 230057831 57 721 408225641 198 968 363729740 944 799 632002216 662 479 816249803 231 950 588074888 269 148 932742807 793 94 303237381 707 884 783219771 890 68 793449340 48 990 594365516 510 644 603725243 776 406 293182730 13 194 630647146 668 782 136079200 302 308 18014796 579 741 973632115 844 602 351259137 9 740 49520399 268 290 543871242 137 45 383577328 961 899 44297496 576 608 733785130 135 507 919659125 469 817 392843596 171 265 530958805 630 852 478168938 225 806 983871232 876 933 229376008 87 462 462112315 545 595 182426846 473 532 515119581 900 960 483503304 399 823 591719016 412 949 648682074 462 244 506960094 673 348 855294636 37 139 868907949 370 778 434257625 599 846 725201624 659 57 925579199 896 541 473034642 512 872 205165996 681 468 144741063 135 640 688160863 872 564 128720138 439 104 986723901 921 723 464838734 213 970 610092451 757 879 379513624 662 548 284402882 396 214 891184582 384 679 462731526 179 690 814038272 445 829 349594389 426 867 517435487 48 325 426412267 341 59 522279058 357 638 224160801 506 746 866115784 576 712 492820017 473 934 469197201 783 928 925074502 207 515 155003221 751 536 603601055 866 316 655895325 346 509 327137864 644 254 678304976 998 413 501091140 484 234 944380293 315 866 234555279 907 493 240942838 466 23 529721307 877 328 788282726 382 684 278474599 884 858 129186808 594 259 696209274 92 445 493173429 475 576 70496580 296 977 645035949 321 572 686561415 407 213 724456933 457 502 364701126 65 621 571554100 191 954 942534804 556 3 166355848 562 317 857849237 377 452 861731593 25 476 872005487 959 811 587642307 659 400 878816449 513 468 881947303 381 906 159226773 146 997 14996587 42 998 441086666 148 222 638340770 955 233 70261824 801 452 735356334 891 567 109365692 117 423 515392102 59 576 377177851 253 602 177379547 774 82 314608403 843 488 578302136 969 190 827851968 695 765 871534641 272 765 153822237 781 661 963860827 333 667 445247609 896 848 164417806 474 43 772070045 128 963 584427006 902 1000 403140719 534 322 329553207 49 673 837964207 672 182 567191867 43 285 520561481 865 165 300528370 927 988 796760340 262 841 400036349 627 335 382370689 406 363 26429187 511 832 975083346 278 123 792156214 452 849 579314659 612 134 162239340 749 965 157837783 371 920 672082858 217 149 63313389 751 143 20221711 269 771 421083738 877 55 895844077 915 265 93357402 222 736 135659403 74 882 113900967 800 494 451073445 421 252 441295755 797 854 411780238 314 110 382056672 946 133 465985818 7 995 187007712 977 34 974942106 644 866 468887288 483 216 575222423 576 124 328892553 742 409 849330660 42 535 933052420 983 501 576061813 343 885 837052174 967 265 75399491 408 941 325901934 241 883 845448041 166 360 100263015 643 834 425713909 527 200 874554747 959 973 238645658 354 993 773854553 205 902 766463604 699 954 83267634 365 947 546341381 846 941 767255966 693 956 560374838 77 273 35352493 314 155 666082277 835 386 23440722 203 658 146497626 186 548 8947219 767 172 160574116 889 326 776144015 138 721 730911806 743 745 257094563 766 574 316302810 984 730 798654197 844 330 378310842 278 381 620704223 64 625 17586581 983 576 274157351 963 100 555846252 130 571 166140714 650 825 671391101 809 506 37451755 499 935 486854492 349 586 528497674 760 909 83412019 736 475 384003810 924 258 505261361 275 795 73780174 655 582 455443833 561 238 20957800 562 988 84985335 523 778 211893517 945 766 263914129 490 119 721391200 498 287 220477330 176 700 489632791 873 2 758277219 520 403 231749826 376 241 978063553 985 519 758808124 599 516 807908754 399 682 552058456 40 112 373043098 225 297 247048308 797 366 72830545 569 785 161057889 516 531 161361084 556 906 673542233 427 499 589301509 584 701 169266828 747 742 47514814 967 560 166311881 295 274 996206264 102 237 926172114 234 602 963471212 814 48 234205064 15 388 822418042 679 62 659331172 399 913 818099050 674 840 987163445 732 42 921734241 167 727 581121793 214 765 56187409 58 449 326509637 24 895 765744120 346 324 530485338 966 518 433699509 676 531 770507138 295 851 477497062 809 499 676333832 177 993 224458290 472 928 883096620 957 62 595272297 36 875 447509747 217 197 444033632 747 629 256722408 999 591 603849334 639 267 782209745 971 865 434320810 594 775 77453425 281 287 606409457 30 359 287382944 244 384 947632641 493 94 542864185 732 707 606707846 913 718 911874507 709 143 711212086 940 111 937402521 255 139 877917882 112 259 493561529 613 619 632247761 676 835 136312243 589 124 99717403 814 658 663617921 691 545 949625518 788 755 65312249 748 285 935517154 692 487 715332593 588 757 179979312 93 183 481065825 707 384 810020622 168 766 971031563 205 167 77608938 321 819 482994562 361 432 673332756 312 971 870272180 444 146 425958107 44 192 675439350 142 357 984557810 749 461 679712934 707 568 605399412 422 826 75024161 598 51 868921060 141 404 497423951 938 653 615214260 969 203 740379527 314 880 359699816 836 656 107640276 950 520 296650427 260 15 471721738 574 367 544330105 439 602 905817671 377 192 968933489 508 453 370913841 461 184 585014145 472 282 332413588 466 367 89476584 313 990 503515750 157 929 904120083 96 965 581506527 109 969 342476507 592 568 520280801 272 221 699637829 743 547 670699378 197 849 79551183 220 665 148386982 570 332 362545561 440 35 808847471 941 407 944675854 596 893 535765609 234 246 858919065 599 176 875268279 693 124 835048385 577 376 316984782 69 109 681471739 68 142 298824115 153 459 679308008 584 331 98041672 477 574 957975266 179 439 258997135 16 853 766905239 12 459 490633497 999 655 465720817 926 348 115479956 289 645 995289645 419 660 665486204 772 451 744823366 129 709 86510275 617 9 71850688 810 348 130364657 721 114 66092986 187 724 137418234 865 511 913842606 198 529 669748935 432 150 573674735 311 87 649479582 538 563 36751081 804 154 941463693 524 147 684894872 590 685 390853760 992 39 781164327 161 605 904073401 533 148 867291388 983 811 324006247 860 505 728405920 92 440 313133201 631 211 438327129 220 621 792499328 515 118 886600214 592 992 798110180 258 577 261807460 509 204 691807873 688 621 226758535 624 853 850020414 621 252 898544368 181 487 219412905 703 172 295927162 383 348 234787441 46 794 718029904 412 792 601161980 143 247 956361934 391 861 986175032 340 245 155722016 953 535 669252989 170 725 170071311 175 428 812598534 233 287 636102317 386 325 617144295 528 648 860943630 987 247 704076971 81 435 163384900 888 789 30969172 648 453 130783563 470 734 668396192 651 914 612090915 155 72 98517698 363 61 99666035 433 44 79967029 231 453 997628333 598 529 459552191 571 284 543368065 791 344 923147097 890 922 122613015 949 91 721540626 275 576 108369851 59 487 168994997 116 370 523490844 306 275 144021300 76 879 62671892 320 622 805112852 803 94 582209050 274 414 474128024 105 343 718176201 563 911 292093656 804 222 526559961 428 768 687487018 863 79 222643211 183 526 462731024 327 546 647957423 183 327 794658518 957 950 965253474 778 426 846684612 136 209 68914694 832 390 158987383 870 984 186039842 579 717 161017376 513 135 239464546 870 893 168245032 201 626 554552290 166 98 533439341 755 81 54375584 714 5 444214277 446 168 403005730 405 206 674985949 104 975 96948878 177 794 956165214 340 675 718758337 122 706 463019955 68 35 826292963 606 150 239108854 395 102 99647033 954 602 677973983 669 59 969562524 332 704 866686171 644 94 162460803 137 94 338418725 658 159 65288494 461 761 380643227 396 652 750065636 569 287 13820979 110 973 490170935 708 531 813155282 177 785 187577629 653 116 524154675 82 269 909022363 687 85 712585593 839 779 207841921 740 440 531384658 109 758 896652901 17 754 622893317 899 764 974709519 154 824 13468216 7 254 375829196 705 739 810532803 122 690 270777848 80 293 354053398 4 574 236904290 705 455 297507492 713 807 594987359 879 771 884289711 325 245 832036551 639 580 621107756 453 685 931143900 690 74 683859403 566 633 70814148 640 174 721407222 21 400 17685445 443 260 843782913 117 474 210274012 102 320 316721694 561 337 976077686 601 95 830379567 389 681 89965632 606 736 47974953 699 852 547648817 712 63 374061360 775 780 861690341 953 834 103753842 128 119 878817333 554 314 609405792 485 797 739840172 814 760 233841677 67 732 689227115 764 352 246661340 617 405 189932731 463 558 457060370 904 228 907130292 441 233 305759269 842 841 781493442 682 566 369870447 113 758 187646036 596 860 907985368 595 78 625514429 463 987 88266638 256 101 764326732 825 259 900430106 901 11 611462483 958 643 952336681 910 981 976818973 865 482 359665759 727 327 171174532 455 839 683834216 197 863 464688290 24 98 763355874 357 726 552462075 596 902 610123665 165 400 721125746 409 190 349222106 448 767 237485516 387 113 697917669 634 159 913631945 13 358 498195354 853 316 207012706 636 920 841049105 893 446 120610304 605 482 507237012 442 46 764072531 519 95 320085070 815 618 368146287 6 500 651028317 310 362 815996171 438 91 45132999 734 852 468675352 301 895 513677749 519 376 486369252 45 206 850770046 596 553 302917202 683 619 971554811 427 65 114159715 332 828 625209703 926 492 743102774 820 604 872025136 32 740 485588996 517 147 688260105 631 481 761460221 453 700 966239192 418 851 946567998 337 816 154329335 4 22 927862338 975 590 970922028 768 942 8672406 255 769 333485849 618 126 52591221 98 516 515363192 822 819 996115356 138 148 752800340 704 764 652835469 818 833 540807686 85 294 425638213 352 103 417994216 491 351 790370673 216 201 851359725 614 622 88070170 121 563 906976400 871 455 452188007 78 499 562579847 16 383 2902390 619 853 210862274 725 48 734658389 587 967 93804700 20 978 395700552 778 190 733543994 599 286 439914543 618 222 501216427 255 385 223339811 936 9 687960133 432 46 528825553 586 269 178687936 537 640 117185764 596 344 525231846 600 445 593394848 451 194 939182324 444 654 396910446 151 412 335523362 831 276 400208771 540 159 97693345 277 883 983907838 667 559 823905428 764 362 61043836 766 831 355354874 895 482 533364612 252 6 789781485 383 602 109913138 530 595 943382768 606 989 832701971 15 70 274263145 776 116 707683613 916 961 949925481 78 153 972481224 954 168 489647556 887 548 80249610 462 597 737541007 364 183 725828589 9 515 671314850 816 345 837611637 941 341 812772584 581 47 663566347 451 574 932329502 238 28 360555247 396 159 332989364 586 350 778986992 625 264 165592039 653 281 832803668 914 534 783518397 637 424 175486855 249 187 24431091 70 80 111150465 746 581 6088275 522 696 218381977 656 792 628133786 121 487 2775105 912 715 605942504 256 942 5529888 908 318 520294872 882 367 12603148 735 201 535543069 815 647 880701747 432 925 461341469 122 606 231839509 623 761 580838623 41 913 780850175 388 357 227321363 762 265 286672368 28 581 589905886 509 24 446082240 577 776 843743580 773 340 309919834 147 463 953856009 65 54 25195791 422 296 879743714 525 50 686925330 209 591 53337649 309 64 414613334 700 29 983477950 972 78 142837266 549 899 521120528 128 350 159819719 709 164 284260212 772 153 763385384 788 65 518959734 416 301 740282928 550 817 811979219 769 206 29822846 215 380 119344868 492 779 525381069 581 996 97598227 215 428 719303411 166 761 905999181 580 127 391532820 753 102 527792274 777 474 320419547 831 211 303510829 115 404 214752266 11 692 439155002 229 231 993618247 157 561 160107080 408 454 612429919 285 628 990909938 931 362 140844650 671 572 595171848 302 799 251258028 55 187 900206711 554 5 148227629 749 874 821486453 260 961 725944821 708 96 255192467 442 60 432946557 789 867 934370157 770 76 743297108 105 610 344792929 413 425 217472094 363 482 587892948 317 351 891608940 490 315 329256533 279 323 553317129 585 834 953714354 706 568 27368304 681 596 479440018 745 942 645537673 865 903 222680163 621 418 896190959 917 454 289438632 263 536 673986252 252 347 966855604 48 710 855618304 760 627 264858938 627 750 928626605 226 168 173164261 184 447 680906065 635 685 470134548 433 42 118726211 216 18 329594391 99 389 18187739 534 414 234196142 556 613 925404908 405 69 426853439 98 53 214244411 24 466 897610582 505 916 185765882 662 358 587151028 743 496 656560534 667 331 187466484 951 449 620281192 261 570 596770934 349 294 272965095 263 493 306290408 257 70 686182353 301 728 177596109 801 957 334544778 282 670 167375890 991 36 849526181 906 936 138283618 865 465 49823759 169 859 281793157 395 546 667963525 272 511 769155314 182 819 508716586 997 779 429546885 530 662 977447344 634 558 900161627 820 261 230256404 803 499 127976120 458 691 236593715 846 326 470618462 857 229 65523142 522 744 725989419 502 549 217696498 844 43 679978734 923 346 925561424 744 343 614921799 670 138 23813092 162 284 252306406 287 157 418545543 651 421 387751823 319 931 871819048 226 804 837901522 345 872 809271131 445 890 334210567 555 946 548181157 242 618 933520835 652 394 526451558 312 519 832953152 544 260 101144405 466 100 329194478 224 599 868187367 769 916 998200328 249 145 670106782 813 186 800717413 213 530 60554630 557 771 375332669 437 752 300789605 91 698 126202082 344 376 811600657 922 433 977191334 885 821 277020870 62 827 249148085 763 503 741263685 812 884 656780794 417 16 98334055 1 36 741889657 276 360 292896594 144 624 504187716 112 534 207872277 321 706 110052558 230 725 782597599 275 15 641838769 631 947 315343690 553 648 575722489 199 286 149817742 548 306 109708576 634 214 295111584 479 706 409760353 171 800 96216437 651 966 848418261 694 162 748228134 280 524 593427141 771 528 240516313 14 677 433461056 666 575 336990903 983 122 303599356 835 292 84159568 651 229 97812220 7 664 657495351 743 459 506950261 214 497 645192530 916 524 484893363 123 120 21345299 873 491 497804738 405 979 777036933 830 383 61103248 691 485 252715456 885 96 317694395 139 254 731364257 428 511 383954858 849 892 814560246 430 3 259216842 993 450 862237505 884 365 886692220 692 712 98305936 844 673 55316841 951 365 485757990 160 508 376764120 532 303 721185840 26 868 249952214 973 982 43893096 964 396 770759455 615 362 288127331 756 342 531817447 331 167 836861403 625 235 685569682 607 474 266225924 660 298 999500042 811 543 788015485 473 864 664924918 295 745 664264822 187 858 171226515 130 99 26998830 765 643 583376411 710 162 255873172 374 139 355603499 247 550 768558809 964 636 801807810 416 452 802455577 135 292 750669283 521 905 543462522 747 446 366571474 626 90 448892690 391 156 708133198 660 666 9688823 450 218 93590076 94 653 266092545 649 473 105948300 818 958 773991894 322 792 331112737 584 190 500552915 839 380 660997010 335 716 135724951 558 545 627097831 229 417 664408389 195 729 394913673 685 796 230036601 112 552 388260146 296 822 104856714 339 676 791557466 60 902 541491930 516 478 846742285 844 207 393599809 893 957 694077399 737 619 575360608 557 292 399806070 669 714 610874400 206 82 578219684 221 826 252391200 743 603 483780401 813 543 350418930 404 260 336804822 886 534 723236774 227 915 682149793 868 908 183959035 821 675 695988244 538 1 899301988 571 32 251486935 35 871 555627472 875 186 426144911 916 475 134446073 639 80 744468160 100 593 377115720 262 579 35957065 536 369 698487684 671 989 110326858 980 875 710340806 980 253 256284793 184 33 719821179 246 174 325616258 667 837 866470120 359 364 949851264 894 841 506826276 625 585 804177748 630 985 131025123 954 772 770432390 380 951 210408799 421 67 626289487 75 597 9350348 823 413 361061854 107 346 872423758 789 678 833982292 790 672 114062394 296 917 965047376 595 216 795202921 234 242 794044147 691 574 138338354 380 874 757979776 584 741 493646267 319 863 283506860 552 783 294514135 530 80 748906137 827 807 127699890 871 731 166792420 546 19 6272946 75 927 6112520 412 15 855043816 787 917 62863708 187 127 275354221 918 201 868523978 656 440 870545553 582 756 53731405 785 989 284465309 138 385 890190587 861 969 510850336 938 297 776859053 586 672 4811637 103 193 626804252 236 643 181304250 176 653 161329743 333 751 622325764 553 3 453059138 117 971 612376075 962 317 836753184 125 702 139337606 253 157 471360788 495 345 634258854 80 674 580664804 17 838 966167096 670 751 922077743 697 140 121505499 274 945 919825983 770 714 563332804 379 708 157555955 624 55 550352155 318 136 610068970 834 164 288332254 297 872 185004060 757 849 817638250 167 336 820143672 249 843 448038507 820 224 468091228 312 397 403903684 604 411 222509351 939 556 404681234 860 106 163407297 808 914 825158166 636 305 251015721 920 732 573856411 408 572 11675858 890 296 817110360 315 581 228163248 59 504 50300704 925 710 656892213 256 489 800535267 36 904 19769999 119 564 399515873 289 662 783022830 966 874 973842150 130 73 472398086 914 175 598334611 126 743 887412725 450 957 403453011 375 255 537007927 223 681 387173820 438 941 66302569 110 796 728395473 716 242 440289546 964 81 851672181 808 660 210710529 355 878 906287688 203 498 481622315 612 276 410120753 514 961 736708869 865 919 671271838 928 540 759844583 81 943 676408582 230 319 15987984 736 666 299643412 562 54 350515942 656 539 400512727 361 139 5094579 558 948 564911500 603 543 849160339 601 394 157291923 7 245 734807789 352 127 261263039 898 910 61790167 495 916 921934548 812 155 231170368 973 685 601714728 242 614 286726107 931 172 21254449 91 14 41957357 232 133 647651261 408 760 328653044 75 965 678451896 461 813 998573074 864 5 836748716 112 748 912096780 642 1 414668662 888 32 212023857 700 639 255118645 368 876 150125468 475 613 329690408 601 235 606077348 1 680 380793204 644 125 126483806 157 646 298455349 469 179 903598637 697 24 274934850 6 359 920544403 62 635 3873011 261 236 605051739 538 176 694744534 495 475 569529937 753 953 43407280 415 932 201263913 864 850 7305549 858 458 710794460 125 989 486527664 639 419 68804991 966 146 445562346 645 43 467751422 542 445 972147406 414 272 883375947 947 798 604540418 396 225 234674799 255 666 617573428 277 641 893027420 1 362 701029289 297 757 642570490 893 242 818413334 660 690 859192204 50 708 730991229 909 359 239454531 331 290 750116580 960 669 109536794 9 554 952776275 730 176 992441677 828 738 646119540 566 765 612833956 566 352 402428669 239 318 934105267 8 592 341924004 669 255 917636318 100 810 391561109 836 687 427565935 239 533 72086479 867 535 959530120 164 106 115456750 786 16 203849087 746 323 511380417 163 326 718600914 389 493 801732534 745 478 490483404 292 501 69648410 662 285 738386943 218 611 547988697 233 283 508536135 844 264 744863645 888 145 759096559 415 11 733424381 303 365 992592201 792 829 195594145 722 97 475540801 432 296 201451097 684 609 618561721 813 24 125943963 170 729 691605034 756 786 508831039 890 537 149904754 346 426 292041212 837 62 640831163 127 973 758129693 388 649 803003552 122 222 19876643 131 893 59406539 610 773 839669224 145 928 235611556 251 832 158999946 469 40 634933817 260 590 462343584 578 340 533623577 390 83 118045359 271 508 463429356 615 167 668380745 714 575 834950961 850 199 300296185 111 325 768759284 563 378 182109767 481 357 478463044 666 685 602796468 595 738 618114675 183 859 256087812 637 127 849485464 748 108 399111797 610 149 208087459 335 796 923600347 963 906 351171947 558 223 658201657 260 904 366382594 10 725 16884884 42 171 858969372 330 446 878785421 503 575 811156556 843 63 850938353 472 327 765989606 390 663 510525535 225 235 601746363 43 96 186782170 138 471 986799903 707 981 624677093 283 165 969425389 944 138 892503119 579 415 428734748 509 852 40952382 502 328 793875888 20 748 469247441 978 834 162607150 495 534 919460751 173 580 762738459 968 62 973378642 832 602 340096980 941 680 32552089 779 326 377580925 490 125 900775770 681 729 18488081 328 892 628889459 28 906 508155950 66 579 251109273 217 622 255855997 825 624 871401328 584 181 560943310 969 695 502105096 278 817 102961036 692 398 562127996 919 225 389976592 911 791 952424177 262 100 979763615 74 372 339281361 293 288 192794981 961 879 282876543 831 751 188433265 876 119 833743221 972 736 29595481 190 209 401231264 341 983 856940259 646 711 213383763 467 589 318084601 343 1000 363637520 928 827 558720466 894 74 162293820 580 219 345155421 69 920 78561729 734 884 802170918 997 191 120394482 91 809 445948064 447 180 313182974 927 675 553390291 580 153 855131818 263 794 286371611 375 310 861976114 764 304 897568192 306 686 284473922 437 465 253793515 539 799 807817695 878 294 327774448 179 556 686122827 199 473 514886995 253 988 899417187 659 828 189156460 218 54 260875671 116 599 656792752 551 981 859892368 88 336 96949549 798 590 700637415 524 360 584229778 303 119 527580357 819 75 618074397 319 915 853934864 188 547 415850425 768 173 280224928 188 503 180570453 754 318 740433855 157 619 240690357 997 773 157621895 38 141 425256393 410 763 254310853 493 218 475916880 468 574 942665895 597 138 813958780 599 977 872658179 839 20 705504622 817 134 897652631 388 524 516064816 734 619 372338770 340 376 379875328 560 518 880014259 147 22 43263586 813 279 221152407 590 320 300014164 278 552 653689620 771 503 23542013 31 662 835287120 173 59 832675305 763 469 475812014 924 868 868597254 155 107 834640436 113 575 839898119 785 185 202300408 980 114 501878916 186 969 861482780 344 581 789164770 828 663 486343783 728 8 714141653 13 685 134066014 618 365 129021117 410 763 643903356 343 636 333125485 388 751 84609764 561 347 620299294 914 437 84069393 947 646 234728508 636 480 194575084 105 395 484581566 484 873 349690604 558 904 146939375 116 937 1125873 934 61 333384322 138 995 805914890 493 142 478585452 848 336 139957774 1 934 825292735 298 700 882939845 602 845 560159993 32 131 421793346 417 948 269567819 487 458 918087701 861 125 163343705 843 402 67647923 334 312 331246942 94 826 931306811 292 350 73706544 462 892 251555728 575 105 17971464 984 250 747638962 956 14 278147300 37 161 569792327 115 875 245112148 472 722 674369483 951 641 595393133 928 90 968483904 874 502 885606629 75 458 707769616 286 169 845106645 508 845 280606777 136 961 720933044 990 10 198675096 767 888 853166699 603 140 623769148 102 625 435469494 626 933 958304307 925 79 897398470 282 164 384752210 358 357 33424881 315 290 682664596 321 437 759385973 470 665 329354921 455 339 976740567 218 447 839411225 875 233 412781012 457 616 7011864 510 914 257273255 990 190 490552156 390 526 928233989 920 488 708195560 347 304 425460262 61 390 642485551 305 375 409310421 338 482 667103584 419 496 78441285 352 419 395061310 649 295 890789937 264 14 40831475 252 908 700427328 51 343 926721679 367 177 379490036 250 793 137336844 631 341 342319706 655 909 321067217 889 619 272888063 282 529 954475311 746 594 371416236 738 62 569065762 84 664 554517531 905 195 680891963 285 628 447245325 923 348 322101651 475 115 339071076 951 257 642442481 463 170 877865116 104 728 491435200 328 664 286354657 78 743 877930511 740 498 865450610 780 307 447887341 852 348 222874739 52 271 383125867 304 306 537811089 942 678 820368887 789 456 902286001 962 408 340020894 199 571 388685845 796 615 643682489 156 559 338491648 265 652 337344178 148 28 361615307 209 13 913710217 34 377 299718208 187 753 741141782 959 283 375508246 559 245 134060941 158 161 682106507 800 117 558763452 87 950 710493967 969 829 428929656 326 264 353027283 26 769 649526178 219 738 46274309 220 13 784667555 230 429 990119909 730 602 29763277 38 35 698856143 644 285 254939665 232 128 760529683 698 342 146991431 263 878 605193834 372 361 533165620 477 34 518521596 787 361 572996034 471 604 156321836 291 561 107118833 166 828 598690215 754 974 784707199 741 71 29127331 521 398 256515620 341 929 42403687 813 973 312647742 344 224 507231966 717 67 42617265 378 679 771488123 232 544 127841087 120 984 617804501 352 360 897260204 404 322 984926376 216 649 403231635 880 901 312411687 217 194 239719184 526 165 10974095 868 414 538286994 902 881 505508990 204 729 883511243 628 898 381838302 40 913 73580945 297 893 651738652 922 472 418467587 869 939 704300015 122 685 680745268 456 138 999653941 912 783 566841058 452 516 170837749 490 790 107491754 910 379 851053210 502 565 421194999 643 738 175885741 857 381 658437251 234 126 781999224 845 411 817380892 305 320 673702460 421 825 250825179 270 460 172931511 572 26 667226814 396 502 111955038 152 738 127814118 640 129 482248841 741 754 786752466 29 514 280778694 989 418 186726087 952 709 854799445 388 165 909263297 197 467 894794984 157 642 609590779 811 659 52481578 417 557 410071057 215 549 283644642 758 275 369251868 148 118 278055431 331 273 134353213 428 291 427025554 302 337 984810375 879 653 964070599 352 21 653617356 805 35 431664949 458 487 720091842 267 695 536935882 536 720 629317603 368 603 978061942 705 91 719218695 897 361 362510129 873 740 474988666 477 363 50368212 995 630 911825870 814 215 607457435 435 104 22187694 697 935 247625426 586 581 728333985 417 430 273138071 5 62 964362144 875 388 603084299 74 134 543424782 352 301 287544044 411 699 392424633 95 572 483882824 697 259 103570591 614 95 348564773 434 735 359427043 600 74 945059771 57 297 222765918 265 18 535819356 788 853 175944383 57 852 788893420 714 577 849450658 957 462 634428600 365 469 995441373 192 221 160971939 537 399 171870095 3 211 410304189 320 151 898744511 384 514 702071904 536 820 342698922 19 789 95523804 995 646 945740149 653 904 374869194 137 713 84855569 111 598 148359675 46 59 804135755 189 851 264707165 952 92 90130989 773 382 503953582 621 890 369400904 800 463 949414681 735 214 59841309 694 687 2817424 387 684 446418054 824 512 89208204 21 404 128116841 243 785 442338286 170 756 361069869 315 215 798412162 673 934 656223311 165 131 401164771 107 814 690988450 705 95 870733360 238 539 30087596 690 86 447037200 959 108 864423516 644 936 703106883 291 319 222719827 930 555 127351166 423 939 729427704 275 644 915818598 518 51 631279834 306 267 578773728 437 862 841193142 971 720 236268834 542 336 883465887 123 103 222825924 777 299 66959652 85 1000 653753575 270 712 550853297 850 773 850265636 69 634 309419077 308 921 683874833 809 818 691268696 954 657 357212750 410 697 767124802 77 818 148798354 447 124 544072421 732 991 958132618 107 444 626936850 937 930 166759433 800 82 134435467 507 109 663525870 570 323 606376146 424 611 967540783 959 527 602027298 200 342 28876802 575 133 285550631 365 51 17739596 463 526 561947986 475 167 370295737 870 988 230798184 348 923 983645248 806 937 555865576 354 288 775417360 695 702 69403100 694 832 823443521 128 290 220948606 555 833 840932949 817 152 339962588 669 145 527488525 597 324 914686650 6 514 182832313 531 745 393734439 372 770 581171214 251 132 180007985 279 824 715333410 619 750 22959844 363 421 364772147 544 57 774650333 387 80 399405586 221 678 820977719 915 544 855110298 218 915 278951354 509 982 821831697 172 61 866122715 398 72 238052401 833 879 997135024 9 544 787474824 744 852 106371896 496 151 688804438 225 457 764808511 952 697 169722334 426 3 567080833 975 371 709901702 391 50 529984145 646 236 389400470 55 779 335686765 702 902 661685737 845 416 390340148 81 457 369191208 417 323 232288925 377 932 645823082 206 259 533499892 174 751 540074224 643 419 777164845 288 961 633837111 159 590 504256784 890 503 137271036 76 590 911658543 60 578 759422164 554 352 561407377 971 654 196998336 891 91 468133283 965 235 829909545 546 734 688936375 528 49 73835530 962 275 310563258 368 822 22740740 504 339 109845449 767 849 989875240 79 55 19397197 641 272 647209734 915 165 135398277 427 378 564666986 356 391 636625339 815 539 103415116 985 326 5891593 116 364 779388461 929 467 406000328 965 171 357023231 593 636 497418592 301 579 698293004 40 359 214167806 476 755 582599558 101 57 401051143 382 370 473185820 439 705 839490773 634 299 981491747 978 521 365514008 623 634 131433060 608 799 695748623 194 533 546740092 638 380 630916151 553 746 414967812 34 87 142155862 422 733 63768547 924 614 715549486 501 72 995115484 198 230 481917402 225 432 179370326 588 372 872991598 851 300 941944261 155 563 344845894 404 732 500178675 37 795 364652198 427 296 363842293 883 405 329109129 634 889 907400733 375 797 778343674 438 227 629107711 470 710 601277410 84 10 217699963 271 248 751865384 58 434 952436816 855 168 40421689 273 111 313791819 510 355 331233974 869 131 182958216 766 37 52285655 628 343 734122062 752 703 486326336 210 84 166873815 194 108 270507404 259 201 949797470 273 834 498335561 387 157 443102956 397 453 460229404 330 104 516159533 991 390 481062288 611 474 753601913 548 519 532135050 998 408 700358 807 381 722342471 812 372 612888896 308 823 471004119 264 50 531905368 179 893 416673695 225 109 941887995 205 449 947138308 526 768 585996731 566 269 325499330 848 338 525825786 897 515 689709307 830 150 632233445 933 169 449636118 614 335 376454021 131 724 22658485 568 429 741164828 492 856 990838031 531 958 177724338 586 453 760766139 401 751 561083246 276 667 487589486 237 563 766257136 396 412 526555164 811 997 789324508 13 612 23299257 658 312 912797654 143 719 588457571 824 194 847574255 117 984 625473026 698 210 817691538 141 815 199463964 377 274 192861030 3 891 182197579 475 754 77591236 992 902 401764218 105 870 138561519 999 428 683703159 844 632 323718541 119 240 369094550 961 136 296558441 849 500 806681233 941 661 912717743 358 396 952737562 135 156 345138380 377 57 353313533 497 53 502755794 901 95 640209757 250 61 999641432 431 635 724584299 166 129 913184421 938 956 901900819 536 404 69350637 422 993 155466486 710 232 236278246 330 263 679594492 116 795 17459713 970 44 33162666 138 329 330215048 191 992 366303546 942 543 995501907 651 556 301842213 769 843 441643474 611 626 380244563 803 73 87848774 901 161 253151268 202 950 297447117 865 118 541309469 997 7 734390592 332 488 387660948 348 940 831534188 717 887 829349292 672 901 330146846 253 704 273365661 843 515 173155606 223 36 426630239 400 560 658425552 22 650 542794633 640 831 28211899 655 926 756933743 565 972 663059699 215 525 236734116 771 399 732540241 785 629 60159519 339 928 789342356 719 707 708015424 818 863 546463680 310 213 732886243 426 106 119589649 440 712 316114521 578 731 909924258 504 579 520490461 78 628 963185742 661 994 157825022 601 293 333974382 496 138 459475074 951 619 288611097 785 43 228554133 891 21 879426111 319 258 815661042 213 979 853327694 50 471 310733183 432 176 623385504 916 935 90533399 626 552 944438557 790 972 285302628 975 811 560170325 555 32 661575270 274 849 585959876 787 893 547048505 254 558 678738434 965 921 77080726 75 586 872469111 124 368 389935425 28 579 589905692 634 822 358246253 131 23 430827545 391 324 793552003 866 314 52564413 697 557 889773362 933 805 761156810 578 408 865868160 593 161 170761492 151 882 149956702 602 808 8775804 52 224 994717732 767 142 964453499 343 755 837630969 297 402 123182074 957 772 532903535 336 263 144944632 707 504 330553479 760 713 953365243 600 657 87274146 3 448 224358855 401 441 23777601 766 821 990395621 852 824 167430653 504 979 963103160 451 370 939509887 637 955 190015349 76 513 122425009 47 503 703096107 665 739 847769463 514 161 921965023 26 305 836110135 752 516 689569713 588 447 217773844 789 134 860656333 170 584 12637601 567 883 390805681 819 335 810799696 904 308 172491401 380 91 966428102 536 78 922574481 848 989 496717164 952 968 611321088 846 560 100000624 783 940 167120804 276 213 508227836 546 801 298033188 74 352 650087678 998 202 214332487 549 106 547778063 104 63 79353651 152 80 490249880 708 340 437255101 601 2 666714563 52 187 274705617 424 462 314723207 880 679 107058139 488 987 466135669 767 306 426116498 814 47 965180222 905 192 328114086 838 265 150328614 870 563 516046007 984 485 327641828 506 850 451394699 604 889 162562337 493 262 624801157 282 635 580957781 781 63 987161293 797 288 990688384 20 483 699614081 821 729 320314678 355 225 310544769 145 1000 225811303 560 38 579880290 567 748 163977250 236 802 163643373 646 932 910036789 533 455 21076416 963 257 669887744 443 775 105226855 627 47 165345903 865 903 803462447 211 686 884074005 185 483 950110633 215 102 824490306 630 304 98804831 141 695 302057520 336 997 804916945 53 915 939286076 685 926 697985541 57 324 268899627 916 53 190837784 228 151 912048051 195 371 6036068 234 779 861997572 893 469 976940153 236 991 893771499 908 383 207238292 873 20 574567574 671 971 936797923 677 991 923900447 670 244 53896235 72 692 455319620 620 250 7532801 678 325 304233217 740 688 501135759 121 731 880873928 994 528 995105363 440 454 184640322 283 479 830358664 324 817 540819201 99 201 377127001 816 851 768769758 114 183 817435341 74 162 413104788 9 989 550726912 920 650 879314400 463 280 101908684 738 960 67398556 649 187 751199148 348 453 556520681 449 321 669635235 977 327 610180112 222 586 256918499 691 929 806744482 596 134 148367160 230 563 837868777 948 306 9149759 398 853 154830093 465 169 298167808 846 106 640523618 166 998 705574845 734 172 612046838 4 983 634661822 982 700 106216633 240 1 917324286 639 884 407013181 375 112 38116231 929 863 956824180 927 403 310174456 683 563 393792715 120 691 147496090 31 624 332987506 981 624 766516226 437 491 584966060 385 204 982698859 201 650 489825192 218 772 686935039 736 671 766259683 491 648 663872397 779 43 815269207 544 386 958615130 45 315 720868426 613 921 353838282 62 209 533401346 924 938 758338291 749 221 313789117 677 890 29518474 95 831 281180458 165 117 886275636 87 92 628093994 825 371 480686173 482 983 56548054 860 735 507187390 689 354 912968700 833 500 268405837 488 48 404086059 299 903 385018730 354 304 372366298 865 578 956946968 844 957 702257826 489 894 922880144 474 146 425271787 475 308 453480368 365 898 671444616 172 316 774696625 799 645 842760895 450 109 793284337 914 738 688327672 375 141 949367380 435 85 736044794 983 100 294830 279 131 838923040 143 411 217040494 795 872 2447384 237 949 303850101 325 466 682772921 243 809 220244843 733 195 434422317 375 53 738349724 666 186 749982519 670 302 759501394 623 264 707635465 34 181 668093998 768 926 956052843 316 740 318564507 986 430 892101321 693 637 481842353 55 905 984788623 642 853 555553194 44 547 128334225 253 49 722733640 943 34 373545994 304 898 219223542 905 807 766045214 758 516 225336788 899 540 302935526 18 886 19522454 52 530 409816731 728 565 152027892 603 809 690028423 502 172 996772432 336 719 768886425 429 585 363887225 600 720 606945108 238 120 997244208 344 69 792458816 920 215 292849560 382 324 344238271 426 830 666234563 484 488 213133055 722 129 422436121 741 84 784735933 8 620 31622458 333 992 615755063 477 156 449118470 231 774 990882874 944 47 326399375 108 523 644875958 702 646 86894781 28 353 906242709 98 18 90032102 9 821 981003460 961 742 774185156 664 254 542280598 444 701 219745301 258 389 519209751 731 4 938904903 218 975 321939619 737 551 342397569 274 54 114555071 59 340 40477744 891 65 887161931 780 915 86781887 768 434 718544869 262 623 632922085 527 495 943789169 870 988 685727495 2 814 654657493 631 729 423962884 629 188 663941780 156 143 859180719 876 25 47961833 401 756 479981871 364 635 427531085 403 486 478683063 616 501 851475777 635 133 858484240 556 164 325608230 818 37 816115544 436 100 464403100 312 770 250658003 1000 534 792407356 341 776 827233226 435 988 549327448 159 469 213321760 665 446 737147922 891 289 603541462 711 389 370721193 256 867 522622927 574 424 949012909 657 496 534652129 410 987 679192219 19 826 678070191 996 794 30660888 556 848 200490059 104 359 513718798 911 97 382208276 421 167 710228555 726 399 942610244 614 665 845181315 86 454 74225630 20 252 192075675 436 384 351064002 470 793 488065326 417 653 512343490 472 975 475104679 43 964 486440726 228 45 724167661 146 585 283633482 774 991 60310547 507 406 78057270 81 865 741944762 276 262 666957770 29 394 623814388 647 65 373563936 665 420 563748274 94 635 550983924 641 94 573862163 726 134 177925172 629 838 529585184 64 673 881480040 421 922 287675999 582 711 915458853 930 380 471184340 177 279 86628596 390 406 531224910 829 441 760342436 348 624 492803121 318 397 185263491 438 999 630216332 908 984 616424520 655 626 133001662 240 44 11983152 850 166 158198123 109 243 658871367 415 770 1338910 600 329 574683000 609 687 919941017 352 559 204851375 472 79 591225225 847 920 986840775 232 782 585544152 404 475 792404005 556 665 687078836 250 36 977584126 716 502 158752604 887 48 305118898 40 497 925596643 302 25 154349334 988 581 742626619 695 845 718945240 394 703 619973651 838 898 932806731 648 211 455181534 73 821 703260200 89 633 809539754 419 748 927162611 603 102 251519071 838 577 246121506 978 176 235265985 552 596 389638874 401 872 257629646 819 978 29808855 652 598 269646126 771 184 928071371 789 777 578010709 932 402 717684 191 113 429557306 195 831 208394997 438 732 931241157 389 308 284864682 835 48 848634918 490 169 709373244 626 237 956781555 979 710 832133736 562 844 779185203 32 383 235002009 140 710 678208485 962 236 958732342 994 598 641983798 364 246 368599897 335 277 249605851 96 64 490509150 858 770 708971030 795 964 270110301 319 964 428550262 944 838 484118472 152 208 633961902 708 643 89000784 298 824 124598101 344 228 758942218 861 928 813807349 167 797 957624727 551 305 640031092 933 757 191746767 867 522 807798816 169 454 352747465 466 627 917601228 632 103 575493073 973 836 356664646 644 736 432430816 362 987 205454547 389 280 484062493 525 617 208978198 443 419 722189538 490 819 850400250 407 897 425962945 66 459 201375103 939 985 376948501 173 223 592666187 858 301 417909679 431 422 37230819 854 749 459850945 869 305 294766094 618 324 480072189 213 970 216703744 908 931 102171461 824 729 925285048 217 476 303611861 585 288 885724 432 197 578329993 129 428 931878794 266 967 201159977 613 44 500939664 403 541 527855773 326 153 588454918 871 452 723912159 686 714 389358724 203 148 141353981 185 726 573617524 221 793 717364078 78 742 1581660 141 272 712042104 161 5 389304941 876 460 680103664 514 213 441501937 397 862 125875 832 57 193938286 781 882 398159248 661 180 304998298 89 844 54227247 237 333 38758462 417 484 65196252 398 811 70901674 984 308 858417501 889 673 44315916 108 915 336625880 827 403 264667530 236 57 703393801 370 733 375679419 527 993 47590287 839 513 456383886 292 672 908232901 560 991 460545914 123 21 346650189 175 485 306087540 308 921 877989771 212 283 514732700 587 244 267434331 236 957 572629241 521 991 27125498 516 120 25720782 945 403 574846317 294 358 188475082 739 125 846952429 959 950 473720168 891 765 939407174 390 345 324153690 982 11 977449335 293 118 205251849 544 417 302517182 156 310 152766641 997 718 109681678 609 94 408013803 86 854 276358013 678 430 781488623 200 341 825610727 83 838 501705155 965 8 74765401 823 794 171385831 116 185 565475002 454 656 425471624 241 546 865634319 474 85 257871089 501 693 955137934 662 759 331651557 99 773 891760162 689 899 507581824 145 167 461240562 988 258 864721415 78 986 818264165 164 420 581410598 650 550 995462259 299 328 468000633 225 323 419479982 954 17 151399729 867 570 648320983 919 280 767712727 324 869 32898682 39 238 59172673 837 571 899420536 145 68 840750484 91 739 60887878 359 187 173037579 775 168 136832248 372 403 928636533 848 180 264544120 911 902 721464590 982 432 977781665 598 541 875417924 111 944 183433001 635 370 179906701 611 717 227573602 562 867 167686880 399 334 987738416 536 992 662332772 217 199 386528008 92 11 116499704 966 211 360857607 63 932 455220757 223 908 84280752 924 310 640206885 497 941 807437341 130 954 641905579 429 225 858409374 555 291 80674161 963 112 142250527 963 271 38441920 640 770 672870658 910 72 330324500 192 97 329755219 227 650 268694035 967 421 472424232 201 68 495798666 923 337 132711812 354 944 660315237 100 868 310668766 300 78 730824057 130 742 63924701 46 864 688656182 123 348 912405777 268 803 932918784 91 765 387185176 721 239 866670526 325 168 899720258 912 747 609904663 902 42 929809270 153 959 375960928 113 134 673815007 864 985 610384880 187 736 386348802 895 750 94989432 143 733 951907857 359 597 259297582 36 563 485433528 495 399 667587251 644 446 12895172 999 357 878376752 776 286 116157131 507 660 564780286 578 833 945144800 346 957 324649383 525 434 282445948 751 543 550130511 374 481 37005091 945 948 210034994 118 319 448410020 257 908 106127008 81 465 350974373 880 112 209364971 461 866 525992301 708 91 369579080 169 305 567939326 150 527 872145529 929 543 258502536 160 996 700624520 813 498 838887917 426 323 708508197 669 746 275687682 713 990 212397379 414 958 256638089 184 287 28226583 77 173 314570299 520 821 308553366 809 792 283460446 997 227 51959697 604 701 917254599 266 436 304727868 733 753 315446035 293 235 113373504 870 277 267739277 629 523 769865182 855 513 243879907 209 868 922130648 565 259 1838852 937 136 832477011 553 880 642157752 150 817 512751195 850 640 281890647 198 425 43269155 209 917 910341749 333 466 735975423 20 208 123977544 762 931 834461108 6 561 297630544 571 145 23052059 670 237 431514332 513 165 952408893 83 230 932864342 393 809 588004542 372 932 583184686 510 223 379039670 853 776 637866471 202 669 942132447 744 619 900636773 307 230 758044923 560 476 575104373 320 995 446419075 620 534 167111892 905 404 57537055 455 413 77622461 335 50 607724320 877 690 938578512 585 372 710655566 77 385 260925890 942 214 825647448 835 768 880767489 540 715 620064950 905 685 749630452 7 387 633885891 560 971 105154001 752 812 803982486 472 986 781544749 353 908 540682790 610 169 807206680 609 982 617918452 1 221 565173021 456 36 988664398 621 180 395165797 782 303 29751436 593 384 484026907 912 328 578104499 169 643 923141725 3 757 797485037 331 585 873119739 772 497 587756907 458 2 846465729 963 153 43512782 887 697 549126876 506 129 967672781 120 13 598537623 496 459 936997671 734 784 204831197 815 156 547567643 896 883 302405145 749 871 353081461 226 637 811308263 307 851 526151765 441 667 321662006 1 565 74857647 368 190 168922379 497 532 917831053 649 341 363835405 823 925 667757561 443 10 656988441 415 298 987200888 507 510 789422022 667 962 87114792 242 813 477240717 891 112 83961194 248 322 3894104 570 874 74934097 635 39 115781630 315 189 294292108 177 136 867529236 287 312 195751995 76 382 186757382 788 927 900253201 980 438 822058488 309 402 484249 524 931 443181811 594 15 583063714 341 473 543652068 809 259 586712314 857 294 872037157 162 229 802979850 700 708 103583759 662 750 550188116 83 154 250920654 944 874 158271803 509 730 560312675 878 271 216976374 258 73 437860650 793 411 841593416 545 895 309939077 660 52 204272806 780 584 17420658 614 475 347844063 146 939 958055845 491 356 915214512 444 8 896852028 178 887 306436231 273 929 3758015 560 605 831592751 639 434 606452781 117 736 871442860 745 29 488380322 437 602 986603391 609 840 420772725 449 764 400580881 106 116 869405229 819 631 984306918 296 325 795360246 636 151 698065197 424 634 561982599 708 820 598600468 292 820 291637741 714 275 657775760 434 870 308967026 273 331 541941924 258 469 473006797 350 308 339675808 202 375 131041445 612 172 207727775 176 298 181273837 703 381 684203653 191 140 182671582 840 416 654373100 262 160 211959443 104 834 709067636 491 421 935049435 431 773 507646690 746 163 960940955 163 347 288711123 739 695 975191596 738 856 178282389 502 801 359499390 7 142 192500208 711 502 448236020 194 881 703992288 42 389 960659220 172 954 373676877 712 958 331436107 625 364 230809172 325 369 325131176 496 466 719614558 815 863 691427605 817 213 777758801 684 985 887910697 450 604 813016747 313 342 685761287 997 890 728280361 774 933 524212304 446 623 851251060 452 300 471368785 117 448 895308206 858 739 232444907 923 513 839305467 267 971 54225926 306 771 555074601 473 999 67404581 771 144 566896159 322 467 433509820 579 648 7534376 386 295 619157534 220 64 981927466 143 610 379311324 927 949 280982380 130 953 747534176 305 750 156362985 5 739 400609508 235 403 755472634 840 789 342302601 392 537 706362939 942 795 229196448 780 388 633763814 825 373 731921144 512 119 843386523 456 827 766711270 402 12 76811192 926 481 77195341 375 205 995412580 193 303 580301329 547 130 16722599 863 490 524730209 153 589 168900350 621 528 540058724 157 598 978643264 559 23 33072929 482 199 320097011 337 117 635514043 322 324 346622561 454 816 694083376 836 862 693541657 414 956 966216699 298 249 202481624 264 939 104515266 375 763 498549207 941 241 727958150 599 399 898084359 816 780 868522192 747 865 536480776 273 151 471840636 952 78 454177258 862 453 606966780 2 10 996229240 950 49 432255767 570 142 880820763 985 93 397378074 594 404 639084316 955 772 38519926 633 899 914465067 156 943 518599196 984 975 860584324 716 230 242303825 448 13 132712911 218 144 569555255 314 363 676498997 365 571 348920096 665 302 503799358 463 737 415630941 812 178 163982084 150 870 613513715 122 940 394857201 428 587 371364664 250 951 823521447 596 232 741107573 47 524 586284538 171 971 106193136 922 937 888630507 906 138 330932726 951 660 764411520 262 372 73270814 228 930 777849682 855 545 126503290 272 66 509443872 540 440 692545030 962 166 891758785 965 953 808099228 607 547 27219820 502 271 134965292 502 520 753727382 194 323 205699871 848 266 339314114 964 965 495419643 233 896 889002340 329 782 455031263 890 984 155781233 597 882 408811450 715 703 783185371 389 642 882651831 520 134 978243823 306 567 19330838 170 555 884946178 536 667 743170185 982 236 768791341 122 31 591457175 780 845 395184923 76 929 226990017 206 140 130060210 310 713 952321938 290 171 963909407 525 395 40791245 295 891 79897595 690 11 150239779 16 715 590276947 796 31 666479204 97 74 768396468 326 881 87617726 185 916 461959131 37 380 610509882 390 611 363215748 662 251 630218412 647 190 910685194 608 690 205415797 2 78 640612412 101 122 140121277 923 136 896167852 211 28 478489146 890 441 839396694 258 724 58555571 144 892 57107061 846 701 119355120 606 888 235936460 117 280 199869565 360 389 541711781 420 965 840678973 857 399 166376384 144 1 840680889 140 87 858624306 81 644 120501995 395 267 14929403 984 916 845246699 249 100 575102433 699 91 796365132 778 378 959232561 866 997 65120726 442 384 746755137 446 422 211880770 462 872 135134378 793 889 942567266 885 159 708957779 555 69 361358009 135 541 472411619 340 579 106504970 112 225 330716434 808 34 277679720 48 749 679683386 74 35 788834261 766 104 975856963 545 692 658532381 950 684 256650748 225 15 111450151 323 803 224589841 908 748 712085774 911 246 435529903 243 774 853364051 106 91 323062025 768 474 419051653 885 923 485866155 906 960 511792622 500 861 916959263 274 4 781953277 29 903 908549278 268 596 336804042 981 885 712362519 314 125 847237433 702 521 299896961 281 986 98043799 694 8 440082788 194 3 474749806 46 440 830946643 806 406 32679730 386 351 891623204 131 964 907527082 198 476 228359470 664 833 163982605 864 340 665388754 169 152 252685142 47 206 789544331 252 398 768256663 424 249 910895341 225 145 915055137 396 728 611287904 777 278 383652146 12 228 905322801 149 136 824892247 840 231 22699802 661 433 366482215 876 959 869663477 679 956 124122241 860 784 210485236 458 935 479039045 786 64 670616855 824 968 668798991 274 302 950384157 460 918 805444277 107 946 765933965 111 534 976948072 522 822 254990087 716 703 437678974 541 406 307259651 864 59 865690826 79 229 782605088 290 936 423544070 370 967 559202367 278 516 811912234 344 894 774990578 303 255 721471364 930 890 946447444 47 433 859150577 627 743 719583956 405 134 820513769 227 633 50036889 588 770 841901288 698 914 223746256 699 428 639378737 171 742 690760342 85 822 377251622 966 548 281023995 351 433 5268203 374 292 10820009 707 608 2102596 766 935 269801858 66 920 551188759 99 580 149941660 662 465 430270964 369 62 49365812 963 378 124508922 714 12 420941805 933 585 160896294 798 190 610488011 852 723 215189877 696 308 412205586 620 681 24654585 864 813 641306167 238 52 484271657 738 348 289371483 975 732 6483552 461 309 52243232 980 97 191893917 321 254 578506785 75 275 912258559 539 103 914776476 353 939 862304333 543 431 357135237 383 252 859864893 297 24 999974064 209 910 641411379 236 498 601784412 494 356 22772940 357 548 440250524 89 972 168733500 194 952 167597967 569 452 985920576 329 29 382411109 552 425 674868039 795 741 590219600 374 860 177283782 885 810 179011287 858 344 111401731 846 14 463401567 467 837 18310035 6 276 474547840 735 654 426274860 988 529 578104564 468 920 349718106 904 425 678095216 91 672 747660426 635 971 252561311 48 277 952562055 697 172 270266249 632 28 426172681 996 163 540268828 911 794 350650990 616 438 738624575 848 445 222213048 982 680 209918837 281 926 897679032 669 948 515715866 575 589 631531414 878 385 103412519 527 436 720911254 807 816 144401128 684 564 167713720 656 932 878423027 658 565 775102536 581 904 216081621 521 267 589620854 970 48 712439697 757 250 857454910 506 65 531294747 258 182 100174982 597 489 282802259 458 807 190010600 14 132 569609599 291 403 749843298 650 671 825597029 282 263 371275227 993 883 99718958 655 183 724836535 135 526 123428578 917 599 983560973 402 895 265588747 142 947 20264481 631 505 664616157 201 273 957741984 213 286 864556905 769 176 669678721 599 755 489656341 3 398 272149241 654 961 246138830 340 684 701101182 899 714 182773130 420 677 896105157 763 914 600207747 336 969 861664400 554 947 715863622 959 536 344824066 553 446 403403749 279 935 16018496 513 317 215703271 444 152 535013708 225 213 696644594 211 513 590946008 980 886 589349289 638 749 695801224 337 159 103834432 874 147 773640319 780 95 917205966 928 126 242644080 526 603 661915101 462 819 681440999 381 392 483285806 133 621 541640185 906 871 276382202 494 808 837387102 640 66 331853936 525 776 261763906 178 466 787361139 507 453 4514177 317 583 178120691 606 445 832727635 517 187 98475506 376 353 935659353 462 663 20038324 583 233 710116098 962 633 156844106 534 415 314502777 595 232 144003753 924 795 330496960 963 450 372201069 932 601 956113662 543 870 847366509 731 28 45175312 144 31 766232361 609 632 551566340 807 856 291371017 485 823 694932495 592 110 93250758 257 425 434488733 360 693 97274725 850 423 247918958 722 107 360354124 516 795 426524772 595 804 939504770 533 672 692413167 235 833 327509211 804 192 710114746 883 2 941017153 783 199 373509895 989 765 293933708 902 873 779273998 686 564 494835998 781 56 844334741 354 387 568269587 393 251 674974062 239 564 982782924 348 314 882933664 587 810 739981753 49 688 189481705 722 881 508428278 952 841 486688793 783 733 758879643 57 34 590736042 334 411 344800455 602 129 355595763 373 418 779394371 979 858 230756188 681 556 746730015 322 485 54834152 721 195 34328827 335 987 635122524 885 939 825409241 226 335 742977744 268 915 917093117 64 720 753299090 699 969 336591447 342 798 466002107 508 598 445755366 531 773 52189660 454 133 610081711 201 521 512177935 357 531 551574593 252 812 581787437 980 229 903737908 174 158 288415999 988 170 62041397 427 319 159502686 804 184 31950833 895 764 221612393 633 83 45295488 517 662 50389301 908 526 354827427 598 809 402450341 811 31 64923150 808 109 358418886 353 817 889265394 882 177 835420643 836 62 20278035 506 15 550582966 750 792 504967054 659 631 644586315 721 187 582915626 925 813 663404659 543 731 718504785 807 302 92561587 720 634 649419348 558 199 42990092 470 440 593434220 153 245 301037396 57 985 728825506 798 399 231638942 280 991 146251435 199 344 136640486 466 582 434357758 150 600 890735565 308 87 417149949 554 407 865255977 464 385 977179913 579 573 644332298 757 638 993977274 214 999 247903798 811 600 94889892 319 278 691158517 405 791 527073652 998 42 266315464 361 783 517248905 217 693 988931797 964 489 80205133 110 285 268299264 478 557 86277655 826 680 386311162 381 887 435009774 985 593 910631331 159 666 84250669 256 803 74337209 480 37 393168901 806 131 841113261 460 609 822008937 42 21 640240017 808 315 27917331 175 910 545051764 144 879 680708182 500 549 213317642 177 976 386868850 547 614 326372956 702 773 883141636 966 402 96320867 206 608 629400499 350 881 785890665 249 918 494107272 611 204 980847641 836 48 204807387 753 90 882413817 258 127 297609035 616 508 135598033 726 26 950515645 925 744 77834976 445 66 822155952 63 159 187320805 617 884 675114634 197 659 670494372 641 241 670528747 837 752 623075357 758 766 106007962 15 464 375919065 460 140 306761275 938 411 409448445 744 760 296821290 801 284 22144312 484 718 857769053 321 865 950805896 252 819 926574013 18 597 67173187 54 890 473072841 831 78 454798367 894 500 969182959 870 141 740694833 654 303 62205441 583 881 175365138 535 853 546647248 351 545 490169999 356 175 231249943 841 858 199069951 15 675 690839706 100 25 890118345 656 830 662446692 255 848 532285564 847 361 870051566 316 243 612176485 478 291 163933338 618 637 630196857 631 277 692915760 505 981 202546635 306 182 46131850 332 90 876433563 372 219 631937974 922 193 701396014 224 89 863737054 650 990 951806417 729 592 275245019 850 353 754655958 148 345 17545763 7 142 672615119 768 325 389324855 561 633 57566949 684 823 76606142 984 956 675198017 168 930 528551730 797 577 794094610 519 839 344875046 167 593 322518183 164 907 642213778 110 140 540027751 454 17 295001721 976 739 824864047 737 675 282067534 912 317 37628283 492 576 754092597 273 971 887610708 589 246 256545383 963 540 828462468 144 787 819771460 661 241 266973843 768 701 427530873 1000 322 113005745 440 113 653074222 198 6 461399371 38 227 132501022 686 171 260139103 616 300 730335067 527 398 736565451 845 309 98386611 165 284 618268499 8 181 231466428 762 257 998097899 903 5 823713758 499 314 567780294 521 466 976501007 578 519 739261447 191 199 781401176 464 224 98989225 279 942 740034252 107 613 51065767 545 553 289508428 185 657 616177684 217 513 341317975 586 778 103688823 137 970 937092673 266 372 414969365 930 348 36103795 43 971 218214441 744 660 618977556 96 503 989636769 88 114 686866990 128 991 15622209 207 738 501869117 352 438 412451679 796 434 744075423 158 271 626779941 771 424 834369796 670 710 705640693 685 291 357010916 205 552 719862785 123 232 225807020 417 622 61375199 325 312 108947177 515 145 24563531 750 133 729150165 239 4 701703337 772 222 78684799 182 331 839259260 495 594 524838525 508 830 473743001 15 911 837928077 652 662 208489119 148 151 70985942 425 875 60404529 59 123 916256202 984 282 747335677 176 139 165957279 117 965 499728917 859 664 283078512 131 778 204208802 915 421 828213858 57 45 910671606 175 562 359782768 843 108 912787930 437 372 77168646 968 508 692563081 25 167 458083056 707 679 179350071 393 759 112108490 370 799 247823605 929 687 762042654 24 900 709498368 762 51 666073528 281 47 325502461 754 428 148554716 514 568 192614801 862 153 716165357 273 968 999371860 733 136 406810438 917 608 197607312 894 425 113220618 824 330 976788674 66 790 563663328 236 894 648056261 912 584 899924633 423 62 22717160 313 552 987943607 559 434 574826002 960 75 651956617 694 14 953143408 154 216 791995319 37 925 146083174 779 163 952951461 702 10 978419503 512 630 856720116 71 995 875567377 249 168 752816266 633 873 953260083 870 931 222795682 339 244 900430681 830 786 349158882 480 993 869060417 635 869 472465465 684 771 795079576 622 866 914477959 678 214 823816320 158 460 575239711 544 607 917612567 205 872 146650330 575 548 651533082 765 560 72931700 567 353 936627233 542 863 656421873 699 90 888177009 351 782 162362826 568 803 118557442 113 802 910732110 991 267 823323294 765 767 5759502 662 418 321535184 688 85 184230910 558 902 868868799 834 584 834456177 389 43 776808258 112 231 359786021 542 154 326189667 371 476 845912712 917 150 350939877 946 173 608652092 935 853 904026902 65 194 995475395 882 916 13849465 134 640 684665852 616 518 94388879 374 569 499974942 327 721 5486764 966 114 483527651 915 788 778312217 243 453 110401488 29 272 187836032 226 739 377776934 603 584 711464249 410 710 965036921 895 721 815102880 978 242 149218885 349 691 800897984 661 239 171363860 646 910 723768544 725 374 473006658 608 906 246494566 80 283 126262717 265 549 719331737 298 381 997579695 132 779 642703950 510 509 405340627 65 410 53225767 600 609 467379937 912 907 274960821 506 263 837500911 537 42 379289299 47 97 469022897 167 776 537429942 667 79 492207757 329 673 646907071 362 999 741958195 909 242 759364022 667 693 88471966 31 991 997531953 522 726 931595684 251 846 828242067 141 77 403183765 372 240 368653745 195 260 565096484 854 184 266640552 820 177 803399574 540 220 424089705 509 527 156658129 494 575 454842297 570 313 666474820 637 861 696792369 482 161 2600891 567 423 199122689 463 302 434912232 569 476 308933200 344 159 774138901 535 942 631695692 226 805 870066930 717 534 369894738 641 321 853294643 768 690 918647076 37 695 841787580 289 10 153421574 139 317 625566264 791 139 173764916 223 145 913775542 436 153 454487387 170 795 487431235 809 215 267240666 305 509 390933660 864 383 289509570 930 874 239341996 732 601 905479761 613 453 942085106 998 649 488506632 979 747 689710645 245 136 479176109 101 158 507150216 426 710 526457051 528 595 367909063 476 771 177652172 502 204 709011647 725 68 592519203 640 6 503893424 88 421 387473138 871 43 567244148 127 215 135978254 376 227 84186886 470 558 421573538 591 475 756217131 926 860 81916081 374 663 830867689 305 433 226700125 923 133 352882018 410 490 537207514 178 103 56528691 874 815 525501849 31 254 732249387 33 797 432077813 725 951 671509240 8 916 619031561