13798
31931111 252400077 211850302 883307082 970618707 575059 708479576 466460173 645179258 530883724 952328793 671155587 459529030 63173299 834166814 437165235 107079891 234942886 130725752 988684279 778149417 354142275 440353918 425979504 774294361 520369405 246927568 497404875 68597530 696143586 142718672 953044992 801060015 207085325 688868425 771678721 60176735 397348000 90655245 705355992 780748075 895500389 376511579 240277105 811190039 63194744 529958691 918269929 298137629 513200795 906954208 928803397 867343069 199824477 207299252 494153781 572710234 454226819 991558655 641307763 2886757 986793679 446869106 803946771 193879003 135737531 428141843 254055738 385601882 371313439 959411729 166349957 266813827 188439659 259143413 78003866 104150754 789102103 848790146 402288382 302302897 608260705 183608131 22162317 808085182 390907382 516316097 233311767 845134201 507874752 874619529 700537309 347184782 174004986 357000431 541063784 309742516 785142273 647635873 695344398 8972063 459563954 714210706 275785889 648003612 973354118 206306106 752154366 762456220 55096252 6959099 917275469 515873308 190567229 939437785 176474841 581474611 455753882 409786607 279125163 816144985 136922487 979662471 163329766 310927473 189179253 556909901 620669988 974321525 204545774 168530737 983293587 664109727 882741442 111595827 164629690 708611911 170418285 769300407 323584483 78030888 776259506 240859951 593904195 819343086 32814087 770379036 253334048 488567968 180165642 532459210 157229304 317088129 364638032 320559069 628015601 553817284 877468970 101201940 380655160 934531095 122249029 216465098 451157173 4990470 180577277 615786862 566118733 350995561 237603621 889703215 429026448 13863126 130563165 22930642 685722563 15893603 793309677 939056611 504461571 825991671 324032172 661690874 143079799 688670204 834766295 623611751 95003839 564751616 577330042 328175351 499282710 699579070 544640448 950439882 557085892 725217724 418743095 123204624 76213284 656346715 12907838 357756083 522726192 995987354 380686725 60965107 11880956 26512753 21717 368858878 852504423 324053888 883066104 848100573 865240443 717832398 324228675 960244282 135100365 901558717 140935984 634383074 453654138 685576431 437339307 10740029 263310507 708598753 133944652 192040142 217461820 999368841 549796225 740188011 847872546 782999301 801153117 712269854 809512053 653691185 933645083 514532828 977745073 816711186 215149752 695501867 387059935 391894779 508262500 522160299 145969847 649198483 9059724 599623984 187291266 298915382 610364013 450601772 7514135 596825016 495158265 224975954 448710209 44954489 817680316 149099106 680470141 471349785 713885311 342498546 125040969 647530394 857031373 955302393 316757931 924697476 650804260 556334218 316592254 11583111 78494516 462562100 660781594 940070592 62186084 848072859 238985973 525066448 151190982 99016459 974407815 646349246 323992412 275634375 543820087 141672728 424733481 224290227 465538864 138618791 566788772 590579832 638665536 276336496 398398577 807939819 53550324 49202836 364274036 370142577 60785946 295284903 685221029 574083891 87871846 599923464 422156749 326857819 124989911 573347730 425874277 951914077 72213328 602383041 227548452 616033414 596572120 504798284 840323640 62110983 495933426 259628764 505207166 134598962 388481611 903605742 795055132 442031934 805324929 11845519 812174511 718627227 307130421 349911891 292711117 395002267 949835354 567384218 574376437 927341616 140731947 250713 879255692 65461626 455150105 959320495 681495039 51722224 464118778 374335031 113833206 960052204 633963794 471556724 947167517 22445404 375162465 594739000 316993690 33003746 606584518 129168200 751630972 913714938 331596442 44342088 161233556 281431795 464242657 735609992 61289762 457490956 588377057 940545453 522952581 43527161 752382300 204447620 947765737 69017429 578782650 914115294 29069632 65262795 385672017 828753500 940224550 613350834 276008851 257218239 646354579 882593368 238902790 397985550 648824658 570499231 294843989 810058213 704447377 759086646 398184557 765737138 69093953 839077965 558798943 592046533 735121477 311181242 796494152 682887213 380198670 227793153 449518859 261784654 145572299 835190875 943054505 85796849 301058060 219063356 195531439 947412638 101656723 434434229 197914539 602997732 857449811 492758528 265572297 561897188 104361525 663756853 180150677 173455477 355351169 738949619 765502009 90472645 50130860 414512513 625876210 282845882 494822017 75395068 397146887 640394316 763102294 340201391 726191164 64160354 411781098 921722602 11572991 365954173 208673182 62003882 968951904 66122993 554762409 234524200 480536532 511640285 750797404 660687208 685095761 106148572 252153179 303114121 49137569 154800390 570142985 675013778 437646271 64965002 750408845 834793157 705359317 366027490 27510900 284066832 430187843 439291997 58305785 294277186 805246169 119495319 356281067 626714425 38134663 763559827 861238624 518671194 275200111 464552380 31874753 812812223 570700951 284027931 115926343 619838519 438828321 538585680 147368648 728990943 603550681 897777492 416300452 161426349 116321334 443811351 298009532 546509176 735619699 356315316 693302713 393382220 475810634 49583779 20096644 513945296 665659957 733851619 885132841 940860067 198403998 917007594 606188641 621621301 53551876 574631336 93976171 344896548 113217015 241344819 73887491 569284047 139122310 490187942 730710395 107959995 786515644 28719926 654469171 522135342 237551593 200288235 915517561 565878579 102388366 788130556 79823874 768048322 521982175 817473067 561424741 572902524 586997012 167613381 194523824 640548887 742244716 288499995 985445435 707978082 529844813 911849277 277262128 521483474 254553570 860488874 629443469 41069213 741725151 136428991 415720906 979276744 336717225 183754819 397671674 439105590 971885374 330011899 59670264 346383900 147484965 621095004 919286424 734481976 788708384 113810247 227547215 383469452 254826593 65509001 91447533 637187757 977358277 221226013 11187583 84428198 81714886 640631051 125497410 675956389 629576393 541218315 507749484 966293617 724973133 905421157 257915559 549374859 235433055 317585822 895758758 235434372 938680825 815045181 969916347 579905560 781371780 49979913 815891363 888714724 115488913 759855248 525902481 945363541 981081260 537090063 29791738 915312497 30237465 7805499 443785237 659813857 401540166 951534720 478623825 126513298 856955876 589055735 528404508 944905283 906641556 424163266 180339654 697838732 91724798 2772352 130260644 725612929 52752265 946152006 614327653 20757529 558523605 992746485 818637422 392121216 382352899 700945511 159950065 412590363 561267362 603735301 924920571 962807527 555270021 256060747 941837176 264742248 845116482 470241684 62163882 604274389 746921301 242503535 154629473 838646098 97792239 284890116 416775379 3060855 83558473 31103031 23818383 642082078 876365867 694972156 34203293 258718765 248434019 46669709 523825479 809701380 650405010 448746049 625025258 58191382 704806795 566862433 322933629 402439628 889620468 385097511 6714017 636541768 480117397 161343489 327704218 577909635 298749956 744479596 580970489 382308428 628098978 457305224 876906857 356981196 4793731 763626502 615699960 253227749 810296210 139525438 915445480 460701219 440787838 540470737 518892600 998110984 959849522 694342581 400550612 849469989 79440091 259780980 338528109 412073839 421124468 518748678 989983474 719874423 115744625 570953962 954699202 743843602 28259185 831606059 100824797 33052916 447748912 569041108 138797016 258045121 561082897 54242496 571262692 854387086 447229584 90155291 852498069 259595457 637014223 105565032 109065446 568970665 365346011 300109906 981044504 638986830 818858583 971027977 211377604 934603207 394498290 166076806 530963160 275273827 850199216 484304308 160843094 297948127 905861767 152156461 408509599 319461015 58915308 979772290 173848100 506144892 922443933 878862520 765740348 559458155 984427552 727322145 128428820 202289914 879948402 961989675 841276744 551323336 785534003 52654347 338442894 32548644 71247504 869406053 307822470 921446719 206226712 321181915 71911197 112088478 473338376 480420796 284065844 532253683 312709437 457913943 38398574 235153369 189292815 656655274 647127876 26236718 236493770 628073047 228526631 116442172 590062721 922319726 520281859 228113075 827490425 858724753 260661718 898737928 580647157 568484188 672700999 786873869 889666102 597128547 751478698 215520829 77549342 35544542 747774512 242775131 345974836 638689437 477928499 535267650 147861062 125056374 561504367 384354832 605645772 642547350 353313355 48224844 564867075 873595213 276337918 244873851 584836317 536999636 143611779 165483474 105483823 668829129 804873694 847666276 118474027 408868743 63187105 48539721 296929636 663477968 291314851 642904472 302167404 769243349 30688473 450028466 746816075 444709192 686899649 204978198 87256541 40213003 253203042 504639967 766324567 529540959 749513818 203677236 66540594 745641948 369160709 24540768 266987428 26550754 724723396 385461454 435419496 640426852 434001174 732349132 303904819 725316024 227769955 458588574 347075725 258458427 908617039 93891799 703167618 448033039 151386348 642940510 340762393 404589389 147580477 107086960 934130348 897094294 163280547 670941 495252593 532441255 877728061 762240020 558992008 602451456 147701473 994411503 95394659 581702647 579276986 399299477 159535022 807046940 857888050 506610746 65505367 619021441 453018896 621189336 67054479 604405244 116646198 260333224 8994632 264226674 219936535 943124979 13837319 383217081 796312272 509089911 915658335 526556684 123846282 327166694 129008139 271547754 174094548 76919149 705766752 753371534 476218625 865301774 412934825 186623026 371912519 330956543 658160818 824931415 952145879 577731649 281853010 68792076 838064872 290847641 185535101 58001406 86488972 51888771 441218486 735317595 560978681 209393172 261874278 684824962 389076217 243398768 808889067 563170764 320317916 514655819 169058649 649052892 232473944 581993474 835675917 604386462 912950016 346353087 281834228 717612246 924084735 563687237 638920673 762149606 707051230 676972125 672667363 793540201 728860895 113885848 381374147 142355927 175795371 643248424 827180888 564871587 739163543 488586307 980558702 59481458 3242125 2133703 561050701 88232420 584127176 249242969 692618881 349593543 595596055 826969461 919722141 519680789 243173049 411159165 134346746 950224278 88131290 807014108 596280830 816992184 773416307 977654976 959348111 801728029 473419751 639045350 219115967 212583293 127631656 199674669 124581102 983390132 201808371 685631802 71622551 638451898 934874771 616757784 988045440 382987177 296243596 760283932 902667966 539416644 171443097 889531063 489640922 112090738 549061523 85921751 929082921 174994181 916093079 740947383 976722210 389512829 232509085 195838176 454612474 212657092 248029196 579193575 48563576 449837566 117341729 972702478 88289463 904732851 441976613 928851255 287720027 738220208 541651538 42904344 277636852 713094634 932435407 619794125 825185371 334013281 558232227 606784644 509007461 474325305 200248378 485729670 716354486 285273814 534084198 170966959 497930906 782113393 602676885 399010833 84467311 720018613 371713310 25273125 477267815 813689923 954124379 764987842 404426482 348292269 660408537 682063333 61386902 445360295 154373809 739088625 779373575 712606036 198389620 288381036 39447692 251154349 626627057 755802177 536428163 160711254 926769135 34359068 942824647 381962372 285886252 27291957 101980984 657599561 52565081 431765151 323805835 859205812 49269344 728232317 60014432 709677880 262812001 121401333 155038175 417185810 713006309 934411749 129791845 763912280 75309136 21755888 15066629 701936193 777558065 551494791 715163798 556843551 438370210 510504796 938805922 724256461 390313104 893303258 234372373 295394537 325068408 410694560 7116700 374337751 138926876 67131131 84015630 254255228 41048815 91570156 523957389 754055124 878498257 506265585 370483755 953807392 528021473 385550383 508259936 305579537 789561525 75940086 862423087 80448086 586444881 653745361 804704546 976757985 547048618 891593271 272152521 724633377 302287830 279269220 98971127 293731057 346400350 35503108 400502636 387449164 979589616 924460025 994020639 858087872 430725609 364504394 664411615 958747081 602571128 25187903 116842969 392132653 101127988 831782408 472580738 687572868 485527768 129801636 516847204 885092737 21394906 788999724 609726113 176199087 920785295 561213591 322446495 119701996 449233050 722949130 507151160 281339017 647409154 353688150 139426888 930651115 718192543 656354855 741914547 173280023 534059109 858757516 565412675 635187096 543056275 890509764 175276315 28584042 20311399 692123519 766193130 894222656 333639594 228435594 922938094 106941241 789649184 245384588 226643236 91398585 968333718 733794395 372737602 468259223 87482545 364680841 251426689 658191439 873552047 993341236 831471461 407611155 704615103 249400487 895314602 247671377 139910251 70590917 128771770 12738001 615230787 894964899 759477009 801386732 123400492 534931454 908327972 765566027 780316042 134971208 709480963 601166111 721281954 82218564 921941685 661280850 299415757 173368374 171988641 25484155 19225961 3460101 433095310 723841063 105376940 180926263 971512439 97803542 104033531 952800560 963057894 719264317 700281810 575051254 373167401 676198653 109982708 281495372 294281031 742815101 268982931 3761993 196497563 990264885 938496909 118439247 651545734 90429017 144323972 823534374 115913171 163549932 679510827 549008480 887390994 637404118 729934743 711419784 735207659 833968273 664220343 550781904 405748942 217018504 125833158 778916342 893217156 88332217 912928065 187498186 831147317 181910996 43776531 27644879 24692232 982273439 146084125 676237965 72702455 142924449 352288691 188615625 306474380 884315869 590140457 193865374 521719986 172591551 905285157 109443996 6559823 422021852 660225899 264825116 639040355 638575408 896257809 384773863 726907624 809185874 572272048 558054940 843613221 616048578 438216170 868305452 450838368 436816647 397059768 523540822 579741095 749348458 564672799 886215474 486180678 154813255 80080847 7900663 327404805 837882356 969861010 186480979 112420559 482603261 303822447 603977265 121178668 200080255 988751127 848086292 861782480 413539527 258657583 705395700 29588104 696873753 426217503 332942824 133690399 823277271 856483645 565947845 425142080 273672795 452163318 911322758 428486049 384760517 771739772 608407205 75159224 741600782 794888184 40096134 76720394 98710630 644073398 197899061 151307236 632824525 898501704 13089716 46364051 9675639 571001767 928468506 706549391 997219270 113927681 692756141 673012892 970411326 111220337 98154971 96600472 563383654 9477728 525086521 800660522 633733852 133493725 875819745 227850985 780898260 915915878 304571378 732125241 412505628 502470438 735948829 45330152 253488494 601554896 944210554 263164132 25073014 725195411 969713522 22292283 839123092 514986014 547821526 662050769 626206350 645976497 758651240 42106355 507970576 136254112 842766877 141704427 122264189 571102973 222071763 755678800 339535203 526643140 340320393 752040830 29113578 76269221 649887333 135118423 677824116 446614238 398282554 702897129 24326000 220512427 577705764 715965443 735498440 125527289 230532563 214221141 624020137 989183803 108843847 984507065 977954266 951610723 978727843 100218454 375230048 200799606 708413606 567281602 727442745 48733998 171838783 609072674 125003218 821726115 744191096 655343685 120856704 142473649 210757165 145182703 215502427 640979280 713664498 951000866 619022921 944197060 17738358 95559409 785897214 126582205 80066473 763851480 930709279 58794316 716586285 158455678 112110273 277516242 725737279 692069369 326250239 897576061 153658395 303769808 571818527 897849490 811629844 692675230 892839491 22387009 690374285 108341917 515882640 256555134 911859135 134905560 200752193 782113844 230464969 986649407 908696048 163047793 603017238 691921679 74358460 172119874 850377356 186468732 449636116 576114635 878538101 628402706 326207047 32196495 932172514 898025574 782562336 596318709 443217155 527918178 471222069 133591439 488776447 987104709 242662924 253151933 122010268 443415117 35265776 204991588 282580875 796478176 368039381 738114464 340916206 442397840 910234337 191293561 481382924 212386804 619924547 212437376 840789510 946131594 97150222 625478375 844157167 879712557 74313435 139890673 260147087 545535504 125998464 601439885 532640212 368661387 854591817 507166831 812076503 742373944 564674771 947173729 391368471 932714151 685288192 732284676 227628342 448038881 776094589 709011265 512942036 396019135 921448640 206247897 194667080 18598861 831726271 38824246 750827770 906039706 31231271 863491208 304091561 157229734 464931092 836731772 525891120 172039260 196414954 190483975 766929555 761089724 137657703 10814378 546320226 675462247 743099053 626464920 123501127 371709993 187992536 488959514 767729128 109441176 695207411 962396207 980556388 379450033 853736805 583900509 138006090 884968075 299908068 442097650 42197808 764839159 131345773 420605279 789394770 327760727 611089253 556324325 941366802 748746956 567138702 340203380 276725554 162754106 966668299 252743032 534464099 154660834 741702545 154709578 116618361 436909955 969622136 949691101 816359988 675875292 386107961 954366077 413359718 686016029 248980079 308073877 303371539 380325851 728679156 92766309 708086577 339768408 501606985 501969731 941031715 68745686 842173110 217757268 84016143 808841408 470500299 470996593 816018593 64719196 625706170 932636954 501629150 447844658 734844406 170505489 123719949 120952366 977387918 537079667 806968394 226367996 845153543 110339933 606693846 426349050 55622593 167296775 766117458 557229577 669266505 559665524 478491614 363955966 777422792 415024108 25313725 100439442 886020701 841332317 165158637 364243222 626485622 519304139 812087879 361330027 689809627 935807828 334798745 519713896 325403846 141767138 746081891 23073740 104623422 205292089 449422790 12762366 225105215 68056599 422508294 894371719 627722122 900999907 110844036 257661265 168540367 136157760 210617059 54561067 977490076 375775695 418804288 603975698 895079833 83408519 817822076 437405812 19216346 152620820 957119707 197136543 146904310 555717950 72726634 104044083 613526390 522149423 116806449 838631604 442722373 391831094 585519674 70444495 145347353 696363709 180622111 313887719 832521468 391239169 368448785 810011543 619531216 639769424 266503592 367127400 723177942 84325668 804533211 594910639 89462839 614169270 792047181 88883500 22403571 864773815 192927583 635929960 239439589 162250383 327077915 682161962 554081476 912597588 605122808 699428828 608961296 638261270 13316546 293999115 29500439 234281682 104010657 501548006 874051106 223030601 868675405 449745399 159872620 525724968 44656038 101851810 139894237 689219570 190735310 14814159 406509736 383662892 503260470 645949325 398429626 830338384 180627638 952511101 742935971 638266797 504456281 204413618 276528066 370289178 498412732 158544856 457087212 454939740 660092861 183654669 530486692 381284618 633400067 690359311 907009585 678056104 792211121 899420173 219792026 982946430 914234331 626301761 219125673 270011152 124767437 617555298 100349535 305395074 422582750 695801857 943661870 779555382 900215474 72706288 2360912 251144557 83767495 459448123 558600648 743860356 643102791 89087340 125144973 276502857 631963002 884670909 807075313 276690474 784091081 26867338 112153255 550841763 653169098 331278927 820852914 777936535 801350576 773718800 935847960 76449678 469520656 732026182 856005059 222252481 804732469 858365970 325913389 888499963 317814092 884514036 484876670 960916882 973601375 462537994 89936091 458080729 199725254 897011403 734771202 983816334 776395092 846924457 387174448 282080541 30719735 60543713 60017075 832070311 834262512 848381387 908519988 156299519 580407568 764525046 231068351 237656388 475407368 556981739 978672702 793221459 441495775 316065724 606654693 267613501 778603717 549107135 725694229 978328971 298634889 312981783 814661656 75029980 159906239 54352456 357110520 190625973 114896168 269643947 22696283 801675032 118025333 783732622 810490902 550949252 400774020 41559253 641121991 876181387 598540991 619794692 521919197 892553117 935860415 128573889 12682970 566980484 530197375 738377198 397825806 828832263 51358980 65003813 903862242 63781570 119356268 113489114 106923895 86768788 235649412 129620177 740960171 206191096 765869151 403967424 757140347 166643170 445526676 250778689 42824556 896584019 870573380 417260104 789137135 658950147 398350345 801820104 78446982 928547719 392713654 328789139 757379982 296588985 393792951 513758575 212886907 365665571 479764040 319810801 304950710 715413451 301947329 898427232 921604546 67816479 302394655 531261244 86976000 600437683 782039932 129800555 497021701 505129664 399577011 138675187 16596162 797927355 793011643 95043143 726475073 38241648 423832281 336371406 334830632 670141583 702646333 547717538 35807153 182410372 867528338 193274214 897823823 21992019 91701445 671944720 89808497 246612452 203205964 176784497 847050134 985245895 159101403 196588186 342891910 558678413 187779724 359488071 209122119 980791366 454531213 935597192 19033013 730879845 124484949 206379997 401021428 827131281 754097534 289344932 862058005 474142224 335135498 612398179 496134242 279353294 284342898 438459090 525965745 340065213 615243586 225532230 177827460 626861341 274636767 520719369 38056105 462416491 880207440 247178224 443207856 187255004 35291767 314757221 918134849 159776715 521137217 171672628 839424348 127751102 461017559 701482352 601893325 796153056 166396882 950543918 75506350 450739779 389003008 453988446 790804992 856762945 532037028 968632451 483624285 806673794 341868171 521680390 269090284 222075610 768858613 564814492 409330614 804150379 879571712 179981814 816443445 400708928 351654441 655867792 528460029 812671999 209866495 982869706 461341407 376263376 933413623 389364108 679519507 174932982 695868905 322840850 31695927 227905932 143989652 367836563 34579726 485857822 742033304 156186361 707933432 363408268 721000852 969780397 20074998 453088915 149762210 836518443 853797842 501416650 344902586 234774223 166605000 554769081 70160280 480462758 783548808 3573902 869826865 463068314 31023236 418212122 785909163 915235514 646118053 929898814 135588428 533214130 268272988 877621732 541916843 976206419 241029999 115434046 798503167 261104997 568522961 948265376 97623439 274837154 302198377 295042376 509611376 321319728 849811456 579771655 801782486 485876616 435861909 524125702 948944929 319401496 942337823 587370444 234637009 440972228 369785609 370225436 974186357 638058596 100363519 368619551 466781366 341393518 484053597 117800884 455014866 52576557 66066259 405154656 327413710 220780987 700197031 689541438 542100715 402524839 121829444 196399552 888401454 557691352 720525253 689862734 877092847 662863076 129749529 964246207 103835303 499535138 186987995 930538011 990110085 287351513 151673914 309407803 628745030 635727510 427208686 83759895 688304066 345791297 341430902 868234127 566572283 41627933 557775564 961189349 444152771 679605008 157588900 185070576 89812711 878114153 874933309 819421910 393493580 4682838 783668116 349845234 356734327 970656110 132899596 346844411 110523975 284573509 656252213 739269004 920301018 83460899 675545251 461121435 281768547 16976152 181871914 848340829 911120436 739647477 662046530 207789558 271768836 819635429 392860133 214097899 550265933 267793442 33519808 796275864 124992631 669704275 146121097 481726957 492876737 131537045 828571367 603400711 268626905 337339932 195186066 41444275 273317182 870731316 502565709 555085728 740223820 684437622 255942908 503860607 276601451 917989437 711650165 400886638 590141218 104510297 614984536 992923502 224820090 648504343 789199366 349812720 170724970 787836814 831539676 663601706 771890210 512627395 267002416 40517115 849967326 462188481 81961389 975800859 185436149 437043449 383402938 778176320 121481071 639345845 282036926 250598873 409851634 993687090 651485510 852509203 950713739 118986398 845432704 175533828 767490740 487148421 525346548 938215709 127501587 209402575 454333766 899391796 722029969 721336181 792425262 424513646 36041014 874386650 400314504 73993514 163946451 783717441 852169833 137943873 275579638 134206758 388542745 537947623 980410200 892544606 390456825 783640290 11531003 88405880 959174117 631538095 428070653 337037016 422270155 555572239 546439591 876603921 307480386 120985911 450456453 99905648 545499557 486497466 826808649 945814060 560490979 990755099 582047853 265177163 128698971 710143842 251900273 369758067 248091464 84826824 114819025 491064640 868467113 126350027 579470519 680157581 757888121 7541171 17194597 32674628 415629761 416150539 909278548 575626499 537136449 359735000 528048498 82636005 698748818 207373498 880966417 111756148 50644949 315530621 376933311 31860271 25674462 628833583 401618338 126282277 713660406 516437362 617346916 582127518 495303740 49333786 114801450 105708213 909391309 131996046 138382840 177537421 400662936 47661387 753163919 790315737 259912738 281212416 725468093 958661555 488585914 458950861 70417703 539230862 774481481 447351013 571091132 652672294 76184595 825225821 631470922 642361352 194179534 101334189 77005221 689483274 150667975 191806670 795191486 60059283 176319068 933574325 90113055 576982003 981235711 843276974 219814091 93664800 124489389 945282184 52326355 465591654 404233044 122744057 857338867 31230877 422611421 280946351 536419522 351312367 106172171 167890444 993673718 300351705 269224632 70678938 989834978 272408958 115001959 637542815 184984592 291321026 571117139 275097647 868303029 404869201 118374620 88117119 498534000 95380360 885915654 403376706 413488366 142665050 378637114 270827232 173895926 801248534 551773582 710315447 5077252 510462105 730722242 851267321 810813809 999946874 774462610 653165138 124872183 889464569 143224304 309856775 180785594 714341442 584954421 901604974 971726994 703329040 842238445 322777345 651225751 728154098 726154051 64714116 870819147 104791164 188057700 897231424 758556050 739831281 460063223 763633301 102809737 190785464 467416974 913623545 43248689 241879583 419305034 168120872 131344151 562529337 477977646 164646097 129387130 62932066 66251070 101114123 618777457 761005866 276407820 122519559 341676316 2561870 187233675 65011814 107353033 375291374 962243238 718425434 967639006 422306460 334575087 70448743 465608275 801992060 836588639 508856964 43871642 108410025 529494187 27732145 670939361 7471832 44894593 652842843 922920249 963662014 606473317 394214057 724667880 882881136 516733615 66344195 885443005 556483641 131356008 845312390 931775014 946115597 416254175 751930372 220938408 750829261 822379114 686546683 552821320 511484104 47919998 449209314 619894128 577414184 329457810 143349841 437402367 226868754 796192683 212838967 190530767 402665999 607053023 767714998 138063487 976302989 686575544 23506491 532786630 670447904 721335232 317077995 616563500 137589407 69008366 837501908 740935019 743903831 376564942 146272691 107904287 424484939 595482004 727798414 1899122 777456165 871148254 439301488 4324918 667340936 652140454 47372036 922523287 111709828 815087034 60586773 88012816 501662577 936609615 473315797 24626832 510461199 642910144 641190332 500566957 564434861 331208591 241501975 160855044 707773532 387774665 268759330 132258470 835773020 996557743 986673943 613229184 867705997 278491782 470070453 387563284 930632235 517442489 162602922 894858414 332529522 223189694 835387581 686708450 12315661 161219730 711335282 522776859 804129873 205041965 23343815 368564733 536250555 117362141 529419776 96540438 505136806 798179105 81315259 193426177 647253200 67989201 806655361 367475548 198997334 129242165 755038831 129629568 646684653 917641753 877004333 979214174 993347798 712391913 518438976 5663458 873611642 229774257 528440316 530257866 434816221 404300482 898822599 823583127 521662623 280758726 920123564 26799428 931454183 853955174 72741956 578707382 774460726 879397316 946182929 973458059 8639481 553738111 955603978 507840485 323896215 832608310 339571011 169760365 397516574 858009986 175423822 123644568 87784242 556380490 653902433 375116814 960680971 405241383 51216292 482343593 538516461 971339855 361659372 469970643 677811380 434401328 901194376 452272105 166314995 699893656 278246515 27470827 106148118 233850492 535311312 430044333 918975153 874882322 599804697 169008078 585408659 627744870 292652645 525709252 184125359 799071430 900826065 144806330 56829164 952042356 479666274 595345624 775898562 693841998 65316266 306226293 128243325 819026993 758498397 147074671 518920648 36744911 27061850 625068766 123111754 562373161 907629450 42086906 289771834 359950498 63611335 875180492 987695367 356263980 253406095 24337078 7851761 6748511 21659759 64680924 958790866 501326032 660026548 587205779 47684381 577859165 893432071 28444057 396886158 504446819 175518728 768323157 393708081 202580577 245908274 369336186 617470089 153537723 263939443 907241922 513488220 327550777 634938765 353699939 683814756 888344859 378037016 691666516 895093369 399696774 756347440 706400586 901022805 268890339 146122716 948707186 846749503 892071138 977151242 96152012 249034308 5186321 864475169 642742388 60283249 110383442 12078573 677753337 116437517 128534367 437511610 629925736 456085143 72450374 983625674 139899899 813311584 214179041 684082766 560921304 613875814 292946557 119838241 367414971 561836895 118477308 168638508 261102750 10548445 145789749 357254761 259582752 3492422 221729929 754841491 63775670 184629723 619436415 741529007 301067239 747970781 31556968 930992974 204055924 104007342 767135000 196472174 769835277 981314040 733071291 183272933 447706206 26017848 155627525 815121176 440371094 274104833 983759683 701473843 284653277 982065783 58728604 396752381 985558204 132974884 151593871 901850226 317604606 771030286 495895584 618671844 371517418 527452551 402181170 575573341 483976244 21832521 624561866 106327873 855662912 357633157 289600805 303369117 236167356 445228329 118490292 529054801 719333161 954766326 83044996 856502790 936832109 141773599 253255170 774906664 127264834 257365392 529273241 297385792 28395677 25168824 916057635 252429447 552621375 170755156 828002787 36597618 45104028 305081005 142925490 900766940 662714161 285042646 56652408 751397868 582787327 27659052 280452668 154636839 982425377 363497663 11139628 771773837 357787613 116911149 399196853 337568799 374276541 928470093 634954590 255188569 953638917 403528576 507618015 358776643 574283732 188137154 247890612 619387759 493218158 243332454 372671050 8448670 380891451 429323458 759846537 963678777 456982509 40299204 118315616 439407885 256313219 129455243 63698074 466617183 98882744 462894926 804185981 473159284 391365018 439140570 728347852 197520286 842669146 235965867 408813280 269469229 424103020 656703892 741373339 917321177 752552697 114044389 925769846 133444147 543367846 538132734 97122924 350354 430948289 67954891 292274590 687261507 49926485 355972663 6395042 148809228 818867588 810581022 621968511 62748958 102237944 202832715 112785595 944907089 438798581 521598875 66892669 715417952 30819118 808266007 485255480 783371814 774826747 263541677 916815960 170710944 801674410 866455235 23577649 232622698 786926477 315852239 772400557 836852962 524341253 778795598 838178541 195725193 589376619 312663404 258474150 691614562 515496118 371259744 489038002 954294698 892858618 408447022 522229001 923677735 69229381 7484480 559565900 844056127 271026156 328898212 14767071 72700565 47869798 38344719 157839614 834796275 206713309 930240170 524165588 731054562 561552119 362344128 926779754 3445090 675007531 37770255 695059651 43020000 409029998 36614005 997314697 154404968 445061026 372060049 930599054 514290406 379544528 490164954 210862885 503087035 819063165 225629955 428303951 866932962 116491025 586143565 554245588 323204334 368900086 78411175 54258895 930452205 293271655 981038648 933897294 968279185 18808902 481473296 11299185 280355251 370603652 861130233 287276570 815664678 85706634 217875624 182471435 465251161 560556929 393334319 968338196 232136445 471480625 249158498 99069406 587971650 835302062 505831346 911175983 56718500 584242520 965434877 839687056 877514174 798989876 626100701 698309711 670315129 107573996 562125247 803186731 330694000 275771831 90463301 146358677 361478464 160855276 181346463 679245977 721412204 427197134 500100524 953548648 898677758 749259021 905134405 486649407 437077435 410965750 250341741 493795934 847724622 68292969 185999341 577755147 867282844 812100041 128581209 390114324 772190388 690706455 45817407 102884387 818994638 136280707 101759415 32989453 297135982 135622230 712235429 18548185 562819363 212335952 824613184 461497120 961594973 729747588 800662879 251188759 993229690 51004619 744984692 840954311 119297588 930984032 271225809 839096783 595600424 399807018 81727459 367790811 90513472 127544865 323191550 762024461 263825571 424950964 795013914 413477904 560573193 507249342 284542440 123392555 572101646 109155623 437406027 386212970 691419562 90585257 637401728 684649251 141589875 234902771 378119913 113403814 18403154 649345722 952500597 614003577 49152739 34228055 981794387 992182562 161772919 157502288 606723375 278114841 582453252 401737288 691592744 995542796 761502981 976135183 971451703 333604626 85290805 261374081 719817595 629226718 351959337 209735674 166392321 493549211 444638444 544512233 606953025 463041597 46374306 411969973 77045173 948043396 446198027 911355912 792742310 460487297 68858199 399465684 738602137 503827802 653719323 430194880 499370598 415222303 258846414 323338652 601343281 196653570 584712732 173677227 825880287 936672068 383412901 992272607 282737630 828051344 389301192 889690654 291092941 435675497 154176978 220654465 236235245 600375004 132010376 28977554 60862300 53384927 280959589 651980788 557212728 934678911 82175667 56583325 202417565 193538432 232438328 803760845 390192001 817151059 977438072 216072288 753823126 360850972 60861246 36560756 41418667 450162437 778767761 332511607 885837934 932944739 553166072 122073178 385836094 537692799 3567083 299214746 591077725 284526671 951195533 148290453 71721933 885887552 57390129 274139497 79425983 289828457 77900342 322134336 106979515 55338413 538206623 713318993 268705736 599067868 602396100 310124402 49230305 233680212 495152361 787584590 19141302 48318432 762174119 257493748 438527582 618257553 556708493 29605307 902784223 360420377 30412111 974506155 98824280 87802239 101162003 30766615 230147047 179062344 352900950 189642914 86917108 743623924 902961906 208139195 195208143 357874357 518263597 96954799 444070920 13415957 884539388 463212222 914250740 499229858 720705969 205294673 117487410 129930813 234899979 872787984 342867541 265312089 699810490 441691821 205630680 800972493 324974787 435777726 832551188 677875736 625420639 919468296 274016011 380898896 127607490 469224153 738773252 498387438 566178952 35360524 364319746 303234691 498572745 131086837 802464549 71795065 336381510 772468310 54242229 423797840 497772646 397109769 689109929 50099487 838801589 894740608 703588331 16292727 183034685 536139519 694168462 808455324 308124166 968184472 189354219 288248007 289924977 780643823 639151797 856103928 816004346 3471542 159338618 167093442 987074731 814319518 238888506 175972592 439304180 293130734 599770431 937076825 690240502 141396711 839692663 381558443 36137318 543280994 397851169 71688355 931936864 944535983 880143678 92577381 765236806 69497896 380825387 55161782 702658070 19977183 911265709 518662415 875965077 923120679 685755856 715556159 737440196 777160713 891528750 29260727 70291446 491299180 966337551 613048300 632695891 658546566 847123094 521349560 54343911 97490614 593037914 986280774 42026596 325697943 78858154 807263402 247712191 312199892 714941535 950370260 184693427 478723596 321549027 60658503 401844274 7304882 628731013 991800821 636981947 520259762 21061548 559789744 864075293 839915450 25354395 349287535 498462015 872477488 870637095 552805925 969968102 316191360 391603050 11994697 641889303 470461203 671774450 889601493 782661095 239232337 692488104 967354521 717955932 14037130 880529375 119800205 873858364 361776739 964117377 510840310 882036500 985178924 70630053 598628144 677610726 95984448 947915679 28589092 820978287 671069125 581395017 790946388 987260484 972998066 655457437 481666138 295975621 179748238 223783982 931153067 418980574 916272086 751023939 136936505 782825567 484069665 109253061 656683930 845846403 925886790 20040591 580399254 763582065 943186996 179027397 441192790 891687795 126943075 469781882 712666081 650528551 903693250 356128821 490305387 729207667 864102609 971971524 25183287 43850846 48271858 808852705 315347772 817060295 559876643 304800628 599885861 43946307 266570041 109086143 742309061 44973182 129126733 322708314 808555246 924830080 354252063 102264388 816517874 333711489 572046269 381700307 984240040 328255870 590345479 474545426 57463536 454448087 299033301 935163175 350815284 199821510 744015879 518679407 16881804 156408874 823480035 469284017 52871532 942566427 578370159 795180593 987539608 560013243 970405258 796094853 337359675 324657320 898359240 6393900 658368809 322921860 388094206 495125200 651177729 978439684 969670625 561157617 285404122 121220277 496320791 488735758 321041787 92853021 7415164 190439942 101778246 683411550 659723958 154649778 625977976 90610468 802346722 466033935 650623711 772751979 114645140 987983385 949925651 13004379 994377284 460810811 188442591 234987842 955936010 692136671 65943877 778122986 253294287 203864351 899343262 602131429 692600108 72901400 694984450 700015271 263341342 796762695 235943173 923065299 803928824 861921148 13675767 606275545 180471435 516815829 231543876 295116574 357315565 33985878 160637304 204209200 494796688 349079894 291713393 450732697 41216565 357657270 81372034 147027203 561521620 980715295 749158632 106638079 906133047 296659433 806653349 21990740 945938479 42596521 945056038 749867303 757034021 811248156 208659199 937505455 180580336 292719426 85138380 390412252 326705303 245775683 594621452 821501990 594855577 886334844 124751038 488588493 96508465 206123071 488132047 510546436 39354718 89807030 617184514 945487764 386466462 276354215 967478503 184921293 171467087 765050892 934788595 928501107 428815400 995964145 718522913 609395735 288683571 803661292 999807987 615388873 49436975 446945790 289407215 496808903 185796985 414158252 837913747 134821802 620281323 326045793 645368237 659636040 415852823 262552751 605123803 654835636 538906965 425118657 839756928 710374051 190169548 627061874 491391510 618984947 623026019 62430774 80897034 764225941 718608418 933221372 232131165 620561744 232683513 521538379 117370646 418480497 935696631 807800744 553302298 555977953 133846536 51186887 68130344 402215710 313739637 673254146 57051346 705162953 98372802 749324625 268053355 141058701 376386499 759444864 612560000 851928869 674391990 693457033 616154809 393000407 479194756 848285973 13562150 711878268 222340704 983449147 130358764 158037334 643766242 536177414 566531638 630129129 587364300 634661981 32344839 753620288 160432478 941912536 458783240 111321631 543753512 726836594 252380331 920140010 338797810 864940330 624585230 13189799 410913714 93256390 258706557 890108469 941542363 124785058 454503088 16399418 960750556 437378204 174436751 604516797 973555617 740968388 87162277 413436268 228146720 119507115 19572907 388579197 913936002 478356146 499900827 310205866 57709091 752281157 82862227 249023252 469737839 707447457 114729402 733167904 800703846 373435958 475792725 594762560 350737367 930295812 611161977 311487922 367674015 785598727 768521070 193745983 379083466 855683347 459698602 607230185 827706813 479271508 995809381 594159167 957627653 348226559 904365032 867853096 100507716 987227258 116876347 422761906 694674714 231605749 8446161 347894912 457558058 484238885 942657471 808295425 414534697 553819448 119783346 634725063 191934526 740820768 828471046 423534344 596504114 140685999 30764528 276727278 619957507 879090261 870886444 430101511 79833171 775251475 297954606 32857238 614995085 267347305 455619143 162186150 498953053 464065304 510081061 956511110 948304188 452738532 617322886 215355236 859074331 589622584 850080299 51008856 330443351 531067696 327059551 779463816 671753694 210340431 56191093 144227552 89430691 927077537 574329063 21780213 554845363 872283668 54637451 22356799 139630972 510256593 184542949 491100376 826838248 694624009 300127838 627658788 147362540 917450723 843014023 858953222 359589658 545610673 762478430 690033008 929194720 89537980 322013175 453464766 299878410 378204268 597692317 241825452 157798156 172021379 263605665 565159870 896821399 318243115 587516669 888968722 681016059 772059617 232585450 507854307 466683625 532713287 135513094 466562517 302680361 831043468 178032090 662270019 229170493 940510519 204819378 10881564 30048499 526832553 464346329 182443260 757553172 62038646 276785064 915351327 86576376 540390728 333027548 983397774 711150194 920544216 872366496 392166252 692603832 104951945 752536910 11803809 490181583 740566355 330882677 645378295 424126175 508914766 160164665 653296667 449425285 364984043 664178230 331990135 744332947 128524559 366949746 501886118 43079556 643734809 269753796 129655931 36641888 602781343 113053705 747792081 375841911 837936552 139958333 68445742 795404848 745011594 932765902 138102782 485577949 263648578 783481076 909704123 772563344 943645741 415517141 74504980 161146135 932211722 259011466 905479081 913252632 625961211 259881550 956332187 269696020 382151697 938504470 306337907 984933039 904074526 54129988 213291301 594527429 46604672 134253395 242448628 644132617 67019296 380551409 129710565 183184226 16548836 891931039 955747569 812710928 159964531 882768900 973857062 92176253 141780365 731852494 857945236 767741575 844250395 666793775 889953946 226402091 605298244 48808205 63851482 361889121 102938192 277142782 956416549 2059215 411396176 198865176 498708183 330931824 431932936 480935100 514116049 448481771 225382490 322379969 113709051 385347021 205148868 87566112 330039625 199445584 671934958 40501212 967187158 368701704 707294986 709657456 595103795 165109581 758465660 511471628 526998701 713920203 788614409 483415249 568495769 52526937 534796776 67203951 383458760 966729711 548139050 897574808 267727834 773521540 72471128 381436884 11384912 277619995 321519347 193940888 477065578 993454304 234442099 296769087 214672360 941737085 6426542 809776154 106846665 617408553 173764133 633845366 331328755 962378541 969776966 899824523 867421829 504573742 819544826 103396940 323819804 220200227 971747 591547637 993721766 73442874 972984520 857623029 203579220 294503867 51563916 533161149 140474522 286006015 829930236 355146881 80259451 688873129 17439386 187106115 158798034 191203518 673467832 490126788 6098411 643244798 242467663 873520239 334891 62012488 976917179 324154694 134729066 830405277 915702331 128450832 756364503 741203202 838590212 812460074 35707068 890154128 345621223 28697942 28676494 28067810 236361174 108935944 569457290 253800560 148558410 728255323 297520429 822026242 70898463 303618839 317787391 313366125 29655430 318122281 227894964 859088960 494793326 362624029 542010588 263012008 343591212 150891442 4215210 34697776 963351516 892438629 924851903 161489090 921136570 806044748 189556899 10014096 914980691 759014188 263814655 63539100 339785863 561335083 738081693 410684325 717470274 55869083 724050449 747125703 226507715 804461764 458731014 721301041 19602144 741601 984313048 363193356 151633043 988528257 397891131 114984558 733483238 175259385 128989999 507136159 981304132 318546897 517150254 748801174 930077436 780964908 664856625 269863298 194816343 255454670 680547622 912286616 311323752 257114422 511928670 537831467 61576185 970659683 111648859 81178329 823917635 95961906 296888036 975550677 937006515 547295518 943051586 670489752 722554902 72041584 30142262 556375385 243104832 547292516 157692910 25698620 180773775 675065886 295561917 375590117 930520555 828625891 140393084 94360659 85740312 504838105 632192125 999832849 328014139 743840983 933527529 151931774 692319240 82931916 979998802 629325754 630227433 775566740 152331857 205298686 700124675 182474119 614190422 943229507 729766634 771883331 968928126 910540408 299465568 117006394 138646877 229986123 945632284 131556312 324346781 883888948 636394417 809055257 736238148 964408555 405412591 522282028 116340328 97731830 457730295 948855482 579573936 87957727 724422221 731905792 145772764 277063247 766896262 759963185 72809105 349179247 384362867 41737230 112236007 683828434 11259976 250882883 766330908 809408611 382439194 90677688 545813910 18833610 752249296 134568409 835758517 157661886 656850436 804615196 107910068 114580730 753470677 687484003 55054808 330409249 271906146 53343923 607472496 38802408 665823459 680281600 387981654 50186325 574535182 500217660 586531111 438311509 603616894 205378370 247720119 986056088 148572410 793534029 857406049 900821705 928102437 545680917 58483591 437469225 350296113 18910010 404566306 956283141 706394012 312137466 139208742 978300157 217997740 746681237 17102564 883821199 279479188 257600570 786523875 706530721 610334581 225571337 144842229 213951475 430949707 245078700 52523914 579522116 38612728 762446314 480343820 819231516 308127231 391343762 109217092 510939695 410253771 366299750 467222835 116647782 678437215 606431576 947464291 896434954 205629164 817083206 632772504 337624704 74683775 419296379 44155424 537534708 644867715 41514005 751486182 75817421 286592704 656526447 507855888 177721783 418972760 988199708 996953298 579616342 232059821 958686742 90556036 494829944 324986491 410295223 463994077 855940057 16726798 411458367 604891362 74872314 81057925 237663866 412497017 8258051 509476596 309168792 545792758 6860662 350682796 149795291 82678083 637275499 806321737 443050322 814997281 77810849 283766381 664466931 657427190 515826202 623153672 747983226 10656145 800656514 10794800 327166573 656596570 27521597 738624940 114004283 954910262 819682864 351668148 219923630 827940914 861144743 529092422 226250024 868005405 879775217 376045314 803199839 517050716 182367051 98766512 184564348 260177899 382532893 849031278 917605088 898359094 324701301 518104665 761531590 125357814 528899464 88698162 634470735 408937413 679839453 748475018 216364026 352038668 100143165 436287656 32495934 813804260 965380077 258745957 534326016 845155293 634791270 190042206 214722360 669674672 288808717 399286708 929852570 671341609 100834337 699974010 422217054 425535638 70595026 36264995 550893451 452010842 977479509 37880538 860948254 509835313 786355555 77312279 861873981 739015071 366116286 746886266 405335682 331496362 5632222 939661697 29168007 492939843 982220254 96406718 15130867 123545323 495693425 944983436 794886931 596527762 497473797 69620337 22063399 420585175 105885331 425473201 872596016 935881191 463353738 586060621 445716504 102225644 515889251 160106836 841240715 882005537 906993101 246576396 66018250 765141674 38754445 95186256 110597868 20974698 191592974 125728734 144520020 539802750 923228522 791923303 136330511 273218670 714059991 10910261 693803844 672461673 288899814 566399859 608342864 604769903 4976831 906575719 706995547 520866082 66682554 548236261 402871618 826192006 647329008 468889867 443850031 686083452 416592475 406964250 559574502 608185448 532692984 556610873 504549 308437857 201050527 136835060 581656526 915110517 261672 275460370 440088542 141677837 694376580 48431405 746447740 699353411 807523475 305959638 220219492 726722380 854195898 475607461 405430737 354041257 944497327 849280767 40124709 213606153 108761368 452215562 821791600 641454351 861342786 822296149 949892207 62393313 811647560 384065085 830020181 664425583 659525454 122625074 658619772 206418385 23572830 257583863 905771795 831096304 563543500 125991286 557818683 270255749 454115098 963249419 624297005 251128777 665046537 516938065 464734929 773807905 969153626 139042881 267778607 683012764 961339029 70187166 597922428 625502940 454252250 280458960 142444874 966294055 403084034 801064645 172712439 426656863 58648507 78484234 257753167 474708358 56991871 668088201 744964106 363623321 483853972 369261111 614752097 1416860 886199175 79487025 775224764 707869153 218529905 895519723 243398268 32385285 965706888 841320695 510404576 272475489 121779654 652849450 91285895 524863687 306430446 263998333 951520550 217595305 194998918 61790068 692303662 104507141 729878268 289784120 468130461 66248591 659045230 82882557 67665451 397760756 14885933 842890214 958146260 85932190 590926288 201544527 118317474 409149527 42865221 628722050 681625015 17161227 134087851 772910909 394541265 293034648 889425594 198578166 510629952 84424511 260368233 55449966 41448003 842762853 345234085 362094815 909011443 856795666 297493723 976676893 107072773 312379656 672083459 65219033 398311845 263009746 119279911 369145670 672159273 14661484 997867719 206300639 31822710 984471921 831727900 426363974 277506569 721153493 624942140 640652872 658094355 737826724 696102837 552058710 580589576 893853273 914153524 342117371 750648938 211647247 318794263 857721711 376543254 990877721 775457095 774855098 106403819 894737005 144000767 631079443 909398488 994384838 837380081 941221197 831373110 521624332 220101523 108879678 95294176 697560014 602048902 753388531 435386737 150668090 157963592 868492665 44521363 72117115 210610035 647686652 136280713 381920649 357924714 512823966 225314722 133381808 140195415 331718540 28118813 136712534 962797982 790033652 131097371 652694414 583771201 814986832 26835098 803872723 776382862 122129273 353949088 378431763 875517803 789335824 529099852 33481394 510344840 426137566 958114861 720954874 73824218 94395573 102875523 431748931 607219539 180706596 417647091 747414953 512425135 298282255 884127486 327739468 88315906 867741208 832950233 672087106 535244392 859785330 328476180 311627253 981914603 682425267 542575367 709948757 324277443 71675218 595946503 834622282 350329136 554061363 408093508 424153353 500973287 363485382 708418635 108192825 544191977 126065725 708124130 909133463 424347979 444767967 89389282 365180237 165025527 922339514 37267342 700269918 782124844 218259874 864413522 616555798 753201492 406988888 326504554 77478934 331180457 922451056 764617568 681509592 329028770 25227427 958179296 830002057 241229160 666597931 790711233 785421136 645180007 351351714 547070950 69527986 648636033 636460231 287224574 813661559 558799744 177008267 366447828 193440939 395268140 83377701 809996736 985984 490366588 989017642 78464917 674063396 763985049 695598836 208089340 93013819 573342614 166268635 775532227 814571773 685382917 418759811 452509260 330562924 622627877 999580209 252607261 271263909 636040439 539831834 937441819 47356535 716840100 156405998 93313825 964624592 239783698 903310561 965610575 730150285 744844554 896591843 256730032 508829602 444707031 464819371 454359772 18049644 631088006 82408350 832621417 168987274 353684513 137647028 499550197 976312389 137227237 604673809 100092649 625784027 144505642 37534467 673140561 713862094 193940464 766454386 531003037 433724161 522281298 496613611 16390797 119642203 245721805 273120828 628471804 690428835 737940199 935347928 708478479 221544556 17756277 393616247 390531829 223957141 531263274 742598378 200269529 521006862 347272186 300362177 146790889 344294180 190412995 672447801 910672625 384353458 291418538 441675661 670593970 813699835 790805623 686984766 933342037 36527427 812621946 414330193 726956262 403078496 202194472 287951092 624623051 72467100 534083690 867671231 296424241 65346963 610269608 496693769 438870177 810058146 649572298 585661065 6868677 839985292 110625217 917541301 76855102 402043755 211733313 747449071 68259941 2538935 286950189 1601978 39066361 99572134 268448522 618538974 502650629 470642993 759006417 979790031 543110092 293090106 847461261 839534332 210953421 310247221 188744453 649823597 120305366 838316750 88001013 127174042 530818393 198626229 897231694 607673494 600669983 108965006 355122565 668929924 111503940 642072753 523048253 3086652 594161238 644013126 474141978 96811866 114656118 85664746 929118248 510282561 378754852 629095860 202333245 442224624 939343080 243594049 92048220 912164797 81910798 32565584 891855190 465245542 83708164 641603235 72919036 684378147 750568240 280557952 205824422 714588531 922630704 581389026 570191535 369308293 225402151 896849864 318636510 192574620 982514609 247754757 555373532 213785812 876850616 757706776 656010435 668710048 1300824 600575006 433391196 935727973 633140589 177762738 253489867 716848753 819365972 326408902 253743251 422450564 606966853 312084024 989555446 382113908 893473049 412263332 751422200 118875199 309113195 70058709 163966170 144144156 170329817 719339701 357929967 899696784 329562829 13940402 420923183 183380004 614515407 854314379 971624329 100172348 884593468 225114195 669537452 556475791 404039448 923280702 978926354 11006300 87881077 820998152 245636559 981354125 233261483 849575110 952745675 394891030 772150170 116711844 539035185 942479986 688567896 896965151 694693121 870647076 910905552 115616304 54027080 377937311 822447034 878167760 330626010 707040501 103281954 163461 116032643 359837753 775960514 94958997 223360404 863841590 768473500 468996962 845195714 1734982 171088423 650457740 249142363 943238592 619685935 788177547 738234929 160770182 685142698 432928049 31417258 448564601 401060704 937960689 679018263 223507737 816128448 9644272 783064589 771926753 9807732 899097232 131764505 638284597 846572580 207641260 502126186 615046079 676638221 199838251 469297412 847726643 850295990 718439775 643481586 322498276 359133673 381716514 483268458 44276370 667160914 514685715 345357323 68221618 305162755 24375585 144245706 121291202 886536209 927310295 745734306 748860292 826407526 730015162 387144889 525496457 937656421 741787426 140542535 466810993 941625677 462356298 167053987 644438018 33312424 810535572 966936294 392446097 44768437 302721103 289238818 711929350 817406817 487112492 632667319 122569571 364004429 776913025 96377124 250540637 704223319 694627781 999400928 383147196 277159294 239062168 908643652 67332066 980849594 901702538 386659410 774991622 216575187 553713396 271945991 102403963 216765319 91398636 494850059 114050107 394119738 636605228 825979456 64042906 123717720 311163127 39128828 487722148 88076151 988022303 590779136 644815821 535166435 442696415 27963016 812325728 681758583 789123019 732174145 515124528 543341908 118833554 142632501 612433446 525063301 267094843 714837408 741828619 358493479 62203818 855878725 605129568 698809046 534374533 669172474 822526765 845537659 560817653 162765264 786130161 548839956 753544399 430945981 84006390 48757165 311425348 748848470 730515747 953064718 333538966 98156626 348922977 452372520 93305478 961356422 977435820 360400321 676193830 571780791 718893799 738397647 280175867 176539718 289723044 667066751 845712191 112249808 365120761 259046196 127531423 151250921 807886151 733592173 434713253 744408892 782349338 746138600 345773713 365381436 551719669 679312679 463538062 900642645 984201550 556843539 861999067 814153721 917243859 390709248 238450863 488654009 981623246 518626730 665193727 271346290 38209832 363422269 236112449 403330593 622468464 216160224 554581513 282870966 949752396 989294766 879796210 732101733 587949717 78086274 97483169 139669386 757398952 413537582 892828382 594116853 822897472 607343800 408270574 592657683 998053047 646721436 81311691 832192645 17864517 599021769 103538934 56074349 814960390 192167734 459404941 289945205 408327957 866502805 572816171 210596705 708313922 305128732 942698437 148779991 383215005 892697957 140965728 140613957 158751890 33794109 587247161 981649362 641137909 995517734 426823396 491707307 494755522 360651438 176416303 365136390 959673207 132471588 421210738 627149948 324639322 733132030 917095152 585483630 599634835 342427674 796080334 160465108 647556405 591295123 309245098 30771410 336509431 450210825 23901718 495261321 484004934 611148878 329427034 977659194 459182964 756250429 321882852 806454837 116901866 498299155 171591226 929091424 630770742 445318316 408757723 955410063 178450345 325852875 393410045 630601531 668280548 189490378 791066639 168353305 780785500 100311736 199124714 117294931 550522561 75542783 465072603 887043846 686691660 647015988 864703039 998390975 255782768 39102242 804845811 225200985 537401396 828953389 6808761 168172138 274271704 415566483 976098552 305238400 741419357 369508596 935839931 262216257 411515326 726906569 430569561 44817177 679734656 482210626 14628459 82773568 557753408 479701061 969817413 96961419 126717048 687036803 95352394 235016167 726139045 752714556 460217152 263540440 581667944 467025912 284228929 708455999 882592394 260327481 13694399 476528103 482352428 949534329 738744359 893867753 528957249 21830271 938684930 61208256 504040896 953313388 143981824 61794303 285530801 113799236 11272073 264764200 800836039 106624466 499780367 379491435 859339022 959997518 643031874 293523317 427023429 927260803 1979316 162132174 40104635 868190066 638660276 522457062 670240746 229920986 268841167 51714346 251751256 207526096 112922601 608308503 13355835 256904424 522619157 298886635 370703660 533891230 563650835 24056050 640515695 63431201 403547484 352371068 23428718 899095709 498410737 302968498 678872863 352906404 465100671 718977497 221096469 103760947 93950911 891337214 186198284 362792077 943051559 437949540 422834524 55974159 46258042 436190358 165394935 421393551 735076993 536098594 955284780 298727827 412670995 448316826 214675379 816218478 800687894 90620448 567830538 151614982 393588945 246703401 504521385 711205967 818197249 725617853 667483265 912148159 469471418 853681549 127456587 265039328 144147440 550291110 173529838 42921833 986481468 338924772 464315383 574074812 727539717 419600162 872802638 140210711 867916988 87478016 808945540 521121233 30614815 376776078 672736214 424203759 475995830 29773950 135409725 294193078 755391802 655409342 58857589 77379571 509090890 38830527 194935250 653238329 589121637 368465087 696160161 428119456 559906211 12991896 2194267 287445927 432592057 727513256 280172990 153025396 667507623 89118529 526662980 698122437 318410958 51915545 974842547 794406787 81689494 962768623 88599865 837081295 618177964 999973805 766977217 979785205 38804331 961912466 485539885 480442319 182893905 34216398 908561774 742800115 47208293 763272392 30246041 479800349 343301999 162935382 485342097 863325973 252053911 12005076 413964761 570464868 63920621 388807307 217388007 145610114 204092282 158504223 835207761 822270245 158478027 602184977 654571802 49798709 416613795 140111686 530241028 599507699 174328083 291319153 342307813 221536375 54591545 225070205 553853076 250409895 388005587 39195172 113735868 492575849 51200247 380216980 63040716 967637219 769024287 132945074 113247333 973116568 291449296 800971445 647903164 449927322 255672773 154991317 499726031 672286567 295103003 29967058 271794265 321947437 173802562 466618429 543483812 80910458 691688634 97336887 331320353 932210572 989048410 297572572 424786420 892765008 677789551 340343487 860402227 299330189 473288561 826165911 124963108 764737856 479653707 625382624 67181530 735326479 780373940 419423912 407613046 75476942 301907321 531923662 249940731 475709882 998542091 793424542 556620340 542747076 743277780 887940692 474957647 584842541 38029615 752260418 477607548 568335517 92603904 190526126 867665706 418408816 869208388 845145165 35663024 348862094 470527788 102844553 84188573 103418080 374784816 344317970 31411373 676692136 876241631 281352103 152402017 727300073 74776644 709022356 270047148 670570775 449479399 597521146 107929667 340025365 349781563 585537215 908360882 294901819 628579692 628542939 565826986 497788080 473688103 601490009 699166525 796732243 556850913 635871449 900150322 931635728 980189418 931561694 460844215 708947401 212913797 613246232 288763825 140206792 174784939 558810973 663293919 476780690 8848470 771223585 816806054 358630033 209277151 725166935 506048203 837856843 206226225 71875188 188161274 679914328 525881549 887327798 329162922 82732461 523199247 229313243 866884541 355905016 13391288 180245107 917368768 226305084 793491338 206132593 219028228 820792629 617459917 882322146 297573318 626308386 653545730 114379371 984938418 862822881 692062658 343502972 553196075 898288882 415378160 741357348 430719561 941259708 628685145 759882482 876508520 4400743 841712076 595909412 212822111 855103364 776154519 130190878 81408447 422162208 188839822 152953026 95471188 806299738 35275171 393044505 432608124 541337253 359940228 270062893 256676485 904519237 613565865 809872559 655324470 881460376 551229906 86044031 675236435 32431402 698442864 404261306 36832145 392671292 170718 102170607 247774655 628841588 232361484 181699453 903520147 421201306 334652479 998991335 80017395 222444001 244552191 512625518 763781253 604492418 635204763 20457737 361528006 101286979 830330295 16852476 982747354 234076552 955412858 657983788 119024306 506372073 62245093 8372802 899043364 914932162 110543408 146818018 396290101 342904891 181033823 152326600 616622548 368202653 151317934 696639943 590646653 395870124 61781812 354427906 852878894 696986574 227401994 214406899 798273552 57732289 83775726 781020905 144325192 39188583 291521044 263349497 545560656 206282489 271722298 297120371 973731002 382265705 296454741 222537455 577686948 477488563 374864054 194309495 845691215 526181987 890949437 288854219 774568462 952731249 643282124 627447355 502234174 870684118 694370606 300507726 780932758 778146331 934044982 777774301 817334914 78082378 41123798 215411921 284364866 165362447 512532291 110612219 400144504 808987031 333149673 977831451 138991945 708013726 24657297 837199511 86712064 915606734 126053730 861280526 720854334 621852205 341244232 75604859 345052674 35614837 376112584 125985431 813761168 162673918 756276084 483612433 240756295 649916233 551540705 525121160 815278679 64072995 635733378 67939534 725576378 968883051 45770984 717084674 529413128 70428281 554284185 616125192 838551366 532854266 477405717 411922051 154706470 818649948 487526909 499759144 706781137 863639493 478260926 373058656 26313410 87053361 856671088 119586056 736969593 260728144 644707215 404764624 177317490 132956944 472704157 902893867 954356346 518475141 472494893 483769474 441419773 26779077 99894665 279971138 412149694 429816733 691893188 566856163 100983032 31936448 919131658 807764168 895575940 249908936 33339175 774405701 336962296 890010262 893991756 73931889 3254757 391215322 478696512 180572247 376688618 951400668 83466113 331044963 322392160 408477357 667330788 763811932 287772785 619741804 896299421 699922478 49558536 440708960 119294993 3057920 472645408 38426650 663338439 220737699 288335585 696677614 995143400 625297881 439204227 741651507 551746121 442458984 985383181 30442632 623031230 362071798 834359651 559013694 545633112 9268163 967491051 212963900 625596446 255263835 832705703 521895867 955186313 734780591 962604826 74481305 590354862 287766585 965424306 253693300 508504284 106276243 950370913 356164035 731574123 242091492 97815541 135836595 684550475 935715073 18795578 307581704 150303222 853155228 866595397 695936334 714939742 686602799 908900233 340536188 941866634 594122287 714948406 749569298 181419229 530069583 676566954 771774090 817836168 494507611 877983742 326340451 600783853 680871006 682504485 184874327 922962497 632836377 320710921 607512971 421067802 339506498 767611026 571371023 45178078 486722775 267307356 760117819 173325573 28723940 100654006 967708558 475362579 668118763 569794207 656781807 198188346 98877512 281072249 16024513 593385123 11572342 194881315 194168975 692443347 729902151 379043302 615405844 215254879 699754222 75435166 636322680 39260720 843046192 207693703 84438797 182285318 327517410 697072967 355610890 356241350 650243325 175835800 831603928 318362087 745630006 340902086 369066784 844507518 474490686 237607648 437892640 486063027 432488962 484577966 178506374 14907464 863621267 646428569 230162343 415891841 721863734 866485022 307668912 417426277 74178724 244624060 599711594 254212486 941697026 807838836 610453835 444456702 983674635 294574114 762818789 729304640 487992551 131885572 426328509 962483237 222009572 864221148 448546263 654498533 201315466 479568988 669405997 64936732 125997556 899568339 333344924 700377642 618569712 493530187 117803918 545264788 738154246 570031864 799477273 532367624 230387051 262447459 976824325 214061685 557021572 592159465 795882676 45014122 576561389 222211185 860013710 798570960 938948684 161076325 305585844 140264149 640645312 827508192 57717233 766642868 579592882 243578508 319536861 198162594 737108695 289857130 743427381 327779292 859888993 395421005 860146915 90276043 657868463 689487592 156854079 67406386 134163408 952736755 112420507 563241148 27464291 824950569 214328459 966412974 986026893 519914303 959193475 626672204 199938846 16910707 245831423 779531728 113005566 565368283 977694321 850114260 855225413 573638053 177893552 567630757 969059057 890556818 510423152 479443871 432560761 519793582 546850256 566724169 325046688 511787114 129965316 352510978 336737682 196810127 171440304 175280926 716724429 130633778 801953130 916663274 60836 900300904 548711353 113066401 318185539 378922025 815697013 25927303 952560077 993590564 593558059 774135485 736663733 956497562 106095707 169224494 476291144 652945962 588465014 801337831 164733076 570946681 6365161 353987109 767756807 30321816 529268035 336997587 13471945 183737516 106177213 13532780 84038419 654888565 979115532 402223957 33810590 647328896 428151259 838887018 493435811 874225670 465538855 230099544 830723231 571634561 251840389 159530726 224580523 840305402 813384909 241829950 411252082 819750069 595817058 31525241 850071884 125085092 368522827 863543828 308822607 474700039 729592959 245377378 129588604 561224842 647601334 15915545 61070090 928268945 854802562 554505900 802494614 320341416 784605443 485734196 891975977 36445831 497781274 969072851 729267584 311166182 210902800 140519666 983432602 806719857 24561258 686020837 784321301 393084084 402081016 93143907 867784123 131673974 191037636 997372726 545415167 838638970 13288270 606485256 619424266 720607183 13507508 274435231 40948599 798112950 760169426 785440927 687075133 110467051 607030129 268859068 421633232 817932928 261895085 257582185 477169136 286456342 943603021 114006788 679540426 345684036 59667047 547324548 329874361 250704682 397213625 727805880 89343651 263018246 186807487 561284268 983625428 200314994 835719498 877090378 998427944 448405276 515047656 538019428 558872326 122077784 806878495 980505558 792527063 68773580 90604094 122212551 207746273 34207115 236219338 887286698 232407502 295886384 287127597 562281863 546591066 684341221 142604094 488451068 799875818 329411580 49735336 636017598 529726574 737971185 365624327 380670869 186376460 880671983 918690296 745248786 855266118 578085142 578270695 500309533 499375073 668874788 475038435 707121346 555598254 711257772 446924395 788005756 859660508 734051992 202803970 258767925 270909564 345408063 747218992 70785382 674819642 649470679 706802979 204546215 239958216 72427305 585217083 426334675 805615639 356423730 24099812 513398109 787025224 454886858 866223993 138916648 123761646 341262427 846037993 531876251 905036550 145478740 319882006 764697057 879530731 522685975 23464981 150440294 868094037 623200325 73742027 395430031 125187355 780545005 599976245 365145570 705488662 37709680 643996597 363620652 246649761 668096408 729535112 33674984 122983266 595759104 172591632 99261263 789537882 871145976 483653865 694574432 16624715 803535871 311787840 896155445 178738197 187769173 899112091 899348586 663485849 972854117 294778616 788673203 605915474 747271212 6335125 163920487 784980891 650331721 527541138 31630652 170944480 109592602 917821987 146444097 705351705 90413618 98221711 347405939 814075946 581875576 41980370 830700660 237927798 206284561 579372457 269182346 246570085 331000899 168530931 910055933 303855015 315825898 551245488 909770488 63097110 557580612 73690974 700594352 60428684 453748464 584741355 83889515 563341065 502563342 230333612 121209121 445493311 181071674 468615059 112085608 762947249 363111780 942786268 853391398 421912693 374675076 122573744 668482777 705675974 143621026 578538710 862047340 459446924 129784197 624334180 522544033 539881160 550541505 75654736 452826195 4289968 660396091 536715709 420147384 15475784 767049320 393872857 460969094 948120994 862487915 573054702 563584594 78116047 368357321 269492344 500028739 595548748 392066087 21027867 153741073 535687112 599566576 15788412 995134035 581867124 640122591 370194419 974264635 43180448 445849155 427090829 47470415 106245245 963806538 320134151 121721028 583372209 714007007 435206473 384009554 429011273 860777526 800110500 359643671 81651198 69602843 859672409 677199945 314185281 880700276 830941017 849872392 332783203 846729429 697522779 767166679 339368371 920233549 741431313 382548818 218599055 21038494 282535585 177360651 837361383 455186087 151598030 273249943 21709445 586804503 657259497 450720717 300098380 309886348 810364388 381749578 379489190 522553148 58949522 693674470 255769775 889890539 396063213 441069330 589136319 946102343 208236008 781021041 866335892 802183672 16086211 84934946 823222165 298621795 114811949 513099899 753807881 266409978 786349842 775517325 853214480 296125690 78754393 5829212 606012037 741635132 387578789 985501226 116704632 446528310 531692047 372474406 188935200 780271611 813543735 630587870 726373954 874296094 411608911 445226197 676479766 427695121 382677494 352218282 578833267 497489442 865318181 185157499 763899420 504184374 960674823 469630251 800310063 891945567 475459462 406322099 633580699 863038250 244339676 750285330 162082912 628548074 975276087 203534463 408819684 641336174 834122333 987709989 515632267 98247595 285452537 44628384 525942715 668130031 249363018 104775981 18135824 114681198 142449831 634551595 471381923 103124653 104181846 271691985 847586571 432157659 530530435 333683621 147712261 774870110 83968950 162311524 255934535 911761389 365845986 664754218 553097562 199968318 504980559 921246180 298215912 790433095 965874564 676674978 311079477 67753933 633967310 329215301 34951482 776417140 963766895 506333404 732058144 920465092 778025388 579644715 205139103 161072174 913328335 205367715 935942283 849813637 367679238 44393169 614091377 733525223 709147386 19705290 933493541 66644296 940951469 84225804 857077391 759342384 760900782 168156867 827096316 247384443 349888519 862047797 23801583 166171766 368381200 755859726 86636857 998922939 188020792 144292311 159995112 953865479 349660025 948453746 656195467 717339262 992846914 270286843 303380837 554510652 289992132 89390729 621154947 83459952 173616532 478232337 842802336 787033665 498905556 669898651 34418108 848794074 384462800 58219690 14965839 752843999 666595767 954119048 604283290 707132911 98411358 764278401 660998389 300587735 565248499 169710207 870443348 558095412 439997049 173824184 112606063 582505532 263214912 586277362 665965483 289347796 64509698 508767818 76381460 415931605 31182821 110799567 264725679 415645620 21535608 132207869 21005970 540647727 86326916 625289259 100296989 37254626 242084012 761295377 190358712 807332510 931005583 60802059 217944273 223518983 87142595 183066688 806024514 350357506 769344049 324506348 639705301 686370098 833274166 568603113 102301703 716973338 531919031 219543733 132618957 405970991 351751601 6141278 946618717 290594869 483946889 46915705 327849494 726030900 660727433 518208205 385879761 444249367 431526615 456340385 520284701 518669209 639407072 178825566 869026715 261267472 503331913 361248367 800153922 189122430 929851479 754971976 906095767 314286862 974515708 891231075 720257852 178783660 897372353 519392920 469378528 233835593 418824976 649744373 959866492 79552408 20468929 198262604 376318126 451995544 654602988 896602826 970664752 146526412 75428391 692207818 260310235 431276655 53456185 60464156 620399085 835824015 815436131 526494851 2627228 642468190 270242278 722885079 673768202 20130982 242277998 143146729 253966574 661102973 645407454 66349417 593171732 665876382 264612020 822006209 117871925 771731359 571125386 88536677 918257770 499070128 633260846 31084357 930346783 539233382 91548512 550745867 227573749 759500995 929757069 230200976 254485536 199999346 953086055 928253737 220130327 47880404 923916818 474096900 708983377 569324271 540446316 154671460 87717004 657574687 976677669 205588929 429306046 400319406 146641957 200080167 899389534 779902802 231164523 829736316 171652536 175229387 232998534 399226284 934730381 15271954 629427259 189215916 215271300 582513313 117469653 287917978 630393717 893902822 762014878 191893445 315743444 154977545 199081256 403460447 812552232 28275276 609049375 94374629 428594682 608207683 146971147 327984215 240626837 378135670 10236882 412279372 553365056 95751767 811505655 340611788 111023720 440932913 529827703 326295019 875962578 499813707 614212997 358872646 246232880 228744226 550766090 561976323 236238122 749847345 965436770 48790353 778122621 427002496 995681333 59233654 35210179 142652480 387217868 275837015 373304501 249971101 688116386 926669556 345722867 352138392 119797695 456746586 793071304 649625397 783041605 521550233 1955456 249770953 880422878 248188335 331031530 283705319 810164658 567269651 33552664 628117779 468576356 664191636 55120274 464257688 723425289 90330452 459426519 963159508 218683818 832731019 213130608 759316555 611916926 558853474 111454946 731714620 15600059 757042602 233856369 651158015 278592834 235811824 753445319 11532064 336516510 84476848 295237382 146681167 651746499 181306397 627315297 120322854 845498032 682435571 437096893 421439672 625282374 896523412 237115531 696482544 581770782 450246138 455799098 193687708 861615963 419770396 925402327 729732374 176812997 11775047 233406740 307922182 247586870 986852059 319454245 584103380 71328906 614691627 583300898 575591756 795998023 63132547 548430961 494012407 745568117 838044206 915452078 223366842 587083969 5083961 919849385 168854750 455330098 228164835 215058809 169462413 647935230 140461136 899194786 677264578 4752534 132601525 985186759 252339404 119453583 304641004 688959135 43298841 919332630 124776384 471406948 567847004 187908930 872354261 61859410 933477046 710398466 829827840 9360240 149998786 834911800 781725976 318853535 142758249 9890810 533912344 312220661 510342391 526889831 211415446 40123320 531642364 196533323 25310079 636498119 168503257 182467434 325457253 64318449 101800063 450233637 535725397 522163418 638142566 260596009 584022828 424135964 970994474 266367019 286012555 120993259 101278818 67738530 292363145 244037066 930145692 678791840 556257727 293004434 58198022 620189524 333127754 589840386 816722846 358437832 78854856 985226103 540905265 404312109 49544551 495221679 707062097 437786299 17385096 197721014 698382307 453924275 621856977 521893132 720291293 907869531 495402742 674086462 828124413 787765887 918123528 758270104 319074078 326897606 51274537 377272100 947087129 236918642 967112485 616326327 595356473 45967340 601552429 988778089 302795800 503613331 336516119 9857896 941399630 206417567 60095262 639781936 660341841 681952238 14191420 233149486 442338121 509594161 907235947 122978885 149876399 677875826 881248988 468950477 857289783 785039876 846222576 656893264 21958518 665851412 273219590 469831342 564335103 727288370 311125783 867130903 230901700 647641901 729505150 24817681 854059467 789600411 664599617 366917660 324069001 678791036 600067145 618923473 40901548 359819443 741902357 190777947 890211621 475667696 659728423 747501403 113223923 505950998 256911018 135182440 24318761 530130607 457530134 588653863 109935328 768655916 308301117 340837028 268814168 37806267 365654708 122873635 679923029 882770676 489791294 856508381 414078063 942374790 475431853 454979611 154710584 69850561 645757557 44922204 545518256 305485979 644939959 658742179 663953328 901850976 646440970 688272088 284497935 103971103 276925950 394433262 725143370 585227067 735270289 993957538 475549685 953441349 969347524 7989065 836212024 311655169 864497446 102806439 254029958 192445650 557786049 408740541 262296211 203543605 306179097 807814466 361545935 951119055 319072996 25499262 852970030 965513966 713771349 137467964 922001420 843213650 384417578 499661142 280957068 119687866 346135031 756506752 925645566 315482554 617012169 614373942 627137722 334025966 717180380 733684031 526471615 274966428 142424571 641284177 331026384 301120019 301614995 692572318 252239073 620687990 718071579 957725455 586201955 284359279 947709770 360719727 127572928 332127347 860380868 261046348 304331565 206515898 17553099 82493482 374514803 487081619 696867423 1652524 821107584 414047802 587852906 200095551 541530581 582793828 841379727 872556964 883913847 142994721 565129281 136152919 763682711 135717211 946394725 202401017 272592841 894104495 563120743 252682121 78748193 276017962 513728468 235596109 482533859 383797918 318089591 857048661 870879537 14957013 711217536 691987120 281521167 151586793 892082670 823051747 734380621 585978749 695608711 618294467 728973469 113254343 606963737 345172531 101487906 405874814 400089900 374080746 152495660 963210642 626762866 231243852 91744956 140491333 466839961 574278814 524289251 784929551 283843827 247685139 652402915 847577714 939672258 933924081 999164507 684271280 756975828 733545127 122766380 305100890 204355945 851739848 270871584 663836033 49428731 372359489 69710846 449518630 746440235 222206505 265245623 373203100 305966709 356990578 366210785 772806669 783785744 890500035 410252571 67629570 138185173 62655485 767723635 930373782 849095918 766888141 467161413 458588097 352949619 589927792 763688986 409821915 294183992 34560569 73657948 196129074 259436410 143368793 645647703 5876644 218091650 763409677 231596095 524058358 120400255 597806879 149381378 756702350 340823265 412150300 676848271 331524789 327322136 444571905 114414923 176418053 63976398 581576335 635006149 269442368 24020479 251211486 679264283 170720822 138288407 752922230 366849895 397724816 748807374 12497597 256117811 819415375 628423625 487713905 195990084 601340231 85520784 345371461 358042580 426344048 757521760 34890850 757868837 84843896 331979107 872283759 113778300 248471856 306376445 601300801 517914223 182913275 852512286 197178505 353634096 843317044 802617086 720483990 93558211 403940812 585497938 349676021 223356186 213921563 837389926 419346270 815261793 922910709 617234082 25820725 201771108 227272194 913227926 812156296 164632441 97723384 536956406 278410740 346195239 843332851 879711540 864109462 26246125 584740178 61287966 232396573 280573573 716421404 952880562 374131784 120362215 538378500 723807804 196234752 604816414 561197729 615581021 272594558 336624789 85331455 298415282 390912249 312603648 64159560 203068544 477236088 161882943 740024950 755646827 508078182 435874152 487874719 372187643 314636628 925131248 285991960 547033200 205704820 2413363 352430114 579836603 975291929 890808613 156160759 171526681 348141378 717358487 639624053 620735935 906499628 724955507 919151217 297411876 37559154 983310776 352996771 514795241 145193718 93021720 122958420 505788251 381412223 463349490 877975893 548565203 388480737 16484205 95598402 446701908 871413919 300544867 26538511 846705848 43869831 35215621 870748880 392011208 752574107 510372932 12747143 511590086 87844791 784414711 809001961 125403944 620241838 14515084 492715537 617951907 107536803 615673956 123740158 341465378 79023445 854232402 890030580 320020533 870716606 838145333 766722440 594646877 138690200 645777302 293869076 35076382 680992922 164617955 427087590 286083381 527507238 439834732 797673466 615352028 76765794 459191779 740755972 697007631 473706862 85987860 314959537 433760016 701661815 291216046 627741745 633201611 145448448 370288676 805738495 868681405 60950361 424977286 463328281 52156912 70754588 757197356 87233293 604263861 774331662 514320882 742863593 301838900 954155613 393053411 917190927 30921406 852245189 510463250 580445388 178468402 596451109 895404925 464744769 150629275 39137322 92486514 636347237 184585769 462775189 442085731 53267174 523725549 867063017 369111806 575882460 790333956 978825514 663115753 247114168 753157175 29952986 989977761 907512426 984108599 235547523 677219705 867546356 87792711 40199306 300508096 118777464 636650415 48429372 583522232 639796041 87566693 528525097 276143278 272152462 991300286 570745360 177935987 367542186 290324728 399564144 795940998 80658683 378389657 311573102 180289203 984063184 341526087 22783315 891575609 178151037 258330837 421311665 45697393 198639899 461510971 198721840 169933714 98161385 247151211 753455945 590473777 334717903 134497394 866617054 606870364 125797679 289878766 637322702 345856216 580203493 36886846 141797213 513378528 267792854 305886666 693667730 251856037 647412753 568967396 995947998 825563789 827298232 417259662 723777533 878454482 878770632 922499372 48388195 829448368 169650582 654360491 272438497 504368485 788857884 139055550 963755200 767171914 281450667 601077902 113028130 861654160 490481099 107341694 375032687 758273952 265744712 921216768 10129989 913157464 490184163 858594338 738721252 169998746 128370351 315015137 48453227 7140983 237514508 949357773 689105702 259681442 603718263 961544198 764049926 245092499 953116100 580321477 12264412 87083118 33915730 977808893 948737277 524396828 937666939 176286315 282670780 203411650 97503082 145317120 116569113 440203596 3911457 707806716 610202341 132281807 22821852 511171919 991939141 112852712 313046043 533561195 372534153 916764306 347621744 989100430 14373156 153254195 569421906 26637567 240337313 603337636 4446460 41590941 127734463 794629750 217877256 262921594 998041399 315380337 260755065 967126863 755583933 117182873 527449930 218302625 101981032 402788134 581990896 93920172 368157197 895036938 479997718 740691349 664317595 680135814 582308130 678690750 833390008 4246387 705328317 926243672 607584022 562291128 967834613 587834837 209437229 185711868 703272782 59994979 353608556 964027847 27121841 109192488 81210719 407088122 180011465 183191750 662392607 762002360 129628274 30549803 509555649 462142343 623757503 173873244 142278156 206065632 852563993 828184516 210312019 410408661 754428187 670412392 825216140 574779151 110763580 34653368 760491018 814036362 94648346 114099574 778064208 974286538 75808413 711791278 233891012 108336229 894983028 896283618 722854940 877127653 926833421 232410589 339269995 403107275 258800184 334064503 609172907 111364176 162249018 672001277 374289189 769193556 342413668 52021680 343972707 453177248 86675048 956980076 119729961 33839745 923596001 897794168 8126283 851920766 462101797 242017294 960256994 209601176 138300911 535628286 86728828 917650683 768038874 278515175 173274310 26839057 612579677 782447216 990719584 774828694 306964844 217525124 396538601 649378511 269546804 740511307 955072110 208738203 550007735 74802070 242577947 473603735 825112589 250704229 178040852 287214386 345237874 138297846 496815561 336055137 526442483 436060741 106222171 146997708 714575915 279496480 26353116 327155591 61943695 17072699 954500636 221424890 87114175 351039236 870803401 209177330 944066895 678391862 417915532 494074629 753193932 660493478 820194715 430822872 911197707 998235567 718037257 108951932 989049764 67369170 445007068 515492246 503429910 551229239 662489953 70522176 830725718 688843068 397677766 745185765 558432118 204694753 966610654 498062644 555733988 689930406 707239973 352317234 368322268 125155504 846391862 974032551 785648982 519102929 404855422 549363040 517338495 975409031 658314971 358904610 42778200 103322039 874396855 398724461 507067629 389403159 469246636 337793346 930762578 719440753 82979110 341711047 924135505 902106116 839773691 332385844 592036521 547013663 684703078 812875140 524685519 383611291 786907690 162850852 902714219 44279464 712213891 272569065 19688494 223045213 631473674 914983045 178883603 358386880 166223857 685951231 747790038 487986844 876260929 531068967 207427596 811756390 872780014 131563100 713862505 712553704 316465295 158415378 112083718 1168372 971290517 636769236 384779663 610714559 799620087 140010233 507510374 364350329 412579298 379715219 439911894 44052971 147214615 618795496 402439851 313438471 157263079 2746240 801425314 33524007 533815207 861369261 697796748 259111572 845448712 264175605 971665275 161914006 422590982 936265344 15598730 246397850 425550932 400378392 709628760 77687370 540388624 217139133 442037699 952967921 596854351 881949592 849537244 744068965 353261439 104493446 910023787 363040869 107239685 563965452 249081227 493571243 425334712 946877975 752682814 123299775 211053579 576864440 285213781 486160912 513129784 300812510 732558761 938680715 553707253 294703873 16368084 94095876 511843005 310922134 899580149 961213708 45388077 601633744 557799024 251165868 706127189 467822811 614206736 813366873 31788262 863287963 159454468 309639326 810165937 912137281 432939100 873735867 489001721 570669232 359896778 854647856 871481741 944971890 645844922 277705345 239675762 514729357 224317573 604035119 825651491 123897721 565248826 723555919 578047816 123047849 974721786 284175004 443387011 588928522 950058228 327691625 304732836 109512695 489847302 114898772 21649976 922786401 841150990 363168048 345971985 53564119 70332255 69970077 998536008 716177176 347675422 90728122 230906532 571992994 694763240 909074374 548407066 112528417 632630293 126454881 88092617 459868430 263146236 531479628 48796951 213204463 711687604 206046138 175233510 201534905 173461261 49399837 976837657 14612250 412567884 322809641 68176368 482900138 392779718 66712376 51593665 740455139 9956849 282500196 164964484 704720088 44090922 713371549 817248504 676721214 839826429 905341120 136589643 102972664 289337099 37902946 168693478 1024702 96465435 343926987 55075958 269926696 393326823 31913615 284538945 658411058 207239607 205231665 141311195 600019324 124460392 45421211 192990814 134417240 327921407 357955297 839137327 372012328 71326845 656385830 901249893 763669625 414243301 890355887 719158640 703580400 780775184 740368470 704605101 877240619 84295456 759681059 147167314 330138631 644111025 284222610 988549688 851350631 489454274 982377235 303886307 613914665 27798445 496877120 748331904 208236203 707348769 587469230 432764882 631191965 96371411 334014774 247377942 510614712 76887013 966536581 66711463 857662196 559421402 771316563 734902814 496233210 383513973 734586479 826371840 27624997 18809089 667437879 731491980 508263362 502331465 35378286 122178027 382646262 384771757 723026282 443398816 92120525 163011864 876163698 723312490 259383274 62694823 970690431 622514337 139581835 789743363 689225799 997244031 201681117 313058714 584663196 697914326 696572686 319249675 376802517 576714035 190575115 44240395 160722366 698838476 399088212 196100651 673532854 634250825 580872407 249075488 77649640 525509284 412087351 953813337 101338125 671470624 16508160 72028555 146501313 8606346 714288269 835727111 5850376 915969385 148785824 590513572 466400062 697874862 762279598 843202578 127105248 952854712 739959325 287827613 504209539 139047536 483928263 30258745 625814712 917317021 279334232 703464351 442826304 691421582 509794040 544164428 215408557 378818551 468709334 361909869 387424896 35513955 197636980 245791624 803999691 198939155 836305195 270399753 896814016 451101144 113602330 23919263 403955855 706078006 311746875 908165393 697641893 648191489 938424137 323456604 565508510 70274720 879437307 860851165 761696301 241747698 257531945 977104858 620566248 726241278 339014726 860507495 614271584 389168057 106299118 418271275 588107212 795120664 541187379 484921227 246221807 507306060 361356842 502694013 213384066 673103716 263375758 911025958 173811557 54316246 86998914 739320066 124590966 966436220 452687582 886287266 60700269 710219526 863392123 681266516 288977156 54923201 394290362 903248739 444091257 500589480 174036365 32198468 148226495 715223743 369636047 394448302 222529803 730992888 897142314 288430220 256612955 13034423 51972529 430424511 67350669 138971442 22260928 191941634 957924013 474948510 78228899 18624281 37684387 794137374 552407148 326661542 849060574 946697510 229910281 145668182 299803341 403946645 30383002 448029835 119170388 252535400 842478136 194216542 983528287 592136802 482646761 92657593 605171224 534619289 375598456 672521892 526107083 397859383 864463525 484031095 725324244 795208776 355171728 763008631 589346149 907578875 89670172 290923074 854276384 172096804 289107607 6596076 576043449 319490608 454625911 547730188 572026007 149620398 594463081 408070645 741757199 77109841 353244590 199444775 464245481 728843045 724483018 990352563 126702427 441462895 326900010 704543023 236671670 682071737 467551653 678534170 442166963 409738176 969457243 148959699 581834980 111081201 155555774 10394780 430571809 610181684 558124967 855114167 759802082 5104399 115701164 354075632 82214239 468945753 553520406 398976071 197788797 130519776 241844986 177007575 571982670 421261347 881550597 808654339 103333083 201618601 339704860 398016397 611356777 161678454 546976095 45708108 272759654 702531869 56102887 703331462 312713552 614227853 410961981 72515633 619332251 526663144 279107617 554062841 995608896 832628022 805555263 45914044 963147797 47400248 222921618 387646818 321177946 956988567 48817508 277027380 11123519 388522367 675043777 622480295 550200820 222019871 668188402 822960474 924551739 724291288 378808287 89781643 191035492 789770267 14813627 662884094 316433410 293921243 69463286 164558657 979065617 875018549 210472700 794729765 774935148 433394318 182376583 96113094 242899236 231194090 373140473 254022754 619716457 48184249 876503049 22433628 122720472 397207802 845394101 899788562 974015442 224202388 989570204 17567285 13972654 856900183 680451379 182922416 3337777 749914664 347481072 982403393 624933212 557953772 777133158 252384712 843864441 812026092 348497805 86763676 43220181 574154629 340786429 515452989 474855230 69805829 537886617 597575701 319529983 235797069 349880614 293545424 459999456 191967170 311112708 326488462 48867352 991564086 361927229 52205128 593995102 709408300 34608521 71444665 119878423 664258030 323829376 963742863 328800473 672327180 903022890 224537005 98998161 96325671 739989994 573853390 166131499 130392962 23945442 485661481 366190030 373826055 631723256 678705838 565793224 942835964 5194299 614660575 786916401 219637879 519382055 233427854 929046178 406506927 304872519 901440953 70764956 628701894 717700167 252081780 153545426 620723057 476618784 252543586 717048727 69125129 826396975 735696577 199518090 850342416 73874410 418224472 224168470 705597665 96930309 789961694 500949980 954640959 257138620 140382733 174278837 776520674 373810586 955841366 35543952 678683104 857282318 106308907 307384998 427498837 210907038 460930423 48221893 687525822 713474008 617786971 756650950 392387334 205999899 956169040 242729749 279874308 226909863 319414570 985471973 323840171 109376263 486421952 130997481 219031235 626804684 305276317 848068260 615270 113634034 883612212 531814725 970916352 842437470 839199722 250931540 53344508 152646496 151669784 740870329 718636855 769456754 350037630 111024188 975456652 158723021 206270288 107847312 385632883 525684858 93319284 709473053 487577472 432257587 840470533 706608706 59062271 998263201 407193318 912193892 111897235 290805529 296524968 935329938 133242998 135724690 186261477 39103857 140887537 337931260 632490537 859524392 959904365 982528167 823064931 787877368 141251187 29335219 895724679 526884070 555020076 989043962 88873474 42597547 273817901 781860359 601722605 185396523 780123559 8915922 97590414 744537145 152237802 246631733 679867082 137997151 234872774 718644910 29617360 375760311 56576169 662107896 87801054 868996885 644636062 910865984 656874253 638403601 792717554 405115283 17804022 200253981 246675597 106677495 95367880 520493497 888537853 697090484 705890019 521177764 558522757 655996784 118231260 563276910 902628516 798098342 701274060 137501290 369259603 730891419 365777952 278352124 245515667 453579005 147349008 890151728 216961340 656739612 381071680 9678894 61854895 398875701 62449226 308530491 505553196 157817105 829023987 246607400 854907588 387430357 620301515 265946696 43427140 738532775 829223605 946055655 389147468 383014017 936073296 758407070 966421787 301851247 36759193 211937453 607946603 36624553 954605533 824907943 693364164 335677212 687103188 755219058 734552913 749552413 916265900 92622460 907369518 597806238 191746211 614793457 985236594 812047726 733256505 28663733 550580500 414996461 827235740 939727967 798010477 615825387 550651388 616948616 917676634 587410581 828886068 378139588 624035133 636007952 55563882 169915648 971685164 742667069 925134706 558754428 344735834 693916957 503893239 104621703 291723195 695639449 571931511 129476140 507687174 305188015 10656225 910784025 720184476 837891964 703028343 370711304 306233702 253679731 987659919 76426687 693606663 669062339 454566275 170158147 157586642 510130156 340073794 129271805 105313577 117724851 540542584 450049410 811641808 44435822 407187464 103365002 592591623 979118974 85357493 100278796 136823341 96013717 863579173 857007816 933905680 566607515 80235471 92655734 672803597 920411742 169082420 366410259 441990432 623648694 536568405 599577073 133778850 876642199 581365230 239092426 994367049 121907813 541658187 658525208 18859987 948845650 614406561 463967961 927964623 699764054 416763108 64787963 795777770 280342280 774312130 582199802 699466147 707063953 674855535 372269743 627475694 843937954 591196354 69466125 467586648 127764758 521559549 453881849 856923308 102924778 692974274 703806709 77348943 87148812 214848268 948725281 35994461 829254829 412693241 816475435 529018882 829456348 733779750 177313003 962314980 360608231 759512804 661781126 67672183 434368338 886567220 547664228 130822644 477763573 469646704 598409291 458044683 991206253 52291139 167484342 94131030 597781764 723807402 23996324 684930575 938655670 972721604 573441387 767910498 237931196 389916821 149445731 919903896 123696570 326758733 882218875 336821153 86271537 396516352 404493335 373156226 135599923 952157563 503978869 613363496 274320618 954904511 923924530 265526870 859712001 91408871 212174252 310010116 667732625 88686927 994940690 606388294 61408531 420898428 226815143 151856078 810815249 228777225 71759973 787028170 555535957 806495199 123849322 494323845 55527902 380859009 719996423 191127825 185532923 76491643 657007672 459853540 31396154 580932201 577896762 891108154 524857423 790071013 53634622 45106399 878757939 48575311 651494692 792682821 321990091 730826186 797055251 132805339 959603410 721331575 772349860 367655719 380343126 748715534 861979563 435871027 982090894 434492337 479515203 20140168 510983980 136522874 479993707 542380133 569971426 57890468 286004638 94828849 700477832 339639259 139935247 431752123 240730922 643946291 76951295 562721012 227288828 874006545 548042702 186892238 447854472 172908913 554547956 828197597 774140798 269043870 116584975 756231691 703536207 596100178 776371858 67036538 732623051 108881917 609416670 155110829 19288736 747937659 102456029 572282920 87576918 94907627 4035042 180824191 738853917 933502688 596061554 966142745 660025585 144104255 5551334 107880056 169529519 412615641 936077652 943670317 681659510 52662626 552418359 237712068 501279155 181306569 304748605 86418558 142704837 766681626 241529386 161993572 514619285 343985414 734276491 454712554 438893040 590827884 488053096 30263309 376846924 84114649 996406053 36872508 80735255 854473738 144752563 102781125 267089378 933346566 46451441 801265239 838525543 451386152 38977307 192321050 485209072 196242263 278739607 627913908 962923889 520268992 789907479 330059525 864254405 376700322 637288430 303147444 820044557 125341525 333410752 196891480 61972525 182333156 86280339 142707779 36806893 83549253 245488903 156412622 16895818 144456696 957677861 707937713 448359199 849171519 900258762 933568270 897930133 31514720 561482177 713370373 551783711 203906007 43429897 416038115 433122680 533234678 571701910 253167237 658576202 905112662 302575068 720548726 939962169 388855407 715772856 829285414 472404659 961261759 985698035 341816829 958234806 795892247 49754541 406594004 497580117 802529654 192678625 248026602 834044373 754160801 961396974 238344435 810583159 857343223 654382549 243705839 390577900 78600810 349389427 901670454 983713471 651964494 474735531 776191992 40819900 190508387 605477405 513224559 4286497 443691791 855041387 962521302 92100390 757312279 221631657 442196858 412358284 414310281 690223459 98919008 20987433 651620433 337263442 831570591 361480007 844162342 927792781 752057906 922763151 277182207 506244711 758992974 929146701 980980242 535184965 822482952 24004980 993178721 188223862 28291476 289386863 43265248 843329129 381487252 653093878 64960785 823684110 917968513 331787417 366423920 16887520 205291201 18044352 206667313 36861791 232040710 50829654 817170924 984098616 826109157 94353130 342859678 585102130 876016182 323839919 972803446 551015486 347844898 965982166 739239347 228652725 107885380 635020947 71981853 489372632 140631176 989458989 165573093 58599689 173762757 531997012 928003560 379053957 402557716 134670873 268432100 634598425 38016878 85603023 471213392 716642386 32472504 814073070 154260867 761005038 990429340 127064312 312020523 190790590 945562829 51259869 419443314 53448209 538797167 491425167 395337192 679428343 333400507 560910284 738028031 507163264 945423647 518547942 886217220 200497714 505735166 154649319 835096139 396268396 92768693 158825882 112910781 125241197 825415303 267171648 886246234 815844643 246752311 50783108 6635232 192315140 954559328 278594897 98279700 493356495 770020063 493616891 25301189 103420570 54527174 763329219 463100185 852467172 134393512 349317404 52964886 640128678 356483075 740577376 36397073 449251767 899403257 1824205 574492963 577334912 268995852 313255548 245695906 515748163 216555007 104847489 560579654 171114335 383442385 658859353 516987181 5978800 152476243 542288369 109399369 59519768 158133939 425015905 911986939 292527450 774333308 817468176 932656127 130816382 558045551 969053199 432584501 309965160 970877404 7077463 887300071 92389607 172849363 132995976 460654121 389404369 90359816 21233774 413035055 473802200 680093126 930022235 479780999 685085720 472310603 441696719 744605487 630444541 866712623 509108778 922971991 493562283 179093305 708144469 476895016 737138856 529714020 909479516 899620367 353107775 769073331 639436789 445497381 941922693 624949116 906151502 183843413 715308931 779901627 596878468 189111130 312511105 379417054 668892129 997596824 851727657 110588847 594718663 334688549 829817822 103827440 110176891 323380104 135437096 818321360 800275119 872575951 200551731 562270987 624712669 553659505 331344317 264149457 999156885 125783361 889098572 757824738 162143125 456923854 390242717 759021592 646034984 702753821 138438646 167443464 700350644 842682654 130548662 147585658 29887554 960366483 103929449 140064445 136262938 239366545 810902156 789054409 111942495 11453886 351325395 589171516 417629742 535186063 853320972 269302978 660969423 594935896 27127716 823112547 51859749 269886784 434650491 550411084 972640604 425605488 570370899 525507599 120804493 700919561 673093257 3208398 513802395 777022705 143272842 502581685 16389249 806691349 291636093 980848096 670661586 495477839 570019611 88291327 30663901 275856934 210110657 544149675 723309181 89754724 219778573 627685282 359641507 654429063 30612717 332282110 932550902 600983616 857789708 53355394 154419528 383399316 56563792 668221922 160422021 52352985 23319958 29327621 711560686 314956050 10175716 234738623 810433888 432711678 175546302 693614140 708568612 385656958 237763814 284394144 475411681 457542387 912079425 835053187 964487801 942692142 19851648 897038703 543675757 730157707 802910448 698095284 113557023 711990591 218833557 126495395 616859928 242153515 155823015 180936965 409625916 165998731 268191939 72576156 598710408 443738240 766190295 159795371 681911549 3954109 444189515 9839581 314012847 208785291 844892767 131016999 151477432 717260766 28055701 547669540 447418473 683482501 98281175 413491847 247989443 317114732 539987241 717365722 411784598 695810255 898302686 821410513 861808985 19010977 893986668 313035745 462749216 660176963 325347467 144660765 516647423 769536981 7016697 683176621 978322272 851909464 814193619 982316055 421686581 694765672 529985595 869105053 230764524 628266769 135113251 478753966 797897852 675100491 48636040 209682449 370910746 946938725 31092962 85236082 965949701 777595981 250788178 281215269 290289295 576135645 278392385 806936717 198188977 285409081 342629689 29027600 989834896 156823308 11343655 411521477 851588979 393845601 133142881 82353502 22112369 268256132 413623819 672526573 943356622 462259858 882209021 166783719 261714935 765818334 104536153 80180987 395930667 355324330 213912607 686219961 931459974 492304991 345673030 129648951 630230424 688302718 158676550 620065319 845126025 22536556 884103147 549231355 416382156 17246028 484101208 291010877 138018511 750241379 963537449 933891484 65017588 698262821 100675203 326732522 316597507 57727707 259429861 712528173 413052036 473342467 398748133 344512010 965647458 744421162 326677312 448394233 285240232 485353861 68459551 130366256 507890417 805079050 532113963 924272572 674841429 868731522 67799800 812859939 618972900 31337248 599267774 683990488 729600069 552459328 863239361 46197575 610187034 122669221 611242099 23239070 596011688 9990231 220267431 414175497 606927745 546944742 862569729 892167976 32298602 783545631 875050583 392705370 441141032 259680897 169494294 115982460 128412419 237294093 781358750 599901670 121147693 380626524 136408509 850747761 933085851 999647870 749461687 395789237 974833442 213220137 419028306 423361481 75726719 639295736 837536977 682654463 38756829 552623057 427338790 71055430 188685040 154905725 316277152 629826071 267102973 338287797 598324883 248031743 575581889 379683632 847933413 696729581 612826507 836858273 399993693 398428710 689022494 1971731 794217946 663855936 215191867 65762603 87217416 290918586 705058338 777270745 826089400 743815166 182410153 105944542 667386947 223611544 260850266 836180450 853437615 527953238 174468246 304278849 775984981 602566487 683962480 476434745 151812419 149305339 165809369 551806112 547734048 854831863 406294194 341951993 371204150 621486061 407714595 310937917 764920998 965289284 88208661 591010397 561620801 123135166 696954938 81524099 346746709 810321555 917704549 52700675 190791145 92172794 356979523 966776125 547255632 893458355 295727221 699068051 42763693 461536589 103390514 590497740 168884803 509684707 784966084 540088952 131170767 45197030 851026869 748608116 10486313 791751881 192134865 572107113 914887046 889089802 653631211 114150107 551927709 423852111 19367133 742718853 368541257 376346656 562011329 915796888 122321362 857738549 614864938 165085054 171791489 718255451 608099145 340676292 80456510 393065228 880765243 64143628 438262257 584308463 812751744 301264921 376060344 4886608 873372033 143463741 746492761 379519595 110130199 298420469 803371706 129497332 41139321 24429314 505843987 455667001 940226201 628165348 165921901 407607491 645766753 337713390 125862941 253865897 530906033 58835802 499447476 264187627 122979430 937709732 848496090 935731173 91491004 77072785 940617780 964863036 220536525 539626892 196898982 330666724 838047361 852787039 460164055 731703033 877216352 818524393 39886386 817442553 299206092 205808286 77566395 944972844 543521675 55945687 51355092 74427707 114781489 550802567 191131686 237760918 341028650 39627775 173492090 432519653 116700559 966626221 249899040 189753435 506253112 446798021 520420158 196816824 152101412 833100564 781036209 29317763 651624956 820922594 699276667 950831047 26730879 776843061 748320242 422768906 832788748 799675333 349712964 947570236 350477899 540844649 185331153 691506548 580472423 211339594 124026200 549689333 177965814 226441591 739442768 536735277 673239612 112379277 733552101 825341023 945479841 367104661 707175137 449621148 188027254 406451804 252968547 67274484 35811216 1288788 490043389 868599963 800964121 839756353 816170198 3958371 380601001 854017702 547981271 813589776 65357295 524523822 363279108 95839460 750965413 102721875 632574737 276721376 67617504 218643189 102062398 13097344 585747849 661753886 462718491 773775102 68205689 715687037 841049585 104016905 569492177 183609326 825133219 222972649 23365678 493819769 226931019 256483030 347837470 774912289 70072805 265711117 151952463 285868265 361550576 902917875 241106491 994125312 179639250 308723994 212768500 134217999 321821337 798516348 795971884 637056180 424807801 716693925 205259568 118373738 673227181 774751744 301983063 350876751 997724392 177865092 844696519 77171763 434348121 45050341 852084051 504420926 310761457 4036513 790289190 672312032 759470739 31395680 666437344 939109988 192636026 731722195 925844338 514457362 382754895 574332574 4029893 807562695 143542850 209289461 778452784 816770030 984041204 80435846 20163132 981765596 110817289 864859651 58937358 545165410 909909991 763537760 49586335 220671447 620090625 692391876 892983478 232077715 576303907 411937173 23704055 768939932 143659368 949548392 135913646 378930614 523880965 139943538 39009660 667423814 349232998 817462444 336710195 185790554 750414641 356873327 20072501 861231930 74249329 79009858 406397339 984159319 695063969 308500025 57347117 167670945 853408252 950330594 399748660 282228510 214784119 423452714 51168442 210959838 225517457 39598439 589890451 749398422 32058328 628900110 269338587 381291326 298878905 458565134 567081879 49293546 815438460 587154379 910525475 889687788 518680588 169439165 726363458 66260908 330455541 783710574 86448205 183863792 586557519 486196864 466092301 801341637 762165929 369777094 864817826 987683385 261891884 307224628 589598158 293950212 936124738 858936745 675241537 87519994 170018230 94839767 136813539 985456689 534510497 899855365 727660828 53191084 69294529 306540637 971968343 252266421 90251210 58416547 436130212 676808728 397129762 754738865 330666717 159295690 124515958 48000894 146979075 238924194 355225522 589093584 532874405 143866611 300546680 60632293 231386604 470564909 155472059 368200143 308537949 689982555 120571859 36198776 595689990 42382740 195255764 420174684 294649160 285506973 478591231 730779372 814832053 875720992 338034588 145498769 887533034 315066897 46016014 887028460 553991090 401241535 476122043 86865494 545108145 776668723 147497786 776494749 99749983 155486196 144694891 408287932 845468750 117783101 297003059 293675091 160165840 492258823 713849775 454815000 777765795 44957357 38110723 445114199 773194700 376145310 443129319 660727733 691212206 489145333 400272544 245203296 890386867 876394587 184585141 435495012 505579661 332082927 64506112 605329643 487569122 61717354 13617574 185554224 179500454 163136985 331745666 339666294 655395807 45595440 794481293 285677953 943069148 832592015 730792152 716263848 208737324 173921470 229507932 899949529 663066802 629780476 997669176 405970021 358691414 182254317 841465032 716787426 366853595 905971143 174633420 854422716 967688496 40767346 892493291 147188949 203904330 224238957 339371594 859300136 122350748 133852886 144978088 65419896 966444900 875770239 634200095 27698575 902208061 716224378 780164456 417791214 198521205 777833631 823761234 557212618 812604299 517742617 126516395 179457893 276230111 301149815 886396961 96434958 341917160 778890251 96140259 545821489 855645559 435511852 405121624 977996307 569364738 402616063 895932554 388325989 130902654 382649000 268540916 33110714 98873377 48705371 450901927 149910934 679055353 127179513 707123551 491659652 644922129 833639946 523633896 921152240 134789760 410030856 17587197 329223271 41437459 113727455 875044759 897083017 549239307 132682734 727595675 971120396 535298796 476044580 211962736 666201449 711209931 480503651 699312162 662599660 529209021 2730441 812510593 60780726 129909953 372150495 552440377 774832081 58306792 76074272 548500672 45612903 338621480 566087869 374836173 232575290 532331675 249880931 129658306 81570981 382563664 709770333 905207728 917862460 38331264 117170464 436580260 749541195 597674114 135892422 264657206 979399487 991139214 77167798 40180212 121049166 449318292 445136940 748397598 507625084 373727563 149414622 553237986 712349042 715502490 928074159 944924331 100350516 30471441 927098989 34437849 265551457 489385673 939645576 35930268 380233288 56816039 472510527 129774482 507006505 460919300 246948039 338922343 452058513 324115836 379102554 425624030 625950480 824239493 26537980 133575563 50483407 175952601 539329900 762832449 743971442 319920410 560273131 844321957 202908203 339888471 878759805 468459659 681790495 818405381 504389926 62023783 727737771 976900452 44314616 87260627 437819752 291262655 426182969 742394616 467894842 657801874 20534998 93845321 334557718 47072977 79937235 385041125 75541929 471783487 389925 819513370 791703896 560663055 663835326 994612098 753067878 395111483 315588108 434858372 66033215 819978033 349398506 793770985 796878485 393713122 733547964 87214588 537492128 12247284 829609203 5386969 670049158 850144200 99232290 4606875 749733528 31685876 389647999 825275456 503469362 390037923 644788825 147689610 803217330 161140503 994818059 556285207 556251985 310406167 843659930 622285199 130384199 193058436 268572535 779779035 439287909 2120498 719509974 976780036 14367782 401635529 982167004 536933291 104296080 933915645 541540165 854029608 818117873 783704516 679305063 174103586 26258790 176610240 321793195 829476119 190267094 169127606 238277677 746519078 479533772 81937607 221320628 462434322 127512394 342409514 94729709 566800302 197046364 814239682 543580337 63930497 68391562 378263692 600863787 172687642 164695689 142403951 26717249 982813561 778624818 558538663 9433498 804883608 735148902 331226693 634359726 925415995 500354298 872637403 524451424 832404421 807091361 598288403 147355094 934603754 940697917 242084802 501404055 137744280 908840836 897500743 201674776 977232397 128280786 802538562 149920038 292976474 797458864 29153638 128306386 428600034 587692301 137739884 233483641 175357554 321482928 720359718 100773549 821837225 445513472 477741324 506757997 252604832 76029727 654113090 39724937 869243995 896197892 541128991 6988274 657555079 291146085 61179401 634787475 419426871 716234314 637223865 712403344 366209529 666377502 693226082 794809562 254069802 830965965 28293202 429427356 4965244 601169272 382717256 826802468 46682743 712974931 186076816 151803927 641521009 840189905 191528863 510765003 588904148 732657854 370269628 246459226 23803938 283965380 733763053 295747160 199693 370986917 8150504 366409222 37364418 553892937 13735135 143950572 237375253 42028337 425894279 242340496 495713960 808611534 69142963 542396702 374102816 107736130 694200628 15623825 947926034 885729491 378905179 536830182 470903696 749174807 635805759 347223985 33140186 369568811 642971145 885856231 593072079 503638000 104781804 482952849 57530936 118516938 626903420 147422540 13061626 52797698 389763035 508775585 713925583 311422349 51172287 88028398 419158478 597889266 956168574 367084511 336135108 335073753 756431044 659555155 936764911 392236803 6779140 822421448 614321965 502266636 708277678 207394044 858420987 813059481 690346892 768468274 931576419 169766663 915890813 944638044 75080712 305653847 305929981 641522646 617076195 209618619 582067395 36234672 807507884 538235969 255835534 996159344 725826073 12266578 655714498 662590983 257019732 515009989 337528782 871341696 869792976 45806460 931252091 728213962 711382292 474115334 349198587 495475062 643881996 265089399 292629458 571479059 423259597 598559438 213001704 40335791 808178056 795069099 929086814 468202291 185821419 37438700 316877986 911647491 902221629 972592484 426754825 11757712 340118824 764283606 883099407 62428152 662606417 666867850 790642113 226505061 140983183 139840700 574496474 637381531 257446450 867125931 208860589 680706047 318201720 274378645 573558189 978896127 69447743 355161355 299614770 107785513 245116406 616492755 871949355 147338034 441601590 151220531 159095745 781720414 915504136 894711503 844148565 430626905 561579352 487307029 509648317 555078887 479664080 84144790 192460417 589626882 803787073 253837357 122849280 121988792 528216001 696407468 953401271 450180095 904085174 253016040 557965607 149201579 869508794 282431313 149055964 163626736 433651843 308151708 945347149 201672331 55379563 642012065 632299235 616958914 981835445 141947551 24554152 314015877 78608692 217014568 903642758 882395764 470851925 26492037 856900908 999067925 575415856 662818530 301764372 479501030 915834569 859729978 481218960 637859714 142161291 630274924 801486449 428329485 938426631 599349949 630001815 993806193 93878365 114817401 463281459 75713810 109281303 487835610 242246038 187889995 557366530 145888795 922802110 28218454 24897183 632219369 879802730 600313038 295037898 34083453 79814067 63388818 893813431 413549379 553764884 888491073 43824302 207767684 169336909 834767284 807117633 799338724 681089829 753512349 914156124 144371287 681742510 23437427 484723248 923988547 63843773 42089777 69877341 986645882 922824582 94774523 618865251 655143664 547603913 766419500 689227116 479934331 829808318 435556898 893483709 236089553 176564322 937308010 443857236 345901231 624591646 103491220 145239954 305681474 857003569 911912429 302569112 538746078 935349855 639808711 315250977 999193627 534414840 237644669 838355861 309755773 184935544 309737463 964899436 732539456 76156962 506642904 212473786 758481631 794716153 105957495 994571183 971280475 895781856 438428419 169698057 372889853 541919638 167454362 678571326 251439558 79366790 833656789 790185636 867232997 473465500 105436612 718942975 7880339 195597632 409815187 170152463 380533175 719552649 135051899 113072630 795709611 494211154 178062768 406707593 141443658 136536614 401278776 112724132 32318469 692223546 134938540 257724674 86659535 154909253 936295999 338099093 86792395 622469140 128284728 954025391 95934639 86237691 525484717 956331329 134351674 935299904 126483791 514884849 507368904 114052041 627957478 155594866 460779546 806020245 562302459 602223204 942556858 963581234 567463687 827391679 508321131 554918579 85116352 594980665 709827831 873928702 933079757 796620225 348914193 913880836 603161967 297365183 852634878 128646684 106212863 986986552 916462939 85213006 501871400 276348194 51781398 982345229 431943060 512560944 640881826 994245518 967300499 435955035 810343103 387280537 115863065 318664233 942199115 53495768 913644897 652026946 927424470 699241006 301163522 128855014 613121841 904325489 426220197 318273071 885488524 532433059 305259622 654467814 617646064 659647373 930816007 669427462 641992601 362759066 34504757 135390778 209520935 1805255 571345813 19864037 389085791 687208877 191044621 183801258 740704645 104689518 835828203 520645466 656446875 136991724 649500479 122085067 893833564 75720675 440358137 779322087 608153734 745617758 286306252 78316149 257781482 217122259 747743610 899774083 432397676 782248366 35164860 641918611 784053620 459027024 661782647 25655763 146235901 852827268 209457020 886940545 810033137 897801574 260102362 318996363 887309649 909602840 441081429 781143213 985323515 881439566 412981651 445993600 479573675 699287903 524309748 737355157 768926513 124569710 489645591 201324188 906818075 377326802 843242798 543388047 836353826 357541797 569043809 982589726 62885416 631017180 722046622 725434904 528818753 982148983 44431266 268644753 744268174 485512694 49787965 582108040 219468611 315285968 28101639 699042286 867090222 404927739 436397442 636016734 529497448 926043032 689857273 288831874 155886185 385616423 832219920 992240010 743158219 253780080 827346087 658559986 884797259 401909060 383994889 266132363 236574394 280942506 534777116 980842568 766455199 437081432 562950607 985923810 752367399 443568598 537482447 471973972 701012688 973879888 107990705 83026487 752439271 650364330 371858360 908325455 35980752 204078280 753081817 631655322 457858359 580427903 290215307 195171970 982336963 526726547 461304332 71427708 807669052 996081447 52270275 426640602 433162879 467737234 265080763 38046629 911305831 802563209 510020601 464834870 628959448 470527657 547861356 233915070 120891986 919719715 142240525 9389089 123797994 747838693 641044410 434172705 180782947 783776068 629344674 15636261 310502614 90649005 87063969 118171665 939246804 139334243 397328619 224926034 607071476 662409381 262972662 370893658 464972590 625509614 835728527 93932037 96037271 236106234 180363459 69445608 155825949 175120335 931351049 132140294 922959027 424911810 418829350 103741973 208687878 48174023 119378234 371706843 991339380 206442202 342394860 783102535 198292796 739723478 8028568 805364272 402132858 123517581 28774281 719621799 749027195 717019160 666070188 697580817 953125393 846433646 619542776 108951341 21553980 550893824 93607987 944513006 975805634 512437336 900771330 37009863 413127711 20149563 408716705 256983442 79108116 751111564 40085976 277400912 343351393 900630895 935281535 745484251 24148475 964055815 317622401 773175669 533591326 983692588 323272837 486716719 830126233 942815613 448184411 704196564 346225788 394308749 501225921 174547773 906746085 401997251 211557635 172390147 274663165 472790692 281889940 206287633 76418607 174492267 483688544 419770000 75123161 271486430 17770602 99271635 88058596 335393002 724963656 621649922 319085590 48236492 108366640 1728174 843568456 409067402 705924738 189794244 803376151 59667010 364342016 562638587 461664260 428416003 587545085 588843777 901206694 869435024 795131409 977625300 43927290 131336304 397395299 119050450 402822733 415165900 70838436 490881328 750558902 648318443 112531249 922160843 549071287 73414240 923889016 245156094 334997994 482330105 434950337 138374144 541997115 651808705 553529082 856177726 80224707 141074166 445021502 981431400 863025541 92669262 811573051 906952830 224005565 61484702 878519631 626828297 476650601 801874418 117709625 79725854 302709213 82757225 1886696 704296851 156171465 778292064 949452944 491169458 113138520 236919633 482059953 507651986 888728337 888105386 363829712 968953043 881695903 661367565 802900794 744721443 754036827 466990196 504190624 978042391 528474897 235226606 604870688 5125498 889617375 575096664 937367703 44842939 657853888 791770751 749139789 814025352 422579166 698592733 157711161 535717685 935512365 492287465 43369671 676757053 380392850 259715734 498226447 114605104 921083298 153643592 859326546 527636476 620633787 216033521 505678867 149108684 303776478 963065906 6750533 193393853 538162569 944118235 238236791 48532808 588405337 987376580 862558160 10984502 538485664 872785672 399218539 326514380 365073137 295104561 3271432 597982338 554820294 354014230 712587442 328419943 507657821 424430339 856056419 128291607 640463860 214251637 129916642 944240337 29833894 136667174 990150541 567996462 933301761 80903684 616529269 521707097 68280263 331603780 385207951 459282278 56905804 784426489 638313009 421978940 79531049 494100792 19961277 486867694 848115021 585065070 815287636 355772841 9495409 523860406 336580799 502475620 590628394 466497441 299232308 620462287 603164614 289382849 40975100 388982726 370286532 657504369 910689823 291083146 841624500 148414125 602881775 898530303 932840613 241194783 173025594 12371661 735295574 45503223 351755706 435926946 630568292 19559693 791699786 640063700 543420099 128280584 142539319 134048492 447294376 294287979 607027131 50458990 583670827 648002230 291958067 806473710 158022950 55164241 97556855 999647450 203578365 552954981 898177752 136418977 794149763 71203346 1306989 381961688 116706568 353062694 817888633 599791211 372622387 462104770 92371263 768558837 442901705 87426933 755123680 890196081 381714911 362150810 793171422 965385737 10153040 85129488 624375798 20692341 140293729 574449004 20339790 196388445 127403984 771033894 332807422 774070098 694753591 186630762 8548137 663976510 539693456 826436769 263767720 764832194 141057890 356138982 533391030 436475947 443565915 141031061 179188379 825280825 503181871 972359800 643182914 365851262 910005639 120075063 386543602 902815719 694524067 259399744 99204164 821928050 30433637 284527937 448514500 725187227 471158698 457062636 241680088 863368505 136015757 505447807 628200698 277073646 714103141 14108079 713549592 10185407 155139140 892737970 835466231 510837362 717614121 331165496 876688623 480136112 451240559 115748576 235468182 145764625 375148319 187188697 820209026 258098307 324232985 121239877 983285533 795391683 578302513 77481972 511276539 714318269 582929779 139477237 991391914 149549271 6101667 557457858 159734677 13757158 302712179 995200907 524594519 872842652 178882755 253799493 205495115 482639665 369548069 440963296 480920641 597212739 480668345 153646018 855311046 804901329 274885895 691112930 452809363 853188407 768594902 964085902 567506675 204041032 956079490 411414940 353590302 962181156 821389149 513324978 975938314 124101328 361042236 353049184 849460331 539924990 606848677 54955445 22564654 976396745 348435092 356001646 426125835 829103436 509647664 281436880 634004765 784533558 972549810 86814127 637721964 593661063 903416380 57744990 797702094 859495869 321676281 151292395 674193377 143065430 664617372 502648042 119683109 25659607 855697225 969143439 418100949 315062253 876615235 293181954 143975349 225050326 649183600 570101184 54153762 11347615 851538063 540674878 795881172 676604224 480005356 286119487 122781638 235938088 343864476 920483731 95433956 665540756 71776125 622143684 661122537 588909848 977308077 780805645 467085807 685521654 602465435 737703107 583906 331597021 30885060 144559255 556647347 532585011 714660438 463317460 543932625 418714852 856508689 192330148 947835428 189030396 478449634 70617065 424968483 822314109 991100796 372918791 340371217 915393272 995062474 1493753 356819472 824886903 634815750 676421630 510408556 89797536 414124736 363508813 421394557 297526147 508068067 830558255 682627510 75244856 146392066 79076486 346476060 2900754 271406634 294311487 191931149 749856267 217444903 616899632 424686728 61062050 989818422 765057944 976455322 837397247 619068048 185791145 514800501 106400149 862212774 25209056 48714037 128853861 241234221 470108593 278896359 749302287 153183199 961523868 677063495 299575264 40600354 23539554 302476017 312006987 170367392 346923517 61863253 387812294 963823148 339066332 448874344 806157921 104124275 277846017 496071520 575708675 463637161 10872020 534625175 178366286 888597428 583339211 159736498 129831648 53447803 438632856 731650286 59147353 400156724 261230132 358722616 293273429 284769685 661198632 605280415 455137076 8122149 519660019 842949370 824461648 858726351 144340065 483135921 815366977 422186081 831723792 243592003 885823241 695112163 778217178 916705878 436225942 214072740 76442375 418573941 120036895 515075230 2740579 179184247 767748305 263970710 537906863 61021733 548740395 51621846 518818499 856393822 59743994 38478518 551859543 736721994 749721220 696199607 72374266 417604548 118385687 904098057 513712903 856725279 451726571 144446432 773431156 887952513 358519171 702389882 306526453 478556065 69981464 309267031 657740312 837729768 573237741 195647174 898751501 974494487 247269019 270086351 830888308 159529365 161081220 235264203 748767710 910802439 931463809 821141975 180923339 49849496 577756383 694636241 759091126 29482953 839082672 385038634 769951817 50118194 87428515 76478270 528674259 157409978 238261652 186414570 995139746 664015744 234578095 746407598 638510230 481847113 16493948 321914890 493892829 30091520 557179092 242660538 940893958 341159252 916318864 974333648 243525099 346591598 521486240 2616225 228590903 213085263 387654858 998542719 263203457 327599724 927537340 791877715 485009702 18315344 978292284 332665799 682331087 65386730 931589748 173357669 547233842 800600047 495272558 41126671 830691566 904968001 136303560 624101876 246127252 52622424 598435523 489652351 251730373 119921763 344784927 480321275 185523377 732439784 478863994 448726833 60039507 258917685 240604547 397565560 277233028 71413182 582747710 959564115 136799911 514337457 132921783 536550105 167453856 480710692 430193127 998145421 385678692 566496686 622247296 484322295 471635461 73199171 973974645 723365834 45637285 171275923 56203460 231160661 903715706 535067453 679887494 816271565 793985138 773008392 66353476 71218165 844421574 649101186 883298631 833737836 15954994 16220413 370287940 183408849 349447456 800481066 34070622 735126147 219494104 656317917 71964794 543645916 582033439 45939438 119528101 627670723 69731713 175731561 711347736 973447418 710799013 243751581 642235334 357300502 16759972 561105162 281035019 713697897 62722699 16850001 547435733 78677692 33070414 770240024 114602893 235034221 423237442 148673514 970160368 642731545 804991430 42125161 38893812 239541221 940580950 158421913 867211943 10312662 334153473 431076030 836276432 44952485 674827610 331028117 254769339 691587582 892133278 388320709 257801830 954855976 405170709 805237562 886050020 290757474 427993938 652912 525791695 851231379 149326425 348468414 346479275 806834206 243109926 385373086 46375426 36207227 543794998 766103721 46519889 877948470 197179750 735312672 775417307 872007360 918857140 30186645 416111293 663506770 271023705 673913122 470879097 676194413 331667036 356929116 966951887 759660973 210098379 492743581 463408703 359424803 841211994 809887977 18775361 84321919 195261062 65150786 120529145 739056060 831254506 19565385 469520881 880950608 607394408 244938187 605474319 378767900 127641183 21585611 42274669 398664887 548015084 513153765 74859300 732198471 722599233 894327538 344375795 932697611 239587470 807784497 144638766 80799463 617672473 163414126 17637733 665449887 228564911 990683229 257022298 912335769 862764966 726543178 793286376 322675725 971481365 251277046 701443624 951638899 125379008 596234644 202820138 673394091 109388409 130195789 258108914 684503993 24523326 602484708 617201603 264110795 410269205 761840368 197426609 880458029 925254493 67580693 545907915 6335756 910780273 802930212 918671524 626061590 381989742 564474251 948737315 205987458 815751296 502697290 157626356 941130303 98931934 360446493 467040745 60836694 490642281 725149658 597857038 367681958 180150718 67574992 631792752 590419922 829415360 681735712 323394302 607186204 749316404 869302217 466038311 512613029 524748780 237226186 138674618 906738521 801700436 939928284 112725978 469968083 295141926 122868686 263614737 246590211 335831530 583171834 159943256 826473811 160837843 757800293 46672120 340988560 825375284 678464872 931408481 507306995 212716935 107319135 114493199 962033339 976621351 433047861 327162719 353886482 670274047 465837336 113141355 324490834 258281972 78383684 794458917 553423897 53768721 910590005 800014107 389600251 493761838 959957362 68590413 654599681 717757654 115262532 995588240 395649289 793727403 779513073 902956284 6444338 886832207 869965834 820994028 715969909 303013694 673098 922372742 973287740 466510433 35514096 150294926 724792404 966414132 944753842 130732652 20182852 707860198 930746758 409783102 54138388 890704119 478373514 708738068 460978124 593636046 556842659 856627413 239879800 188872083 612100048 98840489 928220641 482065881 772350868 496706901 637595926 773023965 419079643 463400018 92050750 307110090 613694943 816843153 126040573 410965136 947575805 146223425 118825333 730838914 408522878 172963720 474059385 886896392 734218139 935037508 333048789 143577150 644181272 425444940 332449232 108797671 524285429 113186225 590863551 149152648 609893125 80975829 922176613 28972767 544375846 14227362 188599209 158070788 683586866 314639781 569035923 483679022 313379557 540377607 214517936 721902435 713341327 688577320 461315178 300075817 476131179 794363966 443652966 972828803 72325257 776102198 81626473 596610685 889288422 525006376 745763333 351697898 605982204 520456297 233187017 150358049 534683658 421786225 160945188 70786875 588942357 729981110 554465897 902321914 122875068 768983832 624224348 836216394 310077503 85539525 136292211 638725033 732419842 432461528 611553835 804745098 61080077 545696660 253872135 950368498 70703035 852151819 154582748 676685238 372608115 387769764 679559638 759808124 809555988 840504825 830594998 251014696 423002286 385060894 153336609 545877353 6561077 630077308 234610099 169154931 568133184 223418661 807879964 153069377 655880188 271950150 957814475 716960265 817646809 64202961 519845114 888349843 916354779 674427861 417551432 141479245 62197624 97111069 901287368 724269963 790132245 584398717 975284659 213134530 969459611 128621267 759011883 828537039 611214927 993621981 997691970 179348110 69556993 805571933 332417487 725437180 77522082 142748313 442397444 747685243 59467625 962242558 488551437 975822403 489186770 906102869 969817999 551384394 855730289 723621718 128170708 498378886 308020434 103455366 711513415 129996396 84592985 323041649 958533435 695807911 169179981 808741756 727672372 238736973 466830040 60089858 964174153 396868473 55354522 259087948 144553715 114822146 73846857 633105152 943160900 563033627 391724372 912978898 966934372 99971012 489116967 95105079 598349897 797137401 51076797 162379664 779650148 135669781 337937664 590699934 683994043 507117645 399441689 411666414 598370969 866271728 324272624 415061473 115656553 232143497 674149421 260210267 346965643 600512629 745831770 142642894 16062607 137556141 55621792 982996978 90043505 397255110 78102057 540909753 46908862 129178853 703289416 826559010 117364985 41227080 417258943 801359027 400861076 669216984 65541792 999232044 388005063 242330767 266809869 503661615 474474264 940959289 763871882 821439906 393988269 362220003 964082799 410050876 352292496 872220942 393047853 442336000 121992404 323666261 983245752 168901265 305361465 539051520 995460274 275242801 432794951 265235569 76601827 686172378 934452552 994659971 537920773 322457614 236990737 804730641 826119229 711465000 598206281 442507462 385421257 992194550 804727464 202020408 402245425 9536311 926757701 647809629 451872310 48750104 971475890 287634414 217651369 129353706 679202285 65627994 404596507 111997235 330863562 333714685 650685964 265316113 180891007 188606736 440290079 417881744 993337377 118925659 981863095 444060009 561433120 219800704 436254558 218676935 421821111 691016334 228213246 201095163 338825963 532601907 249845267 162818204 820236320 320012987 144688261 351954956 385640980 549284767 316468542 716504542 735515804 967154505 981820654 916406810 8277593 274627084 186804905 1614969 393552742 168668000 298191329 954985861 388468703 734445887 26179148 662806165 277978572 106908745 863901327 616804534 639510651 113746593 632139089 312263323 286275931 776827350 664218278 671916911 178628468 980686820 388421452 914144271 947841324 222758457 830551081 956118916 497385541 17355985 810250236 890938282 38540336 108441565 698440495 279525390 695403803 577135994 942331554 973382374 684044738 806232881 442703260 323555388 772495825 74842348 635818710 58771756 704186049 152553340 583205018 882814517 133240159 971626469 796958787 933597834 46901277 480026219 742233102 396803169 349898556 404999689 140257803 240955243 365957605 838698297 520480633 61361407 268350642 462812186 887260133 952395379 121561418 182479744 128467118 746573595 109838443 764285828 657861702 814024492 916839167 241066719 549355360 902595677 65209539 198830498 836193510 112110815 678856717 430942963 361430336 881271624 835942652 501688138 122226866 201900256 192902786 642707498 115778015 461253427 958036036 855554499 413648805 79597453 38034242 542115922 678687399 389036 158918101 336549100 666929879 928273619 430132170 216285238 830869295 495341708 415115736 519579157 459968875 946488804 950522119 821399210 827760427 638981122 175603699 802503644 840881378 368506484 297727494 809175744 829759910 255763529 664730242 95925066 187877333 555280835 638040987 866564732 408186222 649475440 55630183 75116101 577749058 485762353 143917690 261134705 833620412 559033425 633230213 146105638 358038580 436268683 967504847 38315358 75249805 143108545 840819002 768647534 364131380 138546495 577823277 193891289 246826375 95069870 289816354 434703707 502867056 780373693 153784790 911053277 429849132 61931325 986169377 860114541 547693677 130087067 121249245 233830440 541636843 606995809 379936078 899675423 43264492 199957276 937990780 118514296 195582173 631326133 739678181 559713552 769872627 170017809 753604841 16699001 265087678 895937546 303919060 767954733 676311238 310220201 531524361 958676721 372151525 370210090 818791262 919845201 352813508 792556858 6191993 894450350 252069019 386128070 646642124 295333510 586085345 437149256 266364157 781667517 68475388 6042337 341381069 690864367 28576497 947502261 560079719 293664174 843439806 716515130 914135258 372267396 26735331 445659618 183460468 398886855 815869707 2251729 171248408 21199566 647324939 177440400 915649916 899393957 563568469 414808391 47243818 2170165 704473998 166124326 783837682 625465738 24683014 125218750 168846456 53259510 925237362 728926174 346923683 621193519 297957656 113575292 993460914 324692986 559234909 29437734 576096192 227620968 31689462 747344599 248820533 531530752 777301350 16986800 283441060 193386170 284311543 183201229 195556335 988785540 349325554 979394016 614251277 374008567 957129117 783097732 427268076 882366478 364540258 774191758 356076348 662497913 887767049 202053614 839707250 299518310 231491347 415803441 379655629 115697160 15664392 628476161 647227912 792965741 497979313 783185323 986351911 782290855 966386552 34424597 771076394 315712105 13818612 237844023 689720672 970947728 873458106 116988747 705830557 90514715 743696857 61906904 753012627 483980257 116476869 445236228 636014918 347968215 861039669 15670546 463665375 729220412 496663059 110893286 374702504 994642371 746594960 213570766 776933225 712981511 247995362 400525970 881209968 261813973 490886344 423446991 85278052 364344450 392952089 643624960 454859164 136648945 558048216 60388143 473145554 674525084 505624370 109160471 22493299 219180390 977347369 486158673 948400801 474010427 449568310 175619657 321169149 48679621 389190422 98102373 761661132 637185784 351144694 495387451 898999756 842031038 918834441 836794160 58891839 311786529 480419119 366267354 300951826 38467334 426655496 626613731 565508770 784796218 588290553 588002068 3976607 565637921 926677092 804893760 892164699 228761753 980513416 213333847 277441373 222220189 163952571 39102504 859405972 367613617 387006306 610922080 62161006 305840746 447716239 121052844 470143627 780651709 487320197 771095452 671635395 766492045 250225534 237144164 551288262 838516086 677662583 407781220 256670359 604339674 65191331 148835057 833101426 898221098 214685256 110542798 120441287 378637826 2161654 979847258 746251442 241684311 443285689 808412447 547525057 891001927 781981642 17668683 524169988 121818191 641280486 195805382