11209 434899546 946779170 335992993 387765564 628212682 891433794 14993032 93035498 130488074 506034653 62541822 232187714 124259931 410875162 662280106 842500833 46895327 642086306 387013570 872699194 757448333 994222809 629931937 967280427 277561008 769029004 656788383 781655657 14188427 326401910 269271453 892474754 20888590 385068425 267368041 429994992 34822743 976536599 260393286 448949130 292355090 985863831 298394751 577258210 16947665 377816842 705637735 828391866 196754944 781810666 101200364 304163257 73073989 382835248 88668776 587022182 322901260 482619083 705791918 800761425 478445235 552402536 80028673 830722903 56637940 463049613 235618486 595300784 552455798 625002822 107787186 645632493 451535569 817757782 128248360 382930195 14213783 466836729 330728533 923808164 430179791 981336397 305048879 695746397 521762547 895317558 823391075 876510419 89964265 736633028 616451290 815479533 154716707 424530105 21246678 115001218 527031533 841732129 442523572 581641269 642379360 654576159 512944457 866294110 505192246 544827153 271724871 755649753 344437127 941242973 7084992 47222120 261265893 634229383 736915781 859397117 90002853 860919021 1904877 225316035 722347311 877422128 219784736 759210459 260262782 278145145 397063367 656531551 12942126 414180680 317303646 347249852 804056424 982886331 56872622 845864542 302620266 746837539 368545597 978559529 302565345 326766087 276570776 719526673 338798079 925270699 623896147 747797827 601992959 880732495 69052918 293884728 46778352 152486982 168404989 605473980 105325575 134429723 28743540 237072610 215306892 509562332 181127883 287769958 469042063 905242007 213165628 828465559 149644461 911195471 75854990 850924198 534700920 749695140 761585010 968719076 89723637 619044462 20154444 324993717 447500807 805359356 711683057 907359592 406076338 843027981 184836632 630726478 819162783 984127843 13046668 363509337 164510142 935367409 604289839 874264100 34151320 571245613 33562760 252499669 271302927 969147522 373462436 536248323 499498188 866511662 606007050 849818945 427447609 509410048 76629804 359267506 202064368 726022684 264230462 543393922 368915196 844934828 877149 83969743 113960379 200713499 194792797 578671111 235573107 282160544 307789493 718214174 637210141 906616722 252491340 763641738 38800516 170085894 127352455 560880150 426837496 461812476 173231707 939993559 630887563 786257317 649526522 909467653 46130000 763843998 548847816 734711388 471138317 949016783 85581300 213185257 26977056 309854930 131449141 424544799 477213714 784600646 548272129 965818785 658734743 897634148 191862226 752710712 491315987 811047125 238380081 417303070 108004895 232022898 32019287 122337517 185437739 201805924 133333628 797470822 372249541 905278578 214352416 667003311 125297082 270183792 474735211 754977977 271936570 808357858 281612316 339564363 341018541 687096973 342435941 803661857 456459780 690314588 297828291 479313494 133726366 658427515 323556890 823119278 546323100 780228126 620114042 813130700 197437844 692331420 378165627 947739931 286856330 796758100 130537978 675976228 822627073 971627976 382980014 965681660 522693315 581925707 27946008 177844543 138873127 286661820 200627959 785159403 969908762 973272770 290078364 751330573 458908012 718316184 750114407 815610215 300229152 608953844 160779722 483462306 227751623 397065275 218332445 743466901 108197097 912871962 118433142 426907268 294546824 901648921 183024766 422602492 10660560 895217913 373370464 930006609 90939343 958107994 461239736 844800968 46118161 544680997 300732796 983752116 160211622 448287815 759608400 971576147 421124835 754960343 617465414 814939281 112244131 453096244 737502128 862948103 105987469 912037924 152760102 986309089 208366719 809996861 290206352 643330413 667418795 889786900 615290414 778594374 11706842 414484926 288543187 525779344 6427371 916183428 126986550 899705103 524362458 528842976 80503687 349779043 176470070 616342509 650499370 989631665 40733171 749414494 42391402 356061521 718775535 753039528 14826583 752129340 167360450 484070257 279672254 865105379 248612444 598367454 123236251 889142178 531390890 617151255 421293510 507872332 398262725 678332630 15118594 794238071 73235037 504435468 2496759 171865937 435748981 854378725 99164018 178302735 67217929 468569101 289944701 864013460 111721236 759157021 761484965 918465245 551094629 923399690 83322430 101640707 227618147 277642793 374073932 820885789 421474862 580341876 142221280 636832888 404800933 798293001 532695347 681866007 70038575 245682192 598401752 661891044 239808 781493359 390292343 522964645 53206382 91383295 92819296 244136961 492335559 741581047 47283544 964125983 140407494 717997635 155807104 953221846 111476607 847223899 107185329 368316570 339951090 629006889 371127682 450682668 402834283 530045833 662160252 676530723 381554097 828484621 561958191 594296385 282682197 378127515 306253268 892114751 677868146 974831967 51962937 777768204 623151832 698333395 416366987 556384341 235013413 941428741 300481197 970194943 90857741 847113034 250553838 346476942 620829321 678853151 691497987 917232278 289871514 414061512 357586623 916409971 444178140 955634422 648692880 707456163 14125119 217016784 679919857 941610051 104334933 171603849 597364845 972873430 194803032 242145831 546188561 836330107 181194596 261110192 398331809 659493896 351556105 633017015 482102034 517484049 23721538 587697512 60491541 376043621 87351128 710169310 22749434 576031294 14196537 774258070 848849815 896109946 768096679 986355144 331997525 363906785 461267607 838381830 508585090 548934463 757460636 813146082 11587863 292001772 638795361 822427654 206221079 723299310 412909145 499011441 88880080 121144566 235390359 591795157 443632676 602908485 919322806 968771268 18103930 160734548 112979490 529919968 201959403 516953440 434838285 762508020 265590649 609036045 397789681 553435941 105020746 600935571 821537400 848765615 60378933 661000372 39326964 556713830 206915857 426768751 618025155 656752862 352331485 780995293 378140798 794342415 126484632 846236205 326460540 630851495 454054368 775625459 173243213 795862100 146479706 878492747 663590118 916130966 246951306 837786770 72674514 789493079 393824976 831898117 412136011 863399017 484249019 507518671 60597777 150365650 40741640 677665121 158772732 872690343 774685403 893766608 599409575 654615469 354026156 735780877 555820869 724184825 297111563 498072230 419030409 986060179 24223167 444757880 481818848 939867175 365768331 489762636 957507515 978150869 79955751 131793626 518940231 888633689 33547599 971490809 203032618 203846162 346721075 507838190 835265088 944310723 27621414 217716235 35197032 879677756 117423972 602264792 481653973 662159700 592448392 838418452 645129201 891835151 11419532 948941253 206901160 700747378 56163550 945311774 431998636 718038245 325402097 971018105 230968886 486815325 639342062 666973948 76537105 646232071 260338142 359756528 98143319 261704468 563187878 993787004 31577839 801848074 467702204 571696780 380859097 470598921 27175773 444378954 647095668 702926076 43350522 775546086 513142619 736299032 475860590 816640218 397085513 519010535 564153047 910439993 192484772 431701441 238904980 739490456 364295404 579737755 762973013 764292478 225526175 436074675 809890062 814404313 13216765 662513443 178987834 609524598 25606346 996883184 477811170 910066592 495873980 623546296 282909106 888078339 466970619 719790594 65324289 276703302 413857707 999384942 240031838 971606243 145631948 705757215 244768414 446885975 649614446 894223120 407644824 732293377 365012280 805904824 361979040 622228732 32108947 872565812 850298195 912291226 279805049 522263192 44494290 903209916 470623628 729233668 87450468 903793729 271386405 937991624 526896974 538245760 455733278 705882501 486787896 995684789 5682914 851878257 157873541 602434462 295961803 486029348 527232645 658571656 603338443 890279260 147716232 535738474 508474305 781899400 544787845 640776821 501339363 800834217 15893402 265765329 491667562 744231630 309873925 467163476 9655632 26108800 158308540 329786881 330826951 836454065 85037340 930269194 149518576 579622118 415213257 481088765 114116654 917734611 92088466 881152725 101798867 399042830 470387639 782029102 112893747 909703918 686567389 752098989 240541114 480872352 499964568 599201941 480612012 631470793 738237581 857054875 421586108 670940187 715956055 767104278 220195964 608087978 35581942 640268907 72814270 491972089 678295226 993482679 134161385 269576300 98383647 181003830 813884238 958718966 387066317 889027321 649698370 816180225 495396928 645537204 428917523 954773021 333237526 983717537 272336933 628992476 429025538 812808492 78418517 926803740 220300931 777928025 509131647 805677903 498343855 798096469 163426111 669425258 107890075 702541496 325240204 685736829 115978999 875789716 520153965 763691598 394713560 475988898 266704107 878417463 177952872 719459051 748537304 808522172 351946688 485379298 83832645 594262719 224989038 693823921 92005737 696373281 111671425 940217010 183398926 503039998 829799975 841664542 1558311 376856773 760362553 800246862 168145122 576196320 245915315 361252709 27918890 789851400 220573701 751752688 385872422 747284986 124016814 686900794 433383029 593563167 690526748 872852970 159618870 280732313 655153022 790119054 796195645 946190983 212023295 697323219 327076693 585786967 702782593 837376408 273509557 585453064 19345954 509050465 52099023 177394985 205145568 346128815 172001986 518018603 354731769 554690614 810996142 999472452 230140973 547702700 255481120 553890303 538810734 971477991 11085786 913299779 261289899 415190606 376800360 504741390 213770567 704375503 77259692 490292573 878758140 926119869 297954139 967272101 11293829 753622537 133835731 508903196 333373728 783365622 186141501 458641097 114742764 358918340 324297754 707951329 231127687 282356765 192077122 376304400 752545172 993550306 246910521 641054503 482100729 776127747 333940671 408193421 759057014 843727570 174187099 225336787 17486831 131319029 98030322 195891769 205499779 237752444 201368048 677705109 363860523 561050204 98364459 408328625 325050399 617061422 157005261 933571987 391100299 976764138 674901147 856000471 94344107 455138086 200671479 293298436 79093100 633062802 64986421 717777141 455267622 680682863 125162953 253930597 718208402 934748552 156070767 985486779 72395259 593293916 308716789 396319902 745207842 954455194 344338787 487606839 580093738 928657687 480915107 728082740 266585863 768110424 76884800 217625876 393252229 956176234 450697596 928092915 280741334 473158407 138466317 655553038 335095757 885720979 383669277 718590932 392429090 422237894 106009643 949502323 214945843 765911784 249826939 687652547 382840143 900358597 177814451 377517336 608519711 930209752 718712326 932952788 246122610 616787008 40948507 703348289 439726288 481262787 807006669 890271590 55630859 760685444 540682931 863790825 462064940 999973405 115525630 852213118 48506129 691267160 493622878 755757465 18693001 781833432 768640841 866527881 534134446 602926974 502605265 916901578 30594698 41691694 64994412 850519445 331634095 380057031 33649347 429169280 194444186 865882749 204275173 500165231 10879965 908675768 632963679 891896013 423890407 584794420 675136078 899850767 731373982 997349923 381370060 971371893 160739462 762522810 77794287 840096106 109808081 980844630 126057335 521349391 130769861 866509973 575010291 949726360 716578000 785720872 143855406 542480852 211818848 309497529 611206577 751749513 222040370 952894869 139668264 384866783 209040053 697143015 340878078 990736544 4050149 702177698 36419789 379338906 330263577 509107158 239710419 600247236 272881316 572586827 481766036 555307602 204093283 412976070 321869177 678582304 408626788 446231112 950099852 984288420 601590144 801174129 209940477 561079323 397275230 690350119 633616426 659585095 855322487 931847162 703046472 990771364 75594308 274328987 112669960 708526167 618117926 664897402 132531783 268943744 37773126 378707661 440240619 563389342 107807978 893985688 264763385 692508977 483844372 770518056 82301355 538826069 206769696 271136919 586649500 932858843 169048697 871303937 525806730 782671879 594338910 862344819 349971226 774939346 752000921 755227271 443318747 486626089 765631859 842886457 231253442 405675819 560187548 752016996 688344877 808426456 277527792 740573653 528006819 643788360 437231183 866941845 312916633 459219272 417454827 434099068 228178888 563001685 829742140 840827202 32858863 737866563 234055735 649179779 248702610 619852484 587320053 763181142 89136956 933429104 935195943 962217602 697223024 849616663 558375816 824931372 641338289 705395336 57209426 132834545 278254720 434074442 598748612 871576357 510806923 839008985 100905553 503957634 107565636 923426796 117877353 614475063 331635734 693651178 96028150 924134281 52993019 777297501 295258312 692023947 102009419 207754416 393930117 829870081 435989512 482808702 415502927 611972161 165600432 750704420 340686339 465932817 339942725 413986846 142871479 849845213 440575117 783251097 860746455 960965021 14491194 528029529 241253955 772706001 438997752 600026699 712788205 901346332 74155280 345232471 281872076 893925519 401057075 800484868 268596855 499301665 96298695 502667922 155082402 439422738 81288017 164852699 198334927 300197302 106247842 938878495 293640698 560725884 448430686 611141553 210110040 880165640 18311539 715049145 219927583 294153375 633449772 726116223 334914229 991409184 419568145 780292137 448953213 562813435 63974173 182003555 92765007 167092627 575418293 911446029 132663085 255198217 73859164 822415397 183704030 967724624 105083292 972410585 150154438 540407933 117752127 655643111 299084928 984717550 700475752 824746117 526080970 530228566 95185803 515901161 483528024 874302186 370644408 887098679 635743100 665959149 255185117 948216183 547079689 713995548 16148126 893593086 129393423 874473241 150726849 472651713 536347164 628598083 441957181 516126991 629835744 659187085 112104740 642659072 20277900 292345050 205188431 602357451 307376093 563852257 477733571 676037342 323446756 645981414 137764578 257754141 237642396 899561194 71967648 697245849 342323200 961599751 213062328 660787206 59824181 215841511 53473355 956887537 39905119 145967953 82071992 150775430 110709014 342928107 834234659 950054302 340026793 714672643 137496602 933816283 563362826 833789566 287515360 524244952 209254457 934830416 73001654 582314043 330850633 879177234 576996866 959660904 59173218 995163378 135342260 227422513 6906108 625582618 826685523 871523075 84044829 245527168 432116409 898175609 28333885 882994011 126440164 228002954 173601145 718595656 556828798 839975310 664012713 999792467 546398939 606016394 256642626 323911155 729204925 784996514 896786698 994694721 845404720 996955616 47549898 490293825 125008097 871104491 318972970 414487030 66074794 225000709 302746974 595946676 791264501 977058184 692449471 853798270 571788425 845230458 548667143 776471653 900796288 957657300 251700421 514162863 745834502 792792862 237044354 518791965 170003306 265700384 574727744 576840885 425021579 689817853 820424046 844869758 273995209 568564764 266689140 937920242 40784887 428513975 23083963 433837619 49568371 181559772 343048394 489007737 555108230 969914526 26203112 141697578 372155633 942811449 77710832 165789732 628081232 656423359 365060023 724099017 224675000 493441899 291675965 539467500 430280923 453542511 413109813 742478283 452849218 506162581 685423140 723702926 116415954 447093831 654364098 996775359 685043203 711238367 496030011 582103212 193447545 902625917 196101165 804033154 73604605 891315021 909053364 961600001 307343000 859562105 346648479 584850483 93120063 400425537 786643065 804086105 21226100 760227958 404267395 441820188 379070090 658222448 201291998 660641085 196384267 227018240 270617995 280995221 519646068 641159295 149005239 469665369 613910277 722564933 182502266 540429218 315843372 456875345 691331408 841556764 453643913 566552439 478148252 820153109 233209434 796568531 262973457 866839754 397689239 947155206 301926101 801248945 41350063 185720624 948645027 993371557 85276929 341696207 57809756 948435052 174057398 387856683 274421511 787360547 172760450 962906202 214744445 546177431 398752051 979385404 366660036 465513189 449393993 933038367 348228921 502464966 145092664 882676102 101806518 168755907 200606303 847241567 382790814 897436013 76556358 506721684 77949435 603211705 467337684 756663455 110964190 443848247 517326340 568516588 445064907 933838942 170252143 749182879 405349353 862175181 233807535 679810013 290209377 519810236 501057760 689227113 763446125 994273261 414918555 554944739 281873910 929135573 358738947 516563822 350717431 679476446 561719900 711061353 565534814 955964050 14254480 662135460 21424751 590831958 97117438 960410913 403493892 744767974 934561393 954900500 240339957 278198696 549812464 958202946 118210089 645706987 498889311 967846739 782284136 833404044 148525618 650814339 77751898 795611306 115369379 253169381 638501368 977839709 98033948 509109320 382652684 901012184 19124802 173902500 168479299 869578648 34996894 301138073 34120360 586794468 799014375 889255187 759496664 932120986 738351042 932792526 121413540 432569529 205539003 956299305 369623352 584980007 455307063 791137209 55102910 63344432 448987976 543597303 817131117 942877034 19410168 747984377 549029330 620125124 559967773 785470635 162136508 710945910 283607638 818373882 12332028 975071515 100046843 457573951 31154269 556117985 695515268 727809126 382716526 974079510 572242282 583923533 391391524 651459053 641287173 657289539 13297212 106288204 364263003 714323320 326011746 601153859 184006980 187019127 212426765 309224509 695502051 749648813 512420032 885251900 39420368 468965186 374231435 728479571 327666487 337136583 301210355 445853303 656068899 812781289 58141000 509120308 310679127 316652417 46897411 761119578 197228330 360566086 101452907 920982381 390344438 631021188 309326073 920265614 75006543 894954607 336166551 754099082 360296470 416808973 212683874 634411863 247770225 585081981 4533432 897654772 205810267 430234052 296195074 954633111 399096416 652560950 68343475 646775780 122561576 315741655 407393096 454356945 578943977 672847096 88440842 832462951 57885062 682709819 669948239 907860129 125633893 859039288 499599306 668889385 282973882 716583112 15609552 17670422 780611910 965265122 178097034 419037116 154559017 879719782 897579090 940618042 56613337 564005134 855650232 976352662 118918363 519467970 935423130 981515304 84581957 92817979 373450078 825763938 347845768 859667351 268328337 474314236 273868556 619209416 230673136 267613047 920141138 928128701 528756899 928558099 675306045 788495197 789901493 878562660 210056324 998875346 39971916 794327172 756475737 840923699 394116280 539395023 61613831 986131707 574878651 689567346 102292061 270276766 786828695 858032010 215027106 601066873 286511013 954976326 194252392 612953429 726290857 848844032 201641742 290978197 472765994 937302949 160232307 408357147 52494154 495220698 393581870 961483995 155665579 221361648 844182139 890799246 810137867 900443251 473122904 834468065 422703131 893281306 450857526 811630813 79289907 80828758 245848602 773661124 193119459 453087162 279587995 979972800 475573842 925362841 755143443 838846380 166832213 786830493 264812083 509024209 339613379 611796165 279789163 290851177 130124001 732068960 669382051 856551398 138318714 985023971 417434764 724084021 81957419 627213392 105876718 924141469 555083016 592825480 446200192 722717515 156060429 628315757 606494126 872829479 299272581 345486690 433573487 527056764 497916670 748649208 526897772 650834645 431156653 475875864 56351273 614432459 6903220 95764484 231672319 608765369 116963625 796129056 35313462 775959488 299303398 467033266 248507105 389060675 771410787 998355032 22148796 270387333 156716372 743393166 39906842 746277933 858751163 882769248 289167813 639353493 776561838 795783992 51555274 605448805 353138078 813382048 258554686 888605869 582887113 706656571 296199956 966524900 184124811 629674188 345307404 357560359 74394430 658014994 441646107 699277751 116381443 968136171 212045443 599289104 65490137 706303163 103897938 797497423 783938317 932145260 92955499 272664142 531588126 735938778 99850494 761919702 327387997 785487752 644723167 778570365 244320609 393211102 102917890 493810009 525637633 737711612 15228300 351197683 99903688 441821458 208350849 870279076 33193984 246832734 102742202 488206063 148118033 864547339 549120430 885207656 297930117 370766935 274831366 295654518 356019697 880544359 220991761 504773670 408078002 519572975 603706443 997125919 492760355 692002055 355284079 937519416 658332606 711731909 601591050 718626979 278203677 392927797 687580168 837795329 496528347 733695837 63859444 149139043 503768563 603463558 463426468 872383704 955405724 966595015 377949849 455404726 314764396 891156828 150404962 939445428 338547416 815617350 331262023 819563340 286996595 710012981 504920048 743172299 319559100 546087320 118318587 665526588 162566743 545078192 568053510 661478683 196786206 397159907 116020663 633069685 932630782 977142705 258940910 447182504 190362736 254358536 63182911 295831419 368539585 655264785 472550557 824919882 148893785 639260371 8889483 546978338 132843823 927648949 211630412 743046507 127385163 658873135 297512111 363447040 535760667 962940441 32071834 892793344 471819808 507930034 231144948 868311463 791294308 796673368 677336963 911838949 477353452 826818622 339909120 689034857 490599784 615167037 469040936 932278028 454566267 947889847 26402514 947357599 469138908 756539461 194986465 684574877 105844590 245486179 196530538 649584534 491996115 619890210 607042312 671432250 191471181 852819722 228225460 828205133 86712151 653352065 536558302 816871029 125839479 574926336 143346496 816938652 660490549 912577916 464999408 894079219 44928368 103178946 239916822 849939929 565175036 806929811 187466501 377285989 671307430 821037755 506970498 984657833 914297902 953650188 311858010 556553080 103243984 297508722 147832960 862511896 746629898 959216861 143396218 537137687 63526183 319195988 473608360 879268334 67450782 391513200 54317494 556431281 394815807 477394160 74829702 659524956 827789257 857738782 337390207 391259994 98936641 100656459 553132734 853710547 527238305 979363329 392746962 993872098 42892590 743781905 137913916 911565482 594863075 933354585 125790950 661320939 105322509 654856659 288258765 833129473 352608690 824564957 22971586 662200682 98615286 541988633 298434156 606879080 250992405 850230104 166461834 985759914 690182226 693496909 170762092 202405836 29979918 918586683 204902876 898904959 283783347 599317082 770534399 900546323 205183511 665255679 116332428 295987938 240812136 297416719 205248256 608323607 198244200 441670698 621289241 839603417 149675990 219583550 64273703 333424814 383811963 710995767 145862715 362963555 48760970 681125741 319107276 869837959 426623379 846874169 55405599 908519432 371447720 685323463 157769953 303277118 11015198 727078835 153133317 813440938 591215033 595927725 86199206 466789247 366034887 366466660 753090133 843477715 821111292 923094720 429697303 737850769 354887125 992708783 43479434 323139767 11221729 512625142 180550814 439887599 369057076 961704194 147906408 385342381 310422498 536695631 106161310 408044375 449601546 852992797 587654753 623570058 655224185 685280272 222933718 447848115 119635356 685752201 65650123 960562523 352657487 939966982 658515538 974743056 758826891 987895618 129672340 954056963 426180547 601898421 244760923 796426756 232601406 733323103 393816521 659990751 13195396 594751441 566046363 588692370 328752618 841512758 223096057 886688092 242226011 800327069 396949848 576996010 576007312 737690480 497223094 795288575 110403914 994474958 230002173 838200128 383130083 621263482 396768076 462306554 394527182 542530814 658109222 716289959 319795753 586324321 213294624 310611959 756433100 770315189 416513788 461365338 152480029 367947116 19832759 871387356 326492845 595913461 732397298 931174409 242065914 644201812 426278653 743270230 513002129 770019885 463830251 608847136 189825986 689353007 613135561 825416379 120434004 697445592 255523362 500572393 461486388 936819044 368729810 472626728 784125441 953778887 153856152 377980500 418954625 681450951 234224235 664922380 382991877 892137807 158846161 909607552 45825599 549305270 1241573 268005707 786447 80382112 64532289 151465614 43879624 946368121 9272623 255768272 188819509 874654183 466402666 574047686 662448352 840500027 377765649 899381604 361625908 692633642 324618641 880987862 240092446 645957748 169047016 950367233 367553437 854209925 792602986 849157405 75839691 188242708 103076037 747790233 859628198 976915536 280594774 972219579 368772287 796661593 107455419 514293649 549993051 763634330 82856528 989913878 516082148 774344092 8991485 130627478 255219354 410486347 60780937 616692068 94796853 105173332 726579709 925350044 169194230 779187035 44631153 710326194 537530138 662780826 223799673 456387319 80979415 235548806 103197369 236323075 491912536 702584357 243038976 278970703 73588647 228964839 40362335 287615745 295885648 427945406 73597396 767527615 330533529 584771313 408117582 897113914 194751578 332923577 684599430 937152303 251758466 429788043 103082452 960141588 452844591 915940651 90054998 312702070 5767600 169972252 284875580 721788317 140142755 338162688 132783292 345415902 147779756 541773904 351929692 520971415 721737674 825691958 610400542 906341363 101787481 840760773 96717413 198405142 486055966 695337327 400599059 611795745 264754769 413636380 348835690 459916562 742889176 942398799 420290129 439963998 389836783 882576575 187748660 879546530 467598928 999795265 670001321 769474011 107285796 512454839 191761495 911489191 334380405 921486976 242528050 881889941 463898683 470402804 319362341 747986788 93210505 434610531 117220417 880638350 240362723 455967433 214189140 756992481 537798045 665054508 362353253 371465944 369932925 701386777 673200 790369571 265985683 323698344 181115461 588308315 18801527 820879031 24323618 847415214 94098028 472485253 89288522 260753531 144441347 567616840 371901381 563548448 177832495 515144462 906014395 939805185 27231592 841097460 221538178 623147558 734321423 827336988 223832604 596138775 641319272 901076929 31420749 651290777 398739065 949427491 650691917 871509454 566645524 878184540 212569616 231828090 135677941 378898336 245673329 509653320 14066337 222752537 415999415 922994214 231830145 609533096 787342761 859430755 129101765 312360098 535792153 625672648 433234522 446992266 356485715 952639556 366854647 576542362 574109207 909547348 668130525 841142393 415428260 737612199 235871691 698981267 30004539 300602628 89096223 280538761 14033662 608368000 79993012 466552455 223802110 849288614 867663597 928653159 839646824 847352561 714817242 760185220 95720020 556331670 350266996 683197585 73380254 794391059 282326001 864097203 195045406 956665303 42208738 742423168 228732712 920646580 233971046 663348349 44504816 637208197 410576698 449639775 403199895 477734024 538571392 681710226 379861826 431806641 70090729 536021523 386874283 900160744 206909041 299576374 309833825 362158801 785668808 947907583 370678012 621013384 763952666 826672004 468214273 808158891 83692366 315917103 273006970 322869824 336395989 473738155 253177309 402157224 378513231 898996234 218166566 989127969 205855478 351730490 197179857 805406908 132504787 762663244 318256091 338208794 128754618 592555781 525271974 559565812 562026989 882020766 320988661 471678862 3525068 441277825 309146796 657954884 836006315 955684329 193031048 418832334 440069355 722094946 649917046 831645124 188936788 632458796 388186687 499219010 379284 587637953 32302367 409814167 492595062 555808268 597101769 652263651 275033821 922324542 228910052 682032466 872654274 889631758 214257187 892470898 226753987 445650376 698090933 885917249 395285831 535141425 331054137 740495144 244733335 439248654 123447490 567055879 163302313 878378104 4270878 85776528 81856601 699820885 383926018 756807250 735132080 980902933 629268682 898204740 660925889 749340295 849194790 973444722 476313878 971175629 507964942 722547278 617895635 988096917 171575101 568096076 476618540 897136465 214296071 886478553 286784476 704918177 708101889 731296341 589333410 911838179 707979591 929205591 706936605 867620063 98054873 469233545 322042155 553285116 215971775 477004087 879069848 886147563 489098480 585810672 359299947 693848093 158681933 744534942 605338200 880083530 802614552 959547513 630443173 928775866 101017430 807470750 597408504 756157629 155652518 910020296 548990683 666874641 553933428 698686959 36149898 361766575 202416132 814632703 203175707 280471636 114312457 782650647 18914403 791448363 718370399 987678377 393657604 483523641 416357479 740679110 709345955 975586489 5691021 845718709 649707376 773273684 30015130 89781126 226212287 294159479 429105747 867278736 536576698 810336146 309784275 328380600 91116092 125693015 526422273 964987825 247234507 447570699 63034325 932365347 164704608 489229540 266512841 859385864 599752070 648909139 196865955 953876576 466444430 757134655 369162220 667620774 580778256 761721574 707062277 876174448 27249210 231324495 123964007 880975976 103210251 137042116 97902842 261741223 496297380 673218708 82025091 986317283 269580262 571482343 135382431 208163209 67499209 590191226 636430453 691595420 625911233 660811086 580401673 891731228 630147120 967855288 541218338 898709926 559618156 597522270 36726191 522969356 277429107 398040355 813571810 960061094 606060308 969662729 613454440 775111228 217786298 819040352 175872802 501646789 777557238 992471431 53329251 72660396 37929879 758113561 284826152 629335029 981991601 991659881 434412761 441720325 53429192 681301270 278632627 608465627 351664322 796443889 225612705 898823216 14364607 892684834 288862028 437623800 705942654 966732874 167136230 343822584 737138525 900914130 717133548 878958822 282505564 803972311 53210359 703253437 386794619 523977266 587973693 706015445 184203213 360739149 221088752 504156177 382886742 695541229 186777505 768760387 333788966 657017474 191568479 506834252 402776060 769221410 388554113 412340479 388393654 752566756 221406685 899008064 365988799 435293077 98792445 281990724 723735565 917554502 406470803 855292867 52825227 797729182 230141834 830365497 125952067 666470496 87088258 257153646 47929892 372547408 69637521 671930983 199411706 561675275 249650306 480098014 149020744 571076769 66112414 567014058 214227924 412155929 381179386 565355087 233525460 407379661 267090769 494257870 417794336 499139170 241444069 578475652 528678964 892749119 806943584 895899931 65526213 792445605 447653977 767890499 175752168 960639397 83865481 155278661 128576107 637394356 240598543 367210266 728692635 985552278 256162067 501276042 436844676 832435915 358873617 652248055 243007398 311513596 543670474 611366862 256723199 493982006 722358477 914516867 427157837 499134686 467858636 777441485 244911874 311717849 586045598 963690320 13026772 784892123 496704261 538617626 507160447 994493835 87234891 940466820 257578531 440717645 26751010 187314872 454215837 772497621 571023797 990247743 173223696 273513712 115453372 734647424 474979040 508757114 405277955 859702519 386150132 398025527 16202985 249311065 78585255 438642982 402031880 500138567 554269633 796611326 747947603 809728500 778727555 875770080 335638000 574055507 397390876 754347843 3562974 463585827 101420606 666601827 286389204 334862287 92699051 761284319 289615238 841850518 689469124 998908422 261191594 344623618 138448793 307758764 592255278 683574426 529617222 679631421 34668883 397106627 651466914 950831854 515580427 650535615 528903265 738818741 193190091 412318208 314215451 403735047 85791374 407366157 195089648 195112096 40149323 517305203 114426501 853419997 746944525 920057997 703087106 812113783 613401922 826514186 155789321 674257406 609797118 947304789 51179533 142690429 232695962 347596376 100010265 761562070 382994037 647426609 5895367 223054519 56687159 991814861 115278138 924339793 44849510 421254066 101548392 258537796 149018773 925773417 68668486 936632018 162081941 418829581 618965055 939655481 577412703 678954836 162330905 743325700 606318279 796470975 327216954 602839761 697664887 918688776 84220421 446667336 286061442 426926468 316553406 880963679 314812495 509897725 279678277 479667929 850972148 877434456 528797622 606366897 610342401 962725381 70826180 132376986 87916372 528815549 666938691 761446861 293559604 820405072 236443305 472675670 773479201 853211835 273560028 860177705 939243505 940460097 359863267 609605017 502622103 847870234 902748726 934247266 360225439 875054426 174553150 197568649 277941106 684719708 101999478 225424984 50141576 715206428 181607304 350228136 8751170 579813374 25693326 884623635 358852387 828916073 190299110 864024927 416543478 973673220 558877548 673937285 677275315 985758418 166248029 682295220 181174516 824724951 349967292 872369828 678814141 700689806 76101123 823156777 39995702 457918351 391556360 828499695 294970066 473119201 407185314 643728810 35107439 365574823 211408991 842800313 183765560 935702574 253045082 659004985 182944038 488621761 311094275 958485099 276853503 626463470 333157164 635139069 455743076 938544080 295904937 891267017 638510395 692504482 588578832 617590383 549440866 566127233 361073614 420773714 329381597 974685745 214532910 883394467 269853048 355211528 183864618 441145006 153629831 494527321 59555830 549388290 508910416 663991026 425725793 721434769 246976040 334373432 748345845 947062612 263500939 762968661 255449751 523300629 168599796 207593678 10302528 728634344 75834886 114598465 83228232 580044525 556493614 981484372 306457704 972082198 412173331 777959623 672283426 782815055 534524167 609973219 325287320 563419265 390876639 898132441 134465809 321774991 168846565 212503164 447125646 695742705 403322895 463479137 203918639 295275469 224831363 327371843 276194090 669600774 309140165 730580662 450819737 660277343 546318557 626242331 39949282 620058559 356636343 720649803 634607687 901385679 358324433 777783734 473536721 623811415 211755936 362071260 26848820 281326937 280225050 582877704 173089529 616469116 231031231 711382563 203321297 331418042 361387924 871314782 672165338 757915447 481431372 638275368 247936217 313883896 484263475 968165077 158392614 876505958 744592160 968863589 403809252 958034854 141617717 155523593 83978974 723097563 255501693 907443556 482976000 920501744 396601374 431322610 275984846 457790770 699181381 870443666 603010588 934388713 470471537 862115998 117693375 693055639 866284563 897826161 838292565 989933148 183621548 782068459 662532022 844373673 312492145 819094682 790014423 851613039 146399841 594895382 271386107 607144139 142867136 659778829 204225609 844810014 555314815 767592764 713787894 950256128 961699582 991499088 730526372 995662823 435745136 627580918 460559486 948247786 53127504 306950749 308191208 609222011 787924899 983444082 38538270 217335790 91095291 179772190 22799758 552280550 271344657 974551357 556459696 862962602 572866516 686601744 415695308 999065532 140217489 563126263 691173606 819714378 413619644 660808027 730896052 931514375 231375965 589569667 101198360 489072139 407860120 584868417 271289398 386134019 141792938 612012143 79494758 313944066 783798272 789268699 803136328 987260064 284163866 549452801 392545133 877573168 511556455 856578516 293595381 824431962 654745973 860487319 293673593 948729764 185864693 334554116 240401834 793365193 45947787 737252395 10653586 767196184 88644525 398917402 398202150 948280962 294547770 563129800 295715354 358416055 358796712 653786731 546129400 754190466 406891786 650315758 295295437 616828873 30821333 129399523 218801800 896838417 26320620 641070145 221556632 935509977 330889765 981141477 674454476 929157836 60171138 701964508 74280621 251219692 217488786 402379741 400503688 404827572 495372990 903856126 333315834 616333126 328369084 553447124 623384825 661962991 353398631 575324200 48335439 710006705 37745761 370033384 229097520 804599324 592785435 604599907 913690075 935274856 455613860 916682594 10519365 603838939 303894045 775355034 301787668 522300109 21108916 195981488 699230891 716400592 4259935 43642537 308655374 855797210 51244311 491869650 267036805 324236808 670865636 892493339 586107441 874801954 653538756 745266511 2466342 806254029 102392020 613139475 873866383 957718372 107107179 810960104 657362426 816639884 13638881 114207944 360399880 421132689 349418814 827610598 745357003 984381063 380235776 517177905 343092429 637076119 41206937 711996442 117761118 490484691 17594028 524134317 177967563 706939073 155402940 963997591 12343748 976432073 524970705 859506896 254407446 664197886 553650899 812087932 230547537 982873905 564971440 827268067 415785389 614215902 501601633 571590783 153886731 238122513 262250550 842001134 528478129 702325554 94816851 619700740 389809855 404067941 51883428 101887494 672547543 673105758 9625061 202333166 377076040 750697252 105300775 671019917 235590417 761352676 359224938 675828299 45424210 522041599 533875960 879886418 609332327 975247299 162169815 757132585 330135170 918992708 751422146 829800586 880008989 915547720 33263548 835783626 584751279 854444564 467391347 783159875 24618653 908773583 529625985 852135149 630102048 931702190 278677923 421597602 110894331 573548033 191762414 525535864 495596941 633132090 191635169 602806532 330056566 336604664 529842594 575321307 7813359 433447204 287825575 949603700 120692070 668487293 764225060 984927025 565424490 773210201 307431278 371837906 188179129 548784843 550031213 748019254 594755299 687811426 38805038 595396999 629646198 849849575 188061705 562892472 526879226 711077714 179856726 657748369 63244240 946227826 673338234 957719623 594247589 634195767 758728956 770119184 402616321 914395544 127133540 407582362 718122713 911775168 696487336 933637953 673459075 842980972 370070683 536875137 368266146 708761481 43894424 899095959 216540310 697021408 461495836 833533047 865445705 957190922 96077780 772327470 711161988 803851762 67803930 392891008 692937766 716991555 626987122 933006567 182033911 611401401 133442921 992723942 484811122 777919295 115600086 838133751 348709749 644999133 388576138 562483696 502052701 910444959 823996369 865338402 411979669 774752448 305240047 654683237 396109518 739721723 398380651 963395563 560148977 598725018 45858509 665771039 766640294 883368913 190307748 710524850 732508519 864769391 144344162 275623446 283568621 353753143 37769137 365777699 1738804 197429977 138930422 228896242 597154946 738343826 75248945 766099337 174691056 387592993 361481783 655439359 700787649 729650769 269089010 944995388 105680940 550688678 702401738 956212868 366887682 927053900 167960971 909017656 750393074 988867063 84802585 452556268 227084217 483066971 139995849 320396145 10717649 448251091 191030396 258521137 361454481 669818890 324504418 750802465 253588908 969163695 190706469 611434638 366528932 500123212 270520513 834898095 455322628 873818472 69674546 173870549 191340957 496966838 298028186 857613813 755509873 942918147 686040552 864497580 215596585 661464134 422576363 529412345 42341151 311447909 559991917 825820683 681568024 993606848 550891359 865373526 844633911 991979525 215821437 219008245 867985461 951951538 227406036 311901959 868744414 905429253 639631880 883325898 9691168 556485257 578590059 644513849 126488801 336571632 135688556 521880976 345592493 558844698 19374725 619872731 301490210 926068751 323117369 853920432 646067699 926447861 179406758 363664450 62433051 424418155 187995004 581605662 57967702 529228639 17906863 777807388 558094134 882438139 262232442 843931502 460733498 769004134 230831995 771370024 257687291 519532649 485030877 855441632 218310062 636136157 346039717 532292558 421708758 972638918 199231868 841572280 127087560 727184714 277310746 844578884 458446283 838299717 624126771 696373423 154699687 621333708 35534334 514205863 451061839 580799944 250601161 892370082 686279300 832574511 100769805 531115497 409173383 616815687 431151818 450767452 325276147 866325908 413759901 455412226 127532091 673786306 117493157 842719654 623361510 717356132 622717886 768074483 565483908 690695031 86658148 91596571 707302450 954213865 698278303 955166730 271603364 487924016 864318104 916867274 276181565 525996697 504616138 958145170 242756697 833933120 144740607 974914998 624554432 692815348 276395165 776127124 315886337 895811546 588779547 971552774 377449301 776297504 521546163 573480893 491257416 973393142 758500554 997408915 140342565 837177606 90572120 958517636 746413590 916516411 299746677 507916143 30881843 187499892 418755487 999297230 255962559 509597469 281366577 650898096 88260202 794345463 12730579 32402239 681625459 711179123 461718452 709391164 505293694 522434057 514291175 904883788 169541224 601123300 17803932 159001120 44292619 909321077 646390598 733468355 315645190 522239508 106032081 458528341 10013756 153066389 512594722 961980417 846053887 872660762 63010855 525348475 385591940 709253580 189137426 828069734 35677029 421397164 588134036 664740728 104571441 175982915 704154613 748855965 28695429 269364621 493112090 804958473 320218979 414599994 158920941 604306003 479537362 717495595 274987890 778460157 254564091 936254983 252312301 940733675 214546835 307410613 124249133 468683633 26331650 590768600 321963122 816617159 255848812 748638166 572776988 977144027 31657980 881339490 340908742 817944275 62349942 508435241 664034740 933452858 640648239 690258857 217190318 740231302 784266864 880236975 616870083 977630336 269808165 789573895 708346735 801344810 154930972 936773158 593513747 889477307 210611063 666381578 6972178 676094370 512261114 814086364 599104451 615938947 1607261 303570812 414074054 972633892 686455853 702982368 240566719 737477582 222695621 936300929 143004149 322209172 328712233 476132113 539483589 797206719 247113533 787802850 131316862 452735789 554077501 879500415 408166373 983708991 365690087 631156680 644076188 654756242 203292132 660575029 461422149 840655910 181107046 481029612 248310012 832631971 44700300 916523158 109584569 296418788 410082768 960025874 746370102 937777358 615164162 730010982 588606177 890361925 480142577 603894709 90274411 799554057 23014820 617314188 144776035 960606900 284777349 564555359 429451114 670752641 123089376 382995376 15337157 117875987 315145350 562974158 33351481 105929414 314720165 588774496 50266661 922791364 617326189 845276184 4253364 81932030 561739882 636263011 386899562 990064304 12589337 438494385 841959644 961157830 504827846 975547400 207867148 895231536 26397553 836474587 347801433 582113152 30445109 682172092 662236993 745673392 177618828 392294832 23946373 373968394 618293045 696340340 511720485 659958658 72316884 441335134 667776893 798723828 136829193 629738211 622592072 821120759 566563738 897677474 310558970 624708217 167827068 762483804 203420513 721865766 596943679 926190917 384027797 683179616 357490825 474270009 252471367 466308154 563427166 739248032 407078144 985871977 35927444 660730335 239649315 264606017 124317518 517055357 158431017 914950965 259477676 726093569 209131476 879957424 153034049 817526936 122612022 789131857 93543813 420925542 570452307 979630318 354551072 388678014 302076575 939192787 37508078 898799543 44349229 774847867 344670673 682048034 784458211 880855536 356991836 724740908 399599968 783888265 795440007 992549351 155271063 571091419 274900118 424660440 81329483 908502239 405290515 978626520 117202092 300661145 602919063 801955611 703052929 953110609 71826490 210916065 176060206 717561449 211227804 395142558 9296987 475647304 88910865 851642485 44136795 301731480 419973316 471262000 501767709 754395825 912117295 912699278 620492381 681430079 542326275 699997932 276367459 638424331 18626577 628240931 343061678 797356695 8484611 474857394 624739686 886954668 780659227 830854686 339852872 650868238 378619424 498744010 23803619 932780244 132587591 238715664 263856754 730976220 32851351 991356755 873171720 930992640 176993179 453108466 350510264 651497701 111056374 822013557 650972051 741479964 408825927 973077508 149712913 789796075 542571213 945035512 368659016 558701953 302922242 443584436 254586972 922167309 461171161 743757939 68517216 569006766 285566353 871033301 147502166 745342739 160455422 223993242 36757388 70922283 663139562 952573370 530934355 772059644 760415040 804706418 419550345 979885314 521702742 696988434 731521733 799456889 247174322 657587470 853936603 979029739 115526932 437850337 364566587 847328856 36149925 182092114 855879417 905376549 133998615 424128187 688306129 755456432 374521921 989723569 228050014 959776980 80980175 966733251 843159320 988997913 77466666 560599426 463566323 708347210 37920118 800712689 216324688 407745196 266801701 432203679 204851934 876710387 265712791 857483426 73114409 340223970 27605020 417585287 532208172 644886229 102044885 867269581 315629513 943609069 416674667 528396832 131936967 407314359 11920825 366838039 230531370 272882599 666673892 774429786 912822623 977733369 728597858 821433423 140101840 262197579 508236428 673576602 411243461 954005165 64052507 765286395 54084830 318363987 627641850 876217646 157578379 453101089 289240529 444531464 384102793 866430789 96089267 177758464 140645870 217078475 219344056 420449046 37361536 251645121 234155733 768135818 324520415 402524031 429048982 466632819 646116239 816920806 263646944 550235631 38173054 297224748 38633350 478886343 540395166 708099605 120415307 343574445 511712943 987813911 728200818 954674853 1764135 57426029 299686507 608164706 321260473 443741314 268975222 891225356 445413808 869744454 768639334 810104123 428135503 824907432 35007266 119743366 506513001 967189265 134289730 157822256 100719282 512155337 43199183 383070158 449614697 628657607 707413894 998973344 315421671 836015510 45020391 153164193 448047582 532367771 441060174 937741927 133396717 885867479 691235855 697865430 437859384 579059883 470155883 774741789 801222960 827781658 142225284 885986283 251673193 501297554 537997792 885808980 330849707 635259439 83350225 704935011 642929911 964030296 127445927 958739404 379376346 418168651 327367966 854878844 363010311 697083485 301306220 964941867 20948998 144341592 138868140 665416581 349796479 482337384 249134894 492155960 33210046 297090881 228103825 901779861 694092411 948061245 166593734 845175642 53078912 787506738 414892254 551324283 34688181 217218807 295185949 635665946 4408505 497369564 557666478 838568100 562756765 876031336 34761388 574031330 125093573 274670844 164128438 680512953 241907241 407256752 447723479 802937638 379303353 976686971 42085609 773778623 261639766 338477807 838955352 853314352 527740102 953861495 171156676 753923836 14951503 958807418 591066755 642362221 164921852 698575789 506626488 651676163 581028677 979430606 683203095 950386477 402838084 844540514 278737812 556908385 299520636 980736069 670636274 695531795 82427865 329554501 449694249 676404228 748262409 809296199 183800469 639294493 162454599 521487881 70386724 714613834 133044951 985372058 17568812 912822984 305749610 954399751 583211810 855076052 48496316 742406042 798301852 970458024 181890483 209686509 101592341 305672510 921493679 982756305 163379136 520264135 212980300 557933314 195734062 567423515 575580894 611463171 513699661 997811026 127314529 915465584 464424886 706625684 7514967 648896342 611637436 827257022 363754690 406409998 807676216 953409386 23435448 516270310 73177198 742285752 394534192 577332222 48885143 949442573 581469313 921794619 583175645 709753919 93326141 376675835 338610506 837534711 421882262 462076952 31864660 602246007 89264450 703945443 195878979 860567189 118604878 876654655 304170115 431995785 177200798 385515395 137248949 701567484 469967567 541880114 87979674 213281676 604280577 905414011 94117404 648478043 316865914 628367912 204385495 849029128 83972370 191847567 81838972 301825534 109352604 599532410 432049207 867519356 380052489 891845516 77559443 633379210 259258593 315733304 752754377 995248614 608577984 962490860 686108345 751619864 224592524 743337383 28854455 611809490 430691912 869722320 213578028 498925249 514657927 801871958 713539243 846097847 111674029 759461077 117189426 928565379 311937637 413435822 174875142 252103892 176676818 812772712 5804080 268360923 94397360 670277335 75634250 749682416 310703641 386873866 356516531 606104642 464714962 806899439 367972019 851787195 786986279 827892898 386983070 839341681 582267526 980954057 576820272 583772525 296744302 606572444 805991784 890612992 596776602 931371581 279505290 281718879 221955637 855050797 173800817 728273184 40232394 805181849 85915667 668790405 99124541 812135442 536393739 918716546 6955307 555946232 116838504 555909038 42795618 394812348 323099666 918880792 30449110 287941637 422505615 635085457 497307847 967041955 310211151 706952967 356049644 425077196 161578000 717979902 461699992 701364747 328134742 777874759 693192001 860051856 207761001 443087808 441405385 708691843 469404885 565235977 141857355 897480552 731277131 736028180 645373058 709708446 369651037 561835913 27266642 939089116 530577598 898289318 115259726 320600998 486439693 953828327 94726887 371099764 602374784 659135691 293228901 857212109 22808852 433899650 658912295 736211885 232827005 567095598 156010610 607969548 607216680 683262208 89975730 766103379 498319327 844597592 90399040 721872992 245524353 761377716 139070548 903369679 186912781 823920713 181114511 501332110 548208074 555341103 2445782 866872963 931967352 952239759 642055409 917410450 210671431 514718346 239731819 649209773 89634019 639987886 282566026 808381580 169463398 706341555 292728403 627710816 592501160 955449910 300753053 898972261 964258719 979437435 615067450 800528119 397433191 579246009 13760405 984049543 415737816 611997282 592088086 881802085 223929450 360686950 56936834 215706549 321188072 330638996 641846311 664571952 372680808 626215043 223761024 593197218 771795989 917182468 909446806 954163642 120466808 970479799 101523151 753252361 468357342 876688073 14476126 845918357 358610309 965428042 639171307 857504791 423358325 486597440 726262370 985031850 805229609 847728065 305450091 924214713 565971712 757873763 30944830 285182756 853730388 907874154 545357824 987163990 164171236 826199245 59312116 760746992 401526174 471546293 92584110 787450394 47041051 579977840 4764393 204428281 164129190 668423026 610590583 896316448 732019236 930765115 11391194 433700293 438663220 452805079 839274172 867393803 284311330 771127457 332299614 991013563 76082280 845936160 185967249 733976735 618133402 918157645 376926910 398507822 16133105 197552744 131482481 444168150 596740734 942081237 281933223 395398496 263231023 414025174 135401385 486244760 417738333 814207000 203946057 786653118 711181963 808259812 75703800 521702934 342673943 793781417 106008965 922494337 355060399 461065647 523544642 593569709 265898712 449160204 754587917 984971837 139274780 183552047 379482503 685777662 633768924 921382177 379327013 483199570 485766740 904010488 570136188 758306902 129983437 914807191 111315686 529504253 223530325 293394071 532656717 823055644 191339955 343814907 506097970 774779111 502384059 829418368 725517739 921006798 194395966 252945393 36537689 932781814 753760123 934584347 470614545 483673175 171860499 872730250 608880573 737493990 499183232 629790593 329234301 786951104 518706888 536881214 791107069 875188396 591445492 604878168 560833834 653717518 566099595 969127783 71742018 448897034 339031467 691613912 401517787 826045680 264593424 488050321 241827513 604875367 165946130 406978724 214321740 409051061 867954066 906264924 441088907 875819364 312006699 907536023 122629466 559830428 369692855 443846900 307569570 752362143 169003931 659899492 47772312 354583997 760867265 834033261 594964212 775966561 415877357 464838022 184120598 720241011 457173482 800334249 41697956 247640707 895788097 928450531 556530000 579403206 432014196 579881015 190373750 891010675 424766290 845906555 171838541 643581028 191832472 393052148 587594654 893291806 330418765 339292785 199038601 704969926 362729323 569631316 475368115 581503552 360561509 602800283 302693267 797601086 427591961 628768788 397572524 966555983 47748453 471080255 590864311 708331380 144906341 665273482 233682170 901680626 722091394 777125125 71816866 199698460 636873 95149868 317793231 891998129 109643639 728301565 177320825 872707567 6555936 783707720 237264952 499760454 157002472 933821427 403320083 865254079 16192388 714833977 168180868 704063079 6164229 554243854 314493098 419424465 388007775 968910524 200442053 407105369 78404589 294457788 567406609 824769681 179722624 345716846 293888922 970919855 759995072 898088679 41606804 529135193 493916977 537334572 157242352 765906031 634455422 748037195 151235852 436046000 19514985 368732220 40301883 780878189 153579451 790828295 583702586 812943107 36207050 392374372 227647716 806966670 21513061 96504883 458159127 531575318 592206572 878579525 75090816 488402768 109395207 820092885 221384471 578577819 430268112 543157135 127192247 440868080 243498765 265129574 47529613 777287436 33447683 870357649 111976117 448866678 635738030 753433978 115033134 205708646 33766510 626170236 73923152 823200772 618558244 670251458 581919000 824420722 485969284 493248703 446323671 756670067 689027626 773916687 37755952 984025036 38887267 384666634 246906234 773017742 96336570 317647534 5628145 258647119 629940275 995241678 932333313 957221397 677042314 945295174 594648178 721719902 38931587 271980742 309379473 439518871 873518162 884535344 172035607 951583848 329098746 521229857 449868363 718737930 766449993 982339055 362033340 988544229 59097594 363145097 28744973 948608517 31292794 702875045 129892005 482301686 143098418 489130730 755264412 872563459 272068544 880999038 208234153 397273234 760051348 849013566 22437444 926672750 62583802 321091808 462315125 867857529 158675000 945444675 137276768 582280675 398626056 781772943 736323316 877542750 414636049 786234305 30565095 351797063 90811516 877222481 480299625 574640612 82172033 582608636 660382926 680688888 390549703 662764302 301095249 341011822 197008993 884752482 665038620 750626078 198368763 696600372 9300518 103205290 494061341 989138346 56953542 908736051 178357182 255352031 238434507 361287207 335125363 542939336 418819252 844493934 26211772 472024294 410621033 569169716 310280039 745414405 466381678 612039160 156500339 525768144 679491855 891611930 772210953 810506095 479221444 649670312 475088885 604399575 471221384 944520241 63555104 493396833 463938260 527144226 8476251 541189564 311577715 768302984 42845075 210297441 596694571 790846244 299499972 691507188 472395308 924173903 336199482 361481689 62724468 152364554 273033073 563695392 649873294 662088932 290890780 702081367 18029515 541230956 240947067 850608301 302308513 512954630 359956303 484596541 187607057 219754499 7676598 935843862 211096172 866453499 222340311 567704359 327981353 338168513 287792916 975712655 326496337 490541899 312824256 383604777 616774463 703148966 96128455 300114894 96850250 597012710 137046088 942467837 758450674 937131957 756338883 897354254 48962877 227167352 382966909 625601364 550419621 584431820 159536604 745341575 355021795 608829080 755127734 761963570 260054587 873981399 378040222 412426967 188952075 436429900 446449273 791317614 194233834 953130568 715535862 786548719 251819314 532486154 886693126 944315495 790325109 858501873 38242674 204456468 376304845 728584958 894438415 944352677 551627818 672714258 416347814 440927994 500446039 549792705 628528625 970699040 129854529 258040938 104941481 678677243 89839279 978201464 259689981 334297609 479741940 875646049 348296138 970047651 102710406 148356295 246556109 435990440 273094404 591365121 552998893 578821576 414522637 766692551 210805925 879820853 431890600 494589650 253975251 753870123 846139276 943463173 392278824 519774067 401955319 834165598 131504495 685802593 295733570 386400908 189050236 193458797 468965844 619171893 145961569 226332752 120143622 928666196 690966789 964987261 43521940 776041204 673414253 928055155 117362622 356270386 629489752 674418657 487184076 534795976 170453429 320904807 87859658 938113937 595461320 610548787 859752724 929797617 201311180 592129915 100280226 895484127 374346076 455904004 198802483 396636604 190064353 598606774 151319515 531070175 198691025 945777308 204487719 551482471 760775367 946622405 274711302 550143696 52627910 208770834 266977276 926560210 511433745 703663972 174053564 509834281 70104209 706991025 198665155 765789876 333839071 611419181 83963390 212212764 165603431 495848530 596564362 657447654 457118170 849412557 625051217 913782273 652844412 687168013 115585968 379709789 306417485 504439098 695514572 826989978 132962695 339107175 117846168 788272448 832925350 893618212 57696032 180637234 104240425 589573027 117941197 721610819 116616018 547714695 52804960 276142112 30821153 509116643 332505460 531853281 367005376 393530078 54914327 600651950 787534794 859330154 889132195 900512325 505193592 971633772 410249343 938891090 663870076 751548454 786809186 970433793 367098400 636567936 284928377 551815377 30863885 929652226 178224907 548188884 442580110 478410998 565774172 797830208 349243657 758364768 126693077 995026398 92509678 368283937 318776363 927143261 372260642 709353198 188647754 318325381 102986430 792146559 143992305 251387357 251767535 569783869 462994928 910166726 81907221 496966275 517560420 859547934 802989498 947000299 309207729 322110017 526711425 852815424 55192090 971163568 83361651 465757857 52568684 343721409 196017218 379288345 726968434 848407930 370958638 908954183 163741858 808455479 90297718 95673549 530747358 646914858 446044027 479282021 221798385 793960268 255196973 457472882 848650501 875393019 319877344 779082567 155751865 673391036 1522252 441300727 810190146 951592391 244602710 802621322 439188186 859698334 462536753 873613182 305910408 510511041 77896838 590296158 382967393 933592490 473156700 767493281 177658470 923860183 531228324 894422683 379593723 482966620 964032797 990079630 168912362 282710802 91691280 591371836 762339166 903917991 268874269 758829282 305676273 375010070 401708332 917183713 692672392 974877079 697250717 972234257 545606913 666494390 427223005 537465864 281258204 680893599 889754525 988485528 177415573 550118592 398622228 929081520 79268147 134618944 96701963 371911986 359960059 438495405 773383759 926109003 601722648 917752094 305437357 664400328 211844446 288974506 453489889 725723490 188026528 450196321 524610670 621796586 509774769 558220989 522486218 697303177 8756013 285181671 226346103 919709270 17921699 312485199 680537016 902103626 142807449 690488624 80995855 632488778 447089515 559257997 91788977 478709187 42109437 187327145 421018950 531271827 346359887 624432936 90309650 641057475 115189497 730583016 679570752 890992811 815227198 877561761 214324479 869436361 194657562 643848173 757853339 925222905 411280978 746968487 715102137 797046204 16726098 393336423 260118896 433739265 546150096 753078446 495908131 818489409 67489178 934014205 240733286 771377094 453067931 859828459 209507363 969122404 66857078 667490457 434755529 541164443 897159307 906920917 473672166 662647739 217328081 956604122 2696746 278914416 217984066 331054726 13396378 834008941 800068590 907997524 448625490 655291418 113805200 368653122 128400621 413339309 295678576 545967897 420614505 525989368 564702981 725832646 209836097 568540107 522214710 974210493 861966715 973564748 310875531 806631807 202333068 708978476 305772198 945983839 340896603 929076433 429384450 622445512 351972812 948837642 373489937 557504639 110356231 733740180 852781207 951057186 70330442 635258209 89300039 391643962 503033067 638303176 26646849 779680548 318815234 857752923 122829092 824231346 242587763 513232094 205005544 845192852 61672743 841323977 541046579 735803233 386835887 784533118 832728294 899431564 281750248 388947213 496263672 748183387 51104337 286021035 410331315 522068075 665484038 752387895 521815630 850893366 584704036 617243534 59232704 858533860 144538867 677976515 315647840 527106343 272387802 576193202 71108935 695246632 525085535 635342728 4288577 8760948 487075743 828052343 113033858 892691235 12318902 107783734 331363340 600408903 655889530 767641614 545342481 783556940 629798721 871545422 300464363 712937403 388492370 979400607 154400314 618817100 516599061 768353812 21962343 301215410 472523471 742425203 451109523 618909485 62188808 286759814 352534179 729396365 363862007 486014760 484716256 506491062 19157312 629010365 491124083 557200776 566514849 899718631 359470014 577938024 8163495 723820895 61176126 243849426 24447057 945958256 616299795 954928730 415080098 767373703 41897532 728854432 243041961 584176536 136629409 727237822 641795832 987306681 117237752 160568845 466232378 513407426 91690129 704965589 705440297 721820451 187785600 321088403 268388086 692054608 188146429 458558675 203718869 356315775 976185397 978216009 73820963 849795479 262684647 906506840 47433393 623790237 208844971 603165634 766191297 863098990 344013062 770366758 50780397 413888723 559050218 637891515 91522049 203932622 668066276 941100487 23850204 564724724 365628586 909438006 213804046 907350839 167285500 786401842 69566247 930591589 205851841 958155326 428161596 692766164 695207202 840488869 740258061 858080693 283197285 587804465 352861175 539961869 206283167 689793999 685849952 977023795 785110456 980724962 188854973 853434862 331011332 433630782 474961159 821318529 235960729 630522188 697895322 929966205 239298947 404011121 200009146 422682014 69507973 616650886 459007007 926862123 566573278 688773804 809525644 964540028 387358816 732788554 355369588 625600472 326218763 395045912 525062573 920654184 213032940 613936210 422462002 643641793 482825229 650811144 289067459 845803881 433067579 938937882 567132499 972351613 118145822 602083149 445743643 494766342 11972773 16565311 694270556 953226954 553460149 671266723 884398456 985737015 42598990 599191999 94937520 483045378 342611420 795235334 287359408 372509024 300047636 834273737 517582409 794597566 346533393 784525157 67384479 453702412 406182868 672523882 323699975 784766188 267310098 751789032 194728719 661631204 256782071 577078340 144865192 902475374 171580558 567567422 127676248 754298521 262596151 975400292 383562235 453264240 117420422 675025182 288880765 527352953 83565354 967648805 29754490 71867771 255546196 629025302 409818827 676876255 222047592 435937510 13579489 36682935 28707898 417161201 641878755 943030997 354836592 385028116 254117891 901579600 959574728 998945290 352584439 629101612 162757109 570450895 500443098 908774420 101269986 774472701 64535115 824548086 482434611 727219949 539188861 774419259 274887930 796055595 111795070 533044991 76204262 867370011 488440481 554381407 462150408 778664939 5580673 765078230 410019621 919944371 588952355 839244575 28033911 313031162 573036997 903613391 295231968 353924150 29429434 706282135 482196531 581973461 49191351 163547452 643713426 947259356 224113849 760849277 233117371 979380697 466208171 502815101 436530476 521268177 404560171 541381045 284003009 492181591 159337113 877899072 532862309 990972926 431237408 461538648 48362855 485775370 86740210 972010030 473553656 801827960 40725933 126901129 259894220 314470822 778784284 997416911 209054932 259523929 753966994 927522187 258721725 920903394 468360111 610508286 560155875 614692248 11783101 294119898 455396440 690342501 279054284 651702489 608928380 668820538 685096226 944388836 648438382 919576154 534768145 953643402 767982366 854221249 90714014 345876090 78029151 658701162 452612689 968689273 390736684 488412935 48956503 223422483 4483817 457837281 54183876 618606998 399914317 602691217 22564163 639681499 391962333 643620741 645229363 727769851 181778347 763193937 186697129 308241474 778720448 832208937 496552545 866973254 572430545 575637455 294364781 897499067 440403884 976738822 113295905 995477603 23112672 436676585 95461897 931442461 122051869 488463594 389938864 513800309 451870389 683110896 456528122 912560966 467471685 717034565 323328695 363118242 422982598 705783155 514705431 983450705 96709139 473434706 553601323 802435937 254320775 864321991 49138837 85196141 11621549 167618433 741892823 758645333 18955910 630974212 219389727 557311399 243871627 244870715 585663914 952607905 72458771 90805920 110681902 931681459 161964974 707438535 689002998 746670590 203067861 538022528 479030567 642828252 422849468 916621919 602112261 783352929 640418017 673082869 297769771 690904049 769077971 875663583 436319558 503832594 405880115 603708714 484229595 825130827 755426304 820278136 201474071 566039480 599264990 649491354 372163271 549310187 812063133 821467568 66131764 281091323 193736 720816929 114989722 420434319 382157452 468429420 356083384 656498972 698737488 720403353 539490121 874867127 496108965 849501385 226319970 880667278 779885249 807323913 283005855 720013601 196497273 452446707 124292525 981226688 134944628 913696425 68448131 213389237 255949410 958886542 173231999 599202068 388979938 909640954 329695839 633077608 565298928 666066109 178994277 393498419 305170987 323123258 181235191 908511947 518161293 842227779 615710634 739078204 11725724 703704532 3526415 711942196 626260593 802539106 159619149 676440730 83986984 316707193 8912169 517241773 634104176 678391165 626428035 974607565 309859301 400128461 427011619 601034904 202086473 816171017 729608975 870426122 215633698 505858663 43595285 76227054 553017857 779874220 100180624 834057050 218065531 416686782 57543125 398333063 412366840 937749290 218930604 760892424 69322185 351918770 215923582 274549702 183113343 587493228 548378375 773443897 813153944 824040038 154810848 531386272 618734877 744018538 115827811 132224785 721807886 931445399 952443378 953248483 624302998 726249415 142982626 502451208 603917857 901171745 224483733 294260714 400951498 481601667 688199031 892470400 617670813 672430812 703567019 999318521 677772153 723960271 72838610 784747022 355442290 749524420 731305 843799992 380485418 972820692 43866644 580609465 445032688 465466197 326102472 476855798 434978495 678243680 528022846 812217256 107190080 349230716 29319050 75486440 324446036 769103491 549399509 615434787 306181328 430473037 302247426 799496336 459773821 839489056 268155711 980391833 244261592 701133502 126053442 150615724 227049055 375845072 104103250 680894292 75953001 507069109 312238765 816998341 240923805 318312429 132287349 223623325 152541279 829120117 127438488 944624524 225614477 978541868 35688157 145724686 801254434 809693636 519716645 959831559 212098240 964716048 481387410 713796791 386547398 908544248 259508171 349684340 312351974 790920692 80104541 770493936 481870743 553691760 362357435 593766560 117886410 629307991 35454367 40615861 161297344 784408689 224010050 431401872 761557533 984247597 610869196 818566409 29327344 535513128 243781853 938450521 835162612 871183643 472610178 967435770 482285152 675552860 424717384 712371973 353511056 662604017 216861773 958521191 215759867 543963707 263672226 850424592 141597893 409586679 71181524 121998891 264916781 297501720 789798554 948206539 148056768 862730515 674652955 774246433 120206109 588613075 57399098 245862211 883440458 908815426 280956159 723047060 148794205 251910080 691754423 741388264 341880859 697477984 257232423 974213245 110894988 618841568 121351377 697829363 650485601 727331958 431922266 718128676 370778074 433128372 136621938 379200807 327461755 336781422 20992721 309965075 493719698 688558031 116765688 388177477 563693992 632748040 410082276 644577017 349190118 514565080 676061150 869040251 70201199 969904273 438750130 560387815 640283947 809245636 105680669 184487751 501670878 576844328 218417860 455182726 720185496 951387641 62261304 802091310 375042450 838488283 26061710 991690414 190258852 418861314 206206715 910645645 399577603 855277772 211616822 375208875 572397074 994308491 220175744 893960740 365101995 404560296 264931436 819636883 221861466 382506385 168359203 333044633 592893090 703537041 658887355 993124097 38332295 848157816 12678346 960686184 501468329 541708372 259839363 834003892 526147516 614772848 674840452 913316746 75873900 397612157 646858432 832022900 690179571 808949134 592981326 828378059 286761164 699411827 83944841 721947133 658390423 797165770 817433685 964042738 266050450 499960750 569960405 613567863 250702907 903875867 129198074 675111236 265210049 782993932 341202641 658580515 99516031 747538191 765194081 871882547 88122797 276968296 349410775 973823366 650430069 717432447 247732782 722848490 862322978 944448239 148104615 718781258 214532105 925010395 412433131 918642663 324888436 611849779 165271688 613424739 51637653 663740647 787516976 884726991 31206586 469744295 256996714 961701283 46866428 217863170 183597195 809135171 591123797 987702001 146284012 348867679 153935635 534304367 572531527 781487506 127941045 300909248 336458294 977976889 282643339 353834353 137800179 211688095 320525226 568035793 169182796 499973775 217397287 219531088 349993394 484894804 125812745 413987552 514593034 528187342 281859777 706720131 891358275 977750159 271324106 880876936 2584869 935075774 465925246 842754717 232733548 236906549 594311391 916778970 678736451 922214973 666915866 828921487 215265424 349801455 390476470 394882740 227835074 449340341 257677006 749766353 45784616 218077741 847247767 873545613 101422355 898003033 331664843 428195790 638461905 967266000 609362923 651248523 739170058 864395286 879454976 966295748 205272306 979176403 268919727 750925598 359601999 656580961 164457665 966801341 350313697 549016642 790427594 885057968 470498115 861565064 562162808 618911826 423542320 829838961 735006096 783732140 747238469 829081063 53229259 770961676 77761631 702415678 299705508 915704261 701310043 898118292 838715915 843141238 70856919 650431040 290249794 783064968 102708299 264460415 150069737 244161232 677765284 909306448 547373436 581930369 185410485 934912296 76568758 245632635 499569868 832281998 627631304 793605488 540645978 553417461 403104939 794270249 518020584 602031068 275235532 349623093 283210051 377190132 541496619 941005130 287668990 818546758 251968317 492871479 122600671 418937349 254779338 890325659 321169546 746670331 368254356 891562630 246972066 895235464 259832587 618636335 40885863 478576184 694149199 769419131 814235034 996579228 645509755 964340606 502606874 983001940 416522406 767648492 828863142 924906839 604167312 997535561 297798002 557900942 214067747 391976593 27555421 164476617 755082662 926109680 601993123 834026736 286938122 539458270 775287689 778043713 581916533 608522217 480681720 524770201 132646049 477520341 241534864 374405532 500288088 988666967 44324094 403367155 450670491 664772676 228211355 935541945 598093803 753278569 448990599 511926415 459184789 515627309 434341301 940399194 376953372 977338285 304027159 640677187 445842504 831738719 366611 938779963 196511997 557730910 532071266 861577156 132189827 880258049 344293827 759641479 66611277 595912036 135292913 836448419 531721105 869854108 802821395 852078883 767547037 910646372 492244651 625312669 767436783 994250662 365657790 998005131 224591093 692189913 429760482 455936982 453528571 921957791 34972633 242365064 244732029 531830710 638965759 665570872 434730732 787076097 136464966 650998209 225831473 236893892 488565509 798862227 128662384 610998978 191112044 322964995 329532684 335969121 324704664 939278125 16742266 913256535 277609746 820317318 840489329 930733909 135710533 376288348 178668284 356680867 294401823 690715779 144575585 287720274 567657371 964967031 280583625 447259010 716961781 957941282 384353890 705800487 30215929 532771639 106675568 270147619 162304000 870224162 49470320 563863827 3252052 646087663 182141811 315194160 7216704 168283336 111487647 142679534 859587366 876670700 309407729 541498963 693268752 910784277 26520314 300249259 377853103 468407265 300437605 612581883 442804283 580426788 496992191 808815680 355539934 986129696 550744581 726272616 48612611 204801322 403754546 503262004 247527164 903234798 188547126 793450253 774141598 787072121 17322845 435646338 619606891 740538031 545544513 862056466 785808005 934339732 552703370 741397658 417613185 861316844 118545220 562978551 207443546 218859832 12849291 553154582 271646215 428536675 246501517 375673838 737467533 867212389 628578696 720768727 351767046 386212251 438137984 682041213 279311996 369351640 95458387 367227724 312251735 486482627 85506864 969029320 259470935 342066656 61318695 651859644 477220198 670718727 401532300 658194694 496609249 659315116 578663029 626398159 117783323 728697003 435576975 455913364 797447459 997046970 708696126 962145124 270514056 284493645 474144305 489220539 111853668 261372047 57856482 912597455 816208534 983761989 348831146 935069980 564875462 948064402 135044613 744454554 277179746 437943587 580117232 919303971 677448968 814430517 327188703 826477037 290205285 664307023 328896259 670946234 229179643 600389090 64430688 462542470 223098260 736706482 780366494 894081063 667512242 711975031 607887242 895462080 514020463 935090861 422422451 886972382 330749034 911418497 108236472 945783229 186531411 579271643 488348330 648711401 826263837 947197055 524636354 939980148 356840003 839215177 18791329 920120240 195452944 626420107 394322605 806132462 397305622 472082803 413719956 727877623 432423892 620458720 542217116 799739123 354967610 709558594 107911322 332040627 528919649 935985140 355493147 674867911 483437859 483801534 899948531 943263006 271916379 837466324 469681918 788015757 383082131 499506681 514525701 834994606 279783898 317774381 42873116 144467856 671562287 784543430 175190921 909298536 71403079 365603510 32707005 478586070 45534273 81105805 36948207 463082675 286103837 955121609 303576064 379153967 485528523 572849013 619404294 681039198 162641996 362819902 505601519 902355292 1186092 528616351 413540477 870862995 62889780 502772111 580413165 945124117 357436969 720197583 348347283 937436331 407967637 629814042 33118109 742320526 478971848 858550169 229565338 584785816 9204925 261722050 252638929 498642786 853528638 959509603 626302234 811472577 4295687 99967023 154560722 759861559 588111698 726693793 249199386 760590251 568329813 667107751 461819295 936292965 74828096 465225541 98454313 500161231 667804450 780218567 10365935 120606397 268348682 367622993 6516403 410615006 529774687 821719924 157193725 585700777 322321707 503355130 564065525 926675141 219044089 497131350 609624421 631908374 669925695 751728319 276385743 723899758 802728563 968516605 273572437 654682292 179361356 502139922 606580053 996280197 432630020 445281915 90459910 567090547 226934896 778240562 121257887 207400178 684585950 985445067 57710803 657724129 434949029 645008244 168672882 602436058 150975173 312688846 386376639 419078195 856221895 884296912 29742249 731446419 356016049 595654830 537483882 910737169 384807070 706436094 36275895 857282299 69668801 418774159 396899209 397771008 801655016 943700782 647587825 914067241 8342893 437365125 270612661 738264646 385415683 591800981 605073013 741210347 237302083 900450904 140873831 318954877 260482361 502197954 462192344 997062162 216303264 375614177 204030471 472171194 174488922 744069364 497956644 640826395 311577327 530562750 677233401 905159493 548834520 768652937 505499778 550721195 465079647 645142393 333389565 496845369 30392983 141875268 395297931 925266216 128136110 547027288 262946713 293609494 21243728 824705283 527627419 721159116 213810874 898402118 683191967 942434315 337700799 660485010 218050090 989520957 485681641 603719794 314034648 531850744 194160760 970794358 129795854 771182833 76652365 717242471 736127955 785610883 84042081 521254532 147320681 752212017 739485294 760080363 518338548 930149661 15642560 479873495 442078880 658954179 106315836 261360211 54876841 146214022 167823595 745362729 71986314 127485313 223975968 338769171 914465511 993146766 826632934 958437271 173287423 546393252 24222149 482556552 799407637 836731294 534306662 723027352 331174940 638071902 48276404 872675516 114292330 788796392 12925702 839481068 441976374 665444552 19451009 158398569 223422377 829221671 411499451 802213707 129978580 572961315 21679762 921926224 69618581 760689713 853948879 963242815 627768018 804795481 119332143 155833811 184734009 955382141 294166522 828335838 246177176 908622892 773892151 830500338 278848144 835238432 113823219 482609352 480129343 610937853 27837383 586244931 29822675 308320544 153611204 601144831 338249366 776892112 6883888 775666607 340357410 589720668 526584386 538111925 289424015 448318785 347635468 776094168 46992713 879831915 576662262 866682668 579697852 773700094 281825280 423681325 538879956 599585621 405308688 630902198 686488166 772822701 658318174 874689890 689494224 746206946 728871930 954682554 629857906 962679298 208929935 595336820 82621464 932392420 358999055 763578893 221559942 283620893 601697743 806068979 317281258 865933515 176296595 271314106 252220016 524598200 6674103 64359871 601723682 671034090 90376983 279330772 435440423 808086588 415724588 968895897 394513949 621018186 127364052 923775446 393905021 932192755 527267427 653364910 221728416 498578432 845613036 958302472 261685887 996430603 372705457 419400529 698264983 724685309 85204549 202025423 521604381 651841838 275533137 463769349 315661981 871858991 332293307 463891056 583140692 892186617 314754768 797086090 561239968 814017977 460309845 859942374 25046015 497224163 58064755 799114299 276343528 514982580 99960795 133647595 19278787 140062908 784768844 825512318 25166854 156872270 206151087 773298977 174502186 566257760 441066559 541709258 476833594 666245398 766705584 983894890 102666581 679477943 361085537 572731482 113353278 693242713 504932023 823807996 222175127 503758261 153363877 879650716 448862074 998282681 3199783 738335878 725349295 931340392 160956495 336126596 361875044 617769963 463445564 980279018 50815850 185669787 257640777 970828977 171194545 557409809 128461300 445102987 330604121 618187866 432393015 575048227 281058230 375674853 459114031 844001050 227672311 868743661 520926073 558197700 446009030 939670405 81805686 745840133 388497437 487022350 389414814 921882124 218477470 383763772 87246959 186869521 181925664 758622022 370559013 900966886 146986330 896349885 151826142 744425172 485788303 525527757 615204939 703823582 231885078 382711905 645733547 906799280 21794929 991412910 392358618 594413756 413699252 435278748 440426377 766887214 286637145 802415178 580371637 946151907 99982019 395058801 238892789 447929923 229104424 900688250 410272829 661168363 862185874 979861795 803777832 896230629 586480148 977591736 29194451 185122512 20725195 818604594 152033295 359409846 520165649 573463454 724329490 944656038 545961973 847751790 456416405 847519083 362444917 738627555 352477187 950114468 219078045 233784053 193194942 569617084 510416126 834056084 372926836 444171944 267086990 730533055 243391270 262932985 507978604 534428486 339722237 509649567 140935544 384204377 295748734 458219388 210759505 325617768 142145420 365298053 433491749 487275439 152457484 417602288 94662349 596295267 184984161 960563912 656971372 824014062 96184115 630162210 213538041 632557683 269301484 651906139 734579458 938138385 96939162 944499953 779214406 939990758 179894564 630795384 264444936 557994241 108612979 851164246 307367340 609064679 756572511 843112665 441524998 547645655 777200932 885726862 566555077 904970998 391458671 405831092 537918540 969213272 102431451 621131287 459308412 644725286 64846660 701015220 66515143 890762348 725085778 869390057 783242942 910067791 599473084 638995482 13113853 332725702 27705543 444706326 135646498 567042492 366885014 888748000 16875706 919370337 499935139 615857327 691832498 744029725 543685622 922359356 707459853 960471638 381191834 982974429 233299629 330554101 173603504 609879090 151018363 873306744 455083184 503999675 592040577 692757493 227215773 549570890 249364207 859677297 499604653 778067792 494699846 857275258 315619098 430960569 168208139 475236109 447912266 653903541 859075052 986489189 415734679 888608360 152897988 348760736 73368921 886096728 65762446 642008784 332730740 381686620 443917060 555764629 646955736 849446327 23168853 879966295 464903378 686579475 584261509 823752566 408675980 748805702 22742831 142142215 425766016 701464637 36119074 820444038 698786943 889819744 629941069 688898825 558850109 605773970 201003014 247006701 243887000 986121688 23582981 890266921 927323463 985360934 100370955 960922550 886741424 943628572 871798320 983690859 692659910 760137221 197271702 436954371 25849846 470030871 256911875 480087905 251620228 580752379 107068607 701675205 305916153 674087814 311038536 662408071 131460231 287299427 258411506 956139852 151093096 158360748 640154794 781890405 646072724 734147197 497338744 669830716 91877759 406089785 130007635 436018815 113127597 285538688 122269271 938114695 19414567 654803642 771226505 812450671 123121117 296909669 62407384 978882917 248385011 369458884 421938823 783942712 55528843 915083767 286282333 626595665 181038828 814529872 815503988 819847589 479525949 914327924 117135507 400221052 634385232 708432949 454946746 970769055 196423126 259123785 353040952 966800924 123232128 566016386 109690641 664246810 703739402 854866506 38749397 710459498 95376981 185580765 462133852 931171759 344853935 873864403 308617560 889492725 222188403 783441684 286020717 454181366 658809682 705081817 373043790 802782494 531898358 723501859 578633684 770973236 380507381 554196237 671564303 951786602 261940591 544992927 329656520 726955408 465370247 687797192 348214040 930796419 111545376 602134646 464414349 663016570 573260551 691463325 129640723 412539047 20960497 859888060 75026312 420611086 470676049 648078201 466360268 844027857 63358855 735859711 268262707 957515183 644443775 829352160 484402037 513625433 36102149 573857381 91410191 793784990 429762302 431379643 535317420 666448933 469505957 910373032 286917142 350530951 226381537 304473868 334650523 486335617 314523251 323327095 297502499 368101820 65536416 188687590 549644282 840683446 98293717 400729799 133509326 888334289 658533887 991893703 577723213 581198746 147325628 462017364 508152115 897141707 549582687 645710468 390807550 445237559 164444076 250921424 343400101 656590589 350872718 358612733 21213794 686568223 72088104 658518917 594607283 870978612 661584829 826182028 331900437 631072914 388871116 526916112 746835689 812687782 48155155 534297994 292735320 457903663 155683023 870484458 208190493 650050241 724637092 918918937 28387079 439730587 322950404 603542752 194162922 255751951 273555084 438674851 390026394 905806534 585896786 807122779 54021943 842863466 294321077 315835089 15208603 219412501 234023513 338005676 8684843 692782861 202862217 949094556 93094072 744087535 503903204 680263616 352553023 716112406 530926127 870581225 275323525 794101845 672568966 956440430 831483027 866049647 321168804 323349992 725183246 939534632 105132116 577044350 47386826 198942486 138732280 690701840 846539265 977091117 57029022 339669878 740715070 775326509 252629364 804499176 445030105 667563224 310211532 526790289 25681676 736129115 121026098 221150179 94490964 202971389 268049474 346379174 426766841 599826083 391944013 513215538 22489600 973547537 85955019 586331246 524272092 987189526 642701655 914635310 280645927 457902424 142945994 278271017 415682181 945038717 469810264 568624225 422692510 999685466 36992547 547748475 309511519 764526276 376191139 393614861 708654181 910866124 107225242 117086068 217246945 531437951 108747495 110207529 324537579 538618293 16556262 256343194 655809180 835273483 376912256 741011732 520512393 582418186 329342751 395189946 383181933 868073969 108945562 165847607 662124334 705624499 389714820 771962627 17018549 966974360 832231568 882798203 470463917 582163427 305352871 498559712 244139724 610338246 154454306 388161820 655477205 692701104 239723782 437043955 17913150 876322325 76255984 375226584 220156145 289639529 408224850 452028637 174072950 263277165 495488871 799488449 39201748 460803347 84245859 461933113 20182440 248417422 430204136 833585734 409737326 992436042 126576059 652605664 87611841 369207090 310728607 870751278 162600402 686009955 405992970 886160530 362685070 813661345 844271234 868931748 86861395 448080174 184438845 580872813 533833354 674069897 190229850 356705341 285651190 386609437 481206208 659953625 514320395 664151316 484304537 942694423 548847311 837835458 491183689 750680776 370664329 497402037 269702965 609354319 275692250 733629723 958411501 983667045 158675494 411048044 315253643 680068021 69917252 978528390 390620761 880837908 58595123 956118049 294011420 468470819 572293159 675174876 276687721 907667020 414313479 738562880 215369212 673756102 671705480 797486237 347973934 363348117 90639237 683142795 355688211 961952109 206810569 851256086 101470996 906532866 483443049 806660067 24952981 599809281 432531281 891715373 76582249 459725890 497857855 501898955 781776454 808827975 198553584 754095170 820396061 849452302 37629949 152200101 872411843 872980202 232888448 908131613 490468157 676941647 66922321 248591203 227854448 926876060 387750801 921631405 451552051 978058072 219010261 882010224 205670253 314119334 187327202 684150519 30443724 179258775 3903226 322734424 428820997 565895068 479921799 741203777 455227673 664218913 128412404 182490304 328423368 953784798 354458939 837868350 702499815 892568407 74823339 843375760 483781312 708768092 487444038 745080355 376635662 425140014 98661573 364395790 140029646 765813617 62981128 408416833 568019175 621515704 967633421 976442365 23411508 982830504 656398075 768609896 213933596 476171946 67356901 459001546 342673088 495511611 276433452 940995090 467236445 808547405 607356936 981049582 329921757 884024372 107558635 543277462 761966536 880405367 436702678 747089290 193533044 511694568 349410045 872786936 472302821 580663010 150366487 680518919 466075602 921938196 173205276 304342296 238499175 311443266 338824437 824802870 250059639 839631953 340137380 700802468 321812741 771944044 698725963 862341838 824672334 876241818 469884318 807931184 393285805 394235695 675609026 928743946 134956002 960382292 649136678 796395697 752633366 755910768 209262403 479568391 432263666 491000169 79374934 455854336 553008508 810808600 260879682 972926584 214240651 602796613 218622420 346423815 450522986 589875526 104550773 326747900 184268327 670646019 176838707 806703332 9647076 175715018 385611358 439462218 14136592 322379690 258594252 745659015 424093255 990246836 35861111 488865238 474413487 979345003 573290 600003807 810553704 928435234 461325351 889879363 844521985 878727829 523011833 540287057 359406754 416822501 271642005 556658014 89611930 439433717 183460386 891044517 168992162 263879688 391609569 977395705 9611701 955815579 685157006 900571238 390246442 985728084 891357528 954484147 255067876 470660783 213327617 729555078 436105770 866597993 686482470 732955517 521600409 880711194 51819749 97965526 75877923 730553003 34540701 123970984 101526799 707448299 467987679 798862845 233450687 950662176 551710039 788974124 225338815 846207435 416050319 663611512 52888461 937308830 500850975 688923824 414562835 521910934 511805259 899887186 221428005 383153034 94350322 227314023 407808573 623932582 138109371 368475178 72135836 379040545 311848241 776908996 223385564 599966592 238927066 479693054 342669857 909054152 272584109 998303248 288156780 947333186 264518501 862055559 295309898 815284184 184174634 188831165 276213080 927541798 396850271 765736511 122123823 896162484 619869718 910911307 300630475 832422087 446155894 521961012 199003044 982122185 616466529 631597536 378742461 505635457 117002302 139089908 698901118 993597267 465867373 966994795 365960958 554928990 172087745 219731325 745884666 848368213 537043486 860394614 195837807 733232568 94781373 961225195 376293256 939161776 310068406 398966780 546938558 909827868 117622968 442923214 698510094 751398259 581156705 738629243 865896499 996313601 633509529 972309271 100952149 208297157 134034446 734758626 405256210 494395410 121079923 858749279 557382832 685201022 883151527 995931519 131946149 964068332 112059587 892574106 9997977 408925891 146420326 814910244 704134089 802127383 193839898 701151303 683007022 937413166 161620161 597244304 314255813 967406458 100326249 521907660 615279905 772553679 306245686 448078696 64471673 507116388 231115571 718692133 255451884 633276539 298128920 970285116 562017439 997225467 721194220 982156325 76660480 131376704 153228134 961017983 822643038 948101483 282246613 550885529 199782845 222776219 90778610 913058183 76507745 223172301 81079909 342164751 112406779 730792367 127520195 981676339 803521227 984949816 203980176 257963731 184932498 896921055 434698060 699102765 301655008 694627069 100288128 924393987 240802952 645089176 145225803 598147931 142230361 966113118 932653850 997647058 285033106 951131223 613676628 999922186 623992985 691390792 621138068 982096973 696888915 852710709 332627782 533532797 43889346 556901442 560910941 794775459 43772176 688027373 219766619 695160436 137095064 565416571 201997995 869810651 90351440 96272207 147541060 822704992 229466569 739831664 222574025 317340240 36800130 849454399 431358223 802930567 123162682 893618279 470138718 750196202 423904987 736528817 272724940 604633539 773010486 808688697 741804844 923865570 211091643 995801793 105113657 607934486 598296538 659573141 778556111 893835355 399851388 626350228 800829010 953423012 850376992 941039773 330949453 473738629 337495061 590821789 181867221 638416556 200836674 813760205 167477850 611985742 58620303 977319326 102568960 432680662 12961921 146709715 145872308 902089212 411414690 931785096 254274209 291008858 258882883 512966025 779961782 937405249 125916158 439127526 397084647 836859161 184432493 505937557 300557226 974506784 69294084 789972536 255696335 883946589 408771032 783169540 361708904 608860667 809522495 972577257 534483295 771793645 507234960 565380958 226966683 412680991 699556809 920273443 848184067 907716899 190035569 606792569 369663854 694630177 44974362 169901122 550376213 745420884 310506448 677776658 327771675 885158571 767822420 783460510 367519378 451681799 69141140 614441372 57559253 674187278 501990662 555929239 394805579 523149821 236828430 802992874 42561218 182972301 650484923 945917323 22392200 655755112 574856008 956661460 109671659 815767258 408162499 479209967 204623088 633440786 121790739 138851578 526001160 619314724 574890021 850801530 141895525 916029133 406585970 734897259 437656020 722845731 381002026 797139150 527303085 845078011 64665215 708047836 1574607 125168603 191940067 589894499 29330790 516538299 643620035 893054380 522531987 854634610 47257148 96707756 506756484 994725454 354814606 833709119 627163536 989142820 213029312 954636605 86256743 822433224 508362081 549214956 18580081 251313294 387425147 570076156 26574107 571780138 284079888 880971351 870471019 993121459 367909383 863280466 153631882 742755700 559987126 994142280 21034591 917357713 199519835 293468031 740341103 990668769 424624864 859433430 28394233 687733941 153310366 656326155 677723888 884733406 454881296 733444675 255271325 369033875 131242456 777518053 448740190 561582659 882941149 961591309 6578034 401074429 385459818 937804160 610318185 926475137 648699682 887727488 158886899 283834479 685842657 896279673 121357227 605086526 449398685 610110802 603802976 707535545 452019091 468870724 216277316 414663852 801397474 907561712 637622176 697184192 302672298 687065025 893448844 986509433 446488542 466956605 258678903 851483813 592720944 608083620 466472972 625793884 121760046 446271524 575867468 923656898 314905271 977011953 411903814 542101204 609845040 836870404 806451073 834312268 79247501 524988979 697082975 888444017 598076904 790014539 173284933 741122283 69718452 688849321 334781695 968377308 266405410 344856636 484612167 906349149 113774701 339594379 615787598 842516996 480367225 619007343 476427483 477478815 40368913 845356320 286924081 447507536 268681417 865877964 436203229 944731469 105780142 934536930 207217861 330598890 365812409 850940096 398420615 793543640 233547040 810458734 156123714 940466961 459643253 923155054 153900776 316477311 690548111 848339734 805601677 848772880 314798673 920343102 593871562 848067936 146926775 193260162 53368131 352150151 597077095 881220991 666537803 683597925 166222095 511008811 315036413 352373868 273962890 399518732 108322261 804874175 93824327 576864463 162157379 744428394 795263635 866767812 167870616 984310731 237734704 963437890 268399259 638526820 750906632 772488972 47596201 449944604 439940785 645216883 101129733 741141281 67485670 496009152 377256584 579424932 22296003 956329189 316298330 847209471 203162671 864240117 196009413 903098815 167391066 770801041 90226360 854710896 514928286 721089999 753887627 789434933 508069130 551961644 440579208 873440220 349148459 486527190 551306320 585530259 506755433 824262195 269921117 903785503 54994087 782050081 592025167 847946351 376307777 570241194 15171728 518742629 21914102 341454347 145335872 614150247 716977253 872068288 701961028 754158327 140630647 288908649 110530622 185770732 803657479 953721363 528438176 984372507 991577092 992811816 121032070 794576103 820999 504510222 488825737 914008536 650240993 858675204 619642334 632091149 207542663 455258026 319947884 469795194 302491693 989314875 57050177 117543577 905363057 973585453 146403219 223971437 301555190 961995899 9897538 913252221 404033448 991430526 303406715 371491287 113633771 325024574 28126149 162823328 247507864 632883936 195958367 886810183 332428763 699729910 538251317 967471324 742585434 884961289 67619148 282663230 663298259 725321111 236599513 837496330 35077563 772430101 183847410 975247451 140350869 257502150 249303405 535935961 266619093 602157425 32910315 99657711 776407727 895231025 224215063 470620486 485918685 873655788 348509686 407190361 229073533 903897810 164617448 919579891 794803414 954150076 174912241 478639839 107080187 821265412 710636972 987335148 51796388 94952390 810699891 852643068 136144508 547710876 77686960 647289478 134114618 512442427 670731550 865912700 628906677 945131644 84731414 210962123 504369994 861917410 433215910 945894323 125263548 355565133 183609876 893536576 302147301 452610126 521903047 932204685 671130585 960601677 43893577 945422038 318897098 779349849 42165210 280285526 407224495 497928506 609397141 775532031 20736111 433702497 784680347 867782279 55413872 719520890 645569850 683280396 827699263 938373744 237997289 977780438 500657237 765206703 287355140 379116477 478216846 934466856 156796166 792583372 199850120 202245859 126186415 284247062 340096602 754844926 566807620 764305630 74898866 176293614 203018578 891777297 227804836 625459349 608641184 829830855 136465433 511924883 434214236 864601263 137206521 248568648 340796748 926883681 68566980 237058618 680567383 794891060 363490194 831943000 111811197 224966059 62711184 862895469 272936957 304649503 230606307 469629550 498003457 960536109 535126252 679054035 418676667 499678958 67527181 560711051 74446545 438826631 50038595 259233995 350146790 704600823 199304005 663721557 148267009 825056375 598375261 760871169 460597335 813709306 356565311 764624078 414566122 696847218 406780235 661577349 758652700 856273376 652114697 866763487 234587692 255962594 247906162 415299525 792699542 840869298 348116461 744727302 456463998 850313752 78160597 895773043 266156714 639281785 2103902 828591267 820615133 953830698 906825283 953041808 191034394 843305610 464024819 949567357 254021592 427590907 103566981 659086356 73958235 460011164 449726603 705640975 498279042 955410900 570606503 723858355 660466594 744435057 17423961 511268101 555307419 971672292 179317248 523459559 40848816 367282560 72576233 212392088 272716532 485941345 481291538 770821739 362612147 873963904 305521981 480219653 102558654 447402674 241715350 251386501 121981486 538019189 292409293 670283340 226686903 247414067 44961216 136777790 47273054 593044711 122974974 198794200 419924664 583383814 83157377 301264808 395493521 830134311 71951022 835929241 131779857 959536246 684275974 737391526 511673133 851540461 88731741 948080116 492071257 510818930 81408253 105498269 531259944 965610984 11287760 887570695 155965732 277175962 687465190 702344223 257857158 631299591 841441161 971627295 411272899 525759454 579835117 919790297 617792358 756205756 442944115 575023157 362450669 505008695 117937739 594610425 915968311 998202905 407827709 927832527 110286385 443544377 196142517 894791944 869199406 923218697 168772480 650507577 111136556 370683908 144331043 867646691 387552332 793029869 517729303 723539769 62376195 448208332 416604802 738675676 368322118 462650782 944980010 956859921 410862318 489196608 13674624 819307916 46897963 783223366 378071387 631388185 248218626 308779468 519899892 654996938 123774957 476858649 244445781 837665848 77397442 573310488 387326876 995984015 126525102 951068339 425543834 632144391 184337775 781459329 522850757 622029365 237457935 792777078 394778958 483413935 527055717 581654673 114210657 311925791 427654266 918394980 123314161 966487796 226042831 922527147 420837258 604987812 309592784 901539328 420055193 997946150 308039452 645856699 85571963 98015319 217665675 395198021 528621329 857856698 131795105 851942967 147193677 244310969 286447443 922722771 98570462 565088663 216285179 582269838 749061850 878639060 114061205 301143408 13577167 279125864 387805410 403523603 22935106 452296447 512566280 998893299 510834161 743729077 236377829 751071907 346997294 834280547 128156187 877419871 766942214 903415748 300729103 333268798 592976035 678125550 85282358 527599449 405523660 694423923 745140701 903949070 915276088 951192487 294837597 436996064 258523727 313466121 149794011 451030041 291343465 791657179 479400447 981076112 376757665 481107218 817527140 998533094 168879234 841649735 91928592 288098426 379192461 616459092 106155188 114017398 674977265 793081395 152276555 569661716 200284280 772534163 140017380 364462913 767052417 977373488 97373738 403224398 539397256 780053671 197498851 620234523 421135288 787557042 146274035 396887486 191263104 300864215 50035566 329398432 133269009 720308146 349966690 492029688 877636163 996433303 177622453 289641320 153529529 651856539 687730898 870319170 564960449 720691199 71307527 788502844 157810062 982789947 151313513 450662173 424642499 953564334 15786238 850439958 138764200 908604581 706998717 865064229 386432257 632114159 67288640 250974656 314477994 742146535 269089801 708531142 157922053 187789150 245864386 858035284 339205620 392286811 47047644 341319934 27779391 870738699 713420320 999249190 741809433 862371554 156006373 676680609 247720118 512693834 681190502 851924053 417863645 422814589 896147373 977292748 209136559 764186008 118587763 523177526 2159202 338390777 273036034 508739741 588035294 750651914 95028889 676851565 3994331 147965859 515393543 695919533 117586663 163957189 357771033 587230486 709699768 850362053 546574190 757640085 108862880 141119105 791016904 851053340 589608372 815686763 156910265 981854470 763545706 800717589 541633374 773323372 378998770 394091853 387277459 904373554 123847706 978085663 7922065 281243887 564064463 870060925 179029543 590497607 11908649 415550328 560745033 730985995 319971929 831071565 304452461 562954708 209263967 791839779 476442813 717452797 424289133 534997406 245618680 513776393 509488665 713285127 134122709 673281766 680108704 920791976 135895533 611802236 120773511 224463423 8806526 275647416 111341838 816196726 207455249 766822681 173960417 233766868 636424440 695765324 292280768 416336486 168746790 429614621 625879976 720342751 610437706 757632976 66781192 871627296 415557513 522065186 480410549 561874771 515158564 843778407 117156116 726652659 167357592 556051910 550296536 671199229 684941709 969045746 184989145 459414333 85860261 333903359 218954119 838990791 43445553 841082066 304163285 831244982 160254099 967530181 586444169 910763599 426433335 590564502 666183091 864291148 59945906 984399687 462271344 868393221 21275181 772914613 65992682 429954538 182374487 832604513 65278861 512872974 28146036 111197756 243614350 409509795 610030943 892693246 445015325 897656349 590646681 882038991 257742731 670023953 302293855 984401125 22779573 560408326 281493231 665444486 288822396 579590055 63388862 706424697 398462301 408413265 448483462 528374799 32133726 198991164 56050262 345963134 307330921 455238653 630966008 662880628 394648396 413696409 302501666 779399628 335288790 544326060 50796344 578213852 201064907 907691141 459300950 683093851 228278591 534590117 109538420 274161884 174372008 454536827 866284642 874053272 139255979 311404773 131435661 912451475 528282949 755255902 86174497 719817866 136856285 352333603 186558271 281838152 514628757 736130133 188135193 648649905 56432680 495944280 639474566 656599616 137043131 622767651 515744064 648147338 233540517 402958532 519152029 737018691 84964280 587429637 788870715 905493267 73273422 547246001 31455035 308808975 46716023 899454405 73786332 684593790 449490497 958843437 272257352 896938500 281826521 828451737 454227122 804318524 249128161 437927959 778913973 922159609 749269040 765027743 388026605 892820612 180148619 632547418 253146791 563099529 276883010 779034416 19326223 904254990 517124891 748177804 726020789 997600305 182741538 231504560 345228601 920232405 917808359 971421057 652261809 795579140 130810232 697297956 122729807 747988265 450163557 663840789 754494966 783769066 170948721 498498668 596056928 947112086 188584822 714253435 65575966 654288264 573430246 589270773 146156474 822514843 281179164 674018391 219000190 387573033 565507746 587705968 524903435 880066769 525187929 577568706 350377489 702914977 199068635 975235930 678272832 822398123 505026338 783871164 136967881 411629530 327773589 470328425 587588671 610391635 58406147 97071013 255019952 415511834 173183531 832704836 141640704 613604952 778874845 969955978 327356754 616364973 92128848 364507998 489115313 674712575 80866628 107804185 39978581 588724523 144095464 936480701 411388259 491143232 303692988 837884420 72541927 943309432 408538608 566111931 372071276 739073875 533597036 973849501 530940730 671146366 37942447 137962306 723941312 830718191 5087770 334497345 223277378 915209706 715272746 925577270 222515245 434061576 785220026 833050596 462479838 889127660 79952670 626142088 26689397 786848515 630012547 876719773 491666165 575975435 190054902 295999523 496923689 608105603 284449830 526650797 339522799 990226677 697328902 963918735 3413457 350099894 34338318 67029524 94430006 428431429 115628217 297036663 60037045 990201426 162735868 667738077 251062637 553361282 661052712 944283116 523041502 829356638 56622827 900014263 168592662 428458334 55827593 83936023 785289585 974166600 186379110 392353184 8767043 324338167 452865616 577736913 24256511 627771049 297642117 863858836 75896997 281061927 240156271 706892426 326019526 331552438 377165654 406897919 71532424 787167787 273576570 344329840 745861393 958371369 274102054 689342283 387196191 465621966 349370486 451115855 198622789 993145788 436996134 959814615 383341280 870971990 149664396 908218322 583670203 786833802 434717938 817548382 148350478 570468948 124577483 560127527 150365943 858760762 382597603 756665075 335479219 387469215 131064640 257474319 161216449 780567549 536645110 657264783 27639706 105191161 486669223 803332878 889302881 978560750 48246423 229580146 231714343 798346879 679549959 925293627 698645127 842744368 43562714 349138210 19152019 198299237 949099809 959499167 15368060 762098281 367970785 756630821 434510889 795195007 318093891 457869819 152769448 894087110 76745508 901227167 296399732 673188690 506944084 575662174 44476929 956377004 137187930 880396374 421000061 933014874 562993902 971271446 217890957 639774661 676801416 994967971 296552749 371144279 238029387 363655656 18880635 106796547 168926408 747892295 599642813 876812868 569479782 752303836 90075986 492520377 56711758 456269644 45765262 918815724 184735081 825855831 495064552 812050861 310382752 555351682 227972368 984590178 867240028 905863648 95831842 977262678 329842996 356924973 270333692 420212960 32676784 447227444 829366131 916001665 61413539 274201354 80089806 180572865 160399584 578641841 166805629 519501748 75979944 563560745 2517931 329882006 75040891 787206969 102779699 632756827 222066306 632136154 55710423 272684035 1286806 853090438 398618855 480309285 205157336 248891378 29632820 454207813 411211209 535875831 171969311 391058898 707158310 796005850 519107863 950153232 746876034 950827409 165218582 576858641 350677739 768682220 179795796 752040436 522259839 879081485 304772225 461812534 271657311 389492532 307368775 755169849 614848880 625617683 618207273 947219113 320990005 554577891 498822366 644244019 94513155 408993665 485577911 889175911 81382215 183648189 371268272 632878084 425280066 872614821 112244871 477207365 10461311 812631425 501998940 905629590 201973865 297210453 235677332 974267647 663530340 782082322 6760785 155590416 74833563 958994865 697152185 944460630 25014744 149453289 118092037 557707783 595531953 774672454 338244009 429442967 88531013 178528531 735754779 993403668 198972093 554587448 697828441 909681917 357285174 997213940 317341666 419201912 605626396 980836935 212917835 683365853 202261105 333455977 822880073 879263005 898429612 959293383 136761468 389574583 203858148 211001810 301401416 459155393 171887269 337372629 442608920 926910465 119230220 416905405 52887646 331559166 433539885 505540116 534172802 561828624 485994884 971820095 15298517 278988286 101035183 681095578 746411529 962183378 529496010 552313696 183247328 639368363 97935766 648102637 309797173 415506908 800846086 955767455 326632606 641368934 751792976 910803079 143398353 257089199 638879896 954464549 637716905 846922186 465211489 740534090 206720270 401415272 7311996 808591193 717512503 803745059 76135054 354257136 648540883 978879757 320637828 502606933 436622523 894727590 172939591 739634625 77726214 992075381 1641567 715049524 369606197 740011502 306860131 613183612 164676129 766893271 397270925 974192920 141699135 464714896 282210180 847243639 441613322 619718678 561687564 987643140 127929818 603604444 327303387 741214188 760507843 817978024 427002025 632293697 517039422 854721451 225036624 936305042 126989466 261306934 918989670 938262160 64692878 571731860 176536947 191897611 35832174 393439794 235217395 594815367 505429847 619722433 1282351 336331536 48550935 107444339 834968560 956101133 67979663 830576048 516548572 885141299 493399677 842017001 252063830 739748822 483230331 593157867 201455180 587744530 40736848 253446032 336096926 448091223 261653067 999319306 171837158 470258343 59180811 86497879 732197934 742572262 1217138 457999779 798139376 891801841 181531223 880275959 571306305 890177251 262877140 586865593 120816093 655002787 68442974 614098996 398868653 826458114 199636401 300015585 412329217 912926512 302815382 311270520 126292543 527966684 645669113 652776592 183015286 566572371 652834468 765460627 419962998 567696541 538993689 796240177 637386036 981433120 64353537 159351203 358635116 601167532 520459743 626977781 440579565 792340679 80523194 492544775 89566317 903279363 51226350 902481312 417184869 617172592 272427778 380259784 854693935 949686507 600314 858497574 305781201 654594353 502245497 903069928 146576870 409250159 311522289 642912552 924905143 933362293 654663949 934332254 469620969 673384769 251606872 823063514 33612829 549692416 714413082 813006266 367203464 607986242 127539923 419335337 147271538 992678048 612891964 923823625 212834377 795248428 167234655 382889875 660029859 985294426 406187986 949771690 122381096 453975827 611446524 631457554 113639600 615456679 71190392 651275260 515348107 752940378 538052905 965497738 406357633 639517150 381779738 582043254 373329096 731759864 19743774 472818005 218840248 221224197 403241135 749136608 391718632 485201527 8701123 46315128 99429701 775767442 122592179 598861755 685066607 849127785 187789261 875641307 624493957 801561888 124983198 495534962 171849317 217542753 594037386 606422300 289529117 485815167 596405721 760726727 541011982 995047560 413660845 514935573 767329297 854701332 224155037 281753278 239397408 993559596 263261050 680427071 946361351 977378238 425888049 555619530 108657959 958853691 80110153 613421684 460514400 795790731 109700684 415392594 154827059 404120777 116084098 154187504 473086293 547650750 207928317 633854925 513649294 703324407 755903681 944494225 242974302 443731166 160917401 746925663 204781854 570475191 220560033 704286990 82502746 248583967 332208587 643623342 402263902 888457628 236694903 637496680 137756788 393868340 597998886 818453764 309708111 824319031 242536402 250619006 447161024 857836079 354919847 514068669 324000975 776632805 245168983 285533698 20396390 793373966 126336989 187048620 404480357 423613847 411781300 919091833 173392443 949080325 347456914 644703712 247392221 919271147 89604427 757037349 634393178 668533303 154604866 391038801 88882887 387759177 196505747 455792667 155150433 560615445 303796142 605355122 410760522 531493196 606903780 626172181 541412768 605903880 242162084 918053031 380479382 483372083 786117497 982331091 434589969 997142610 492855318 733975672 173081984 900144571 311750548 844249859 676823899 827121827 456669202 900823452 262521089 577471598 573547423 607753208 440289486 745626727 535254572 692159006 356756446 459552064 241037862 820606195 387521072 544274904 593316092 687666405 266245602 636914535 253405206 385637738 183120821 241231042 163995998 699123253 298311666 979437998 81219883 949445591 620562954 786808261 515395591 529298101 2360495 896711396 385167708 434036313 93708304 699639537 742718926 822002538 298807195 912861760 782360152 868956313 428322420 567409169 463288672 463294007 145973580 191455117 756701206 932798716 67576309 331018119 106026007 675842575 101947751 569435456 147895405 277087613 475451183 854567713 463795916 805116904 970147707 972188246 161231583 498344846 19333933 494635500 62476961 203002426 837821496 861537453 332652617 609968865 121786395 435209600 404664367 459187030 504096414 515618548 216599638 231788896 46782456 783364595 281502504 879135945 689160034 789792172 280394503 546839689 254426602 603317999 97319470 922583941 171495374 356117729 138118069 190407214 845182165 930527414 700277880 903344748 621085896 952099851 190617870 804881663 424567202 682746252 11322556 296718921 276361074 924936050 543058381 800720965 558122882 667268991 687419652 957308932 301659597 418864528 358070002 805625796 236595221 903090545 590129183 925124988 22696926 266048283 324866924 388192548 93347993 165205381 533453398 895537911 735434519 957806629 507430795 766446852 22939229 788481250 25307196 550881259 453960914 464806087 771056210 799647072 892251998 903623788 691313854 719639901 185096317 667382906 230097194 239123917 154048380 159002800 33520460 250154472 132246712 998948125 132751305 694795883 309741227 494188097 173710815 987980162 256389407 340195954 248715944 368451809 542903444 855629513 416233307 479417262 90832801 424866625 902626324 907797725 106739600 611181128 348293253 632817738 8049255 945670690 138439045 818962778 226181478 297433742 433071060 616083988 334036840 710750266 861308430 983878505 338039779 373308372 500237283 917642437 638427600 875450115 88569230 911010900 118825563 303887096 767576605 871555899 51078322 841089406 541703539 733182527 493209721 674257332 73695583 615757968 368620722 825094091 187891433 626829945 116604547 645641449 762610836 897953719 206024200 960297184 203872244 892575073 557092463 628641649 304050701 931187344 411777031 837347278 408349802 484627728 491677655 754735080 374324511 728366744 145875462 413743393 206581009 479222241 772827634 895842906 142738164 961110453 128328561 805814312 758976577 827275137 213020268 303380637 313444186 585569323 959127720 989640149 384216871 605567015 134150402 460984122 511382975 883950598 261129000 630863777 355585064 424759203 514549108 923736589 56561253 97106782 143246070 274400742 158205525 768770805 565329120 583787847 714981337 791802425 691932927 754440028 95244081 731984424 683309474 834823525 547168368 856657692 706808785 933630703 173471499 800540279 888256903 987945168 328276482 959368840 210862855 518393220 651374304 866246696 306587805 986920321 29114989 939004565 496679744 925445726 442935236 877238797 505749950 977236796 145413399 499642181 509929325 851329856 184126225 412583118 605835809 633506968 405928649 977454207 789644539 812065212 591901934 657279056 19543134 525404888 866509356 964637508 721479255 761141244 19467985 674617363 376145338 387393610 92087231 539691438 227521574 237027236 243961523 414594334 28229267 282899082 175454969 437092643 438182746 662098411 10109904 621611621 409629700 621020666 55092641 649146109 319930780 663091187 401455857 710799136 71891937 369200858 327966280 657898287 193424659 934484814 184613856 898257788 155805150 875437245 253370505 924052538 920862535 966532696 242739518 287023129 433446660 755057703 447189265 895898940 444541413 452428207 210585517 710499640 450893504 869769546 545551716 781000014 99504408 138302511 155420314 529384578 456367960 877735213 287473344 310404445 327997467 484678081 213884392 264660251 42788994 675391140 255786171 812697799 163831500 892700095 276368160 760872962 89354368 325507471 22641535 619191269 153907204 492872021 267749400 966586101 399433784 702887712 259281889 858829573 555803171 733078228 313067128 541544933 114100170 913336198 206876556 530619006 395881922 900332165 53444268 357063546 7549858 87944988 201751445 969082269 568977869 700306163 514712720 984291953 339119351 913545158 185640413 463371181 134386945 361133864 924433310 932152301 389091043 618585056 210533902 278033103 618843651 838734478 126557734 993008952 622462508 761548697 241693468 797108870 84301784 949097937 388517710 635991072 28692876 45079331 311939465 407008399 303777789 433511391 400884731 719073848 215990765 675818972 15436338 143437695 587323464 870042573 559055648 828692555 540303306 785601812 264374066 613316212 246674815 276286853 167304686 927343884 6025565 298876668 141234482 724342808 392723175 401849265 497907871 929624250 571764588 702172432 164617211 627699425 149184198 322880028 177388775 760532974 226784625 322952258 344705448 471943922 377630645 995711750 141965730 754152252 814289497 876234615 51838083 987843729 245628797 735920469 212700434 308950826 461085497 785704590 273611361 697449142 482022849 959468505 455025390 812726476 57705119 649561168 505949942 608192432 162477181 254255435 36094808 705186943 597722444 655891367 72655732 302950191 48130632 194076813 298943835 616251378 65225648 132486441 167108232 182517233 84162537 803678712 108595461 504318812 312449752 800122547 42239 810669976 100596612 484272796 665699221 890496166 921665076 980398628 547682237 624680365 674219299 706696938 4088802 504778413 382267731 428010302 29959243 969426085 460817149 781023673 345839966 937312461 342039863 389964995 460354157 972994353 103858083 112981680 61271804 168791982 758759094 856048868 336651051 664966542 419397852 979399998 267613268 666992059 369790298 406518382 653619795 756946236 655316344 816957625 630774780 995308253 804068981 849771638 598309754 884184784 563342494 826806993 518500633 685212271 148374466 216492792 30611229 701886258 863753969 923220888 256188233 819935984 575996871 580899664 214932796 674914621 257930744 867115589 425129139 972706327 366857833 918693980 638195749 948684107 718141811 725451520 514068904 672412082 28020208 924447323 451592238 867861799 595758350 768359145 133748523 301922730 30525298 851762424 312037321 983435594 224341798 949941005 145250477 915234013 336246255 476838325 401451360 608193912 105865185 724242428 748322020 973994736 273103366 756806912 337235796 968829800 636622983 677906086 491969947 787443691 65915493 300569981 714902359 816657538 465133999 633905719 862147091 954194138 34944856 441738071 205406628 798871810 268906113 476843161 396605567 421649775 782004971 786691877 3436822 797832466 727946498 799666639 78300438 346153178 309756329 528162336 237607326 304948195 452827152 517865772 705858936 898879114 808173837 973089178 133751350 702178717 298015668 960106843 531347047 951980914 391745692 427080585 121456910 175776832 844872979 915479349 407753580 481751824 162809939 716634490 565921241 606486721 18417775 917253998 30625237 729226875 582892488 705413652 653014013 708068436 155561085 275154553 122200091 230160775 26749001 119413587 96724729 497183283 325085082 334416620 10117267 246753289 64776773 949829993 19695551 490538362 889744663 952215122 774660958 857186831 413271987 803053134 50350083 303091509 818609386 868715997 466489572 532445803 318339817 709054018 526529260 660582703 627036272 957634166 67904164 832577485 46207099 923703067 782464644 984511146 675507204 709698166 702946864 755130906 385385531 671622095 242202370 662073170 210154658 341764193 875110125 994359290 133103242 885016597 50630990 186554384 75053980 382068405 6879334 774434010 173944052 770617719 219462711 932326025 173642467 381781318 28808100 84513753 358381925 712521413 60879094 69510839 551186508 683456411 223131202 479295556 29441743 162381835 419350517 705752023 180164544 805980638 116966549 550188278 855831676 964233103 45916679 380661661 306008019 763685766 122230311 241258361 52145774 892797449 231297848 410365128 265585959 323995780 482465659 519623286 617705804 936282092 35295692 391844455 636217612 655389759 132003598 718348014 419792518 607610533 138997484 864985175 527019218 902712454 123991414 882123358 33618800 986108162 13906380 465462959 38022025 512448960 355162588 695783480 687717349 742179596 557318990 884121938 208334761 691672583 74465844 349110430 35035164 630339261 227437245 851062200 241983519 378454255 232520835 441199028 603063544 700910109 758506271 775931731 930702005 937432898 522065633 591093072 825593893 916343809 685574652 707259535 4341845 711528178 264706070 917217088 80910460 967858256 119668738 539597280 436881070 564503181 879693543 974925027 773962708 963874301 88015599 136785551 6522344 45946397 438989551 440022740 161377074 415785324 897281118 911886444 261512122 826267446 263077489 664646519 578103489 629637587 32198576 253292737 703992176 984199080 367017320 787670968 159689038 622196355 223333961 667926934 426333239 642361932 621348138 773073508 7304212 452077326 125878474 639338724 401376079 846916238 279137976 818220892 622497906 790042194 86142981 764177939 366074362 867541332 739721901 818001872 374546444 707942559 5913490 483993063 93296859 639651829 273864597 275968108 135467002 444045391 220474046 864100429 564882842 687344872 115638907 837230027 840184831 921227903 166630375 709221285 205565279 717156087 509748047 562578750 114009781 137958823 288092090 479184295 119876599 149851960 784495638 843473155 342857417 659431331 194537806 481142430 814908952 955044031 164278388 468852429 272511988 978323513 51508071 54278310 9666734 901277212 163849690 428482031 389215100 951142209 315197246 464662852 110891664 224897190 159108664 213306236 81320391 227730726 666709592 851370048 303754796 450465299 268125150 349594671 711057473 862199468 72224933 822486317 476285465 663402160 387158691 920905904 146347116 506781033 767547326 918402419 412030909 948662537 582786467 778261060 387179686 859611586 616759083 679979283 420183100 454462667 190358318 863163753 345768045 842869704 170877872 218942352 212802785 522104763 456353603 977044425 198148278 862153887 36841632 778501295 240053563 709218051 423033160 948745964 594553819 673729035 101246969 279232414 299895431 930191948 665668842 975672016 62786976 386249536 368635856 744572349 926013346 971204176 19416465 899435968 4197730 428044332 743727653 852882875 18731736 953204320 149476000 195474023 39122699 736212807 413352211 781950130 142680680 700668262 23943298 146076612 327824167 567166662 582906299 990030528 602552708 808206197 12242092 239997989 347698197 856905467 545846353 874334326 730704854 774956350 739542479 924836206 84499296 89072745 389281303 583230621 253958108 837809871 205378982 844948418 574498569 620392422 420009140 473810480 45720874 550733698 470841124 987295348 265585334 725113716 385400498 884175287 273903316 461849446 391860948 562963308 813687746 814735172 72470598 459335219 515972533 749703415 233635219 289022390 675102943 861840115 463855013 920046945 446190545 723781593 273123770 533785303 214115674 581819974 26342333 89609254 25649666 933395463 546781659 812475513 404040231 879042177 155887148 836427569 350198850 585215053 123940059 520288594 413636863 791113925 121891859 206643177 3966010 903455061 332387735 895785204 615880999 896824195 298114484 653713806 28100031 214210513 497872179 592446527 299491362 400305760 662908362 863155410 534005959 576951429 65070080 823878888 515021369 648739876 121536119 389498634 371695372 616536395 303902860 877308113 486072646 663533506 66638887 869593572 32403902 209515013 385767682 684728189 523751180 751222692 284043144 893807615 493426958 637704899 815876898 827178723 80599665 354348221 131735445 250775654 28224258 923164037 329933511 468931692 392117611 979496229 59818130 296068704 209667340 337866649 391999825 815301113 679205206 790559270 361045133 482245324 260319785 415343788 20734695 612686057 314076205 493323732 197680416 229889919 116949214 722275048 99677958 317866670 384019605 812880719 146863857 956468397 100553986 835733560 183146807 369182625 394490696 895664805 526850190 733844284 383333055 971813376 400860861 659843669 131352764 637906473 122483885 802979569 422835528 764533743 152683077 710925041 428335128 489765692 547135399 884396835 435702796 442770961 543066276 893401377 225072570 517731883 547901820 681404315 603444067 887509168 135322076 146396032 42839383 235011288 529289812 979300229 337438209 476276898 864343004 878418042 869621779 989715829 189221476 876984724 389688198 660941785 247692114 866886181 2697284 873233761 33731514 178983409 278736153 977872204 130224805 278047959 192550039 819241511 643100145 749133076 331960351 394347047 344951787 848058366 190252364 987260991 150648631 304909132 691920692 837440850 543583812 751269976 40291451 847536901 791516607 965579830 493853028 844009579 50884619 326416148 379117453 517479179 404781673 533534270 467007117 779548450 83406787 463150758 439970104 711651250 211711845 646520655 111889171 926425524 481199810 588668290 339559154 473529291 75123329 107289939 589149422 957746216 261793253 580690093 447969663 834806930 86494933 611321491 419687600 955364684 662804049 954853744 54487257 429178411 185585757 549479853 8837467 826362422 152859167 261155952 206480022 712351999 72472132 278408298 127724561 882711643 205244821 448978101 415308124 695752931 508738613 882259333 628110455 661790243 29897992 595067734 613060139 910843505 318266015 956390037 750377983 905983464 413522121 814231437 687878287 764716199 663817345 953803152 521528569 655732468 380763628 721437990 736172830 982563754 64935262 358628301 23018147 854023710 58169498 697792158 103573349 782394288 713461997 796079804 485469562 737838383 68878426 926577414 340329688 858573285 605158761 988903624 36962153 400002279 302308371 989839390 717480883 782648612 25448615 33139360 881222594 972639093 766287099 839936072 371871885 458687732 93656911 371546741 731017372 865176086 428436521 485611279 6870999 187044074 143170448 585926903 397087980 463626866 85843884 144636288 546711231 875302009 148275720 849508353 128345949 187141588 42498540 767899861 330267663 538320370 610606011 825452977 141195438 303112157 163388193 929941409 145019214 435937873 297795382 610789125 358738568 495439330 540811142 768408751 23590447 440679784 857057273 966077930 280369393 929986976 48917629 203483753 794664050 811413690 406827471 478490716 452009555 884700400 150260342 785121272 232073063 320145686 406156494 853339544 51347213 846312356 329064372 766195810 519029928 798953361 819006685 897276686 427650754 965760118 516296134 745815458 9087057 261236504 235024851 532667105 684038085 850153409 550531075 593754666 257037409 799854634 200469570 768869043 159422568 459982306 107117100 929285622 115568010 899628952 447111922 852426548 180013438 817012250 336885574 766616839 527932702 558274883 374194200 563543555 330508456 493405392 136012489 288754535 148131767 677794597 153713242 761305758 535461118 822341225 21456481 978893506 275943651 979072836 591178227 980293120 87992379 492476115 729560612 734300949 924437041 974497719 520802575 580190235 202735049 629455716 764129529 801531108 387887485 878487203 337636243 461937233 314298153 847791887 719748089 992944890 723625735 900294375 96131815 307601944 274461102 897972721 132967811 184045025 126712970 924688329 573872800 804613504 426357366 504500402 269455059 860529855 172022965 511458619 172098977 716657556 190041067 550746341 3997404 833214176 517941758 540125424 67352040 443955335 290623260 852707224 65103130 640225813 273277615 471336242 467045871 580340038 483703925 670349146 394823840 552112823 376263422 999185799 50350069 986473130 149790826 521339521 454054586 467632220 602005298 878303890 285103424 829082707 342211149 911448545 191458033 533425625 395872845 904747144 28538642 236461113 170476987 933124213 658415635 966434486 277982626 613155322 242333181 463754902 519567116 747603535 638497229 691948236 137189245 281464306 160624467 884645015 742828436 905823835 225538927 326947861 856558531 961204983 753104028 992716371 67484980 71431613 477604493 836215707 300161577 533428596 736790585 892631439 603995149 642155198 631805364 851143441 106472912 792730311 581727222 703835864 342138921 630216023 22286425 36907836 454461686 480421789 202188798 284296288 772302240 868754049 358920368 550962994 448811652 483431115 550343424 789299154 466366967 917068317 88877152 210844490 78582446 977233631 713585948 934758593 530279834 849812985 852931690 976043793 488371282 968383202 393794663 703521901 2989692 242849707 529902486 680104529 479728999 718464430 637006312 728380633 723011632 816789647 431163100 879735115 228403249 938868163 660787639 903196095 480215921 911014780 477912426 483254976 46577569 273289269 203448701 886795129 379351351 696096584 24038884 782950873 498396203 586099663 514782211 721727605 416878481 954822182 202196423 853790532 361477636 778308551 223960429 478228469 116713835 770984713 273395088 743982613 161185552 309946565 55219006 76330123 714585045 950103407 411301543 882055226 83866514 887709690 512496762 746677279 113212182 205520999 573802335 862368914 567802053 700529298 256366097 958364782 605400668 724450917 711489398 827844634 29514826 699638038 301935931 764424131 152114498 447188208 409087152 784550896 879808835 985969788 240556687 775755426 191983357 561353414 667058662 860526451 293206171 293314032 408934809 989272062 161368647 911179327 330051390 644595575 459974708 580589622 23752565 373120845 189830651 506551868 373843535 826860529 147427457 551441875 516674315 545661486 487229629 777631898 221520876 816435041 620535819 945214505 363782584 759530518 131279141 746768122 46415349 413815757 32961422 617950992 239950128 688445082 723249141 898891985 624167906 980485430 909896675 925393153 758492105 959725463 579695722 702032815 457297990 834358611 111475527 823312104 234261659 862804553 252161306 543735738 401817618 658923832 418496303 879181996 39026321 913016986 374347839 806648332 70344662 480292331 518444464 973591042 44558163 884234362 480933913 514965859 474936436 911208291 526791111 670815063 320592920 385083006 439817047 748160594 254417825 659743524 567690711 758291823 382585602 916709237 271466044 770860890 320792266 639331543 458502006 989618871 645935581 646688569 649820030 920199038 279381348 604284346 452621145 770591037 338784057 472593944 102695454 477940538 166392513 633716781 294675848 773580781 50095711 638290749 122980328 452180154 162798724 569283659 76191142 936185449 698038126 738955806 63899533 693703274 256422000 583307163 278190572 755794975 111201850 531147124 742404089 890569352 16427324 456570561 507714776 857596742 141899874 969732366 18614061 102558597 18191516 235939401 789238971 795229586 750621357 980992309 465599356 850870422 187101140 369423082 254313431 833123654 451139823 979267898 811587971 889102419 166788125 298180389 454387598 979446020 829169570 954180033 445077356 548049634 651559913 767040720 284508894 983062699 117208116 363677566 317502478 623260904 531285672 587638502 57535064 638095504 183516012 638782982 879135035 955220623 210023560 641288535 304444153 870940633 509736539 992190420 63338940 623451908 76609545 428158429 290900216 678548204 406855086 527534850 274296937 875323857 596360430 786782185 137999536 196120766 151883761 729246985 573294956 713065264 589442931 953339418 199413767 688600868 69386305 649345687 177306902 823344435 76991725 396046417 306990451 432196362 814784441 909562417 152564195 777430178 561924969 601809474 464127148 512423543 838742714 964062595 665840291 938538955 643323707 759056449 340225549 759259267 779961191 875283786 12440660 237088466 24760608 369916695 445149469 625096567 541748820 804541611 238271616 683242009 638194663 838216544 385034266 790982171 126591023 739722505 308312146 318056828 221508972 857627004 308229693 523598303 392952116 414532035 336280139 559644226 518076658 998171166 106484113 637322905 108024696 761844922 311132620 703436734 76149016 766189499 154663053 723434062 440046753 481758701 486566054 778827249 44926152 341776206 34355472 471329711 321679362 420062817 78409770 653593017 35924710 66216032 185997473 771561872 434238273 730749667 76126262 840708752 232614724 596756257 335347659 688780697 347303206 822799598 761799260 891619537 190306319 431029954 554562230 704507425 160569411 741606527 285899347 391288119 396963046 742358798 460664008 969549976 661646566 746270000 503793313 910902191 868901722 999121152 40499437 337725917 254073457 936999108 675923429 973901589 10353683 678790657 17307199 257747632 682532939 765384042 268012045 874582239 281201248 566553528 210248090 328956625 185868719 225417956 267598124 822702985 36882956 388475130 14062249 621502958 644228550 928120340 192317795 836741034 525256076 789931452 40072657 70803829 700678437 801614455 818229366 873240140 490048348 577055731 269414327 494564254 866885298 940246977 181070180 785094461 545697624 616291648 632398635 870598684 586970334 730434800 563197885 624555243 152733038 717217499 42425867 731511803 426011837 524544588 24757223 281433132 240497496 554498140 33727977 171441437 99275460 132128475 277095360 839832378 114633246 470315952 161125600 725419589 223250194 640168617 336072498 972698502 163240380 939205908 70804581 625911644 175797891 996760614 385176399 963722717 526098250 783145333 489479702 612553639 128266868 636921249 263703192 528369312 749482439 859834014 272876268 544945603 295685726 716944882 80960837 465210710 182359142 855848366 623519632 669004195 459554492 500132075 815442114 977090217 378992697 640050152 366431323 994077780 61907107 452291508 68142173 841523721 838699 221893232 324542040 743749747 800364652 881417514 67863755 445578467 206398625 929124914 25433282 234863893 177433525 641865556 183886561 609458935 590873476 615052599 714401419 966526640 711634115 845838265 854462006 978108353 119799059 348267648 439276420 840522444 172079355 335357124 251161520 628998043 117763300 991293659 775908626 952219722 360220343 628197340 25623760 839325912 729563561 823960695 216766126 977695570 644747001 944779071 51862972 861773991 722030607 950275732 7410116 924659503 846895784 998905783 482408439 711042269 728603852 874157150 264196946 784202245 577058458 905465591 654580794 971837881 43365101 905661301 290487603 446477092 286069570 410811413 195047968 819622363 2804898 67097038 451132727 730060424 521545905 559200060 558485232 561901864 331736321 749237602 400892770 853478044 85139349 975078392 207531927 704821080 220746708 387559991 191553351 216340679 179195475 387629810 17037145 685595054 699549861 958362797 21772267 975307871 151785628 406425805 518087861 876125486 276608324 535818570 676193143 821531577 509108401 955992701 269601258 536215452 409866458 617810623 715124797 896445796 298698679 840383171 545800207 835695831 501719316 867969603 529764078 570727772 44170671 149392803 441594105 968780575 129574259 849184678 619662989 930909171 578018920 646815407 866096899 874052171 448062813 977029100 106624609 498885298 24733145 92029880 20558508 524976890 400429688 974108756 397762175 806920235 59448357 151419513 137011904 339854777 746936254 987874289 528967645 629363701 798820689 900187401 190218009 518187113 508805812 691728458 482023088 830945186 878986059 934120966 232111316 931617168 50607541 922335467 179718626 891044079 298319455 683936034 360901490 992180793 119207964 392884031 343707591 908617625 82106727 773004036 5238231 855003121 603003135 865541112 220013868 232611846 39102942 563769328 420340059 449159147 192526343 651963177 401262412 830038970 349000803 812763270 106417974 470185608 401420213 401910683 26179738 608757175 243704270 595428811 52032508 268297960 36119882 790395333 27544529 453560902 33035981 983209062 932391288 942995807 658571240 957173211 91856992 474454513 328765330 805737155 119909576 414268815 229252263 904934372 352133949 747787071 397454806 452806994 51437376 444760010 246943724 575539073 464648473 510280654 780611389 835307939 95213655 781986447 579778581 995536814 403118914 918910700 236441068 351001380 182663087 578643790 203873018 401044474 108094640 700812431 216790232 751558445 206323867 957350376 231162597 858264184 455789081 456001719 164554640 971561595 91493166 839277059 482208477 635798982 3892030 736310907 117451071 872349725 179955033 982777132 52432134 929998747 643824147 765955572 258978224 991786506 308084823 484592353 262260394 373946947 520675563 799086271 336174567 745144645 130961 754370533 154749648 883505873 118742094 974006323 698800466 730117740 354009204 740345491 683315930 971266915 460319954 824592447 518922547 773978599 367067698 501730428 474785564 704731927 541137727 580583839 112388294 189052874 179825287 497220446 272285916 445879160 456588206 886190811 663914307 960952694 409829928 456102361 330388887 398003385 700357589 951664326 321608074 898882298 367503735 889372015 778835251 808315201 240280429 420878117 96100207 521287376 817752937 877171123 169755287 364182738 298307144 875115917 31158687 634833765 251260069 995231701 587176424 951752339 485541500 758386817 785584143 921025982 376719604 428768243 342154351 460644470 478240439 932961982 113208594 326401769 248472543 359599435 166681409 304412270 172665221 317449630 230866140 733390655 441839361 506058801 571898152 571925482 392886475 443300164 44479410 656405184 246592742 729021839 178875974 197265120 46732567 798256928 258578833 596965752 177865795 436513517 70368953 241689570 146871432 916942334 421034455 775002685 327185338 829054923 514868255 744850275 641844699 995911903 11840523 816698682 308539119 551692809 270287996 390515041 270844128 408646371 286168733 446450613 521920327 662483737 343744819 422662530 777712200 894399655 199581852 416478343 418516517 914987383 558559430 579394806 12020239 939688620 527776986 945168468 56565308 165126353 332159838 720248584 151216706 836825891 679990663 949158077 198969761 634627535 515932728 640264716 351725107 418046222 345862402 851109444 177787104 794392733 194914826 575363869 167973884 275914895 270833310 380757130 934400520 941575769 201758066 662170379 559651143 974103664 216045080 545435072 337424814 353237274 62993522 682715620 76581800 919082295 537388200 854422613 18361331 146329849 693685679 813265712 604802034 861258055 4968395 499298949 173979753 278966942 627899091 710524709 453310818 701651233 49168005 437563832 138205121 677356778 97409456 231725024 427718308 490806679 291177998 959019331 238426880 364736087 666504878 822064079 37904689 152161781 471950725 631568869 107640418 342577660 571308353 952315787 365876384 483263186 126020192 901929949 271257715 771203568 90771046 733284352 774616214 787925451 11653815 41506367 440068641 636283506 231678959 974084638 116541677 595461618 578891196 724820841 296123612 463939126 134219072 948252640 595011986 805095194 100257850 518974228 764212625 803410281 24829959 742308412 802071392 904180211 118380803 515277401 511268703 835231161 444674872 601814968 48624162 662866587 268253409 864378244 294422530 477394644 745410680 768683555 177679223 820943418 177017369 727435622 402278350 628043799 670380500 966553722 540903162 944102977 459242234 928829578 204695162 638982077 215899720 640140771 581149177 989044730 254890742 331685003 317482279 720259382 91981456 741030395 597496367 807021340 90746600 777304219 583551095 789420434 781311951 960378941 454102237 639171313 20232925 807779977 14821497 359574816 200005756 200704758 4112029 668903615 461362260 711295002 516152083 869819995 68811399 526827171 527409464 967142010 45619344 380198905 218710157 404737943 566547955 827970368 692484519 773975294 453873203 581299200 743467235 766689249 26886748 830435423 85820876 692022128 166141063 357262893 305258175 851974451 529219531 889956273 485902338 508763744 345155813 867282885 368589428 691874526 198213717 485006447 310817625 913892912 608050797 872852861 569508330 871291994 575220569 612616865 2935519 537092548 17263226 322604369 564817030 885826417 169628767 211295351 518918012 854547352 391204232 790119508 122453819 333491607 683547607 821444275 354535086 888995492 606957869 703434441 599675878 838365129 342941197 696685110 295818303 659617670 662183138 755240478 34667161 639756716 238236040 894337951 78957914 319735571 202137905 697434541 466614293 612183030 5930438 129386587 143280946 262102576 130484234 597642282 336503759 368247570 5512946 90349591 117378347 667454791 250442087 673453511 34984651 928734605 77576310 814696769 72147880 579276135 543872058 859967979 13087708 835682151 73866924 641080895 7804020 965915085 300865109 384900259 382474254 475322537 509440497 893941122 45025563 489422609 466341200 474381195 133460767 598913874 705037942 852698455 436548118 581638509 420780074 969468666 504000356 727974346 178274915 397176620 713945903 744554938 485999901 748585878 312960368 801785263 119318239 884561337 335175674 571779250 557674830 848714674 587399760 742941033 421231636 904517493 637661287 650532043 473456459 980697502 622464248 677929277 169845385 653150658 271275951 604771800 410422007 985534808 227689407 276142835 156213981 825522011 57641054 312380096 694438129 992160723 71276512 340208862 442775064 681293346 523717265 668472764 171754153 406310096 224579651 759476120 165591327 717625667 203485154 627360045 559101969 724813169 182949036 680986492 92832500 220792552 621095013 798717887 132351779 197587761 366044091 468731641 780789282 803573331 273919430 795427861 499938756 592231499 73142232 893505111 568598559 744882789 529499383 574934154 147716832 827696025 592366549 641710980 558225248 569012051 625967320 742610863 589063961 856213936 152065113 496439691 240275509 652640182 23224163 194027693 68540788 485500797 230870863 938674845 90008640 992312356 904535005 942265303 138098302 378869714 367220675 847842648 898998471 963228478 159241681 324248518 379293525 492753760 260305228 761070391 161842993 854904700 91048610 515988471 13348496 592224371 167571128 367278279 304486035 620608900 550028827 924951996 249857873 962288997 573073531 751685353 593059472 919495497 158924472 299238170 179117343 194581374 43687664 671007179 653297297 799207721 97226944 369997459 162388116 287715698 858578887 890886565 270045308 800873806 428779261 737663706 432645377 696395135 243680655 448713745 471535000 784944702 532378780 627050448 36911325 169096657 57652623 249843530 80417626 684185102 740770180 862278218 520748827 848335039 255385204 576181426 315475780 791642386 78024876 337569433 19604770 739172322 1109399 620453871 498938192 554012805 687588794 960960842 275539526 717314539 364825169 694282450 539657265 971430629 60585183 340509932 266199699 553390614 39232568 622756511 13648192 625284586 886194938 987247137 35037823 127365545 481957814 589200570 128782663 861248161 66690900 980572651 211794898 353428028 331887650 435946349 112494526 230200375 244655460 912350137 145160875 605264682 200410697 684623768 460640880 823051318 387003362 947769939 439624087 603748914 247681397 732659167 875689074 972429508 145151626 742387333 150724881 281417291 535329580 781194090 909612954 931615957 188153407 796710489 54670657 480920717 343914540 637394940 54587687 106698470 773319778 909605713 458307501 487798430 932513321 947866811 22602584 201852939 392226894 743893901 400163169 437883681 669601544 909818126 450315710 603540764 201058690 759784336 303354316 339269503 347451417 899457200 697998789 740170200 233611764 591446065 522195185 918248948 83820670 945248877 131673807 914661208 282804365 336249858 429475757 824463103 300587375 614503403 735475263 988087830 401971373 448938149 46181710 755944258 33105525 398546126 318550329 747662891 252587340 853495309 175309188 672834020 325845129 538937368 557545729 700085791 287360680 360204717 484903547 677314550 884070307 981883358 56452494 433243094 176860913 680981799 64462266 94363548 108419739 480389608 721998341 975213686 221127621 848645166 219427002 226815392 342279563 773891399 23405886 225757353 203444741 851543421 450879246 506581137 501366513 879497231 696225311 927544229 197264873 740094835 325377938 806815363 433402030 772412097 728572118 976026084 488889635 583447038 511288147 722920960 124883558 728793420 149740255 337490101 5024606 767432725 95093127 394873280 624985558 642474551 36907288 276969873 428375408 740987994 49531017 578938927 23769009 617263710 312850714 583820575 54905645 132689041 66761839 552829259 491800698 529172628 215034659 441223730 225279649 481048745 62403576 89774389 97530365 857289600 813958563 871235688 543114634 616467098 401356930 607216906 9328044 895964560 207002076 941390116 339347553 831147199 584246255 629292461 433377887 808727091 60645657 313712762 9856142 53195612 429397706 964788576 587122160 731913385 213146302 487704649 736666599 896735406 679052521 779633321 430605686 898915941 340899191 809059010 456278097 783253070 754265878 824116038 55648328 430683752 604921752 885291011 940966412 960864426 323203702 976428942 29320052 279485049 421562732 668639332 26829743 541274286 276957180 709930381 757307172 771712659 465450187 658876808 173701953 215443516 384679993 389270959 288609656 349565766 168556268 257084312 705617989 816232910 732164526 777753080 87170085 133896073 21649130 685857288 448160339 676677037 530469926 795574607 64316807 815559035 668595793 840525492 254397104 598452709 421942580 816413325 125987286 511903764 156951006 980869068 4543368 23248376 95840813 590985392 10752655 462230228 558437924 569143188 658672333 813248996 367048396 532266356 628168220 848446712 297698969 365860998 6005390 474845802 499203451 945603016 535676278 969660669 374570610 583169841 280583282 580597093 178511593 335843934 147970576 904496475 799540567 824273653 365495866 802943251 678847530 884430361 54939106 908304626 168639237 325566242 43488827 579679017 62717667 543676516 626606936 794105542 167726810 514187863 862285988 933317169 132535210 917155462 129232360 828984554 276847769 718774780 93437493 367933882 223828461 329686475 165554521 900941490 126436894 467788979 23877671 421704867 79168778 409341296 208441125 534741288 425306463 852224050 120285599 296314895 210140973 957296487 273640244 829258493 24124320 810637639 365560267 529855639 161790155 776129147 107894383 825054754 61995495 979985355 503424005 887491828 700892994 853914241 389943292 420874723 23921921 528729730 704683688 867814421 630930550 724609521 163901962 416449363 101992683 620916082 564607731 806640518 260960198 948295983 444710649 517406788 136686427 765774763 354398095 733643166 197115415 972261905 209601476 340003200 723428004 823951502 675267559 917217043 582877011 972248435 66239524 547350263 270410740 317758656 746960846 870761387 634300681 947737306 161818986 957712494 388636621 577410895 920089522 989062729 62428253 324306571 221718571 453153800 591415046 754459883 753116962 794676204 126406848 528528113 275844945 384890993 656099048 736662001 562900439 840458912 107103453 672262414 242686300 255734254 954317976 993949214 115106560 484140762 54665145 313220208 306202510 546675011 355499311 611968653 25230391 340846163 139461520 918890611 117215849 460476405 359311836 393592861 675407264 844892412 160373239 310359879 397062016 645980830 585261245 761381527 65921103 862823413 59538059 516497723 741781370 874256580 169382024 962768937 133813341 671416123 286086327 454326596 266241585 896501074 468107725 948560121 100913861 198706250 556218126 635947153 722801951 890132867 274297533 437320776 701031799 848212631 338247609 493969926 407318814 926653905 345927405 475239262 479954376 785507416 484718695 614665769 560203399 595318071 418199028 637125167 146529087 222358730 431825845 552688754 599128795 816067343 327999668 347487246 69004571 154059333 101755930 112342245 601884286 904725784 543326061 826485932 44418757 158486414 259036569 951411869 251643560 456820056 152775705 504990514 35244689 533123994 289850081 955747299 333425996 558387461 385917348 415420955 7555676 789270391 245729911 816414950 210586121 343873677 327979035 740289018 731592308 814783792 470714280 763605229 54732171 813320956 59360701 64241669 601216494 852298685 186308871 505967191 25415489 839524991 33336429 641995076 278900803 295321474 6056118 710071954 290429436 875512342 53823065 895547890 81768282 597631755 330446410 726678660 70039070 90640179 373433678 657273877 360586373 469046367 141290662 420970207 262884598 801092614 18501694 865440433 176989478 748025597 544783518 723766628 252829875 433842063 951374481 952132726 577942375 814037626 728903404 766744067 655914222 691429599 122467478 326356241 70618242 185655463 304253734 331160927 214889382 852662459 630674627 652693352 794445491 977222031 53799641 259684107 201856343 728813489 436744458 955911436 261482332 957213736 166846753 907079026 14791257 657292766 146077657 453100295 192446809 589579882 258011424 901522280 312708384 445555582 392814528 621241841 597703262 818552449 372852086 681022301 252183674 699961980 80471960 691429436 328164279 732209294 119396071 659802305 382914576 725933202 465978254 804788491 877061156 880767242 729783702 765016343 173848631 923068263 518983228 887593533 396694074 640706728 117474114 845790106 494804087 962521534 35605391 375075502 741285322 970957390 136891580 668578734 190519862 409901623 704276283 802344623 117536094 675200450 67597879 683754516 617729745 645336408 347183241 750990362 691873508 981605005 305357026 365770196 206496480 647903319 194374038 770633730 406268508 419571515 339064276 705809495 54028061 626018181 84072436 519432137 139940403 628585181 222954303 868607122 96935299 879488201 122462590 622181254 13550953 327285332 317759496 540051941 96638031 663402916 379229650 964939530 244163533 265311108 791162243 923564396 549317403 663118089 800955548 947768289 262546756 837357289 27054916 71557970 713026240 983794160 193623335 409517749 312991088 455263103 651682023 949520467 271357865 636790169 183686132 902951430 270748805 812090820 486916966 613111511 281625592 808821468 23801658 260865530 354339493 959369526 47967504 862561669 790072398 885165316 604439113 680137992 88134637 920629568 80181468 221230871 22791870 713557159 532264780 582684931 331539474 902218672 101230361 765960746 798171190 864790697 51494320 969990651 889385080 986644600 331237213 560031043 178923033 299184581 431341342 828670057 274030388 764309560 36678549 980113578 85051406 662604126 187095413 323974554 170778790 438703827 454034736 668665511 303537573 841555161 161026030 516022027 298607785 912892544 444421701 668034003 288876119 403835625 917910134 995548559 320596720 858786835 127661942 192620632 386964761 391264936 374462986 847771181 170404772 437732685 444006361 805808437 185567111 638549998 415960400 885555275 131261827 880191446 623517866 725960287 431069372 981927342 271806982 529244564 117113316 791006684 109990639 214765916 175410267 195198762 194524900 524305310 837245770 888893650 208830803 827778620 737753852 944690848 506188501 647979828 133929547 591396066 266071968 471958449 523235740 924014693 371810412 951631566 857266548 975578686 121713878 394937284 8203780 549762413 754318511 969230829 93723025 527080972 114541645 911516519 290090502 293570208 904226003 947574413 11763400 318295276 4123694 143158808 524877394 698070881 14663559 585405528 258197246 965235934 143448133 663115664 494618711 526713225 93652869 593466933 104409105 597244816 356789970 740499904 387843726 887758801 63826046 174253179 458453272 633472314 622897314 722201932 386372585 776432181 310748734 620434684 473235182 721979311 96509522 946728169 245666046 642181084 137909671 327505842 489458903 585276049 263811672 378237204 591439095 782370288 690408543 904654251 244942572 278310693 7206809 478980841 869089247 976448628 797307268 844583375 339093642 879565223 281420974 666653963 137655989 210205866 232715945 762155405 553211262 564099155 364851333 714631435 253603815 281991450 401196597 492061113 743761747 889715691 455820714 532274746 137242213 250711497 18726570 94442862 171287982 301810442 529009375 697912803 964239212 986167561 79772275 289811973 395622136 804841340 113908120 576802986 385865782 415532847 747463160 873469124 875618765 913440807 457713282 672318711 130586159 144471088 77630167 309382922 415066258 521113413 133034577 356379463 280025599 620122412 122642693 737305318 126262392 915756719 751285151 751373591 308744346 499573845 154466595 633020098 145382562 391201614 78617295 483931706 578007710 594084037 42696649 425390014 72136257 444209159 97835029 926721154 271117361 274706874 860514832 945267909 38262427 463229244 548725561 612722338 845445837 909191255 170458354 873437921 409913510 833690858 178954268 547245108 230600188 420563377 172574210 722203478 632942566 857722416 310852870 576556598 351968116 819844438 482835929 999983997 426726565 997890705 631195475 963064282 316861486 828418947 676663764 789512278 312611426 892712416 21028578 804799324 18713677 672709304 48550166 729096868 667305382 990971618 623026151 808337151 683912054 960675689 665976538 876844851 513319974 807957863 381650593 578200360 57170846 867307945 292581084 690135351 279535025 850490832 41218593 799507052 106583711 838399995 255358760 305337817 300630390 314180596 686805374 877071767 456288740 877560487 740628201 749043591 493486026 957066204 129709805 409901432 145245466 351624824 882979862 985798286 43006544 454283909 52837644 561590532 114096952 130504102 72716031 749190216 951998010 988508191 83552137 940819093 864477313 970626467 535497352 804566131 298940174 343054755 305574394 897445222 616793195 759562465 301756602 813509189 117194343 403791384 360511032 531146131 341970664 664411790 115750623 287265560 811984831 852908221 329191725 999668945 191498981 634919844 128848559 655218700 637600244 944346999 490940970 692886100 82134535 551979786 134015953 748675333 281891463 766856588 510218783 578009353 286982053 678069744 546135197 855237573 247407226 296186297 168620253 712193961 254877339 943559521 46683675 65582636 435035715 990351067 52870040 935252699 459299267 685505147 328819768 519882395 820199979 887859988 878475641 980929611 352908452 876372387 868746797 895315355 74539957 869016211 211585608 520995727 561883931 627895674 252631772 591932604 48121941 412636123 306884528 904299346 419644588 429627312 20501583 232640628 70318757 734558372 169888902 386071220 276106680 478683216 232190951 368894621 231334491 635734496 90216690 732815417 385681448 971035356 608648455 816201709 147870630 482979299 228232683 949749917 60334845 203620968 443143144 791595023 403663823 444687737 16692272 361019572 820735767 967817599 3100391 414712428 434556103 892197874 346992034 481305645 625356763 632236047 437664916 648759560 516168588 548477932 34249477 549890336 18064360 628205738 424464851 983677905 331546199 707556131 142026403 936046631 133060206 877593114 677074169 981716903 99953374 673572105 196566514 965560346 201949646 203036398 495171015 782258878 138749458 740876390 769978094 981045824 428256593 975900745 792493666 816441027 754250757 943206229 436088984 450105818 239814539 998651951 35054327 973517349 544354820 710331268 220846095 372106766 427090408 852166264 97714494 657572164 546909301 598559959 590462552 774214283 211996624 987614514 340597512 898984471 684306743 728777471 533555506 962085278 155898870 620856595 148421426 633131268 481988381 724272789 746730784 867416000 143401298 732238261 161726869 455624779 44927026 526761310 375056184 596450368 690872169 960934014 230718673 663296925 111579378 121857880 750467231 850886060 447834736 628361397 651693532 767727202 71565186 872018533 149144246 548642004 73927946 691603936 157275410 362413542 475210050 953288919 694381643 843602064 304351558 994609562 800594203 941568327 335352936 649031018 694047360 851084368 468781350 902495616 17520696 977535373 209423127 823065839 447640784 713823312 792715774 812164768 185824209 794659485 58488643 149846613 56628197 68872388 296361859 783713475 290328180 683462649 245626608 332334319 189615247 766424550 289090615 482294532 296960557 958776660 549475567 591904617 387687911 680736466 297313013 897241020 422467198 532551234 490665760 719759290 172523184 798987211 17026685 56880768 540081320 613136786 16904106 179723343 294983641 631358640 599195195 832379116 500523145 781416082 779019323 916750715 562317882 778182863 329861134 526962282 692621511 984964869 719971420 788275117 8769362 961359919 38536443 424971755 393292102 599721288 945502432 956405754 338598308 812745749 141297893 470103494 109097807 810513480 229389436 539029054 38070686 688633351 113860994 161515734 68123905 912022528 114325152 245675969 303823049 620333874 620767818 944199482 835087781 985765342 134279522 187791876 183866824 313454312 264773506 340410076 211986512 493850047 486876906 555679105 632310606 992245387 813752071 822957824 494830495 951398912 419918502 451403957 137262272 578674546 656557683 989951707 406128800 551203781 46025213 254615399 270597140 520067172 197344582 778180117 93801074 505542218 208952963 631304693 524734048 690773623 936974208 991137280 21754477 346138611 143606541 259980279 519816998 893781813 128132980 826595222 265514439 769493904 800658040 867296262 361168957 542965980 129649315 555131755 483615313 974401545 517137600 897088864 199849913 210070333 827758916 946431908 416638166 457557050 63320306 477430346 208507428 788499972 16822805 629258592 303647795 742892798 626812285 971734914 621864642 879752755 54379266 824414779 249074481 522698392 538224708 595712694 28232818 128143439 253071663 357088151 514164383 750623137 46514643 806340636 76834607 415914114 95840792 982279732 577377001 959407283 130084540 436718080 400610441 683153045 440121026 466020977 351249664 423973203 574935362 690454954 354741394 513926325 121316807 257235923 477774753 945036177 73206381 692157028 113698971 389187271 119794126 217414836 703166073 945860839 91405276 748257589 61502345 684762162 137750606 710307898 228273713 955593580 388858944 452909897 134295759 674073372 662013635 900268731 313811741 535592281 127751400 168521879 539801433 914054363 591353932 766408008 176526061 451548268 57684756 872836871 9723036 756830001 618482274 755665305 181729773 549749028 733121340 975537831 741130227 976787849 556771149 978655217 467265010 815934462 139867503 895982170 404608679 886729036 226647297 991126773 57481719 485669830 902701815 983389417 785443541 805731857 676239437 797145637 493429459 953747760 238868011 716168551 619505607 950270343 41161859 546284879 157895119 594407258 323651430 371715862 273500999 419864073 361776225 823960284 306588026 556579454 506313078 722353933 402116351 921022681 236332212 545224705 444240723 539434790 663684603 909630869 71661908 826635184 60325274 844941254 540958453 633691448 161821396 522221056 78798754 422699821 515252202 868139378 459502832 512823291 658202419 928888910 125831625 562554290 564428210 736342235 431589072 982202742 64789057 253632717 231632641 498593678 409603754 637519038 64568724 543553476 293939442 747385294 234257344 646429903 424645097 471065873 311148447 450708076 833886176 995048509 176250960 955324676 155126462 524247261 1578315 253275146 51090995 417220747 550789426 939046292 92090740 259154419 684227130 703842799 197160780 389833316 545352194 601870772 467066211 627277536 727240999 733290561 372614782 890509266 338835905 899734614 345442444 938654374 134206605 610528998 95870311 304051815 626961497 744097315 86285671 787763744 45890347 581740214 171046255 294289693 196637167 656696376 464332702 619225916 169375350 227430346 384133080 668953551 77342681 358088701 80485495 234061582 322290424 896795809 480214477 897378996 493686880 930582025 173107711 605203147 721232068 996846851 90395640 367671975 370500642 723812870 188744183 650859836 505847763 527843658 115146623 471437147 223048621 903226027 222000888 394820566 460880173 605519450 426418678 807588536 63129025 216405747 225277252 700925715 152940231 532881984 397011835 644766126 465431884 604875251 616886340 960030661 386742028 694308413 28907949 423868250 73451586 316751106 542412858 653454857 488709018 873879566 300491399 547430523 750503622 870064678 121239487 921825427 153543375 191588864 220048000 538274340 770225895 792865956 37015596 731048093 95041417 253889851 336305808 565746021 46780357 450712825 138487468 903569309 112287987 929353556 371579996 709570506 702914279 768450617 318158791 427650883 365804505 720610520 157294641 853659693 569543428 766969484 21285703 783472972 295648617 506040231 79198859 983161396 259219462 596298128 685369757 903642168 205487235 472323390 469147711 604205345 26985163 923616288 329513857 511081951 859359312 919280434 52906679 903658709 161825347 554553698 261805494 384167721 146396723 463814291 101078931 528694216 294722806 862855076 366578806 810101567 285174146 619711504 68045275 736955976 535327592 730817885 440819337 521901059 386703656 976835732 288974059 483205424 621649107 831971524 66166987 148846627 109918754 579101563 206106386 892504983 373116866 832995989 27100927 688758326 437875692 497245464 248653122 417040274 656146676 741756698 117384223 288718519 543813616 810050507 742097395 866357739 647845935 804514401 46581679 474788453 530149580 834047105 34925072 877123466 670322553 730141770 11890803 649392242 455569722 546123764 293319105 738247737 14084755 873614608 157449708 580492449 563379998 815377784 655080648 668807408 30796800 342128006 194663079 945140277 310334812 683938159 232774423 305335366 6672161 783071025 182679684 974273086 123719231 784938564 619662899 886076015 99065010 223819987 177206285 877682568 510673488 678855096 17074318 200793582 431267243 509026779 509578280 784473900 16238904 346515803 646009279 710841565 498798176 835204402 123556054 843524043 265371249 879939781 115066151 770329035 217588334 987883020 185757622 852317250 378597272 769503513 121016209 343620055 589084074 856732147 372387057 631271997 143424197 669902744 86971175 203417729 468285217 884965729 468313877 909350525 66432073 297539112 463916367 516312125 419454589 773694760 541069186 961470031 1546867 107581608 409895914 928834430 179542996 801184227 244025913 856064918 468926330 764960121 158734937 821424296 108380771 252758466 653407862 816814797 382172980 402091963 361556734 736457163 513261140 559720215 216629034 484802606 114823204 521161819 291431046 478017747 427949391 705161986 210514803 364258009 298414815 552741584 356416579 732642996 429218692 673778085 240419026 552076251 410548152 975381513 387286850 726218666 497934613 681586020 611896109 739002281 795191635 825287548 40684563 196901331 538699950 679459303 403316856 424453719 120383075 342847304 2072376 37307436 246897656 663060385 81856506 490749748 523666773 917846133 317390550 819059221 680299962 858394285 180749409 829480581 437533270 552831911 441339234 756293194 397399336 920558638 139320381 640536398 286950636 733567539 348453793 627585061 21449121 793329382 217493850 646015452 107704592 296277145 47204693 466133524 272138005 721332969 133771047 252334496 46547055 589176637 170037765 896185268 94808201 636931214 179849675 234752992 582946452 792294516 357040748 571842720 415761300 741041961 459187467 576222405 303138678 542482218 290057300 652078827 529027046 721873494 193210215 803585063 36048189 263757026 382828184 813560778 435281502 780221852 310297050 589335714 595036287 915793945 430060283 902038092 527748579 966266525 39527511 421669141 286413871 340489373 404162857 740649942 161716346 962446506 77268526 475858183 671697136 716892217 326389922 364409398 300622272 739064166 382550386 950168194 30739466 947246748 290717393 961342270 110679038 599092006 158805503 965666403 512737248 605436390 87774322 643364207 500058534 864973059 52888162 279465238 851418908 929801237 432967333 810737758 711639810 896521046 786386733 958215888 181216809 788773952 404141310 837027044 602153755 794807552 260593961 274689198 240913326 583419990 54820360 344786523 478527541 849163868 63033627 972846205 389753816 609444021 72051368 135066684 588970959 692105584 307374677 820043659 133157827 536225737 284833062 601583434 357930751 786541732 418380247 885111997 470355677 674436822 332155798 724333050 121516927 500466459 60060032 919602449 488045946 712628796 119915396 826778288 5597072 861219213 922281588 934378515 421278483 646091652 77195100 692571458 269033204 420308630 187060463 431168451 287568707 480912085 14306788 351407662 626912155 956501864 167602224 776691240 149516072 785619650 400987399 504791705 69847161 578809571 313948015 646468978 98068602 494398019 151899494 290236667 143801055 889399339 303516544 944599074 657998840 868516586 27277915 859519934 55954597 564549856 897820990 988420556 15508830 405632374 398333865 959034363 251009261 811579554 200473237 637192640 355013064 670838530 424452287 650475199 239825487 682045439 366274698 380496560 371828749 936400896 113459125 422340042 519431495 884195262 389378550 504716923 127803426 651493620 494421940 573076252 671059989 791530064 53552668 634652250 49627194 533036132 279118881 560845621 191720332 892821935 164142977 246941851 50566637 607136070 693385422 774267431 296876369 618182921 43925771 409734033 355194130 668859649 148926367 219010549 152367934 409388144 56574358 885154182 268043801 890941978 99872689 422112287 43974822 292724189 152978289 690246571 408924348 442527066 839571377 984318162 191751284 311045010 227027226 704824935 183605460 748134777 8480962 949069464 121997644 833232347 675836821 750518688 152583545 255663223 149508888 708948753 70200819 227249274 561599339 802254983 275656909 343192525 703241642 729843718 27756483 610163806 22797282 193218768 838456279 894820837 459660872 995667381 96544522 784307128 438829840 647131494 305873379 317902121 366707335 829299328 463321057 707324210 274514895 365365076 569762010 823260593 30532752 155489608 110153648 886754150 497085166 514409361 240486307 446323051 148762961 372765623 546074447 913206544 785390866 878392222 153570866 476702123 334443831 985547865 389384576 992897542 934201648 963388557 155330802 959589842 227250597 259412101 442892134 883754007 607484590 704991654 310928933 809996876 582004099 961336937 67071096 832804362 433170275 643323989 9863173 276272567 184794938 312398254 358568167 769198181 1830797 271678068 744462551 764138999 320344668 834766294 147218252 215665870 68939021 886665711 691524963 825165451 25737921 582280366 271747352 764429107 740356770 848646568 202671999 620748514 247209061 692747162 826789299 917131481 220638712 702352113 183539121 421946842 156311105 199507564 98972721 368582404 30801292 395778600 180874885 366797937 370199905 545592556 124104626 970882013 391258213 469851620 632501796 766026909 809274292 822321850 155571648 720319502 182086711 264717103 193518156 821850082 544222908 988042877 468238761 782470846 759134298 945860481 668941427 992590382 725710144 769659964 663826579 866636264 273475208 657846890 97838275 691634322 26206507 532008707 677486538 685471401 768859787 960676948 817056017 909765888 674118391 947555249 686793315 804222285 523784442 707686464 141473997 178052040 117720939 588200744 100882286 526912301 499343241 719547338 55506204 927266055 330058230 596586013 680904552 871460098 395357180 823646787 325719427 455673439 781453180 946262722 221247896 241226540 329861321 962031400 599039535 838977994 161194085 874361208 218873713 883874407 119189462 928426730 376741550 405315151 231313896 625127878 498968841 828586399 229571250 798354227 472406687 646277850 686019044 772216127 575216888 919912522 497167084 983171134 674149924 702409060 303398728 972792777 488933948 513823271 640517579 778645069 143488614 305783300 158415789 798452204 598609690 988653685 183145235 258395830 676762370 815253416 124826924 965168761 293216059 445245633 807530915 958241647 285285830 722713116 662811791 718235877 97955597 865631630 145295669 318287294 587116584 676573776 287046878 824734485 693380880 866702734 543344922 924778206 430616467 631631251 368387787 379317903 248298183 934775733 289129414 891626340 207751770 898764338 602156567 751924662 3116027 632247712 28281586 781639062 235805210 554622284 674490165 701845130 393951096 782052440 382656768 891845464 591010977 709408500 65579572 850773718 218574022 626090993 715439595 849319596 66511803 563151907 478073855 637661467 128724534 355311184 33624739 102310906 243458383 377112986 359758995 518647928 10304198 384692056 95427524 955205095 365431476 741424354 10261789 932856155 326938478 530294266 35774960 905273583 330614130 523791739 186220997 666044512 374726557 406754203 504430762 919114314 21956117 48881996 94142559 361451568 415260475 507414271 367056436 969761420 197113841 838447678 195925168 684430042 186757991 740749445 172228490 768241319 314289375 478502737 526468922 873536459 301683870 383400925 521467490 609474092 832243582 897299672 345761713 671975572 34340817 655798709 647199115 881512023 696814173 812476559 41300546 333840113 876298142 912618680 329038427 481468490 551557865 962305781 610455761 694151400 350430021 467747846 586919798 712824314 72377974 483547930 155649575 746696801 420000738 773015262 132690307 886314498 221769000 576814194 269973684 805800074 356746187 447036882 108994813 677880813 501686586 677366850 28647097 93060786 756595887 793454021 222921025 685977838 419711868 617585780 56455608 895475429 605095823 751747591 589678229 637878200 359961750 434654648 319326954 807123666 369688315 533506355 888285196 895474313 478140407 877029581 506409117 667290025 347845839 505013284 192295198 396649822 779911016 948675080 66102163 529605291 417489848 933232013 551495605 748299890 189288822 348919388 119167377 457740791 739960780 877817372 172651325 353177215 256314961 612722037 133152020 744829267 373449637 529941987 78949535 626812353 175144591 457731088 46038499 353453522 221670598 550360841 532997544 835763386 253193766 394899419 195360530 581681537 597934793 992254769 53190097 978121364 94674907 614454625 895930545 999774280 148004557 375971130 488743356 887637465 315609094 818535954 70958551 322092114 329265674 470036726 525249708 965475232 102535207 733136595 736186447 882819825 705767604 858795842 525662284 806520904 259263149 905294818 787627948 912867040 335508386 746906935 422471460 626799001 312842846 568714426 232837127 346309327 113156919 721632980 193071145 608553037 774696032 985683232 19722880 66565282 399383954 959083612 698836107 802749540 243453397 634585135 627861429 960121194 348453500 759411832 276117242 276414018 482407892 579561128 153279592 445572462 202310654 594963655 435299405 946524359 9595120 290712632 208260847 821213739 50569070 637441746 372597812 677393638 318923567 425923097 675366848 796671704 148360812 229951805 116961693 128122371 74273088 319332166 346639478 889323932 170592462 641430490 119769275 527796794 840954184 963955200 196957016 550554029 274102798 864520491 852459645 997070427 633455792 746776350 227060558 705998346 135412775 890491339 168740313 174287339 24938682 226415534 514516095 850810887 232015944 493541627 355041317 745667860 559767791 999524008 473020028 506549815 37382562 700170219 23146488 318321564 227084974 280932637 440335118 618641879 395651130 789262291 628448698 813949722 523630240 662192485 188784532 888399157 32049011 197324954 453811740 605973571 378908102 434015930 537999909 718833805 648558703 924213697 184372751 243173235 826626895 905816778 668089934 690566764 575658421 908646787 449814783 569552091 805117168 914686818 302264575 892447343 746953417 874738573 51584665 308747746 512606260 938729029 386322066 654071200 1236030 210182031 791112630 797860091 348191390 880397040 436865784 603239808 304175944 593558275 7925815 761811878 31420754 955751936 164893256 590682434 125060066 581388407 30650663 738618179 119521918 287542422 922363724 943179215 198574782 285190059 480692692 536242322 962216253 976202894 677808695 965726010 109298051 117489724 476585350 923497985 445157992 922386485 706645927 898942755 214209403 788926138 25960562 712000371 728399965 803049605 306228283 695394666 301629103 963161199 263921003 856777296 537672770 658328747 391708281 557580022 539986216 955579567 327205905 647402240 790330357 947336073 22507319 188147953 441911020 868261069 47265971 813660725 88562524 534146078 292839614 335742572 501438031 889581081 98610693 783783492 733116808 863737982 347879280 952602261 512535040 619351176 550756987 926294553 20370404 471450323 365699141 422769289 420864267 575937232 420355370 715925827 411031862 814766815 416387905 899784332 382501470 430496960 859483731 861874587 159148087 803489421 325467071 595976950 76585994 133577276 299712050 393232930 633106700 677446745 640521070 912310442 65784387 935214989 402952743 610898068 198548644 360370543 349157155 551119346 234527899 461612042 140241349 574658334 193522074 545951141 377640932 908379213 187182453 623967053 215485297 679180980 23338426 902151076 337078972 851202906 65781780 498090986 310216462 330988318 959423221 990982520 400358652 613557086 961526755 978470517 61096856 430481496 227921002 631583509 149987494 615157014 429727007 741039562 352864217 863804784 286343840 723933640 249767375 253118925 78126749 832274564 775938784 787242740 450395363 528143977 46707811 555691969 720786364 746727072 524048221 756486410 315022025 584198726 68174390 169984729 312864713 810532736 39811751 910868880 875527749 884519226 254286225 857319915 120949197 439371365 684391263 705496235 512508615 724159779 446854215 449951001 185963930 664378225 302191555 652371745 362483540 891342970 28945095 556068413 616684390 778368269 77354967 868948100 442723273 719300615 162673062 972441349 88647932 452372697 410909817 677838443 305114831 819991900 234798564 535778949 376334629 728404089 185448535 599566653 337963450 920033821 53232510 707663380 238028973 979869935 80986202 379464759 492164636 592987892 916156460 962945071 713963955 733285181 254003325 919592632 171710193 296704452 265929803 857589890 21620064 811470595 606588421 994400488 40093943 317964279 218974933 939131939 574094735 621928264 244774910 824344234 358026025 358330191 568494764 749859764 430489255 436651916 687344241 844271358 95981183 218932527 456376053 679152263 393049999 671818225 229193134 440838624 73713855 479394834 59910292 89509428 495862968 981604306 611730406 733432187 648122951 677393021 12544232 146669449 329084693 993098420 69560438 275206982 18815125 96321595 179983595 765511221 6825962 406785870 440397142 497531673 258196404 430473843 308812234 715189981 543449745 708927364 50346485 380723955 623745396 953667585 710751387 792272312 277905891 874389296 214985557 358486831 18865449 736688342 563790122 734061966 172685266 652883163 44917120 837907605 70952873 931220310 61826977 82822763 125843873 748192493 29027570 336228315 396456887 971680789 152753795 897652024 278469589 381025544 197539537 464201483 385146131 925221275 626524211 690497102 7013596 372596891 32790323 586245264 174045405 961245682 504136017 510293991 178066539 718642597 350674385 540457957 624777663 836806591 478142056 750933744 13799686 907858301 171708056 185940631 50651139 284945096 262165574 452351936 730544739 999420799 259819726 717930137 698316155 867621847 120288477 363276244 372426548 591151596 633249680 738945988 444262459 622635875 593651660 917682071 15259253 507324101 113589312 755124534 152289613 916438819 724974477 759153672 211374306 896659525 614644474 846724398 382266794 731043948 281517942 345418008 643942489 815865279 241135875 777796958 130133787 430223060 36134422 131808702 268862809 891569200 431799506 922948940 797507372 813025090 354034509 960666633 140971576 965542071 434211361 471595368 545237082 899071164 293417540 754951825 613560505 786993227 64694766 912957310 184094649 804816728 48631736 203166030 179386923 893790998 107730426 564722681 262639157 942987278 861407158 941159202 913375721 959893559 324484033 976876292 444330542 714969411 58959150 114273046 554141413 705821709 99645432 206138401 293054663 583694608 394289996 551163246 604060398 671932033 534542263 832507530 11172098 914512715 412879754 948551007 8395068 520165245 785854772 887672096 290307293 965140144 304599300 421036966 58994131 902451020 815117338 960339941 80784699 741138817 10597534 968267764 57650101 156773693 147887121 166081134 30459864 879262734 392135024 788177605 51330747 128391504 418303190 890697593 506451428 858558550 518668090 876791107 126482680 927019802 170223043 851655931 42135907 828068856 539993238 894458368 646221871 977334534 294807459 440248616 400179671 534918225 793046376 919035689 669560714 945481953 150458763 937550987 616888545 645822793 344638382 354358432 460274261 990600338 492596023 803670687 322574235 833692182 1380967 171895247 240845264 898276450 572877502 654451129 56361171 319044295 178174646 909324174 129920971 717987626 278773921 509848129 100875222 788630618 197297857 474370852 692008046 732140137 798125685 855564497 807628325 993063985 289030723 482738024 113246526 969171387 372102727 408265078 293437532 443787471 380748056 794928706 713637298 932195018 361304659 385404461 699389020 991525117 859198282 865863482 442896860 836789803 619389176 788360759 279069310 352788504 465268075 872333817 416120496 610701955 150518731 671422662 36858953 978818378 383664726 709696661 200848538 995802218 110276749 614973957 685172933 984715762 187385924 378508501 18366355 530353501 55088630 916377866 280802991 432240488 507642530 778917547 510147692 723709188 31479989 909894303 437326287 647525714 267215726 869807806 52235435 687403413 443758125 791466780 388195862 838844813 348888856 363913369 29422928 515894676 435368141 577726307 309400715 318337192 474568363 682806567 283897966 394143578 65741231 287293285 201974894 453738960 259300470 692698471 414760045 845518223 197078021 528585049 409276895 463792729 7488498 398347153 393200084 449397085 822818484 943335310 93366353 584514794 40976391 548253033 587219294 913817437 539628037 943988781 129812237 758388397 38086166 132558911 464931429 544697978 198262587 754704093 645998839 763495801 130231335 404561529 334835681 569790202 174927396 880898370 323698197 949664423 703384357 748318923 407665982 626019499 195922291 549701681 53544000 175187226 34785883 68428136 488274941 552753112 270217051 295551622 47582704 882126996 637839658 924147341 834289896 984807621 178424018 602792653 209726280 486528437 572400937 769727810 93617631 220686303 323111346 650683594 667206964 702721765 427555544 907733726 293220700 466300052 182617450 227089947 811543099 962695609 20194837 391603978 281781444 866553161 11255418 631588607 303778491 705666309 73033246 236290721 315357485 822427944 719306357 838875430 70417832 987182777 372995849 618046174 555421219 987531178 363795125 911986842 322980177 963939311 30710827 851831632 333402188 554671868 613535470 801123560 229883953 683738058 552016809 652657487 66276158 744209251 29260361 217559038 144479631 893344861 592622306 697654619 169904845 721639607 43142485 80806291 368234398 417450606 710153600 831577234 888515203 925780294 609277792 977769520 90599184 366126054 199567698 876063528 366948775 624004000 373907279 533064952 223651654 942759529 13779407 639231575 118225511 682994133 416932633 465857294 231135197 527589830 87487321 646649102 604605002 986332080 565311393 923244486 46349414 680998648 310639856 961828407 260474761 876761131 59171623 86376301 395602691 520265260 401890833 962945898 394571508 719680784 246067383 509060068 722205191 759789063 218914324 813365155 478887063 833039347 76643369 477972159 79787245 631065258 746055036 866210974 623886970 988265826 635180446 839987340 348289688 647341026 163439162 207670678 163267865 740110255 97854030 723590036 435500373 987090726 434758442 440691903 43948494 222128631 93789436 585999351 3784169 827236135 12965089 756276359 763919567 899076019 367310 38634162 430402271 624940859 7664645 358522188 610346371 972001883 217957264 890900893 99877608 506733983 174737448 729635437 699728115 965000894 529466479 994305547 109275238 534978789 75433166 661222797 6931370 152614352 600683702 826916761 527172539 665957139 47490349 200360114 511424080 590733327 850363536 961305788 511785942 826932758 70389625 526217006 75515235 929163175 265450044 814100350 117755372 750333480 368659191 539713662 163346199 840398044 542892970 568111951 183142053 777409582 333455802 787524102 268640705 636290190 365914664 518331859 815535806 969243294 78119119 384084213 153137929 368041193 298453169 922295970 165880930 680691982 378041575 980265723 433363518 531239040 542716185 962799790 240240181 400918070 731185260 746807325 162926330 601805901 330157845 771294434 46056766 679705881 50525981 115779036 247332643 948056815 518103058 817946368 18178014 574105977 626846525 888169876 77458843 863223412 9575865 469156017 390289658 770133198 72267397 942305645 37759310 874097546 754313761 992322725 701080215 818230716 711047980 818252159 149773718 164909059 505070924 783528204 306673236 571446511 177875099 232256924 316521856 488977072 571647126 861250474 515984193 877164478 357451153 915969143 32319638 905025477 850050608 961735597 982553183 988675352 312574695 505314772 261974516 634010641 698839880 740740439 34562615 252502407 83376621 891359748 144849200 667013771 575515928 782409024 658685134 878143304 789928811 855460309 307895103 468893099 664579345 881933363 195736631 781196014 454051555 664667256 155490040 627156994 940292825 996724862 96691961 872426138 2401171 452046703 105568542 120513432 527846604 697196213 220610856 269966642 587169779 716036941 452309360 643050355 482899439 497866113 13376414 298598050 248586123 448237895 326739605 775536483 186845415 723654251 381510699 494315887 349194433 364828605 817304036 865342273 406117540 596051101 356054072 945124356 308066890 797174447 118470343 615500706 316161963 347317029 290392131 376285097 394980948 489031085 596856223 870327367 583053970 886889721 6339735 734348607 587309013 824562216 180313511 442272971 230835907 315971621 251646815 998315832 80368005 561254160 8079455 272327255 6284512 605311754 514364003 635243415 43573120 967971045 553439846 758156993 185280937 207019221 50676145 819452114 195448376 706595599 169935542 600041230 643374546 727087180 26340007 108210080 159731323 321360538 388409100 679356818 78994851 213616674 151451217 471007800 132771306 961264870 650269422 763161572 711778517 829922430 384729615 788285425 224909964 587192238 175740697 621490579 105501080 691932163 467704132 691952737 179828102 471281361 624667797 998880716 449160267 870842261 60383036 465264243 246985911 408810471 340329182 511110162 394630111 924526790 408031241 604070394 724178461 773216888 327830973 660956400 230028526 832207281 122565387 369457687 226077971 399373922 114930593 986389268 839553593 885418898 506889256 825021633 123927848 292663742 51990861 403004248 107935861 596973260 384296761 574809361 53630296 558358760 122064029 353519270 118913270 462654236 371960140 479555614 43227985 253381901 612487737 730058585 134362138 702402894 564262533 791059348 70570833 655545797 209574815 437322622 588007934 905825576 482016976 779150487 446491597 494742678 74971716 354195692 179517582 508608203 96256225 432195567 70762155 465093711 205006861 894300245 222035803 574589607 132796580 645324330 245188472 790595748 474521947 741436835 258343727 922417182 400067042 917883074 786066934 834860060 157912284 933631753 145573796 193473430 634134755 871512242 71285007 520902663 542304525 750142829 79066398 776455731 395792982 939981585 472372088 986946136 52643829 221038620 135893932 697544255 689676895 975336945 109426194 563575978 25254148 132514497 24040139 677001368 22330947 450566620 598037573 856391321 633812227 738348011 265620303 476290394 77175755 312273436 538594087 662058480 130609054 469745962 360251042 462484920 124345741 502851864 37419274 557660952 308319600 937098510 701864786 960856833 244786768 567333458 107732127 558033470 48235567 389248443 693795480 785332970 745036588 859727135 113780314 394466289 246363555 715694589 331342281 538223952 326319833 344289276 263783653 699567479 349837080 847513478 49780262 746339432 559482119 862247163 842450809 953124660 196984124 496830976 92398174 351171659 286309879 844651139 133312242 181197895 369119416 560344979 485746067 859800228 3792893 662488074 78236693 607301763 696944301 820241901 789379109 917827866 725837853 751934553 612632410 732774097 182892277 649566934 85375372 730445874 260856898 414343448 50854552 813997370 298441454 910300325 816151770 912708296 652852015 759754896 183296847 197655175 144935811 773522216 377270208 631886968 11408103 583467435 779944381 836329991 22441361 47521138 269566949 347151771 368114349 767157115 538948190 669389989 355806123 556550923 351707790 645117862 666873051 915949303 658274720 714780034 526984634 900920584 5632954 369229768 578160707 663215644 480922588 848372552 254180317 388146149 238615415 472890571 470542189 995870079 704235043 843196193 143151122 479185906 432884150 468482230 512240604 738111405 154353522 373268415 682284684 812524878 169234753 287782432 579117517 894163672 834376201 886095752 880318151 994374498 294403095 983171077 632356385 708343068 680876026 781166132 707546556 778967295 355234510 395481351 152816994 285240175 334020263 697103515 505195741 799081864 140017691 409831181 174930089 578856442 401300833 894177687 448343082 754751840 554837729 812037415 480432713 558946487 106095246 312619882 150677512 302738427 80305065 722301722 641272537 688105395 162905252 866429084 32708776 803871719 404363191 411890569 235034662 266279946 655525228 948112037 812794565 923315172 200048636 984296312 191501409 859707689 17218832 662018444 105788012 541504473 787852552 986892025 503036581 931673875 3893532 956703437 536074931 741403838 530725078 824758173 389371008 915229108 676643077 847273389 301191576 803329506 667690299 949485655 328449714 527541740 96302382 649641576 863430577 993931011 603041303 853425174 828739111 959801044 126749412 908478692 216842610 989442980 57559414 918563071 231563102 442253066 27637305 643064009 102446731 586708520 536685158 673151656 120191619 592505776 444583419 477500692 321082331 936302355 750112383 830362997 483549015 823298323 29808596 446733490 30121252 860942863 469411022 595421200 218821016 366465227 253357021 595174891 190425052 847883012 302341822 310187911 498667062 666108284 80886687 509403063 275500053 718893336 122628821 937122598 142827138 699530371 470685392 498766723 240932754 332463896 70985054 626448552 233745040 548637873 95710137 664215277 152941872 171629768 170058305 678779447 33937606 654080755 250472471 688404058 80861003 529760788 378477115 585390565 509538124 580895016 266044802 919744186 482819582 756463274 876692099 933581318 655982489 981155776 206604081 382737715 730803501 946546615 968873654 982308409 243591778 899838110 775432376 871328665 311127609 726910793 617158241 680875822 307426826 440579873 366597120 795811704 414400030 994148632 220002197 466825513 304111489 760324496 24417498 267882322 275509435 696901194 178002305 707029561 182551002 777758490 231096953 264765173 304246786 899805846 126377091 700595022 752604231 767287680 596180205 899358454 599300604 928717096 830617755 835676122 353400096 586651053 633525607 665970845 366977404 380072278 223680350 365734787 122277340 470302597 692895852 796785010 441654212 592581784 61083607 175147640 287000156 605016662 436165210 684151805 222886328 680914182 20306066 382108701 883458265 960288103 51599343 170334409 426546027 438723812 588121191 999863483 374471843 807982540 380019904 761932888 730717722 988062941 652457288 978278903 18055549 826497060 528071241 807548854 271839712 299165674 248170471 573287789 243173483 646668289 338145015 588463599 518730425 722681304 198182720 258038439 616237521 723996635 675610523 914218961 551100199 681942777 770987252 953174914 5658432 625689811 177483580 466428557 148026414 599086743 789447277 792047049 228585768 687804480 258864434 491587443 749316968 975710921 183417893 632063402 261352480 781381466 329256613 625343901 152070698 242561576 355047051 640590287 714046602 733950159 61796443 216991595 592512898 947239654 1617268 544573873 141415104 422775673 571315185 996434176 35186104 591766254 144265428 983583742 105495477 576779053 37252217 868369524 819284532 822226106 496280270 771124002 563281282 616339333 144252280 287047910 618322029 858415331 422524249 828653009 412158409 943196692 370184393 412862549 549861949 907175169 267191749 784552308 65342022 185737002 658300797 758153211 217311714 483065427 94826243 850760887 47053680 875462705 40066152 752461657 223378808 450777179 260818439 948265765 202658914 280362909 13084875 798618472 895807793 966819323 123653571 951509209 346719417 587140026 88752664 229910007 56467780 97384315 5097087 610420510 305026065 938694429 39449335 842634529 23068443 588421483 552593764 874799958 136043846 718032751 299569685 521408625 19989500 92229804 530466685 750812866 721680233 766501878 17718318 80567203 778543443 940873921 275752690 463506373 597315130 897980183 917546160 941898487 96416330 330646417 303906126 883088294 432208919 831003369 18983760 454466341 248357463 574009727 302991734 780626214 183219853 357095542 251309868 876071929 24655983 95271548 446195192 610351344 555148473 830290021 737755892 801121399 235231802 253342690 620592113 995469937 386424789 941058085 166240392 902351548 15265942 18527125 4303128 536458558 440936696 775046099 446899498 761881879 87084255 422377502 551761666 637894134 223532768 664406699 520380263 842376477 153514727 790658607 560955463 807580691 141026211 766574801 571930566 837262388 511055498 720531984 257829266 649201411 437968106 843832159 292767686 691269909 67925901 757063980 119679273 707285142 169270351 245093825 454318745 455885755 434984828 683057224 377471911 522264832 185808232 517635092 374980498 725894654 490284612 549828158 273610907 777050034 479777094 782337886 353809765 400090773 534730959 901401252 5709729 455583837 126580301 708943006 492123410 864836289 430844146 711457215 334552194 722254890 207192982 389299729 739976409 793563526 426152430 570996426 856461444 993386443 94058755 829573684 144444508 687043535 28692986 589475402 462041125 594676261 447855904 462212138 124256077 516522145 238540916 667359537 167369326 822868974 98873760 856714886 87338517 541177285 160014450 430695534 714786301 997545242 751763103 787190021 131463248 690283316 181704562 268636314 315743184 524188151 690643241 830220629 355406355 453720606 161161744 288597883 45178550 604605013 275042041 614127815 743847759 985805856 438087335 886667910 304838158 380304559 21579998 120764404 86223431 376882763 412008223 503437822 598028214 607938001 321113178 725611605 383230241 552395004 500198336 670626058 466992048 665419778 19694444 897140311 61541913 398266963 76215785 143276383 128751386 526860421 761505065 761815612 451154890 587070842 361434279 665527657 522073231 982376858 28221088 447274960 342799186 499799733 359551705 653213611 431584275 611727112 616429101 838567206 344231743 858114674 7402007 280211844 556577671 567779157 49620447 262398988 305114285 545839808 298605800 545749772 91549569 586047580 397562900 475205253 261831929 399867373 260878475 978933507 239971003 716489131 427600186 922722520 220000270 741729617 141130 878637877 67287500 813188089 148435416 656634151 556206987 707019826 27390936 124635595 260967852 740519205 160195477 176361049 530581902 764117577 163307017 419454785 119166542 853179463 37364272 100164900 447228034 875578267 643389692 952573319 269378039 320872825 755450426 850746877 481238180 884368332 65589637 622835113 782634983 950755030 270082226 574164262 189075497 366331625 171977230 673060053 430491782 494653173 398490389 426233029 108939345 377827649 68368939 572056303 490643008 523102059 137197438 271905152 75089479 415253892 67177675 603511431 300335581 781386647 470738041 786128219 70708641 205703931 768639721 806326483 338412612 695116996 150895792 439513604 300716220 841313437 162318538 759657025 150341992 296936487 241784197 566033045 490623147 861624014 412809800 775595029 570378837 600377395 543890929 834882567 78864148 849195930 217853096 258305176 420920970 920239313 755644098 932273152 247558615 699386944 465354075 521906020 28917310 592439464 428656088 897137369 17821655 275102585 175069271 246224847 285288735 492332289 426832833 731635940 111468130 356406317 129078177 312386664 382454898 833164932 293727886 828742528 7227485 17652563 269594389 362602982 428772480 470833805 231698208 975756117 20528077 59337368 5543312 244606378 462859370 699948296 831955567 931258563 481930879 961614003 277280966 558011788 38929524 860166715 37230958 469144343 329585882 340436855 261014458 856603287 62489234 770258746 265274053 771773854 243548912 938586038 400412046 662902240 112719832 863069765 970923355 973987531 426467410 462301643 146772419 971873007 283767512 668718867 633336884 988960096 378783800 642135819 18633420 177687760 112961182 505927307 784347780 987015930 14977835 597272306 910535909 977659240 562084264 988303481 221637343 877908654 353414558 663386225 328644289 703406474 623271115 651262560 343476789 768770948 217734528 537858946 742846895 760181094 709394641 710117564 607206464 652561021 56366241 210151889 470205467 475286001 826354233 994773691 271952546 689604920 773839265 989593608 401490766 663127223 225008666 445079839 123697219 720854538 319849287 969029984 373100127 569712417 505497220 753969556 609831318 643189373 597733896 647571333 2188940 694852900 544531596 784584739 119825655 751409729 504400506 640537991 694330989 928224193 472273535 609529485 321024151 977423295 301175634 836870105 31469701 567729069 366080137 929404759 409292113 487430107 376532583 378456610 251664288 420754062 915353025 918574766 245021406 348108412 155595686 606773743 73273774 872217543 247885381 558089508 264853085 566475320 778261445 932024134 172281855 930814671 84586097 900558269 5740270 147855479 214157388 420883119 482815086 606371494 385987580 588202804 264589917 448817729 280359411 699455415 131958288 377766902 151482167 342962250 182386682 468701862 120263539 839489833 59502549 535465256 11022644 610324520 181067806 862788967 496704248 970349615 16239165 518949160 465360918 772693823 750259691 784886220 301803962 837672291 144455715 668503275 105213158 851741710 423155464 443052399 587144936 680657553 19642437 417617714 104384352 734217403 172095775 648477292 503698908 947895779 490482266 853232396 257656255 972839997 220773695 469938799 511099214 774991301 11213520 394494799 505827723 586129568 266833854 515322945 350795957 652912514 501809668 607686265 532658499 917331655 493072888 602807561 504836384 952739417 238121598 345189016 695879986 965187650 241827273 999680027 731473212 908064764 552381139 682789331 361898597 852046462 170549228 173139289 66542030 935756851 871346044 906832844 78105089 635482945 685112775 908084467 194295183 539090293 262291531 520299739 73115788 595815431 537002890 712978120 203843635 439925635 716596482 878122520 355471459 397140416 81181336 434793998 569716547 653834731 635432954 879630532 480115929 668747219 137253667 999966343 396046171 638428525 92270754 110165294 1791067 43137193 684731970 826210426 160469442 441840510 59001504 697373915 413637652 812937958 61611623 726636024 15325418 904331318 81724423 663692007 352022460 410693994 862678879 937644234 228524890 766876229 139125614 531531897 348115021 993392110 728159719 902299006 459296210 496461140 327461419 800617402 824658165 999089760 67570732 702061671 210122159 707334505 34730294 868748892 328825160 868833869 216742333 335833912 477692715 851911845 1547874 626226539 178344385 514659340 142425768 783417447 220201075 394299007 289762783 449986184 934719184 981766802 495454270 833027409 399110548 722567169 239592068 873059303 526669500 813830320 433171921 532800365 328757526 688148660 635293020 979827951 49749091 376431629 464631978 809700026 215703810 221358102 335076962 568456312 757759954 918249685 312930678 574949446 359785870 525456173 490215447 555937299 47106674 146687443 180880932 623774172 138955233 364817626 511761140 518324567 417323659 671937656 285048665 872732677 54412698 320097575 220294955 571650533 128213800 396115029 193540065 619373211 681447688 943882387 119922213 161577990 392301501 718725070 15991045 138527792 316791118 523339364 392312816 920926380 332442887 654972945 619894263 772898665 230456318 353736321 507532068 618403924 96120327 197015106 385151430 925534956 522618697 927184788 761972840 883013891 2359937 450140523 929113140 976628165 34910462 70643942 44273565 821217664 328396820 762199613 170298456 993342336 153054612 215785414 402124382 684678258 247816007 397726976 699811096 886747821 351797024 572267879 27322470 474542410 457625909 809480781 433202990 905144665 165456750 180045074 119647393 694454860 142083049 188827807 130296284 612671915 571903724 982728717 5623924 774670768 917825031 953657322 63290074 304715200 151462799 587822705 536754706 810093735 115472498 270030687 497938309 688587319 921043115 944071645 402624159 811510324 587011270 869537068 37061329 180821921 323243272 361352778 96874725 346980626 168117407 352338364 287265036 732307572 803382455 907480739 61844356 302002543 167197373 722636325 452960549 522230546 5958535 105570395 510569612 906954106 466184047 557008716 168426036 521227103 10111198 339313490 774770206 917291050 98489688 189557251 520948653 553856879 52407952 655873262 98992709 603919374 816027157 948443011 205074128 921142703 563451691 705394868 207200189 321663473 379024023 776062507 338383827 953240676 474799134 618967208 564544080 744728604 392000931 827829657 123674357 544617371 134217820 992238199 37582752 712977294 157537831 591054304 25259337 891987336 16028572 363521327 852631637 963584344 650707308 667669507 209407375 499906357 476751172 770402968 74973578 745697423 427020479 999296774 97949411 681508931 150874708 227542573 307695496 969855613 332608168 554399358 193687432 739792826 18505768 203118496 328530366 867823164 115254966 406173886 234651568 454723417 105561592 588055728 27076425 403593351 116657235 286701343 471723483 574822511 175885685 318041062 79294649 701950570 11514153 330763977 477093322 914356690 52573782 418587150 499004388 888997669 411262166 524629243 839832458 985396323 261379073 956770715 312754112 696652074 399675886 469411960 55506136 162881607 413213007 619684871 470143405 815708721 179569155 437525328 275264293 552239007 392042907 898942971 376070298 471536918 178292344 782291677 428885113 863484674 167419536 217623619 219829634 914739257 437525103 629143432 140368413 417075641 572020893 902331408 101914017 221661653 46916191 262391449 26162790 258059534 165499717 975048110 331201369 695286657 615553035 947207135 98794533 770659764 77410528 508107826 13425227 899451382 772944872 890377231 635574455 647459334 248691587 595238730 623384919 858803560 276994962 330199399 482655145 636044833 138066583 220350711 684124566 990748909 237016604 362651823 277984072 681523921 35476453 803386097 210396960 431642898 149691702 630010991 336702398 773564937 132530972 269440648 499349535 974611368 249241988 496209441 796726676 865185480 13621037 730239986 110183709 764779567 657522489 910642055 635638400 867774185 142768185 912895075 317220486 543876306 842301153 913053282 576999658 848862684 622475133 756811899 562626336 923563212 365281738 519282391 208594237 735840226 493081083 798843276 64865368 319037280 32151929 471368099 45414777 596347713 309403944 736548717 186020378 939851387 335852807 404646506 208289417 554960808 290951693 808405707 346527192 422668530 224108668 394359291 102345549 212027012 74555870 449921125 128210999 701294561 713942771 770261093 15966886 638461730 33751648 923262134 376233003 600823926 477599970 828747281 566948988 689656353 25024593 795665503 215474174 755968342 362858227 931883311 122494000 320516142 246451795 821390179 52275498 360265296 706452254 718613305 186720274 192836444 200955127 978995006 28657544 345812699 450450568 505473823 79798732 693794638 26415642 469022843 486048750 671152736 93198838 497038639 811227210 953768606 507227591 841573620 202999049 747701837 98171850 173723671 165632747 281296951 54690137 364532573 149608805 741626137 909425252 992298739 901710400 902622764 653697660 765414935 573330017 785241894 489398296 890072755 125961314 947116734 80489628 848837507 6040062 839352735 161657527 513671756 95029569 308324829 233301968 403322618 352851043 853097994 722508066 766462461 304473699 401607630 137340734 571367672 453775290 669201902 398987616 794572697 307503909 484049349 519017473 717723948 181823785 787613483 587829424 692408725 25241304 275272206 686998951 843602304 992923155 998137994 323425625 520786290 618476194 731445101 64964659 941203973 607545804 674135730 299480719 301244609 826411716 969812742 15641957 356507066 489295634 822325758 542793452 546439231 486299602 859798174 6531117 907911546 139511574 317102923 12837330 287712497 301990842 621434510 759055346 863779113 116857914 700414256 177045754 191190082 368287483 575471369 118005981 181603803 50627289 318145157 508642317 593162570 432710804 929662430 17356596 73666283 251499311 459825455 523815535 676081966 811108206 900537745 179501380 541290247 770456174 906927587 195847795 674871544 709067436 784017357 356423144 943115139 205977166 841178122 31828037 957564905 309857321 644930626 144423561 575244094 226136199 681603393 447221933 647219914 642422885 951798843 269287098 617041358 290608224 613474010 221077806 522099200 57217298 946266428 1698547 986706972 202634950 419354698 360570875 523767040 827929488 924475233 227721114 726140161 532874629 646471557 133589500 812175618 453492126 839237544 468904544 976160817 445903833 496572532 174491335 593388611 516112909 732677806 319084118 425834805 323069708 548361676 518767733 981442106 697357788 964062662 280069844 890051585 420890569 686543582 496749604 913135269 274978459 878642412 274582723 760665240 327261364 905115611 69811501 649995061 43435735 66422480 88640873 374088656 587063062 692309830 148002095 973169823 67992048 937197952 124734163 462357178 245570536 533286273 651260299 829186982 28561108 687850610 15061198 500557819 467131479 500722755 386819790 817187213 784709819 823426660 135764683 904920102 382077941 509804686 623053732 956409644 307038211 468511447 754856057 845286850 486614619 995331960 71685392 518922232 52819871 360487061 503917923 667292205 544938714 847280150 80654825 351978653 279322769 708401522 73921055 805044691 63517322 250109879 149886999 357310345 411574719 618135643 101312803 754968491 237421799 343934316 673383926 702855003 152582246 457493515 483431089 775188312 137857536 143844003 548838986 934766365 343802551 734399405 186204776 252424958 530401581 953444381 94123342 840637527 902405655 947398664 3165543 986313683 49080257 143780859 289024920 807934636 332829777 487977975 488049103 808023590 103860337 156391420 141703140 460942225 410934734 483379917 150867183 665176971 456188475 950107654 297139295 457143929 578825137 933857392 125120098 858877937 953018271 962043769 1838264 805240648 288527112 394871727 35438975 738858516 938122959 992008808 28978935 289677526 9630504 27644358 76781281 768593849 360145744 473231153 195401292 693379604 74376072 661163949 99007616 496007022 279833250 387917151 214138612 886934007 862568619 869410496 709169653 962380468 278254929 388669280 621015910 924204377 52365206 221033771 114972068 511210341 461880342 840567153 145828794 686610165 468703751 475365213 428908489 741755716 566523646 636712159 285561269 394805226 486087662 810953516 568259756 936972072 467692531 530663036 823309975 933417330 12920062 506783064 40703055 993163890 621471349 720403057 473884006 589052204 187953577 737869975 381787745 485082682 12798027 757676453 61642877 928205361 171666474 647143956 79936187 657454797 300743940 690579302 831343482 833609499 16237588 534033832 45442148 81967742 639546884 735989875 231180616 502610861 910896339 944740795 137643182 786697084 97620353 892886066 99219204 744471726 557507205 593571435 18384439 158759048 305107413 312681632 295026211 695568393 124260345 312323720 32702999 704344500 220086665 521022609 228898446 936528202 30354585 428298343 291584329 586119168 927055904 942945159 249064016 863621254 214028072 706435778 457294981 930173526 25280311 994451892 592476153 972991152 120656939 457434348 125882364 438288701 694941555 808835793 306454097 461137758 286783847 557066586 67863103 318659262 49746213 167567871 572312349 591855168 214655556 515062173 193822878 343533208 151658128 328517753 707493393 777379260 668000069 814401170 646083500 881282115 286424030 762661349 303313358 980634469 314667603 694792567 737012228 739852831 331096096 827863080 395123014 427410831 551485 342805110 146466255 218799830 559107363 602134691 471514521 826328856 74929223 770671130 315173029 526230015 627956586 744429411 180820286 759682602 424489319 809982508 240569176 286696397 377805470 457555810 419443468 832178709 270917990 740354678 222948089 579272442 504483816 727405052 227587283 416582354 333556074 423198763 659913072 824296325 35849509 189007123 272490103 916086680 298132690 790058699 966903301 978775314 279816102 443545382 474245500 480294065 615425277 914507688 229875791 373409717 234437856 282915274 77945756 652965140 75418924 900572111 635327327 742894327 171082159 356096642 761025583 970458631 111826293 463036912 588559859 919323965 112866446 726578425 123113280 228422544 368560952 640569514 482373108 938951048 634208006 844494533 495065816 917827583 329924006 487759508 332021255 651272424 534287220 943346079 43090368 546166063 275380306 757618159 41377171 921042126 61134365 569601163 685992272 778004849 216151898 838763278 150739700 362160340 184346921 207804832 548619932 863145474 194667996 718420672 55065000 671114473 520535740 606570209 111030866 891154060 199250135 589742654 133531946 917834116 896888563 947810093 520237478 625746180 92876964 536961356 44416372 674522903 120630481 379238432 412310275 798163971 312105807 378514623 202500161 628595863 960380743 977585386 35688139 325422279 691321728 799610418 476041453 960037607 170562222 240633810 10418413 403894938 85988331 981047765 34839957 237895373 611866873 990033739 485164041 767809202 126490409 691357110 730494009 810378180 724885529 990370762 86544682 726540473 579756295 902077465 24446426 789358622 478307437 494999873 286166778 776159199 315869091 795502510 211639583 651969614 216419305 441856094 323631115 329797621 211863025 641739515 279878415 438100234 38991541 668704301 602501307 703053093 113565163 280553861 75382989 982699500 590597399 829677978 237159690 673552695 323891065 475078066 366005070 623953280 12492325 770472522 302384667 943885324 16924065 630721063 679791070 683774665 567136410 753334884 178088521 789299519 216845329 722493229 277370017 560052589 480526489 852555578 634454252 830927527 213964761 547471337 418813856 419792299 363333315 989412004 205510939 626747716 208539458 717686697 173150597 730890992 4339570 766382992 294500591 694219809 431603329 927150974 404795580 560054092 231617327 839598421 251914110 336150984 758902088 901897936 114901993 920877854 32619326 932170279 176845997 289631278 222158693 766436331 751305398 884463824 274945177 637974731 457149819 863383648 141664858 632486259 157850747 731768233 17398440 836964431 599042551 769548161 878846394 985854242 246576032 556929536 564899077 865925354 190364247 723558747 338059962 907315754 11299922 164779694 184781330 517021823 314785306 834476757 196111059 985683540 64454975 146037400 121605946 202369220 499533973 661040267 136416340 816580687 348815471 687707738 3779909 161075527 33139208 362827050 728982001 977960728 208290887 749602604 226771101 746585838 309765468 956361544 104302146 630329383 92705525 735529980 188432401 263218088 202018408 530739862 579913827 775100015 61097627 411564918 510911214 921004812 447466767 471660552 57335000 442030447 71197704 419537143 541417137 875516196 904748609 942719726 105860210 350007322 697031363 886284791 368298326 912155385 258951033 351009705 41887587 986993859 45507131 867234866 45741965 692836346 66892589 113962178 296155427 515463567 596417030 756003848 263734129 673272799 414003347 840760082 2398406 683441890 315793822 693308309 316644459 835775563 655869274 776870445 255378189 652000440 662934876 920361996 160146631 988772833 427319579 945930437 83303480 945940145 40060136 790971325 377439717 698528579 516502986 672208605 39905478 845577953 6328797 173110878 130911375 454420785 596202894 869453534 344270063 867560541 35103448 928289303 155750307 678308626 331387847 707998925 240764840 258450225 299372757 737341392 28067096 203369211 40466322 955081569 236705016 937138851 343788858 835318050 128456246 447428550 115801554 777338442 297289778 561990605 580904061 979446297 324097847 737221698 88934642 157566197 199629229 842655532 338218052 710643267 288171177 522442430 540025727 640365714 265132047 465378200 512948598 814871809 333977949 641635215 147996119 777198873 544079706 704288284 506059270 740597489 425762971 495448268 269399950 532365650 16593080 711352075 121657770 160189057 911414577 939586356 37728989 861812547 147284488 195220689 703611334 804271173 224226542 672778354 291250676 791146003 7033301 9449738 52908064 82042020 544094871 756162685 663084708 705163289 397858135 414625781 129960679 497908394 8837792 92665919 187382202 577452772 198067478 876034487 326567965 470469168 510804651 978600525 392108459 491800081 25915025 248467944 13718732 135823250 199189285 711985883 754288783 893833109 472787861 861857245 159463075 731170846 55490742 835454144 196036201 563537460 248816067 791191011 168159528 396117135 124305133 245415779 51611787 456223384 459312546 665083139 243915294 600161788 47454083 596582125 712769493 880261591 232306005 318763577 330743647 667385466 310383635 854822973 244660150 393148035 586294651 846574624 411440218 539877189 191990790 542796358 33473417 365884430 476969305 909418116 295892138 657492387 443996392 890945915 385551510 975265722 322691028 364937755 329261224 957262222 358715875 651535548 124486977 560202385 564331744 912990134 11741675 583435393 374111619 472726470 704103290 755640279 225673348 596818921 192290901 364716750 652812191 913411239 28547550 214802330 119428624 437303892 31164512 289755709 333443680 690251001 185993016 659016734 9056031 626962704 15600260 352142270 403214910 580444769 414889309 434875902 624233939 889543381 299231196 353455435 690181329 746278531 384988591 815566940 312067529 561290010 353019195 487489518 103948368 858413473 36016629 238510235 337472574 756206879 837124507 927795340 420939051 961493699 386775283 576801584 904134596 946208307 113741288 355619892 67839675 379382209 238836684 474870443 610439715 832279740 921263047 937736776 136970589 198201765 685166619 811023050 251112747 440728435 141405106 887934049 563272367 733890799 616570283 705380152 55114732 417686050 505648325 611623853 104383133 582892875 85974362 903489136 32345401 901785918 311770937 715525410 170769703 787562239 496184937 634821792 217953021 907749620 96934928 188740920 213358705 278274645 765001227 923237449 389309095 922904411 356456845 796858721 171404560 464797045 244196443 375018299 3141879 546264320 491713597 818343149 166638163 811386390 99798970 972512485 666080488 698258862 546507983 749484053 627275975 800406019 330555636 541353174 351546713 387578374 223942236 283364317 737693132 936833034 173785049 500053872 392913962 402087045 55796832 374693759 413658240 965253837 436049397 784515612 388256657 906498094 722296940 995324321 52301256 157071594 101484216 721668857 90342584 485177457 267563769 904908566 708401019 742183551 462236792 970672420 743745103 776643413 263884722 879484415 155403251 843733274 513425528 694367795 323648471 771088539 104084826 976574586 22307066 597111472 210808286 564376015 410290114 956505042 637269353 731559251 669968660 675944707 85876197 681736933 156622458 422871304 183623460 859887378 89401504 520873941 415668089 793585244 108961600 345388739 578687723 986518117 44561924 871958419 788020524 946503948 74594660 762512616 60228417 81203287 309611659 929824065 687233393 729197039 319169399 896001689 235162838 317710225 354987571 415918879 395319744 866372601 97378789 939945840 335343352 874445254 678728880 862827029 152390815 617826611 382115903 575646272 7058164 456485891 181464145 910144212 48441764 985752314 321220770 332419633 504011410 850707498 19291669 823676367 921262641 927492145 618568850 641660427 455401628 963719715 432808631 499254170 562781403 909550719 728728527 879347676 370367312 532831228 507302149 951602624 299790180 418034538 766997636 939376095 586266987 600013757 238423166 810713351 400253424 471615525 337452410 765168148 34059500 135451422 500690543 556159178 116949325 548598775 17023568 94242431 47363742 791984813 838351576 962098932 314086704 804108712 169957024 949733794 213630502 682740113 197632087 421089775 513162479 617517839 126144405 242879464 151594971 257521258 262851913 703542442 15331052 58773055 189377338 462039458 43950 611351720 570967508 808043930 199286359 321917843 326348756 594338128 172413863 992148689 143602090 439079457 927806393 965026843 418347048 708899058 694983802 861889622 373984331 807006662 862201552 960805364 399838857 475855497 689281055 709760721 222340248 692738368 49329916 634144680 371242731 637012731 362868833 708610057 134642170 438158585 75100350 347930025 562527858 788526918 168157824 760960205 539483125 664346464 222691593 500986618 183521602 849064002 169855231 581255578 228306799 360531036 103317225 869635782 129880993 754607828 72311720 347405366 8060312 146206004 219412587 886399818 461923463 929328165 248163107 807793238 212105181 885427088 103809610 913774941 144381263 876652376 175896504 854125057 310740710 563488374 51683958 536782587 338574637 759997130 87951934 470390495 217339019 229664498 368742359 742365086 503699177 936375696 488057015 976315962 307824367 476318440 726994397 873396475 31133791 425892183 151118667 700491596 82923964 758762115 530992273 673509227 179101983 311040270 84492236 679689384 325108549 877306129 604136004 752617394 124317019 818737462 419703546 703950458 495118146 787055244 379619068 693268652 103471675 140812322 409607457 758311907 578941668 721627946 531790884 627416212 256818019 642379508 204169581 284625940 64428055 205150313 108282410 593910138 417184038 981428433 588956100 901764754 250090453 470678200 208233868 446317124 331400935 361952802 785826531 790148221 42708632 685354912 593850747 719740502 54132478 74649878 468055862 700038094 134120896 937557264 475924559 654187817 375224748 674125434 317613515 686544595 312922154 796021287 521242858 620398511 281517233 991116270 80289316 481185425 610647715 799489113 708884715 751140215 515622103 845344221 217192342 936510112 430604047 745593977 819358643 935220425 287104748 534386770 662469061 843516354 260169639 554664522 363975525 489275275 449296272 773990960 88562809 840765136 336765551 991113220 13552064 192969639 51669612 772694872 806997115 850186163 197329748 921688151 10394817 37274225 582922793 912001767 384256696 623372298 107476616 404688329 242993088 483653776 158901924 597046947 355640941 993184902 72041160 782789109 28952566 139911093 809140842 966137973 704816933 992573671 536402657 897357461 87714786 877518338 529539525 554984992 549401244 953711417 758179658 822569953 128162353 530481574 365562420 573514666 257707999 565604756 408591220 481000569 744106629 826810588 553441449 559839571 174028126 347144184 754939265 958386435 806158242 843175397 38716780 231024276 167447298 906632368 545914999 791628116 383174882 553757872 718090138 880993100 124291503 521559472 343771511 510693888 438187934 691097492 283389723 705783172 852543334 917422667 665417990 826038206 2930437 718571070 590913451 621240243 529283844 873754197 27059063 469995924 480248111 510338108 14156034 696307081 134821762 863012461 59425358 338801814 230531409 726102437 936383338 937363043 95098113 969864739 84821427 130477237 477486651 715171522 595770550 857783184 135644425 965093740 365602812 631905776 9845287 74638398 524266238 598247813 269618558 889555056 124520131 959214201 126731161 813185444 128678644 228311139 276551741 996714056 483825389 722880217 197974298 982797783 500028767 527877128 87283390 621247853 53459020 561865176 875510184 885361915 35942427 655967324 828813383 977246412 36279364 70722228 107578615 498964235 835766415 956115141 484020968 519344331 257899365 459952551 435182624 708582645 457376043 585873976 309497943 652327218 32426130 615400035 326746355 850466122 419958953 862071074 57250719 340816963 669934547 927082222 665184494 692119356 754216581 860100127 706626927 849492019 85968045 766001261 471096621 561634921 349690243 531828066 412670132 675365791 160001332 821882222 149072525 628121291 315904105 740487976 96526044 681763110 196649093 910003003 445477269 577188534 296298466 540819957 253792896 476544252 626252812 889176517 180234367 681223861 114441344 962516070 90216180 749715879 81522693 667870429 931813547 984002011 57467476 860411316 350896700 817911975 197945200 847791049 203088568 269047491 360449986 613020903 113932528 966223517 289248322 711762686 69328284 201335108 301711335 375981449 160737292 473621154 91390184 479022652 48990026 632035485 232247470 652444015 516744869 613036520 368974197 863743925 777040508 984087389 59591160 607508256 703433565 980970825 2267610 976703266 402297960 744661432 36545887 260102667 496852356 516738354 807118015 914573558 703605400 842192910 257189285 637800305 441644679 780091392 393860467 527752338 270389245 571512888 20856899 358094058 196513953 468164729 577506230 599683631 74626078 510404413 254342431 986734522 18735723 250564071 442310851 619985817 38909100 448940387 301172489 578559016 80068796 987123507 635596156 661787515 885753075 952290107 31286372 58654796 793710064 857563603 598190826 729864249 509173371 821364295 537422578 773657926 8654220 304678701 737958689 943851079 428335983 464762458 817098335 932231411 7453530 27366102 443539836 965322996 576811660 960871182 156349936 213386247 259117860 968754586 502500066 929864317 733211672 796207753 357016758 527602897 491501593 671154955 832017738 866932371 62433846 870637517 30184301 230105114 423164171 712502084 205537784 600252830 93794961 933951479 182621995 744549102 6727998 941560364 552206199 634701604 735536269 793825140 50957535 318242167 592998843 846301867 911301924 929802346 445661169 807547546 48049447 750226909 19876985 349572025 51340587 797132837 195634016 549242585 394986901 966882535 172132973 456396209 61722924 966408855 581850759 702218701 296579706 906782505 540345185 695112003 530701152 792873511 166483698 576547417 223165981 655132007 778776139 983092429 552981206 786938601 115590787 536413566 306349543 918791194 51496937 971488915 565431759 579848039 402806598 690576632 206961958 480465460 22139682 937936641 110851493 176911305 8915916 248395669 357047881 789803491 62683151 700557352 41496537 213234465 40614611 176182781 235246130 676284066 439241512 730902810 104163919 647565028 16392143 834937997 885163434 941777514 484917571 666063822 891930794 907948747 565971178 849304269 237486644 996724573 503624320 965119165 149056180 890077483 420333965 799892465 53563052 598559956 256137880 411649943 38108845 193458536 152790208 786730695 523555956 745213912 240934216 315928518 42932225 110397479 211250042 514207182 574379373 673071542 120058563 620867037 112816428 718260528 330136254 600871157 215339998 936179056 263387883 768031863 22118494 788721246 7400656 326797781 364102131 598541983 485083733 546310010 160149674 508543842 30964642 111897685 16191017 150510054 323461269 471011855 115961932 839122845 3997234 673228642 2820413 426302650 540946619 788688843 374544094 528838287 345376889 510820521 10209877 292615881 180702088 913230798 248677892 344583139 232503658 320663832 135736082 495224332 673600557 757615897 83410918 377295303 231016510 973568485 157696949 380683876 521533035 735312971 102134231 690778092 274998839 742594532 642252330 855376695 2075411 226948869 767148705 805313439 265193110 623354094 241133339 945870042 377273144 511177491 487108584 588058010 515117080 903695832 288037194 713124455 86317857 167797108 152496143 787252647 237458284 657006276 385600580 619745312 169220154 764946134 382955720 920488831 174043516 848748678 219327027 740826595 458749502 973246963 192529045 798689699 383268492 548908022 889212560 891729799 565574337 612417582 235853575 401869336 21220305 616830637 286117620 659020226 149892240 244699565 513393824 964305755 27043167 947446602 416148299 449834379 93655783 936863630 464704 155554208 418460048 446697852 584292303 919776977 120648435 570039696 126110055 290789944 381820945 994618083 638456780 794615972 263885606 888307557 161900082 579129481 389455308 709194483 480451865 498109950 460883191 549418507 211555871 367373556 551000326 645651072 707261041 904522091 79359391 366620905 131258613 983023476 855437581 911476340 18064988 211242137 265991044 635071442 8065654 814144293 51325560 196702651 451202740 794804734 544058336 923703224 297760018 452198532 165711210 321019153 451140587 654228412 373451620 604648749 531136321 961509181 158551128 314709416 162984035 622643302 429292659 441671677 317736305 581422596 181897271 758172520 377065273 995989775 560051228 948570177 487254845 536406345 504736291 992076512 150126362 626972781 58404575 478024412 385243067 722878349 765084679 931887919 925330925 967240633 745234468 777780921 54029340 216418705 553556609 556903451 323684291 796875376 454337472 821498941 707884387 998874750 834983812 938002993 116821211 586476543 94368443 780684052 308175803 371781247 583620699 738864989 589913516 903154420 893006935 978530480 627255646 972858764 75910595 801893862 131478812 715241128 300774140 318719618 341797302 521088198 546124752 731246516 105594851 980167854 546594706 825019780 519056717 575447830 277445242 676712940 471361935 887915045 107580645 795239365 88068890 779290520 174539301 664288412 536696604 589215468 38967618 252003673 647232640 832447028 192621737 909222110 538970621 774057507 15043104 488275110 747034240 938904979 358716534 866947067 402678719 809343530 210788962 799523767 308340709 991614427 62541709 346205328 375748969 944798919 198155808 406800842 624537768 943517766 579045434 607433579 242499236 669948192 230657855 721548138 433188212 481734768 21781084 742452029 15592421 729462285 385864390 784351178 52430393 759529743 177383902 634252207 780440914 875069522 739296655 767156742 774139818 855870741 195947997 333792967 207275278 254550874 498620892 732056434 784837425 930337399 329769775 973459735 350104671 433951773 410403637 693156806 453769520 511662490 663760919 791853334 642045176 745603048 425702089 839971748 588941033 772617408 37017566 631557641 184005790 489333261 469790783 755021018 282300997 289751881 108877868 366018144 65636295 578823123 505466541 697917588 40102196 454005104 45621664 745390425 363123042 786367765 85375256 929177350 518735106 544817160 145879421 200574455 424656394 964985800 166152930 951731169 730751867 795537791 109218796 641972165 87981501 499378355 277300496 783770510 74148435 252615382 266998739 544863332 42779957 691794104 132663029 723743723 93812012 387243746 145654038 433587993 223817983 403336420 615418288 696307161 626728626 976157588 142806067 665975893 223198009 912296878 360206206 426216642 224852307 717847583 94267819 564028286 427513941 583245960 185481140 767374850 619496489 935220801 547867309 954539601 798430383 865432311 367420043 614173762 445446132 709232262 147130047 697017101 634885719 800121643 170336108 242249958 475999879 717470004 411973885 885320561 209567404 614485186 269719861 431546287 678663637 734570467 817648003 865125073 60113109 168492810 272188435 500969981 463902488 768507205 72012 716481135 114858303 633696067 337535778 572720582 486657435 956217889 690621171 792965082 50832420 334994649 147349770 937739816 224163225 331736671 315904264 324761295 491424767 788832111 833522168 947324735 51758294 786321775 608890626 786037142 87190598 554748863 429513890 747078934 583942516 969240847 96803490 709596240 218526855 699395496 183622409 301916726 170729687 654083119 166835961 516963560 751852822 914643900 354696473 822900173 608176133 758856200