1854
413547386 908248101 502261296 986599631 367377747 427500372 60179405 826627140 777891147 127519000 581958394 580467194 69720281 527538380 470018137 959753946 545044318 5142715 376443989 732713152 225456485 71869665 101325751 538634737 800216381 246466736 111735183 611952371 685974852 852745522 119357392 82265382 490718512 888340336 319532117 581874611 178038748 180169937 131086140 750077607 894468246 168244657 693802038 155937762 720751725 265649140 177301275 306666070 281418371 153663717 793002172 623295923 165055900 885368008 858627457 309134945 696282017 299389771 774765894 72545072 353732823 136835805 53732981 456056847 298147437 842458984 494149792 653930259 266210101 22086838 181511047 632518437 593423294 294690197 536333825 795984399 273500642 820025347 540447955 700280563 905888098 445040960 900054857 264006990 626267969 688203664 596910244 2878504 887457576 439435555 509247336 261218362 823796837 55042343 604038701 820168325 568696444 857300517 64935689 722533531 409080315 834042274 418996385 252715874 100796521 832208143 131304260 679369573 678416285 116113127 66959213 482947965 312407250 775170173 96205431 880379023 465512207 533909793 395678785 806943412 71003373 780148822 110397740 51507187 42210813 588121951 796229478 478190395 938299305 579064259 530850790 909940747 370066218 243025526 419493525 990305572 2222546 650503478 764962158 77822661 713124727 751700779 195695689 386746052 832161873 711274771 788477620 151339837 898919941 473956901 784886811 78516943 655576725 437896850 121144123 312368073 57748751 772151680 613889272 822288268 292521800 746046174 779602678 482139315 174185425 793616974 877195441 256595080 307801579 46337750 784534603 252210521 391090316 511395975 240721023 101216555 728729675 453757874 387936309 593681975 882042107 818612232 591611375 219935668 626402238 52855363 404530431 623309042 622159261 322607212 395391440 351121495 947747872 488448680 749103091 770912683 897495595 307728057 994924115 490786230 910578529 265216993 289379795 604867692 145421203 129988232 172257516 816649213 693724528 341407579 32279797 254509789 66001284 960143864 851599975 101498627 498909114 517245547 264419574 422941816 200145335 846672991 245467771 561779476 445033448 525539222 486164320 216258377 867833863 543983473 91256677 664623744 427072692 601207482 816084478 477953364 649597749 456918396 701835550 28587492 666178332 678403148 426611138 30451076 341214311 650044784 786567903 343090593 445802940 638638009 960508356 463483799 410596042 839373904 404705887 347349753 995988820 7607719 412591001 410143050 226332429 8053120 821437680 453467185 952042421 925010130 741432193 197308143 226539827 278911333 641458112 563887967 329883725 923150519 614261729 250741567 603202510 429814516 225764707 935768623 171682418 963698252 401811290 799768598 339865656 698786801 136586001 373122456 642133157 170437742 41913805 562350225 241890376 650917945 335112230 488926425 396095568 97179217 575862246 255446195 18089158 408125981 969361570 687193610 838929068 716126799 482325346 747174652 419994539 964890376 501280924 142200558 265879341 726520438 997920799 371577424 896807208 928285949 67557736 48945482 799850688 107913450 789645513 241833475 650649292 676496534 493093620 735399217 355257325 225830593 952271495 724631785 4748243 873508439 442937706 198158773 144238100 394145449 565065877 70915655 136706886 829345382 967024363 334623126 138033799 271005350 148505794 427115624 517895958 18470081 891389423 452728901 908717367 957488721 403783810 673736873 747350688 865608635 307007770 484083007 365358898 448862189 178500616 51726003 884301259 141090860 500149853 44731580 575212028 699442448 198535037 331205635 383050373 768151414 74391592 372825484 332941091 119438091 554500247 529248292 144367567 916901729 199557554 637672580 537408096 64404715 107495034 416981878 385214695 904726171 298417540 641897979 284296568 791531984 707028104 131708773 13133377 208703686 340295930 823159622 831428902 41762772 834681492 230284338 496338366 743434254 798184860 841062344 177158233 889001967 321605400 178716338 486026095 423251107 714942285 798721576 484750727 586192808 448669196 528845725 427468714 667037601 806663721 617527632 678001666 298403185 795353583 655904088 112420479 856256531 722019360 387663630 243837313 863742280 953572368 655876885 901296024 146037866 384877094 735157747 293290618 914065030 183098516 23450490 416727858 537386914 765904980 179161433 182463990 206886983 381485953 534559306 997024453 415248240 145849600 134112613 946093313 845625367 511495490 928131417 752900771 931060382 91863629 942185935 835064085 129199669 956676615 467510458 66375565 757712135 706782287 975739291 67917145 964528443 952619884 690273987 517239099 764631966 191333063 611995599 78222798 691524650 455241704 167327772 23222313 486761579 424594997 824500554 800097653 686930865 236183659 661561518 253473514 267817339 707267024 790932771 468065595 757110115 30589898 221226195 112348892 350403109 418478539 690081316 750680895 573374973 290861396 338254314 522344149 981909019 152730590 635274626 539611903 930661440 744016482 654623752 765813228 785879739 624543122 722533094 601882620 197915904 397948676 206644424 296429016 258763166 394266970 316166781 905804695 693530900 630306404 577266090 247422806 639007092 374691237 74046820 864141679 982040655 992178748 344008966 232100913 569025646 476447633 57320799 848467297 670939605 851073801 304071421 452653584 621027975 106988072 91300944 249033002 600826419 798491212 989796142 22122524 44495006 486840520 75971462 886416082 154359183 20739099 971053790 980866024 516963824 882131656 412459374 404426637 918404739 52636012 781371206 544838978 342482816 100703489 138934515 139614810 497995294 783296380 143816063 502107712 739624325 525438643 28766721 976662682 476298787 34775295 159435481 803633952 374103323 393152405 427873894 743170368 94346022 480116686 649802352 242149479 529103138 196981283 869078725 138639442 445248068 522094107 882677603 424048112 609962194 980597004 273785880 171076388 851234518 197125118 176844339 771856271 862844846 760675187 87740159 155656422 616944406 902768581 31876601 449567542 121051085 985784472 888121381 808407894 847037434 819113798 173500816 768508364 270720258 476034909 146462387 444664370 412344383 334104168 110643032 989385782 339387471 329912156 420137161 151056632 946243774 32385731 511913639 486631075 831282243 361189123 688901461 597033935 543525839 461491238 893513763 798542882 476527270 999852308 111356510 775746745 781456909 495930589 673997065 289771918 772506964 376663299 754568098 78341220 918192794 914407535 60309141 551998263 915709944 487305026 27229481 727629391 971370278 700631321 53381120 695366861 203297917 83707276 195070111 59127505 721097736 41849520 330377222 56914110 354360231 462494929 549111900 357125847 268999029 259186092 712981572 771464546 155572504 170132712 128682661 879601467 581958142 973081616 472045975 753425835 65338701 607656517 563152751 647497249 414955092 843747357 439679222 564925702 187093397 751313253 200706382 227531172 732669137 869167256 379070649 46942296 719205123 36064128 56624118 278419426 71220117 148672234 132792281 391644311 699623015 959416657 762886284 965128242 606502718 157443153 791965275 128318570 944970202 796999336 818048854 244848617 449003815 705245588 935463684 578371463 780163535 332482325 664399802 220866572 713878539 470078954 372276191 592919242 198670833 874084080 369192034 913666662 95845126 172937710 473573431 672392286 868373651 890448769 584300571 518393233 316850478 602291524 443489313 237484270 702114415 604148428 756788969 540906245 294386467 243654530 600225061 888231841 687888217 114546796 445628715 816898510 102933317 810661490 572741662 926551074 670301045 697120786 88129960 930888694 933825089 893191064 543938482 206947310 305697809 840169090 748130599 352057719 775791238 357313851 87304462 391960372 579335438 525439953 686057186 177241706 924831550 153135899 28198498 145446705 958938811 812408112 550826421 304125216 763479176 475814173 12879017 570796621 568502565 611563299 572897155 699973407 371859718 534436611 982493051 891399877 369545681 32994348 461192818 327399580 608078240 518986598 714821155 66964628 960377409 839227253 439051325 917240441 442153811 272427723 794565042 939117002 571173594 656604826 883281046 324074896 51532856 389381542 320209738 493875400 942140430 648160323 442024995 605292556 510627010 728922907 110098037 67950533 763386837 560101429 924297719 490195196 978660035 494989509 780351515 23702289 848722062 551366886 107420165 212176888 351393346 737318562 284899917 539719306 286865126 763955815 194598354 762446087 145391036 51922370 67112645 718037636 591425367 611388690 170524744 996676105 202110137 909466094 402660108 671391888 243161262 346017354 637073018 712891262 902283860 863127612 262052798 278878574 592621108 128156639 134327941 548833205 705928327 357727493 243816582 661132016 74527843 389778297 387520013 20247486 196283568 180221104 16919699 957149972 483485405 328947870 694961410 200959793 910709307 187639631 995897494 527036461 340614602 605217131 424168714 943613603 110373880 259505924 215257423 543035435 231713758 976959270 503402597 713075297 452073416 243041908 905932172 845262904 659018913 729009920 970177396 340292968 586333812 295688214 607569513 433387476 360717628 609632563 576511071 20915547 491128537 84539482 805453310 629322476 362699003 518346688 562979846 972255203 321858141 663530783 94266472 956088275 476517256 358215547 861617788 474583806 300237297 630748463 301004707 399020251 513645980 344011420 996506055 251069254 69793415 907711908 754264910 867322451 974712600 820406851 301409553 323658971 62523212 265238498 794190790 909388988 687772591 953926292 510219119 384230352 524440043 130245276 660280709 894853331 628791841 498523631 964911025 182691646 921929131 21387161 903661696 406256787 641592676 452630284 180517096 203670994 188834488 465466323 585632992 847790759 870460910 230198183 125002218 982300960 674129150 38843226 52247318 915093874 299021740 408056440 477954155 732603218 656087103 5428749 533413970 205877219 404496498 99986650 588338467 154885826 204225845 915225136 626709689 315118597 563250318 120853751 511156163 823846361 255652285 992553973 460180481 115954238 379766255 785800410 219056488 956591745 836776572 820299691 104459823 564029492 660131756 149805178 394730150 528337111 54232378 787053670 562817902 403521282 433037984 167231373 935847497 224809574 694851446 232914132 83755200 8820745 342647548 243443574 830574095 715000697 554251751 554777338 23728203 301964491 99220213 633170993 377873540 633294816 497919751 420927567 16142726 711703422 605341482 129807719 961709798 561542398 93991070 253865462 444746404 569235031 837670859 511416063 406819180 170462734 477462199 816085658 777531203 878156237 792894587 163361727 680343803 555199796 682529014 609481261 593575418 473852935 879814899 777773923 22337540 507780829 615040746 689382641 414626891 617805381 281420367 917220836 602584966 758163478 93352869 579793217 865391894 719184725 67115274 269653393 397497917 799752145 618121020 900655315 520530262 301230597 25253401 197102456 789872144 991180806 564654996 994157771 130448349 305627111 782542869 245591430 12345055 755854024 977395406 470080824 537905005 77406328 920371887 959236573 46394705 94800511 752216768 231505037 193490355 164592066 161453782 776145037 763982375 875101630 216802739 783143490 205428885 2887716 354720046 21032595 539936516 815510626 88280811 251431454 519801378 550888698 496760238 747285679 428580466 491255184 316882790 95588780 433042903 620664756 551374420 774114808 68320515 895321052 829657616 663591805 258283818 296889940 299089524 257413133 272740205 601546205 3076460 949253897 666115999 497719599 771101898 788932900 199530451 529527144 302983279 643011217 669196111 769122940 974820395 576049672 237900674 577200155 778943423 136755847 521293076 270068353 891433977 851493686 260829634 587351756 591148204 898055733 161114685 270224883 9033066 514527232 569226517 819916833 587193750 934772737 905277174 446796800 238455160 711837581 521108980 788829540 753071729 313971113 855916553 65884303 877038906 387596914 328761735 695693197 516373180 663561981 365913604 924110384 517459521 50554579 336662497 808135619 390834475 192300644 55584288 113254173 796299863 524693579 840809356 918127360 277868044 272391141 860942988 632117501 636091258 129924635 577572036 525300400 640488116 502306333 740473780 532509405 668367441 843058726 664990635 747869211 726080488 582812287 897721025 551337856 842493016 47736696 966931173 738652266 309375136 319670128 828725839 215771268 242645872 133480462 585153668 689767317 795837370 251851969 844512224 85153017 547560998 482325028 295975410 623060696 248825317 856929242 821367802 690824581 532657163 880769288 544047687 630680836 320020421 665224803 945785557 198960119 964291356 177397745 812494758 145554666 398162776 452850279 821938705 291016153 604516917 958996840 686779356 938832697 911485897 497020137 379133148 416115296 36013660 380922212 342392892 923581368 480234369 321701690 646861231 784814950 941763283 729232295 466516785 645420498 756959319 437992662 641294778 751354024 592582397 742096234 952225502 567246046 56443992 359600631 659632278 950108589 867078608 804988673 903025944 178976277 313689418 191631771 782120374 710600575 87650042 148518610 958439257 115530266 145256132 498846780 842132686 40120294 690078447 4211549 39523233 15214180 443995198 93438734 247308991 726673082 343488411 309298485 861908964 317789623 234082280 301106077 106626196 50559026 549096985 458277477 632285986 143294433 577673856 616931230 316132154 226437672 178815406 970763928 889491418 429729391 999945072 128481151 429409678 75365172 360659010 766140736 669474400 176269623 34781828 215265886 386338035 227644606 890150556 948306502 279225534 404674525 455399566 931574627 869206054 559591042 876369851 616666225 155825243 915474893 451924992 821369834 894118105 54703341 811260192 2963348 660267498 536263520 186118128 841727194 16632925 123207542 393308655 470653888 531322643 289978133 397475213 20077542 743110372 728760323 44087372 998100089 168587119 468658831 271173975 74557731 632555323 581924052 514999337 152072560 831251425 840919213 545957568 486632936 510982081 101265905 632116784 709292658 506989102 884915481 654542638 843582479 681198070 825409646 92312988 858104803 752886178 80277295 51309484 278287652 842813231 506057637 578897981 750496329 936865030 141163423 477062284 565229730 105379535 203467082 890992277 133160230 121382637 28339598 712153981 437930140 811103839 577195507 813200776 437782299 959861726 828528857 688242497 16828888 969786509 929209696 830562181 454502681 79556027 374543803 911594628 420023054 660944421 772449638 410236089 127366913 545275520 874600526 252110914 240533438 112222742 934216322 692676014 52632418 788284516 488196301 197392032 239804570 337906726 726112759 501254025 208760462 14434910 736410335 399665949 811454542 135806524 594116988 589861176 508712534 35309670 910207253 311517253 192302636 90169415 332493392 909352725 437325082 294183881 692245880 790944089 121629737 451416908 525916042 205919129 614554490 860971553 751082166 172998817 71323542 948751425 453370575 683382967 936628743 360669992 471364693 804086865 544762215 749732379 865875231 389096827 409262390 362560193 123290091 890081801 934208342 699112443 865004639 322431118 961372020 97521782 854808252 929846769 891476512 148110124 530044202 271885090 952548863 154151083 826877072 861310952 952879369 834317105 166630257 453899427 201420785 488670944 844727871 443661774 185973179 959479878 320026601 783321473 298967092 728585075 814397603 138243393 247138199 370834951 946645543 937412263 856093872 408123655 446116847 447479138 296290687 608494703 460064185 842097197 27859729 790531943 992147395 338089011 763949312 129422088 142903413 236033895 514974071 774512885 142525002 178077554 684192250 308441958 411775492 471805644 940383387 25809573 813926355 241462584 588410486 482683414 922452920 896602658 384553030 6604935 376483664 515707280 178448349 9496061 886536545 357807982 400235483 98245334 45364903 743002856 801900686 959709340 952650783 362250622 186438364 269161517 84998940 214196729 607340608 369759852 979464939 390786675 114351436 71691105 803773173 571462970 899627250 203229594 233281528 781960027 793658627 398119948 981275424 604835014 602065530 756436424 589483040 349763507 986388373 151691735 341509618 607021046 481678415 548887664 405938944 410027334 782359748 914841410 491151472 459123992 621281350 656611639 194506029 254153089 531058472 127468752 104975269 580904707 867573203 231290818 131637473 166850136 717971371 21728341 434047509 709356824 842005585 282914889 480137686 214502129 498995422 774177666 627703038 337053917 990634458 967887360 654633868 624889062 579128328 25684028 761485583 548456454 862860892 813728861 504383451 455253594 300989173 346892537 771589803 65723111 586075136 601237236 879908841 536559480 6974510 652278338 982614111 31992627 652716180 322535678 820072388 812134963 370088337 546508912 271430907 989065683 866164530 6091671 686533625 283713870 70656219 459118249 281409877 504852268 663213075 682915268 51633471 134463551 798138857 568279548 493245763 541068531 42778703 36307790 437806548 44334296 734984249 739683763 891365745 553074824 926211799 754761790 765229311 459073162 163927820 27697071 474032560 606176059 415961611 384531323 801697123 698614192 905029081 808994715 369501650 44492400 213970310 314416106 876642901 740214028 606952198 942198847 504522746 493472402 867064781 384909329 317832483 709790941 90288924 738175425 627957367 294017360 596431040 552257640 801252008 171332209 372224310 2242239 957795737 772098994 158805127 772019228 822224514 671665249 555389674 59453733 29242704 590525470 789593632 792191855 792034022 629964301 330242476 526953789 286456514 59875107 19543574 577962721 365842697 687866032 776326934 570260307 916745949 589851239 775611521 919477220 244903568 908980569 652184396 134778377 975143568 267038249 646021080 834811892 106138255 350938158 435380992 172512651 479020753 882272309 174020283 611540632 216222483 236164287 740118472 561508084 993319285 560735780 510465762 620120698 472098877 614569999 796491061 324595889 454547967 118407089 699798419 414942436 943761592 264897131