1000 542031364 472407086 851932874 500378863 833165373 404160236 833582921 786042773 98766254 271885116 105620672 287206924 293345024 599989981 310387646 626259649 263705446 721316150 268887243 738036166 270085050 76628294 270435274 681642413 938886446 13753117 941126229 19853867 681786846 252598096 757938334 253727287 929135851 460047452 929347346 498347832 326347458 403902365 328030153 767648365 169485601 463520521 321305441 487775572 151901806 417764617 179047322 419047648 439673810 759975804 454852492 866173917 800189393 106747914 813870613 110161374 709279073 17987037 743747074 73393763 119223771 434105864 120423586 468255639 383867693 803741834 665385724 809328184 140605667 363050584 182230804 679845019 389712741 278828287 400786302 348693198 844979803 72629186 845147047 92376429 583699249 686216314 591405951 753239240 539315924 617338900 904882495 623811048 494567590 568420621 497400355 568981653 554050831 729356646 594643664 744766854 844138727 15478083 879879924 22166925 667998312 988220632 675474940 988300603 783374951 921086829 830551206 934315846 907415133 827459628 914004309 827742080 174464380 636066090 241371136 639197918 791567518 720655114 796406833 803299514 628553266 907535077 644670369 917045360 721666236 243812911 723683456 397989477 819571736 497901248 899343962 498209559 331123508 825821061 383672990 898218830 508626576 584757992 703633932 632696201 182672496 869578082 182942979 871383423 361047837 220123782 366326579 225148654 326696993 534105835 336204308 614946725 150449160 62530846 151517457 63522570 228511812 325934378 241222808 339887405 292874446 746026218 368996895 746909925 915563957 272346481 945798127 319617073 314681036 100814355 337441063 102406270 77580691 138239843 109722368 139657937 39631068 472918564 40900620 488012073 331143479 69418157 360411161 101468651 51793897 324656623 57231995 686569415 791077067 95097253 791481347 95492878 866630291 354947908 867967386 793058871 533862977 131538332 535759805 260884428 820429747 969254391 821206006 970688484 775047995 297379097 776492715 705077677 247832941 166271018 361732501 365838821 275992897 282240740 280971512 289886348 486067482 265701829 542003533 299328531 877538743 900936799 882036121 911396945 830029485 433203986 831420704 433542553 728679396 558994787 728805109 573415788 219486147 162367418 222229763 183703277 698980122 994980166 702009496 995336989 192666829 306661539 212897063 310047017 932165540 78229192 932413166 99787222 502829479 781149963 504672917 783808049 610019303 963402537 613888593 964913981 96468383 897175400 673345331 900647071 843940624 503840058 923206406 505872403 980430332 599648415 982972145 822298190 911791863 102210969 913882359 102865920 83101771 626953536 105474662 627959506 70039295 531556305 70956537 618361331 342106309 239140051 343173868 333188854 722112927 354278497 724135647 356359161 187910005 13713607 191065873 15230778 650140191 410148004 658437743 412175049 631062451 679315482 637902914 738682985 19654585 895149796 24064649 895706388 771769999 115823228 774563791 326830190 962415942 44254813 963318545 49725481 300921122 101804123 301016017 112395805 468561987 966621132 473200312 976845244 218208464 406387096 227479433 421326358 639868254 8460553 644894873 11692086 812717794 347062439 862088379 444984770 395850083 737204320 413090665 754111532 305096559 115479137 305836535 141370462 855279090 214141834 857938952 214399910 547926411 484277398 551955370 492596684 248320759 311020188 250470719 311381049 465608976 804027386 468055769 810531521 989933845 886496418 990263726 888463360 16288495 347812732 64296324 352147477 350828392 653879534 358835601 933693943 381653635 594097294 382247706 599332947 559916237 368410663 616288093 641641267 853393290 266088931 886362196 308296082 885998460 862391256 888377051 862453021 595307582 765126550 600277557 765232685 694507646 532375685 700714320 814725151 826628306 347435490 829937614 352364823 986360108 359360088 987566303 376128582 474809950 5282078 539788627 31366985 654849 62374437 34473010 457718569 513496192 278985676 573373106 279890276 691315253 741017586 691455920 742737311 12006285 671519147 413926352 701347521 184876207 913229141 186830319 971180406 884220313 647801583 887311151 648932698 702012995 434036580 709187235 456916833 515492191 628098746 672474007 641084888 709363036 912912747 712907322 912964095 353163385 363725120 472764825 365796304 70139060 759241400 108969432 808856963 500698635 964447955 505289312 964945631 495255067 926400239 495352716 936803566 141578304 322035632 144989350 333269880 806192911 587010541 808389263 591565178 231464180 518371052 232338576 705277728 281555559 840275175 283551032 855519663 17761739 513485048 163058117 572547675 17734509 727707749 17784579 727837197 13332999 830986082 16129428 832407593 353193858 367519531 355229005 375285490 139769799 360837379 140072464 361377660 54018704 211804113 66038514 280693603 617209165 397674373 618864266 401076383 704048126 990229395 705635326 992784949 577330099 473875150 580292902 474852276 163226670 618958611 206386025 652062691 319310378 305471830 737134750 352364187 842253938 333394294 860988011 336566277 793978002 509425611 794985134 515526071 825647717 841161164 832916448 879906122 995922426 57211329 998518549 185483854 897219680 567121626 897480488 572234512 197523393 656328953 202579052 660360178 796195829 694835885 797401782 698241103 730752487 402260285 747227266 406812304 417559855 435015720 419908272 437951574 698292963 585923361 963683915 635249241 628726512 423570444 636333460 526155126 934572536 162154020 937494413 194719509 460735387 711792102 464903377 773624634 456720983 112844984 460587179 449179024 829814022 807687822 876394008 956297554 548176450 638315152 552746210 693197449 171631026 538169434 177890448 541678467 624444068 118746386 626507218 707723189 357672345 132478739 461343083 732820440 43452850 555475470 49266524 555935123 321110791 392297265 323831138 438813667 950373973 836942172 950922800 838296069 14013627 220560878 37119203 322963078 15991065 231594130 55747418 233259021 294529684 212481382 416015676 232668829 731309451 847186780 886300508 872456942 183881320 57192663 239983539 61423067 367837590 663067158 384739412 672380354 502769931 177311234 504742350 181200907 839437605 402661625 946942091 458809643 366224674 620037510 785834894 622475407 689054763 932214283 689908733 933223288 45233600 220373857 46779405 356187869 70703592 438945220 75856119 450201865 276581051 472922401 315585488 478445164 9478264 489800583 11405706 491455662 854204990 456424322 857047499 861042809 683204067 731505353 684888886 739561044 318646847 258656012 338483886 264530524 405189019 158736539 410798781 598507638 203918070 199885040 204407440 276698119 176476599 394933101 485832315 402104961 511627854 120175535 513561981 120454041 366686131 95859287 395890215 162319635 907444860 895944567 907606594 896321948 755652114 129748938 755953092 468180456 400090355 801254078 481081046 820565612 862242565 285351971 864132297 285501322 63434922 865458542 313420094 890063367 89710230 212339032 94191784 239013794 417806976 773899638 432601044 779613865 530697641 916956753 538957256 924964791 445411529 146764628 445990279 172584183 864328353 193166115 883153337 194798627 416619520 757772016 417008596 764948190 768736997 837571161 769988338 838494459 787563408 313384620 790180551 315363336 152477973 793066325 177809468 812216854 197960055 736757538 202898010 754469150 73800949 889990244 556052946 891800156 150227070 445945145 153179206 452504679 888552933 263209976 888634936 265763882 157624876 536078479 160913008 537460464 860471799 819533094 861199282 891924156 52453263 303876301 53596850 487624602 329141150 723184135 338484758 729882984 320047376 483551023 320832723 488461360 484941304 145648720 492983471 153872750 224852995 651419364 236994712 664758451 425039217 140033471 691977595 144218387 907625780 128038221 945945756 133455200 310347694 273305605 320819898 277016717 542453047 186155762 560602026 186815042 294674732 516637801 298369490 524426613 640376702 791165978 683314029 816701944 678143487 549854360 706299511 552416072 595034209 311680828 595630168 426933422 566961885 464508302 720410218 468414133 545852693 393942528 551608795 394998748 590146060 156387768 591672039 158057516 258979142 422192318 264121105 423787570 662063164 407502761 675076952 414194772 913551646 327418435 914073806 330303426 58600444 775350575 621614179 777702635 970952282 556563823 975686483 559174013 797673445 45544533 803291354 47377093 195801980 626448194 212018811 709637190 780409507 702283720 797255046 704181295 904869213 180770359 905884597 180872268 683015745 169996395 691489626 172690366 821022015 283748123 822007325 308375156 101544587 795249142 102114171 880675373 4573055 691516793 36611693 754360149 696472432 392921604 759819313 394352072 782007914 773653504 801405753 774153858 230829762 927428794 321308236 927550915 829114906 615362103 830325451 674123507 917491168 407269068 926301754 845597108 989832471 627247048 990475998 654568257 810732964 915033578 812329346 916228708 382477478 191880289 384611984 244484365 386361140 537054175 533192732 537285917 782990123 210168391 999958464 220111939 885234826 566976213 925794426 598806745 114727251 995471904 130055900 995652650 643518976 208095925 644816786 209394639 503861361 25752128 506349794 33876154 47683154 703189756 71934285 703385669 193044465 952588540 194153942 953926162 876298273 335168694 972796858 336974711 847882002 830321067 848132437 831945202 115683562 139521415 117580365 180699375 78381879 496736127 229408084 506458960 40005156 865319308 50208627 903278877 776999583 812865898 782964203 814015674 183273082 885822365 184587901 949299870 951360748 240356458 951791615 242504985 637836021 191634221 682514558 222506868 371235928 30598285 403288043 54349842 593780352 62271078 604102368 63069591 311974380 607445847 317729027 608411100 202900420 904142288 204310649 910265574 501746322 626444989 506042057 722430601 7034766 562601009 14493340 959862614 441788048 622662620 481755769 948900595 665919092 902451492 757751325 919035404 892911531 438196256 939780954 494963494 200058911 532856904 205716916 534045473 285654065 995804459 287592102 995906563 678737671 211639177 681495559 219483960 124112206 176364402 135633834 177202569 764199727 664411044 769051654 667662544 7944509 811008116 19069943 935484705 566582690 42195753 573349537 109426764 380091584 392280634 909654552 622386468 698044078 764728038 745566468 767975006 251657526 502714675 704948717 503262893 494856724 17543972 498811559 340637729 599019642 121792833 601014931 137079155 760917581 319337830 810531464 320539661 783521365 266188221 801534355 269136829 405114132 71593755 410173591 633934695 393585428 338043968 395275830 339057320 487322797 513997107 489328050 589640601 751026426 148305401 751131665 217714575 27612084 448578498 29628840 466861766 853009177 838443048 856053671 842030775 7086939 918762274 118313118 918891000 520602922 445952384 521332933 471985680 160791744 882958206 178412296 885208067 493256732 45317985 495339028 130297175 317199169 91665136 707801880 96478840 854885112 103534190 860548195 327966685 726949148 143921449 730770719 144756975 793262781 648760796 824236632 761148039 78878808 962214240 99144642 991281679 716747498 52357100 718512816 56353520 528161527 925156993 529681296 927002674 157025741 220437266 159270561 224600085 74531487 891808520 77719079 897098534 384905848 110593803 386874654 204865910 40572958 243090500 64056816 555362467 831870138 651877614 833531999 777381803 590725003 498056503 940275039 501355192 614778534 89074229 614900252 116632349 927721608 550048776 935819799 649674192 246549910 719057253 249428529 720567092 921152024 921909866 921298723 922682436 736212795 661126196 750169480 816305671 719454182 700551797 722508984 701911526 697405206 840643013 904887886 846170334 93118026 934852152 94977854 938734391 874595840 116533023 925733119 477099251 953346421 69958118 954053331 153783852 233858440 11936797 361468192 19444764 386541260 604241883 410158078 645310155 513198300 83004400 515937017 87025169 793737936 944025295 817737860 944436553 315731522 3752316 384159226 23771332 290833754 104737646 292830956 106878408 895512282 551488747 905888522 607630496 133079446 108788187 137097979 110192664 41721696 238031625 43008292 238978049 39080253 220800222 39516776 295902545 800218384 506830126 803446307 508341699 248837957 600043467 249554970 601998630 274986763 700351440 279735321 760222063 619814734 272802870 629696714 275063407 380657823 127938969 473573496 638940516 978978758 906765724 982230816 909429977 929092819 432768139 966787918 439912638 348198357 203216909 348271279 204486560 202869302 552709612 616523856 557894082 69663200 975216346 838366017 975982488 638273163 239397877 673577849 382819525 92290983 940370997 99295612 940763786 232014108 771488147 234268420 781771479 578044063 792263086 586631516 793851090 22533312 635648154 108533323 637031410 76898493 566243113 168289644 571740949 23600814 101923570 26221495 102580043 476300643 383182958 481178729 384722852 917695751 598526742 949717186 652016176 203828977 260519291 216879779 293987340 583367482 762755723 599638984 763732784 568913206 347250297 579996813 348787946 446460133 371760946 616171591 412181313 74677622 575903025 83580837 577245179 183048742 79668929 190856088 82870479 193737088 612530956 279029103 675189060 653677948 5766541 659211004 13623703 419723343 622993069 425693628 623828941 17913980 508836209 29568977 511143528 146910397 188849171 329298230 204636572 677407756 95093152 684591669 141347990 312091021 383623634 313813494 400366876 635100793 407578382 706073819 409755271 44829045 863778101 45102641 932791967 727902099 485322359 794559373 725605753 259635272 604942608 849851661 685406497 345559829 138322126 346974781 139722704 846281271 713447729 900103053 713991962 680097033 500860556 682727900 580936676 986368645 445976477 988481431 709975883 900149154 294873359 909642194 450544555 420731743 993406907 422180923 997960949 49335405 388904279 61006210 390685882 980188606 113679419 980232964 131875982 17026396 996034799 87074552 999343228 170197584 874524693 235897207 942702730 317824692 613017402 365472625 614994025 702093814 101763614 703918750 157843576 309528139 673197668 310302684 702108273 281280540 749315474 493182903 789489709 457915679 151981346 569300673 155571715 29736094 798304889 47794218 807143086 783389850 165172105 855853629 280486252 88559578 439536179 88750521 444274979 967538088 388347391 968675860 395133166 96850496 902389294 111617472 903846840 99769586 358336033 103077592 402811284 894350772 468436438 926016152 972023861 86074537 952764153 108293417 955176192 549958326 930623896 565005486 931353910 512843672 91488458 539460475 100471705 112559299 907772531 261325862 914936553 855089219 408962368 863987518 956094816 542019724 248428418 542187208 253351645 345571411 662221800 346034309 663013021 615040661 210414855 616869307 213784243 359573202 791085250 539709533 800906287 565667347 84146692 587791983 329660623 256555509 327330430 313430047 332583569 822643072 877053022 822900096 878608861 585963105 298224543 740405980 299670380 34125432 250652541 34861318 253165883 206115267 925076823 977249118 937587212 264784081 189398587 320673312 279192581 619114466 502395114 619372375 568910082 171856846 814307857 226485223 818201954 434112932 933397336 449604060 937907118 43520056 500197393 114630996 507370315 658111990 617562676 663472089 617895086 646889574 11882016 707095720 17573163 32277803 27570226 48074131 207877510 413004114 812353197 713344144 862895472 814590325 281777002 816884646 917473400 441671875 923766099 444996055 942067930 997294647 117601928 999359432 120041358 938752971 849483961 939628099 874960969 316241568 853585577 398550381 853950225 845140843 208017668 861072613 229075379 85633406 756186292 86329234 761487662 985109769 441237500 985121395 444751437 153681244 371683116 168568551 372509284 623646680 316283963 628208649 466349754 181499746 458438222 184162806 459773307 868736736 629692182 869334415 676477197 225497580 432678374 226911496 435821624 353543256 974068901 361534756 975290405 783496493 196880073 887107827 197614239 787999409 929704279 788881251 930309007 651296626 917405584 667121630 917801663 528765776 847196625 598542330 848796933 587747558 586388919 590141998 604397046 423222204 658759011 462256558 667017280 984806293 405202527 988244028 485843585 873215584 957164081 873561738 961640574 249019546 402943554 251200401 403828718 938437884 951650758 940011796 951758298 362989728 610948549 363418933 612432727 804630861 679844205 804995656 683104175 362835055 849595985 377615715 850051076 438582641 843710621 440403696 846824786 866843515 227588534 875254815 234127330 836851094 292840846 841072099 294010092 862708216 178446240 862966011 178726172 309240515 615348695 338662012 616797690 202881289 250062252 605927141 653861620 550579397 424602083 565057379 533487804 289751640 536303666 296934659 542097862 916681497 612838376 969153992 795978296 840291720 300698575 841951202 308949853 519608939 773199547 535019846 898419937 271422038 716357418 273744922 723201949 184275655 242893935 184701369 245989001 744219814 862368815 744247823 966434511 762122275 806212674 792984572 810761448 481161896 819336738 493254996 821965738 992358045 773492856 992765190 777147435 818980741 413084910 838718154 421369829 473542125 51583321 474845216 142687919 207941376 972582068 244225225 972805200 210994075 676162234 212904519 692942100 518002395 60578489 529102820 62011720 868244522 609119950 897540766 614584061 425345996 407294985 958985108 475191409 994246760 552096739 994289186 555087345 648388431 369069603 649330269 372778764 132815048 458233178 139140470 492269379 10892610 231182144 56433481 238550331 219106017 381488219 902049862 578626800 26023647 292359179 32494586 340480307 964434282 289556553 995645712 294972040 764585580 702535335 775579019 702741400 256075842 191466319 258173568 194030280 942259509 529662785 946848584 539012278 732665126 927867345 785588459 929681616 809502389 794762741 811306392 796596825 481503068 187842137 630816288 620707603 63653007 196445956 68590184 218114603 342695429 54020824 343180827 56366034 542671634 448220963 551781605 453276206 758044778 227824027 758869755 329052498 983336074 36004227 986514519 125588772 85775875 414761422 327650095 455114221 20792268 952175909 201969832 956602668 117580796 360501292 120258442 379080318 508397080 170072667 519443163 171967738 829932097 50510989 864236210 157897758 672918814 294136874 794074708 297006573 728262579 872966417 752455179 873278988 24647965 379659201 29071362 382014817 156720534 760154847 163998783 760387785 812962058 364948816 823440487 367334331 469388456 473663762 483015452 541284050 148957979 228515462 153146632 229481798 446178441 421172419 462788303 543609854 529155811 799004956 529161430 800551273 383387779 753134775 391761949 755940754 139596949 338350481 317857236 374618265 2145264 549207397 3416793 822244030 329254964 318185471 398153663 320210554 901476077 165143479 946238324 182767033 343195592 438688379 359126083 781388260 372040022 17402433 373111869 25237985 74220501 471466522 75825798 504331961 207220356 514862931 227372221 808279445 932009137 206657337 937365764 247674710 278721506 790664036 986085117 794248928 15957213 982092092 62029855 983029769 86472770 229853978 111535133 229945076 380760742 417364107 392180996 432956291 88030204 445396539 91268649 450253634 729974558 591837084 867857999 592888108 651971118 707800692 659142881 711679615 163400701 953078487 166864533 956729069 131185712 657996058 165179379 671842701 60554545 818435796 64618858 818919339 220243306 489683492 232813191 842861036 557525626 997674262 558136968 997689104 881544226 147766002 900508865 434110568 904814481 249145627 907136293 251600187 636825472 493800363 637325732 570731560 716661257 36684715 718104333 54682240 273954446 14966270 275238795 16605408 121691355 878860658 133076982 881673473 384659954 519309942 388511490 529395366 442401898 460518970 443546803 467018613 613419713 9752417 932770746 12119887 415252105 461944235 442459596 468156330 252802681 1934714 282954079 49056690 169992738 849018230 176103371 849178356 835055105 363282195 836870898 366493337 963618959 770951217 967138012 772976849 104145031 567428062 107828536 576293418 620395446 237258887 623529590 895947991 941506179 477634955 941511748 488219483 541937809 118925927 646836935 239450425 260322292 134541943 262295580 137186645 219613489 918241669 228235525 918879399 747326888 179107575 748759582 220992239 436222999 769715844 503992997 774076521 151730544 681687617 235926981 683043470 152038466 516785186 233993007 541545965 778239477 258871437 781005532 813779279 678077090 377150567 678152087 383869580 654037025 877153307 667480706 894932443 87691581 642835386 130909952 647563402 31414095 386462382 55228571 386552074 425482123 857522201 431770742 858774738 199642290 922536659 202751768 925146686 484951317 530202547 496987404 701919361 547825741 296259969 864483358 297241534 303018475 819099120 326267184 820048937 102698795 454564699 103034594 813701695 294226164 828194412 298906182 828396617 537136137 958316784 712437967 992291269 914969083 797952298 919548382 798647138 515552949 725279216 534704394 725285429 364993010 941821554 518324636 942558931 119326904 693615264 147825340 699822445 141414555 575552613 144444114 576289067 879711947 103597947 880859392 401935698 969438544 973585200 973346857 973591253 187465125 530206578 282245233 652134904 65643009 842453087 308873986 842906190 8290629 386620071 459564404 390260824 721808190 16430163 722364182 36547915 708354713 317309795 735730609 336955156 207499189 897197828 597871798 913444970 635996338 256459632 811872354 322639066 197733319 693315810 678886036 967736140 433032579 680023279 561463595 729661284 59833944 642763111 147714628 682748476 339397862 696863314 430578821 696993968 77085036 144782990 81583722 186386531 614189556 455834272 614411097 457223470 521367225 142444038 540404546 184604610 955035294 689167123 964571862 690386955 470996753 107738141 478329236 116898263 83573431 692275160 93737462 710181171 212742405 680430863 685535181 684735648 639462754 775091531 697787274 776950441 573889056 468724800 575486057 474019617 285911462 687250248 365715306 742596753 203796511 877588607 713826936 878236723 254569050 66160317 272414034 172140519 665071097 835779167 732762426 993125692 220195036 1382111 230228841 10569856 979598896 798713901 981945865 799076384 42724509 700814230 118052320 715658943 927757351 495328601 966428656 497293897 605117645 677813685 605952856 689910513 437291415 176795463 984054324 179533942 34370529 50657218 36696804 55215940 317358185 626314492 330968475 631020857 725835285 185731734 741758783 256801544 747281184 970364486 747305384 971075321 58021423 993870298 64514953 994754513 546821454 35743814 547022623 60592077 963819883 10100550 970499412 23442478 69930072 419929788 495426882 423895071 123396620 575443503 136958098 743391839 343365911 660654399 471149234 663927167 77866994 335648719 125410212 337805290 920686504 403760479 923752396 406479483 798087087 167548515 798416462 172379220 543964421 89153505 545410996 94727815 20013796 485568439 249507991 531979176 456695135 940965273 459816841 949384902 494660626 53671201 522912282 61156359 465526409 374731393 482493610 422397078 739284870 541796507 742019015 545761476 971792967 765557387 975931855 767392015 173879742 181412073 296604148 185455410 390998041 895325543 449504093 899460746 491455217 122451375 823823930 185510619 396332782 873986552 576998673 875492062 784314264 807568455 784862348 813725693 667388663 46475406 685913473 82800904 888241837 892544527 891185472 893625304 229924505 110244521 241245922 212916488 326927500 955804265 330998200 978268527 536337512 380487489 538193350 543639873 204547164 799111283 852715927 800947571 90132140 130004033 94617167 135250162 192331266 537294679 611808005 966949808 927160475 386097927 935769831 397435738 339410033 221101612 344670951 883350270 767068233 868492992 770871322 868895668 232388147 633829903 260402525 635568235 885121161 198875719 902635925 201698196 400625896 517227513 402689422 702151151 446846095 113722717 562147234 194042104 441990799 857996285 459035298 875298664 103395768 615084388 386917078 616335436 443964760 588772592 461415097 753979355 392167175 976490493 535337154 980479390 935555 482404776 939356 488317067 413620478 566209566 593984934 698122423 378123204 537954398 378737490 537982591 555759468 604591197 557074802 633404866 947996900 146298624 951469465 161602350 388810347 455729380 391485804 746662104 689469520 76494552 691691740 79010970 640530716 693568126 666461542 736670241 754235478 685298384 768814776 775355195 824593921 651491262 826953039 675177942 348701190 455596645 356594604 457869288 950984404 691719352 950997305 698792557 542995874 439200388 657655618 451624411 753426730 606428613 753608374 693503840 105172281 702555456 110820917 723386717 331929066 354129172 376172662 397493356 100297119 40508515 771814125 276235902 513196000 127673462 513895663 196877122 230568011 965503896 232104296 966967644 400079882 73120494 534096853 92657007 345096604 130341745 503420854 190549509 779243282 995152103 852252491 999131720 646630244 424829904 648965224 427884458 246728541 673390027 247784171 673734003 630485937 570180711 631404341 572560439 826868932 241001802 827073314 316438976 727205344 545892509 751402323 582769728 791894955 146789746 793159812 699520797 434096931 196342152 466095911 262048630 310601540 524823121 313427507 624570651 148878777 27390621 149629204 30426676 875101466 882305224 889033917 882934822 589013887 560132253 601605213 561850496 66556382 648559615 93170746 657264127 11039179 95442479 422179627 106854987 222164027 386834149 223159181 387610051 328326765 934543216 335094976 939555331 252046582 46484516 264567450 159738738 378172679 215213502 378572849 994597331 113937575 724350998 116568375 727575968 182518009 132904463 308784297 144129770 834643873 458385969 988866226 458693963 710436943 404555047 753412867 409447470 19069054 15001625 19922576 43826564 244209788 493459645 245897357 540129340 822484334 292817009 826683129 303292717 721471247 518603205 744679467 519472767 687288114 633791265 692165143 634434802 199146020 712794755 249969426 715642741 38617812 223994078 47342088 227149489 716121138 455011600 718086875 456874951 919020294 39609218 920268096 41880401 222100670 577594312 222715429 578462395 623331434 502573180 717939473 607016809 491944086 785154614 507689661 790508150 335714794 606118268 367429817 608031121 225422295 978850830 706914614 981969963 729175878 68144721 746974420 72951270 764893980 470020891 779985492 646808403 567932230 110714872 574572381 114002353 631002428 37464705 684340300 88549348 893889213 718955170 894497935 770764261 190845806 220272077 222068490 273427615 514242918 175513034 599138943 177541319 770265247 622066246 770578062 638873877 100516938 841705009 101503731 960103914 309502057 761966512 313576460 779195581 643614775 819521277 726030161 823413949 363418649 264208723 496887377 837652972 650398812 40635604 650610528 43458747 448501879 295543940 450578785 315271405 530729860 773969771 531988965 825343070 871759377 186006283 872462048 984755456 468944367 354581110 475680159 358330140 896501445 519348 898823462 20107055 131832236 364915187 135401227 616521551 765893107 632407579 771221701 642942992 727560493 692229371 731185158 705306440 881811091 310626626 886891083 395363645 833529069 996193365 860861425 997652573 79454443 160197638 116784771 183391471 439255690 510014912 538709073 665874985 565682227 304081985 566074568 336840976 211763947 778543964 215214120 780194785 140413528 176078072 141610739 366245717 357113479 656141811 390886255 714866009 490200389 780906493 498495957 782794024 721246614 9495607 726472418 169084170 733971915 247195996 744377773 248039345 362352996 491928013 363551691 714007794 968793320 47862197 977308747 50389365 906404756 277327363 906727921 372602383 186193440 185622107 359670147 246124637 234351518 968888793 245384848 979658540 400257714 294999467 402620074 297394605 738345500 704002979 739313750 726409043 59166753 691971406 106805901 704351426 924140061 926538472 924607999 927096954 185317372 999544837 189245401 999589840 113727735 531414430 202556125 532026652 747766994 872028758 828924177 872527233 553765306 481580829 554221717 489342368 914335229 721328279 934777202 722029945 13769156 256222736 115179415 261646188 376299038 334330102 378171834 349080988 13280192 232060368 406393842 311637694 748960309 340005501 749493965 550495798 536146781 41657436 574647896 41705639 848377897 286378445 999428609 292576483 286593634 488907141 322489631 491665731 224952177 578199192 244327102 578554307 351756013 34312399 352383399 49389371 799912153 153577681 819295467 156148969 692763607 27112318 692871135 43901067 611964570 607106895 612434218 607131525 32092174 17661469 32888486 29741936 280265373 602686583 311860204 602849773 47050688 558537158 58196573 802993166 111054605 20808 112002640 48860683 118868210 948989456 139230116 950739361 609392720 828356726 611458609 831166560 398241986 912151892 578163339 920658080 901150315 762058113 946390179 763565629 398991545 404691535 671191631 406537005 970714460 630650034 973344402 848562379 57848962 519942144 62274221 524567190 517879326 671470255 559479467 699654656 263861428 686886412 364688012 690367738 492587030 214569101 575900494 216993584 167421936 235529481 497307223 291082065 177601134 156591954 342103806 167087804 179328223 749545576 182177845 751576640 38683668 827517409 48253033 827906232 378405146 990836797 384545237 998983247 61137265 703822502 68889219 707473012 316934068 9277500 381957468 33899619 697132894 848552145 715229778 890638096 64616332 117437845 84239411 119163803 83866869 908377776 186556811 911750467 16490282 15843089 999964984 202878753 74415512 633409407 180940580 663358513 748879718 266682849 817272013 340865137 941208988 12385109 946988271 47295362 904409960 922983592 935518511 923041561 655054898 874541205 659010735 876014348 274829766 183137828 291000099 185620081 605966566 297264727 607245171 475045140 416654985 321942657 417061764 330935318 756575368 828379528 757094751 867336773 650995277 860382775 799631195 860667308 195407335 578171207 197648972 592008268 447695835 803581859 450482557 822363482 230973460 380532333 382042330 381238301 759407984 390735855 760904380 504511335 65663045 538969420 67951428 539229140 58396685 579788213 67502253 584319546 693217851 233821623 694247325 237650094 575749244 103603801 590355838 135954596 321282384 199407099 347487869 612337857 192349959 8206417 478001621 314834167 396689186 542026996 400791340 706789174 448601206 426814497 450938315 431613187 16401557 37262363 24479899 319803339 194038562 592489290 198272881 746959576 37652635 161103850 61877061 162965585 828340297 620462871 832429415 655850528 22929354 552619146 154740449 589773732 983246427 173450138 987764755 553500934 264323532 834906134 268233164 835367310 415323559 295644588 419895994 299639670 929010234 187970331 936975934 330193213 333491526 498307436 334497245 507122341 699973312 750470295 715459220 755398269 735276022 103457193 957782915 108776398 448352972 783965709 578563953 783976794 778370409 588027130 780081116 591456839 16290412 807841207 103956624 895008192 558239908 867496659 558901809 927878425 525803438 194813539 553662952 195269132 582659602 668388804 587098590 727550105 26679128 529923242 130079891 582302399 751169487 322944084 771694756 326925994 755126446 64504796 783493806 69539255 996539804 722922781 996959535 723560919 494251828 460519916 495593060 462405758 682464058 185462686 682840101 190265561 793410560 426261893 807604957 428658391 309408959 347718880 641193307 439320638 14193603 732020560 456287570 733586235 443076865 697553864 502898034 699487537 475416801 199932624 488740045 237923215 163710937 643184369 167297706 655856917 641688851 192706759 642749114 827261998 69711073 940787821 163083426 942807314 415958587 246492367 430997726 265763037 842592851 62440866 843057140 164001238 555593122 842658937 741753393 843357945 719770181 153369811 744071491 162711456 154517370 460902299 155921282 463857570 182474639 943344092 452131821 943978168 365270302 110925958 365604286 120946580 618359486 186957766 619033727 293895563 327497619 838791256 328967277 839605598 45268751 778721202 47773823 809011229 997287875 588528080 999449155 598147253 522391906 122205807 531084003 126327373 584021836 713909333 587432429 734268001 435431079 617372362 449540581 657095185 918971730 101751461 920071126 109685909 208211800 332749289 208741489 405422602 100332997 313803908 226246665 420163909 39559440 556345963 48604848 561176429 472108892 737016872 484380869 737585280 115084080 622529048 146720948 819585706 371279463 675752439 372957199 676653755 366288037 262668702 374959898 845930551 139670563 65612147 407757524 964286081 858320098 566427790 867626140 591939988 928646154 69684611 936389234 69943391 555834182 236463167 557126068 237060107 685051804 468884900 714034955 472779520 230107121 1964177 242668867 6832071 340877623 270697266 353686570 276723506 452531940 695850190 460967347 699812769 320890187 53558766 326277816 398650867 26619158 743175476 31677326 745845029 977846932 643664585 978283417 782143253 756254731 573401599 888025419 574552981 452451436 600031022 452682510 608945194 17674005 69822486 21983606 71202331 837814519 311094954 839142598 315324229 918286638 481068604 928792102 720464632 274153801 563714406 920807196 564158865 457257548 742582022 461805484 754858426 18147188 962768575 18622041 978452017 298276603 44494752 319786902 46841598 111837597 640044050 152787410 651603546 590522463 720757564 598957325 727486659 209663785 412046137 235595189 425019962 177316268 594182055 409286940 596206413 169467018 232769146 563525452 238575155 733726899 460057662 734735138 460192561 212440048 834124436 232152612 902803692 102992016 370035872 126505165 384362227 879689801 730196270 890827308 736031769 754938025 162969750 758897614 173507108 545777567 40039356 546847908 216982914 536742083 135389089 538096360 139876643 294850229 773625931 295029405 776350740 548484720 715818424 551338939 727206381 867229713 121479023 883686001 121767089 665303517 128922211 665791948 142032248 176575059 39756063 357925112 87045932 858421274 945110889 902938004 960763103 35402352 401780604 48707772 427379922 888642597 706975889 912720397 735021481 102219998 71637771 110359913 74933065 24786558 651633056 44265318 651683392 653724092 947120044 654912133 947674872 16401304 142452285 19668952 143320574 45902413 587223340 67116514 587264757 558083936 433229186 569195413 458603119 337406068 745997546 347466854 808377557 65037088 367440873 144117700 377323770 192847671 192462192 194055431 287214528 657151341 71133631 698576292 74739284 891497759 145524976 893654592 149804383 269198586 105982912 269624375 817419748 492144558 13038446 600162804 14218177 143173760 26235320 146663222 279144273 202642506 63604315 270029319 68803845 871168293 100949286 871198942 116983108 381303023 630927833 390412867 631813228 913144344 587483946 914049292 590767918 724171755 738922343 725993283 753621038 942038062 637815467 945825510 808142025 916178163 757560219 916532658 775533811 597610978 527597765 678980982 555305853 490196045 645631271 491195084 673541049 551680858 730355497 553986889 866087737 84365283 150469151 204758276 154175915 813169199 153192893 827556735 155367925 848624275 882856213 852802369 884504414 393017837 858271590 394087788 859269366 472253452 519940059 473473011 526806387 300695782 227740055 302819673 262273618 765597627 850188176 774203463 851532685 812777746 618149525 820413103 623334511 847692962 237250089 852329497 238577624 351414262 365745341 367748305 422729676 493709229 285743290 497355904 883870640 303570238 123805148 305767931 341493996 425491211 283975096 432828083 289940163 634477836 72118131 636401187 104524114 496610814 284365026 707201073 567425847 288850413 17904810 366946145 219785149 419589359 334367866 420646859 336839251 89155977 83708331 92449109 141321713 287659343 264972798 290215450 444974110 419607035 962115731 464610255 962122313 608063411 119257953 701194988 136027329 577450268 933510083 580341470 938312227 486946205 436556384 487710343 452086484 281925905 841781046 466678844 845520646 4408979 414154961 817314722 418886843 39665583 344146913 44522025 344969078 47323139 622873261 575703007 623649586 752666079 693555774 800400975 697965656 381185387 212695301 384480387 218192613 661897110 802864794 664108985 872019949 817191533 848499303 817847142 856005676 967469692 368118728 968610597 409320694 447065123 404817346 541116329 539266018 608308396 738329797 611215015 778522552 69126840 618384033 75756749 993331106 379837202 565498571 455033284 568912136 550241427 231587034 604100502 263678765 115990706 35514617 170861809 80774308 38864994 514368940 427983472 516515507 627180490 859353101 631866476 862025461 782763668 196593328 785877856 222545060 101639716 7546714 105440335 9380090 468521803 607914981 529495152 608574980 265094606 725199299 307491085 726373229 693191083 340350142 838981316 341969061 138155213 413878847 139909633 413986924 242873106 863484622 325831076 864143749 104140725 247566122 106048457 249357197 391495015 896349340 404707652 933915047 284688465 36471187 572203121 44192362 834080050 559335821 869724264 666012866 126323195 780892257 164526618 785582899 324967425 712290422 357518017 713396040 675949120 510879379 678506716 513165512 233523261 908849106 259343397 909251169 308438561 832509072 312335697 833762012 119669572 56642141 123748506 221267223 412232757 367914841 413864664 454597693 504335363 530620781 715362075 554444834 12565359 592600945 307258046 650128206 917600042 311061723 926634775 315018936 267102939 532937582 271395760 541245177 355843098 834369023 507404719 850314008 345294434 764647962 671372899 765505796 783798695 255332782 927177039 255831156 189779765 497138913 190659375 501723724 259178774 838894967 259426785 840345334 664731573 313997879 715909558 320098901 392397530 189017936 430342767 190040710 138453323 601242207 317838788 602288548 178761369 535758220 182105007 676325692 909254163 944710801 911328154 944870943 123348810 720180547 127193760 793067469 374685619 525056558 929723351 529234701 387749480 424939421 416869989 926829792 293785698 783248536 325392420 791751946 717645204 480382458 724026295 588780931 100017801 16219608 100676029 16987058 264397366 80088481 268805632 88579198 521667587 325850680 522341372 349050152 505544535 945959126 506889294 949953876 927918604 83196803 928500640 87570674 865398398 522620569 866743399 524625403 458153258 265272303 463808549 268436931 907732437 258942258 911212765 305296089 610970352 69651062 611701419 100006163 1697154 993870162 23074049 994366433 907324578 734697230 924180278 767661593 387665530 851818416 387739953 856377669 81333843 205079478 215317593 282778132 546681500 217549924 580927668 218739611 334359269 498189000 341785025 498567260 475734 355713665 22318671 356496102 682173808 838338192 693320450 880805625 332439477 70923892 366962666 867303278 633057335 531495433 635542879 882551432 270791142 938923101 274975744 939010483 221742879 848558630 257393539 848633634 594263778 570730516 603032385 729874348 34940267 716659262 38220114 718594242 704119881 801793307 707497405 941570753 465238372 282749257 466904809 308683130