16495 689767
330839423 685408312 440026543 847240431 764203768 511723684 719577214 295259566 854878797 211225990 236961096 317571522 575473778 1232734 240167802 792846753 584340188 211202178 806306760 719938481 906779074 442338504 168675674 723628197 22342768 101157838 291895549 332217807 64838216 244442301 501493019 386215043 952965114 611076488 610961552 404867996 951127148 256593748 450566600 331309650 525786658 899187955 29660789 240082896 771377631 63102745 119864675 29917338 979598269 640513619 558967266 182170302 912214525 45459497 687836309 470530648 755790885 864719452 710234168 407368162 870989452 33162612 638514057 75508080 730881836 215636008 383131622 906367415 563951898 118339589 456624406 145557084 453448770 726248731 924745401 699539782 948092916 240227319 53220817 816060006 535825397 341641533 436191235 853497427 962225468 381676233 715157466 265440332 470635806 695029734 95088716 604133059 469403112 938773789 369783410 515256203 37409367 794197816 338746423 598858789 798695183 547209653 734087383 301718468 858905915 561548107 861820616 73876013 671605879 311088820 939075852 925189789 539316862 749600092 762882924 124877101 250262350 60929310 89078639 272425497 719902339 529199340 638946951 357899875 168679162 209507539 566255766 662137922 230999532 763992099 664345479 525657181 351781851 311869675 478263362 754042680 640123089 868321433 167709089 879002169 172076399 630067423 647514333 196166614 809521002 615471133 275161030 637539932 155273161 217509032 687815656 901138400 921208042 914731907 787767843 85741651 478091812 716920904 709559597 395056703 128645104 776860106 105339969 674428257 491114233 439559201 148324111 642749914 377886039 448687650 37319696 659685492 758273707 183402313 486126275 911445326 59093088 231581725 794611593 193664222 410412133 631870215 28480738 787676867 221019658 860022085 139883833 254920794 356256651 639635112 440960078 555328496 694568198 753259060 145143043 186908764 3199264 239349975 136855359 955071721 856118100 627856575 121343775 932438781 588502052 615833072 665545088 702397561 389718883 528093821 272458685 280232451 322067521 709080530 255911194 671126772 370724887 370423442 638944189 759515437 669581081 996564583 668384566 770461482 731479151 586075555 887758684 682327819 584172958 131746297 223166497 672523415 357825931 850863378 395682814 90378905 884998759 662206922 8278255 95536912 680016807 2240654 893587546 133149188 351709875 468114733 887237406 398996443 747919248 756689941 650942385 790614224 844055716 203523267 899489745 874234271 329709583 127737793 177996909 619443533 772783089 471693470 958877538 582010611 520538991 717644974 880143009 87492444 67905288 210179974 259367006 486315625 613476502 979469397 455389317 512307166 84885047 523264365 563092752 148700706 682392584 238178906 31095233 168917299 260706255 526372676 499874373 897289588 19779202 261875963 313752574 572752611 767862111 560136142 857995536 824114487 195200708 11332287 809452018 993539248 394342736 635812198 464541413 897033149 714798030 600046393 830508120 835550336 833652323 666904929 742986023 77724121 57298118 779898812 876004896 62995346 333304941 260569735 848479390 826596139 709870963 605820364 322858936 361999016 111834245 303530753 287703000 913679497 420105547 409461340 893245244 137444306 684425789 566292527 866998580 169879512 935589435 315964134 307730282 912553079 569565563 367679144 429131711 727323980 528180757 63497739 969921381 144421509 825321908 246532636 321580914 482897267 5792747 934086635 502840444 185499800 252068757 219346172 51072380 71015035 280466168 11396922 916082432 368446640 334400619 418926299 866755431 7827581 781442984 403079180 48504006 280627434 993933756 988444844 968117021 951614435 51078966 822402444 966943045 399830776 273659965 132406604 737360950 475842816 570300842 991742300 461493897 233141848 79024922 238145923 71908272 296334762 863019194 147835966 442751737 712423769 367948935 607930966 262570063 667269034 230004939 525261478 113732338 133537777 25521630 281139710 394792498 727672618 783557573 502706362 797906213 885051018 898518931 676202235 813258088 161600892 515635176 535028347 760929714 576512537 894099947 230571890 860205049 196373290 907679427 329819845 32595643 132248072 971973560 769333408 753916177 154874870 341035377 393307948 462684158 573980054 944238567 966700020 719569587 779862208 28049598 128968279 93005340 986463411 802164455 874816137 230185669 908777518 723566072 529527540 736139219 103465964 137285624 886211610 53598974 93807796 19049437 511143835 837528835 547221438 557961636 80441351 489520418 126199214 812260216 181409356 295366288 984298188 257283406 901976654 797442623 21160486 513554379 865390802 573196028 464422279 300864486 723584970 977184683 258924626 126647016 411393450 694686914 684464395 12312693 880965594 923563656 884971285 203132070 671550837 826419140 333301895 194772910 471431112 17687360 393484189 902905527 193317174 936823881 980959698 250971616 835199304 63801486 907139746 795385837 660797407 320264283 732713964 962578655 122416915 131547671 560235641 549213597 795613111 498231600 444513000 744033967 622733127 219684613 41688916 266367921 413648877 1379617 256220533 656804366 719732847 464072799 230508140 36558667 143950530 649945418 944684228 221384024 933391443 752110122 536750558 896713830 576947206 360802619 540503810 661995347 667517218 189460509 356043041 134192935 508510055 860373354 528446136 276255361 196997314 514566985 778334480 873146971 682916924 240321661 292461953 816684983 365807306 56561183 132473094 742879934 880832593 760869667 327045243 459023464 962979916 239881127 697703019 619251083 969396711 325480396 999999013 413171301 823441305 93495341 893506622 361121733 15625741 798656027 659658336 398210592 602066998 451619332 490497691 868583811 302065556 498423636 884319329 923873873 878984020 53174314 374868373 657318441 95485678 851749613 715096786 193256533 692407363 617984299 412574208 551402239 808178863 771305850 543787428 793962542 930882702 572507458 324817574 921021966 594382648 312077553 559870237 735944019 442159183 937668574 165522112 469925117 128883906 583543447 543472959 987699365 756418856 732313527 146060513 924288518 399375769 161869248 643148319 582934530 304188051 461122813 600320580 941587450 146840324 600376614 668384490 268532878 810245417 179815670 960213267 355950150 743588292 748347905 758292983 585933376 126888752 379793614 470725347 724648400 365359002 65643943 695586679 52541808 202667148 408342480 457008477 11245317 95896153 133771859 735876241 345745395 808342505 122841603 523109849 8240132 928111199 158802432 761171740 47889279 298672965 286069688 824867315 429427683 91934539 920664604 4266388 878059686 6959743 135545850 21155975 534158788 484545396 872555854 439761598 647230197 792931613 712151764 387304547 724428863 385573107 776873731 576437144 427609318 460256919 405936547 102046879 199583971 658934237 742248203 277353654 601178970 792619552 386471444 700769024 967367565 776027001 186865731 776861162 924978414 540377096 640358485 583591142 943524311 378245439 519326227 970223236 376645333 716151872 839575178 867995948 313826166 940754281 8708176 742607194 767679948 117522280 433058328 90347648 69409190 194214689 519075647 357854578 639742091 131069077 833239565 160482098 869928787 197902268 568475852 717648796 628495929 57208563 682975316 179403473 506630288 919459796 450934803 391014095 381442117 809071062 302118640 468503932 865631598 692145973 133399855 609201200 961054630 611690098 795991350 446699395 54645080 134189513 388420849 21647430 223722148 27423609 402264952 49055396 813212391 988268401 453549114 773196666 652151815 803215995 872126795 843291013 292815638 4605393 165781133 962215748 726844758 38250744 411111214 503244210 876972203 989797265 312048748 508195481 888447888 556865646 14449522 90253208 823572737 421784003 259889477 664659279 812853435 804210840 683792347 418216756 177495954 726625681 343818418 531574685 152744188 221426629 441157951 459301098 901419285 986795807 759913503 729940831 654944592 995514412 121307559 361183216 922526049 319039678 534486459 448649686 166484650 923400378 849302532 58478649 840820788 628158772 424370771 765984468 309738110 350207178 676771630 534797902 396830540 280811738 575262239 303207139 756382167 276659420 647993926 469652511 791789593 855748379 972448115 182813904 276860433 322917512 716664556 782387647 512505236 583032077 912080942 264119827 988508129 578451607 962611436 707678070 897568218 87693170 806613592 630365057 818488074 541246155 784088004 734995794 53953636 796537696 499514776 593624446 654567148 848414072 385871533 93303966 466292171 206084210 154224644 866858850 453421628 799957728 815618570 567364143 235055600 559885635 562387653 529361784 522149123 548832575 450563121 701585588 157763703 385979198 118296610 10084312 255752042 841233729 62276103 756870104 48520610 754975307 918688505 596720111 495466015 284009681 782196257 424482334 979921489 370964568 44049141 166234033 417070638 734519259 149033669 713261967 610586950 240737289 842205851 314954781 976392908 190296979 115487274 63905473 775132025 315379651 118554961 599365289 35954313 103716676 873421793 183408427 842433227 694626054 388388247 119545871 60597185 103465627 286880576 704533083 344919601 604240839 196089407 989060628 280930889 849344717 717803767 496849359 234601873 277856106 10356988 735982037 957216655 588372122 45992990 836688191 128732551 851305531 777515319 995691854 284698166 740810707 103177074 767889235 769353654 645435131 283960819 965265415 773522986 247919062 891564786 594720556 298520687 421902026 575490878 161659638 25497940 636733299 800130375 61809024 517789971 490110450 916320380 221016105 388225084 264650570 681163225 821541306 663378486 873851160 132530438 536283469 574866525 758216642 33280710 544355583 564295078 527719139 380171023 825634150 799468259 737168360 596943293 823340912 971853689 536164501 128209921 587602145 867255681 595579903 887270249 374593074 395448455 623811104 200163174 832941691 700709545 892353849 566988621 626609612 765073025 319805001 855928754 493135736 456626432 260773066 46103833 974634826 104050925 935459264 332736519 60535144 683248141 320219292 892333066 366505292 181099252 798689351 105534522 853242272 456137697 24764828 654027917 849715839 569536317 49328106 869809381 951534474 634835912 509858399 303109510 747018612 7477910 455404410 687541802 229893545 995472009 445989415 696064494 362166106 104586090 66907601 270020200 346794757 257454540 809097386 618260674 679224427 674907837 629826481 355607100 659680661 996987313 90116664 581483992 677645598 558329139 657891131 333469895 104681211 622754785 60691771 564975463 361564024 675231498 996713968 626674687 978449368 889382721 803097149 407014659 413699024 89252831 811508107 970035257 360360229 312610458 269703539 733138981 219704148 885376325 178554309 43052982 603573093 610860694 6227326 385999300 307232788 124648804 452426366 3075898 778131918 893624503 49291378 615404807 539075809 159509732 897085800 74829461 437101222 322862231 939364303 340155686 652870588 933979952 403822048 909950671 36188014 423023085 307636148 188456721 691676640 131979030 8277652 778294058 914950897 440367250 918341191 289446518 122164465 323815544 196035080 213152886 299568830 927933564 668268267 25591633 47559588 472491093 35690821 230680490 423478794 624509996 680826899 964295238 968900209 390268718 604152937 939879391 576730897 119330617 298514826 426277077 891916296 89609649 747706509 6034652 682049721 483909961 219098814 830634505 354486508 341531742 72565192 988444987 69816715 173925950 648167532 468219070 952898620 897333193 136754837 909584893 536141252 361237863 405606312 822571006 935906975 884971883 694960255 645435333 66940842 584387472 816011059 834024513 289874658 68785741 944602978 797887490 355334541 284372337 805648087 130361293 377831927 40477802 644836234 657687854 999959814 292494027 365984119 793873342 310747975 758852994 175059624 595434563 2673315 528641508 52505141 70673726 428521559 409722640 297819679 504327966 480768025 350422933 357978590 75515889 909332862 400621834 934020631 763503967 712593887 647800614 802373780 160519659 303542531 801921226 365080568 921754550 505945286 398021441 37139553 286016140 788613080 792197977 644133928 246419184 788142534 681214792 941582469 335310953 433019033 184787108 53267280 843333496 926683149 500650954 644333205 443520301 274983502 543536466 556704949 878691589 389401643 13028457 677831917 5738505 944917191 450239846 568797526 295485650 205578523 405782481 229693290 723577508 960786560 217257298 743663129 483755101 962108133 595636492 508310678 717685081 242074176 726708051 550175509 931519558 244709624 613598322 661925378 810150733 430115460 197530126 701765882 665181066 827638926 185489983 650423045 746431966 772408377 584062913 36129144 148440150 4219474 178288650 206667947 278397637 104099009 904625269 46861913 210770213 853390663 722186714 530631585 597434540 277287369 497552318 762645612 947594132 754833665 840249848 19517487 31618691 855980320 628639536 935911620 295735152 364264455 340748660 289328046 525327225 677341424 434505066 528361994 523031028 755741985 326627042 631567366 247728941 967764671 319347969 98508734 615890088 353818338 997838542 463784640 584366215 437248940 679046780 955650057 557992713 942366901 198804838 409396993 601427979 608590683 651137187 41639682 732789443 161414810 582881721 257561928 548313829 677531055 687476500 413214920 857801181 930426227 365832387 833269496 853931657 781816386 870996011 621856881 652635882 115191306 369715348 969799271 252766559 789969104 831819949 967743379 846430964 709351997 63509340 255214646 725996404 4849472 910444330 593464866 275128905 962809565 38568816 171664283 369715834 932741625 918395491 362019305 450651113 916127482 511561304 556408240 921449763 186338423 737048843 279985408 742098404 808503625 240433914 877332323 999340980 935686740 381762321 506979362 814974657 409663270 383343390 929609670 470763722 456626718 250425265 487984758 456353915 904443152 443020171 643907624 601827833 764701716 190779772 993217292 814919415 687540601 727014940 614810224 869107338 358851780 405338282 575388696 353987726 573324287 798246708 81640486 738168084 418689429 702208877 932433000 642202624 366724431 323500830 958986017 667133668 736014718 120709307 681988966 101421254 692526828 689043488 741215585 443042404 384634387 700976073 367476898 598090452 737550859 635927986 334664625 13899905 440685108 53923195 929226460 198340716 445952171 548340645 861830227 5139437 122779400 775182260 797885169 39815272 571058106 481814018 484246429 512193856 565907460 559790946 67937680 208310249 810255520 451797894 206963115 213715177 928087790 6260893 861725851 866129057 533002499 466022073 574576994 607486812 691446718 470467835 859608644 818518226 708393385 982039813 470143142 977990768 112597050 962437494 163769697 604236072 595826216 281944931 23390919 137007602 259920537 878191120 665926033 379513101 801343896 661735639 408417785 728731489 146447338 38148163 511915874 916798256 609229317 602940035 115606424 989126301 898697634 867482828 746399168 626742700 825493155 615535208 586159005 593079576 307315240 370862806 199881041 187099142 235143966 877968569 191700640 136324730 836160492 307290033 751613878 860389616 871549366 93183679 146921187 28828583 105875787 87600777 598164758 120985606 278410831 620381366 954470692 194894970 420728549 533006099 506025829 629364277 780223311 713219613 525064577 892436274 828869919 261579363 321353433 816108474 699640759 98563406 638554550 405574132 218585706 502147901 255312737 203095038 228662237 813235893 489092666 779166653 765233931 372033898 115774669 793382750 155343026 744273697 624176771 702417451 6354166 753451293 192184744 943306385 801091874 748296063 774311222 445567966 613893709 200706755 538929598 840064956 858952933 979008996 799441012 494329461 179251987 167728484 361517228 859369322 296903999 554405471 868663738 929218207 237027575 355330671 642547344 257907206 958776731 19614811 285046852 317293887 862450874 694023968 279999787 294148552 865601027 667406476 311614546 577356973 155989129 81150991 87594818 99186826 578791676 150369704 591057623 671886413 155887819 123915069 899234150 661487196 102841741 377646934 553778305 823077811 326469771 424207321 538378148 82336439 98106299 126071599 951749704 500153990 513387377 94518884 139761027 107604525 292271406 200249039 84842362 215393587 579980734 173259575 293138617 166604752 455998002 552895374 392380145 581057525 146776545 675488613 795269559 889799885 578014854 953980652 158455975 905480828 431963607 753916017 370624875 984770533 959466071 244671632 109380780 804778018 771864631 93938828 272532794 485452555 340547273 827121870 575706438 96567715 761041368 817594377 58830017 806509820 940375316 515833205 145532690 419292252 82813617 856800742 205613473 723600312 837382586 844590435 1524004 839638206 54514105 352788650 150662133 137971198 903497699 966387449 333233409 495842656 75233498 650391677 217803338 642863364 218142617 672386312 102989838 452995149 467136594 740395372 404423920 590327006 818672618 222412933 251510385 281425562 169229967 141437012 957933169 245737812 866489776 786758597 626843026 57912452 212689854 549440477 121864683 893677289 120817893 87390826 12400490 518927724 157013226 369697152 635957558 865280458 622243928 933358408 647464259 636424226 692802674 168909982 699446749 38008110 970292746 561747077 32251866 634067721 243030783 418668505 242409665 715182381 66908454 435889089 246946349 167323227 502150478 810777626 251486808 9198860 476327526 876026052 460138983 750296393 982662615 26342927 410622268 711660416 663954453 166065993 116326828 819681922 522696311 900101040 35531000 273822959 697430837 890883567 718579293 405868685 113182208 266250547 387512542 752237797 929401827 262356265 619584639 525348052 192695246 755898977 105890813 914281280 57249940 563060718 369385837 24113216 201251369 818241862 265453002 300479458 55790812 68464390 397590099 409825750 500081486 805486220 606941339 646413193 995822427 960328401 830657231 536134725 563529128 601819115 207285274 551902476 274366672 747195037 203098238 479388329 232488673 212029761 875202013 886187458 351723128 300087470 34070059 246063900 889359151 537943807 567017252 221561487 13776878 591696893 309411583 195204442 732956163 475934394 623195117 754605795 36096676 200091168 713564696 600804453 173983049 941651954 386299856 438251583 93493526 400220895 951238490 586799248 672900345 205754369 771510866 248802368 242244997 445132864 688179506 703710202 721497006 176886579 48910052 378279224 530319972 796942877 370271834 84162364 941276261 996590434 207308 8594285 102653722 539999028 115377880 465471735 970176453 797557108 352496571 385848985 830076013 407652853 100236542 353727737 880358623 352869253 536700098 133510267 946893855 436472429 85428430 233792900 985793468 822618153 998782996 706182922 46370490 496010765 13496602 691942820 228525518 773717769 777654911 903953344 393611788 271259854 475009105 540045477 564326302 899456644 491973343 37147690 780259349 118668074 705261693 106914080 443707841 371785249 585614400 856779242 695945333 112581618 294874768 503530279 378286217 887559715 644932944 304783641 988669977 534261624 112385393 70480615 378995300 411792162 699025972 348123358 610083941 805380563 543830016 122047635 850354826 192630067 839781198 440634573 795931 138643821 676820083 510640462 713503147 172702098 898122139 639027196 67631104 822896266 250385864 537136043 521316692 180677359 228857061 852129913 769230334 97423183 192726300 140010861 842206061 245495734 500628460 476060884 903732159 945316553 750847384 417968541 397401380 776573955 834421135 123709620 224506819 43045128 931240927 264071945 613272852 165573369 579588003 541356468 758772702 4543731 852651927 889148240 712661027 526957461 118721184 290392598 797385776 636680169 117933814 438640711 585362497 578812605 985640082 774654626 712587415 116543315 670101968 713454941 165070061 23678704 889813119 295654618 424629230 666579579 5689963 337931723 868616077 468057493 665439603 534185278 468358409 337860952 512360922 370159932 853345059 681534344 993287947 16235946 896646578 556588045 3257759 84718455 217925463 81056629 121933253 200337448 563337210 552473212 134116678 151120955 534569539 247626622 46379266 108984612 149683484 340543594 97811239 823275229 847355921 946395776 482829756 496677622 728787419 174800078 831950507 761053648 937875366 639946965 289012612 179613345 756912411 366957049 597969082 508420944 532756899 231529134 467357290 328304100 66349705 992216532 441927919 208751165 49057682 345596943 929106421 336195921 329542187 539826721 391222988 364197668 576503183 998403142 264826035 170725386 424313977 695903140 326152525 285960100 77706449 577703213 26294924 808296100 985365556 271123299 243998365 233809495 655818484 557549721 628771450 420140946 131175647 930046051 827687946 494562981 623192691 838803063 404723707 171653904 190414173 902071087 946248541 2464612 893592159 761502836 673084127 304674779 669091454 244868213 930208900 280316138 918902719 844696534 187875851 393167723 299359002 302980794 423392436 273932822 68440700 984987961 416873383 721146958 220671386 397213280 563003676 620522268 906430221 349022130 664381605 68349 653059509 652513150 901577945 570575498 853022610 617092368 312123967 226340275 21345266 739989086 294301702 926019832 516636269 807609841 388645914 884300458 739679086 685823390 548423244 481911150 583543837 746927261 677602819 376368222 335439574 468968554 247419360 447892722 257151029 819387095 505500992 587072051 336606473 230531818 173598169 935957614 933658278 403750038 651381958 891090859 805799524 190261357 222063992 554598906 738788275 170864532 189855162 756511558 520878623 221354621 18004799 712995950 783933966 627812084 775051396 756030992 495271567 810043202 516880542 927220407 760339188 790975910 954326891 699322039 482284198 467909947 851758846 91533931 612197883 896030413 353924977 70602749 581946084 219508455 477060677 260042436 993246951 275122830 744482203 502904127 747707506 201040389 651160761 266021842 4943464 989894294 674783820 38768341 811397359 76513029 352587288 988354625 272515723 305330373 839343572 789783376 14429756 696572989 603486036 436833715 350881235 456892194 967008950 351606192 488199918 207939222 476898626 609283124 645403736 241779051 502314321 601694903 38439536 30886562 642889583 769891416 107827831 160199406 176742766 334637281 819268784 490534815 526979987 775586083 328349488 356044101 589457853 910460988 875613338 515153157 908424102 72410954 91078952 884948660 101730353 590935144 760281389 995663272 955027528 779987353 381441920 845655132 956765834 955328005 628887099 103505710 142544892 592480737 818396339 588761078 961536206 897386943 208903275 657663577 653639965 164247005 599779730 504141299 619740241 291850216 244226160 479498765 403808533 843638291 65237654 449970245 71242368 812544417 7732978 638115213 926876454 259249442 511648001 927571209 733988914 549114282 653117470 222504133 428532602 762300679 273813070 912634107 217595704 558595922 684761339 426548019 233890023 918531798 646998460 975745309 867205417 591920280 166273481 211874085 286946630 915277299 650585591 843448890 719200556 443166953 335195647 845523320 357368719 278742803 798363339 313068963 831587899 629499214 836347428 131695415 7702431 504224666 527395209 217623039 964138360 891122234 78309656 641372548 293447905 797076465 956707168 915714353 974445416 598861391 127799690 325494212 413170971 922354131 739492597 858426134 81066071 159849953 173749218 61300578 893108390 765812973 588328316 127621437 593553274 540392559 125938104 583571405 200060826 185532583 892989899 568327002 862256791 391546665 723566472 221604730 9838423 803132310 755648893 333848203 500403935 768121214 490227749 698519520 616602692 241558471 526983057 473769288 712396146 585052874 191085926 927698541 52423050 859254207 571531224 906065044 233141859 564798940 165114092 223412211 331308221 863231206 421701232 899429562 788581208 3560682 705667886 777731695 695069742 474625690 123243643 756906392 539031146 374137991 5213857 898846558 115032957 372240265 658091390 414246113 931186432 910987083 446969687 746060884 495532436 683752863 857381512 860621649 979128935 139551760 79103382 201279494 820139211 362842562 404469830 171667035 40747838 781746032 224605308 382982067 681631126 171295030 335859090 711338843 944147974 568368915 598061969 883445568 705066363 891137343 362359061 840708642 432108233 64743868 374805803 367827954 107029068 355097827 930423306 466965670 150340588 535959475 618506889 367743240 202920476 46181422 73212649 24125860 131746341 962225544 486125452 462348967 258297363 84285600 903314758 104340671 201931586 48578708 16110686 707080076 373889702 628561323 353160974 327246695 502418228 151569036 34316857 358314573 596918091 289689854 547386979 531240170 747572726 546253688 787242785 348837300 546985883 364777177 130064813 762288692 41323154 32419126 514121013 669075316 866572237 402737774 608738245 862555881 219002814 509737923 966797781 29755587 446106514 269927864 134505318 597236573 16710955 753188756 702143860 999472687 305577567 453569382 682438810 666901714 446928891 449206148 608734327 626308578 156462937 832927652 95230550 105556270 736543559 231762506 857051905 27429193 707841104 219110894 511194424 770579799 480767704 683287006 180368598 995260490 911874276 978145621 559401395 228249166 55018444 360034390 423432680 991395208 330006835 945919928 90782892 22763092 161941082 6506872 302864711 919275186 218750606 144422557 217913355 537836535 530599822 360058376 657358149 243787508 417074255 820203492 57216470 392478362 379619760 412504111 805514886 668028687 881542069 905606837 678843791 993476923 305567734 624667672 783575367 319282598 465189148 662124727 158470751 610495537 813527413 437830191 927202808 573196581 911849091 682486062 105323388 7042330 625760957 959894270 989636867 76982915 309953259 444130614 183585964 886747222 958049845 360176831 762634320 868290228 905167130 886325011 607244199 109673458 176635819 738773919 607195246 101181389 519479434 288694856 337076158 865658647 490278842 244603978 18607900 588697027 527139341 785236368 139925337 326260616 92138232 563414070 300578389 472028706 167643614 699336958 402166096 514174739 777018587 479707249 530935725 495253160 378890100 365583764 342179417 675783937 45954290 150382862 402767766 646859897 28276728 861623187 967866534 912769119 298288142 916139011 119908775 84320659 918345060 392870705 561471345 306941970 33369041 431245581 604045438 480102701 420068983 565003441 960529035 879511260 467937100 797481981 187573853 428644796 438964903 59576059 865257519 154352111 103175462 728815162 795115633 35196847 667068514 763438770 503066897 473613345 632072196 782746749 270468692 314586609 571654904 728532184 596780770 396244306 767395163 349817296 441040598 54106116 27655213 538354599 890521562 492045767 791853183 213827566 221892158 94839128 413800073 948083606 102080113 944682571 617974470 19129516 984265349 447767347 947666831 298638533 841004155 679719773 125370578 467242861 712576935 792249329 317710400 442336616 948534335 825169018 924541938 118430395 276472616 845437559 874471438 733071110 409290680 927257082 642381979 194417040 83221212 942222449 775908974 559401743 121579699 676942511 476591734 319180374 449430871 852329502 644066994 521382870 27867148 851018659 383396051 964984871 962558002 263535838 398283006 81257539 383769598 201589824 490430660 771682600 430847000 471108523 753175612 58367161 48566586 118687752 952252138 996353368 444331718 76480810 421760472 576350087 292376661 587678589 352931825 395309466 51766285 659672901 753269129 3050378 826677890 292132530 340874819 965845791 248258931 906449053 286117587 381956362 142545492 627707712 796037903 220994237 123905357 593686538 281809594 380666667 146650612 739175612 925091555 402752126 989339084 892267528 389960844 492712005 930865104 779515426 21173142 784118069 531729453 257976611 442664073 268292713 820757622 827265172 686764130 450810132 674977111 338224212 698791855 664510943 997561208 834918478 37324323 609921795 340106776 246636011 587112078 557629049 194541517 495253421 992373617 637319325 881912109 405938461 982498220 411898999 712714866 63926326 817290052 264870589 586576756 717149042 670083910 82772185 141159839 655970034 694160577 512210820 659714825 765615295 579044706 640549225 128026921 716577952 47992225 850586075 150899431 888818051 801003866 354738966 475250423 292632746 984625070 923596523 985455916 888658658 120894544 175776053 664269047 311732633 806378748 263567730 106998404 205603868 841025364 710012028 802539801 676002077 109673762 402970700 14558613 603777994 886798454 298500489 126390700 979029907 515945791 94945715 111223395 194834682 530412470 696947418 488070134 825238946 678485412 69451264 923773752 874478207 25834285 501202036 78245402 573665293 234329697 396120431 566988624 560003562 957396892 805225774 477470091 117261260 813862960 891675431 110336792 484545022 389242612 292413356 51085570 798852959 354801926 132948682 873900079 111017576 62084609 853811628 681582137 366821648 436880994 502799572 431213063 650149229 481366501 735025629 295222286 766737916 832026268 420574379 280880547 5172257 92831634 975667186 20701649 296808745 692799944 511606176 827099243 473764285 203236028 925070538 218922455 695285312 451922363 331799423 596995364 379938571 852620297 739389867 123595948 837247490 183441962 284264874 87145141 632160076 936988792 834179833 217967049 711237462 729084225 92580118 171487364 276669174 957143448 502282200 965673829 60774119 569042258 908775608 792861283 509997190 705743794 763920095 996713725 791975282 204472418 664240733 917897157 281133705 523029521 489179161 110242414 266449014 153679426 978309098 208979422 387282791 748521713 760933472 3873495 889059636 908647662 899451557 290392769 401445290 244353572 332038591 788463585 441252655 612974013 353439748 338998993 1438884 830919855 722876290 608776884 73156127 989268212 291454966 474397733 701812360 162292566 722971335 198420148 556277359 284999414 426598441 476038080 345293417 275480695 597873638 272769918 279145809 49175316 260280753 365270989 625882100 24759276 793856155 678841716 374915150 431365927 554488820 551898593 850955362 993941259 93402297 813760365 347465892 274010880 481126086 682201805 694947468 355919745 205316488 837392256 992278077 691806381 144946240 943945253 214312269 106970660 922810634 542060648 778577257 530437374 59453007 271100488 315624313 63491421 842791792 192093217 568121325 548706698 58941705 215916772 527699453 870992048 94223894 236108097 847640062 425446009 373967797 144591816 759296587 773037325 168424890 869346447 467662317 841410150 433340741 103552874 62660551 832257768 615272429 771159636 505781071 609904184 736493070 978094971 920164601 312132487 486286096 425451847 251644002 770621436 606729596 270970010 511807778 343014195 373088901 939749068 269698961 583718901 528740431 252905949 602845443 754532591 144751539 623581215 907631245 749604446 530116249 645639791 235155615 923530499 655146881 853338207 700250241 280408471 381415626 827975361 829531147 801129768 89010505 953907739 802889335 809783951 992207142 9568308 546125340 737855016 719382748 371857560 396547518 7219279 294883636 15747767 445098779 135556966 61895784 771856401 586752574 241650451 738195737 821623598 617854364 570198736 651140100 249696377 223647113 135477399 768255783 943526279 502840616 530442424 24995130 926846633 546377901 415582778 981850984 831110322 975337416 179455564 472050787 22859360 899132143 210896083 189782629 919588941 433134512 693123576 123387369 323501697 452017764 440168545 148483613 679567123 970176039 397237687 885818922 840645607 636815145 535759149 756162735 75004461 910196972 712592158 244676323 21974210 252089570 613507309 204875287 597304289 846225437 199034351 946483291 30488233 234866120 193532626 179875897 455032261 302564707 678557264 722027375 24291816 356313234 344867446 445217947 757103081 746330452 692527077 628858309 502151286 234804858 213318033 559766191 244919403 517377347 524097308 691722623 653989995 605922658 466973064 205775815 560355332 133975780 408887274 884478678 318900307 797235850 337986850 954373112 171065213 538420822 315622016 140505400 337832393 669627827 225278963 590667717 485596849 855956953 441571433 482662002 260848466 507983176 902373798 271922341 64993446 653004399 950654165 178480716 449916447 381236882 338646688 66625416 41988241 40313245 290379772 293506356 468422685 109013542 782306572 531011077 687528535 139388326 602414224 737256439 235210773 550986953 346377249 458781877 318277510 552894461 194061544 615582727 923350248 37980587 959600896 11482131 956001670 540308855 857702871 236591114 861813863 836223604 265706639 997119764 421418904 787316183 814906305 704179224 657246393 251290977 661908780 731041079 904218945 696733091 440606553 368294971 259683470 188293487 578025789 971437800 44263350 69171657 435192785 648113510 765996397 635315110 251202851 562864935 494379232 468746279 90235266 981146675 281725929 256288242 790569479 963125025 813906181 120222791 672702587 353906635 731579394 746736810 455010040 383221961 586211408 330084818 455098212 930574825 738664614 892458310 538120117 207451500 728670899 770982404 25522130 108761708 730323091 885660854 771327681 500172299 757469421 303000002 945490603 980247304 801476847 642861536 841306128 113051969 907699379 200244378 28834636 319080770 453475268 105365995 349290699 178317553 687031151 869019922 809989185 650520786 760518222 593754893 35242613 505480026 742632261 344215415 847385447 729316205 193184834 81937522 748769232 653579777 153623700 548664665 323203126 269026121 573188844 917967288 607180152 443375051 940261759 274283277 33074791 548344466 425514992 773707854 584294560 425138462 317335087 635773138 137432035 484584150 194674684 484360995 810522115 776711576 704132381 926422832 14090616 697287081 519099402 920327882 760957224 648970307 764438286 342974996 445159612 461286476 257603965 395236632 747929069 60152749 611052292 739649582 377637769 656724824 475417211 471986973 883260635 514984134 29733252 873747258 81998019 662780320 782445764 889339543 356559946 891449230 426939996 735454162 83434687 922337169 281954499 114695428 918727104 486449212 669055957 525451349 40381904 433170150 557284357 313349546 425833277 341220818 214080857 386593276 450918362 199197181 602190566 947805664 196516343 451771126 81801980 514995451 955819282 499762033 901726464 385193713 31853431 740261729 638413104 820422942 304162711 522999505 152832994 716638616 593434843 914130270 102210662 114502151 17206672 58122615 537328955 402238241 944130971 691183466 651475917 455483733 107936120 383501743 519044827 407653134 886010271 460815302 458727872 440169650 10801474 837856615 450220534 975390664 719159320 988184826 45222456 981918470 824866287 478684714 534334798 785645571 192180567 240287046 113640207 842028952 371095154 221067041 26008525 547845927 916802989 496182850 999917566 126400040 924274660 38412681 165141760 265438550 730226406 977756829 148062518 709054784 275399245 371798916 924653270 993503195 955327387 200537759 429556058 858957309 652104261 549295667 174710616 782218980 451510740 397818167 174870757 777309228 969655121 500302026 139137160 964576750 225264933 3032209 635882580 954638478 235366295 276532686 275697126 297010292 643796724 177521005 649349728 231695593 53206463 215533278 135641384 30863543 540447314 835244752 811166217 332784408 692993783 481545876 999359125 830493104 469984250 835381975 807717615 657868312 782413919 285921576 449472604 16547135 225220413 999148706 645232684 813109980 453127594 25855875 411017277 456293648 264777677 115308847 67153008 362568495 539626919 472688855 128301862 570562091 608901391 46860460 462660854 121387006 773189732 606793017 898837599 951391275 187034650 524264562 417783858 840917266 30419586 152652131 118270433 510821245 267313293 171950493 279666556 741234528 87561747 144867320 761344314 249009506 552435307 810175485 965732269 201675543 241495168 113113468 584378891 134642147 557405165 521158166 103873679 754265388 69115284 677491778 518958457 810104918 438002137 646934664 311811234 855673798 256442439 778055352 753869539 291150936 277195828 910753851 975405709 160858067 787050962 198222546 816068224 503763753 504598661 891306654 449949161 644175475 927991790 209580880 26211808 249200627 741142313 878718109 6270643 861342700 145964823 905085113 469088863 759009524 618032049 136484570 901376461 314592498 75530440 206957144 41939227 743851447 190651141 381451865 736488337 919465789 358626362 344064457 824969371 145898578 632903269 588683568 590975640 200755259 784265740 754965184 908705215 372984422 602760627 650495158 601044536 997010049 896482596 222326690 60740125 854383555 274717679 207874176 882506078 22316712 495198499 179863403 454973574 871646318 546127003 538821164 235032805 643809627 450329675 323274975 585972048 753940701 917778052 127379574 110818465 581674458 913357794 361036127 887386289 501426337 662665740 714727837 824106576 279125615 784955388 382511322 720117229 818168838 878342694 685680 755676257 831941827 871878845 591951773 105274376 124336651 209876283 111006802 566079411 177835041 295027016 738740764 82382557 979429521 278341137 844093690 952769731 324588396 542755806 66090402 249679615 943967056 421681331 635861995 168021943 802625049 132423651 627058428 628226746 136230093 826579866 296600270 328505464 26335365 844690327 855690809 961492043 736950601 258862480 435410676 938729823 178223041 750827206 938844255 669509098 511049254 619530488 213174674 282743268 551507036 589574576 866101994 929993317 18915843 354512472 981987802 736003395 586441281 697584389 995052027 202197186 982901536 956465337 274865239 832567645 852248625 86965798 247056918 966446435 44001706 57881253 553222988 370332627 295979826 942561503 40806290 310417419 771541507 871866080 767859801 720030136 707195722 95332960 662177927 839000390 677554454 449634858 471769840 206883268 791524747 678889724 271742161 976774058 634599627 495742967 297290574 848419682 204097835 68287413 886351114 202917058 404744779 916069009 892764974 79660565 103816354 721172942 485343046 853298108 705244970 206628358 27539486 910017714 503669943 970917882 556521253 110046719 770851160 359422302 668894535 908678652 101647910 168303865 910348278 241134181 506613190 687609242 890730648 368806043 985397309 981323556 3237213 506100815 191304413 788731140 358565857 539071055 345119212 472143551 686355824 839258518 438969160 765466790 122874946 22011594 245557259 11226411 356279718 696926089 599331281 926428140 539636260 302787615 315322859 871106167 664038456 236589170 456456452 358629415 652561149 482548206 580814300 36929082 491550253 522154513 537961686 33059807 762577275 13109360 510714438 323209295 646890719 173566005 60487292 215437501 926646463 309496404 471479187 390047435 186927117 812456880 5518344 208562215 723660293 428692655 790542854 701839188 964703368 907098803 72285405 767775825 271258689 884299312 895300564 530264250 854152066 235584147 336802428 764835464 902905293 292528115 765950327 448058884 732769993 434185862 73581101 231376996 433915883 270833162 370689327 820926413 60700133 129242748 304877947 292143429 129481177 283089637 926730427 144089512 384220759 220725852 112745358 846766267 80138712 786525993 207977748 80863220 322810977 668200961 157707393 111756184 766261378 612595578 927895093 682065005 240872619 913757201 222033020 896695482 779191651 534416010 874537613 295123984 357272360 410323816 513877421 504343166 496223854 980865444 988362654 643645867 187458057 189549820 111094807 368537581 213271677 419393688 794708393 613680743 57206528 808400494 869704557 538013778 911977913 455987781 888315404 491181306 665797043 493682367 298931458 490262517 974144017 901684314 821603864 854694875 375397900 350574355 356372327 215897539 913847512 858156738 470938901 824272527 564132853 523740837 385557509 741261048 247022948 270982984 542637665 679482183 972421979 902295887 301669453 527204015 308391544 80190147 260043185 169275894 826183900 836782025 809002177 799283078 706522642 145421528 50548365 73317067 286287623 765349427 298858706 280872168 556828484 440072065 220123363 59686332 101178835 62296397 966307974 880143600 336734168 905236625 256895805 862143135 876846320 895434786 190218576 716846198 101584676 687823590 37011269 153122227 145738207 637002400 809786878 729399614 943698147 982229142 223187714 698884914 429168215 856039446 414798526 726980023 199342939 436545707 875441547 244088584 146154044 323536657 874907721 659045376 587682023 544343885 323797072 468323370 883763556 610444424 886781070 145180404 166628681 521877548 837391967 276694334 891970880 200651157 295280071 436622720 617456734 269315220 986167140 691907471 58003915 247296641 81556683 499588072 585264739 59459789 603509431 536242108 569058590 289478003 785340291 932493318 787264958 709480140 629629028 556487001 253463550 849342051 157536328 401738478 79923212 65199092 356610580 577720928 659621710 558614426 10394674 299537902 652532384 432619704 885878520 943077118 283942982 53658542 379980693 791995119 853214806 307880543 775224604 914138900 497853934 858413664 46752330 546679256 730593645 140825957 775486878 994842726 739568566 621645120 529010489 130284090 279073709 651585025 41648354 265651805 342426261 379345237 918265975 517046644 476737849 932129863 683279890 367613202 291329683 628378303 197851912 679478519 921820123 668488502 795632792 770916876 828324467 2647395 319546685 652820187 751118080 959345488 240630434 599800990 242198520 180988834 380866302 299091169 970260123 69264763 272893912 280664022 498894339 69220675 35952289 128350976 11587439 270388791 485479923 697462231 554859372 940732005 732352683 763775483 364996152 504724216 79006904 124158358 132373000 855862295 109194651 654894527 54666517 505092354 723480193 374173289 269956361 857223439 565794577 562874211 297290200 474893095 993832918 489267252 727815359 801596729 993690030 939054080 122981208 206153269 941628505 891376886 318923983 100362133 224211107 405232691 977728097 608374955 655718958 705859045 928124215 852625486 929116596 562413046 314713619 266004376 135541555 527352093 591926532 675372461 431605535 628995239 109460026 296052360 950725678 947255215 164630720 306522010 851892864 655982287 66288812 793232066 994023116 169125878 916305427 784946280 329709143 704073672 614078815 682926304 92273546 157818440 242484212 971698740 563915868 801983852 865774060 701403152 587043539 535431893 776351278 373898658 980480905 117246124 554434259 943861992 618933797 324400669 980716609 982685040 395436376 333677855 633634219 163340545 272248496 595643591 421239700 410148170 82708493 723183395 705608523 854191795 267202091 793751021 496931215 501710697 171246756 870850352 315711228 875510080 592258080 675282362 390740783 575612468 871284954 749439517 929538758 258258495 481190577 718291791 110682017 433020818 379443244 430029909 942483010 370405517 510455049 325871625 919095718 690449407 326792637 607219112 634775116 555321929 286334453 303967403 948003624 289174545 665345693 758293694 914847925 811670093 152765343 826387480 408932829 226122179 926892415 623434983 450030920 494278344 27840562 882458491 456369273 713136381 232113134 967933496 601466404 471800987 31248529 85073320 251382678 672129202 446666999 528097308 643858896 259992590 215897617 446834986 328225587 440373121 565215107 845371447 834709767 438437812 366828449 842069906 233169958 555362965 166896006 421229068 803695535 932081391 480634548 974019872 414093210 779568504 309283894 653627451 724169016 453319719 807792251 644450705 575265950 84142148 237366060 506476786 686407975 834235693 349088495 263183407 437669725 124832878 862078991 260453539 897148990 781216720 836583860 654575500 715175027 638480047 38529058 328819592 113917943 911771568 723528062 534601680 641051167 280618838 71688684 787940067 956608180 120147404 916213211 191755832 863036625 480078709 830619432 725808318 849390070 948054440 798465759 398740366 678970406 267804385 182815803 624171874 634265853 882217881 652662023 409366793 836400649 106897309 70462535 321914801 707745233 815594188 196561868 22502925 240707948 870285190 549898520 312217747 437813132 279076290 423516951 842501687 647617740 138994245 351746112 681649732 397936464 11726872 520775133 589616308 950887665 231034915 489834932 610995048 806739263 880194424 455288093 74724847 337898019 259075904 373331522 782346082 994423467 309545697 156884109 458891994 357563355 449874357 112121166 687410851 542483177 409194013 268916050 79008743 204223921 793335257 359330675 858760506 525635235 615842040 985131960 839715149 929806858 185318229 840560359 712767339 41434392 232924982 614880896 18055020 385296073 866177545 217467610 449382950 263089848 181232950 752311971 148021177 186544245 620282266 876586517 106025396 990878613 504693348 75184786 539398864 545583280 457474425 157016564 361335861 95082573 720411366 723023576 542766251 983530440 491656365 158187121 112689950 123376300 374562931 506968065 47082639 57113822 427315021 936013872 619818533 502000093 83725916 151367175 327642139 167615069 192158064 371198444 846634219 307637096 813379463 433272315 294020084 219070878 654726933 929346224 401445362 341088174 267405181 297820188 955795171 387209284 846647993 675832125 791542204 580094568 90290626 812474316 198039951 434778027 620591974 26901488 750782263 600982823 827556523 731024670 234164087 220103943 790680253 97257158 969295804 910057321 997611244 184078903 485949690 711500843 818900095 7911402 520608525 750287849 311738765 437463544 646375100 734572614 775447231 492117395 927183535 659185604 354745123 617547366 941685366 46562611 833535523 525986081 204848025 500622367 935498975 813365470 572072772 352471881 876393775 376282521 311210329 906506196 160653076 97543053 875797812 151059273 671395246 56560906 599430498 551062973 739727037 317598257 684436291 319909677 644089065 51545556 348740060 719963785 136353232 63057829 963163916 789702661 360087350 313524693 339999695 490254272 390473376 977860797 815578395 913340861 802582487 852256839 753150496 842326032 703397948 564737016 443136004 549793535 376930273 743185166 86202993 553802816 132315785 987378264 932393 40962863 360306679 487374858 808407711 452099147 367148356 493495090 725635100 263089174 41234187 191047424 456745181 693034537 798373209 340447776 552931483 820327230 790099187 19029359 428798054 785966851 901081588 819238669 503395533 967892445 458998976 137095140 970602635 635248752 315339791 179610171 731618165 951434915 523751129 604536911 682007091 54024712 325044937 663935890 930665355 620815690 789285828 833210079 438480923 158053702 761640804 602820801 190946971 722263698 4828936 824834738 766653274 29481215 354160842 192030430 782040872 570037527 365906854 498154388 786858588 645623335 120762425 554177069 961658013 479298684 563966144 183514884 359310029 249548810 933443648 342738647 111649135 590809057 523200367 535514341 400912331 805643841 850374297 413984365 561150721 346811392 35931504 963644151 924368958 245446986 421621580 285707570 662973611 486189653 990641786 910976124 431894966 319151981 103090641 79259883 279610241 874034486 729846077 616947467 964601924 367537073 796939534 183540301 87139885 95459498 665784936 860951379 637669540 570507725 150127364 896209823 336684156 544063224 254317571 86123728 132541416 27528308 748501789 192937645 440762054 465949955 267648204 465297639 318098296 749758513 850483736 371487134 430042223 154317846 3285025 665897009 215332151 239113889 796473971 380290865 821088382 72360876 209467672 627606485 681704722 130999862 275463061 670711432 244867341 737153087 985454777 950688781 124158870 51732872 662838682 479602288 772050557 671368278 897298116 987800311 702259456 142209710 971371127 891869091 447352325 580765398 294398987 335610879 912501351 472150668 1715973 499402090 403396080 922908871 184167835 555518433 26439170 872780956 485724977 204286131 756434275 405080603 276616858 874035847 90290793 208415607 337066797 39102728 84767817 828251186 537342598 472539774 173967433 201648882 356194241 998924367 12843322 580042047 812543452 333520335 79372435 209384770 113654485 101874653 348332419 202102744 720340369 292157835 55902105 709684841 853643973 106470218 627106055 916249197 266290038 115429384 440071671 990755608 148300224 50522450 244889343 946868126 163977841 994754980 732122498 812136392 968749048 547547745 679447362 485280997 751156323 390269465 30484458 244591830 278390321 984832208 682313258 376872935 680343865 263998502 866799645 252809366 872723797 398424367 638908078 988881942 36413575 973466916 942453922 519092068 281415335 332675026 173956241 241627847 512237133 229311473 197897830 843000452 645162328 787589270 777974650 881756913 937275297 545890145 730855880 33189500 909604933 418987177 57687129 985101647 125626744 523925183 642302708 812961769 213870281 532772139 77598411 935779054 342921423 31727509 153260423 135562238 432135941 857838765 543906282 823114406 357210831 932465032 443414991 519912287 372375963 179127970 590346609 694596152 808620330 285918703 693656164 684505525 630462698 259131054 675971750 663511476 32202631 399041601 459026436 690861859 259020124 458946839 915541000 491791330 432960103 644703612 597034748 892824799 619142257 257040396 271472083 495453341 574281218 910394913 710987531 555892434 928646069 345107451 566470851 141535912 585534275 790236728 792082582 723127617 466625660 713142420 193373925 591783594 833973418 961157092 97503402 238663665 610069121 573804082 146135144 416760764 81342437 388553550 560438663 824163308 397234289 433864358 627771426 508329017 51796035 396915073 610217601 815203067 756456911 996913022 273650828 541854854 869994365 621790843 920967212 695285301 64761228 222105816 580223040 759577679 719599444 303771443 868958511 555284917 141227231 267569505 216126704 458272330 304502499 842380915 154556199 482571147 640868503 417325737 419335274 790340380 827722927 493594759 738419237 503603552 405225272 321983346 156011976 995315986 593650198 474042532 750467467 500480275 781093129 966272196 805648104 777626037 617508328 798061182 259111984 332279002 25522362 766962025 4453345 99326463 750175782 123122429 213333376 711150731 202102290 956469487 410698488 262198780 513465720 280860493 806228358 731345294 397555996 55951758 584103401 734601862 55466277 357516816 411828595 35551911 936156336 990002839 705911626 198083191 675282292 174355509 852415196 288936833 240729150 447315337 850793003 697355440 546807332 446215282 426307836 847703373 626459295 688811052 306350460 806422610 817438669 702009833 247823932 444684221 229251246 414402655 978533172 533918425 555842170 315404561 326539987 573766383 535049565 12452452 287782682 127533593 290011964 712988386 938012897 277021092 603625204 628684058 672206473 704155728 683968643 117667683 164222863 526637725 83461902 963014290 323573759 721657023 249333141 421110233 904950153 370983026 25734451 632793433 346953370 301428923 684786119 74635749 43662800 436329927 705880525 643790555 493852245 172408031 713282340 748269160 115591140 268509318 623499199 958119068 842009244 857005895 269227138 109301865 779419717 643322153 929039655 799293701 852178959 824419294 249490851 479762895 237288953 221576143 625619394 748668442 849668393 379772796 999030417 995351905 757005103 935102161 494579392 311464872 22577974 404681539 930468644 613210187 845306599 312129281 326491419 107701148 942568037 247061232 476296343 793925545 466349882 50287325 933944909 680842914 241528437 339961779 83816676 354926817 60235203 569689627 578715073 865951670 30485061 270353565 972414246 686562054 885862314 642415622 231142998 111365640 771010699 541388047 736583714 648662587 847023605 421785526 369006953 887413088 170375894 396774759 786148865 658788772 227478202 883166988 432410384 860317241 412481261 860714962 748176019 106349205 157222005 132215092 607446065 332350452 712965146 693274672 851004107 208912192 791819809 928409103 184266149 985142950 923222313 572398377 364100591 352397123 455030563 286337311 741103287 369700892 656449975 760840417 565339893 869280829 429419717 502077467 363881432 900754362 879722200 861461871 812921640 857920414 334182211 429126812 196215426 190722846 906246502 946289728 238439036 950499818 988970336 316205334 909964592 803745116 712611849 311599912 559513642 246500110 883453086 128117351 673414986 805003091 484342030 909895193 842205938 652078688 23452222 34389207 897152224 810243197 314922420 235820757 374554370 209541792 524602787 779403015 7822844 332813611 869179676 176365575 887049174 189955281 452973903 18543504 409547569 305748115 587456758 969293878 723279027 109532161 809396119 23578970 199851232 482520037 418781220 565879651 584060875 215762376 16760905 891059508 594262479 58156456 241403289 90736132 26990107 393054430 819942948 680480733 431830812 375697932 130745309 48703516 775595513 385769466 169017369 477739141 905566491 886304898 569645672 249402399 910560199 641652986 285340124 399777220 257196766 738587322 479343312 253402992 275378429 187040353 207142587 15104217 884896418 798084055 28495666 107799311 353851117 232252716 649340593 936240774 21767736 460429597 224247663 5140621 160076896 809149723 139372112 801059007 645510427 408249199 614163878 125538460 79344191 359211247 241610847 683895986 719691492 89471464 82746746 476629359 432473202 68416043 694267202 171033788 623381341 405349937 48874628 345937271 229418853 840549949 270962648 990225458 962977956 83914560 295786795 58760308 168575726 188176894 752807514 755190362 420768394 468512404 13105848 14215729 133022882 896180512 491069727 108468188 651624599 198333813 130641948 442153051 789866293 297988076 274633636 339733015 713559077 649116540 25317003 293841010 72047749 35801683 2144207 763340253 141030822 844985519 284184533 157267162 217791096 604182065 670813522 375459865 68676133 557034575 203673462 797329758 161119714 421361697 807755132 930776987 113991264 759258793 106385615 526898658 652289709 207461167 598096880 764985322 868912270 897739779 492537700 25755076 680055614 8967328 903038193 939973645 815865972 491185578 621060208 125043411 169617446 68850538 847972614 447658977 946435562 599763673 469500499 455953887 239270383 59563030 480987465 848788801 793202885 200150426 90360039 339820144 169682600 155507953 690410160 356993299 357756552 412363926 882202368 658461978 358054894 296173393 804773306 221623125 625778616 600682791 309422386 138422692 400421424 734666962 546035859 199410738 760101845 162640038 972072811 836000286 461508999 429208 597510925 740679582 303927017 3180630 624021310 493334200 469546453 764850275 2889972 351281771 852573241 327828436 648912463 82334952 175286707 704275450 988807509 749715686 911595951 783962674 825705623 127304825 840136703 854191364 123074215 328329805 803799825 213132221 207273936 114634265 141423124 324249160 681966948 20826124 425148975 967171042 394994086 651811917 145541090 49498660 770815923 128927 711112787 681034210 351413947 26008286 442982157 760436667 377761865 975237698 923167445 778883094 171204930 838083310 525098115 828350416 658878251 712482366 205943711 883452349 472374735 981399735 362316044 448116429 989851435 421448557 581852003 372474513 876463888 43152508 125737843 719297805 386108208 620348082 604233772 573165475 398887687 282492613 661323931 626807642 459504934 441993702 117798682 285137867 758953029 398668630 894784627 305377948 881775261 618490892 345939350 6486815 348998258 525020816 629978968 360178094 748697117 379456812 335134845 77154962 929415498 311165138 730846309 365321167 995322335 254439397 856059239 245184161 369026401 138573287 436520625 903048788 739936886 244295575 445753878 315679971 350719914 944050350 275981807 217894019 318802139 812364227 635760341 918091376 705315356 349079470 506584824 281988493 713953236 570442769 929227000 190375881 280735300 139711457 15896130 229783310 383441272 141997037 513864019 114057256 624901198 612251278 410970047 237764217 739830457 454300806 220343622 319205877 665583776 851289635 744478990 582854058 973547861 641940356 587074576 335293742 743349315 159930191 652530947 734602068 131053753 305390386 958947243 391217194 463503084 224572020 634462263 410778363 87563869 41558885 685629199 74101348 515266762 725683938 718048179 53301307 717572592 88310327 265440340 497420674 99095079 955604546 144515232 36100710 147216976 957978732 285353822 558328343 441836998 649967576 484106672 175138253 874073662 512130639 615787697 981538663 307413818 737813470 58732127 20432523 721311982 112737008 822868055 571109530 779852614 25811156 906258331 640440612 378940974 604792540 447261622 75191152 267460857 161683134 999522853 28168417 374544155 971132596 338445181 576567022 892424640 975281439 951410767 928462480 687052973 995289570 777188359 145328319 896622932 900146665 426013020 714360116 515563585 61112173 928528851 451871572 57748520 704218573 476325389 932450492 381721275 711130254 378488250 301537070 968044550 661637955 86779693 234135054 201074061 164521193 759845925 477072634 158756794 531121568 770270210 349476589 410232967 863641506 832220402 353539027 352272939 31773045 466348828 460950145 85406251 751094862 875722859 243488649 320458237 734972197 161474042 555113705 663203002 337283222 944353749 708432746 337924952 248300903 517418150 357989748 724216350 973299544 297590455 628229107 646166502 696396234 339385442 482724714 319729200 847473311 833928370 527529260 605604814 507298528 638764680 81085727 338305309 114514536 280350845 385013415 417999667 971675748 623116516 436126184 625198795 765401567 242042058 791100783 686637437 296543916 345557726 125577237 216361838 467824250 411949707 294988906 349786029 739904582 958195422 994025430 638694188 725691764 243668106 472974465 325265008 24678589 429023328 994065681 39206862 726699423 376377429 100647542 287083706 892998264 281108029 930227948 176601840 346029675 211670472 651059273 606170586 931186531 996637678 104510816 720586847 517933417 160378646 558813001 538502896 946077792 829626784 494953978 122834877 916766002 398232184 794196482 4993417 367308998 564081209 28971038 626603240 833534093 39803978 985473054 655193272 688858009 209210543 419823827 754099738 157033465 845498104 627471602 982057385 822267793 540658608 446773551 653849350 531249891 275561279 219154771 940152594 522946646 482988472 457201113 410454555 221659568 349285382 805014560 621911579 886351309 960355889 517578250 927073607 106135906 797935247 329019843 608144887 170686883 850596803 503586124 392811513 719880193 950256805 721877880 172766170 13475937 569673640 744123409 15510291 367605789 985198978 496967237 967922246 419639122 272458499 977496347 42350548 62056168 210764375 304376373 318567987 236528359 610519280 193779053 61416335 696383531 78311572 506571145 198196633 693206238 553479895 48300641 89302079 363507596 285467590 40644650 141575930 325426470 806290837 84445521 323596859 712041001 507957002 760910412 922463241 327916097 966797362 48672995 198461098 317652814 311958448 291775763 184567810 601036633 648197165 969874717 662821506 305073470 514299426 494333330 139508627 369004945 717890008 888115746 456529878 258663025 714231607 322141647 62769280 210946684 410959722 218406446 249696497 565151282 155265558 526948145 256724849 486521153 240046900 690116049 554118477 13105779 193946105 15299689 793450617 805959395 71539468 295398657 830762186 614837742 894628626 850840481 965313903 844087301 361088360 633174742 88862049 141516094 254003218 689696514 786031883 235743978 974111039 906321450 971728113 242315600 243076914 779122093 785999549 714679120 202873612 323200307 38909302 915827636 459461654 2759278 868088132 389313138 350359420 92629048 231572416 217134021 409626749 494806990 621452855 365426332 239731591 656038606 802148846 381861859 550036018 416347939 134040868 3449367 976833645 611206451 829143127 723657727 305294187 737293720 917686074 142499233 353240185 571926336 552872970 261086869 994326143 222082050 103947392 380072406 810834451 367173888 315593276 755418167 926144386 407411911 107106277 551359105 858579479 562205858 929806430 860697121 256009601 548169794 827446748 971306325 821021272 520766973 335603578 622150054 254029527 516947070 221019826 692619499 175823653 129260095 599374423 143731826 907876164 829028712 332517211 417999568 239873019 548908965 969555059 224151352 114281236 752536058 1006562 36188788 335298871 349063836 663177062 28501998 504767334 140796721 547180578 155069315 452886228 506446470 363109817 856323366 207525898 872773893 442140751 392969763 767524764 387092899 546930218 843100685 143772395 955892923 907408517 594718391 224294181 625033738 697660486 506363768 457245271 309636255 803741502 567428239 673251094 636213839 663965230 57718379 559338461 612167836 230143643 382396814 408817533 934310402 362127962 472670342 475940077 738776608 9117451 884547856 289487449 697626912 129529792 9675752 242548533 819622545 481613795 566157415 880457331 432273277 364230305 65014736 667160880 186863435 331156542 902325666 707748661 877384620 951173357 355688341 131945485 169056762 645219059 936593 435553163 640927290 995734275 527620474 958280118 37308935 86222635 884529946 110961381 871873348 996445936 357748921 974727457 109266346 916010950 592293498 97681900 570458867 952504 556049693 782633580 220036039 260765939 518636734 917375245 3745435 35849975 698427505 448354014 318604677 659401735 511580999 870478232 907201963 111222359 45095950 573236182 175297147 97135566 854455575 256562175 399252354 72400789 159621634 733445201 72931420 105365215 259563461 763132053 604925730 454947865 378407488 393750955 152836457 247207790 876791466 583543120 946141219 716942980 803348303 39837941 358873691 791778694 423164279 234241168 614785715 557550086 33102905 982644328 143419939 609222994 720518520 4163255 560021447 531082016 601072530 398128428 906831811 461747089 284385218 385952594 54502842 939198224 282302258 775988250 32300693 951276597 95799580 720118247 848867628 916818042 653716847 837846711 999207966 471446601 550389110 399293668 229173470 206858556 167176751 6501428 559114632 556163837 780872152 366036023 35762709 303324299 537169728 106340672 900491117 876471970 182288198 611073590 579275105 78253070 574821359 184802252 748549441 391047129 630797537 726159791 780101110 88372216 828250618 256286358 968496388 218559516 428085492 268464662 406117508 654374017 123649220 922345663 477747997 189878962 217863984 83929365 906137609 740551972 290372842 846799686 285101813 831467933 624027805 14040203 698766080 691745515 919210927 924987480 143259558 848070701 174346675 182403283 954164516 455568622 733169079 144664508 798060815 71733352 719105965 141007663 531238562 133587651 645943765 781167478 158387757 434887915 94411959 610715577 172449401 447127272 96251174 904285523 50035033 903545308 643553384 69080677 85517903 640952921 732044777 564944327 479613899 89806025 12438243 473302077 708799199 520085167 580739087 732582202 500104527 963605494 514252239 178748540 127864900 550065229 16128487 813408435 919760930 113919248 858857939 641695985 369567752 135082666 256633151 812175961 710520912 576253162 537813915 178830571 814975986 175843400 196584044 373907170 795992034 186875202 429020946 60748806 585708927 141218737 553243697 484543297 520789927 971980632 203687646 968591873 656151051 200773156 369918688 680860584 90208984 256291050 264602949 407899562 251407094 670109064 700055769 338082385 222829708 38269915 719626601 651140519 580667159 109745272 73639735 700629827 806992980 456077220 537730710 829192466 572479609 524495232 216271572 111323149 225485928 149283211 755594378 637788629 429676259 837074052 744227163 938773324 786537789 436645309 459678314 505489761 763079904 239795941 940626936 194202488 769091205 236332806 68024810 765916489 66740924 510631502 846952627 412335132 82779099 514026941 993623630 533951905 915184898 261571130 202829395 499311206 623137556 154978235 516433422 760912410 417999057 68851919 478989959 418019029 134660789 172671368 854330196 917892757 684535905 927278678 673585346 412906859 489305470 932009062 76633975 258320485 27057471 868130252 700142124 662177049 702705690 884612139 828977669 657965552 739656300 413613607 945599138 127944719 414022204 59450810 823875943 596459468 403401294 413691764 252266516 380866997 346263627 458292632 702183136 107089324 220035985 909126204 436372306 560998406 105506334 304178966 4767641 295686191 970719877 268091781 745518246 564128662 766916111 483455658 843967574 366367938 361390477 257976989 260185229 636694418 950499173 132260578 136387511 493499170 496664805 187652590 746783906 89064456 640450492 908279616 615757949 828444780 136883495 592299468 707825457 689766743 928625884 991365006 265677938 284184338 552223197 224864157 466442908 805982779 132635462 877045218 442577508 356175386 123324996 103120223 588413974 811684397 229003620 865205875 574158360 423787332 848091922 670297077 463275408 147881160 573189505 995085080 570370504 352891226 326910482 420824615 340200464 477391413 518276615 308067689 308373431 939646195 378060647 798923160 401841181 372474586 108048967 584828232 866597330 940992714 651863909 374719783 689222751 909982643 390859584 122469632 251424511 969225653 874737872 300739382 898587917 808646779 790929677 928955347 116505391 551754518 698395994 79516757 342178036 288248578 48333442 87822317 848413967 889333516 218587959 131316056 34681446 397731657 147352430 634293268 368841315 577908248 735995736 992823406 477480171 573653170 338838634 946886805 233714058 384012078 704119664 550388826 258660071 489145175 77579724 24094840 628991017 886188245 568706611 617819926 972518829 62417889 778361975 629918804 189686953 787716912 121939623 430210363 357592660 382025820 352199179 956018101 970914084 578768985 219094489 658841984 846291824 265369602 919631789 135680268 109332457 770448546 177042502 993264650 595684409 446021282 43179586 932895708 765552798 203085189 400428101 926041325 376410719 179734558 240200060 856816585 655034831 780249195 764744983 902759869 859174149 720213771 54954894 932909041 340678615 490521248 627462296 586025944 850483264 149431473 254856654 379205339 712528395 605982016 456927280 241418786 706093193 366779451 310940970 903864505 968768997 50089083 473797800 518368582 865368783 887542175 54355822 565441345 940494742 199734344 955869126 355481125 269858787 512072124 995739343 213573817 596633175 971342626 584091220 337889279 434479032 862899177 911836464 812423743 152607996 473365902 558326978 733222567 858208584 319420605 390145884 711362022 890486085 464903154 7765528 74170798 191730946 641484164 226202552 452204692 752536150 91600277 720599603 474984263 923883980 892539363 427020438 380435001 97662889 720297290 548789239 311764502 127911508 788532763 528361892 685026940 600910117 398969278 378682890 540663760 144442839 23257760 436897879 299613040 229488469 838672598 208333643 380967992 749954201 230365488 721990378 855395945 194264595 170123297 162934274 877861375 670986039 224473154 507999181 533359530 277551946 789188600 789782931 357899792 554204929 513276780 993576350 360607885 968004373 911551193 30073743 908803806 181675773 70357119 500304739 817635947 742639519 261112181 172542863 176580830 117260394 615522945 392609924 154198494 899025206 686269837 278939993 893610474 935638207 451862903 744116366 22619761 866038969 228691772 780 160356381 284892424 976839540 993871272 638454279 73191207 236511367 220950214 936777157 35384011 209504962 433178645 693817576 280789786 813222712 788387207 133591876 338170906 803498154 834421667 368059932 628746122 160401677 453676927 135290936 189789575 202160394 550482445 710022738 952596987 982027034 227321254 691114768 973172178 953258835 305235631 952314433 464709153 734293811 669244123 244178510 431352387 989905508 90835310 557967007 1186095 656962467 678180545 512139688 427100232 732446413 303046252 115191851 228354006 935219420 495619251 881690482 90231034 898335570 839338420 774718167 321455232 287258688 422906166 259101341 429777380 844201036 811352278 860248269 258058060 831508703 207361906 99840685 163393227 854904873 268770641 114135226 348934657 823651687 516790280 959456626 342666175 204567550 986779117 986276753 38871910 785797316 265366687 993991279 459524352 761744479 813757404 790028736 616127196 54285167 655212151 9815583 210294766 25930728 472792357 425586787 553622365 628814812 735574515 879283521 17902678 915000039 379876994 716132995 411570432 288429104 673891745 507247252 983055025 120952019 990323618 706537426 145128501 218657163 561607600 286757277 451909647 984167969 339423104 957019966 343832352 791190452 87738972 638930711 237160157 343632079 590360381 493812430 965090962 191820322 170250132 574164073 740809798 442141183 67442510 257579756 514749907 943880192 728586463 955274867 959906506 455453249 109453509 946745903 323205196 902234818 191261763 264181265 69415998 554117922 312867607 784181625 213138830 85616856 955102053 926533774 876933540 773673414 420673997 508170308 426484404 175575444 125136091 357738698 762114746 147728373 359226158 900449953 21379714 699817481 376882054 408603395 985401818 162820956 824390859 23155299 822899985 157478142 114352768 502272902 279288232 357195699 392386689 679516972 444049629 152442868 309016328 228878336 352068667 510990708 871375186 680757133 280103033 569284542 981052587 700684602 81023640 503641210 475794469 422180105 371343002 285636501 424908654 575058014 794366576 742132185 939175632 664244320 190073978 612636003 346734649 924961526 575648408 527315973 49694728 617629647 32531749 968306508 988951076 573389781 904112609 293832037 411684782 39691803 876144604 952474693 244990518 855220826 245922417 979968309 731401632 726606985 25352061 51733309 719667071 96996444 148263206 131367993 952061834 695113139 847846774 395921323 388506319 370483251 854682406 320867962 577476176 893874111 936422945 392938810 193902967 158264009 116540782 502650354 987227074 929783179 545466895 564223397 426082495 958199661 501034122 777175736 324276882 780594778 156331935 225287821 641062507 798870061 452433809 832761977 38027939 96600120 643775089 919036029 283568737 525073136 625619055 525820934 801207708 207852600 134035460 242539265 825824962 376454749 122089441 3621776 939116160 160474143 173900031 722888882 432859982 646359690 64182461 656230327 83087903 704529501 924369353 655651199 297300378 929849682 933357142 16147965 960749157 779643751 447255589 604610578 469314790 256419655 369051166 353584846 54419421 494890020 738557284 655278803 957021569 85555961 758054191 880671102 2564770 282805237 951001841 755242864 368888290 970303548 638331795 358422072 670709409 862824739 833590580 727587304 538018804 439306586 8392480 108293730 603315850 796550654 598103422 772338059 887638758 113180974 603514819 904862815 280920788 10516429 917201873 874085561 665161517 969797148 684415856 574001594 461742849 111170836 145939039 835997960 651585958 833900030 607188314 702498910 974789615 88980643 576272917 951660784 375939234 736531904 247626462 672852683 717160582 946399437 896649284 366401961 179175446 315631178 874406593 528617246 783576335 59065416 184539651 990449907 150982 953549166 633264165 774432129 851228481 536307650 498109019 738778079 122779608 254647739 385948519 95485454 393025685 356914155 261540598 69899367 495817002 879220553 371660925 587445731 725506068 43482521 899273328 406082253 687225274 640794035 331850733 449092532 245306242 493131429 493218997 741546274 933310799 292422384 983363240 143884169 463524456 866037942 562002591 372495292 684108839 325394322 746579636 190589088 340665152 614543761 756444067 723817735 869529771 822658045 92003068 419263209 639878649 652519590 604926076 780320886 238974602 885178048 226900042 494563404 609662584 181076024 434893780 104284929 100398886 665104114 945808350 634906206 355713802 797036401 841493001 701959774 834177469 918569811 959301659 791491802 709954609 225667797 84484440 558371134 506598354 769981006 637255368 948066659 412475399 807428350 130854369 709919690 162871189 173885912 572272056 731353545 418141488 609918536 710691346 640146899 438027285 433795806 975494340 312127866 540703600 997482683 287447817 442006184 330999761 425807640 494420095 933736903 552002874 630100034 566582537 507070972 646836504 758221631 26011810 307977275 616651897 464013998 455272029 563540585 7601938 18202622 835563038 393512882 495972888 268544175 778634582 183478875 561751892 178532842 282500283 746925223 121892771 635459020 334194554 894148768 849228531 804701026 453267368 564569456 736739637 66974218 356423010 998670575 380907886 998614604 269938121 382816308 111742604 983486926 99670144 586145122 22557998 322111848 976566365 134337452 319668471 48821584 189705874 791853346 57383728 133815648 964381770 170091849 809970603 908471883 984526330 9154431 778955383 655968814 196919166 976619605 260042285 842685081 26141561 306256977 186750738 893816661 672586040 740616015 37977562 928306300 524411910 943045614 755648332 986415871 889143176 19876538 809976915 898442557 377148274 924983429 884476147 366575961 914041382 865810875 293329484 810251622 50344067 391309671 537245606 836203653 242110427 39569348 897251720 466186853 8682423 589214265 292718806 770470041 609139463 646213190 459455058 830797953 764262656 32213053 828773368 555206348 227951394 678009158 49431723 362223944 119271660 589425814 781736328 944815632 792283337 60141996 881452801 195255500 33256030 221780432 142092165 995287683 57857355 981081206 537919123 187239653 554603373 186359150 632962730 520890228 824962012 102725876 917414023 776679819 285728793 467081439 581647396 154500956 97661530 518238079 867622648 692484326 486825231 460156732 488253177 228395058 105762145 254730248 91225673 493291340 40495464 72127476 768668675 701833746 343337735 848801521 20004173 262007388 41629651 992931127 659255430 532500311 998461701 373322007 833042600 766833228 643624557 268605523 269334449 517426405 863486306 259630541 255099653 82034233 966364504 423514689 44115365 988123667 87600897 164465372 887283932 660493877 609564919 320052599 904383785 683400541 200711546 50850869 172252598 448348879 644679983 156837624 931410717 843585381 179970906 503679357 677919795 52174220 92895547 310483752 332127294 365204075 356418442 928966377 421076631 105837839 332719807 471242434 552931241 48127863 713298139 889746297 259681670 569748174 441884998 515895738 648543874 697264841 29921043 965580455 176386875 980407772 667688345 87997197 295492181 336960988 901666316 360374101 226242239 235292623 999475090 865885584 280386344 212064327 47511345 94476603 376558631 284659999 787907810 53093659 594685771 223041889 535754447 122702988 127482758 208930540 666362155 611036265 276126768 591671510 471111184 911196196 79007432 51693819 115231332 965110520 997092190 657609812 628309460 810758210 489004662 998281798 745446253 920861868 748236198 468515873 810125407 893036028 589427216 638034806 982843731 447241115 364042891 194255390 646456195 853985885 989853280 635719546 387227502 290546181 794351688 215151319 868712120 933102725 240729588 103926547 872877216 968346356 580980002 454471097 513563584 457536587 100998516 679910593 726906619 317764982 743309926 579264439 722293722 685581136 557873176 258648587 731309660 146160116 833239594 618814258 266811255 94040674 559806795 391747966 487533154 119081134 343322837 415930159 515748305 135050128 847346761 84400266 487849633 392820989 763727528 135747023 264250220 538347057 379813960 180028634 107792682 206465624 859405521 660373945 910174558 785499784 97661585 324880743 489868126 17934763 847180962 840195155 146737849 357067338 400392432 233832091 677961759 204167752 477319577 50281426 231554721 926702666 275082486 96044266 364263122 17007041 690999261 426660887 301213098 128397868 876513013 329294305 550430898 199315531 46012388 699458131 385867478 159572363 394145130 288291855 251117069 693678446 375234059 309115001 347230914 586788067 315081591 942308244 454722415 867585693 707308114 670240949 243606229 467438017 979414283 614361641 293151210 970133924 883520296 105531096 746328303 476052387 417377439 873868985 104123884 313485708 298282351 480435183 724069698 293101218 703771949 592725834 62878805 130702465 775595462 696800584 578714634 1581070 356573202 336664454 523533789 271177906 624239754 261685541 464420691 266378152 742684808 237765693 539564039 842384409 486933296 484217472 679938689 710962430 560869095 856327132 193227977 358935180 509665642 522637938 93112132 457456358 20841020 325591191 466948708 597122460 305922600 845161886 860722667 661149308 702873023 846799419 794743300 776204304 478399353 531615005 428346025 600546514 644652812 930798530 777246786 192250817 686454351 272440326 34529589 610677455 408463943 63125336 789327879 466936004 587233285 204319592 601031563 438393309 743011335 177770336 110509045 789986737 971723165 659908142 189687924 656420851 851870277 925850038 26287034 43659972 488024074 453321998 690269 834858064 882523199 82542903 351542843 962336940 161866971 744143262 599681528 401299978 872496762 140659756 20003476 771334341 7492552 690661978 601837216 485596879 18987857 519106880 869527547 716145067 712997274 362817845 487873791 993265038 555504694 803893198 87705507 104476865 630679085 304580094 433672393 361498573 526337952 723949682 888217677 649261016 926226471 722619367 741127963 78905900 15597446 958211575 588930971 221555714 667711725 59322885 642329103 166756695 320317434 216005565 186237090 608330902 122002511 442873567 165498226 254238895 545904032 438918011 950174276 134796013 762746871 364896684 625546910 108033877 299512199 534000979 118426040 911065839 751114902 763151241 15865388 483117408 532227487 230318243 829092132 138753299 516808147 404602965 884576526 948663520 581223701 184654610 530528090 115015253 531822049 887533664 116161911 359975358 396641965 618348661 487036333 466283514 265540855 396062842 326495745 176266268 18803529 451927257 921166082 405559014 770659383 776235032 622111046 772864945 912367192 59716468 138813076 573723243 163507114 454629149 912843230 140455491 970936374 829986226 826499670 833431636 196184490 84354935 107041740 274065331 494281452 469143063 399061448 929116892 157943356 633745747 315427306 420976859 400065468 831939729 274527604 524004869 525492001 115256117 352050684 381725868 961295108 947191763 634451974 826301958 616268782 654006327 53452471 145517795 257613864 888970858 531907061 426966186 258727307 239761360 623728810 794177911 599120234 679460942 299808684 346065769 529844325 109825894 332470521 216788219 418099906 922757312 968318778 926771167 796019133 106008203 196497133 366622353 179844082 937494490 747231118 540543160 962484131 206100992 788932700 313763496 223627156 963945383 922569752 305128660 726122050 482904122 136573904 747022532 788029749 650778824 639449135 24521575 509125166 260922835 824879400 901824109 493866763 46389217 717670640 79941240 72673078 361733234 342833398 961062334 142159237 578493585 55181946 133815633 623423161 143221771 591440244 662866705 766736819 646824213 928681658 501485631 365438821 868702754 189742743 481696324 534510165 220210405 780406839 964870871 920149573 147216716 809866919 420769321 158568022 975237330 544512278 213717347 452846393 497710647 247575371 979194456 209169632 812377071 666361863 724255699 204453410 198047960 822937715 574575877 512051207 154305027 52611806 578611269 858181223 878451071 811869228 334328610 597112308 919409757 325835568 235572658 179266016 662401978 44665807 807854301 514227137 56446293 665020881 623441774 931090517 947411801 480078866 782022797 271272530 859942890 320466158 75658551 638992569 434627272 219005390 956639334 647692009 682247885 346666848 569248736 19559299 482751940 900692694 486032997 447346538 111052768 77838052 987350284 319727929 569521584 680243785 557207065 326885610 706867833 655084769 618319328 459385829 643186531 855608117 695394245 765557400 347874352 363845275 690457185 771679536 599241052 298012132 184290998 963063492 56561017 323282004 430144417 994173579 328354338 82163655 816836280 227779711 120975567 245674260 441548671 322378811 683351792 491965891 622999031 700555281 312919427 771163964 80639294 61719760 435846918 294145071 323034087 775640104 964295048 349022823 572516876 731051086 22487344 483159908 784694534 121045167 734143104 55728693 21074083 478111691 494507797 30087875 597732646 525158180 63228317 257001593 798751087 143845060 724600834 985604573 558021816 788935997 62416803 849658077 859126356 348680775 654157885 63650249 184655126 22068739 425261842 337425507 589302889 185625669 673116 447867086 645610759 792799630 982762098 369810598 571068502 155877058 936362289 100987709 596956665 982549885 192445914 849531280 77221063 699017774 502297624 707682306 970169398 984278709 874625483 139172975 264215393 750933867 577182501 987753271 299467250 408342678 650934260 284429966 94550944 883044443 967111330 977164386 457459661 753915794 530177754 676996669 416203582 832382290 91289209 50855220 629124039 648815394 204568845 992592990 655402682 443666462 549631935 585180247 450233966 776345021 60988238 441683542 238035358 82519100 695075015 798236118 59418414 859840238 788232904 731504722 552227239 142680856 554504741 869797156 639217862 304877453 353516919 472800543 125574634 37912775 889933505 276706343 772161496 327640356 277951649 145541100 770394405 138259058 276474363 1797076 62715451 673450567 283898826 800466450 755883249 899676724 963704561 906354361 214368950 262763717 295940998 929404117 611134290 420901016 146976129 814731653 642298407 617006539 48503621 888657491 217313436 645167747 268203361 438774607 970063965 74362989 179381471 336384483 222323421 894561259 468521854 631823516 563420825 925238298 778648826 633423917 853259552 955041678 902277107 632362394 703950393 988436275 264020470 334414636 258535321 593181107 224850668 95683878 130280419 416600104 687617924 199866933 334835907 909310933 270617236 624408408 266667196 217394853 529888219 195577376 781891185 123414446 438230970 133125429 168093263 289971583 817034901 339651468 589821681 700192715 570247007 437336645 650164103 604133675 365696441 504025179 37810886 493346215 287327197 169650400 991885386 712265613 190002100 793715139 986000290 50332965 280861808 2672982 734214557 410909485 688122542 369423325 278533341 522144043 425818096 14135765 105209135 569057904 220399702 615475843 192112041 129079192 210868952 73968435 512338106 225372683 584861963 854150015 742777766 498674746 652034853 284874308 216604744 825028341 416301750 148989996 981739553 60350589 567889542 257829054 26338863 536197026 467377873 23686988 264185727 132587355 825630945 781551456 473900844 309613543 947717446 796840094 240509328 619411217 333678202 334018570 229728250 33515272 405596874 368900268 559707703 488322458 504219917 93262532 915093830 279831164 751511804 205257877 439931638 650558318 143506603 132585477 442636739 153016338 205013001 472271250 497407951 455992145 713049713 800844468 594745713 513779495 478514913 941833775 232786065 478158251 104500660 203103613 5788264 652289454 718732582 539408809 669185561 921964518 24257498 738633127 726324763 76501522 792262512 356641742 955556922 172248985 702628225 387422342 117580425 927123963 675282028 389692873 99120780 103791300 30625349 514437345 327347921 362219434 66400036 174150958 12370453 794838848 570914067 784805993 86114210 978339381 76564870 331842813 526905940 946925914 252214797 732697323 430129526 7939597 934334497 805200546 749600729 991885173 565389881 111622248 397986658 965135742 493411075 109589514 747165345 282198618 386055563 483501403 353598253 418033968 119056172 871129414 601355781 458773025 462710566 545998995 641941297 387052859 490518684 948993958 526775801 298605865 944531505 226174093 276158018 486474288 764394455 589199672 818202625 714658502 467806374 237280282 151661674 834948398 479838182 292675914 198761246 528011356 599265498 851407613 706988793 970659116 582539395 730482838 269882196 221057008 756014535 817714124 168807930 505121082 923244419 889314664 889940615 257246770 409890650 507339355 353627474 148352329 69535785 25415189 663378285 98663263 935238700 730539953 422208431 999069244 488037449 730236121 260352756 25086283 909639811 395354330 269338251 558050057 479775604 398863989 286017247 688209620 443299775 151748813 367301959 748459658 622089410 306653739 740120247 393351971 167163482 139490715 809054785 16432442 445842952 70982596 242029087 780079893 383162664 959466601 472270683 529969916 288285192 702408298 627390412 263128124 374867130 893224635 474925210 701705080 124073513 505032909 129046113 922291670 661784495 313086723 928206925 452526588 970982055 119464975 553418778 561109883 318650214 590153005 79409353 149998064 372744298 297822115 849861565 513876416 146408189 711047288 911708456 478973195 80714935 402017154 501431071 214233667 309988632 197104785 110457722 632899472 216711692 505084153 650386738 121345304 960417079 854547455 617051190 976208421 665882611 715412660 191121035 327141777 792314393 523140185 315034411 13984747 98419803 589750871 320173838 260939755 119388850 1223659 740807337 99732574 29232296 538895753 972620334 283021980 980667822 652132012 271464384 975452821 126605819 416080324 856462432 77794579 865273112 315281134 354485476 745907892 908622849 17740921 681796882 664366643 620578762 690207610 473222958 286333073 59440604 84538363 412480918 75184770 269098624 952568393 694564606 46438940 74569366 397352680 834244449 370970377 378036611 13106430 921736153 175603459 613961257 456838893 682251195 980849279 191584829 509810154 302602377 324608685 327352299 452747869 336874887 3349832 4725445 449254523 36680640 991809720 719821737 790997289 17579041 529040187 552966423 470896568 879505258 164374105 144489624 281086306 476138339 353629586 965813811 248797496 50316850 569802817 555323427 227929994 995954252 314922369 192656351 816804620 462983917 516040560 309813511 909218089 184487268 499954520 351536158 333794342 690850646 351782053 481828636 389451887 327043153 164525669 58268083 558834986 649030320 3381211 579082496 71091640 445753928 642373589 245141856 235167231 253256376 876011290 656590859 287530897 669484377 637950844 200723184 249696058 806855349 350075451 767907020 117133719 626550990 250830539 215887614 24091178 952452158 178688618 435737905 148354306 177854616 102029121 375923645 911884092 789916031 607515233 94288561 490246194 709630156 209934854 884051349 182352472 278861595 524512043 858952290 49620338 935380490 882009017 700331175 585352804 401320513 311485645 349940924 893731163 20918575 19410418 411935271 586440408 874822006 641764961 443003316 858039479 200275665 746713884 644932979 887579408 979147928 703551296 17032270 972635367 950349985 374729884 94681620 963671203 44990423 514573634 599646357 898766888 810377981 434160434 851623615 604236827 698076775 362301432 443308689 445102761 850314342 556739775 107380432 879758268 560352046 815370877 814182699 819343289 705995463 282503490 576544526 211638133 547775232 996266395 585996481 852797560 86708244 921070539 318140505 620790984 256082030 872745035 720758259 15876296 671255101 793095416 318729180 3762168 234521732 954934965 686376057 97597278 153564426 555547172 241550179 159845730 498435034 822346563 7280660 346613420 963692578 752670758 644546734 110579335 766854957 924540848 144800417 91124152 312766570 17550308 401158113 586286614 1694457 296661585 242749401 458738681 3084879 330401773 601179533 422021384 818290154 91050153 923825670 264743618 257238000 142003041 914256152 537328987 32419481 432676834 533241153 76544410 691912313 920117577 526311467 555048587 508863207 951964117 545761331 265324273 550353303 673212748 609755030 382277136 649968929 792337582 40650775 7607773 900261467 610204530 875319314 853221034 837237590 828506836 22368887 582973365 967289399 328262524 908660287 932215139 730861252 744961805 962729781 4013454 369614637 122868246 319284698 679416146 287064336 780148062 863614135 399424706 35854585 95106467 627259034 519047721 563462763 721688223 524219442 455824671 415277861 214178369 167992594 469546623 484470577 651004040 508039645 822892951 221915897 655861282 143248419 639095692 635725184 589622291 798436103 553968654 982591523 877806476 933721887 887389521 547193397 752520756 493315519 189162302 939448028 47267403 758672961 827982554 508358353 758742619 167261411 3274718 853167316 424753459 291746744 852443988 952333575 281541592 80740979 785321816 677044812 389450650 824272218 639366903 307598094 158522694 385021407 625250517 642762787 203090916 710671046 420740946 907783645 868915305 567006812 497566288 357219811 310378844 643219357 125406620 983468772 231419228 102869399 868936603 100074873 824748639 82230366 343166273 593180959 479094323 110396895 983151848 559162187 816114281 235318576 375233974 586852532 785736190 276312324 939850020 719716824 533395875 920286228 239529733 914858961 282457929 221873713 34501558 4682789 963962795 27388681 425580110 84074141 899629654 263325396 278627858 970478873 723128143 679057651 730834604 597595070 37043537 100443277 717427433 421158209 65212367 121439675 243285095 661363757 990146667 880557660 17244567 783215004 112287264 321352064 285559203 885121865 308863840 961320970 186201862 254366789 316923861 816984956 779420000 210046078 5378275 592888810 72858857 760798735 759152005 328929346 952673042 760287739 738687751 856022888 943665176 114970825 480745220 790288022 904149367 113857056 376625482 826279537 64162775 390463019 794035537 837765835 206074795 700470640 588371902 49457636 664989595 959003705 947740722 385980282 357370877 856117724 463273789 443422441 851924615 625767119 249159928 695936570 416581577 118133420 65651686 848096128 671810237 427809652 516344943 168062711 985986663 713651447 344869742 521328217 260020395 968758437 408612953 163580878 37387338 342820587 987202021 129973467 444362378 721632775 28299428 97775716 315950006 704959476 957751317 277608521 107484869 130167271 92181563 425020054 680575907 402699782 20431276 112816932 335103563 895135529 888812706 549955964 7322400 277990692 733315380 796725662 567915800 709760101 472755799 296166943 230491724 435644072 179498560 440627638 191755305 150375538 962278391 357207817 158849243 926304186 179313682 814759368 776905765 462356128 10020279 734619121 21146128 652897278 344533966 526328074 556988193 310099847 944704258 237192357 580783922 942313863 552503557 951189580 81298136 55265733 611110379 238047771 898505922 972684961 589640456 108230285 92985643 513935635 85832044 492262717 629642370 831090695 320856076 175632804 269843395 598576617 325057814 122893932 184793391 618231430 968957092 475068735 324382388 463879710 370592289 682313461 22886721 353644957 409774581 518234003 431602944 506574385 749777499 820606586 788937658 221356628 368400357 271802473 973170434 415974222 585617347 750978283 836906119 996506847 912943755 719234585 298402220 242108655 767365394 895043605 622699096 685427381 893044254 152234925 834033027 455318565 770856378 323834979 530749204 425691614 193972632 334639465 821026976 672523409 661686865 724551410 878039436 691071353 830749339 653813645 56132284 954638497 355230090 839607991 729360929 160865292 352451446 15002491 851517363 88533321 327328211 12245379 906639662 919756509 696346639 327002192 434813128 439553220 998042726 947051052 222626981 190619006 890146321 531076548 991319618 619776877 588637476 88982000 641599596 754625332 55093276 834911716 360236398 834262421 290545938 822619121 684601316 150962825 516887088 899653907 41911149 654373734 795826768 742444074 340636500 81419562 932376021 810359677 560078923 724186525 561178874 129779424 213129943 780016341 69335151 34841058 989976693 674934127 788646517 292229230 864933059 104417368 28519976 357420347 285039929 636655037 210568717 716974517 927918151 963025677 446050477 846190663 224826828 698090099 649393675 793465291 830388747 691587346 68433832 348151805 2379626 621992236 614182140 609166711 200960326 305160635 657033465 410411606 434865363 452119601 218426825 700003380 658336126 177691742 52234095 789256163 977556970 63905532 406273528 571396438 122439580 371174234 288792205 167965281 393560762 282799910 635220683 549332331 458927078 138079542 989126460 208715022 474016574 448699643 731403202 370197238 704599003 693202112 648714204 838979270 879432963 325488212 253951260 475364521 832029067 586468448 838683819 509624198 730755815 354443500 782757815 368335792 957533299 220472566 926426883 629343835 355739050 974893733 639776848 210904275 837819066 678760782 904975367 313155037 330370132 982156978 555369128 25158131 313648431 519686716 617853173 97149301 443039089 967053629 64869114 869207921 99592375 75693363 286661617 540543021 419847296 93118575 684999119 974778658 380183682 683149122 527050302 682146778 35185322 218120128 546388788 502151300 296955908 146164185 899027486 122622855 791534474 777257270 656143020 307636301 331559126 24141999 685298734 980992679 711719121 158110067 513148742 238262303 126850417 317261275 883556111 831336440 236739676 611156326 681427933 577831319 59403765 608374511 334498077 884257632 45466719 365372735 366980939 558059040 497609216 272401773 873714909 976020356 367108247 90112508 563683136 815653087 785126500 458219381 331778125 500050734 97612001 679210204 880607149 221801241 303467154 827310588 295843734 768357351 863157653 26970295 891075072 31549958 23631566 310395379 371771536 134295879 242417782 636561742 555742874 692219237 584016201 957618587 602813534 99896922 546869524 561336043 369005927 801107080 370044187 278666213 691572952 544404574 896643933 318566625 564150645 998057975 732890056 711928503 278798819 593889831 531757476 468448515 737221586 648421533 492068261 773916622 343896753 450142252 344109551 277293676 902297756 504762526 139585940 578952389 41598580 963082848 489668063 775057054 112774471 279882001 801971077 41074577 950220628 643535916 265560971 713005358 651914613 621508664 384184578 28397750 732574540 401849966 276186584 437966420 722922135 531718072 363974594 810052276 114919924 842206438 584233291 294505173 49663445 408484398 799388997 87247188 619311781 802199602 73090693 339365637 813058331 102071634 970259859 691187395 851682074 539549198 21891693 642412032 573943463 745108428 46080250 925672929 749737507 236159350 883588144 805855573 411159544 37937405 805281776 715979158 712158616 616778084 299218360 94499119 255882779 294521325 399193013 396330358 896369194 45590135 173368158 733317345 531298677 958712934 69812424 762792646 713909442 399528416 292246915 155367504 95914060 12672536 705092795 284476834 123442718 269699248 224958064 769780721 178802016 565609643 873245377 81965614 633535175 870921956 370251197 316552513 340056116 366523444 277411048 8941790 157037577 264447219 8967861 356581303 678326468 253585234 986432718 432021146 247756606 879036737 597844108 750115183 470733391 952361561 678624755 706753021 733921584 611506822 45044622 610383540 881205475 377997376 680740775 499288604 968377740 828642444 115857767 588712552 762367515 590532888 508459686 23500660 293840786 484400849 212727312 122227887 37066197 517449424 844091509 244407116 838263797 915659897 362684061 677370410 18831928 620535827 549118525 997649345 564715200 439181306 809314271 206930607 965628061 229415089 834754983 178263096 457316168 818888623 674312472 669481487 832549352 691930168 43438392 948416990 848553917 25905549 371191576 292192282 268179873 570316949 498348191 802199071 821401008 534805051 473504963 60394015 235145002 419555088 48819956 383233016 471057782 346343519 233279258 244308984 855033218 173273269 410157896 648249711 90895811 685639220 298669607 205604445 596259626 340513528 470666802 883400156 580430565 744296423 596079573 422162893 606127713 679240850 241419423 650157512 911179168 626056808 432338992 946029836 755771250 306279520 752322203 770236798 822151279 458133157 839049754 851248326 954422986 859450681 48763227 534462836 364314154 876184311 312464976 29110250 624709155 25853702 276504098 125133205 239287743 217235073 360766312 809414235 312385858 513480450 478525146 680278493 604667976 64388114 590879178 332094604 960234325 218302159 733037189 997491411 59002635 344144801 366909863 869430189 125466731 258240282 54353623 334730840 142092914 800533410 852657661 221064783 563132428 692435507 512879761 540842739 665826655 374301983 889558381 695631828 166338919 964537002 662820625 872818037 293593962 25710648 558240191 991551498 906276053 606428278 145541145 81819052 958353525 946941790 848135327 84240436 151436820 494857184 286502555 184864018 167995796 209154436 363962517 18250979 124410155 764829337 234970789 100340394 580784445 524582323 483475555 299576977 434548043 603546159 426771613 225379262 804190628 54155192 251909400 817014940 738201699 682351459 246234193 779137311 282898872 235739283 95188183 457164889 338551752 867336162 491101378 88173932 274909704 466261531 670410799 576204016 833981255 518545776 804447711 926165206 691329093 112504460 675327664 609584153 981129501 975630563 556520438 923844241 89766777 771009786 529583414 186536808 543974631 121597725 102837541 101058371 859355874 76106930 358246640 206203945 518511174 976135312 600787414 331468664 232694951 354148186 622169953 719609541 280112043 13989311 44734821 895075052 357017469 134469497 20409905 692654732 335966046 57813913 891179509 448727575 482358450 400544449 406212998 647366784 527289925 869910615 328119311 656483194 413949341 712985986 959578897 641148156 596248229 582069866 948217038 509863985 657454678 496770398 79286967 956860759 523343790 314580909 795774668 361149200 76336736 331203357 346059928 909426665 70978322 167266545 803114010 612518450 752110198 363365892 196396101 691752868 137409143 247149590 140368211 916362251 574524930 756972798 241015650 810125652 642551814 56942356 702006793 7273381 763665720 260029897 734804199 46176081 156234700 956542880 105686908 531682500 561748224 356598133 325542812 888133382 737569602 413413776 779984948 228221857 741337611 16496069 302315899 973777871 233180638 377270876 419551337 155047480 481461727 416206008 818506204 445096665 265853869 62755971 483148939 64389466 878486412 197259637 992127857 675972438 301232882 895563134 227427991 789407448 994506455 586076272 293989958 53190535 480529765 585449660 671493777 309318862 387725205 66060997 642920229 512338728 995061748 159214366 852692398 850873309 167185357 512854936 643117003 795218304 130308865 73126956 771243393 21434674 275854854 593565287 529864538 916669529 903321691 584685247 466768191 364887209 211568279 961379403 77944503 304223342 934749825 341957449 10994633 973297025 560676821 600846294 232740432 185365764 582022339 749087289 681891183 312846196 229555181 418883305 224000573 839447098 564791650 919941768 639433729 440191853 293002912 234179518 454045679 231202249 928521244 675236515 31123419 434891675 177430041 169302263 123681610 503121233 745216129 186455894 988535009 580229530 134831093 54132921 58282524 219227268 993457653 101802534 215720465 180229211 580327742 264188437 641597453 404333679 628221667 667991333 278960437 721170938 199343015 639061309 559961216 405209756 948121755 569513148 699948915 269892803 512617096 64695400 550890459 690042978 25521448 813709265 575192255 527172478 934545563 367957820 56817367 247389633 77267329 778345389 191920618 803579098 104685180 775578360 237263721 644987231 949005601 659129660 878698706 354758584 710460131 980593623 459378152 273731473 878136466 179273596 533742621 930343603 879946789 92320785 661487225 915069823 649761203 825367017 719760991 267987056 444307481 770452031 297525219 405965900 698618922 317878586 335497789 833114612 699887224 908366210 321721012 302031596 613007225 198488073 671144033 193134963 650873772 921795130 643162331 212101825 338253111 505911968 400755377 545222352 907621418 914057279 557864374 658479364 549628264 500024144 167565182 223502303 84987199 609860884 360494764 283646708 45801155 575523414 566678154 337361428 244068208 116481004 128296837 387273878 179450963 94073219 707222758 480078342 605034501 557879706 875884909 945734014 109215380 891128228 217428768 29977912 715289095 491865068 668062778 371375426 800728422 341180030 455492217 12674220 937133705 916264353 941585077 257151636 571998986 14576118 407483372 475272566 51920099 428296730 447681690 499415840 780816669 953230246 782067123 808343431 523489993 76062099 626308618 363381235 419697076 937146573 912788096 781361022 679200967 965194305 511801084 850934301 155685548 554209204 422950371 46107459 773933362 316121286 309992864 623032864 37999337 913312154 581139511 208176934 736069631 392532198 690502931 587098267 86476025 937867370 830480322 39268511 548556174 453016520 694855584 803975825 637158384 122089631 318986872 17605607 56826360 274942911 426137755 486963715 731842888 793001882 797036975 911171551 208459282 81242289 742745332 359715626 559561760 722136575 583453668 111423348 906676130 385887422 645115028 524894189 494230637 904752713 229097436 36557862 557745469 761593445 48452199 600857058 110439002 51232482 413170645 39649145 456398365 71503874 280095377 755044291 686404786 304623120 149984021 35994327 696228433 621391139 330154097 177982015 852821451 65613962 656429350 42075885 531043465 129018551 359102937 980333005 189291513 172006861 196233009 294896497 864618344 985609543 470965473 604782000 902835876 417521734 692938454 211108829 2103046 800545888 224807177 282133135 561503442 505475855 868453860 778287133 465865689 582547351 771639644 578715222 99462932 706967312 319650368 638762657 599311201 715252411 211011047 690802140 758744971 802742958 623290977 571702186 854045645 288010318 706671868 13239826 261903981 894453965 257973647 803794731 293855646 483929901 198394608 623258190 468866683 885954047 817999806 463748371 86497804 607849310 355285046 257116316 348342800 889666321 683808050 883802148 523440117 473439872 686206645 292199173 927297293 85584680 566298744 596503813 441946502 95180157 429398511 571213981 53113106 337127967 613067891 894712081 779155806 814329235 182631307 922069991 398357571 569018732 959465921 186549549 675465129 361962836 745704990 696358522 854088439 800409813 42389127 515712301 340629825 597572106 189095658 515543417 536226678 954486864 986018762 843494792 399162366 2445731 939142093 237660909 12421411 241700307 840418239 334658782 880562778 143837819 494422485 808243725 415111724 308628809 650678715 5466963 555597421 760554563 763757835 401513852 900164817 380325001 241533653 648177074 501382030 559072516 925267869 643553386 517545946 803273162 416946340 714180841 198789720 365729057 53737194 135609638 171687616 179119409 825651732 449267141 335876600 542966819 69832196 36096722 840200455 476322460 184188987 621108619 928154333 297900399 820880386 25337256 654466458 620227108 853892467 394116245 2978792 502539237 446531028 950314313 429751046 827224223 129630649 477872237 387356301 555286609 227642130 642309051 717173573 89241904 151316690 644132801 87601439 80503614 260042739 737735998 37163190 516751609 148629169 606909035 439260021 237310928 201777774 431854632 95672030 118297881 793513972 711109267 474841147 612411492 765040336 505890239 465843208 580590024 195583172 268922189 599495317 610333486 784954909 247382719 217966453 924833112 37182083 10233554 911723833 147574726 381333859 443620788 334327404 287230039 223786732 764281750 573519747 972571662 594809374 45326465 292705689 158576358 340099753 179003429 664695239 316290198 205833232 217798408 437315324 337907302 819462172 359062322 320177422 436982642 117096379 614391357 57884140 368183898 909681286 983692070 109789964 567667074 788432634 401658940 567746353 69303746 955791643 312616260 107606179 204407775 245449100 959013947 552867578 851920401 884499511 999767135 141278809 254562750 859379692 321139386 779711480 667987500 124778507 19512978 42255138 974815737 200812476 553526381 740492295 129163915 294823996 616944832 216882091 18253684 715150844 782486630 547868801 126528041 619810344 52173628 571250791 189319380 871824315 196612227 279900263 333528237 196560161 421936165 724009494 968640087 73066028 408991114 527695966 348427409 948572197 98443379 76733380 330078583 537817442 146844383 411631963 790725491 788557936 144660723 578264570 661858836 818245488 506289159 376843514 372389227 167027475 379137452 929741518 844275631 66217712 57679859 2718195 712546045 490014120 504851938 788404305 143364757 100070617 779734220 972484916 780417453 302661932 989701994 283161609 863385401 493183562 726087003 338995102 787189215 995647102 105346623 385750157 201692387 504369408 805629683 841132962 658758885 240639344 198537130 381827437 648130082 428826621 316530594 941528401 320387910 739041933 455978666 434358588 236436980 467010444 287823593 456577236 349821004 249339483 317983359 355547450 725509360 906400072 489147684 918363127 451501040 146994531 754792451 711313163 991633738 437382598 83362153 212992500 751845659 665975658 786785227 413860355 715759899 612166806 740903230 396299012 314585522 769144787 652381377 276674645 513596011 820176556 60094484 781403434 370576847 337154777 273808149 801303329 115809810 220128638 997964737 658073011 259897672 428738667 85107681 744045513 814039298 453041176 80045986 490514699 282559574 767756778 137281834 957443158 49881797 372558959 26417427 828286425 800654294 508212555 246222289 676296896 359043822 268649752 921251122 268378159 348623292 578202765 873150796 419394964 156566314 834553904 800661431 318241282 24233338 111351254 255682098 241122276 665576015 75937452 794950836 717268141 918119868 84736048 257203526 814636257 561794894 723566487 863519527 519301673 813695841 589048532 969465561 691837318 6974625 929718435 964294286 394979393 202102523 335758685 242108785 354659301 316224610 576676244 354247474 128605421 168822576 883565563 552358563 479320983 598490228 550949047 367690571 889480681 204863555 430577131 676910206 437692696 979469363 952981149 805180363 196927270 611777037 707988557 71014227 64087914 652895905 359284294 837138935 659490056 426309493 103615984 885661455 39445414 575339928 828977886 655489536 836158028 709983911 911872554 572504907 113084058 412644657 294689410 440724741 325672539 562850669 395811800 325868700 71008081 316027682 452858345 264841028 711244571 124799146 986126735 44978361 755400390 702046367 962319037 783439980 827491497 406463994 219714089 141680795 726817798 626364118 759261345 196834451 151433168 436556029 629098998 516076675 121112335 187323404 584227516 146357542 267856549 552491234 222299199 617767741 30897328 861825786 488146470 193501152 589706661 831598690 853133818 47366627 549200573 202801310 249262752 350602305 863057035 495295723 796748088 781626734 302377729 780952674 389561821 222553247 118004098 961518435 386070626 795393269 661434764 875813698 554573278 853874538 457767633 68496416 79789934 540883769 721196603 776116214 720948345 229002733 661114694 858011266 612163291 703333018 815309423 784497664 184034033 976901137 817946253 682360544 41721507 937188260 686654480 344619485 32530964 526594105 229445940 429099360 849793938 583947671 989513848 513144320 131610512 315268163 231195641 523189587 54664002 641542973 20127498 534363728 694063608 468142482 136434321 202552078 183262549 262545362 103650342 987778638 486664079 900518373 136928507 494026227 68378112 228281639 789913260 423478357 227269276 915115882 130079628 335678784 254444143 398465986 537690756 32128255 88123175 122062734 128280813 851172770 587410883 116323942 732740010 494643968 493386034 889159320 992708304 269698639 851172610 828998997 321195589 13447773 476485555 184269245 359602658 627719830 545605912 515256976 60854519 108630681 972927500 440713857 480767742 192206252 575549079 601476869 113670554 230452289 435677026 197553061 810612624 930096768 289255833 821536741 493197493 697927389 297372305 701823863 655323269 935130059 412063464 239508656 270311756 208383796 703052253 384901464 567134437 637458347 991403949 905826398 841372774 937007548 746131969 591989879 992161598 378170027 806661258 907886297 136814850 49354680 172100161 496994991 483373186 464870065 731016057 151970848 2848105 308815797 394410723 467022797 103728594 936931947 369025778 667056052 625064672 739288292 547273752 181686735 389048411 815304970 901765127 152422238 663546339 812249042 420758924 347268500 339365938 879252038 371607099 925472324 315444545 954556094 186002029 893274503 231664542 823378953 669010937 302407278 62338928 911344295 554895175 140879005 953974438 992366904 955406914 847871238 672033426 341596547 54492049 599343635 617850028 676466366 561678362 274443139 176913315 122073089 485040948 800853780 864802112 974058282 452746106 513449216 765362996 936275293 520173724 222508976 145733661 535918888 627946146 968726243 609416039 792181696 100598385 292186044 227889290 900879903 102862202 439771722 880462921 834499137 336255538 967005800 739971670 866748147 738943628 937797445 239710116 883728751 652869558 113347990 724372968 480767739 77703201 580097624 529695517 418914148 111758483 359369368 855524953 352309836 408018253 151975431 915194022 654684073 434993791 11135078 821645528 73787906 567611123 388871015 822173479 419375572 801942741 715755602 787105975 999438102 641335433 609134485 930784962 625749716 992313912 253976977 242606002 955742329 508892166 246740935 967320288 260559906 144161691 389485810 592655526 75875122 68936675 566608584 470759286 536253410 998389909 859405713 736057564 489553230 284503116 218284605 479227819 390915675 890085462 292647534 467246264 255419509 683692314 989522556 820496941 221492944 538558209 948086007 537042468 550434716 482508192 464618302 149371477 433863954 427514645 995497507 822574905 889559075 632420703 793336832 481136406 60757343 50975963 174256516 600219768 419824610 878764137 164270928 45256381 963095522 16400092 527386135 969293066 275532216 162010430 120219324 302515347 353126282 542847420 745468461 173108955 561018951 807097829 635965908 577870465 759054047 596605525 700955309 75740579 447861717 826199272 356511971 508688172 217861960 534225550 346775392 44675205 392338241 231916895 266246438 715056281 589956080 806296942 8715515 443782410 44834858 263732670 780332738 802752325 993325679 780731940 702352421 919840351 150250202 25162808 407684928 932196049 358824806 375599706 14630596 511619987 121561220 240275143 170661960 587406204 526710449 774282797 325219832 332632592 522749548 440499091 550106200 518342466 807868628 11719713 339617331 22507980 33154166 486055140 859527061 556753687 288954067 708342684 363467538 726113069 548783479 268398511 5342620 166517114 618622041 568885646 285301262 910406235 948430616 190176018 296211469 214665973 377788073 747314814 725843899 2287006 883169653 959792254 853886905 389089500 666519916 302763596 478798739 590279346 534285164 116582779 654072097 567467311 931117022 534668103 879785972 304209731 754087787 639416766 115881432 66241920 517183396 93704572 378452166 975968555 139857851 34318511 831118721 871988453 907653541 454104433 844397286 238331832 12141564 694303574 471949575 321503270 216943542 502150682 379864127 932332521 513746260 446570460 126757257 528123712 374236334 646133665 415930505 189033760 642378430 510355447 55054428 542543464 932881719 848205690 737490835 895266424 105663821 794611989 777421979 291858603 303093143 162112243 877860145 633516071 688314490 269728743 718184077 80956235 488974883 279872554 236327660 529415539 233285421 403016351 479557012 874625056 351918393 472403439 509806819 885890604 618840357 159031846 298763468 925876673 945503663 77192955 691757460 873531320 285563946 847612049 442141352 356610398 226479473 713029341 739611769 970502449 487568252 185740635 457800980 32345487 818025148 472906201 376874703 512195346 984444932 728095920 918511516 795991278 319712212 833205033 856493269 116571552 727107717 757755122 382998762 861255264 148874730 321504870 475535624 504257560 118807772 748064767 133141220 346615966 270865231 385777684 384742481 663460841 731882364 335600228 219516754 754732873 899145201 446020721 37639998 189246382 360238213 127607615 749087282 140704086 969737572 264420945 165872731 927943863 713601734 601677783 309767749 822892122 466972966 206105984 570559056 206930698 252625548 96939955 817200908 682703699 164032714 988324901 673730475 906935162 293877038 868119848 727359167 265925013 651423601 612492859 243925995 613618404 26486774 827473409 60117578 981697343 473178351 776540208 675282295 698475598 446744014 118560652 600208809 157021653 248810922 72294175 888942426 653173233 11510286 439382186 508144484 395618385 125058421 23396847 917178196 358497853 934262983 711840323 918593889 600490548 378687252 222838976 523750411 976945494 674438643 557594977 586615225 321356652 921164265 940029733 417615762 983035564 967403732 39316841 117261388 874760066 624036546 762707828 868064099 616369057 511449904 558337629 58585515 786737518 287778940 847692886 709667395 877966496 270761285 85643381 140023085 727644108 240757887 428686101 293624164 554073530 497484937 626454177 410405724 869607187 67040736 587285051 69713973 205450669 743436901 679169360 53832304 579305323 374094836 156647104 152956374 691354331 110539076 139210833 420681864 245557337 543132174 433879797 686037396 443570466 41482523 461906051 420563980 714472512 300467 977981562 828256750 672264563 856648980 386031154 123655587 939707250 66256085 965477082 83755117 47336181 866713009 91862101 530371500 365601072 715366757 806604655 66752347 799480162 645851189 448304093 443914826 899794040 832559742 188307079 131407040 743805281 622968755 404654475 240867058 36545789 404292087 880143074 344785885 492122960 146625316 711723353 82930694 813235934 332404120 73491114 113985470 912468014 632894618 689018008 924336884 964818803 522934778 560122323 206593424 996740090 347583576 141947919 303979912 709080601 898539182 24142833 114901169 561927122 154171734 326773905 637154401 323081718 814820088 158486311 763595305 701313576 235686700 406900303 694130409 284063583 717637564 589681496 222199296 788165937 305614231 38381933 97453496 679696389 778640792 220527302 372698841 674862928 565610005 704921228 944956834 156669401 958185899 423455345 252257183 313844113 332270399 355591873 239736106 905289094 866562845 982514347 25453060 682146545 449039294 173251324 420234073 461671201 814688319 218048254 686372656 664327619 128761232 808467498 449039093 297717205 448566878 834924800 97079863 698810225 655781001 645891160 192367350 901967696 810597578 543446352 314718150 485500026 700738182 48440062 692657427 234606907 652628636 278140066 939343647 456321981 84067306 742879600 933694916 167590046 960705070 94321355 893304651 997499617 288322850 455458621 175891651 234245275 458381632 65711802 708574082 989109629 450333465 891371494 757598378 465376912 713329530 845809674 863589201 221335061 370965911 656323326 891868965 346871661 218763649 815305666 36975306 935324417 488982506 336986565 389949818 574759372 648381716 879457652 223746358 282896535 833805524 128785585 118690767 46590990 683189491 169379836 188732120 596109754 12461072 492737673 488042193 186627638 563004044 938861472 754563773 323501113 464814761 316911703 857106976 813587304 624239314 294959348 705742578 628740041 959150171 787906505 488616798 70419519 933673121 704390240 614709737 479889451 369689831 573515746 359013521 904598909 215986964 353160792 851544089 501221328 470595880 445952347 197721905 823424395 138896224 210011011 789094114 154931625 331486437 174094163 240687075 273483475 397262798 17953661 303309360 267542309 980627478 421140663 530494224 768151198 947085050 123970641 799026873 620321024 222239115 138514292 530905244 980388611 669301915 975331111 227323113 68858407 8724812 76204359 305893727 322629779 3489848 827908110 251841091 661620754 847664661 321655373 865491342 408641350 761393298 871176391 597180099 396301684 526956566 932565943 320051937 413495283 948639375 656243334 585728173 278274716 420068748 384612003 198653841 655700815 567261591 301167332 525490448 451875255 279375342 3085485 643317394 55652113 206930712 389607470 824800019 339477801 491539605 234507982 136904921 489106597 696489263 473899303 468554916 939081429 670609222 681800654 848382202 909215896 749567333 395458444 105563750 297189867 364725905 751380087 757959188 842376050 800820505 359703061 855043885 230222490 931522568 533615932 661427192 522823447 87537578 797115089 159981747 993954654 784624629 537818609 735139217 484108144 347872024 521009080 879466241 532500577 864151058 713909409 993571036 646274131 584154596 403722068 855294186 577231731 172939755 997345773 598995821 176505775 863577972 431465511 437776233 28280201 308914399 861504578 560318309 900416340 917729821 596666008 700407798 203156834 68086610 157350810 802377009 541523322 155031147 968046672 557285053 425586848 342272974 530624116 687586752 963517034 223740869 291944916 636551825 530178085 956114674 323871784 104864438 510105701 7303664 704335069 317523222 163870130 404997594 896289543 456917477 88167655 818580749 465799191 901170167 613910952 937639778 673213406 87283206 424140334 700548052 735592963 17934078 504091937 331415614 279373536 330867604 634246097 281214259 848414111 547257966 721653443 389575870 388137004 278184374 370697599 898766675 298283194 56666395 710876043 186703934 406849552 710983662 80703061 309592168 691952201 177119839 348207271 936472356 474922401 650612257 128428594 681008657 486809093 867529865 741505586 623678997 931875356 312465357 401150058 346160455 885691029 172151358 801269162 482125019 248764972 430268326 505246602 569748129 857788584 768084313 127933462 51350037 324215770 187792441 384781243 87242512 752487978 827289265 766681269 157471436 14839415 76286884 6385498 859309023 697342362 93255548 625359853 846181958 390265765 39806473 197910317 856295539 527486901 830547566 571219753 624663474 756807585 757706682 12101340 714831229 638758595 538389494 600998866 356839574 616187473 203882030 972189898 580480993 141454093 941626792 687393732 749514324 6628750 199466408 304745570 621110445 374409793 56799542 574866945 692551020 385282403 659019309 444903414 852868629 167675775 953544050 355225854 435168652 346357900 159340897 218881544 948727836 928391998 43637802 93604703 758128180 816011208 677819569 245562022 531683511 516482624 958086421 405780532 17520526 399502195 636226787 319800221 653610338 161017671 980673345 708120414 403374249 123166059 727820777 644992312 560777925 905694332 126862949 832549299 837377505 578812912 145909045 32821218 372194538 652060074 637130756 480119095 659100694 79200363 479388850 645380376 249391750 167705894 283395092 504946015 236556714 241478531 786699793 389767760 911121774 614248335 911211669 972315046 390316468 442585679 764207999 850684966 355230067 111629458 579770889 890597781 438444379 893368510 980989808 344350752 449667941 183291582 740843818 223577326 554256606 772622062 369520457 824962086 782264403 365710751 173902139 213828091 26629049 73116199 87077657 313132502 345178939 73355433 925161573 920838968 829108542 654848360 417074936 922225595 601491176 529429292 955225351 211556178 266940074 698744086 694705660 849289399 111633140 165072999 489728107 72094948 675122318 893840423 849293918 27781658 660722975 261463761 578296979 653602594 712227729 381568765 937852038 768996719 250367305 154813056 81128915 265835767 751358483 134362768 776047501 197213332 77445498 741363981 650208197 917737233 705631871 476237357 947362310 238461682 268319462 651683653 583016395 768416244 629759740 355301593 947784207 226506018 948420154 231057543 225398239 265882180 928043012 663923514 357771117 868905643 446279764 750345253 497178411 741091268 692237057 443510017 800820560 147500178 575222581 29609417 988512038 377205751 185139898 12453256 123085562 440681921 360535525 631329466 736391025 310128672 372468346 699898922 598013950 928053094 291933769 659859011 967513540 572022737 223234600 203050160 496169101 414089503 654306555 105304339 374394663 397774157 805983508 367180016 786823267 492839748 135194469 801954236 731128495 617149296 780541718 278692847 758726516 40958522 206527285 91652642 41250276 307976597 833009744 972814955 11396896 619411422 865292150 790581497 666315060 948251843 246482776 371578522 59673515 992826606 25752483 333522373 712505620 484029121 479475772 290469890 845773879 77878805 815920098 197892939 984021574 178487519 103389269 98583916 483194011 637732574 375560147 279876326 499380592 591849932 775372523 945691532 926717138 809284201 47651760 353107085 722295456 320567362 861058672 435791927 73853677 86977970 834478331 975009065 399700741 35991019 519541636 826891907 714399200 784191107 189294031 992176048 643220048 404204307 388480077 183645486 796596663 514627953 305962193 671119427 230267112 593869240 622546744 435530393 658506446 11629161 806694054 485809933 827607216 665625973 182140164 350428915 105709679 906795440 883248128 254466894 930754365 99562052 889607299 514263396 376899244 474497182 612919691 470145590 120710271 739961860 942753945 422358145 84673333 846731407 577043766 181375134 626235916 960806925 88968175 580445614 18100194 921430037 444211008 377715481 365773180 90441089 484257759 698550049 944620722 209303735 713933974 210982133 628151583 628750543 416865418 320274194 952414714 634613641 482075522 136794635 587745194 58939508 130171083 964342348 727745623 9019412 658172031 826472006 146155349 518015365 164378865 506384397 213751342 372474439 941218578 293185472 942812909 75314439 155755408 870667123 140735455 689767326 159783334 936119454 591130622 380124814 488209984 658924130 534088721 882319333 884530873 887085278 904044587 662515284 477326128 54723572 953061630 99660945 882787212 270573772 833773620 415849759 543612658 118344266 755215802 690349015 251067475 416251479 614551014 957547772 521719622 952856211 353877852 537859752 269798545 454995029 710663845 744259283 18624150 319656882 998060401 361834897 965416619 303828457 600570754 914442368 139769599 40616872 857431223 872002880 413625491 39744735 36265602 531533020 152 463927013 897871400 49224551 302213987 107455824 918713715 688144494 188193314 608315874 225925693 418130387 978417936 886351397 567399120 34706398 227000893 571005886 47138557 616941824 476371636 110021791 63723948 328769051 565044750 374654932 430212972 491091987 373821049 280579837 467307606 897660172 115939594 780972926 880370634 826187169 488688987 268935656 663897835 876694726 446177873 806477938 670727949 276649188 501460923 980681450 242816370 546986130 821475136 425936796 434051679 994074578 741295968 33461145 427827153 901024543 383511330 302603862 619460538 836856836 814697507 934605280 202102063 512458158 972798632 899192590 918867941 433775461 731095120 47993057 371002568 370629680 879806265 782196406 41896059 845233755 742945960 961429765 16780388 761584763 287723616 392045134 914441854 403556873 409430044 720678240 938519799 24850416 716389429 614319675 940905397 238607071 245670605 868172268 42357588 194514857 829978535 88288429 854936368 464083915 923710545 157593834 776496552 264615697 632209669 504049654 597587187 963487441 381869831 660974622 895508149 816530396 489577945 79401678 353248621 465619608 187800831 965820773 376347569 760123806 32153375 319975771 575532863 916678916 855078062 631587122 25459134 117840778 451441096 583596375 309055229 989208682 140692389 293978557 519776350 454350844 983567583 187917510 125961916 656134229 287999429 147389764 970846489 545875990 596584575 475052659 259352746 680459417 105846741 553217405 994760151 983171657 174118840 85526680 973405999 327831560 982503913 258060166 154284860 68947887 907476257 29203041 615815661 73852365 131828366 353504273 222795057 411435834 482160183 828126593 927333037 51084953 824436460 37938261 641787083 829189274 776751131 924670030 176923974 780933089 42427718 415240427 835748623 963261628 845459508 775091313 297615976 593200413 401179203 461865221 799062805 899172743 445508406 114588934 670480138 739128358 994644716 219384264 633672096 554206395 905642891 345855688 634512305 695466499 965055005 615059141 139268452 687608793 15816128 255214167 243208627 762283985 488913328 514088432 963073849 809952128 329468394 59297102 206541870 920602120 841042184 679919051 424259406 458143219 958778676 364001397 476350815 914251765 145419087 561388428 265041828 206096484 266917626 627111284 278449839 388314370 853043174 2706686 445589373 77263457 778140559 798550673 685857839 71911580 828541399 108819163 568221233 652206415 185566180 619714740 240589901 177954751 919523251 893651773 263770524 872959699 478879729 533785115 402032992 484216960 459806870 270000270 825129884 275850079 577527390 505912526 267629914 290936727 265487127 932217176 523179307 150522880 692024727 80702885 573948783 631536516 73331867 691612949 907245778 808547847 85965851 798170977 111020468 781382853 995654748 543047650 767478954 803391368 414091525 253144508 896575215 23544629 101932693 883933537 849488378 550526664 101627504 394347616 662866582 762432779 767516386 482337072 355226219 679537207 302052765 413835478 877351406 472319815 397050046 614603838 408781352 676202664 557146018 1700932 838531853 306867061 235386698 963913843 705045204 790250470 567177466 179451742 207506697 219464501 226544351 316361556 566238419 190884183 667299568 793884054 904512314 307799636 686049377 551907301 920005259 151528511 287238846 838757035 224108691 834581177 446855461 285397913 184912762 14138114 314834679 606706870 551464453 20003679 584746037 556006114 147121389 520526111 807710605 823978679 3904384 3191918 44763228 253829854 380167873 171151640 641955606 750971017 867380723 857598002 976538483 892956141 931983084 689549768 698044867 777086767 291192265 429565695 248821028 705912245 87399674 826365807 612515138 667695008 291784422 94620181 756881955 699355310 204288345 512222180 52110405 690728307 26998824 274655720 421318681 735526922 137694794 980875354 876224448 511849621 50509710 405670661 405610761 476629481 792964854 127183244 253711310 251075437 644264539 731043725 344372138 196774143 844435414 28060045 247520895 130196963 964148252 301292218 221415677 1258133 397407309 605951798 669130541 480748961 494349010 927297138 222278837 66175656 253950331 77968495 654103011 261146450 410070694 205389252 799097480 951932515 238811276 723625235 744949279 913180940 25179088 195204360 364736990 362090432 150879398 710937772 896237034 275776301 929806280 765946125 115917058 754023539 647927289 398208654 35506952 432559596 998867598 786254327 299201981 899357041 733222564 139755212 744967733 477823718 463035479 249019196 202569142 900836217 443752359 877666325 51903821 407539769 530282794 965895758 145814393 538703188 423503114 662450415 150003466 627658796 911948473 200124098 885393273 837333948 865453965 325844814 485289665 343773819 400754675 906602275 723565867 982711384 9121055 564644436 551173035 511755668 9819622 252262840 621411849 667707589 526383824 555880189 406976802 79736916 153851644 619054926 623845433 665511057 976644753 855043130 4604962 597845440 828544466 64743285 373797237 179183253 372724844 746452272 63000177 401167259 236713182 546394630 705545418 306801571 237377248 373767773 484170350 985056241 299466897 807793583 179747369 898900331 877768186 244195022 694394343 439609995 994574521 321779738 901445889 716592758 600001581 701493521 454392860 561299386 150195710 695736026 429456050 331922508 720101670 900146229 985361177 337680828 334984691 698152789 689155184 910079291 441339058 488467806 143472300 939951184 715048197 216799335 328093136 900325961 518710005 978458091 673543640 394888096 794422085 978451581 989483097 957629231 504272357 165152024 866807385 681578914 115735313 175378127 443277457 318053695 290162206 788793742 475136741 953766629 175600957 526982566 628063927 188997090 393167469 941063694 189077925 69234935 432187577 319380623 331643916 480023667 961062973 511369725 852726059 64243826 972803403 201079423 531810996 789304482 238310398 378330487 262802218 585195688 916701039 495874815 479271194 279372912 373607236 678898020 819364481 975876590 916475822 311407713 602314643 336386285 38508852 483172923 792331032 158836184 528102025 327783731 86752041 694106605 232930177 138015579 937407643 280045599 198366292 301615698 457312700 120218260 945544460 422202027 715334409 202374056 887731166 529741827 676139616 429118795 858576911 22489694 325720985 949823912 599174811 144559269 583925312 377810718 403419137 33398889 539211265 730131848 764253975 480464013 768519589 964751124 369797749 65948747 541032336 182219424 976340203 174932903 758668405 21648942 97717749 921541712 937393502 85591470 669264768 337111096 426694737 290319473 890617321 998093263 506700571 118980909 429400165 468130841 175547964 919870666 493282073 982303296 517336575 399236760 731239738 194757769 727633277 526912501 220019143 283301240 968154137 212630368 663930767 414065383 153757227 766495809 194513248 419263726 392120994 970143769 383014304 827018085 43638199 972987658 166161331 307531212 458839 4584156 188227111 220726459 600553045 340055550 625619263 832566221 7217077 645719845 515435878 184320470 893720338 119031121 698472828 696198153 287816016 335224544 826174746 969841762 885032031 828877435 56450041 87275275 108525449 643549713 306922100 48866037 575884470 493735384 274703532 606323832 492375411 431883564 884650797 894139978 371762172 100449326 693551327 601823507 236590725 599761070 552750263 928572377 536067324 504460348 338676485 963059498 564239261 889248014 534229006 353851091 501702126 81562082 793553512 266263150 630414238 97311321 199576140 416565740 851678665 154154788 308437919 79268676 902905396 271757834 345578933 258233916 370504195 511839223 797579202 260740365 87172697 21371987 600523491 363000895 954925160 371378180 114738568 86169950 924216767 105200939 196349298 973070684 57319359 417195011 186461716 105742450 816773167 452487964 977186901 129951588 442582554 675687781 547247929 498542532 21211534 846511683 529403369 118640782 124632069 688134789 255888143 171779315 122547315 646903639 876873212 63857807 218206796 821423914 843061526 170629675 133742687 435779921 38380843 206438948 510576998 772081305 326728413 180979093 752639721 339486978 825019666 316516715 170067254 441451064 377302707 262669489 153868387 921760873 141686644 842835172 446556684 876762154 893965830 642405219 891759614 91615888 695095712 628215335 221847286 929786660 364071101 517371896 592510729 281301850 502152934 817560805 518048179 872017113 841491880 162795867 641544900 648488631 202792069 678762327 392696596 110505688 574550761 399952731 294934473 19990370 956687021 276244862 987085948 853056320 952073790 729944514 44177497 96401284 535949490 903534386 586950827 787225794 366492454 229459158 585338032 218637597 587785184 739225972 785946964 373345655 842543825 672573965 398412278 281371984 418584573 144319252 675901781 484703638 612180364 626206736 685899413 336550662 440495858 965030971 325833366 709766858 577476440 310704343 579666402 171158180 334223465 510840152 563825246 169524532 255621299 495058546 306791700 282341365 3850947 568658475 9646286 323724064 645591160 292963080 303458948 979067341 254307433 669955228 162500245 493329723 653082037 362261199 710785013 566529090 620361298 727780976 669463612 207915254 522084912 611534563 113666265 595868879 474372301 4153478 716334893 134003421 595240589 628332023 922615432 138964000 645543449 552693123 845717381 759893218 268419977 964266573 606480674 101418431 162050851 193970563 785827446 58179388 868736814 154157163 432410664 239075926 481229026 622622721 500563437 966089649 429355800 190621451 901355464 924751048 582145998 434624929 117507732 723534160 786113374 324235052 714764136 22793158 77618050 32014126 5470023 720023994 828850626 523106404 295220467 645448084 189842618 798128893 836998807 197644705 895984922 606495211 978091310 107193428 452094465 18664783 216910652 747293885 910424294 500609899 176895412 189481629 462108995 64446345 907720199 924190427 892382257 44302984 874544590 260404918 886491485 878455365 726448063 638136557 278742420 810313864 871879601 101259412 122342084 535059316 589415373 613291961 883219508 616898278 207666020 466282589 782104949 293841817 603392738 766208018 935353003 622147299 698739889 466607459 180569219 881378568 573183625 313157179 816848133 569345083 771051783 871653628 419085849 553883151 245926942 223920505 719549242 475411305 578838071 66427749 40608251 282804658 858760433 751504537 308962622 757189315 774866683 941973025 338166423 575384659 312273194 290531959 20122507 188354786 804881880 195205071 747084287 291259024 282332258 320741688 425667624 868091195 353861791 985892702 194692645 579025020 597652028 800571085 409839447 315095877 848061969 682375419 999612379 414713346 264423122 259929144 186065442 137329183 236429478 231316916 30537382 274846538 453438059 469329309 852005658 981011957 462448334 42045622 42947753 850556023 225450042 512750070 2398991 841811279 392342673 729386850 344883590 755525688 437812080 864622860 20923422 275860666 792283418 434146219 983531101 560740807 900024003 127170079 681556870 348495299 211553278 686516322 707688136 778751781 324208476 670184953 605772994 783043631 609330762 1562163 413667604 604103056 884274646 803297218 333057891 959892522 302808669 66981614 503855599 21027148 646582649 638888832 210584566 226178409 716668553 219672141 268654084 293494916 580438957 540537552 436285203 258663604 491503300 799604836 710500761 967859775 276567430 745643754 323652440 460918528 651713860 978763223 57066268 234416328 358003383 370099360 757203694 686955723 548862422 215113658 511345634 245998627 3631755 629557867 511471689 822873819 674851173 770965926 936848383 987990458 800557561 842999303 254524593 558555743 847797153 237770892 732341191 931798729 19485720 318137518 550841876 613719650 351763323 622894629 317055675 588296756 716100916 25954266 419558726 177789105 662176748 130366390 263926396 184866139 99442030 341434679 387477518 449193178 755710379 469042308 78598429 474056706 810820403 642784678 956820810 345003684 305207010 192802735 962262133 52324127 683476108 414795957 674039381 290228256 977400303 160748023 953459793 904384782 113925159 594801006 164316549 59645462 340466357 929269646 33521255 458844957 484297527 536780793 151678942 802959503 107154567 477826865 243533777 168917086 815961932 670392396 403955265 402560428 859002723 980984358 10336873 236056363 119628060 744789738 620526193 660890543 766652674 55465469 539845575 482834202 214906109 227215647 703938079 274460809 988117499 35038087 34050872 611161077 126886063 658911390 226933764 348327119 991196243 33162306 775299001 901409586 310367507 598597309 530329972 964824033 401368028 620790337 492435720 579928265 758525718 290484810 377189968 539374594 95502882 325955624 342428374 557141823 681660397 130230697 622578701 83070930 74180825 558922323 658850351 331370054 159519281 769851496 648427935 222727553 918827864 490869433 656658555 686880229 60465035 860112965 715805780 192065364 730177143 255233953 391070951 228464665 849156137 163597913 10922449 132554380 577196028 986706351 764817241 978798400 360874675 375153667 384978261 602313553 218437150 519815246 177342236 275280465 966912302 862392507 973511221 963026802 832450568 41384255 511388723 849094275 671570727 140680895 255022178 748324182 69122799 60701405 743197659 520420459 34384926 935422354 410371277 825431576 728985469 149992073 576231563 439090598 914622637 926501994 831872747 624195734 237736718 277395961 276055917 761812982 968390412 224248527 553014456 85539724 364088040 531143659 485889916 941950181 914998397 718938613 967871121 30880745 364197304 886453471 410941762 729116023 219615611 562913168 139332959 234960751 96936828 113319024 702264518 700742899 952219493 988822978 412682791 147864225 110365737 810620342 553883070 676904701 252357755 988246920 560645683 43283262 775581888 995288203 94604350 985131458 697256835 382287514 975330544 604596966 376613519 93287210 943951027 421596228 917159631 409925902 615161279 915146931 411422983 763034435 446921379 731768614 424057095 746195933 770966832 555389038 916040485 974117374 104108968 363454542 11624250 548871405 887428460 82154573 929744350 328656828 245557146 403245676 392477922 423636433 683632714 476053989 569663458 837802849 923598864 672405996 52295196 794207319 170566939 83706268 96792734 292835092 716408161 583550240 968828501 642718272 579599314 613366774 384002048 226272204 107044357 199597410 942093444 516636498 879191338 868151473 738701601 429757869 343160857 284058141 804436377 122847379 625512123 931067675 389320492 33995471 690735784 264376886 714961908 365219562 509048993 237336041 576950242 915052899 961879647 851432974 820872551 778640534 146914646 445128697 923673713 91838109 81166603 751618861 280046176 365316652 39007584 435244029 846129215 468380568 794541160 978366479 648351711 284097164 800309512 344194441 113015731 269254322 490315585 499260087 695290146 6898592 266326568 733259447 106888443 164569784 405463279 223580481 683322141 578206298 828502418 910925273 653039755 107853476 259021209 413461391 120709810 272706291 920486251 283141839 505391868 542178640 87685282 976997388 745847729 575042676 984067734 935215887 559448545 760769082 60750161 385289707 550388487 922767808 659742928 430675171 84088845 638206157 119700291 680554338 693306710 765596174 654589642 705146994 429232610 570309490 572488177 73033805 123913139 875039520 500191883 816673211 478782583 156785216 533889285 24766524 62315334 212091497 567142366 370405097 983447061 795698280 967977328 251579534 199670573 588670651 502150987 392141736 39092747 572717673 90170676 333893217 208423925 932580452 485252831 328770423 922605691 768901436 706492230 715760462 764262133 982263112 204415571 101885896 951698641 363826429 530831574 283765327 362700636 9070116 210379838 722451468 987442349 184051554 260918038 99936792 6925089 216029935 908384821 432276174 5983767 847034921 945249962 374875554 456839834 173720856 523410182 314596068 641658847 912814639 664057722 42562448 525101095 981798233 36060380 101120079 897014608 683857099 744617722 94066002 717864463 213486347 445061330 659403147 833046876 337858475 619709321 50118692 962515795 423042688 110581349 829100461 218530882 845399392 246949381 563408153 306514892 148618006 886075417 691861202 997850105 493579597 554043060 79603857 542759003 562705633 609255452 721001715 446503974 970998582 235895090 356504835 512378444 298593897 151807840 327639993 288687611 905834844 43176058 193799720 910192186 917671226 572000411 615144575 594746117 837654657 624142508 829117957 212512091 756389414 690040510 57166228 756305835 127184229 827153642 304326498 492436227 72344207 521284187 935019891 74112549 71774582 731828128 898018244 91125212 968041985 314533783 513747920 518784295 892886223 735231386 115822594 903790183 753491846 453171503 396857484 193877093 944713338 704841476 395266714 13872954 203373294 993242828 549561417 646880856 165527595 120598641 68805142 209934216 765704257 465470346 551682099 118231749 792463121 409601690 10085247 331477842 523215132 302212947 412659855 607862036 636957233 391705210 639836215 439138865 214730678 904405737 566970554 890058491 994317481 127932994 801943089 760363482 73881469 590850826 450059539 298746849 418827508 722696615 485446889 785693100 280555680 52590496 628627925 762882905 878145297 836197653 101162908 491114476 227022612 333077527 753821137 145261171 834072094 966314971 834727337 903715171 833929377 664402998 724479818 768430051 389558957 555310404 79261032 348961300 553496876 474123193 713255446 757576651 544523043 665622036 976198060 445703491 214021524 130087384 594647926 762501759 70417791 801297501 519742570 155072533 635185240 978999684 141402383 173535422 83478835 406681120 388878975 514748539 405773605 678456752 489426086 662777865 876723065 931240857 338649263 106444796 774248831 540234088 298380536 446161453 896100109 508252502 59191485 270799584 425457996 952071274 346263147 194924417 855786164 500260786 430995286 765470822 873674934 59464934 512456239 913453406 811153448 853068376 296743917 6892051 883812437 210005114 222887742 920733098 484085971 748478312 777127491 941663773 143726065 468262556 799491614 72900959 328301170 813867473 519763579 137285918 676343778 655721333 641577292 624581397 552110337 167837024 394198751 622390395 313446452 860083075 894506448 352333486 451905808 356946902 484185212 426380820 144641428 123606506 82064461 372090802 517516990 480859552 102812467 75875053 239053065 229303600 250781676 271039931 142412691 264081843 146936153 145754514 817296202 475960026 790156507 685875636 719338820 978337923 809096283 324022775 711327416 110380760 281256369 857727284 615470427 441618193 102499142 326668530 407475282 778844313 356119769 733265285 794939016 374022582 927737355 458364388 702228945 574917817 17934035 134690651 240039088 615418952 283486268 429896762 376488788 977858945 600787479 240819088 801509941 136438398 905656975 888420485 223090822 136304685 252147355 797899387 324299567 99851331 348575389 659507085 963557544 689077538 877325906 134952281 353808562 20571451 621498151 53058469 273443036 636837848 793694396 665422175 622427932 10076246 234521705 775298948 742125485 49935126 948620315 691123742 662345669 925841710 360247890 689255274 779856063 772083849 364420480 510924155 304784052 500501719 531286149 123997555 644646746 291220323 137747013 142407755 968896896 592226665 395799362 195699753 25568420 238142609 93437673 892705486 340494447 396799302 590518795 181898501 739181447 492844390 577728345 262909832 238866308 818212736 574188858 518899839 843741774 42332021 306441131 507133648 314121930 35178915 15158421 996540257 119572499 349022663 888758305 752853281 391962342 876893990 455917929 612585265 780846542 604688430 926009546 379127297 701722559 540868203 475026481 324333618 295221167 30457451 810549466 452474956 955706511 83877292 722568942 854606572 340858953 364462298 2779212 842537534 55864180 550200084 507501251 196195796 195178135 192964004 587455871 610808148 797121078 17648316 173496822 718364497 234161205 573762233 399147920 964008952 119634779 667486019 308586598 870803252 477286750 59366181 345137732 917240821 772374566 710021353 776224802 290615285 726047628 592599401 742355493 34376392 604753576 195160676 51523512 514208124 493615797 868669361 19313921 751449935 302118174 944125499 537899246 806417923 187655265 958970042 744000306 754375013 148339032 874170247 519758279 475664432 592343000 582890031 992798489 240017201 966004909 487973928 295804818 276967976 723147969 252406767 233519278 919738597 561677550 720294243 820699112 783718805 306601902 857893547 191756237 903935875 516979727 847178299 140390750 777367568 76108065 584789215 359435189 199901446 343447825 342874445 213833502 954387739 982009202 969353685 293489545 596454694 379214969 635965179 966487922 630899054 313149179 655278843 285406435 59320408 162775820 903455751 893559226 967838008 443116499 354830994 421688022 145801553 148117777 628076654 20342656 807417001 68036553 48358616 75810909 610605490 907044304 3344784 172706196 24606420 794144781 645868464 897591123 909580202 289467769 580218561 310157204 883452824 815035989 611133767 891475451 46904341 564229539 504642690 576232944 170569498 654797080 266040544 630342086 555799530 647836729 840525987 925664523 327480214 128296697 325934876 800130377 971697788 658727686 887809647 40675625 127876428 195379733 123651148 212964203 634938300 811781643 869933253 200982661 780601841 456870417 656837009 426621091 315191744 804449017 903275434 477956013 344393346 495650022 351781306 942911760 577466990 602464949 348788663 588643542 905739512 558427211 536702243 544527351 15672725 433272704 769225231 756890082 525627806 664637501 689814 721309875 700395418 411054809 405884868 64234457 4318878 375380629 376916723 756491214 441401379 916407607 454169183 275734265 904975143 75668907 335136214 395656053 550292277 323994839 428100810 315728066 314449955 32799751 171769350 675282775 841117882 562690930 680738057 603729558 698597611 918140828 859938054 933394470 239985915 31148351 391300610 759250217 500295341 433331198 25500665 707012219 555456726 943132499 71243171 84842129 627464212 416632214 427369632 529536670 284791019 872916115 171338243 720117149 715609229 540329962 352599301 630480289 937814660 119400423 356020811 799679622 369405943 908761307 103817909 889542988 584428291 125707881 922001582 625496724 818501751 222626780 119307314 129692349 588639315 601989155 63835747 46138846 336759070 121517110 768505438 457328331 5285456 857799319 374554969 457160070 163538424 511118404 206960165 822647574 993957191 899456547 745772577 85222163 119558916 455681606 821814253 217333852 637087794 724256202 653645619 620090371 473642394 573222651 465483757 15484162 514888828 479695961 713162996 65152480 956780394 479604492 803498142 978567379 205551322 828510555 428218101 351833836 748408970 936035912 423448752 586095405 701377665 611212724 990853231 728608500 40447076 445938517 16536919 29560080 11141708 854579510 382833416 976981858 519671114 945075372 58439420 731021287 601297596 685267421 226567063 322409285 674397665 51042776 900398820 764303348 851492319 271576871 489461533 328509795 666452264 390004029 938712531 282991058 583219737 137464369 694925896 752817704 271649013 183943091 490109459 554403743 68259026 740549684 487237288 150646548 469735245 175356138 417735143 501461165 235769138 753765567 280293777 319052805 248846430 580615980 652638221 47475388 578384782 287844437 490911860 209382209 150829730 278188342 607083247 934020444 668022256 635027838 392871793 589411644 556706302 884676066 745582932 343350608 875975738 446600080 599896061 847500497 926670640 460448469 475351582 499834301 893219947 732813633 165168576 83267050 733335334 636101991 940220527 912170846 245405018 354333309 371194236 777677481 202471885 466810688 141031543 715446120 120940544 232746494 55669624 968728301 601158498 738272125 194369445 359608249 427338082 823167006 647209644 814615367 627336233 916500109 99422516 114008206 216031772 781775286 370983456 480222670 348385120 467780973 384626078 477973342 260770785 773067522 475023189 4945271 816918097 245640426 373176973 902610590 191065975 352669841 893092985 667005428 939077718 806381927 871040670 78670042 813859829 339664162 623655836 361987081 102831992 180963575 466131590 103273229 10706479 643021229 974943345 533243406 465435205 642867740 621085656 353583158 486577806 138413202 787207867 453975938 369966838 412988876 794739866 126185376 41291813 150166805 95019629 390683557 514070122 168115357 274699643 925182493 134461487 40870319 893818002 442627964 906437210 84842118 729757376 513099315 28263795 797441494 972176120 36233624 833887418 35868533 91199138 466283096 134695237 722787351 452478655 305232689 295946356 554650297 579932650 912704539 918064754 600439492 125118690 313617279 567821549 138207448 436146604 426990781 187377946 160026884 762677249 852739351 620954191 853500318 881133634 20003718 997809008 763453214 606520045 884962860 62545045 543266019 287870421 508770540 979703049 578790413 258749230 453444436 622405583 964713498 911835223 958013780 968949213 167380157 854127336 145440893 563794427 230661631 683288674 568617116 261634075 644242640 585177688 61433681 813071735 868473246 712891660 453860133 556227940 116779543 580282336 98724870 107486958 431089736 884284800 619091726 908306178 260905162 486784646 361631992 542846729 666204143 400483306 722651857 586917279 532500987 568838033 859318143 272844838 294530548 812625398 281894221 287124018 792633358 624587714 472657976 876973837 230937636 819444430 159379084 123034859 307277894 603546418 699073018 541361435 839636812 291686521 251188166 779791901 359768356 37172850 611824294 415929560 312621853 264823489 137578508 898289284 430559175 904771012 923160321 816167157 525860076 685871903 909076680 625914883 744949260 273351885 414646534 723759691 914190886 750668375 992532148 569852387 910714035 27590962 604581777 325697870 983393933 779728403 915800356 315929989 301967247 313998734 28949519 131932764 941601002 448450143 843967818 970964811 682055245 342569850 135195268 153529605 401465496 48623354 890489687 294065409 468266849 349583129 53802136 651225111 452161089 524580019 608667046 682448676 896007888 459614603 688099549 702818314 211046988 235350318 734571454 666643603 219727558 308326902 750792713 901492012 700365493 650318015 185163274 806412930 307354496 711487600 144838363 237786842 923989353 854289598 42335416 950499810 346511681 685826967 198548773 795956541 798394993 936327156 755471707 346540958 538313282 981966152 473889393 158107559 696950590 258194842 501332314 819419030 356137601 751294591 366956286 296026828 477688386 285051852 526293116 348092482 992282714 971192378 501365397 463161111 248790279 80114442 347651251 900645560 633923169 484972296 675787078 871202449 216900510 871657825 377457794 983921664 756364982 484281445 701502150 912691926 941932709 570951223 97832594 383942228 870962776 521810879 508977094 129677197 716805238 128034517 4125826 298316315 493097024 604092099 605616769 260869369 869727774 629483993 858923972 33218895 94560038 463622972 990561692 147994156 209256616 580765709 320138287 452469017 752881829 651741540 927315550 620804585 740809768 425370962 215360668 288822174 947112389 778673921 196446826 736508890 810433161 257865576 390814882 207493339 373140586 831159665 629573608 15268293 301990314 650990376 902829192 789494949 648931755 95855427 32420030 125537772 147124954 95170017 602755561 840408855 544319059 965217818 690050261 920485387 815677041 771831776 32306348 441775628 512689022 484226156 807452294 976298307 543739154 543629681 854891630 564852513 130769632 96171016 417149749 98420110 250638911 560549199 208476599 974443006 876322443 678520226 497186616 983030496 542352385 192750791 138532460 254320842 166080446 939786785 229530078 248524565 965856700 606435717 796438917 19592494 561296933 555064703 499248278 106986828 869824178 899047029 424501911 856103593 788185001 729783492 444335117 521621528 731986119 872761925 68976743 805151916 496963935 497944711 301637960 460390055 595613170 565488926 739946488 814238024 55968687 928932001 474170032 910097242 841744420 477916778 91660052 170403040 68004561 171331889 532986446 404513882 982200722 895620580 645262043 637915361 128735431 19100190 742189408 7587831 738241563 371890539 507675348 265284324 564848509 519546105 764186117 920952860 555606772 993825883 694906749 913422753 724294443 217526674 962090723 239873514 524598769 558712263 877427036 351930125 442253365 651527492 313233189 798375419 296651619 246535637 587879879 983515838 989316425 405929324 784530550 123082478 174119694 499162489 30078425 480299564 109125797 992199689 867206265 816190915 751157312 810569714 301657414 804375402 334541197 991289751 649196566 198653631 415230455 510577933 571128043 337456530 354803154 189018089 141697322 598773065 633443509 731098979 533255074 420673843 533556371 668178058 241250342 755889710 308655832 176279091 515087564 687739981 980799757 173799696 444200654 124029753 267785743 816154734 775791860 183517865 944110265 536548942 980740929 588620899 547639192 723960452 510530643 724744880 109200743 503324133 5653964 401923549 356238347 828234694 664245804 154025836 998274147 424462291 13485424 110704099 646706290 850142802 206830354 185341375 852322640 882095904 964288105 14286466 733922192 773287520 61609413 182378700 110006886 971506016 727930552 86221548 732302460 51512038 423672990 909947476 701684993 538658618 947740293 314217324 113094346 308680566 372598199 252454809 333842508 129413325 372634753 454948414 503223969 870479141 502840656 111163811 439381620 80716061 662177199 437914622 927056741 700094181 465841573 146230950 101336967 152800592 774803611 492850500 301950771 437662932 775272248 41386450 590758418 491021288 275217448 762313075 711543709 774426471 982229276 452414607 568832715 991903467 830024917 338483042 296600567 122485172 58256989 178265909 837865843 868417714 814508058 535009065 653350009 291583094 998247577 716809836 479734008 774608890 172105373 525326951 468102661 481219918 259830890 306540996 337101257 756523429 302148380 405598468 913885006 892304304 305506622 430721415 164065286 526794273 123130814 48613415 275865354 593784786 21831940 503081610 666644641 875689166 326129710 90579226 556999767 376657502 174637081 427536868 699739868 934576896 778933291 527654412 560987713 943918232 24328875 306613953 738229408 738285225 628475274 545606747 852297767 39617327 810939327 769052648 800113101 243419289 65928043 157927596 289123118 996984237 64394302 691270348 145137438 454004324 471749543 249516259 395982051 465351460 501302241 791269085 972156912 250392882 225119885 281357328 168353187 277720589 54289234 720986430 720121781 615887549 111504816 56865501 977131222 529200456 389538580 403991074 138790051 490428048 489484074 116056743 642595184 691673616 491884912 322997835 660698627 451321627 902727461 630127272 913926509 104367133 397515235 378039995 49226172 875015172 841266531 25972027 688007968 66220699 877301814 335814082 938197600 252896402 953985651 612984876 762584023 776111768 735310633 597338773 841667406 425989320 790329292 270483029 394971473 781881900 203216462 482837889 767957194 998476988 125153297 611662111 532550294 745849561 856604408 129537737 49159134 404649107 469176663 337285071 51023386 399102186 382216823 413270137 714865113 77795471 108218274 78714726 57951249 97340406 870781400 932435306 548562689 983457872 371007073 375917960 694226000 730733687 699840563 241229689 928427016 774154351 50447626 627828558 82728999 302808759 757267641 707289661 977966898 67939335 73174074 202579793 688523237 942643576 7230770 228403061 326627549 73337460 613594861 143376672 393071939 146920760 619576864 956509984 691308834 86871175 38506133 348598996 680029499 180679548 430681256 215787686 51836454 329458335 659434995 186667011 97638046 69167181 625078385 548484517 463117500 432439347 485104713 756349621 415751732 22698986 292961805 649104552 969184829 934741282 363134917 301265914 111427215 13015625 863037233 968520430 96463839 412273120 435200598 759275612 644142731 529192224 986934313 826606155 80704467 282022241 362681806 590104745 485283687 167072508 857352002 423999158 174271224 583725726 135725704 65215667 617420527 808938762 550854533 578908406 716955778 252951682 127107929 45042299 254953311 931746782 884935022 143531360 604042645 955975872 673861277 744351984 454745754 716381613 257262396 346433220 40925616 58410854 15030581 534569593 394046892 196928944 43398694 399453127 55871244 388887878 673225112 90034170 956786750 6631453 980786299 810847613 998361797 178597503 936623699 704814386 114770599 317059166 893019942 17047689 566458769 134533639 916975830 663254350 690297338 761480103 575158691 175326173 425510222 296907923 467023661 817509443 340393443 36831443 11926411 433453595 186927685 35177149 19293351 837397353 317223213 388220243 969010223 182715229 314702057 442011867 707058016 186926929 681784963 395875292 973712989 462837360 596858543 300936887 421798258 87538209 34432201 632784570 995607818 643570170 973656467 742901950 64235311 865775655 882863185 456285898 52975567 959771612 674278190 863108956 607312215 444313432 778380353 36057538 531021969 919135609 280057217 899456625 483568426 249666370 167067761 381267656 751645046 640872539 674315492 320217046 737147178 435841700 611405253 925428592 789403097 268352555 671954801 3629833 581123997 865241897 791547036 269586660 428696834 977269521 154585890 94702042 656144638 835701579 96254968 965968923 454185746 763939876 780127223 535677682 637973885 185980799 94446971 295191887 507453412 519940851 475939721 331011624 153407341 898639260 140723974 837780825 363619532 491706799 828220589 168326204 556063350 356484386 444798614 545919851 944034118 906245208 206006606 2950470 288042832 685129063 485485375 79629915 385078066 359854274 35083312 260989871 700458414 851381493 435334419 1042807 254675293 172079097 146144550 865976524 348608086 715636241 592072825 770081227 176218884 820823039 866348122 816000957 843957659 22512966 230080717 510486176 563547083 542862745 568574164 581798256 735118029 601939513 715288415 508359034 781932520 733033830 569573366 688022247 637953558 784157066 484336191 953940017 929548204 979469881 672705372 976847702 781637766 13323994 225407259 651706290 728954431 175173001 225703501 687663728 908085012 420737663 150169427 484032659 791714131 189078861 39686337 378548571 284874848 986469513 475940091 287135528 56822383 528636725 251131614 209876195 101013493 515630710 234529630 636719551 901574206 750711374 451051920 106328483 372695447 735573902 929592720 169941696 295466637 524315903 563131598 151194018 764952515 371046691 861554074 726395971 870426974 789093610 426311778 578025418 198372845 785021289 645525561 624659992 189350493 740115850 618564116 47852377 819293228 803975505 389648247 412321592 594378938 952357274 364811196 895011110 69648858 941892864 71657435 601406446 736675543 677638339 111052999 308838491 599393498 796000928 593568699 443473025 330398415 53414621 109528699 360748519 43823023 26361089 726485896 85101894 204366276 107823683 144611250 695955684 899313684 695234699 614628046 219607924 57827808 140087858 883255508 771309001 876442491 68286965 495942673 603252293 840136802 452184775 858102830 774946036 509363608 505058252 311409245 59320320 897329619 92533917 540729861 121711132 833416447 49001106 966740972 62277409 645490137 730811996 886851455 153768169 250628896 132196415 737959514 310887039 51762083 380376154 877075046 108291463 498931311 863058418 158778504 534331756 830201407 376608271 381185992 929653964 677351535 860290201 443695346 159517863 285727817 56486806 13796278 714758967 693064554 856096473 222350508 899481046 547168469 964984139 932637994 972954813 672464048 194851337 500371109 266487276 683230767 325935981 693439678 985966313 973501249 326938530 792934031 393312717 708401705 256177986 996106734 126096809 144304590 62389593 953747107 102221076 390409194 629001268 56942298 821308060 419784923 71736681 710825922 283987458 15300946 184042416 444230476 88953549 892099606 337499648 729897744 931950495 187797885 857917338 114904765 662672640 82817079 325125244 37448680 663961289 842425965 13761947 459014988 267019690 730263655 558853838 690800405 450431207 705050730 584717239 338999640 467973294 899916792 687802062 268746281 138649281 936569088 418059844 153918397 113568820 467270922 698267881 571470986 855300308 578913901 471095409 852438892 728394875 965711500 429213315 3507492 554401874 6093357 677166735 930984101 408870121 373915845 444997632 914398161 746126361 653209850 927894121 686805390 108983474 831748764 866933868 748162573 194394643 866838702 981156512 595049668 589183996 667476202 196316317 692688032 749156951 392411949 276679517 453158806 320869324 382938971 122477870 108158542 951363219 51449069 901800245 293110147 699637200 349616119 893117916 842896354 271620843 795114908 834281172 681237777 780086544 368186809 205818591 785624147 709578999 8967559 455804675 742660574 144851620 976680566 537328170 576286117 368126121 877750334 590681355 891426681 482715859 578671874 524420260 832552003 337442258 901816921 979206469 341709656 831419838 664282360 739419814 155670261 208283609 522982146 429033595 395809986 302159020 227285827 912115225 824207594 907837468 272072349 484296221 410773311 712554106 187365653 477036481 39448408 873576134 815975782 495784422 531979299 818497927 576789644 708806490 666462665 776740905 354002269 263647004 915333501 694699148 168188912 839246547 48362684 967706265 32616456 650450432 254193979 531740653 810417940 95468982 285749267 607368746 556700068 289032684 801510140 468141457 875273910 872323252 473661879 930078505 13670548 732609028 869801776 530705164 558282555 706917209 206528776 338557128 321397566 883685263 268256445 68534947 712492395 882834794 666696020 199959474 74837204 624862380 62828538 663950826 438503257 849793613 334746651 187900845 805765156 549733814 322701915 106730163 717191404 337995522 626706594 165855299 668174981 487170082 464276935 660457696 632153019 511117412 433127810 576738337 72330603 862056604 313172527 616851090 841194429 15723494 781813708 973588824 336537894 826024450 702041099 141019529 171503498 844479199 659433918 395480501 412159016 792919323 766561319 262802175 632982510 512551901 762259827 534019501 357195092 248317156 166888101 524231956 937026488 952025651 565609392 270270469 472492291 962225696 672781573 399879729 430826584 221268468 340468295 179851773 827685463 500297303 898148388 101740825 640602763 558370198 621909520 741554790 803663602 710751452 808903303 268528651 26835663 186287187 844411956 696085512 40379838 229107059 285637058 127328155 36125860 996010798 626003704 371103677 960846226 376163568 993295212 389921020 356455116 517191943 924799926 774608624 265060747 168482487 544248421 602863651 158141188 655472554 790983444 43272277 254012980 86376309 615853546 346906450 611279311 904673791 657901678 816791825 800625322 589541911 978504923 56595519 274684387 489817207 920109521 455365335 104444938 439203362 421306636 200849430 885799363 283131679 358774131 398685699 167534268 716427487 503986973 547259214 143452309 374660387 718092566 983294108 287207004 853367143 256261259 775457452 462825354 980237592 361438291 301908125 651460395 124088650 50635262 202831190 78437685 25078575 294222619 470038964 759730358 103465287 397361653 886516927 363939561 725122467 660598099 59037160 632068613 907671046 155019262 888244278 567144962 306200251 931413758 757364269 365220546 391716155 812906178 711144252 512229019 875747986 917927852 300739243 798616732 296178404 776377534 631927359 897352370 274341200 401799025 150902697 11009175 804137610 102386646 439065780 169904325 828556102 119454685 981456945 852723063 481223693 994500926 325117342 924399277 103963597 260555578 124175123 967744121 997959531 66911170 964673019 244510470 87446428 545706977 351862524 558483467 970070908 595343322 68810311 255171441 541028718 786357028 90515326 972888961 614158928 242088305 729749638 666315912 62048742 827275791 135815458 703065440 125367366 654293211 87303067 675102819 831066851 451950030 254905868 800844123 413727294 261003988 187071091 88375434 385406995 258190432 46852903 591402969 473087409 321649535 711699444 61216082 3538465 985354243 351077436 781406347 445589539 918066915 290812845 131852580 387845284 660620739 580965300 658002872 709975196 192017715 859874125 956947503 581412111 535888256 168678602 381788837 793487715 142965959 295447188 408805978 524113830 271407172 484897199 241617275 104421450 719706492 818094759 533974472 751488922 358654567 708944560 421512233 633712937 214860802 632510191 305146503 918456523 850398078 16215495 797537721 714670083 471801608 264870987 787360140 931991227 770877663 214395363 465362832 937906819 68514047 435316639 758642860 760774973 315223861
