8096 999999981
434952483 64401881 315449833 455676329 243824451 126214007 1565974 297454534 22128684 19201671 564655895 635422148 117787502 719385177 761458440 58244738 981500301 166601223 885745564 382891688 23650810 309873729 747385791 549142221 74825857 62493970 638589478 541071298 168264612 63400957 660584023 490441658 709794113 275041763 138257325 98953172 584626276 457977677 885697372 581460833 551259550 58206489 652169974 850042138 455120604 501470338 581944996 627031509 428392275 19604142 736118261 313203200 702689677 323417980 61536715 363016448 372310234 886952806 356615932 325068087 196123255 374986835 544769277 364849775 715656131 114084673 644668205 529566644 896491476 599704092 472906823 806700142 872787635 875237748 732609656 447406949 44566720 999794296 626051304 217045785 271787818 292378369 609217231 755743909 574123259 652701885 674988242 983121919 937905317 173550226 905699615 871806951 246946969 438141585 122462191 222939503 732370291 115560696 253492886 840653928 705775861 492389407 363231301 290224003 248190565 166777706 909389458 494282290 76449297 536197592 558272281 770816892 487747947 869816175 387448785 855035338 804646625 396426582 76894647 668759981 154523484 634772735 960860848 151835633 581050238 131110866 17908007 246450588 374976645 291963533 73576 15386089 622797022 558420666 767555337 719050459 550272881 140088525 392120473 18171567 158133286 423397186 384081732 795436926 615062391 719510931 702988380 576787341 291764739 23389343 406272674 80471103 693269229 925888348 607283734 578160108 901485823 604559077 589180903 190997657 873501676 545364754 670936839 770441978 433235960 470624244 131257358 999679354 577856600 851273974 208159479 117654202 19900546 672048732 228143510 386258185 616739504 456083954 366154491 115272676 3853033 652563280 588271133 621702485 828132267 112440859 361788919 176829318 847984983 748826650 261134545 702994101 626594073 918068052 745525013 545571359 52503286 647233720 498315626 103045723 460103472 527096845 289603894 998726084 306962592 525600362 512041338 608607262 231047325 671762223 422774768 666715651 60631751 762260737 666375562 874157820 950087903 271677829 33557785 757845120 374914646 886822748 904224438 664573209 924407800 488856635 518643090 864842498 5396632 116337355 554585794 402044497 468438890 363828862 263225262 955522852 871594489 937539815 996813868 190010293 319572202 104580836 694495907 420260570 555176633 271265365 380424978 209061703 917312155 673545316 81384322 239341218 389843012 261414683 648453434 991212660 934612250 13070378 28902123 9606751 736948211 329260280 712001870 420879931 661495441 463833015 263457604 861843607 413700261 568826379 155606773 569377227 250908596 67852016 592253675 594035738 625663003 516585511 738464823 373653177 171399816 885551780 398227513 101438245 415509118 625911766 101979082 666183450 674246995 572577249 257287572 316766730 297916139 853192289 449538123 383731349 773702086 518809030 49458337 659562063 701730163 641815282 373762262 601933522 70627222 48282366 709494982 621771423 457040992 549046922 267932353 863158915 371937304 460134950 532559872 189380803 704537408 56569524 57729455 278293231 506044533 384488650 436400433 419475568 57588499 154057404 272423076 835477109 543193441 190658465 524955865 650912572 527228397 489519569 682017402 138144479 769353156 197639686 866643755 50221584 484181054 948954010 579950463 808795641 646432196 836688476 225596993 1628556 341059448 945464389 376904831 650192505 773978656 549546325 376333537 393237143 680276957 114684854 427140493 941081595 274876670 370614755 411569159 266908368 126692968 417633853 622771930 189178953 645556679 194109403 843625753 551262609 545096284 264589596 75496709 543412073 461422666 348493363 234685905 627398320 246514467 259107725 39054517 7073512 22172515 399769019 309298220 169388535 789793385 571698022 558925895 978334996 477253985 512060829 423091247 821079192 248672290 495834286 594770951 613753257 791163585 470663853 112561671 469209160 682196693 381740327 465855814 59252268 868317733 665754639 286050224 90243033 442333422 420883040 135144541 530442797 103777428 217580850 657805003 752576119 930563119 40673109 864965497 360241271 204318266 565673732 200593923 796626183 223292737 521112468 860011027 101659709 262769239 359894386 647138797 707173484 531438543 773274005 585183355 135119812 757389486 376454766 922423299 303777498 270569868 43882397 48983619 493557763 232156784 602856209 814176168 440695879 950467645 182612293 814055812 251536255 259719378 404887899 246464863 238003583 561698594 49184113 173243871 548983114 405342297 630611616 680097097 19033898 204483348 294203218 900814052 564283319 543063143 934312194 619308112 764328412 811705086 357737904 551545945 959366660 102733284 800524407 718199358 818582703 997540595 904154879 156878232 269273324 499376750 844912482 468112165 19140201 42920789 241860982 304085979 389619772 300038456 749873927 967909015 729404830 927136383 760079909 342362968 588332194 609143514 876890457 691572339 438189643 472920439 971160965 975156905 146084661 979388871 212761725 619084022 936806961 156949443 333522156 370710678 240652360 933121017 646503606 185680967 861412115 233337883 504075861 717010083 393619804 235386342 131512671 551976932 888410150 988840516 165884779 580102350 367182219 572518276 428437920 326315458 796562832 901629024 259752334 382663754 683678725 483327798 201395977 914415088 306612272 583934550 626170920 435278452 2814757 182184119 582741230 206173339 871838546 211367565 705682630 957871819 91132413 81928788 914054 822356350 728043788 539956055 441938528 775401862 890940286 765278100 40124706 884322667 831657245 242624013 951551057 504408926 177959886 72830949 162597370 348673606 796192962 410742626 739556818 995956882 656835462 753763306 673545344 100458398 392403922 395608286 818786598 518358261 945196021 578005430 741157387 86046776 192971540 388841118 674125731 533392054 152245353 416457607 350217201 305777537 69624058 196810204 999899342 831436259 707315893 873789762 695457384 538918253 302246578 830177573 183476682 765769774 255596956 386696625 459659992 159843529 400376354 555113603 42934682 915501963 579653599 540430793 473176966 597921904 976650361 129945008 922667180 95949032 225622328 572881319 457234061 376330760 914117020 675454761 92352732 929297076 899170083 579016852 930414527 664393621 344481067 580891508 319579951 489848314 584482626 492414330 674352961 162619762 77499565 930219271 375855479 604038558 228184969 923605012 226332170 232621697 185190672 673048692 843757238 412168157 392247736 206304174 545283174 141188560 729149644 514086211 950989080 870975532 382442633 113931655 916606612 447133870 807242964 58660376 200578332 214458376 244702154 579482956 620534801 825966706 713193016 990713449 892106954 157410065 344101300 720413939 394441244 461657581 102401802 157310166 150286986 244499070 206162320 581201349 469341234 841204584 56181275 85580104 823657327 418247978 166918467 984555220 346841698 799536013 979558827 893778521 65364491 951130449 48024056 759217807 619436221 308126853 427491015 201372744 241727351 796098296 938810255 584697044 27396501 669791834 891056698 345888420 526165189 965990066 652700183 322269701 578660631 107557454 391680749 998713952 669002268 257717215 430854881 485977743 332498439 404012258 496913408 553821525 634485525 696667155 582004911 658358752 712435918 105668533 280828981 736546495 928522057 472122161 4756818 225751191 144700439 712010541 952319096 553270759 805749305 317342757 70272448 379481574 793952610 724848446 789676403 188743486 218163737 925107120 218373053 70556299 756335229 243011030 553234333 390728815 195652670 937859162 359129485 99688775 891711574 633888775 287261389 871157689 318037051 926306427 785641276 551894823 194664359 73091248 926778407 514797689 433551074 250693569 303468650 474056576 642229821 422734603 171558363 697673669 305929044 902101023 370811028 313797575 659972222 87885002 506597957 754335730 425315711 32735702 348773775 587873604 175639834 241722116 589586131 925702392 373341056 165301558 275505294 117099924 56943878 556557989 778688260 635096875 124111800 723511956 168659731 811095608 197199582 761486094 364749002 501909367 848576807 77180922 245045275 242164582 74739210 296794820 71979171 15204431 462947032 369180862 842451724 988717820 310479600 783776075 283154362 414135845 320655892 676965868 414812148 212535907 785975191 964450452 688028882 847717684 879960756 106795341 383598481 941992350 200113316 766683826 63814408 740751981 596095476 278204426 342565895 719801769 588308790 594206076 539135446 870202780 158196181 478189027 141173873 929581670 69346185 585713964 417886166 668913654 128029758 363179120 100900656 310748919 115379290 911848111 464619501 801182884 958966735 404164474 370591956 23955661 477843240 547078629 364414882 562210149 169400456 103122342 659969332 387834605 100097246 785304249 426207539 921099007 753854806 513995442 671370719 409197816 671339264 13961124 679761549 100498743 955405451 616478527 971432688 10633165 361525389 834840404 233585080 461360049 817489216 813511593 898779129 911682603 846863916 105169715 592781279 331735041 880704902 719200527 577247438 184783579 814928431 844153634 351469103 300660006 335213256 514893191 766246588 522294633 814673523 177351917 387149517 417453330 165533851 491231376 254574816 859058058 26294188 303777459 905046128 240232503 574915527 577266417 585275159 312720941 432855924 369220668 196828155 791750568 885962619 24070954 125653302 40505015 263724749 735670560 746944743 492743115 663928836 945233881 962243155 707081855 709647820 853370889 672553614 138327022 308814551 756683057 361892143 874674496 859907783 350279884 105623227 265292983 423460199 671603118 755535391 206335140 25395308 559584757 335155353 430903886 132618166 217182399 823247707 585256508 211038854 916981919 876672713 56245162 554652815 906000048 811208817 531209598 857635533 859903969 949965351 499123425 470924915 895547653 482257387 115908466 313043833 982244895 421351671 485292343 762446493 835154212 281040472 565903403 15850623 471335105 958311538 268812169 636146503 414954282 821491129 438227395 229460656 364467065 624439584 430918799 185225544 342786079 466444398 469661567 337272799 63637226 251788481 187449563 720116340 549792685 946100658 988624410 834487856 574311420 90270485 403140841 315904361 520150705 313167011 219945036 321957605 754374411 806815812 277507107 192045582 618020244 394126664 994270380 434636226 275675881 283532074 588633267 129639800 26301460 440123099 541430808 631295403 199502490 290743852 986191022 319612569 909640304 690162086 893595636 34786122 111982948 963232841 36083381 892882864 732303936 224303284 565923321 935494503 132686025 799261504 787220554 502621165 309783283 800511765 58282306 286828454 249746561 52644063 86430931 434183654 561650229 317750723 780530239 622963313 39011691 274143976 286668099 895896063 300985733 674971684 61904359 764397003 625174912 137213006 82028964 894221054 60918524 575503118 907286282 229387096 989751870 977777687 852936111 419315403 662648615 761198300 538145470 265469689 347467306 993160432 162157880 385694893 862861278 219583508 569903180 412856043 286646300 351825825 828463747 839125420 842953466 256496962 624457209 901938828 174404786 413325262 506727643 817299454 792392574 997187455 631647009 78555465 375161804 608461454 531148322 743585125 351307838 188969990 235314164 967761444 189260626 260327775 771785655 498178284 426818586 931045971 685771552 634737824 251060787 147877605 531366045 867890122 871702598 498463957 756653956 531097880 750789651 943750609 37063537 551498766 239770412 274249921 753455772 21498207 940551177 93886405 337690020 952445859 964930654 400330635 939035919 667804737 267635092 13046526 749358449 495931705 675420375 978239285 952229401 580006375 67198600 86364995 249095944 85615753 283160317 257024439 919071962 242075738 72487529 682393199 481958424 624492811 671633877 746633220 561883943 18897991 880049570 453734919 673724073 434388576 569250176 897719627 908791935 212021116 388400728 239183105 883590175 163043248 272456077 481241848 536669257 991597249 429634994 519368829 329677873 905531480 753968455 579739608 401242051 166008212 111936826 739559654 18012538 574572966 311666477 49017109 151149194 252633734 895501599 372759643 665148954 566757036 640762904 140624540 344063961 15610594 772955904 392835795 804920413 766393008 417819433 869879332 385568012 812178852 263473192 963394231 517257134 885425036 223426235 444759239 69762336 250189281 31391197 997389951 793148721 101198577 381854042 285965583 868423129 859346800 434419477 95770152 19553224 581642725 598608294 987902150 52302171 997422383 389864214 992758355 215040083 435739792 580297041 15784062 913971901 957738087 272085770 274510366 509556972 245347785 687055497 77808135 557918935 10647471 567818306 809932967 612932955 198630091 659870110 709223124 619758795 344098682 414048076 686971183 513503447 40361298 111103084 675245923 539819196 254150630 55081220 646174179 354034587 327242715 381232040 118104378 856849906 449450631 431598805 303135919 882496020 136476691 744623938 604560589 8550888 254526122 570691257 283313846 919611942 928606599 445472873 273685275 925448399 511806647 453180409 273097559 965785799 183931155 26554128 563210800 704946290 136436807 666940028 133324953 795897275 786869956 906747641 804714236 261074156 405405010 864728709 176690851 964597501 95683145 516062999 766298938 443010717 407632254 46219561 427813201 884048568 547299007 603207345 902276200 173200167 37872528 239584519 168271492 746580240 387263399 940105035 457457035 584329191 697683576 293736451 468352794 529061276 478891600 123642650 591107406 422819214 49428580 131352282 786358064 710729953 612166616 683404161 297742951 78519065 321314485 560078982 25600932 188456970 158452295 71820505 707781867 959308778 255784523 580766631 483005643 131415488 274986201 147525472 90029276 312875161 268234228 731017392 759539063 163212366 72875879 982752044 586499307 370000477 462072736 860044151 987635829 925639512 548061291 190522133 187924894 561226406 888895511 905907318 968426546 481012545 276357486 718650473 637390648 264221368 377791114 611862629 596024401 780424757 737267996 296828033 151209125 6050091 798414859 362756004 892369342 153334170 56435743 816654308 951993934 486282200 849301086 149512609 920001521 55108340 872326792 815032822 357283608 673104708 107494591 5414468 322787827 549622163 906861106 162998527 688260442 481576352 810788227 716797956 466462911 777748436 96781642 403946560 248994543 135308905 395800173 485720434 893143510 259022529 661824852 262014119 85063436 377483557 333207332 428200485 308073944 393574684 692322780 397917275 540787466 647008523 21649540 248060494 533730452 392794627 696570944 571952957 651748731 284286425 759590597 105574403 190741209 969944888 338480944 829366912 253484165 157685836 526735356 79101234 248733463 56654499 249699074 768288969 154987047 833916998 643528487 663644929 450632722 970059034 155890879 756134407 825930931 234833409 411289801 530089788 657926546 830501182 246354118 735458178 211204551 370800483 16001601 437125186 464545026 147132679 439456181 970966743 442245264 96944045 236372496 633031284 391752735 348133750 593862020 901519962 612589049 976419171 932433780 829771571 141677948 796841446 385690379 890753540 270323644 111148371 924664879 635751713 955357258 294686292 838883901 690013295 484310460 954655225 494378085 488403763 212843793 322771460 614948317 309093145 489660905 90218137 728522076 681151084 689214149 391861624 94691267 742605645 255030791 413672452 657932083 369853263 171067097 366834770 878413250 750643022 221314334 686403463 493032442 307098753 56111857 683511419 970174234 873179358 653912744 856617311 746688260 431073453 541482870 536566864 26715265 261518506 886060941 220047481 707535210 361634228 545586372 21496378 538045712 401941582 937949787 824467340 190027456 528488136 526649188 926790862 24856678 419826784 400856702 192404207 124899546 506735944 499644900 299292658 942875214 381618730 937093734 329812550 480046969 164599206 559845264 392120370 325099294 487624348 92418876 814354829 738381119 330504982 255580758 181683411 312244747 768279875 118475491 170402875 544728928 334350789 977776357 986789205 64190233 605886845 94058826 531097554 109261133 997969987 17125806 634063446 55969273 623591520 994055012 184659563 311214117 239419172 407319769 653439534 981965002 477213246 612104074 323477833 616750707 779721427 538160261 357302200 877627630 84993652 998075430 368713594 784085050 35980671 137809086 224720012 613782800 400693982 429950569 811630551 972932089 664613746 881899033 398504245 643334059 540395217 795554889 663509895 995337695 806760467 794276113 163833334 125028854 894321598 659390046 363370566 656964903 746544725 646774943 338746910 989168181 512203956 253646272 612410264 555794034 450128239 636204270 602093058 984726789 415602508 13645425 795386282 727096772 360588839 550424721 857740518 406536163 709078964 32500994 805022737 56296902 862209835 670132751 945500932 104773324 244486957 897345934 78532879 915268747 860717241 890092791 826233682 597856947 933142432 680163912 420008605 916997958 465016609 995373911 844554830 42763440 273585477 120580407 417222085 153163708 233082783 41427660 725503810 938640257 345737239 392156964 298097008 574620686 871427504 599861971 74344095 966148188 961842323 888364738 459100529 997703577 518448893 302024807 561929126 893051223 314009381 424016748 859210815 668733875 86491191 249955456 710181895 893764605 747493915 179324603 264752098 149880261 932360223 242941719 845907919 617307103 137153910 305345942 904990294 791750278 746003615 479777841 3341884 771341102 237362773 248988912 398519201 114862747 313967096 201011797 526177858 928460855 836714659 263085769 917340877 47174649 170124108 485994716 618430021 142635329 150655150 713746057 50925540 74276870 730085300 705414644 228003992 344658312 552614976 182694075 795726981 514131308 415567296 503129454 717963102 834887808 385048162 733187301 904906456 709511747 408066509 560305374 371910416 435728642 692801306 236147465 437162642 130261390 61524666 714640584 542085622 734194376 379335154 932589183 167707237 178715208 246508348 680906176 310896950 85307346 356410322 712233080 256950945 514232266 61618559 447192394 156744422 784421113 662787006 245827653 251504931 48337134 428319524 824822762 879026999 482996609 511204762 209329465 810312623 932674955 937291686 775962258 771070982 930452039 786836226 454338447 674151596 692930863 147154678 786451711 171067494 17055938 49206082 216189927 64890243 682204793 525608880 364948989 823717648 399879647 982281347 971232255 888243415 573794845 339751796 496666567 92566247 72086193 703931100 355312307 704322837 272866735 612757909 733867384 620501196 923247182 65024883 690542992 312554705 688638290 860317969 217709727 907614361 674402763 110539404 400490104 568458317 283787313 487148395 877944876 107087166 250866231 433159849 156188523 990142758 107813276 58874966 29041058 302000225 825703542 793951282 360000450 726205922 238491605 982321248 860255036 788628621 985786498 368476085 299489041 743666540 866132313 416362926 760474126 334393046 725831321 811541883 60045675 542984115 153511027 937574112 351800323 935647125 821280287 831179453 159970737 629961196 672430285 561984986 819893412 601683272 579921545 316561582 132704358 564174927 904682132 446059775 734999057 375725588 962414725 619565671 500542364 252013204 54654360 862795764 803132547 504066961 79718864 234032313 161433803 451811405 326476068 385017969 824848063 259976461 166615605 56104549 179022839 491292883 173162360 35760978 121100948 815517720 531261349 51301988 93273227 340167504 751766853 11319913 915010435 903028555 91188936 635796809 342449856 137820509 325959061 534002929 640863012 784857279 129724331 385937992 133256669 123420200 210111984 731068060 236570130 266163307 258410099 890202586 422934738 330281996 920507051 854639040 377905906 171042527 95872763 242610756 612103377 662657384 96682449 853900985 177942338 632282104 65377430 167746732 159374555 494653892 643693403 497021709 72569013 257990400 289706766 72733157 743754729 337841223 429329467 859016735 56599277 577072842 936739651 687583605 670213616 741997759 828339907 250820626 691690437 622213528 984012508 891644255 173577890 973249068 258628292 987315262 769299801 119844673 909216099 964561348 102845743 425351386 211197428 766866510 860059893 896188898 803308335 766199619 86780981 910897635 656039420 37484451 124511854 142960923 661010695 811487319 633148985 178217148 872860252 920543229 806835779 178683702 628562377 492348388 593739819 27797878 182673420 534779042 557666070 741893020 789173615 350205060 390803738 715428980 151872226 725646562 558653265 118222154 697681880 421965550 523148505 509800470 461383645 834900578 645164102 562184201 455057111 115329292 536464391 948456885 769282357 784527938 702160963 406723619 260192678 766371076 92012082 756528486 782108005 578982621 671980133 610005778 413318146 529462956 245527771 586362569 244808549 732439270 618274951 675101646 63294914 877207428 903263769 522793383 482969505 116870019 324671597 181558480 980875293 176559798 827928340 825529710 914418206 83026837 690416539 273987469 28939743 320391041 93055222 468088397 687598780 880683772 723649775 251448721 477102573 57357717 130047431 154725280 207046224 8822611 716965220 30740397 182495808 249464023 259623984 700249683 867531922 586253720 227564485 767898953 334853591 283775816 482746738 715213677 930724295 503317048 146800798 117999155 180866308 64363455 406724001 496940600 250697708 260646114 946184509 771043455 576876440 324724974 764080522 645738047 708848378 172921707 599193358 920087400 663730748 839298481 752047816 794075000 118994732 146705653 54563220 982597275 64956099 418855245 245673313 128456078 904768689 854024127 548275673 79699777 898012023 61604680 551286533 812223807 625360443 443422390 422372273 420201875 437176358 321677415 181895981 319987785 341799 689183631 540488981 682697928 586033516 76818931 255719255 529813146 152659967 596035917 174554280 957173619 733260363 651867853 35939342 699336194 931676139 906209302 128977253 377158143 743552694 986899369 946092621 982723807 300360959 847607640 687924287 839878100 483480369 802027927 231207078 631394167 687653855 478970999 947960060 49329012 353515010 34293894 751766041 338303062 304337470 733525100 441586322 917591563 519702968 288791373 471731671 741066368 741839698 82710948 578708240 43644226 858382532 966997241 855305484 744073442 830203125 698265467 473305522 515448915 460279548 611788305 401445749 436742097 644663733 659371199 861962732 686218355 38502013 891546150 877216252 262338937 210926843 721699465 718348925 419248480 7960526 83984207 281258740 367233063 955332168 192900769 394209374 396481237 219104267 699628916 418458962 607195236 474962297 684875760 147000608 577680611 143086929 979807093 654141275 735055596 336397749 843724686 225590660 444856409 338467977 374740369 277698036 554367920 877593818 346483286 313231215 498073525 283326206 618614875 694933904 66651830 577052042 327381775 172511183 365421178 501136647 406424046 367500381 88654927 154214961 79146593 566944695 304387311 928758754 235525140 500704649 606482571 470368180 54120193 252035887 711271409 281256322 923656839 832572547 606438849 858408427 434288943 814778332 473115016 476981286 489792623 428762725 759866860 867736064 917352086 450157935 11069176 85484783 530444908 402894243 91197867 924686295 694308949 185376552 787920394 697236845 745851295 457616432 143317703 765096571 605924937 530299763 425269489 440220719 486190658 482693162 987606556 378822186 442878036 710680463 731577216 445374438 378789169 634459152 653467125 885763262 344187064 431436697 847562267 838418080 369625828 226754376 253499672 570981461 367605468 902627692 593641480 177767277 755351327 113766415 535505651 642733341 293286600 776083332 570353712 585094963 797550548 900912413 217137747 492094339 177551718 833229042 610909421 59548164 848614531 36095432 507984745 938363108 629969544 942148424 295358576 448448905 516400417 110325003 3898842 655844071 420118316 17813033 526329606 351437068 803975060 202683773 273496847 317887108 668253552 144741692 849837013 625954919 401321415 768720807 398270721 405066801 72510005 409587630 908800463 849662269 316768925 992669009 612455436 486628093 534954818 830368692 993751037 799195228 659058192 512291740 396828730 426690153 735850687 481329728 801133464 997656829 786715194 86529811 521895659 692130194 98544797 38102024 265944624 482043604 625774136 741950783 661032649 973993730 305586223 245023176 985113354 769492722 900676452 286894698 835107689 755691808 933111701 419720359 481656809 220261481 402809855 897602731 506850259 33010801 914192904 86951630 328176157 64874352 295456410 675616155 711493805 453784957 272815683 556003741 772391823 561211879 871804248 828913664 1424021 198093609 566977859 779623531 114926603 16352201 862949010 725438814 268755964 404863650 614360793 649343591 874611091 12715268 126502554 696375217 253891059 584007240 247663208 89535992 977564052 116992159 87482313 508207206 619863033 701962358 307679332 943737185 182266394 214273517 301672894 79278745 176226165 362568750 808196035 374840751 328941121 949120042 674524687 269133953 765647059 202124854 770510537 267492930 271667450 38859066 173977123 457384612 103370241 470566853 238071930 868232697 773349247 116273026 951483400 300068518 841708875 50147085 472693506 768701282 165350166 952315193 497878459 97788266 226957035 252672112 144485882 392478910 390270976 238608455 16684833 135921679 517785443 550063823 468626813 391798198 786190527 561905350 940829303 320131546 273337693 390712841 495334354 657706385 517467090 353993193 820133784 320971677 666864180 691010175 429665499 888768593 404963288 989365928 30385075 443174935 515230229 52700792 303584240 289068275 115936821 301663032 685274373 392580740 261528219 563149445 694263457 547716827 38951833 721884479 990160241 985070870 693050828 29422889 313010610 968787016 806933246 816131128 483400907 86728052 570069050 26477715 459167766 503283919 638586977 374044224 763115920 720751244 180746898 509029612 47773996 178777348 700531804 537713330 248048847 38711707 270445196 231336807 497967877 185549448 319815753 799917645 757771051 831613844 71313546 520878802 750397408 692702390 896741279 899182786 568191664 239498086 344434531 268494435 752883821 171474616 891024042 628900127 431792209 420687180 225859148 830456395 796607608 753058724 505740466 171977126 609375406 816721803 926130160 918625779 172577738 800171890 448424645 293122997 684063404 760238354 230588469 236952947 276479681 936119631 364988554 763425859 842765255 782859391 103901469 555904704 358399995 668528807 947263169 902683252 446960557 514206563 436730968 35782003 440311214 689806337 409985209 573826820 138122081 667161851 894224009 482113101 282053995 240854283 709571684 554423675 922197179 792685938 186258377 761997359 971158150 412291220 149259693 540105797 511027337 612133547 603250177 263699190 705813763 369474795 194155321 396939608 343635992 865894512 207182445 40804533 723943112 873725216 154295182 792415979 304950880 746868791 843553110 789901238 278567389 281703098 623053410 153508145 220523516 9275708 323089092 967724005 385897055 227220851 948117592 408020144 385564570 621801175 815769437 252985323 134202861 686927127 102440582 371703165 674986028 633495015 59621714 503701336 820480827 71666922 754905570 847162879 51442306 401163386 389956657 977007597 946131625 175203646 476750605 662402753 221838019 905596594 519738158 230763722 671650259 580845859 924659565 7626619 67835347 247021326 261704249 31447730 152531652 622107074 52031740 279278417 554039285 113718157 544772565 731808784 439318756 29050591 12109119 420832360 532650118 599937557 619866753 887575525 200308115 555174736 821483496 91186587 961552250 163034483 943139230 18104035 51205291 24930413 892651153 158706497 439705697 819273940 892914326 672969188 432972542 964677768 687522479 283611693 425447560 427162760 649962791 241645604 613579592 130500842 51941558 859584711 587184484 373166754 206295402 420431478 342244131 296512949 458816967 21325232 3043171 196009381 975061364 743548417 868811221 962087283 905432612 832556829 601101264 618414511 980389533 20709977 390390051 210954865 169338830 883131124 649170820 505957908 667066795 208081114 588014863 100637546 253872367 656051922 567758712 18027306 740894820 417921276 879628818 77275310 499960640 587611837 807860513 833075921 783530841 946176336 600146516 942619008 17528104 877132373 741695722 889668414 319530522 182059872 437714780 468848926 637934813 778243548 970909962 468815315 399747341 686211868 10795620 900726543 411453117 259809110 509596565 48857321 551847287 286225878 741758807 140327233 860171667 701741565 7736449 743224483 924183983 826925978 208526035 99483057 291891840 3313761 142407684 287470289 669734062 799378210 739459181 495328051 349458364 319555033 657174826 547824651 220729030 35121275 970893260 957972951 868409480 230380136 804360968 961571888 180687909 793249600 929381073 290958020 462821880 620580887 663113553 520796086 852192112 963017476 505905281 436515930 435761850 533727685 443290569 725613230 992879682 119547458 647045373 855830512 755287113 482349751 464642387 383736973 17814329 958729381 646736710 267582215 125948565 403533666 787017752 184582082 666883307 55559128 549731773 89667233 131708228 415201496 865188844 536387753 566577230 962479627 292058838 737246591 323633348 46819751 370984368 460205150 168778589 600403430 750570683 52684170 961305543 515165350 205307489 511223542 283943363 195789482 832253743 863586497 715341675 15399739 555321880 856171500 459458694 905419081 379657586 197195685 255243443 867009377 362240782 898098635 459284195 46061541 879220016 331222865 476627789 833648768 581619583 500493236 409703255 588187848 966663067 416299366 130382177 254578364 963272924 600091446 487601468 1740550 477605810 61298397 37090837 267046731 235650103 179534711 435160564 698541037 606121138 876321027 707177372 928547993 765057119 769401289 843094934 979647665 375410102 316299450 11143629 178391078 88538680 804344673 843543135 517365335 411726455 477487574 524825206 125039478 121048568 957818729 785215350 617408540 800416181 377520759 881381111 491875250 789676459 192780058 768077070 545414599 892401237 528951167 940884833 529597345 333725636 520293262 101270103 854288782 446295390 819543998 586175260 431165920 696557220 598547547 946166423 534629370 545944690 379037199 544888896 918710275 529586101 632269188 838411490 961894744 950272610 355332482 777900202 235628281 1736515 259887617 969551475 146783284 279560068 465264437 343411603 531486758 147764192 576211662 250006991 713060656 372744342 271179276 832180804 345146543 616171922 89908788 56056541 473518145 387980171 363056510 973568709 760559445 436315412 619906063 27713091 874522885 187212011 939542497 603167399 504179176 839964070 457944969 551085563 361267002 324687327 109637632 519102538 851077943 554396777 123605979 678300775 816024933 999519940 891867928 590793978 315997073 819710250 209218177 943119688 356900730 228190698 723528127 32898794 96853205 687995888 626840401 684779667 950127200 2424041 71918735 569894989 826233687 337167303 205139518 90582971 370674317 803918982 121546537 437013401 962295877 459376638 345956528 821733609 115073465 705088511 81750323 483874577 155250261 66376411 34134595 342880467 869004175 776436643 224265174 471304318 531269841 134514943 837308814 90067610 303393842 467181777 628483079 700844028 444318415 651724915 157917237 229962633 500474457 342357056 330390984 212926691 617725430 319188826 405126666 844006726 797031514 459198626 217915650 664535106 301706417 550653875 293556542 781670740 705127903 480627260 9551438 413332134 767106392 315728532 861771872 255444094 38124286 534021695 814453456 570763747 883296191 120752887 861607774 122449955 75617046 519799598 772873264 570271044 182347951 964988951 596332125 666273648 627757203 51632257 643741448 518507371 39556105 837555415 114948697 505387129 661840148 854333427 585959311 862520223 501568549 341154120 31151221 665179169 557309897 217641485 486514241 307839263 378461936 162286387 196773535 178915345 895933814 315955180 521079098 632537182 519227223 618132868 126718465 847937147 874895372 900020825 414503466 322818994 328755454 405435653 458607831 588815699 535798074 340153800 877420355 63632046 21158828 753713507 70148039 668597550 3410962 303252938 63858992 120078292 272031895 995888163 761276382 598140822 383766540 510323850 665319727 249496066 502131405 175246429 111188153 90174543 308663507 277683422 56239432 298163845 547569136 332975849 16855160 873718233 931500030 505245081 152078229 262192029 902183147 794200210 188934154 162899837 102619008 931020559 251183145 268489177 283795137 594407269 516486763 511125713 672703475 24333115 154806720 586309592 885062201 420441787 441414340 673231453 385610540 923157797 25899421 281342017 521080323 534280000 825012432 450149317 902908631 700935024 914799011 162929074 223160115 543416233 119583609 377822724 416583102 649684232 410042888 782713126 435724538 813963155 393395865 409114254 65519408 756993306 646758003 298654209 607224536 508813142 170570558 750111690 668178589 895529269 345490950 805818136 751708414 169926364 853122946 888098494 522807761 331290267 711036644 25255832 686850278 936541319 267891562 441209910 335230217 128355093 996118515 187174411 191584318 784046291 577406680 75777977 873431546 887594149 923514430 703635739 305651988 598956377 127583784 33668951 753400379 660785163 839693160 26064100 892990244 519201028 476434911 153297300 922194546 832759682 154521687 359232430 514368266 271273872 898618115 183057637 514635729 17713633 17502170 766303899 741924755 776463708 397655750 868350707 901507744 826946730 849471741 722226201 197879195 308625379 982858490 681958866 459319877 716129499 207357720 460764670 912281368 261048955 527289276 446362626 115252636 110361467 394951738 769472277 655797548 37977771 156920239 941448773 55961818 546500289 634049835 275010933 909505497 886572491 14776986 38061925 754720910 229593715 52688250 145770018 93392253 478209160 60618765 837567538 282025488 287284813 684262027 970896497 264821086 742436585 479924255 597804022 847839392 532762993 328157484 235893346 861838933 213248321 627717852 184733989 831989144 958506738 918142552 557277937 38130211 856025811 925837666 746333491 539387554 711675464 957230576 665013548 441160181 64724628 467679709 243007741 118609164 732930642 937143299 77573846 179411611 66752731 431745946 609216359 60376804 59246486 297141044 499563568 304049283 184311530 248866595 697178361 999513806 926830518 320539697 372721563 921156517 620463141 89048773 613028631 51507992 210205641 102770416 957040929 290905716 203053245 222116246 6065694 544874493 385111253 186966740 217693418 750116920 824558285 370046096 692158398 222583274 302270214 675990175 798573077 234164806 708747347 469911943 139416245 592278903 401951907 333751157 461344827 424462635 359150722 1019711 221194586 963726152 437979550 701354718 973857595 453969747 284960622 469260332 659223267 88613152 942518067 223546741 516768337 618525304 583134635 800855151 723736085 234131493 867606404 138879340 85385052 781113766 602458203 944710462 297556656 378004993 985809370 827601977 254855299 870948855 404586384 349246776 802532350 752708077 391093880 507952074 895272676 967318377 982803262 405070807 196528233 585877915 68296016 527175152 568110215 906838569 591601384 256649387 83929914 826463101 757010402 738154667 686868669 896312435 327599074 9589346 251017356 666065574 146871474 109178001 80153383 637684151 350181001 116222354 615398659 788656083 622943977 838712911 768163541 991310151 921300283 407485277 303173441 950619496 386589791 820884541 265466785 317340442 881629263 230641855 113306865 366098765 52408485 141842776 896469580 898408718 182681945 425458597 673182275 216944480 630171048 110784601 541964826 142821117 565945038 740170003 373672325 763904858 364058958 803742189 291467467 312346396 945337284 705382912 693129339 25830288 318647657 404322210 627827880 525619342 298379101 203157083 285642897 809594713 893206329 769368752 957363195 712715018 946131807 531362150 231767859 174411608 395660667 99310769 987418260 234437580 189591491 756598311 909116289 362776943 268895961 677183487 609069122 503670063 798110540 900969219 169515939 536764987 777933607 833254665 256483205 566846449 448074398 645693982 702686260 451860838 758975642 257985158 82783065 36000937 701859022 381405778 492631249 377902833 300258807 746981053 799924858 214104970 740789096 582558488 943625757 144826523 457030832 208187861 534583657 48785167 982835268 185535859 500415949 725793183 180879251 208147910 476157999 844023880 635454526 685658118 430656827 126130697 220868436 250669418 890074634 219481506 821283018 790784229 364133847 153208481 218606939 436451507 586812480 799303816 612011610 116532068 56090139 543705830 658888634 912377177 891827354 35901992 678389395 203567997 653203291 476669619 197423061 561946854 251249527 737576653 918868329 84965866 652551353 136595597 334329554 845120356 76774921 91243210 813109012 423305181 201937121 61892418 994498666 480023437 15440792 387549518 147126704 308097213 752132754 590552792 307355615 599155526 931630886 812365579 462300074 559357872 298418896 63462180 728138981 821299212 113050344 560795402 960820617 740818122 287016167 723554423 918086087 570179758 312644187 874260327 412358788 772652811 905993351 478962847 323015577 16116832 619280202 311306989 296001549 769076009 10406125 354727793 399506019 707001637 447112229 872913628 42246896 296533672 202127998 267445748 444230864 915242255 833559042 587939941 346738742 985023205 229790888 62576919 263891304 883263214 721894925 71817240 701660432 97508807 720312743 523794828 631522203 702456823 585288573 302922999 660622832 793909370 640188058 642094172 209078695 256419493 588769623 251740782 266432886 298025066 86078740 565462089 554651766 690267427 84552047 200088281 445692907 697936815 710169463 989678558 131226726 412664245 431949729 745522267 323332685 216928865 385743372 377743830 916697280 404677621 998807661 262283011 65343481 212877759 126768071 477734576 627525569 685720438 411913352 600998619 813743565 888699805 573001083 873632326 822063251 460483949 304151267 518092595 395554243 218452271 87888195 646504152 97159577 775554016 287139422 408815673 46517907 348363198 838647071 144115073 581170856 549364257 612013162 833026632 19016930 879143113 676865709 611903650 693902713 413283494 73272031 922961251 683507313 720347282 322124496 758866275 352900947 991056486 464457870 247250895 169771666 532190206 161632690 558142393 692861245 395851062 519897201 532202086 28910327 217262975 175175844 246850151 116364347 139690436 816626670 628128725 250773660 162426834 882473751 323352728 44254787 542569284 664330957 93335984 300635464 28712528 611747791 702513597 988641396 231122545 96901042 764023696 532330789 475249871 315845375 516152201 452446655 729363594 415063832 554326027 2715233 599256573 732472130 722841420 57021722 489359778 34322150 891355141 528309433 921551946 69671657 422005711 629619460 750306010 343647871 700057045 868923908 776265113 937492971 801799091 741569332 123372871 211960525 926880798 261119145 424565013 641668281 55123262 917831908 289117914 824226372 25942543 665684901 427127429 4349753 531999495 281422286 221407514 9425873 764611848 18482647 117154863 844442766 510199407 844366805 682529751 931373349 454154779 979682405 977145619 270441873 79627905 723374443 956395972 289877970 927497286 548448540 794495513 927211942 192860352 10888178 343452591 106709891 964125726 870601922 465819092 199245291 291234896 113338105 647870784 977038151 175272379 239454773 815715865 183009871 223339992 250049337 698343903 242289404 178512659 251617985 11542449 68726350 439004993 521905684 539203105 899049617 529876260 81567135 473205826 345992394 42240966 190964698 64775733 527877762 265679797 948304850 508913349 37913939 878878924 663234133 841446956 132686430 310447517 644358187 439138580 235957402 722368190 209292994 783972495 226361143 659105477 74313725 831027478 655994922 467445503 948662577 299232048 437414493 61419072 282616578 741264225 637524183 36987829 534407348 875805585 971675526 9907827 506589276 759314965 967404976 375690193 329410575 892207683 450129347 44421558 104495943 213919854 573716352 97344765 172189113 724409683 991325742 230593629 220405937 868270120 866460118 938639017 363408697 160458067 585621017 75967236 497189411 373981226 179658655 28995218 651785269 136201966 953506595 103123572 891251374 738769033 160994334 726803277 29745744 498001898 882073169 213166660 143092925 551147706 141342443 416640447 168734794 712506186 642457731 881078657 329035855 86689719 261325655 65667030 870645426 832791937 286123877 780138865 708693367 361809837 368578951 672120253 207478161 250931616 286507701 603122019 482672517 365976214 524646814 969410138 696178223 817189957 482948647 545460600 11904294 556750762 270919973 126974267 652521802 557720352 841315138 646191839 950431379 490650765 820641911 60455771 116563774 287517791 368675878 125341186 337508422 788542840 602203994 900298878 756885237 194652315 538628243 712295752 837920830 739621392 73603065 745783284 9542727 181944077 838353005 593205267 739288676 589164277 128976036 739762273 641624266 494594519 346360033 121090671 844027899 261518316 29434005 430315115 992973917 712075488 531655294 346486098 381851633 311722491 618663975 588026024 30574487 758487815 823624987 887950396 513805209 438037753 526514020 258376602 267396619 231156782 58454048 980293194 477310004 471153597 380873788 241830622 118468742 707229266 482779910 528768287 26265286 959839002 718699869 901927797 991788264 308479095 775861742 964039246 884039593 394060147 789169982 244760283 653038681 448300745 800811647 823993829 22105905 551006310 160174846 337137128 302953369 588707987 613627832 889175630 853986776 27096993 665078325 84958446 741594908 938834729 570528804 268219255 818001550 410056129 940954496 626719698 782096379 136586853 53558321 838450803 883387131 987169791 615553146 95981422 321559534 226571603 221888213 886980259 368425273 926359934 872618352 882437235 452481954 95222715 745281580 122234441 494633690 972377326 313145921 740574562 8750886 998994851 889749409 434522128 427338123 445504801 311475496 988745314 254019427 378930940 19261168 224182883 193541367 706873900 916219380 151557653 501975999 827882407 140494542 7696254 726461183 859536553 31045541 900226960 549649652 661397173 193652258 77736670 636048533 50000871 992719993 223532506 435147527 772925570 241619239 712710028 337592897 754601968 181265992 277647582 519174990 552760982 756381397 112312288 738483190 263171682 637742638 649568117 175706129 754872380 391675818 859219252 510471664 433490071 596126883 28974209 803187114 792626314 461111792 142950150 617309836 266064392 744249086 940914442 365572770 317473294 577086225 610844730 314062198 890839124 552134370 148487351 10092891 25908114 410467161 773288112 995217185 121005739 187978130 534942001 615955008 645184515 536405118 945886920 126606040 808896530 432116648 872113778 650372267 746322450 832370390 974992028 773523810 999809638 752515055 435498198 340673985 514055959 879571274 520709179 940603431 946108146 803113724 3809707 238324107 471877625 769958611 988679503 325260478 30014758 307248409 434570854 130741410 299767763 530138878 785289597 920058946 959819295 129283023 838093802 966921804 682585733 181201322 41158390 985557316 621521406 812122857 691048706 220275741 416716683 837443384 424077556 534044779 348048896 396881526 322666394 850302911 601940422 439625010 77525202 654323417 722229721 26593758 398467 651522370 817361761 371145091 353127903 77314980 863981008 783903553 404153659 675171135 853285106 766786577 56271724 548567302 191039699 653821466 278657885 566614003 862084931 588712814 706166447 638727756 67241311 337194536 555233012 248773342 274756067 95874271 227896312 318745332 782738276 35923875 213221251 153645195 41567763 981320431 96781994 527084756 796224855 161163102 7097041 568661732 255395681 65903317 255794268 527735770 919960421 123340138 370582378 664597406 87540635 442232875 677500344 643156879 747343004 743445817 907460301 551081703 733599077 747172019 978861837 303520407 328074981 51903462 473436967 822883425 385045474 427190930 768531900 421845960 762370744 118066936 822318297 672194412 488011142 485252860 46247700 673859013 675080886 892914807 366851126 118279380 329333194 820780686 348038433 631173392 226547886 802175123 159320265 954512715 788219030 735423145 869917831 353153949 430545740 575585532 567290812 185315547 983274124 306683143 43718787 484984018 167462952 905057441 878285454 840806017 294926152 264441868 876774476 50914922 782793175 606594466 790566416 825935396 466008840 219432865 877144619 603920824 427201945 380561608 138945461 790365431 217539346 960793571 409754622 199529485 294745233 168658622 123518808 137190447 890650942 995503729 376403817 150450536 227545508 894203146 918488145 540406884 343325060 369712968 276566961 978683111 307488093 160703485 296973243 669336991 541562735 343195541 625913298 405959754 765259814 570923629 461238169 786860194 96378514 588671202 109420789 181519153 338452061 72154291 541218235 646533898 655754551 167687778 112072729 132748337 952527702 221564012 262082721 578577976 209018425 26166936 588079086 488922079 632671208 42931012 324408997 775928978 578135072 97248565 60418431 510581288 564379148 699274803 915236097 111654366 988689655 8811973 69422468 571472173 251357498 796828072 965463998 814661211 770176829 748225094 322906057 784523389 718917615 635940064 529566303 304874513 4947452 987205809 959840846 442570593 328522502 127962844 45082707 894920985 632255046 331872250 370651934 291092984 196128854 389831601 297385566 437428302 656042205 812868591 56316498 337064988 238153937 704696700 26904905 487825127 814471965 393276333 316024017 725189144 262376121 186654621 246528239 838667510 537278473 611197637 931299629 937403730 967066889 818561412 682116087 475746645 121076298 620192211 664086281 579176813 553721206 408607789 548499362 354186475 656314988 182623948 677126626 414851974 831219366 972205421 740291863 872396288 48111145 637191621 544052404 716934674 140464947 970661193 513279558 558545197 147128748 435464028 879374059 635512130 936831476 512474292 986762384 265112194 945393229 601441564 828979303 622476344 879430998 732727089 546087230 424604185 908613587 314474421 985868053 25549857 702444678 627488923 650397546 124376057 36447334 885985827 682848227 437907639 872577697 893701743 101164152 987174429 373749108 493634824 813399414 681219565 587834278 862014400 646508000 764127729 413326225 693041430 245611602 319792430 401542162 613909505 661763876 679669989 985216960 788146237 111309844 898498506 851481010 335482205 408875959 121822229 844682730 89047614 167726366 387027613 863803834 707542737 845452153 843835931 960946094 660542726 685040465 745305481 547118612 865066546 850371567 521551404 897872694 209465010 603600717 72977793 299011187 679106805 926404446 935654951 563656851 222985327 609841530 659371571 502809221 957511539 454588445 246083085 430181153 152349427 619912998 976737324 704399402 377445307 161052308 898590145 563086245 415495147 310201676 14711369 878937452 428828078 337962199 925136135 93332727 544538391 322304402 438249006 613823918 920252974 352713627 218716193 284111853 279993006 191867831 480363256 430836176 878589799 737870908 788399851 777884285 10106776 901978647 714222704 966539087 149311979 506004341 265542941 217361653 372787333 473683434 719023440 865569313 7013941 724645872 263956404 544996249 219927233 533616190 16307797 741769701 386426296 733819405 793411604 386798896 319961483 114407649 585689542 706932878 277617152 755839291 14252495 652436584 66845412 763651713 543470140 425579829 366652082 574102065 964386152 804453185 8087843 383378468 984236680 762789781 189547929 156368594 438365260 358779295 467496926 399136211 555177819 541492339 704248902 286108104 505818145 122295111 276670544 423302439 897740548 37622915 439525456 966182346 16731334 61460454 513368682 114129998 492169326 939578871 335172840 657409947 408799127 294115420 300788282 977063782 605928657 432657955 918049528 661289090 205793207 164657795 685481174 581924574 214812575 782227786 487398804 999605339 247449878 755276846 399069680 765749767 675792597 988516310 709976395 465387803 801200239 456786434 116572302 165775554 784726301 474848400 631280311 545215879 860291777 568735355 445275868 597243617 425843978 118820852 40002809 386353020 226234063 335892527 519627985 940074315 331536425 174691518 540168631 437406826 214440307 620273959 765201980 528164076 605361211 101298117 598988925 79138068 189590833 205788113 317919112 389383511 235386939 786081617 797311546 567570272 667057893 131302801 526483508 354113282 741681713 205613651 781138227 991729323 679388387 34643650 771550987 984054090 925116871 940849549 845443721 52509405 500778005 475841204 243038444 817584678 202078332 855967803 723726788 323026319 854728321 708202605 596701345 504973881 920843354 685860950 637713107 577402937 950358923 313022177 239642557 527949778 404604963 501937292 683758042 719725093 335850311 778347986 457382356 898650222 908902275 963180445 330495264 480766963 885710167 793920870 531828622 883528526 953893695 619561227 592792907 924338521 109871470 758890983 241369283 780688387 665823840 257675563 569217735 649437126 909504637 491901377 111466081 120027330 616615851 110826930 881846362 809554482 274768998 866561683 38002393 917832811 417507916 135944457 605499058 587220222 45613122 327940874 737428414 240419237 574738478 739959616 898131470 783183536 124556225 78895870 835710825 499392363 793478900 692309345 440123187 244451387 731161510 688517200 624946064 696250344 904340998 117410493 770652563 632849412 305620647 981990145 610355078 214927576 166166557 994275434 185063329 782573280 485284507 524155843 184169146 909400970 468582879 932734007 945942426 361781714 434090311 816204938 835116912 525213566 994222742 644858206 743155718 145423861 988382659 499758865 765535510 798434940 87957296 628018796 659795316 169925713 587381198 72919443 933514155 983369634 91513479 864154845 214802684 765738896 33801487 612212545 304041649 970610343 739056874 439963924 360056778 840830141 124736177 805228574 24474541 346745518 60387724 128472960 674339155 280157540 262317299 308575512 222057247 832832858 518769405 960134869 832862099 539744415 18684019 411336258 740428960 638365217 905927555 771534648 257749152 22390657 190787338 979170933 600998992 61562091 795690051 740901357 728189080 79544591 975561074 113559100 667612228 502578210 457811726 731894468 957666602 658899744 879153534 231210376 975009337 17783555 922116244 959377666 557390830 24650585 637042987 495494459 939365339 377341392 328458397 434896330 671359288 698842332 500763973 397228433 24472802 380629655 979011765 619583072 680519447 897027167 531510481 669656826 846389762 786331813 646758894 411973870 787449070 139698618 918812384 850973371 371794750 388267154 802073172 981994414 554451819 573445116 552892398 865100583 891614834 697072014 336897267 764728770 432413654 910402676 705954676 726944490 910033142 784269858 238731134 839819661 749494106 87172604 986154970 795295661 309648164 657117510 825441249 583356111 213443507 384002280 853396749 317538438 796278688 720565319 695677005 254911934 908842552 840559374 272284879 19970737 244754855 546289458 6318507 470793950 283834109 365426265 987165707 854216103 826600071 430894296 866869038 429386182 180581844 425272785 9060337 965340065 833205288 690906526 394104131 127541614 320528571 664443832 636431778 443111183 330773051 772171316 471051396 424887525 253173831 1222722 669273006 772511583 633097818 515649147 793191947 318972747 236387856 344534425 584871658 967708789 106973093 909888942 279684017 578183929 717675883 196415031 790408477 509211378 310816639 249388350 682969189 911403709 741715948 922957246 648087070 841880030 923583205 482026783 189560218 341187619 829083563 543911572 627471228 386646122 660078125 93444707 726172123 807855877 811190508 604699749 564349490 277853239 188586041 846293049 862042395 509124855 324517853 52715829 655029914 412006039 276103888 737345013 360702566 34543197 130296450 247385122 89734795 160012571 927434603 322845601 648837945 419248518 623508866 322333215 29791377 901644038 807351980 718225994 666983081 290495471 923097225 344755166 274453197 650022271 623466422 777450454 423811685 224824136 748346467 928182041 671492716 153803084 206708878 574721173 898107034 941320403 53119005 326545915 288490033 439080013 670588795 728463886 837615836 149706131 717661126 429437923 933226340 341607693 360179415 129407230 847656433 55974534 173036251 891198512 361798154 24199395 802755722 867923200 258349120 114684142 780061185 171236949 331046568 25739227 209394106 97035911 647136861 243238762 117511950 924830781 93860623 736465209 487191064 943007031 982023700 220818904 717419903 784684083 126049573 825417870 284072630 690341065 260896166 823143375 708888449 221189906 716587401 699340410 763334000 627995447 616620763 943589758 672924587 500746818 581768733 421528949 148380543 326591249 471898028 692402827 402068347 92644953 563018040 953541205 947347547 520855993 399613036 362233857 247621934 89919496 859947148 264186155 910484195 157803469 146175020 581374026 397758091 696769864 475238259 609376738 387253135 933249360 285195850 223990591 701888407 254346894 201610720 931629129 715940495 542877269 95624503 326182392 439867152 635364173 314019325 797060395 257401849 353527659 668867689 569401790 359608227 652373181 800523308 903785645 788843212 201084954 88151671 709893652 483580306 414690331 109357727 224095709 948625624 565622963 921729409 916639657 315564286 685727859 476736986 875121132 652288363 709925549 98633631 192011392 363720700 276542850 539780608 455028824 380767983 495385788 694727023 257605193 290483470 484930059 697432333 511732212 748103083 697014718 998706615 49263611 807079595 752852978 651785508 56811184 288242437 10280128 623502806 413110241 569382186 799446928 397012820 278849176 292387557 46139842 383372948 433413728 300633385 499277125 843613788 322386221 299908634 101162782 905135647 191461917 552266395 449940176 979140020 167402964 706893766 804970345 621459693 155010366 515493198 288338432 226067535 219182449 832124957 452230290 502073568 88921442 761456602 133995909 548135998 306121467 912638823 614615113 860173394 624796407 450958269 851348362 201393815 381552509 258604069 694317796 772933713 190911074 956218630 971364125 744040216 248937695 428442630 248070854 59938310 14187226 137514145 845740448 588186737 105392915 414237478 35541506 291231660 785675151 555728034 750388965 518333194 949348790 669344327 889583226 236746344 167607016 900119289 294070454 153473789 768069833 331273050 905015100 737371300 70298144 575228434 447939298 955681752 42430879 197310484 602357814 290618582 91516423 395455010 782892816 845894963 931705344 812086428 80284542 165123202 84335513 900479207 759351805 991604293 258936015 234415391 36542031 917334809 453151874 782035995 713781757 461059375 48303088 523372945 487467096 133003609 268868864 160989606 321174372 163274297 863771045 401333919 291055885 16103068 726914270 211737679 419248025 612396439 354881623 323585627 750322746 449142678 227380471 313978194 838130969 343168987 587643057 436758210 861703040 889888717 579338241 343829970 177362885 114052756 33571249 897511728 892187895 860382535 44401505 110303526 584895501 924419713 922121699 109497839 124700319 395984673 424746290 543739567 315318068 742672905 548187743 126253115 300546946 38035886 760553775 665164902 141121711 713059054 944055189 291600436 451125282 211511838 655975181 675713685 650668828 920407869 598168385 786364689 402154828 177481223 395173976 391935152 671633540 168317706 35726071 35179939 497322834 864908873 70847827 742463815 971636266 205674267 331893834 931863602 943854023 517271905 145207843 682729038 304686134 166083388 628787264 924449701 165428328 276618505 70872558 119229043 173042297 484096628 939764904 910021305 315620366 942034041 645475268 506944083 153525146 768055056 981172416 808258103 83878532 907552380 186583152 831616945 953727077 595441320 37564857 439149195 514839941 992557563 528453658 838470170 230708669 484354184 396895686 72250590 622508029 37100880 451626009 591905779 511246476 446586379 457180175 312255492 86712119 349038395 752976538 964082709 477138504 651627715 858630050 909820850 700604418 323034315 992061795 890402928 270636447 346355096 134492992 516383363 976988503 534915711 135156288 52583124 19508141 342025416 658577642 367601468 890881550 565987128 534508198 941062061 858934357 525553031 239164376 55171862 521927757 403019426 423064408 501118542 393955471 156516748 99953345 710176168 663064337 551732665 863922329 284473864 997812782 790079038 447896294 393264301 804385784 728563338 171076660 393060950 390198669 146807996 421467400 687422853 423832454 307396454 925876762 586126056 238817551 301354327 772611419 651176612 540108508 109069033 845449758 785854215 792395775 409643455 251248168 883197306 447213476 655329438 824252658 311078304 197113562 201988170 434109828 435741165 664249566 296809594 802911668 119243524 883267705 137400974 242685965 448013008 923894145 925954864 454536128 241476088 60383925 294492133 931751295 423701847 298633274 320429818 773895131 787524750 389091763 16453837 388662952 20400890 623145316 191275864 997978809 118047696 550602917 254449538 290259388 392861144 532276876 215763788 424495960 387637758 252169124 150989771 472025561 849428792 270186992 512509584 455266084 172069158 508860285 987810152 83435313 782976938 9523082 768351160 789848578 476289439 173706636 790736616 394844337 564841103 935743436 902015517 203805279 933095968 343543614 124741939 266550399 536696175 714991899 406783278 323672715 951635495 481277432 569861711 292952947 690702801 847868596 333670611 4294091 951819138 775592929 210057660 896705491 102123312 430142086 844757113 82099115 428440108 781978964 741990877 943532552 229208203 240613821 662173449 37127506 547961528 119435861 648373641 473717099 52696869 403634393 274022265 511967660 344296121 536592038 390266640 529661411 708712873 238370166 92360462 301707596 717757040 240275116 628737806 45559413 61178375 845055326 499222404 145668505 478184307 485662963 479208282 438200957 81403561 875692113 123391521 743341988 807021643 176592594 915506256 509089913 28168808 861016126 915028977 682963218 855045623 246220567 128672588 544847164 907541174 391495247 4873220 936234223 72012097 842534031 620631492 380277557 261145099 818358303 556602062 249519413 501042623 446908977 793115282 446258509 784052314 810146918 429925114 72404613 594566286 312087359 550456090 551491220 889965122 882454117 760381125 62963243 17786429 598261217 194246386 449506366 815479393 557539980 808243393 364504903 540449554 968480342 170843457 74990648 146107788 139339721 53065370 528393860 836196578 160919314 688766200 247915927 85566843 401398082 385405014 296406220 510591542 42628605 815189378 842218651 411860055 637777280 531269627 675194165 870389073 23441038 812364316 22041162 667081397 762021198 618940334 660554264 884786064 325235020 662364122 679256515 926537887 181689762 597470595 538564503 878245856 259057795 406266664 905324123 364917069 707487177 526378985 36985137 520982795 17719347 206610580 894880637 646028490 49735581 838315904 89653243 422834639 251467539 702829601 710402715 186746993 429511981 711065744 199124734 24325859 74458477 151413578 357985557 72917555 961932594 305829582 713291315 766587280 218585617 796080405 414756589 564722097 915697584 65683666 760117915 590614900 854742383 836314968 867554595 830980852 887714146 182511198 438467089 361577911 45602331 187725951 402294294 370110435 903663633 493413399 861541723 165659937 275649876 204219545 197558267 644932281 386051637 827446135 460559195 769044486 48346338 423248717 534411553 305658480 260664260 284117143 689858876 792526956 204878376 392419964 37703874 739287246 134806246 896698851 870319406 154968514 449731395 634397167 218539557 680258910 802280413 46875916 230268082 24285090 247307594 659398049 492652428 381396207 41235716 166245548 72463440 703914358 717023518 91913302 519939501 682806025 461997308 445380643 198492136 75058606 803874962 611821120 553859644 570740320 425915559 276546457 116309959 976622906 779494719 567104694 288223473 631654154 349762619 81030552 937823288 166986885 149337256 895371987 511953136 962501161 427638514 388109078 214539263 857753870 28077157 235178869 277585993 551511873 452320009 508670955 747720329 774597896 254306922 877037028 229197953 337084979 353647535 40706649 257775989 995182724 542737919 346657789 754867737 667838711 733505579 482978843 881582450 471804667 932079154 94290311 217702415 333689592 555745381 36482774 485760595 350540913 489933532 159243005 392045189 158691766 444466668 129170966 24115111 123107207 726848708 237973375 112133543 653667892 586067149 230182697 896113123 961505889 69206618 679999384 691192566 175822519 320230499 756016067 68353535 957926703 379312858 831011363 709338058 93540355 67474737 338524685 85167516 797309568 910816073 828866281 16381635 95323599 385558928 695507733 775421018 898365568 730379698 656705291 24338951 199046570 537238065 647671026 547832424 150806622 995495790 844902729 376387571 572890974 646304644 583807784 418251234 748622659 352955761 357972049 257378720 381616100 16802426 298043703 265491352 111951348 37505220 394419831 318582874 21356588 169201913 196885448 897706443 365964701 973214300 200961150 573769488 88376145 848850022 501404358 419318392 803766582 996630176 551704562 904132521 224522495 205138315 602346671 754003143 493158766 295877504 66130377 661560327 672218924 555956867 125883431 318166408 395669484 289537688 313738644 238231173 789856283 241420562 849205243 330934410 847223393 560322840 132930448 151819327 134444369 612554657 189733081 964123918 501364598 982149810 360650379 503578168 984879230 456707123 761040018 727580940 734886531 260132723 607055760 938103977 869802906 572211143 390517584 375698068 938104615 257497989 934335653 978793598 969829378 7888479 329286556 345140335 810652563 29735723 556610142 342504330 417782376 3109582 307280565 800498807 535238975 669966842 725678202 952145787 855264428 195997112 379050636 48238809 134389734 375590651 178953701 753274924 446444127 849405285 678288718 999689431 357729591 315435818 63293463 809339118 50162069 838653242 953546457 126052379 727711886 767838916 817162389 291223239 636609062 438945537 746196036 569827047 850641708 109236793 994699981 684513557 540848906 740824323 67655808 739243742 802899879 917423224 289855145 58207094 594131793 456012698 152250408 191631175 213597985 69229961 504689152 941082563 96095930 782214725 268669209 22853739 57111191 872370434 248495423 655799400 224696795 390487514 588138280 253256492 742793673 66807109 681838295 27193607 343687388 396957871 246155428 6613022 664786496 624522379 19977565 599253215 266672685 467959973 534128409 196457050 581340578 341015833 316349638 57995871 901593563 380170787 873105231 651288031 51014958 656851779 378886125 443049191 469942484 448765328 189266431 911755564 627260306 157456778 893769899 506053180 117453042 107152799 750286786 61860267 670675101 956113585 406309175 738457412 994622885 474050855 397512128 235491329 310717862 107409332 404407994 901090270 693862766 22502647 187896038 205774830 659218612 552019665 790432146 311444166 638942372 725166178 775472299 117414848 478524249 234774540 618467623 823131160 76309559 421359640 5556006 970160881 37153966 343491877 36326398 986588847 527961344 617471427 626416912 955837996 921693052 948942974 23865153 631231914 960359204 230744767 223302529 448581826 565202357 808329739 549970371 403030335 33320488 345535196 458860921 107421363 712812911 943037760 901835948 585471792 824669797 602589140 763216414 584202639 656471585 916550738 639797300 422675254 619869550 343440892 974023623 630424209 6912867 744440578 254339816 273877314 940664678 255379622 382420175 908623733 200274072 964382902 862359685 765170194 46805823 176782749 356978426 376916194 224811383 377181920 12175592 702826869 445321068 187687861 214527149 825180528 334656493 56176555 530877088 319939042 88707382 73600446 459147834 577888895 266308876 61109858 334704897 512660395 800686467 371442728 405680541 25221362 264434271 52425856 389930468 461532829 330191737 601992510 222550177 463539988 476033385 464023582 809415624 847397422 150103322 87980344 946274299 337136304 427438628 382079200 447831574 354188174 361316344 655609670 250251548 205794849 717334834 758094789 691014532 946627723 241348886 756908098 237162234 625756635 965637734 521449801 483693512 686518562 630941746 4800729 258802640 858463918 217179906 619412572 598091908 641852901 430356962 645239459 883378053 714484183 23996197 342275417 683391736 30875759 154996661 481156193 377742192 267965634 52602289 649312216 584500162 130198835 818869438 349745447 566036569 113774383 770898145 711053036 198966281 773402813 489775114 332880611 548393808 421549119 883958609 633619661 878635854 846162455 667617520 296393281 249281846 867593956 564589029 273614469 654146226 592228899 57427025 172693545 879096740 718288182 729921530 416924177 696830825 127628583 603779242 256491699 342201870 8362703 212004711 654161125 927130014 350226306 603004462 389649972 870119360 477090945 29280803 742166805 48431126 310482585 723496907 618540287 34601309 965667408 550015807 400511463 837368186 729972670 939453596 278872499 218241445 993225335 979525001 908135309 81637705 911238866 25918874 465327743 283681459 892796414 880944320 467444411 654175984 636852215 138313584 522440863 643277210 198151901 521412388 825379348 410587406 640624283 92964889 344050395 450831999 977829443 338610150 349616327 234755657 872273548 91182641 89622789 991474950 909440754 806353725 737771722 93548194 631665222 652898488 562055278 452502011 794426456 896185690 386864822 338188403 409734784 548610691 453649362 877502157 974496761 908050045 640721593 661981763 165955621 887621636 93739039 803058985 153797100 531670928 136085150 162527418 988410346 245430941 399676165 833531526 328916152 415127320 830995838 590139785 341784894 680034864 161010625 293017902 535059035 152612513 405271511 630174189 851004433 801159378 578647589 121950147 739026834 425815511 680311521 45232518 571470518 672054886 985328127 913189711 890604166 257972998 871562631 553924411 634907007 154994484 508836513 879143619 363595153 29903506 728969390 822013147 724009893 356936094 459603879 145163589 8772530 272444580 106691080 737169393 704036705 61489847 507479527 5154949 436266147 904093448 293402035 49287760 696250740 435770408 859422007 915386202 930353354 762223694 664542025 294216984 383518251 69440544 361897326 985825735 370860381 349877508 742520436 557478575 991661096 755314844 629331476 652120589 556381232 714668168 661643016 823576385 624272651 681133096 336714533 780950334 165504189 110635504 148734503 422279291 551092816 616610604 347792570 25125259 509882621 730583367 794558430 415944765 462717578 373985753 36705783 385682405 274872669 403800380 970188606 839214381 207727746 374602748 547532920 125554454 521343239 974165460 915154778 27870290 390053588 512014051 656468135 428413172 217877992 515333442 730205257 374052661 25024754 86214558 351917971 625997643 959868946 523792277 996649530 555048666 137694922 176396275 204879395 889559109 933121879 753676302 338945617 624963382 198007724 774285671 123096183 348948186 669695847 114213402 990918799 805359252 296424778 456430526 581880314 636241802 212238755 696924227 534752262 474423160 175006673 9288761 332730973 794334306 616794567 227782100 497649654 575447908 222881370 399624275 960753718 998187075 754205791 926894015 857475701 237394795 152812093 86725625 996423635 898763399 904299109 921377309 955477474 552357326 822469048 118424755 184100111 252212823 20546052 266568070 91227293 208555394 235445705 42436781 537911279 683326915 393478469 542268509 383191573 680757391 336777974 242005156 375584951 536895200 26554303 382237432 832290195 232940631 345624205 382192981 481592077 847434171 231449240 654262683 563749979 291302779 952703562 274324344 648884756 16917986 715387713 680345031 845935003 522286630 175147228 594055992 697181184 112607271 691901963 666889585 621413255 178569146 991016266 962671793 537558937 944178669 892182754 67083329 930946561 914513872 679736313 581312012 322740828 483707833 771346315 869103622 689982530 300499621 273567967 628898929 480095974 33528778 353182689 496775240 624756157 127786074 383581243 279084167 937274166 72866165 761115203 123318831 362311123 6411850 442569391 638732851 970012873 621097123 587924285 218085631 555662566 94901948 207648455 350878094 239654533 425523397 463603028 22538903 772782213 863780678 565974653 775001924 326248107 695911347 135626228 831289406 221896408 207894047 924619411 596781083 366569818 717550986 277384083 650162087 279618597 730407458 779797085 625130910 915602667 975484183 53701240 174235491 167827456 193455971 349046711 29112985 174147445 628456147 568703952 638897315 337020107 808539474 153139599 479465694 847265270 704779716 618376983 124783737 47552644 506376133 964615371 597258769 121157015 174377822 261778878 407284926 803102174 945562086 970140484 78366048 105889204 398352911 205291598 50297012 452783894 599786846 56409733 31098495 858078738 964731391 467457068 796311244 2347159 618073653 490105032 928741519 96012978 271218617 208525974 439277177 569876241 925335715 239706458 826072061 467173864 736065794 297038007 698907104 590799757 82532855 757472177 362248340 481291294 705328830 256472532 78126276 176649187 74950316 86638902 163914775 796663886 137170901 459818629 811131524 587952553 962988009 246565071 378162965 724163925 510440622 759633526 484392738 232107708 177343870 855132632 53861333 665421732 23140621 771837920 997546807 417415234 334916843 819418206 40098804 263936903 253861113 955394410 822710709 870877982 318456046 618527962 603452305 756560750 763601000 671462132 614609306 63362047 195907747 437139100 339677514 170315554 362943025 513469841 740837982 854386618 818779864 5912413 536074921 950144063 128987307 777293106 420882495 993859477 916636923 899683573 391328626 173792577 605378127 969358807 562109875 429462831 304800847 14222032 912879432 574462914 824879730 915476725 602303954 195064479 441490201 144125981 445776376 876731824 596436484 180999239 787976696 432956534 617659797 766102064 59854804 528706302 262176246 615093283 548364831 925397272 397218189 41042613 969700734 706794442 98697338 818331837 754898886 787894493 599218510 802852786 838500426 254115096 57946763 246895145 4395147 249613451 259513620 456139531 775051931 158138924 741575284 149327721 819305844 879069352 563566239 3497356 884350542 31269551 17124840 4680026 198521203 243861993 612599034 274301342 926459365 81096666 29215610 809210481 48600460 127624192 402509429 411551597 899322941 21100415 65852546 241585902 360257062 63694487 178306574 641566568 98508365 981280762 369625339 843522212 644178324 51818776 417590142 233693648 583059065 506379960 982647048 254049296 780996991 943552148 110752372 559811186 837107353 424829187 752126483 892943334 498615530 466836526 412378838 243784865 42812429 99097416 295000623 727907899 443986433 207438516 626578435 95498043 267865741 51644603 517639735 251927213 319754352 40024784 572024544 905892524 57757030 60888997 301188834 423295470 164354111 192858619 995690862 630729539 748833955 952281435 728793446 93860130 41221366 505627856 820071621 621519757 458292884 406622368 210856297 200883169 394064842 852050313 557756536 349689055 679448050 40817679 594118005 771402944 408165737 83746170 592822106 533496777 376617075 903614241 961525595 466614267 749455591 372213736 44416273 49340060 881994373 823894298 843981342 769349816 340931102 861388034 385997910 534949793 762544033 274217865 452451897 271844181 485491233 860858080 479096992 355395581 28459809 585649659 692752616 501946729 623555306 460407850 271534323 294011732 871178451 316411711 543188929 188131299 796030052 959862149 780864854 337695574 392256402 542483828 724671293 150704101 874226536 699391187 519452407 862460050 613135637 691317139 23564406 829860470 661603873 794231585 134950540 846365841 522900732 274150587 754365938 804980939 353310518 856167085 669194000 156318634 344530905 673437197 583149728 293550261 495379172 416317607 780038281 774750370 742030031 199995120 707160069 303555832 646153892 557885133 955483459 949574272 15208953 644436472 666633538 964101339 418879024 377499128 563725096 740945836 991603060 580768618 487790870 496424051 985810525 502414610 803687272 515263179 750612047 579683007 718480177 400000093 467128699 490721783 448490241 745030358 230936154 426650336 701595866 45827391 571632070 153894415 692336977 783271008 927241720 385512291 53585925 720712734 397974482 427271609 722476166 340030865 338019896 146029681 344161434 725480465 459415799 179126989 63522093 662355958 156131069 212097381 562761175 973814319 658386770 736294980 20343990 708849745 887167213 687304914 48738588 651448214 204493127 395425216 33968324 699465953 622000457 448905383 879780920 910875509 993004360 913569396 988873581 979056804 319877620 96141038 101766856 99829148 287985538 602397769 378422909 525875197 593946834 159717454 870845925 373311582 521599112 989198460 859060699 558380622 226929208 369508754 419968369 491473909 883490333 234819655 936820411 631182733 369966100 314825322 132737983 377612268 512313473 281159852 551969576 520958014 79937056 730157649 774281597 906926485 935107626 231310635 379824044 928169741 900619564 892968256 790691330 683461200 343334708 651145843 415013119 247329613 151467900 154655843 314242593 514322836 444854347 449733673 474703162 250320091 81755502 567824938 623790572 561158376 765755965 484213661 49590164 375403686 696231956 145202433 303114090 766050668 288898792 580842133 840225629 459170667 644569639 655686922 884384322 328000243 42437130 254758906 191061723 66356846 50564610 177365251 427600265 794194925 34144559 897403062 670360826 580434778 156581522 702602467 798264735 68251438 668810690 743541111 232104379 71612723 80279950 131102376 713375089 177268936 616503804 21242418 121504385 648227158 424884543 200092303 76013477 662233821 120108704 474763533 665929939 659594157 228210895 537943327 534011897 664769004 761765284 652949272 258892865 130819511 932585969 870342647 117047531 295596693 977273806 943857454 192414608 8752584 964329225 243260231 82714831 5185408 544370763 783253247 333998586 51684076 565039102 119578510 779421128 934642538 627629669 823236292 122300646 185753553 677017187 856232790 467531634 511766519 563274843 790925454 259291480 954471293 145992222 594597704 495713855 673140453 771417679 18739125 430147545 678864032 769896543 492125483 405797759 188969684 398197649 863351895 382505621 133199236 831091880 627123859 100782145 967440434 422216788 712004650 834933331 580779772 967147097 639017182 935401808 700758479 347208573 419771439 805036552 279961027 599369019 93122293 585714947 682139208 287192035 479965698 17781143 896445172 375047277 98374949 175748390 446068534 818800647 298081289 435199594 210290655 465651797 738019967 303109902 52662206 653339744 682002617 843152411 884244236 956003497 465455911 469919994 563685672 246863261 670186848 899463940 31740241 888554284 316824176 202244724 354350471 639188036 830397567 565973821 585918133 800164196 669186963 767132470 207640611 624493076 339498450 191885981 925928602 284447618 711834339 683099337 679517716 249698799 16203857 415121012 650253242 380629179 337220493 411675072 563574275 994060554 389872869 523378995 830903137 450946220 769900443 634872602 717251539 806448435 975106857 713161976 257771677 140392808 948820751 718774382 855499750 82478139 750626715 269435289 910116556 984069057 131596637 208660612 630422741 45529757 205859049 160820085 153970257 911217065 889244841 297413275 113562896 902504407 555922095 910949658 640758124 127971253 112508737 671687851 924636711 687846658 743368195 564293331 35865257 428637602 836126426 143025964 224667099 59695001 218903726 918987670 347940353 594375728 148342861 707605378 980431809 192722388 844880742 153156861 739853553 246134563 776866555 26534245 422567444 474144677 383922941 936396136 414532519 391710504 928095465 619609825 269554326 379624496 828098981 58610442 269506112 465238152 830049766 761421294 58897000 980071659 288567389 257867628 114208551 761142872 941777853 619088111 246201073 574368247 969969431 806036060 746149600 862904184 562177704 501330052 181544009 104291326 409451335 492993475 939340166 97865098 999978697 313688159 571484284 282003384 514401880 924737389 62768983 415821702 564589369 453932453 614243196 477153808 365080206 306249883 111783263 283779175 975594543 353781718 874977401 837195200 870684698 285985114 821338404 382362038 563534897 717378575 340167183 931585991 63034171 237622811 722929248 485452636 349121152 827264033 148404596 797268479 318841307 914178879 860474413 247892949 3985531 366244928 2079132 5020478 359372962 505631417 553565245 133963559 996304766 686208879 285243916 313733953 950067102 822045296 332861840 615901820 948870918 560082010 349737426 803285995 764629604 140706016 516759123 700928461 296239454 787240993 923044732 753658278 627586240 76837638 705702889 28737794 585046927 738748269 311821752 91163034 6579839 295164882 68899997 692076164 445449896 283299953 183664501 78123773 629290706 570212430 311418200 655625822 822376142 573458789 677506619 141032465 310165323 880637401 826232990 787867945 395193157 723551420 613407622 966262238 732326172 305811482 357262327 198468372 749017870 836415616 916747969 710926715 477381997 984130795 166066222 274082260 362727545 439898330 873358775 283448893 38542072 89504611 213992430 839628456 191269336 201794327 226592571 902062205 843985353 90220787 74947255 704802544 86315232 172299893 360456941 534467241 336811223 915807931 725247109 461499141 174713229 272391469 499282817 285884166 79620229 226904542 72734511 245409334 517281825 855983601 272726746 781872910 140666321 662717398 690162581 435039552 163596979 111245458 593733732 610341290 369973646 977247756 444355659 681345586 602462814 485771487 901438249 890639322 645586745 803337017 244543522 666817699 319035464 944505416 654087623 84963808 348362885 777675981 433970049 656906693 224451599 879374230 428614778 626188712 299357668 372929513 904899026 577836271 281388961 34243080 603999823 74615293 683224932 479245561 896473998 529236871 84204865 146141764 85417176 170189740 239738010 879327052 847818444 990792251 648936111 490568081 514537552 443397973 339168601 186310412 255482076 303112663 442306133 950862330 734765140 848587279 63038227 831735443 606513563 922017722 906951700 904593180 163128368 651268207 674660238 944225751 286978672 438268106 881817762 237898780 471385606 728559448 463115227 463180311 887988055 36820544 256822465 370390705 702428336 976404123 353000212 136148891 718632204 960796680 959965797 584966508 561089326 815260774 173237120 622670794 973375904 30471913 142259891 631915817 994019454 919313683 122539587 147497088 587640736 53010441 884270 675628145 783931437 104902635 383248302 352628807 25064116 549648380 490726917 570416987 949570347 789676870 704564748 941592434 819150879 287737362 279237197 946538697 671485356 690025281 754990234 897630341 733861886 55923495 289149654 708957207 351312079 99810500 497062327 48024283 94624916 840065754 987591222 738724238 296664343 393466609 174535854 322540009 393075483 591750044 949624409 545774944 248790041 463255872 454376391 168890859 15031659 605409826 755749301 763894483 520335092 257069551 878716757 693709449 836203927 383677696 710161848 862015094 948157264