2091 999278317 205190146 142353793 537124197 96320053 617585303 330957388 553393884 459033796 321824993 30771224 141354159 836740305 107604719 934275376 247254414 893405919 985642108 486259597 433623829 875024014 649413486 663603874 603235165 948886779 897639508 607991076 479487405 506681243 349202431 815879535 917264844 65047016 400633428 137288136 595070735 192014556 935306990 909051388 731783927 493611965 563547949 382127003 429156069 391238888 429136935 517356461 489919347 751805995 496462538 609226053 552130141 903363649 785048086 787215136 927774031 165506420 182516433 384531720 606339490 164900017 160030872 546298851 276516378 699470906 669437617 14837569 777963784 288608483 25248337 104811571 801720380 772348734 41120228 74927282 719213420 534467787 660609441 525410428 542548327 869896425 314385020 806745830 21308542 559060735 699203763 591788692 564552859 900450694 160014097 333063408 241080509 245109569 732084004 871763977 267335115 435055987 514707736 11225278 522468104 849008817 227278931 251684795 515860566 174045944 625566088 907181530 132015749 582008242 875204131 956227166 653087829 296144573 196382779 930391406 892418590 248682636 343690099 319258417 264305093 759115469 46751534 675178992 253540440 120921729 540835098 893095812 101600917 411515190 888470824 57146456 551372933 530554299 141364057 180209868 406652965 626793844 525887483 761951090 34447310 508720104 518355349 753377767 195109216 943716991 841479127 576666902 716998458 582860229 996535353 674647914 973548318 49898656 944993589 125703327 526509745 526690731 570685070 155537181 811211013 519373346 813129643 921929840 71101739 137986331 711340830 338490685 228753519 912323529 77636479 426898916 807431930 971575990 323170094 418026275 512896018 305098564 880748030 321764373 611696657 31187473 486935438 327298580 208807499 622013434 535800529 48813823 343779268 473493031 340394370 291144037 309015343 819373816 845344824 476471654 307166981 154346294 369031633 912946523 941443185 325297451 201325581 679272791 423814876 866958030 532956185 321233582 468106577 929955421 560237294 464014181 647814208 138178276 14987724 155641946 868029406 728242488 267105768 7200680 61682548 497175050 771911481 164281776 338926578 884077346 730392934 588642811 485732959 829088546 244892429 888777822 608334001 147205996 951346237 275784851 769691854 862947803 945460291 416674094 774568887 519185631 790305915 675266408 417628701 66994802 578027807 174974652 504538306 846750864 976438510 529327097 18689606 686478533 243477793 481064758 293840266 679917704 470737722 606889648 872452939 130249998 972356778 164465297 592441024 619888405 98764100 638460946 292959134 756503257 133936644 755680575 683649877 347335335 94381487 629764680 961294739 817967118 521810828 449839557 185526911 361863867 484572120 108295773 116523982 791216739 566944310 10106703 995651056 222391104 901351703 212920316 751556172 436471314 844658317 387322306 119797916 618104236 738497313 974067240 201075380 359694573 158923570 468422968 537797277 141789766 646908017 91660351 561402844 628133375 453355400 638392925 94777098 449707227 404510210 569035885 471515720 49517316 935948513 591476275 842146406 240421331 261194895 630504653 935339272 122176064 380810076 689050186 635059958 183145768 790220914 660045743 733900187 514684922 346812895 721330216 719801660 340825651 668908684 326934704 745455361 830637091 533479519 574565846 613291992 820440795 953806662 404318029 231993867 739582642 545364851 526639844 286025558 995713933 917202552 822596841 463105463 730308179 862394837 795663307 787257001 370569933 579101094 60449103 766173987 530808417 820496999 529957550 213337798 322080754 340749638 838075569 2824308 310762346 22419384 504073922 485568325 646250172 385488962 273495960 305620239 26853167 79579686 541669796 900581592 918010595 491433131 68332174 909015046 955331530 162557706 672012990 29643423 625172652 757905466 963564203 749617206 657039284 638234945 949627821 703280715 130645370 245112147 811937451 635954088 681587511 189725202 773172565 566482274 807982929 979397515 699420729 482169421 746632156 764741205 185594982 364195377 249736351 976942769 604177560 46932123 419579861 33997924 964355183 635017167 994968173 844406727 529532420 413392582 563141435 459416581 142701739 267053431 121942671 21128094 25227041 212557144 235911209 283695799 476546960 40613718 178317507 929467335 734730785 310016359 981414810 288391063 117255840 132124159 606743006 867577581 125332487 862060170 697287084 572928130 874699362 967640377 756180014 650204406 813003051 700981352 599110032 149547535 708817319 985384226 232453624 137406886 995045600 779340531 764373655 344282316 51697101 881191955 130705188 264075811 630107122 648850978 166277288 611452082 277999846 132815769 620122 412618057 410086092 934062124 793626019 793353225 413097460 109869561 149772974 631616551 316218663 821555642 176775827 91381805 729612588 523517213 704655807 639458920 985179043 301027184 662014225 356673003 990655789 205421830 399593881 459188915 896326335 87528998 721596091 873059283 892966124 863235298 773424997 550641947 742180984 174801792 896946920 90348923 828875856 793029921 911082288 397765005 407881322 244027313 705544927 21388553 442204148 873717419 538944435 66720203 675205805 707989122 208919215 648369411 164186572 993991609 328314548 977969937 272411472 770410282 455529604 156731887 547175 52318209 396855577 974468796 364248866 227798825 611742638 648156729 449400942 774706204 2915555 692372185 146625926 203606042 547754652 425691641 582030880 15852606 184515119 674091339 999583041 372075469 81264955 961455574 277454978 854259200 581094512 476060582 133542661 868365143 654218799 321308296 255749274 518028364 415595967 930944801 243917883 64380867 483090134 91876873 622512522 101815503 554612408 396700082 349667550 26419025 494618691 662871899 669195724 938353279 548871120 226377890 365801457 415559187 279827636 28019622 814515872 648538959 598384562 374476506 174099595 803881399 429418168 370716959 814624494 93252725 842532753 106150414 358228350 588405847 783172954 451624933 681391104 667016051 68765266 248210815 464290291 512910612 565035189 315652063 383179347 777622584 136274340 801438538 741278611 22171786 714296781 967190104 874740853 317340556 687731513 233812697 350146857 781049460 984767044 256641866 870148380 532133126 432070996 179942955 112340020 847494900 10762126 942593228 655604375 387242467 995604161 808627946 264285169 735960253 826163124 804483164 62267768 225557899 371821225 919383698 854873333 927614816 74835157 466706370 513295399 876149749 105508911 737564272 192820643 142345699 104376550 764573512 213959452 594491484 138487085 517867808 598061786 224255432 683003303 822230930 400429405 784344623 620879333 822959847 236068472 280392628 843931916 148552735 765920225 899518370 835676374 994104503 433014227 815798844 824099024 632052898 988313825 772435892 231465723 637762460 996764023 819714806 462506880 504584649 759871350 273825741 214177253 602529504 997613766 362783470 677093173 549889507 246587601 632140852 855788719 845698938 709444101 945570430 774491601 234539419 852798672 168846945 78629125 164169378 563258468 696148808 970785465 565866126 28321839 228443386 584410343 34197138 770471507 39079362 950900066 473616589 427030936 34853258 470917270 916362004 251736540 596272942 589753363 924935921 731081779 433884009 670519647 766883517 84089882 541657631 707176058 516817375 197659510 497594307 223614628 999135649 206695082 309280110 329492850 726734915 191606669 55909086 860824834 583812395 575633377 702127290 241429076 120684584 358375093 86450227 544084655 393794745 909430860 622935269 52017373 820993102 412138652 450657371 971197415 865778084 198127158 849338491 320107181 313180861 830151596 641999658 682111928 47276198 947409027 518313943 951337005 888868432 55040244 9478486 909969262 186323371 76243921 662234437 644308377 247700164 19775928 265748905 777319612 840404373 948086284 226532815 519296420 331859433 259321501 365937842 503915696 678621288 297777115 201759066 798156744 763352324 797018273 582273500 458409006 310955513 118811296 716379197 303001486 374115064 496389409 126922975 905237241 81236612 870394501 96596600 41165122 361059898 662090503 990417151 43168340 496681150 614707812 873793240 670645168 738581535 67094626 333429893 970411746 748638275 531636886 960708159 657268099 988291194 100139109 403159531 975615696 938594125 785923090 367622294 417408928 947835939 568570873 981264622 666629200 399237920 742065312 108431793 152201289 877960551 802917650 257580233 73818199 824167101 918689610 368675694 776262324 745225242 245807586 732622793 542812201 589120657 52886960 693478549 220986372 207291868 40570215 524436932 173793456 671182571 155889799 873054515 426815637 18882450 259809844 314222711 798196400 224213107 256512874 137675730 648101038 319161243 969133862 232461381 722965915 946735068 928927588 680048631 370648863 390751427 85258474 415321448 215026028 562534942 256273600 566584290 924386684 948285614 574705269 404859764 539222021 542467201 244155486 334187116 266828774 522611906 385794369 321422270 800375748 747616576 480756081 598069035 104686479 979787301 707199801 303604641 324761200 658044089 433075874 748005217 932569309 128072150 921947044 655145143 14125462 600632266 332182959 895447250 272398 356301933 712172131 952823875 695838691 173778238 995002264 406497622 457527265 823300921 579308414 999839911 997123116 154489381 474602208 457462090 852076187 301837671 431367665 834290552 319052781 227611745 250397730 283651315 733446886 477187008 222662636 282589154 278218655 282901402 492055073 154014837 170251018 386602182 81901573 660846574 976185778 589769927 1247915 41667271 5267027 873996105 259733808 677190619 765607151 666091196 69924459 336985656 302044217 514230393 722711065 226386591 406677462 427397317 329699450 453920387 4460118 326938646 454089661 56349322 141532915 216694812 56753834 373508497 971372002 103246917 330391243 779251625 81422722 487543093 331972219 573053987 691279952 325289492 209946841 76897032 581242945 628383002 401329873 986966834 125135152 961217491 121512378 736558833 805607398 439683203 392421379 95361834 456629276 541865024 221160646 936703917 818621143 168512058 601692196 115412878 988934044 193410777 226470381 115690918 249465606 424327655 468650078 543137514 608046549 962975721 629219953 735453321 763708705 426268220 391339681 436966056 283265904 169708033 412953690 602487485 8875521 426902064 657485458 269644168 747452147 956063123 452214952 702672158 536190775 172462287 974900898 151475643 241092779 776853747 934572385 665806008 895510670 899712568 33762850 136603241 117476021 85847849 552951734 116630256 900278125 918014963 836649262 409356734 961139601 29763301 166543947 444908248 217561491 249178405 538084500 483884325 969695891 671693842 760529541 461756119 480587296 903853721 307365095 279000791 519144344 882120086 878325511 784296288 326332212 829752172 558903307 779537059 372896896 549646293 235722495 678927900 26887679 677295114 149082506 662710869 752961717 298205945 514722089 276027491 608265004 813907682 962354172 395280953 36825916 706583358 653830079 500708988 874662852 309310094 190293918 557143993 641915352 705684323 280334630 698506544 983902273 173511626 564527144 467987046 814293895 612689994 681387846 55181780 501141518 526683550 303960771 55421897 997920535 450059457 876891918 764636523 318259617 248081013 317442402 137728661 993612509 89071375 887048360 998847972 970667451 718362567 178507410 207212986 109677012 497814483 174825970 500795302 806345789 908746587 79712515 662040247 95531151 577493862 480567083 75576093 587643741 881566630 70802456 639466394 756119324 567653327 391034890 62792309 641706339 87459979 417947733 965033294 369049611 691162142 664500748 300842876 734713519 917033395 787927313 569605106 858572676 717147429 688147116 579102188 104017094 319093747 334743994 244305417 814516068 681250341 5980611 561387496 906260779 938678504 136687063 559555910 9481991 507325663 953259447 847282752 529455361 439686281 959498476 38665248 663419572 387986415 911862872 124252420 502004767 750713125 85580088 912266670 499461984 228919566 247253638 416658797 943066615 780442408 600499329 916271172 54105638 662828769 529547421 970251401 200304514 558234603 572977324 442737531 517254323 830957437 255286192 909890195 118347165 11679432 282955722 639460957 498141649 931448974 319951211 322965386 73197195 16066764 33409243 98161633 824954138 455249958 742806799 752263074 860975249 698050895 838626463 998586675 841405017 58852196 861800904 177759862 638020049 745816556 279346277 406437320 271205725 615193566 492687114 781465831 537776483 757447259 433885697 253939358 463769045 766223059 188680554 647337352 40601297 543463462 822470293 949670076 733173097 7551402 107095642 296813071 54552466 871295264 272574906 541660511 311719286 904333674 822824330 34249540 624251850 248819908 305746394 375270412 888760708 82640761 344176880 421169024 900443979 98214961 627407281 555552913 949113866 802925589 89597003 539561328 284360544 995909869 93656900 283532820 803917647 409203588 724427403 572085767 928737454 41338369 404474566 386780439 293676294 911979707 687061037 924342 702193643 333575438 7919229 914356003 80751202 216167419 828429206 681202266 63174953 835328225 697343701 623834205 498516082 332765081 340766455 584673022 290905115 725171184 449005757 684637215 904954009 185068537 776914208 14567095 494136159 428954482 605342211 68404748 582490686 801174559 30751080 762375968 87617602 828223610 32711367 561926396 620195592 353981740 922700918 347626546 415494268 821936070 596322277 181689141 18821712 776786415 349127272 821920896 799677856 319572995 334574199 546635586 271253581 453312985 940529474 908738258 526413360 618618642 169625553 885686769 699295781 564781579 306524252 165079576 435643573 415793053 948905740 555615454 923352674 937452668 86707712 685831216 528275642 876283714 185384694 839974837 850767938 905481511 574067532 896954572 324716403 135283549 673126033 828457496 565671974 775019507 287717971 839061592 937338037 694922837 585092464 599549724 409735605 945811020 487360878 128854501 138035826 345399737 229740477 792788574 203070158 771552094 302847460 552323130 713141618 891179803 264591467 387261591 668376844 864281969 60012671 542764238 219776401 451259272 574833801 488440500 995843010 579704244 345645010 207369834 491654681 563833731 171181306 197226186 964983373 265402618 96044355 379318652 566271113 253904305 356394968 912878713 230247871 301231127 31388405 346501957 439396970 102021058 754473891 264331785 800815395 616305229 433203421 248596481 180267563 377789212 339849790 837697594 69697399 925294552 93506320 930324238 749015096 435940048 463142511 860123761 900822792 472152361 892118973 105424213 22721716 817705382 554598927 475267220 991055604 720278800 565325412 97258955 575884527 267681992 64683499 184218490 210720144 259490424 161475928 520460406 712759994 946415895 287947552 411693678 199394260 409206673 165768088 860936497 820671655 306194478 292336814 74600913 726883027 573562161 463417587 702200725 553888091 497291639 686432619 632700634 713823661 266960728 275954813 658172490 8590058 483541613 78554809 425459401 312621158 850019473 207883826 179472009 508300434 793201913 684543931 979658948 503645744 834247596 925609265 103235523 129760425 277024627 379735649 654962178 152838904 117237261 38666140 377440275 359641509 146745650 421230063 599163145 338495973 93791380 751735522 540101193 17856317 703199527 905970323 972388216 310174380 42064413 744170149 992778568 50085064 213899438 737816558 240144867 683207559 692769866 736987655 953688086 709401091 2136723 153221191 942493321 75868913 42496663 347724374 914918439 782433197 399357522 740716178 347594807 776803769 758296301 597401617 676225095 382063022 477567944 844839704 778282993 593254451 859428561 799438369 344937512 163991857 200429647 46155292 619019226 809811787 509700898 251624481 762780886 220191903 738683305 467335893 921339434 950041938 794687222 744073698 939046729 255450190 803054218 997465960 442761719 996108706 319458360 434673318 230000674 646499517 799782179 374992680 671733585 44373916 330536043 750354955 464547086 299943809 417205294 392043043 242442358 636017560 169910446 703049310 309343991 487276748 449947227 251959488 421813362 696527165 682910875 624711399 514762650 94543751 212129230 69107356 65330936 322215319 299626123 729478255 86219565 965326220 965468010 942686835 989563173 833383745 792306262 583849971 734649134 869128951 506420871 665330438 284619477 489095844 63241976 252592203 377615411 230885250 506849163 922865915 749284325 630417875 465711430 319604874 760072708 206859574 230404046 860954162 745220998 207275595 861737860 725585446 282847922 589841383 420021601 680412848 503227116 412276101 738591556 195655206 805132961 835705053 607178163 86684662 299364323 199060183 567256147 960939821 710567503 832243973 694313864 447222721 979886794 369662088 523937016 856211138 208775919 672779901 741091137 998715027 680648931 62579238 127043033 194306439 42735998 291694360 991069892 789349334 623409725 261803159 561191056 249335624 118767777 350902950 967305528 373928429 118574281 373259847 823092575 842799253 574895352 407229638 326091613 35326068 96482040 422279327 669164975 650358936 379136304 380310127 843610683 47347576 702751823 208006883 45084729 493798424 79339056 301568897 586642970 649304735 862652075 319834647 834039278 431341616 39523932 800226748 807279318 959011980 886531136 22920538 472274768 482002279 611763932 420366507 759259819 739638003 400600037 718785224 475978859 161843340 119647728 632063053 672264710 336501509 759235122 504811015 297500142 55767489 504214988 353930344 488522850 417836142 465356380 95640575 110873633 68556882 989235697 906937592 845217414 253462021 198277238 914198738 362174090 729137209 565597603 581188985 103741824 598960009 905390102 433929216 958434586 235120626 30002214 671109125 316503528 522669165 667259541 993820870 908061058 28111031 97782770 979167304 725863750 439207887 695467185 865699895 285960158 404308516 490261997 704852837 950496892 148944134 620904663 117975714 999230877 931034518 525639578 100985390 54861229 378284049 224045822 974449240 538828935 521068331 829647013 117464638 755310536 209284285 829919320 768286839 508714213 695574737 207127477 796827030 573855684 52363944 465669938 495884668 147925346 29710367 837150806 297374184 837953222 761989523 428691240 659932968 41220563 603604755 830246378 268386932 11664137 66891641 55811823 118266796 796183074 735869935 297535056 905293466 386841787 894091947 330632526 621675094 444124505 321920372 123354905 29050082 52978543 789757255 107005084 907092225 165427775 745496706 427199445 518454250 857083904 52518468 174434794 221993256 680694634 463216955 712381903 936914617 234632625 80016982 900733664 747959341 275966316 767648566 892248485 231162524 969034764 341889690 856648395 534315319 457030708 925648948 325682885 662475108 474825618 682691588 538992187 104366178 72409518 159857356 112225194 976686077 249359919 65829486 912064777 905107415 370047003 203070273 754944137 627800672 913670833 152322985 851037138 938518055 743185180 555334206 703886906 330615937 401367526 263733619 495910327 731750878 909430697 165848897 768335521 420095451 906970832 781135396 714620271 464933285 98119095 881008718 540829806 802848421 600585221 236558110 254184981 368499482 554455236 522360990 602102017 197335636 821480591 281792323 239321749 593832197 41862437 32357635 112450075 684899456 687915778 267920931 970013748 719433984 729434046 458731822 6990958 108688507 165051850 923364943 129576468 838799015 433736637 905935048 567345230 269909184 361448563 597329467 465984583 537999365 803396101 842361781 261271036 132157145 210807617 32488687 516742910 498172978 364431589 656262265 483367145 329569183 79847057 846199354 908804813 397329229 214776156 991692160 528339872 324016428 756220722 990205039 401341424 585125166 46164600 637394375 544411184 209304866 593607746 898244558 345386585 674444026 357884378 72592067 796312922 104906167 788891691 375113285 96180183 106679559 239036799 713130526 520828892 486384307 833259386 611489565 273099343 378336905 388831665 334319514 97858076 81013352 566887942 110975237 883716616 666536990 355738314 459714094 953695079 806815844 846473785 233623159 771733327 674951816 859994454 115319276 989208856 690658093 757727771 18902802 269446239 519779218 603524745 178715809 380890772 680578445 184333123 899773278 639218169 519357996 397350634 525544726 348382785 772685731 867309927 742461133 228652132 495622214 545143481 923985815 773363710 426204859 677960412 916093663 863743430 533728706 258241150 818948525 186416989 756650470 868454661 466524715 429757885 212685966 797103950 543137758 739323986 456959821 370574740 56381866 947550240 743307038 950225872 243579326 915341493 612295737 141101385 869213414 56252098 14123988 36441421 559665656 213924102 356635751 523203190 525104891 45462545 195642983 167244583 751447219 122197302 185762540 639881395 181653675 700658218 396679828 686449655 536519765 379782842 854703479 525317144 871226687 334372242 341498459 696892641 929066824 202141702 10437669 961447001 535259779 103670712 416906210 970595046 429497495 333783253 671387430 252383106 537859647 922937493 91779363 424368965 993756846 983211886 442105043 801492074 838196148 983132819 69794444 725485442 719530594 947379902 103824703 681892610 148221857 497650305 257249787 927398533 425659323 830444918 673104062 650241874 845710308 939290944 596494084 379220221 972762809 532535574 292294487 326441602 941509949 598798546 75662249 686000395 225640035 611555973 337312120 638589784 743651107 428805481 378915859 394295255 232836492 746347450 583610150 663736675 971678327 734595493 369610177 396622451 937079343 723456352 198748583 24146073 99402343 557979532 871874590 788445498 722064953 39497512 324804426 193658662 66270560 127414454 796552889 611946417 195767522 734506606 738231254 521885103 164280202 62052608 649227562 866784786 194535545 737624178 212001527 654025660 789675250 434532133 204284076 735620233 246823726 329422439 697868495 716430535 750302543 969960539 521144236 829362440 416695364 749907933 829703847 637321193 104577885 723328131 136247240 325221292 790052082 491679131 155878913 809408145 972534978 698834433 424077363 222130462 865619868 463599854 238482132 544651624 860098982 344646863 686999742 976758942 782821957 844917441 698987575 540774417 501078593 336603668 962002504 194079700 742796668 500286611 149131219 178495919 150666770 437151381 812252912 61247308 911057916 705782134 371690957 500588861 431062031 226018260 242364374 664958249 54027547 200413805 972582744 30747310 953179257 58662005 115475603 857816544 600570007 901065998 650516249 704022432 13084675 869447721 151433663 977705756 939029013 593882634 964578247 404376888 564276377 796923989 523120677 334239413 942018271 787173670 948621215 337836807 822409616 239337801 705556491 826878877 452177708 520222146 109400382 258961227 53557523 609264382 779527231 602437894 17855498 189938969 94073936 555763597 991163518 871948270 595094919 698718970 156935944 131635824 24791131 861941412 885277190 548957392 767966496 211625686 885013798 38667655 92800744 904733614 233235335 590194229 663563808 795810585 46293243 436163506 694065360 53188948 846013919 34575809 26861023 233298572 88270617 460462169 938911812 554070376 760664618 851362610 567216590 646245095 677506294 638111042 546678751 475484931 814874836 692679377 667991691 300392927 112719445 449150189 423390094 511085272 2778394 673100741 345987509 36619283 341732254 398877237 968876856 331100175 698170123 979740141 653054030 618297505 169714178 658404943 679515901 694806562 444624701 955760462 935231954 477538414 744017265 696003451 437483072 831713956 122019564 555890280 788796875 882393129 318320648 108604116 6597402 992560427 289906062 253643192 807600069 926973383 182925608 388662491 745223804 460986081 940700278 182991381 395697627 980082845 449955213 600792233 550731477 971822596 217277212 642557440 659731103 484327983 446736926 497897093 289175702 572267675 753811022 574722316 486835148 118876272 875855776 51283518 993658158 52332912 907044656 52191403 801626859 376218956 97117857 495376130 27253084 638909682 914096747 742200504 552161698 850356025 187117026 146656202 21626048 698547677 307375364 312345161 728044738 279826532 30649394 518425454 361309521 853297322 879240812 308229877 749096673 367412384 187281661 806822945 990956793 614502639 93621254 320069252 590123803 408425102 214658873 759010317 91415767 981196010 164763822 867520905 943545174 787935628 526660255 347237306 861049586 164713435 571994955 400294460 790100959 375946802 994357312 443771517 127364886 966713695 712234088 310663378 950624433 174652039 338850511 761536641 168482511 928651456 333282661 932291464 230688360 880652659 248212406 432611837 63352358 163951390 843687582 925008191 604363748 510828499 661098890 884941868 992047292 240133798 412425140 593948070 761192621 691616207 246432502 451468676 944517481 12788412 993526315 992193427 177330759 268992525 965408043 289694826 327086050 178084977 701039750 598409656 182083571 595547474 966581345 927100 244059239 929188654 351511086 703380222 407230790 526435801 941953738 557487178 808510578 805699300 692951242 689598068 169210374 862169330 867040504 247819463 574176407 818150736 788661863 197071911 731699231 167315249 186425245 691267234 448712343 163538838 15933462 774830338 375200459 419525090 11445796 358747965 878808632 903885111 619941358 942692455 7821456 737763075 735443248 148738941 48133870 152741315 47569575 198373817 633412978 809161318 23058931 877205286 791267781 645032186 161187371 871166773 845620828 80557145 469059096 969622602 867092266 724758664 19906213 809115483 478149179 27548886 792754587 659368338 288105347 948652263 861819422 628461109 12505389 135362046 720910039 52657146 267908376 733374372 163766224 956851824 681483653 227739863 156998629 581804698 519336760 292177647 755966087 432572349 425692564 846871084 225831394 381749392 275699837 376471283 946448530 494017283 768824032 20659214 753030927 898483852 130772720 601612004 863363468 955319893 129004396 170091934 742102218 42366568 683184088 561626642 307520108 858094367 540709782 521374502 57607308 656871233 165748828 735695806 146601632 359165467 225833275 217417668 388662488 160432175 481645775 15101490 621958219 603961239 94141908 11448651 266885555 255786696 289307578 992875133 772144745 71158257 464074833 10384544 609512630 80323770 249112510 495698683 677974193 538375065 968762645 486891018 833298328 28167323 876859287 943372623 4652540 29200486 491330523 802432921 299936251 196340223 204218081 450300358 849634995 754902897 946258715 568777072 707108643 749361388 3456287 689697824 855587732 519663286 522995343 947300482 797635281 216693685 904245986 352397991 3029284 837224593 15200734 699882662 637787957 851583265 509954763 229250416 526610349 66270916 381337849 359283922 654720315 297399452 360277379 806248131 567096817 630584317 956949557 535936983 271349093 597928722 484810022 3235677 944825389 527712760 820954398 707757340 463544593 559754881 60855465 508803461 355795771 339853178 686575478 90001738 156055461 816461018 464149289 628266374 500394598 483736759 608106564 44991283 355939031 151460097 366935386 230980939 901156954 821146138 488851148 732283484 676883219 488076579 32249864 931548238 61995760 555171116 151031815 542070792 300999538 46951649 58912510 349331825 185020641 419209806 947931678 675549079 113118713 782807462 739482178 111877821 252008461 257320839 516805918 253277128 193399280 658438602 463358354 242499241 378006427 870085053 350821944 138823050 721552708 113668881 255626010 65263929 256416687 101450359 569436695 163283123 362570156 2348126 697608420 745679258 850346242 641288709 562408325 224716054 127387980 542665410 787427465 46884139 612723553 773086583 174013379 294848063 170647006 538476900 507847693 623438361 505173594 760103991 973050611 280313411 432292785 82119788 462431931 146195355 467313491 60796320 306355491 6436086 567938781 452057805 203113444 402902835 830249345 852757737 341043073 283920116 61037594 949390817 242767643 186901508 77458248 450756156 850356902 683584560 370295889 137676330 768909713 21519251 760885589 666418726 338399327 663495660 201600125 102866821 557156973 51833441 193804698 406147653 441777145 184558144 844591041 337475873 500772032 698639367 52627056 374253547 69214263 383850769 836585270 698733645 911585463 349376054 688083273 804288431 445932197 756402523 389300185 46084373 176502068 695643483 297216174 28563936 777810170 386507988 821768990 196433480 458541669 248533175 955575641 805016072 285647795 379629245 990136672 776155542 119529427 581776683 402839481 974107189 231024282 865723188 508458 799811147 601273596 49723942 992480662 57903464 311715369 238104819 482941211 62563965 117629637 39800653 342345754 30369686 958014709 631129733 823954017 331807210 647330629 842023180 222418432 575966194 346982710 602861929 17217950 235716263 525610195 602387582 107016719 794157965 738134696 535753637 946671656 130816265 804628944 160696828 235333862 3244656 320943638 618970358 265033834 521014730 197914561 93262967 394973219 766756161 955835844 597962474 308478550 354671016 830579001 742628262 688347126 90456072 65530271 267159911 434696395 886179853 859036767 175472551 839094224 190075073 720379167 214047154 586524007 567833154 628478448 154262123 350246640 864739271 80174253 486562901 729563149 206630487 716799762 671580218 42393686 768086858 487055351 668389431 828217380 901053129 484008867 856007928 125864111 923793235 391165167 950089446 276367964 179145482 405621234 275390035 637990304 49773754 918981675 251118824 33081827 96399031 548579422 670425454 797353810 967747787 429428286 586961315 682558074 918150329 893186424 884415692 219739844 868678951 435759277 279107179 49292531 124622597 930728672 841164958 783983194 523722346 693012316 370374692 669980118 464145678 594932228 323457184 695961142 681415657 106984684 175555730 916140896 461727814 367728779 805390324 970285521 800792525 760141783 408309234 220681640 740095845 191300994 235284473 284717840 363247410 658712129 660143740 5169021 702943484 660724830 535145079 731301186 84882451 867023085 736444438 565636057 687656719 629002291 681356313 98852745 201232874 787498315 340191427 841405687 821092588 479833270 986039317 221080281 170265731 554927342 590326450 248243957 276640622 93551853 391067876 273828142 856130691 673180877 825440256 718835946 120451299 329920505 276874702 441671039 203673907 252774168 367350378 742336343 260030109 152102590 29638992 513566751 219512547 471596421 613671113 454900875 449156705 161416714 59380938 760940196 766983589 689065003 704349477 379746748 53206419 420182121 427049640 734625793 214504784 573833367 321969927 100505328 450808949 702609395 852435535 200789606 148400326 195656211 693245905 33958310 628853837 44735191 543956171 319145563 215799107 580707139 312301212 440773878 378185237 653733126 285765161 668753986 418818783 46317673 889876295 981311184 640623569 917700622 978440140 64999505 428354705 581855802 331539377 431372815 264603293 331814741 490057775 142934791 498948846 967317 492018482 65199394 652565167 756376481 899057499 435825642 546674189 439714920 96859505 377507796 136680868 275112298 872388116 634725463 655929573 19313398 291255258 734380395 188257582 103167799 193634198 226943730 856191803 773198299 681931285 382568250 458171579 1105885 981088173 682891218 990379169 626073718 792421947 228653751 761913275 800754748 375172738 513430880 243086594 593118534 271297660 299083421 632520404 135507750 727815997 940773564 254583386 795103083 276465313 726908726 584375943 930372349 505700971 174071811 615743866 811975410 178172361 937472324 445878137 997595519 211146944 452712852 133591953 744594424 34530710 414127949 389571203 175382318 52839688 839482814 259476853 342351899 543022950 290287638 286138650 632928532 658243079 272664578 149416631 148446332 442211835 383386194 697779314 694012410 285646367 166229475 626368437 73676541 674786914 986571045 870097107 773999861 25357400 361193799 398243189 767021529 802017818 415230664 775366789 94407694 322607090 649503868 841626836 211329050 819656300 164902039 220940910 350288271 435978109 293190362 701532155 572723997 76637109 592305399 679851731 302297175 718452502 935150258 719312893 534570539 870502487 125736754 722636434 357949149 901227364 911375397 414624203 483120763 552233323 635262980 988144125 870583218 955415895 592455876 495959636 59184339 879556941 565816643 204114286 19869700 624589052 744244360 406468008 94818702 12006538 630989119 107266321 964623299 933413837 414967601 559914461 126993471 95554668 661931324 111859415 544656211 269899833 149467278 797426287 567828764 785448956 535716595 271892321 990233891 368418569 222928279 865007849 631616060 718336324 46295200 287353971 644909022 382802139 18865147 354946682 389338390 35703021 853485530 321509188 754286770 71450147 114749492 922348628 795869728 351055049 149607973 463346529 576663466 603141336 438554853 702221963 975870321 976298410 823319106 603548977 191915190 184914056 163601587 64077890 821809114 284446244 484861445 734847353 409053010 815522294 251020227 12215788 705761967 200452757 108747550 920494130 477542190 18425357 695875167 109988949 960931811 221377665 641291859 52015511 286435921 21596190 17224197 514206091 187135356 25408057 71767170 464300867 599417660 555185248 125413185 160880965 130291578 481892009 248642648 250704490 608051779 641625117 624292086 692569572 12380345 541975873 225673233 114300156 515657562 332738208 717321951 122072510 814990221 189229932 896117521 643377215 196511202 974745041 546126751 49030886 979180933 687974420 831911170 22919635 734120366 810289126 813156334 73207381 487650644 171442026 909780527 515458795 612912777 638349292 161278763 191314302 337198904 187893689 719023118 688029499 894666645 665760268 820680592 825881346 443093507 830959165 283452342 415480814 360048606 831318587 798434002 501816397 404272825 33330285 608179656 519368047 246119689 342852756 197756025 694823938 684801686 558456189 607496773 652545711 478270705 206431764 729584954 488608872 265979590 957214391 672733607 973786327 942785903 500270774 127159039 144735279 577517668 269614005 508090959 636574215 613906841 937323735 917304281 874372087 883157774 374123022 692528771 986308907 658537996 130558144 696009226 28060053 484632166 495437102 110371279 258561979 907103238 875825628 176732794 931113044 963209026 627977137 653368920 701454832 289058824 106401616 239198680 103872170 687438621 355150200 790949755 382909188 817343164 938488943 414537643 837158792 816348481 885669084 768214431 848412501 631548168 281459505 901761987 670377453 51880222 812712861 613454385 228824669 551225652 365438994 469504960 221423278 256179729 334544264 605262287 94247793 488825148 180753489 596658137 346014046 21858483 161558645 1477552 844367843 380034009 671076567 439206975 256250300 55697767 149218467 588524828 464641473 525299401 662365096 640379799 383348200 273589920 518853711 199243446 702149739 131271339 399138730 611311892 197850656 535462301 234918919 724247536 469552104 784133621 64662830 648881148 879732643 428160423 211039809 40457814 153002843 281642260 425673165 884943676 928522189 487670042 302400084 628249281 871361934 733417307 783916356 272854601 873520798 343656038 601347674 466944180 425999991 413900776 885714228 381526978 741429698 194828909 650707818 77027391 370400168 403282972 871023341 209838659 205601661 741524165 852404150 909160296 807963481 566935441 109891664 625747772 163018739 872614543 198905833 324926612 748315904 412806359 235606135 200488812 910736095 45363633 855133910 378640259 229683400 657555223 560669575 171284588 778724697 802226660 728875182 542517422 92025483 174066545 130213320 266449295 314924142 927489174 980306905 3592038 286695747 627744563 419716817 215569050 353424153 490752917 174419308 478570167 766180707 665050797 923317144 489860307 131339866 87970025 985916019 117685214 585520627 390024428 338552241 929904790 814678794 962079405 878019014 46408693 797029898 732475503 540427224 165102751 678723071 801936594 257863632 389238486 183882607 861807351 652992331 969243779 545040040 503707485 797254004 809758877 592102521 760650656 572858153 281216507 233028296 336587483 257022505 30243677 438783883 570943847 667785276 212757254 395273150 74165488 655654603 565765590 933721677 404557227 897031121 56069033 114600117 604844302 871761850 143595106 807995203 687003423 886903512 689724359 84214190 168781097 230066248 578793745 288906642 284658542 882576797 412039009 109212508 118681695 336687795 613343654 614749748 226214098 206374105 981921670 490812801 867429132 268530695 137216584 207096580 236376245 562794259 645352850 336101963 159784277 319633889 595396857 996660434 721170973 218810761 416720162 395263486 453885452 50235053 836200925 738536096 143994166 865685534 158242016 891058018 16428555 370253896 791999771 335505703 467711110 274444687 896591555 415584013 128308781 897665423 94994907 634953480 146944945 766667080 244072093 696795736 850786548 107469761 124165973 804397841 108683492 654564984 635288113 471450770 866423835 376497489 48154792 867023632 151837767 329872007 952424398 265607986 163831478 466059841 546441109 510450160 734948339 583770155 864733176 358333533 709942818 265633808 957468395 223013073 15637522 257351411 49471139 525383209 889170 996879176 772644253 789606569 669116311 748080899 64346118 587071868 378797474 573162836 248419376 463292345 9051059 799511716 126251354 134098931 338953626 955126204 128651987 586431918 803455678 751899760 204467926 188879943 18403761 235366067 692236328 332311325 974863656 236614270 153804086 535020078 27898853 858470102 298771413 420759200 477355574 899072614 445765224 489111780 462819103 728720038 894734230 199703470 922845485 689849032 795698585 965333328 49461950 871951665 23029112 527942312 25481878 887156085 610096930 58556926 978316734 624745342 552843488 343770622 80101309 191647206 411254436 432011146 372238415 522078584 48318400 300901814 422134769 99419965 162890941 752653418 377283772 711870687 151919470 947337677 638829226 237549453 408666096 586968397 505022978 7698148 627346560 14407260 868095327 2189104 802784602 248651622 7896990 35605135 255584 35196409 871398116 979398841 793529284 990406286 967361816 49389565 640541103 965654144 993191600 869664627 564741633 718287738 221740919 131436162 638824470 837320850 917064757 903095251 847838858 941185377 199856694 422227649 725851602 615877623 643980031 223775154 490022545 291625939 658988583 247712947 941570619 755640538 862844664 894268133 757719806 376127965 518137150 539689677 308777736 189564664 391214896 602915385 655948922 56015614 369164400 557821124 509519033 825529728 375296743 496457917 427663924 216841482 754926046 861168219 72025069 486899796 662552785 571932452 272246591 832731246 970222864 185314779 766984103 699938281 741089941 375576216 827297942 206580385 7173449 275500072 950870560 796417878 662994979 184549922 624441436 588904422 440013335 168476374 560505836 962012736 436791990 534887231 631323168 604337273 825488538 775101207 673598540 881420208 792990168 876027709 172661506 51545787 309922016 457036539 969651193 954899915 266157888 650454299 195386682 100915926 918929932 648765739 269227314 37324302 628288893 681566011 198540600 114460984 274196370 611392261 490661319 94745369 976844290 383741437 789823193 36830832 900780274 751796243 556511445 908726352 541974357 936228726 224525825 795607310 124311712 575532443 646797805 772403338 351078679 139865424 327913913 626677713 673788032 261119090 997879812 799041274 53410156 789715428 655728624 163561862 784554271 714916355 763805132 798669905 145926790 881796873 498685440 955772399 12143840 848064652 844696265 313825065 666619590 694339312 109464198 911065565 237996961 980331173 757273993 702284334 440362504 237037881 737570034 259846310 600941129 624788515 496153782 905897780 382088425 664449074 835486567 140409574 798175210 485342303 843573154 752610805 547371652 645968268 535385503 855047978 334934148 876670565 207458609 687297202 664788645 653138176 626240932 593606042 351577529 348360596 355226553 32773783 802149086 499090485 869217518 411083866 30821658 24006614 44717738 392637313 83543878 815897682 70069770 514793993 831112846 127627164 609338715 279673688 65018566 479791421 10205026 192189554 887099018 740294096 179607295 779593397 575512719 30407847 463933880 320461782 899896588 617805797 474718346 9296525 576972342 161350234 901092710 228593678 565621512 23384669 49512037 702836424 249335267 232211640 104859651 564372311 925248952 637339044 653003818 126284641 630652860 81845781 377415986 523334631 728555171 853024529 986808755 137902464 177598801 95814469 355527964 223114912 575201318 409244228 614814270 439452263 455934027 555695366 987946685 659922610 751275187 435959173 891614674 635191212 57645841 587928217 391767747 768169824 236981517 3626974 284664598 898045171 400985540 195713213 171996974 890895708 846082038 452706483 240976763 352260736 412637903 389205260 513484926 568540053 44330102 297418568 548902565 609472054 855794806 559323385 611207567 672611011 17629341 392758852 566529173 309659126 542946128 67564267 716298856 738390425 193729772 827771253 716456301 155649654 125330191 750197200 352314041 331259657 370067506 575617368 507726843 135519798 558914598 583000415 684765269 68166241 540198739 117795 722594034 954733351 934248323 367361319 206210612 345486107 886373925 430141649 582877735 716578588 603554991 984313004 452062982 373051748 640753726 501632514 138718847 274438205 929658386 279561357 399473467 947543694 553550027 574851608 305421977 912962599 984546286 903646838 353352056 605106588 926593003 589831244 113695436 20042196 589880823 20675637 798811860 947179570 214230393 122713596 768942930 887385860 883834078 871390299 498032669 920062848 497894074 810405421 686924872 554242457 914375646 161538283 482861817 973721607 374358296 497123258 389419711 50569723 316708754 823339828 568658707 825720638 767504687 81351365 405765570 174609289 171774599 365956973 370516517 21794352 628809087 965159913 437886964 934343138 924911706 941562393 158424329 618390968 20487466 562987301 723108074 949884048 115968028 115286670 244210749 477483430 751450570 829594196 658941211 709841773 434130040 436994480 733983715 232032198 427247570 742714245 67331343 170805271 231684223 722097048 13612427 45878153 56159332 455266170 938303657 7070425 496044392 910024433 398258683 420162047 120367135 704685244 436050971 95833221 245113208 204462350 555710762 634076411 578716795 169247749 818795134 675337478 111379875 505733346 322982696 811741411 750498189 811682863 894693936 940694489 561548397 113879951 685555232 416487120 261849329 158318584 862195731 508867811 916377223 271500408 964946582 730168511 458585127 587314748 445022278 553914561 413300962 226656969 187555623 38832549 749116378 595608153 918243365 740835528 781868125 433207762 722824988 434777743 326153281 584298900 19768683 12909055 476090206 26489709 157588924 205328691 837916813 663946252 997493155 675259303 833726311 696611707 998226421 883032011 150761699 517910115 659983369 336657705 666453154 550392918 578539617 137452424 278115068 439611945 475454897 874016067 91783952 726183447 587109613 658366064 997948086 193109046 755311288 549323399 36793912 796503881 26653917 514833097 25123128 306469507 708014025 415592862 753856949 327963242 666041764 613364426 815497405 904898759 145256445 489907026 720370732 371435411 503304143 466708439 743718230 991856412 607189864 641875703 665525538 72589137 383184527 655440693 730623999 397855685 468709026 784779001 19817319 476941174 903494370 430715275 343651446 633342284 935388055 120665029 751870696 323241935 81860119 475179989 863990663 987843055 173552893 407942927 486888941 899112934 802256563 72616155 573806719 945475202 456012649 308974472 201059294 9562869 634265472 43977166 841746946 310058689 496617036 555745075 398852187 78416203 714529303 194447053 770188652 967822715 290382551 252721361 145200437 547392511 495281276 683193716 72081872 728805987 833619887 957012156 367743026 49768672 407660318 133977644 53620498 555083153 224048972 453200319 934733165 94961665 98498194 24250260 213646656 835671296 648501329 830714067 702807114 406755070 772326204 754875547 945408681 438480181 620343147 538643793 953273505 188407979 492504784 38080119 760848235 604743054 96818622 201674974 667595556 6237507 228155278 921359113 724561991 131771755 547856986 975409965 474613860 969102017 670430330 939478675 506270607 523735545 671589424 550581317 659626573 813128027 239896558 532922361 384120119 55957292 91959788 991087278 620073333 711376863 504378847 471966168 62891166 270458145 221672386 530000705 349716418 609494399 146687667 977209585 120101352 549306955 30349772 658176333 670258293 926589720 309113937 399264573 928314060 591629561 157708094 475633472 572073750 954593903 279316362 218985109 331713386 158550135 53869719 546944567 322683912 450943466 609665123 612029259 334944552 681960531 37666707 200749829 872784243 501437549 297963551 363494725 119082820 988957971 698468283 927500003 987433586 5814375 79193415 403835641 847594968 635981952 46336892 495837903 959339515 914243925 869079568 812792191 477038239 122384323 558162252 586872696 916474678 360057011 855281794 301009138 646978368 752714518 191927767 307216251 326055264 392745262 511504732 910012366 255323558 892986267 71767023 723261294 281472468 546589689 578044249 779771736 323796412 978813736 711113305 789859031 181887276 632870531 505335430 646051697 6914427 746131475 887758464 156416028 193580678 224045468 955390238 536547898 363058496 586664955 877461967 88875949 472494805 855846104 754503202 568775343 367786408 11001326 875360324 206503101 619035589 117914990 307902596 128409905 929932500 413808319 773132551 153086701 882546557 206838355 116390573 466692605 988415678 452897699 892254875 245537173 798605485 991011235 681206267 796122766 729159338 744815628 488108905 484230723 783887095 581994470 493762633 911343896 743292971 788081776 967837114 740135393 610418644 143134224 781503598 114000938 671901498 76570964 151559940 810995227 724929322 473171529 861916039 522408057 698884030 14062163 733829322 902543706 381432955 489752694 290811151 741933163 719739237 943071709 311553652 15355323 410755789 991669929 25359035 398017043 840006765 528003980 287820117 518472404 22243802 100939946 214465566 873784780 183571483 474710719 185792458 409442354 374460675 856035337 632131902 691681293 291778716 87674422 420755143 304539585 86863164 796410552 956212895 761709022 576677117 740473160 632070786 806754205 820342336 545471098 957595595 548615547 940175171 198375479 615865317 871415016 610659332 130128212 873824082 6163334 76091632 116512268 924831340 794853145 872541231 477679484 581250361 249232359 725158006 502293772 248187152 392426545 185017051 915310940 946094936 83389665 482439388 387866826 776194497 724467078 789054996 375623077 486200494 853884126 693319447 269241511 824864492 706028793 215990248 109713814 165384090 266299523 145862438 720249501 197796047 578729179 423596461 546463346 141604540 504933666 284563882 107043364 389701617 271683130 188080559 56061367 231339692 396110906 493104363 552852762 895227525 195730551 897752549 676030659 742168870 228081791 731084904 287435911 253577206 362583427 773169668 533769348 172869673 985388002 595827133 148006052 174553405 806178310 630494179 737627740 594666635 416370506 208009637 306196118 71635341 565807833 781287877 788840048 168589320 624953211 892021459 771232145 611504503 772796696 725692346 817930974 260638633 84290329 612458401 493280721 865945926 861580440 265700228 126469345 227422276 648261101 588509802 886885549 389203106 882575105 621753365 420227077 767829370 605817815 681028421 933319327 344427561 927453154 806097478 888488673 987203821 287788511 835204367 736302034 444363780 239998036 999300085 278824961 537511411 855369460 619813754 450908119 717873325 850911017 432547359 482922829 273427501 882940918 293742689 703000625 417147991 439164857 293151527 813127179 337035582 756940856 706888915 99769632 186844424 330912322 209731240 563300375 984219481 364947009 712271993 808748085 202695632 286542877 804530267 532586286 921068802 39451991 385564350 563456316 237612410 896089425 53158854 400764675 161796567 184713617 543485636 104422928 531716918 883651864 996390426 772514773 900684493 185570841 126954890 690184563 326601924 395559484 323540238 125148602 879946212 939099738 706638139 788221804 792288718 574170844 844883280 663927455 97801315 284937214 413855012 128052783 320728014 862367756 713146886 907815173 811464026 654085145 493505249 337198948 243954747 903937860 279366420 965694194 731664659 526466262 87340068 567552120 160733472 7447293 260966017 971192109 495840256 307846946 239427035 481960877 852359339 869908721 982081411 504080504 257032880 533103571 265023812 99932631 419721892 479941257 870980802 495715862 734371600 509676230 861593549 231453005 883396108 786053712 269707635 849594808 37981058 443665627 576997774 769964495 329098684 630146385 877573556 528052762 512915419 610169498 129915641 799016469 847702118 98289763 307402231 355054534 349675157 255821797 187992136 656571305 243488198 375467963 975309867 8376229 402169342 557738883 877183127 882682272 955376368 42961705 866689635 99428453 249218815 387068384 997500310 219418844 325469355 515010297 556299812 204339220 882952538 501805786 210434271 96225046 277043129 118359278 330481489 11530933 558986381 127283584 652340059 782707328 481212645 698636315 546099637 69711508 495286937 686605683 86781130 300850914 489433225 14552049 920317302 263292962 594649685 176468887 193037589 951937368 716881366 993445680 822873582 401657192 722274065 904321528 302151058 777520850 85582404 661817826 594321032 68595742 604757934 168293911 625921032 476713575 43484106 487606669 111172185 158366128 605534173 173660090 722117175 467637803 809816311 982229323 987687676 694736640 230728742 91947412 300704641 988957904 36259433 900332814 573372040 80502321 834828139 761358449 376298174 981807571 592667496 554284882 401671463 431653283 410568571 314675398 781568444 437684656 945364082 656404060 558915406 880136511 905317198 93977274 579438123 744671554 152920367 694353127 372663486 695012147 448375460 211726717 212952466 279133059 463344396 174861546 158964144 707491078 783938984 641276248 806743749 515618049 746198842 260621276 35948055 553867701 931155702 301389884 981563074 224881140 786305953 203971612 646928062 514761354 120303690 365124012 345556929 323883696 102233599 803255482 724898769 225027728 237759445 708460262 175446052 929282671 27271072 88249624 272793097 940008822 55720370 902015711 335296645 491983015 404551540 630402595 706654995 942442283 254020734 616782916 454203335 471131162 393637591 604698183 225074098 170373442 338157686 893936235 259283441 884654813 935603223 629709271 518194958 772799726 337973558 172968895 87566696 22289236 917049375 326079896 380863972 627227803 446855858 727728764 48124903 866505189 620525822 24937981 914223724 449936447 313977929 441862307 401509810 890779621 495236289 82311139 63093761 856333939 377907731 852633346 436149003 969735239 829981636 987565489 933450594 774094625 382800949 891812757 972476834 125137878 982994409 884516217 12244434 548963418 411505402 707260267 493857981 779880452 501409126 886898251 759518397 539154610 44554983 110261948 739606065 335406374 650921794 332929350 619704520 25090468 152238154 370346225 48887543 945541676 761733688 597405432 327571212 804630057 383480727 288434887 845012086 768274120 334304396 673669210 485928288 800706814 458137866 776326615 487351369 52506887 726316925 641502725 300176767 77304219 588815094 121242903 586486984 235156665 382283697 179314318 907752220 780262839 918149439 681077155 2864899 465473991 110212174 944569280 406233828 759907690 510821620 346631610 419679219 715325077 481761407 676151745 69213998 450143088 298266682 81278173 321594382 433212599 64018498 669139486 470120840 49933488 348812720 486757781 795471305 639491198 177554986 216791011 282235696 894123191 632046005 131417049 73576489 702128328 215191947 405267808 387073768 68783461 127623344 273167649 629642956 646534802 158461650 965198083 568766804 950592788 729418242 439517321 516072318 93554534 535454059 353898862 5863418 851100690 204781178 222867974 801398367 596699479 249201939 584738941 15910385 621376971 58712747 698938276 500221494 680991968 53577726 911875541 372700351 97861651 901549406 316741767 812205844 78123580 79882632 842502561 941583268 641617878 146255011 925127935 267203073 137029553 162826059 49109116 197915627 293765612 577745376 336609307 885068690 493440469 459174341 466801810 644569355 315097052 426043641 830388687 199142352 224479418 582529927 636759822 412021375 391710790 476223135 387421069 127594558 837914959 414304069 118682143 974744211 936176999 464250083 281252609 12899623 85214946 503054796 891799263 718160652 373897369 737470403 144358072 941702201 727461856 226424786 745470699 475214578 688408110 870110291 933726324 182334820 863045984 294687496 561054305 792499843 223557672 670399632 70510757 702950217 727765223 758457364 51273412 934505959 427138676 698446404 539308828 127803437 715712534 927477692 784490162 919703387 53129592 846745831 153510821 48003278 938132404 932603102 764962050 443970645 258867489 871260878 325371027 585097394 52588238 28476195 632319828 423205378 999925992 214542790 837109795 976450221 231328911 381419173 877661172 621595126 908998618 673133731 355582184 902875350 648943741 720887688 366565364 926749679 71874840 75284448 202126034 164793961 222500067 393123455 381252167 499346239 449158820 230793810 778495129 495153403 387816475 410113268 217848653 16247347 343074416 877767419 22647566 518967574 655262532 71827071 762690237 599597628 644883345 773223847 706956501 528039889 655153050 863573167 879060874 409365102 788862078 918578148 549959110 311429658 169329672 110350354 461047504 651491598 919633416 240709971 335619929 264707345 262202638 931320016 501741303 924951205 915918651 453357436 198606322 646729449 738551438 51394760 245374897 426377305 478338146 48038852 193655929 173841677 308554769 561590933 869935079 777062189 611894814 962953542 92161225 874085817 442788632 944618791 434848489 233318028 150041179 801293196 768800206 353978975 71164243 512030551 689705715 552247303 274527179 150870789 102484455 829018353 589747621 480185338 818944660 84793559 529358462 903491716 927371674 556539020 755416978 877538045 14404920 905943290 126825261 783225856 400956931 380588242 670300007 46232731 329307434 359910678 869280674 510670651 258151960 624504348 853312671 686721361 957643606 342334283 961852580 962662780 692067078 970367659 554624628 440985602 69242553 348265143 432954032 903396221 15672472 80114486 888964765 303339664 969125177 383969908 326052660 722826489 869440624 517433246 95030749 65066717 831912547 800362095 935777128 108069585 404019560 234196602 729901853 765947719 989111775 424183770 963758356 388909195 698060618 253354665 723334897 498587136 727897753 486415779 526457719 391284152 521918099 380928672 973241999 125065437 141395917 653361469 789378243 430024684 590417341 75330548 586335550 965853767 608971561 779696573 261843723 967777165 139292489 817576940 6217070 255244913 926168892 282152582 803983629 233856288 184044281 788502567 391654061 461548788 356786135 44446154 419772712 716651411 557853479 533978106 931859858 781301323 799837521 234251023 214437408 252659552 236876482 931187104 312637089 718583787 573999790 528844816 847919279 463675042 539235185 200618930 221882202 810345177 564514413 141502023 568679701 750847708 10537513 272557803 713833837 98541509 995522482 562307570 491636791 557024307 966653960 993013742 581304429 165762903 880643516 95177788 608070472 291828090 352223012 577113203 57359351 116440212 51982852 498912471 747664142 322043607 733264521 57311557 283360450 49487930 75563526 943983108 642741613 24261686 491776263 456793315 641444130 673926989 831753698 430651479 674532864 898630705 656250789 573946853 900268397 605882417 830549078 570949729 378276882 782944500 546598315 806543951 575534616 903697469 876625003 807900511 241849076 108651527 524567292 426750279 816863624 495910668 75506702 348963215 376222876 208294181 988437271 420676404 648023227 493039760 733828965 145815528 555680646 463504178 211633827 229922643 282365060 753832162 481619004 949029178 767949898 119191529 123652604 941813254 80245942 491850271 597827942 929324469 102525907 633437531 38688356 940907057 113783329 884517584 260614914 792317875 345156228 728280948 459690288 325031045 116360516 239642957 391813499 773424219 767578846 148339640 594014114 732330827 231726553 304118747 65805231 579569699 421047202 727991106 963889029 527383561 189248675 727293178 762855399 900813658 714865918 752919279 963252958 466818643 416193584 835953838 476331977 341022060 334031265 169053945 473515564 604298018 692242522 695582497 830214065 487243197 251130372 939794342 323076131 727808774 248304364 335561801 786970358 768571404 601713602 235287362 449012891 391901311 894463344 261025291 41730422 215991578 197189565 61920290 858801556 201626667 924514232 421291776 544098772 259786702 606354896 270814934 718683277 634317597 819028635 751020072 362490902 152302816 748006024 929546928 75128439 660644952 611279085 218198373 731194404 206032619 225297471 71829491 692577506 280695627 952981683 676573713 629891917 78376133 898109020 818216204 481677867 23564317 884685247 400622398 83733318 200715836 236383114 638226693 652393023 688207812 962757677 202334069 560463688 171323176 309369791 260264618 825175405 656865854 716123578 355411139 480072489 481417674 621769545 566675643 213461084 594286678 226610106 924241350 809960610 832835984 790332798 202547106 582336806 961828497 402606799 808664741 955058786 781022734 242872586 481698432 52356213 115279834 237612037 950128716 671568997 781432252 991078600 179665980 731930235 131175876 882379186 420759387 662095275 657172032 522918709 966015432 242076359 904033428 82460682 271550250 337609679 570528022 925189501 169283145 613032603 227320231 42931099 171628484 928958489 528530384 644378193 56082305 523396558 437146721 316827390 505573204 361276366 221661820 60979422 293270029 89434911 770989463 835603610 627549863 412284997 914859593 366207970 557809722 87238829 477689349 933609314 611862476 781041102 488985710 7667269 965607049 840492915 988326604 180537507 201571851 946353842 150483616 935439573 646461409 441308763 387368781 929070728 255559071 752729959 409645531 615027011 121826605 333825147 974691638 341453014 768584790 134137716 565895832 883923359 110062339 141169055 638646337 815084834 631099533 942859077 806783441 806782570 220607912 567941331 941449142 386568649 776900370 147591093 958225494 61796989 270543206 601185291 833172781 92662738 984942402 571855948 659658131 78142854 242381320 452174918 671383959 281671529 541145762 177723711 121252902 695685152 143931614 158322667 552198231 839804250 720973913 591464019 70117719 655311696 171750906 555427056 258710344 965539062 230098237 848917307 179352623 587035357 473679200 635745848 95478240 17457136 357584664 831678290 669854135 686951834 347945343 838808647 701812304 926077252 877250617 857476629 268847193 413415481 464605867 918200755 323192304 194804228 315190044 14113665 717927604 949370610 692093655 318628865 505275380 943794690 585947834 521362558 33087576 978923063 583171835 505929542 962999793 733714031 630854072 266374961 3250442 490167180 983228690 316329449 606753594 368670357 687401005 852573382 495800048 58573929 425385321 613859607 456215032 154091221 785635926 144211148 7683444 880131128 842341966 898035668 90105418 205846567 589556328 753816482 268581927 102244345 587661362 173008234 685271076 847093548 567448897 636857896 347876088 182085816 947520045 428653252 192004462 955599834 986192260 557998002 439923538 13974231 319534103 618505660 301800988 468917759 834193361 814372746 93220069 175585502 843143274 204949359 82592751 231220787 319549004 8702981 581386760 716269314 423739118 892707000 881382413 983404984 775226651 521633510 494468223 335754166 202319820 739212476 27110968 36298609 845371037 562680432 789488540 448723487 243519781 671347617 328823610 205458805 675413171 522959485 704133039 385422896 965580183 583562517 194394290 626061864 347546780 792037907 292511939 638291573 133503219 400350828 334193442 301914362 560280076 741481004 35556017 601564582 880074454 141472954 494124873 371903439 758468411 770326292 949703176 100101600 814742079 69311237 72680842 537464330 770647896 122951133 32103789 789495003 674755918 80998356 439215347 532740066 993336986 727055264 452398080 816682914 87761658 648030609 266147623 377481877 203793883 966474740 29434419 532125241 97894946 458737231 411400245 610241112 944634423 147013739 761244602 479833465 211767726 963122317 85385630 252715188 330291778 172696619 176410943 901581586 898532256 231706377 369438898 598938595 93095940 656889713 549968220 672508499 635219406 344909381 849617291 948631317 184384605 562184030 789120872 834592970 439604993 453696103 451860440 941564540 449789579 15256925 635030728 89526592 832583471 227327720 962736550 237126554 498194873 794346845 998684924 312325453 277538144 997868731 622454238 68384452 30245227 408169086 931374020 651418974 446390316 395286446 651041973 494201433 505701335 224369513 405167068 365231894 340663761 503216651 596786001 539417699 172279898 978982028 791206614 125381243 146333123 873198938 661289713 804325274 121171476 121673170 812774938 26693776 18783057 656986285 170878880 413817214 393648320 952937613 37817965 395434902 124904766 365062427 555165314 973799651 518148933 44476228 5602609 258248173 932830627 151118681 332572174 62744281 646472433 291489385 187676951 240717255 800086077 906724995 718491932 170745849 755836271 8635752 334318334 156008604 20903794 947649917 473683218 385343096 872031988 258038056 608634243 451854225 611034636 48631531 170979248 557265419 92376044 925688152 367230207 766855129 306562823 5295492 792262786 580901754 325200433 239236154 857376381 763410945 95018436 901102298 877035612 374761711 545356709 596147662 758639071 983626133 605302780 574363245 758800634 295451831 61947625 44130580 331072795 940245684 339274215 92337585 141438813 728510918 703996764 516956043 716937387 722760574 449886029 572703978 444649395 397818921 579708797 367706825 672499802 121091202 538760600 94966834 796602088 941358495 610721062 861091540 370118737 876620667 564009836 143196441 647442053 650660603 223569859 687933499 936652850 460956112 262141697 940542303 901997933 741742017 922025943 534141496 301673249 414048199 396793179 140040762 300375628 525428059 33605677 5544241 518429620 193975023 588500835 450039578 548273051 960032908 974787683 159996140 730694344 83396021 593639276 889587494 968196607 775734411 107697112 296758930 728330966 596397106 506582838 221240720 406223023 637704809 352798277 662760194 669572046 136309737 139835506 760550167 64909112 217369825 219289300 17574012 531571438 234009216 360803717 290167729 508787277 999070283 4088194 655115306 869736048 154177275 591146228 837369864 843591260 57039780 600171517 466670446 188667588 390999105 124367854 857073126 532390804 307868758 842156213 192687044 412606084 17313389 124939966 649822975 957764494 993933437 346826136 590806545 710769040 213670578 628667253 617832495 352036033 222928228 422977810 457907430 971976593 400222836 396765934 717290242 804455759 498758114 510397247 137827548 198682694 940906812 504447053 559773861 828180467 788766811 490433007 222528811 485184992 978057526 787176341 944308086 267988766 300297238 188001205 580685877 595156744 707007825 503286321 845996320 327857912 793639167 967650159 614577016 222019128 828998553 573188619 929043853 334421291 704550348 89947590 296243501 31022554 927878173 911645520 218895359 995111182 901396182 99609936 662889596 984459132 692529372 682155262 907527180 852536223 340920070 363354647 43916466 877663318 6733309 169835255 401587940 839704221 726449957 350509692 545795521 126120127 695486917 11393540 480352344 719713006 412201919 638230934 364321603 919317886 106276716 219154012 30767546 540157597 857362118 678701669 232709093 700483378 245127117 385567449 198073906 714411390 995344309 314054131 789029238 95407531 210931894 773679708 42498701 72088359 361553155 441653735 165834195 565291180 678323370 906110536 451343967 318167426 708187135 370915830 742010728 358675406 143552357 634733294 426502869 159280066 823939855 421466981 375031836 87202252 510203691 496405011 829451713 538794761 541370972 947991502 68235091 87235157 761573429 973263797 700590703 169871759 917915509 562265078 347690486 40346525 489852632 608701515 25488226 405621436 211749214 197470004 869574813 687280981 845973842 498331148 133527064 28466294 510618964 892106554 931694979 116232687 638276111 381467942 314184082 865656898 889323268 281189534 827394583 110254534 762964457 141868650 974757598 182641974 94585370 354927161 965270806 99499648 152205927 400491417 205393975 244898283 632701747 494181908 403246334 874750382 554465059 723584816 744667913 67903418 498212046 908525195 519645687 318359785 813217643 512336627 139160619 254422652 460253225 410774793 787382518 328842554 562985583 736006403 108078179 962152754 994206649 995263796 399391048 608473622 769489423 477330420 372296499 926738771 73388371 6772981 130282211 239758318 491973488 163177196 115268722 522370317 545912516 617177481 976908078 234131942 359926425 959495053 695914251 815730040 46621842 600398352 909508974 635869956 407732793 713916395 794514642 231024968 945909848 371990135 130384542 926534235 124329152 733953090 521585880 104129721 49428712 375094477 592542947 219877555 91820445 56284544 771852324 27508951 43205519 902774270 328953445 513997262 295104146 752910806 981796597 130528246 104397354 200811128 381042521 301385559 277044292 788975965 677836621 85440599 385171069 932454682 640294866 28324290 577921837 457052344 925105308 922252636 494876893 516410368 777270487 910774354 917840031 685841734 227521904 367617631 916047072 570576103 419817815 711141060 240748970 549120957 978446618 764365272 587088672 415088408 68133232 87641015 5991553 559348661 345613467 389998102 175927291 322140963 734478124 190416165 79728453 344677502 105765454 290854335 200633987 464036679 352894627 308912749 462916772 579790785 123140433 847476029 134645949 311302916 666695747 902786948 598716168 353389315 228554022 830140058 151085498 104616713 338229686 404189869 718055996 795795398 132558829 194639275 117333938 534384452 459268187 126103337 951266962 919302087 351506707 308098996 560128539 350125809 889514391 105547737 345615795 907621688 198201514 664595566 765943180 293936758 534892919 762730648 972214573 266453412 521610027 548338736 604597565 646401426 884512374 124011948 913527535 415963391 242486244 866209111 63275263 131719511 865034283 809110965 77018024 273408453 750918046 416521410 53318770 347351533 213637389 78499767 356553414 808426702 328959698 454083202 649365673 293952646 4649333 10407358 108277397 992029036 474855914 228549776 882245355 745612537 154984805 64578037 897334014 158208156 167938026 116648893 821505945 411706417 576475243 122879822 743481392 774189508 702412507 482582618 236492849 689549681 327839119 602864885 161956691 829587692 455130058 304218468 417226669 862542573 625477130 766901665 663322566 321297740 928852278 62179256 108244612 208236980 478844055 302396229 243684888 467099827 800147984 522497311 301923052 703678644 431378861 464355349 313985138 98326775 850158943 625239870 409455515 636711973 882666856 855252301 647578522 234453840 612472545 645212091 889446490 417303472 288358460 116321999 156185360 407859901 279605087 441772458 115767531 20549060 772911248 219074326 129060128 582226054 237189067 29966099 585937084 473804639 814913874 176668520 766373542 669121760 86758136 648784927 878751542 260587505 352263739 148763077 27412933 17107530 286562705 153904807 175926905 941340462 989603192 758974847 166409836 578471077 502220580 451233013 853601804 370474676 34899655 952563489 840689837 388054345 970847820 87456403 473095689 490358441 552570673 278617225 612054990 445911647 613387377 424897849 762389464 200565668 624803514 61616305 534711396 219107688 211920390 295471414 786972850 57427798 869391948 699886085 780493399 682045738 551392420 433205442 892663765 301492055 171551430 127404191 959001402 209478002 474865200 242922600 440811417 792415526 842386200 835541061 878426285 407707530 194496346 6810308 538513303 361650164 353661435 603160203 288128589 317827592 250072371 391373627 809892277 296024596 407190547 61572099 114269441 67995202 137214619 159505307 379747092 182582500 472659383 413289782 910819698 237993999 843717015 303950694 738651281 104289605 212282644 451127990 226102896 350443675 56676025 186425826 14376522 458802091 236399277 577235567 19897683 442148510 215821301 467560301 80486212 937714159 819800561 541889367 348732261 648027669 130242565 605611274 898942090 900149080 483847393 154755262 697459236 400229759 647417368 675326246 741885868 243544951 317403726 310697796 388388276 539239629 128263327 149488494 946318013 403002649 233638546 31065686 447752704 874206148 922251081 724193252 287901601 884530485 322957262 274385479 49573743 42170563 436286638 688023321 519831655 733589214 587611823 980131258 318655941 860497155 677262576 408218374 390471360 39747359 939979039 372296037 675906461 788895384 249101489 538647976 656191734 413892191 477095849 978491249 389286310 659358345 308627187 192757815 225211775 767150223 636115314 382790239 606985934 44548653 984517872 275258912 800797072 327514510 291224713 943000184 36376624 678658735 842491053 417895558 930817845 212581639 694378983 827054503 226060529 551116742 480457729 366129654 48439707 895609059 428634692 200960506 258900661 70090569 269433923 975543060 617843484 178066189 491203803 823676726 549439137 442583292 886468864 797234744 535669656 188275170 374208566 494536285 873645243 295017763 141744933 326999793 225075253 353860258 889451800 244352106 636185178 237296914 756744020 557430021 934283350 43364593 245696514 477436654 418335597 142850275 662032993 310277847 739646936 902175581 426372556 302715911 20150101 48830398 227439608 776014039 983671202 622829728 979169589 267582282 117283523 259187721 742645190 422848813 401072327 976305045 699069605 151629626 823659035 782641071 779235965 628256228 598199712 719705134 143149373 925184086 300667295 333392399 122843549 391106115 764942727 376134211 420268896 695063293 950292527 38003273 660710884 678555662 434726986 451637047 638008116 396559754 22183833 490420816 641935855 267835752 50809989 544049886 431952391 577121678 167865431 210057609 603897359 377480469 50284303 818063800 703873480 508566876 163099074 926943830 159631617 928140803 638718736 402687707 146167595 9971680 945563255 662150682 811157923 716385095 882483422 125290612 253562896 454798442 703675953 886188780 600515790 986751108 16772657 388003412 529640220 911152942 277352967 604448403 660913690 985555513 648658895 648222971 210997681 103326087 285623484 435983993 138101463 611143213 419472475 735238508 417767483 967118135 80268424 23105013 22392622 828742854 37381165 972967087 647096513 454181595 213842703 813679216 990923997 259824434 811346936 105827149 658276698 99253481 254517693 885896464 194559906 821820727 609307937 190534247 250743946 47330422 662078284 467272297 198984054 843060600 266858596 795387703 470067973 957259416 663677582 137355589 814133197 315936039 571592618 464375239 140552517 285365772 790132322 330857534 312516749 802249822 36531637 778728719 470075713 449708809 531642576 905935981 219888854 914634756 426484370 764312355 536353230 321625755 611507279 714099655 152984324 549475826 564186068 316939100 582942159 256432245 745570013 839224697 571203354 171807067 584760524 759016017 299424502 319805863 742423975 430948123 826537422 654340881 486050254 581948606 213900756 944596249 178863225 16308270 899081408 325731701 472238043 932749745 227493066 115360746 722614415 721837627 191445664 155581055 999022607 821015851 816717294 419751670 622909815 463313288 282637054 27152020 550273896 29505386 501756459 278803242 640483859 193825765 107319374 755423000 141862378 585097210 263974335 84681132 403293770 278970906 268262834 211315150 738337517 887255539 422198927 113252914 192940205 232416611 179091773 411625523 554919839 287397020 536000456 826963375 228247569 95675423 443275404 64229947 612111922 91346087 29623774 566905871 753972883 955579434 947973229 499047912 85335900 596472902 347539686 80089913 836936 484869612 718792981 305710535 680990505 469294016 700338863 34717801 658454118 790131357 89084680 673874518 488797127 780154333 585347190 212872216 14607261 441421086 118491471 762250230 442585066 624120383 78263609 607778629 97766661 54879453 396640723 623060742 160788283 54862321 929578415 664105566 156697740 478667074 367904084 706878212 391092813 897812705 689545542 318876559 837854938 608134226 279744367 77460441 947952809 310559817 217064271 437034612 927001512 464506200 382836483 394147976 606478063 813917548 407079004 690880256 225608049 490146349 735856741 35906072 441574115 771105624 120945424 998875264 734817892 767904878 440513338 180480145 618540871 206851228 552599950 331403518 582826051 680908315 684740527 444850506 426958681 591476514 172572861 938078253 112801743 907142085 292913771 218077328 222891874 982583297 690341171 591052922 3609314 444051326 646923246 173106275 849079632 572361961 444026163 205349266 277576994 322255968 808110826 349464332 865277441 853980721 261206698 830736998 293770218 39658145 65298542 669753144 986321016 272604366 80487516 361918600 864713539 919182034 567058811 19155109 44153932 973361547 967664519 96461413 564570201 927872338 586204011 271425436 213548805 265870728 241355565 817763183 820805052 540504234 113163840 661507222 84830781 217591818 460502877 975932248 462385476 419055851 955598181 145592984 653723139 465394289 514729419 78746670 702316042 231111454 123160080 792090641 920589156 683861339 426112566 993408090 184894172 442596939 257971198 297857896 49825647 481402476 634399506 85987535 242425359 108088190 378972085 79598704 860820619 144899893 39702639 636280938 896487416 870283126 342226986 693874944 197612053 143876484 615563671 286640410 821554219 703220583 533261110 374271309 990952817 937175434 675296285 936437175 358437919 633656245 468904283 861051577 670620210 725537910 494894297 807674257 827668771 87660666 837953244 616974040 644788575 893874307 921157781 588550227 804701639 962657719 151052845 677822201 68748126 565868076 164583880 563034582 986642481 431541211 716598637 575494615 793196500 722203116 226935946 230571040 170179354 83723430 253401607 468398685 867260204 702680800 669245228 586195036 254248598 902725791 395012977 901058524 166764886 176561368 450366063 122999938 467340572 224971958 684374463 759203562 501080554 399958186 156949193 764392998 957441392 285299260 434229667 910502223 204226582 101961262 259561792 571816547 500678174 940955364 375502682 916445842 878967299 107109985 453224355 332810674 122868714 660563280 268402670 63765052 388339183 717289316 677006667 886901776 453497546 665095761 996302617 116511427 301060097 518741602 74353280 687261982 112145021 168715616 391393172 808023565 352353439 295663703 385452571 328028704 431383760 948897187 400203979 386596049 111370345 326785016 104650686 327005508 859357344 427238154 229750005 179867288 294312467 418809813 531167666 436427609 786505357 733046956 18736323 725689821 390964742 832391367 496569935 719628820 909523743 209809454 871077778 323853969 231761947 27066459 510091431 73508120 181744537 230320721 367857215 623200110 327548973 867188183 937454251 463335879 158146108 669689231 145770035 182890094 886308967 199219834 835895312 172148641 935537133 456745920 165779747 66265260 405421568 311098077 723217949 787213539 835191826 382108314 615260574 977714370 716484321 89981375 856747570 451387576 356344554 22005297 6270728 464769924 248250017 460467887 46615315 979128401 391955171 810547424 79436829 813341231 348473580 830104016 976702258 862938851 811405063 855895835 373865163 874853715 836546984 62373981 356905903 743314133 106450053 505306857 386927172 702358221 654181294 673482870 945380853 587565536 553049692 652921405 88933864 545403202 380325563 488168562 16789314 464881136 436440675 864333924 977861949 351401345 973618482 381414870 3407850 343621839 767581331 923209338 155155544 792395520 325509204 291941890 679763202 57503715 393454276 855879660 582302341 607867876 456423352 133357396 333488869 586730156 220023785 154067144 770136654 261129629 462580744 622092221 252465100 897133963 914171337 861299993 800137859 807867296 137815007 388419492 60472696 252354345 491868130 291981817 753342531 504861968 167983931 183549089 887242772 391512072 626074512 538153799 953505690 736382246 246068229 685234790 647351825 858454197 593398564 10885240 965297657 832652837 294034968 295705176 235986117 720122270 292250375 292262512 279316586 373132216 743028837 884663847 406431289 951769588 321404098 498126639 284506696 486705097 838154334 83756752 492280784 534148155 682048585 997629770 398085785 161255741 921551852 174978956 385595727 15950425 662710194 606688107 45326058 534346406 167192967 409559270 106729132 20086496 436223044 619514695 200272677 744979636 601266649 797091794 266723922 56118834 74727539 27233496 76797857 404299318 514783409 777084959 862464043 424839716 295407430 81909957 361918331 454798702 194148969 26619395 575512131 208936304 811880967 304725813 293870749 862285797 428311844 651316215 635052745 292231793 139436056 775729879 760885169 368135890 921511034 338806430 322106075 783138278 836488352 454692155 400007789 728151050 184180398 551634730 903741644 681236774 592420611 603511802 468196284 483684917 457603686 334316864 370374176 844755486 248019334 925206726 61461883 431766739 525063132 89731151 816934829 284818523 514129461 620602263 119067091 374586788 881361501 326885089 191518805 196588627 577534783 336990672 389099377 41612367 414568074 994928393 812729028 785705998 569371434 846739917 260957309 955045567 453297773 485429184 688641414 612499793 744162135 375500535 344686117 459579542 771511183 521637398 317511130 11394149 182451349 2949449 685219997 216244698 30615733 272192602 170017754 885118714 93169800 897575897 932495643 831903605 797960584 721214164 742025533 652225983 341190015 510934998 846229121 815249866 566635210 84557886 63643345 53242341 823599 417269462 356773370 268165685 96191756 66411632 780336238 275039525 213899998 156234377 694447670 858455837 486666522 907211988 928966820 198721124 448751323 226056900 924392038 589782210 603343335 780690081 704177726 674465044 557509642 439028726 219041465 112511057 812321758 603779409 881444927 910020338 14339181 463834396 898424378 894026289 772045218 363306602 706739599 350088837 337399709 923489538 116269996 539919283 423575999 691828396 655007414 599864439 613836053 753874430 216678694 721803969 20568577 65926952 792448786 186154393 13686286 686239489 182363469 820474551 221053465 802552263 602592330 857661317 324823309 344457128 432288665 184844901 837981489 179836773 46174915 778844043 827954544 822194152 566186504 377953111 960736561 323709733 554731345 236903991 206538836 746206881 468019961 665299935 922233219 277868386 871842283 781910846 12601219 888259512 497670559 994306034 418892872 703823223 159488629 159536248 564143768 413345083 549100868 588187649 417061535 713573561 704842018 467961553 118834951 920578200 846728551 752512995 966979530 309215636 687771933 45806698 446381812 474162245 444784582 51118466 54853867 705624899 63050139 909688160 777511029 12368400 65466973 984392202 154704692 258453005 475270730 745821682 253900003 991061231 603893474 143540552 985970112 520582569 786832627 364641303 878741348 746074660 501620884 902769554 583737424 544623230 612006000 895824896 432956105 67507256 4366079 224727705 130322225 830110512 816784471 2471755 576901588 309521874 144813193 156068757 652068780 982606275 887089210 564907282 281824005 676144791 813088671 610923453 3370462 702156927 31384111 481075109 46593766 562655183 254127705 802863994 174099636 891254825 321341087 993093488 24772548 711373243 46557615 493182433 88590992 942024492 202459112 422340358 986653796 75696185 629031751 361477458 549396955 698891491 75233683 552983295 168282731 925423909 160161657 26668765 148071190 852417340 101905869 683247677 917510707 580300560 371122408 653232936 33393471 14439037 765035702 321989738 89591492 863516333 654368188 254961706 415615436 824907775 231755150 639519780 959503390 479128458 211898560 592352635 375294855 825353669 369584555 954122297 476597069 817382439 250206523 650232987 917943257 527953732 367327057 787142486 900806508 721966317 350671469 520536510 271159472 42756970 672306956 860094448 750503636 562120176 504975800 296191784 792325885 557166094 382003420 602019435 53055052 577128664 861136131 355106752 774107643 818186586 449413152 943644846 17441615 296305198 783029493 892794018 49661139 456585577 457924147 347843953 195503554 427021389 937393608 102306805 221815845 530889643 270505154 986554804 406096302 775366594 763822182 580055873 579171153 805400693 90624735 828956155 314968179 7660533 161997035 11979157 320216411 529442039 502815504 466973118 793403510 619564532 965159523 472534785 420436255 190317242 585733852 625595039 286384371 542585175 479400745 513022523 927055387 927178649 998636984 235597336 94294932 141718806 272704397 9331418 850712293 975946797 70472098 165242532 552391480 802808453 964766842 661381062 643501517 960869371 806910932 34402863 7750730 930065449 670656832 924922379 629131928 599343269 503641139 698672265 664234495 659233852 127459598 584453094 389494934 426352977 864650723 822684914 61458603 189313942 563176412 112848919 266916236 430797391 60329531 557331720 677317363 369409574 918885926 422779266 257151608 734153416 789497531 448920082 500947000 490939850 623346119 546365162 679457077 314776676 368893971 636685656 50496413 153057475 842190683 141685127 674705637 347971356 413269232 795626358 110798476 896808895 399837369 345503141 766208940 46721976 227863236 237414462 403138779 922384822 627287547 154131657 718056367 666400428 6939311 779501460 452373020 317887865 25240967 420584315 545989787 813106825 750953973 366782192 749427644 56181316 904294962 6151759 381110766 374424187 877059374 987033744 740946100 765530688 484088144 564227930 329555655 69183947 983900676 190041508 412499359 912285599 462510326 464580142 21752841 372565762 602031848 309625245 569771585 416759864 854194777 945940706 324217429 376994496 244367421 760413151 482801283 98157687 931610055 941867286 605084367 75002615 615583789 440598109 151180423 932381899 185080462 637093315 608349591 464084562 394133250 290997029 957436674 245016635 539995215 15657348 936613250 240162010 309189514 622282214 964565348 342535616 288951976 226535185 50017731 262203622 936885947 74664791 154025120 782335252 224297414 37852767 197170115 320829391 695292477 553631451 580972977 997519453 284671190 35171665 657914656 84461461 215775386 988466200 204484620 506880552 453109767 806465270 298703673 977341368 760737369 657799931 612708587 416868944 701242013 944732894 603502826 155618972 908568796 396340575 880094068 481233029 879680245 385331271 325671219 201702560 618396930 309976416 725841949 123343687 97912578 321421198 61154282 801837456 707859721 208770909 470843044 755312458 114052654 504709827 625796109 149015184 555858916 667005673 298740819 884946838 842911498 327669392 313707875 953541449 845476793 296849602 75261449 175129490 609215908 439041023 224021835 40406146 780857082 272532955 372029650 880986991 704051637 854555745 615075913 755969067 177594220 954232890 864296843 787889111 172617709 15060348 764946982 995276461 723730606 57457808 620261651 346393571 964050065 270634547 46613603 107166586 255999122 657898344 825103393 632932253 645045900 505899976 497667444 716547526 84274960 389677415 827274387 181923216 474994702 425452715 729037281 312008562 242292683 816770192 626767002 622647297 747272063 199388099 355417130 838736686 18399389 884663323 148942344 86660768 832712710 676234131 126107114 800277418 255081085 422766007 708341500 355080900 446301550 178900161 887865446 497816165 164307853 62016981 698704147 994582986 305181144 281423148 563823156 592861148 589058155 361005051 499558249 791040844 384695632 952387856 23420745 836002273 476208375 49860454 999687868 843242103 923952924 775332498 612337721 151180905 223401546 320839689 547617624 634971759 914869634 125342937 176724599 368690296 692394764 307691704 103259949 119945857 47810253 287411090 864057111 939680495 727466927 82403396 695961663 701925221 833217917 917424389 525873600 989252463 917932354 176432808 847193058 504025637 752372625 539936926 766204045 128922569 50646735 719990490 511765843 598299165 710766466 121640008 911731388 953408123 131024000 8037202 449489213 840034725 125016233 128407420 281467819 785299588 344195789 486314929 234819158 124379243 813597780 828715826 118505160 704468905 586514422 829370842 607338005 769226684 715509687 222504117 133162178 804869319 954658187 812301791 271086014 557550103 726126970 423535239 191630937 85210834 626738894 344181465 353630765 374268749 938389767 330751481 495224150 77365128 270328782 930064959 997664476 32875190 738067799 716644433 899254153 823585896 678842978 508844481 797881454 153649051 876284708 119859065 419802232 625662184 315582769 238077369 469813052 881196507 930452165 811716770 355522434 300856366 711054266 548575163 533281135 606636778 256579636 640319393 315173062 875609553 72536548 785998009 751568503 456581412 795101435 613742832 749897944 74604267 633858345 612261274 262490789 672772896 202910984 522019129 435363963 848381972 467354120 682873545 470910161 674688647 747168961 287227069 475262724 707179827 628600646 82277440 416435794 166918700 169621680 918289635 798023942 302985852 280552759 678828565 459098852 18257846 183312578 316326287 887197778 797879009 423456152 856747267 135036674 839577639 868587549 995251229 701021213 746290274 518494900 333986988 275066539 868448158 779004019 88465321 766850728 523576341 101848650 877031033 49876332 514382993 136946024 257555334 273027155 313384687 881604874 501611569 958641253 223158237 847542548 640856292 475210 419682977 376042683 668476266 352839512 348432394 712806835 494693980 867291757 145086635 458088380 607134430 307207213 583669833 121424110 366603066 736062052 535488612 872332938 367175649 661237474 793639012 55383531 538297413 43983089 45076054 636401382 644071024 551864539 499877163 818836666 550330640 874230165 229349516 170625980 963969162 270641568 348369866 193566434 864833850 847800571 815518327 918724258 189944223 31760103 710320981 558961390 698581008 946829654 694299115 59935613 182548632 94665009 794374611 673413985 263213548 33340948 442761724 80713737 185858340 522114042 827432199 585228589 500547513 834009714 388995156 168086974 120641584 564465379 259190522 968815692 44839835 395905107 461741679 499701053 171433839 977896096 135713733 79672348 385222087 807528202 164351304 262969876 853337322 893480999 11650956 68723580 635799814 335765258 10341955 800244625 906713399 915838666 329242839 644437313 123530305 632983201 902970611 214248404 809315068 750770879 223778729 451745162 118651487 756569003 917704741 66126067 235340486 860228443 346546211 560342053 257024035 817296620 495407728 33258892 884298956 209586659 875113910 212729579 279010474 151171571 838819185 561596741 568313983 878013624 834946824 510550878 296443749 758486668 793699420 962084130 927875696 630975330 480073567 119140525 890859086 1424742 907283503 920269646 24218325 417576727 341851805 450829417 521514898 302558709 107237500 609723276 78093436 297407836 340110062 380083582 724450363 669198860 178462814 950537962 738842376 225940146 681977695 174600754 394014770 955334318 604185632 621432917 350553441 371036182 968974135 742412153 469661729 827699465 29889140 758548439 951650473 310214311 153134856 539219618 60056983 150051882 420515458 211395513 942351058 79094377 411064529 872671285 424229615 253688674 61455445 492504206 694125009 982564289 935007189 420105285 438167912 526078370 612519687 526711622 703289937 645124783 284049607 127605374 369938538 167490589 105976192 84084988 32389819 582219754 581648938 615433587 880856760 854592387 495733144 420998535 483865719 604474414 656527340 913099335 728814939 430317748 567232490 552213497 458723687 914188850 387295759 427525680 647857154 278029542 838671723 206486760 184860449 425504174 294288011 448064652 94973969 398271188 577374799 197581345 754057016 222401954 108182344 856592808 399713219 19229184 838118717 155738200 251175793 791038156 358530087 753461179 404347355 967111218 573056862 863578798 419337616 964286867 776701463 553069127 999570024 390729471 853142082 909019221 973419917 405709202 171326556 195370933 100427584 319605328 995029353 316459644 502333250 485941564 803785936 744516021 346509644 986757353 997827955 138576713 79203348 18555260 410721110 657716380 994038118 973247552 910152868 789533291 924643812 504193189 923440042 343702490 852205170 944738998 172043278 977934751 151155553 202579861 325845612 995316079 343434372 283360032 168766938 437960226 132034925 918990105 974475125 372234487 501421692 374208380 497667832 875589788 569393125 652646877 354487790 201977281 994705891 588301043 419221074 238591715 842555467 917172847 899019680 553180846 697757409 823693504 47153249 25194071 361758317 985195014 665032633 783813385 521499345 632452640 293523258 922021331 379403328 843852437 282248770 946054719 859572254 418309001 908480502 538972464 774623324 501310358 209084379 444879031 368879852 278095510 663654080 508152816 745600009 962352507 118333249 129493394 818603073 515091671 804772839 687017963 495645528 557412672 25345503 211038091 284553744 896229177 533570453 297166717 504858221 553339656 489441636 487970861 161946699 594982739 689142477 800785805 971163624 523775106 184517538 320534945 98733058 356185534 431541406 612952368 301480474 67199857 728028500 816877859 901470650 437857050 321960107 248751584 568640056 155065077 324987808 761728358 406881523 988063180 892231391 10630621 97508759 776666086 321304401 589837308 139553970 254758777 411282793 424451609 779979189 274612481 819126351 561865081 598263940 438127144 968537725 704775782 57460989 18524909 870319262 70837494 311691037 557476426 901170506 728079003 705853183 695273446 507926906 608892213 636117032 901328543 499890228 375138237 840982362 285733455 293752639 96870941 815332933 104289719 705021090 821423899 912817631 648228437 527018048 898388673 876305456 196050378 681297960 640595622 585158046 575802739 589870976 310983529 899814400 364385016 849011288 980331296 800542292 57028722 403967432 934686526 187359837 552093371 113823143 422484961 230100668 831570642 383578544 48242728 927765094 18028057 705656202 493925348 352633146 399778329 679049324 528178493 267744608 780237133 894008602 299843746 599593687 129471131 282888331 95431385 81910240 841643621 725797214 400774304 984000471 22975667 706723461 707384372 135945890 717322481 211929396 959710108 624802720 111198044 791653809 994983434 581481107 549436605 769648351 495119948 562907231 623093996 917323409 686825112 205894953 893244884 654225874 911387296 824702805 483759094 474503036 774117085 315827205 816037497 744421160 477005902 989971302 863251473 882713606 29864949 746851428 962857021 673072809 763831831 988917977 513610698 299948024 419367927 479580445 156427121 395621504 483545721 317980719 590134109 526979363 751834315 227313015 934651853 991578866 204093849 823323005 867572780 936540795 681472558 292651104 286330935 970860391 567532610 489805923 450035544 882049959 784375259 187848047 133369648 928638995 351800715 565958163 603874166 367986213 377761859 201063398 705515009 903377643 767492978 270465582 762482876 573249219 187146981 281481667 920151866 663652503 72754631 321303592 71257017 745324016 791388945 720393131 777530736 166422470 457268365 797249703 378851108 91006892 588707052 986565337 55510794 134169588 965188406 605287496 919411139 683832820 102247910 908740815 481928535 586446873 343277692 845973804 96004852 493333325 643954813 377104502 221447946 150234622 837744103 375930948 143835628 94352084 495174737 928017334 430153043 235066422 504989095 285299080 340860065 33846211 462804033 451784193 211573461 62158736 483703664 102224305 316382598 12390970 646326444 139644889 732004196 188617284 365733022 947845979 838319472 127199515 371878776 94003373 698268690 341813413 806487892 678548538 708636400 129890348 532369137 854138697 201754688 834818537 48730409 878185788 840506711 126506226 50893319 112352552 964274300 133646898 954922645 391778721 176190244 576907096 35816002 534324052 223462288 972769948 824746679 663032355 552218037 766045118 177562766 493890457 470486880 589807381 106521315 426511705 658460155 412097372 277416431 450527621 949826010 586194948 733304175 385390566 270511544 751072120 184290463 234392787 694296386 795252423 85617201 508100845 619843555 380410711 163721200 546215797 979396829 116604170 168518685 105920265 323980103 121762068 846189551 878055015 185327046 148486052 939386497 168473050 980903735 324791172 369854223 172986160 271264032 896880452 293043255 36296537 177035455 475431562 926721569 341546193 661796647 354490811 345496488 794570631 982024303 57466764 214105432 607367986 321930862 106334183 364724364 512984602 502935614 380953485 173335847 546281232 294156854 910439136 643166825 946703109 804091089 235793932 768035033 517321997 574801655 498538550 113973793 912295439 238624615 856885508 373877243 965863740 455150085 789863065 82286919 614090617 725021942 452836548 737266569 642575453 713434694 129254132 347319392 174437983 117735580 499557413 535666452 442136373 306421062 345894672 529769075 180427922 396136524 657124578 444338743 21751319 128097459 470744513 359479871 881340802 706300139 512597643 43789381 884314393 945278947 501755429 101299839 977191793 645742916 205104733 983108948 634471649 549922463 632975232 358950787 701369432 827128593 443175864 627988583 998094164 83627054 765815190 749375279 13194798 739477926 401381729 473730314 835673390 153107767 865965744 39243503 739020803 97492452 61397044 448800736 158445803 744324289 98602589 542415855 862779258 54041380 483150902 472188190 643122441 520498611 632735817 589197873 835162626 120431556 413005546 953355097 975094981 342528500 735076771 618422049 812875853 554890144 778937691 428499217 97391620 317232747 817233602 833179568 577951028 533771486 136501272 732940249 506071442 461774749 806219698 856276038 558170137 141059494 705372523 203953400 123473725 50732466 486924798 685996667 259405636 449820421 807845927 521435598 376275670 288562265 482511597 50296530 384927342 999561270 495026469 151480285 294181123 301645981 728875857 225225843 335169148 327714269 277560959 393692175 397522033 241462220 479129462 329248585 221492750 462022213 703332350 419452239 504932331 435347630 435595352 536430738 221420062 59365145 260320909 478929078 272151446 242692220 592068617 512889193 70739794 412818407 239454537 291384078 383822056 846707042 886387290 705958147 699917835 541008149 796838995 156070161 354486151 184573160 823452374 630826881 622448929 637724105 436400837 955837269 685593043 294918804 914606916 297833975 18237478 527973852 648739537 655923542 923636101 673836468 740635098 866095345 284109441 283570976 669367983 226692886 869128292 864353373 801007157 340976770 23582230 832064493 818536808 530578310 698767689 411560214 903505286 148350856 395425822 561951775 244331610 122953217 903127504 85506077 617498878 466710046 19442274 668756056 614937104 146353967 289448603 585686971 579733177 982693630 209160277 170362346 230990610 759757751 504079 234279351 758382322 360240136 679291065 717456960 205459631 894654523 762537757 166488938 376864909 256506297 915300014 328709913 5781458 497038459 757101387 85079386 39091142 547046405 563606958 603061650 761988541 78508485 882534657 340942394 204977023 229115905 731262312 372969939 187387167 833906557 404554992 894280336 585154877 479275552 186085528 9548065 94840701 795481460 908753360 387331849 839894508 623115677 623049743 252480280 102744336 715816270 537169202 785680900 713349870 937410693 484129617 128118409 500611315 483750414 214376116 291853541 19857252 998346876 292727500 741491734 600877616 472169526 146344901 179046109 791633880 621003728 984509476 569375211 941148719 963274943 72457221 13747768 412700294 884966215 320438691 845686680 284445512 35272930 668314753 284513969 402526568 168088989 788922639 218109073 717170447 73414009 270614569 895730535 880109260 317796539 437067071 234651033 830043570 168250427 721915586 341009553 149805176 642665093 784739960 989999890 600528803 6990146 654867158 278665989 447074542 239043103 38906863 278338166 232631384 714151453 631729666 350322543 95331234 549859966 469005045 386204318 807732158 612526401 396888850 747892134 97991168 801219610 529350882 829757242 146736965 623315493 680725837 236044194 163585789 639744291 599025078 810093024 327551785 81743043 142689408 414455744 134898487 521158645 236686527 448812900 620234635 980281431 724939690 270043457 249472330 425836674 166994926 127188895 703298829 438718548 973845219 88545026 873121279 929236854 432261998 365233274 953881533 244591040 455782459 387165390 183710679 564157848 694520266 58161418 515650685 948558530 592243021 32283476 255979847 189114059 690539046 47274885 806041260 542763022 924247327 251735162 1308765 224839960 827249733 665323185 416919305 174960253 491593464 86410771 741909568 825805785 497283532 829550475 642877755 451929118 683985645 341342040 594434215 274640240 552487276 811377387 283349618 557060155 64649177 777707822 300762274 263358 285273756 874138644 446512720 183819133 575808163 213840702 959921147 729497940 273591128 681051923 2909865 394531451 755779156 526959821 550044907 346926837 284264022 352968092 977959352 752611774 646676819 25173219 67726975 944405650 306244594 126056222 383942265 563838593 752792075 841384459 779873688 714832468 389907718 166250977 300264142 767970854 443686573 474913563 680958747 474328836 281265820 682625991 913560207 762842761 620276762 555218460 313537689 246999604 798358705 994462275 430506751 429906259 975823306 979325772 590920294 178319528 484837078 465425303 759982327 195128858 960162386 423092393 89301285 33288432 782286920 336157708 112742814 607033967 91304156 199596400 860117974 6892822 317036374 131967517 748823835 785720636 52726285 210579970 163848289 913471477 198475850 95150256 889844666 896227696 746310585 977727294 36658973 934189115 397667781 913389425 6772778 843221256 861807642 697334215 931018497 643584186 621373680 211116331 75932839 888713623 660927504 914422613 915772516 274349838 876324522 400706313 820343909 602714522 677397839 642123566 340200796 469202882 204510623 82126585 533166238 563567017 638196865 20833963 561882408 913313374 516316635 94268750 725332842 785736612 779148962 732169686 746873597 811686961 528930172 233094628 123695700 447426929 502030357 702390018 510293861 480476633 857007707 568433023 784101630 249505533 430144159 475431970 353037609 820854575 186628356 396264188 52336389 849486271 123960540 664389071 901069281 100627019 524954461 149805075 509059663 322592783 204884079 680168596 765520058 454587740 722180097 612151874 284801021 187555986 729330743 466389828 629098635 444134460 391782049 424351486 22711066 397134327 965242622 789058044 532963278 348343112 459665790 324058094 42394369 225908064 755882663 619270534 496277482 977691479 294877923 499562355 371532660 191675177 817721121 304292692 833459186 982355634 975356022 731178269 921766521 351774599 914082936 854567198 64798890 847197889 596241919 820018979 396391449 303825742 163774898 363764910 811349374 467622308 772354297 900597673 91894436 843854036 243977898 368820659 396266754 809609934 650379123 751858101 656069519 491388910 257047180 80530376 885869514 282410701 252521478 902399043 197019280 70901142 382340528 208895234 350135899 250101001 827532433 190263148 698795084 81944379 789078166 3091540 709211904 174325970 967956979 695056458 83950785 101567396 592511530 974895842 200380442 271531725 833540645 705213074 406317037 327154775 952338808 926701708 446005851 260409973 772098792 555424666 40678387 79852440 23073085 173346586 67173648 152945556 950438210 938560959 144241921 824941203 360982519 952714830 855634403 464947308 484664097 225089730 84264287 494592627 206842261 617805750 484474482 328552800 906675734 805458225 215617304 216794030 830190844 314482632 977691846 101683027 265130382 50454030 416817498 353874568 303797202 666818910 875656140 709511677 988260197 922243026 693916824 798724793 669655903 409037974 682567257 541030116 824667073 927451225 960277849 709055108 963705108 819121252 818737091 555863859 705643429 437470239 483509723 13023357 297543348 583899481 161202623 627388475 687669916 859932091 99818517 914380029 802810425 405621976 973461040 72956831 929021936 219807339 86808648 697086212 894647901 522291762 901308228 803550026 306215760 513855692 830889967 203571644 943060565 624388835 801086904 852726481 980361661 643519779 428737480 58399870 198818174 465478158 629799401 28280841 406601420 169020330 260983360 61945445 226822684 413789659 224440124 33034205 88012312 575762979 657029544 697328707 345487007 202577458 783928523 85906325 321324470 92567458 643965530 653684383 821599676 822574985 164554538 295606066 103045413 462779604 51902373 394782233 850985428 217062824 424344195 598594278 23165960 721047732 810347675 578832778 19976679 116236203 503482171 76455530 777745129 114447816 673501980 154449210 937157031 509910787 430695176 343747114 374741829 402836922 20024304 259888332 169010656 143342472 433760648 652122461 232277300 588547709 440059941 368161712 607617870 358505181 371196821 734103300 926042706 312320509 455374921 847442789 42234683 763694516 51222099 908614246 68206540 475240109 301692661 546101172 556402358 555319315 812069276 576930791 94108233 572476787 117628886 132737696 868175085 442161169 546697874 396921696 381229647 565039356 817063841 242281759 246620024 640208268 16516882 441492282 568103671 982475499 509233834 263124415 610516936 524694909 774080032 244349971 995840616 759735395 194441177 977609584 340896824 208973814 374980111 255470910 376677130 899090725 812287188 850747927 803330836 329977930 192234412 387139484 912930067 739518369 915101182 49712650 362275746 770541979 555716906 208717441 279039184 372676812 590833507 733387313 357918998 351063812 242276264 718762994 411455131 134191211 162660106 649758250 866403207 171678428 381232447 825639421 132548568 552065737 728615324 593558500 600810475 363423779 720150868 371253745 592884212 27776507 609157202 54866374 367211003 392144083 108825138 157579454 309078313 342121904 204188573 165090788 710052591 91577999 692942185 474127120 317609640 565924318 962069928 553509088 991891672 78876393 370863840 28329919 105852288 514047361 183310035 377998402 155804092 215790661 387853392 646208332 390585142 758259579 974389804 566275380 493787678 730272647 235041393 482245038 157997802 178922268 301499601 491493924 869180644 220721493 927059828 515055242 530928370 642208623 740976946 338883574 488950083 739960338 565242690 358160471 229803755 487446464 397736652 106360166 366989252 397223224 627142732 933028837 404146026 82414322 611874266 981802036 138441843 97007217 732746448 155650740 58615072 351439946 488477172 368755160 508544181 584613285 169360417 388932941 437492131 999642501 606566472 505850558 419070587 279471775 496236654 477242108 750921666 517586559 185965302 558978574 34961564 961236180 346473864 114002414 821413632 848970612 109906171 166606261 965097674 327615976 938958018 462857232 310681933 483300424 488078817 303899334 907659189 492582842 915581005 660425995 893806830 851358299 898764476 264596070 94924750 362698664 470967603 860502274 565430785 76972878 264580506 107722972 333781050 708790170 875762733 589423781 902323717 288832963 170601661 501540336 554502736 726158942 652462257 452913058 466451242 731348196 812997766 561984155 64199120 871413745 236644810 10499411 490051366 440456549 445262673 704135650 449851144 856090106 727198819 935977312 743121061 936712894 938978649 373454602 573996254 792805847 815344876 820713910 489168640 948210301 961395585 757241277 493122529 115070690 973734379 350941593 174140355 71713607 849337764 533984256 612197991 766364041 498424769 366524954 852740547 247597767 993360386 275021350 119897995 129613784 893278305 905790437 982776466 778371164 698458562 764432461 915056722 105538318 267782443 532544490 428716127 619963586 726701005 507281005 90539445 245159968 438512489 333659590 235430362 171388153 544618213 378856901 269416601 887919056 826007904 344653302 72967415 835843835 969217100 678664642 861429243 295669779 710905554 225157946 755839233 763367644 200628305 252787263 835749011 175062899 864760424 139257601 352790060 322476678 190269663 567102590 883003835 837986921 485862318 234032590 630837314 639059995 563090061 96734265 273451529 262130850 931571112 995676421 632844920 286170759 254948816 58818581 42355498 926188683 413202218 501903173 700131371 757332655 167400868 677274754 817014397 515332503 290525805 548845478 100115005 358126356 909633026 580668935 444756934 97838504 196527289 920199834 947434156 10972714 952504110 101901846 868385917 887284090 526407187 857598519 496586101 675212750 769575270 50123618 382783164 791573555 863872067 749833312 262019940 345309300 898693701 204840586 899971400 728879353 275197966 282907609 53221152 705746611 770019837 849320527 224918996 425814797 324942407 967999193 766449404 221892123 831571464 754080629 375325651 920099797 566620020 278757177 597800896 601080885 539500063 898362867 167050244 403115205 125834688 387798036 682695687 323900568 175560829 404110743 48692975 56655089 356088468 462614264 437037619 685697245 226471717 42305073 905079303 778614665 151625732 570839905 70948674 773452546 420088261 625528764 798294516 96098539 845923521 972029693 911640349 315991734 405877377 531316832 58417336 717141890 398500317 638835912 908938853 175372744 767410766 205339363 310057161 419439661 318545959 521360771 667378322 474548014 569838034 974560865 704099168 135129942 557680383 761476007 785229148 548879761 520598800 612517009 182926161 55710056 37200317 269086643 780933204 777235767 961595375 355724022 854466751 911864841 735105782 136231068 13543932 603814947 682869971 775610598 781870543 518936989 241384768 910478095 157624893 296721382 641826919 726475558 237085298 276791998 978530718 294200420 549521809 448274704 740565047 156623990 461530426 867441785 833632330 569094711 703362918 415407125 44843582 401790493 669084572 856573768 523209180 993665474 922647130 372867071 640270248 725680280 147170066 190479933 75776642 701707112 794020951 910002410 933240944 558050835 576636950 567658235 639770948 252921856 79261196 449072027 55441332 727979480 109661612 565692707 799624803 445047723 589572596 679465878 27423296 103954752 219607255 569802455 799527013 160076362 780382566 870999535 317248764 95598792 469625126 756454789 650099482 530967265 342578506 559836432 775576315 875559239 393913093 79865394 735911571 332756320 756253127 986305965 248551770 287730937 883743800 431534553 396784737 262526534 986139163 275934256 72766094 140234140 4614434 254212789 672194749 475293989 263155751 615147379 847074210 405605756 844747375 985361484 346364687 742277569 985506805 531149748 534989908 59495860 54133382 266363307 152603955 43450316 72648077 879413837 46654051 618493755 95563275 133435502 662925614 768060788 880914093 468687735 521023832 270726189 433750085 516547354 843490356 99998420 569248564 276125131 86232844 525756920 133242512 908955735 488726709 870303293 148711386 128620776 22724266 382829823 219262680 838827910 511322418 333822031 305597244 87615341 683883784 974608935 260378465 26915221 959244451 992755718 143443874 408629704 902892960 890682599 249759422 398681468 972743181 617048867 218000021 689375266 481467464 742796380 991748056 360393488 185818667 500263959 822067580 991912413 45776402 541470504 965774067 109112411 695200885 800723013 186149199 360828599 731482491 483906058 238323697 776721152 680817638 622512381 92808117 848375536 708830504 2071257 995456851 312214032 862270517 152497685 820844555 652825109 842963349 900739502 152544644 615185205 633183315 360528587 853628357 499878907 328276532 893083462 436093058 588117466 424916415 509883326 66826282 758556679 783539848 332919540 174330847 781583850 890473164 317731490 204748762 48005888 723281734 250540677 479902052 576352117 710481811 473775121 443816352 571753176 334378125 1650164 323019596 297296487 752793312 81824283 882735357 671414348 730678672 784949857 661904388 635933638 293272702 747105967 30096311 934244801 609452411 483375055 241523412 268474451 672713714 385847352 725478232 933508652 694964480 96053323 830944261 551608010 223132764 663942691 998625958 375412921 187820373 535117218 966645490 791219108 134359634 939787513 325234207 415156300 697791590 351256012 23410640 349244668 797501930 844221499 191040383 545224288 258207115 104654525 526856407 859355492 884288442 169399368 131174030 888623478 195343262 449965714 546915294 52541501 328164281 93567893 131647023 486792413 137776357 260064532 946007796 867653135 199619054 723618445 376352873 645921036 676138988 55832333 660980406 642764040 494764678 445675034 402178352 222312146 700514281 674079810 247520232 97449358 258875257 361116038 926776855 500198687 718832109 667537812 877141741 898439649 75611956 592710660 428413184 788829392 141567661 705882852 76842060 264929246 307967969 619997552 595524391 153066795 692876003 455709263 453221886 823826546 628156136 637010324 404996961 567089748 12307498 989440264 469671662 473340009 547151889 218177373 224055818 123732088 927178443 865575372 874048511 957787993 57059635 141290477 838239453 108403154 217039678 382102961 977650631 400963606 339146993 403735965 922453533 169943458 48126634 255032767 406470703 704473126 273167675 107701022 801275914 205715978 522647740 716831926 912789281 896789808 774407439 70018259 242067265 600244989 819664903 33769649 808905212 671410708 166216854 670523470 282836704 997795981 6851068 173087395 396908688 557311150 688354458 951978349 188435462 251277469 834052002 161714337 843804255 694817147 937529491 694059137 15710384 478938204 25561547 564952171 764206933 605682209 955590212 372572027 346080216 224378832 641731719 429624200 514613405 166706527 512157533 145946623 729221869 792338929 525878188 551075878 86023861 725670444 996291281 745564097 44062952 859666267 849641235 221477792 983308309 700074633 575727867 317549554 377005471 560970004 208821727 326307191 806260059 421532732 141008955 170245661 245298682 672517373 656579465 490626620 588905054 874602539 482101748 604188096 308651517 390574619 289248960 662471700 936701606 550998197 475977983 923452580 672775167 874873833 182645021 600998217 934328029 454492140 706571586 166505499 231231003 288266260 719922493 105932867 840511234 934004822 697912046 316875639 447345849 659631770 196673061 342690916 357274172 719090791 391529390 667417682 651960131 510180873 250071540 101311624 402691781 45764996 375238877 239159680 519845556 343899685 510770376 337841449 266080175 742544519 447753375 701944398 641003657 609013470 254815143 913340892 459141837 237168339 899504258 570239138 242570827 468872491 761685662 871486993 190104650 559908072 537313407 234950253 233742990 627053395 577311106 349997224 136158 70951577 284105028 828371071 499244907 3005692 955549653 61676653 190057567 383657743 103936921 756382156 274508312 821198903 382041440 79648863 649987501 842747733 431057209 681718321 82437497 856864356 846508245 472521106 202952254 964143213 434177403 548268369 465085536 575574052 350845944 974801913 530231191 596572998 602657523 367377754 469971045 979976 631600608 138173893 457511226 879432804 912464569 136883208 308815563 771145383 281783309 802356330 343173384 843393195 436046781 751651065 335349395 433071881 111836121 449423820 719555529 712112325 505097179 431886666 998039297 784122596 80150316 498234290 32306530 236092146 396528839 186166018 986795593 265362745 868169986 114068215 807789491 192628116 162177418 538189432 163961874 365517086 979364820 875712574 838874574 648880758 922167373 667664548 37673486 1042942 64989600 891264041 277912241 254091375 961464494 350317385 175640078 333537191 477311103 519850992 424240563 657629291 21036915 949318281 339064605 869237955 589946093 991502149 924910221 839204669 235888825 780120504 385313838 72898145 623632837 264664502 270916785 460844028 929072424 381667627 523496666 82482377 334385813 457620224 188824931 502248651 693654580 790782310 660312033 437877883 346867391 673871240 672095699 796682602 161828524 93220732 562974331 327717521 904347233 636900077 461162306 13453793 808594273 626191855 316376891 134006861 455539305 231568262 39352978 408751212 638840998 564469336 253345703 275832962 690508767 917218094 842390467 330428760 74832304 711519428 200819207 794927746 246773610 147473624 163912580 194726535 527852083 360150480 57977163 355826789 956827907 688155977 649569445 116028800 232361333 489377288 810249205 779263045 289059901 79838763 529681757 955071946 294822406 15179978 447157785 699487071 584784825 810180058 801878297 465887548 11414762 167443239 990607512 88693674 782967614 601337738 99897775 3471814 949855878 354280827 28424889 597034328 542838835 14817998 186078591 32455535 465760894 223599957 345583037 550433080 829198017 126694310 900096019 391154034 44231029 173128842 225450160 687497043 540941480 653685479 438056022 345525825 414066912 859464780 926423753 149121195 560587221 512416588 278671285 868240708 327595747 700106524 38509448 5613194 126101969 606584075 404824018 854836430 288302390 79731813 380404035 841676746 68457990 528947307 673043769 944259895 586738904 496696420 566113251 754190057 838237635 646090299 299455866 987732467 466182933 21864844 801867563 938367817 430201932 57713929 621910126 672204993 419872968 131547243 419860155 749229468 134355041 262615757 499310593 94792810 759206186 997926500 231558836 443001399 785535381 612102872 1469007 541307470 766672878 635194195 867600527 630629391 751989045 509132112 659492954 807230830 734636150 644828341 814994636 728077320 751260360 897465345 896687520 993696068 348090308 232952894 830209132 594121771 844604552 165647624 79910315 147523374 620822698 104977113 668928954 763884156 941660010 520806399 566497169 53878417 525412893 183491217 236547949 946130952 456984809 755475223 866823864 59873270 102674829 651035353 990414703 306382824 560511018 60740689 979793722 617463380 635424555 878563573 266581127 230201879 82497752 788733901 670500573 935026438 738418020 347688240 877575224 321339559 523809525 713623950 530538400 943189885 174832509 779201864 245784251 452102510 419411075 110177470 60301328 141894765 647250937 859276853 915599622 232228760 487032767 616842471 747382131 578920482 703007437 791892610 730069765 53990249 327828609 665870507 163210858 429350013 585276192 533680199 742487696 82509663 278166357 800513850 954369646 841694959 420670086 981772218 293899832 18202193 23186930 96286987 678290145 732802808 881749001 398400544 95362916 603655135 764435116 853777377 491654884 467941332 170280652 816711502 417832958 283680128 649459996 177713157 447090361 871397316 52821474 81362067 308118623 772948093 69016545 460557493 328124151 28097498 571471073 21548760 230340497 109709151 263647475 524318206 111591921 479645009 979051724 302787843 260760949 580549919 376679351 631305926 218312730 615425734 486075307 236011752 377507464 702314809 686982258 612582132 620747961 112028198 740823315 969795643 92241034 552766493 607486843 80266754 379618299 412888425 516301764 455231116 267386127 601389779 696226711 381451024 134193786 459642496 848116452 815683173 889713553 475473719 180148120 574554477 306276125 982564141 715910501 336593613 695810314 955546909 461399876 397469652 644920524 36475125 718026012 410758980 72360621 26135896 374703016 770602958 61235531 749037806 891016485 419540936 124044870 516159961 325271692 366425300 963217734 241846051 536139298 300686788 987197447 535029355 480066082 848916996 87438630 929185834 726581750 898406679 406294363 952047699 769963096 707293914 123802227 919396644 257122233 154630424 169999120 729133577 931199295 914366147 601602846 670874882 926523803 986895702 981902454 506361780 622829826 209606645 505605687 717204944 37868060 346757320 118609067 297351954 506984798 234189917 76902466 779978127 832947855 680785110 844273190 21350848 360301827 724986562 116750708 185640113 584823496 346484758 169510430 487702170 211223507 987436416 803537407 377404385 119021493 898732089 95247575 778924515 26090958 817486923 581524054 21108268 991060087 308506337 172431875 712639748 741819528 416268512 998036844 263123064 806183754 262775938 476773058 696233803 862210041 685292528 651176621 520697039 892068319 269272078 507029038 709764771 852737396 846927011 233927447 757322727 289512647 414937556 142821258 569629767 221294122 882270786 351741132 162471831 952855396 387677649 370503774 80736227 764428415 569547869 191837785 300832367 465234275 253288266 971039494 416593016 840008956 794211899 981249745 554639323 4490770 525706793 80803259 289934832 19654076 247629833 247934654 62077074 717337248 190990560 278670059 182234764 271570584 448857876 971416073 336518827 259830164 112904160 707944695 626532835 367010830 99736100 326219125 102875215 421843573 959743186 174095053 188655367 937040705 129645127 535888393 910341650 767954151 39050150 691977408 74727401 55967639 604532946 749990293 602245806 968374892 302510843 319026792 980607934 525035230 474263972 273674950 104150628 576590668 271783866 362086731 808412657 887696246 71766640 223988445 106290918 20540806 352413673 634964578 6389533 947023042 726084636 780018565 809290223 418332716 640886259 261866916 455242166 449783876 290965367 966208186 395140924 909642160 41597214 862616194 916663215 672104486 897712366 825564200 957919495 365735518 87035087 611424359 34960787 897096455 432923035 806256573 81259975 181581087 613332569 824419715 913831102 527980381 350160783 184362882 834786330 875111843 903457669 188848125 947782671 551058485 507877019 451445589 377822617 112800528 201948689 781245703 670339202 839188374 111244635 443930261 396977316 573719157 110712995 611402695 238374236 382249159 604535486 449101091 805178937 706198933 473888806 103672250 329608333 38178953 668008371 156707919 71530001 724944855 12190893 472643112 984997514 432252515 198980329 510706816 748396265 243773106 463615209 224139202 736143412 777095372 524309102 972219421 757558405 990057238 165713262 465295091 213849752 774946386 485570157 853154911 875606160 136158480 387059565 466462821 391527870 825084152 843233812 646353786 983624416 179164135 952409669 987490889 630011475 360679262 633966238 496283182 748495364 498072923 203603414 891361825 337598102 507240200 186530992 388764535 210699155 104444475 759668612 469567545 766557570 512852807 577494463 558622183 330446656 431282424 659965637 72551387 147269992 321867658 888241667 959799188 941902324 363414020 58906914 524713742 260752198 634233260 153507517 929267471 710526765 283083614 958456402 798014254 204396381 292257548 702884774 746094257 379463815 221891663 487908534 283944895 658011550 947269744 305403989 140296616 925545114 702421931 773562158 941189919 187006346 360524093 637194568 395074489 343360568 304261823 259744904 114273353 637863334 842386082 858259128 794727919 616633050 713756914 183157713 918604427 584612835 602563729 93585418 709774435 899209290 65938890 638790214 796783982 509373702 97279403 551002873 947246559 909947280 548114992 776637009 45446399 681463653 914394589 153909646 252717588 398789921 203183330 966735680 198818591 364249575 322578326 439448797 930050846 818157023 407110926 373823935 592950493 271987980 236285844 650753747 439959575 647508121 72769597 938515106 547069778 222817484 516940244 131951883 794685201 503321076 835741081 53007098 575362917 599373069 400279115 576927488 142504277 35855262 318544608 555100311 598167473 692265929 709337028 822218396 54663604 310012070 730938611 721030124 954721828 54256247 205076845 162279382 46037312 88969903 38372790 535775471 918788178 533832714 877608259 852813263 828485230 744645861 878617407 550914691 747822294 29632991 864635951 414628262 757782731 639400776 266574738 36778668 872056962 793147029 707274951 281714632 730443314 733475986 187563821 700537754 612297553 351397817 996040560 76165682 699559032 839519126 449052610 874182781 153836685 944862912 758886814 392386445 373878493 959206982 511358902 433132297 294520366 730184299 980711168 158040055 37849263 855604013 445710630 714813674 954922820 139411997 768318656 770155358 888296535 939743116 496373769 834338784 445428140 690111374 236788777 250017318 867884799 699732894 787243101 558939283 864207931 827876718 410601610 412340489 793815674 585368288 569759092 518913698 56202097 601412818 930194118 289240702 340244322 937652458 821084110 996093551 990575089 234028715 777074826 806789560 283946890 102109647 927556704 773276320 588471418 49522073 145567911 596270417 248263789 682096392 810480281 729557810 193227279 776105218 748802373 551139324 597378117 955379941 396423910 567835394 913028396 821809175 995392654 195584802 75018206 905812106 177136261 405162013 523069852 945116641 148432081 765323683 949794596 745151702 871106436 895683662 106728441 636211917 885141880 274711938 817559429 479313732 351121563 510937957 47750924 823685754 333596396 457717473 717708861 594176717 336859632 42151576 653516306 73894696 801589161 543283824 157196017 278916101 463748827 829181637 741285446 807326581 773889872 774102596 743114618 463188527 902774422 876622962 552466444 40314852 36700985 294332278 688479933 724037531 682073424 470433362 867384661 653290061 50455537 269769367 550676680 151353083 446155103 902163126 985017717 429515914 683180764 154401128 628802034 332546834 809721757 68920574 194232470 638870087 723478878 372396858 255662712 567254889 287124454 313169822 816370925 861426826 183564249 227905824 845149114 785760850 109345823 640603481 293468367 470174012 108032902 558094458 754748204 914006576 974365188 525663810 535554634 598172292 581919691 704548752 158015428 968302862 310328015 711779961 16398796 155880353 194194954 790331325 400392837 8274919 434596578 330091828 509918974 291304640 666526042 815738220 731542067 535098372 662449090 509888185 236386317 395039272 205679051 340136560 783955580 16595030 548280159 764803558 474600779 453113924 588302249 275353010 829540696 45334932 103023502 125325102 297306665 567221520 937322605 523307393 151318065 498497823 968228260 969743143 710335582 991387931 886524197 224532195 390407 441456418 489540151 296333451 460770143 611162644 84110339 520447936 874854521 296926585 301840592 580402084 78503567 645513871 318519961 27349416 587448212 478915621 822760937 749484952 194554305 201619500 272588456 959450403 771434549 587079734 83413504 802070696 194430285 838609206 75928016 21974605 959512480 922699862 658426837 210384108 404488834 617033699 885318703 169399047 348871643 344099504 504471470 738320771 67758587 673472763 290495629 856648431 301169158 888778469 763649995 458859477 540382940 531443676 944742024 722426903 425800267 267858354 601809545 572125397 448207610 829166135 907452617 333745329 605882019 684444440 852340004 370393658 500805662 293991636 865856875 860531420 312139943 286909855 414970195 199120950 189652859 325643900 306347941 759855230 89934682 845873382 40871935 627369904 651038801 903781257 45841539 901142857 193474251 107274184 992052877 575931710 737827015 134364611 824406406 822841653 706619629 544361917 298175323 637875956 229419918 475726607 541019310 750669030 86700013 20818509 497630118 556084344 565341033 632199574 886618434 947246975 232565510 206108561 632245125 202012 268658381 542168816 256250838 254970388 215017599 236761989 901355996 298618213 118561312 341082315 736422041 457868011 192053510 756792063 163484962 263296594 717613902 839544356 543473010 786355606 211649881 566419114 226257273 771611706 444075548 37994384 42353331 496197454 206950412 773996181 377710186 483866995 153863832 236783628 822085849 497790691 223296320 66178488 471940461 219253637 649755389 77663138 395299655 400030651 504917227 453025589 889143666 246518551 365700512 818864638 8002963 47433681 649663297 356148438 789049930 450148041 304269372 314544305 686026359 123913073 73815144 240997150 750784049 200269441 265148516 807402342 75464373 339543448 341757881 561600487 856990278 643913697 825187832 125209525 760322831 726392258 853075471 370427277 486483231 320744425 42376335 683619166 555536715 229175215 842893589 667330026 665329113 769337849 616093933 175817213 625587300 663307883 940895966 29169897 22416487 866231968 872442002 925863397 169593943 10094738 839476887 676663348 478347308 769009152 820926178 853609194 484051063 326049566 222316585 315250301 184778229 688807472 751121643 528413139 67676 76378322 102893319 780707164 901122817 175284069 127786381 794790734 77128989 76217846 767298595 687480775 418589735 77334924 46684350 561118838 934353967 453194680 174577416 376902860 485495613 111937347 510892190 250766049 137289108 772722466 438190529 937446221 992722388 676750147 497787524 528609292 759321556 131720125 681878287 727490962 763405728 509432622 670534250 502676569 728119158 79560673 111631076 825197285 707920007 808010311 546876372 562894220 586214266 360941898 951497587 989187209 496216309 694046237 557002092 727541067 225579869 337094720 770634476 475581733 943833746 729673655 853800789 566367071 928259842 281586311 480197122 835442344 652206984 223964364 684074957 436493238 475960116 259661807 35145230 391635540 266778896 685482473 429624854 43831677 244011695 237516080 391127757 665939857 778276861 697991324 625412451 717264337 274766005 921940256 463598563 335939393 516096220 705153590 830858113 388491685 408484308 876989793 587232783 123679945 931979812 74059447 178844585 468409420 210084425 721154291 467245546 915256674 253322283 491502580 739126906 328697751 652751008 927970403 593176065 10075152 61622209 138972462 443782066 353717038 193964752 681478796 396982928 903037990 551326744 136531195 342476040 974596414 56586280 460229209 660204360 51182956 245543581 307469859 223608956 617450748 384036774 971846623 520822523 565154214 102805617 843151568 475829115 927025357 561118998 157174514 906979925 719798373 961911077 574159031 295274386 449252590 903957962 732630479 857793535 819616166 128888663 675573625 567994021 171976031 371204819 311784586 319870549 709497613 574023758 799650203 981471996 163670455 798948476 960309465 88216531 253813981 881682407 181726218 294833783 60082226 75757873 184329299 522122969 844660401 565532944 791516166 229415545 718471751 36086610 420623537 372196247 385562692 862842273 516214064 941685283 801510300 914409580 471582349 448539430 358097615 797257 276640105 234163170 406336558 259156875 319395602 934192183 615183273 558809322 324994613 42625455 59002369 264064642 300826511 132318491 170470332 348731288 804089487 888656372 944221627 744713566 901835082 58099860 149396720 716365175 709669104 882483147 987729901 838424680 891218209 270375951 536097783 379093032 568095664 67985075 846577294 835857190 821418427 366302812 765596443 692136646 589594268 727914524 881400534 264946617 524456401 227272709 334942195 505924150 236480453 989110179 396342475 792880011 610519063 834556076 52350778 686354030 370551694 966174864 740216437 726724352 278174394 263702356 322615918 322221460 332566054 836692509 792071893 793825429 544791383 777384583 767052977 271244537 577931402 309447166 470034357 364744065 870933489 682334651 554739815 735907431 71096424 292151301 960130431 435095055 285641611 262642815 979736292 107935443 48136793 294913434 158174474 81492705 634805961 866278714 47856988 587048421 288825443 452657721 735451808 731518759 457269048 639609723 651115921 224975964 512097014 52404142 819455723 481115089 670890702 977889399 454772555 395203927 584806366 396250695 254124003 670468959 587217777 145143388 242299422 68898536 65201702 878343461 687336038 753629111 732980245 833948234 736618026 425902184 250141286 238575230 243317290 578829806 279657113 401001706 368862976 59785346 23728455 193790355 22418328 342276399 641946549 630420440 534345039 356816555 936096289 895947214 254969464 530705113 854105555 503693472 42462729 7288682 939917535 524502374 643311642 572946020 499370030 527615535 300320392 633029699 820737962 737825385 6471845 722144837 363816160 825659372 451455734 131606498 140596398 488899054 753506025 638167228 231532508 502670521 647308587 452964377 919754714 855668377 121557074 54269875 344111185 313536798 906778445 689729638 560974760 719338377 847869745 859622343 401849597 124531498 985520741 409966022 785556914 919718878 351974087 941387898 762697582 483820714 431323147 574732764 326029857 211756859 723339650 854862304 295589593 505783009 208799198 137231453 88908070 177297240 448846906 478653898 584252573 536970413 631688287 230780815 996203493 706027112 269024476 956779079 336067318 950001177 917120899 498612546 382038766 312457152 160583076 303273243 643603917 814349477 520412832 554614119 793426244 300176646 710915899 188701859 578440133 534268531 361283048 836757301 46083104 295789844 98995540 456648694 190185574 493671168 519271736 622954680 335819634 963302702 765585962 916832140 687149688 728792790 862044954 850826871 352689729 227990101 795797467 527714664 469401075 567903825 34058291 410170619 611670722 193149387 77966983 402792011 715002419 822388934 581496976 981282565 723130432 930609113 397739772 741398873 843982892 984906876 884217976 116414469 696839092 15322506 717231084 312265136 448856612 68956067 916547275 964870308 441012260 697063447 539486039 33921563 552784509 301087607 322942062 655874947 935980342 921572711 435153115 620230780 942509233 268697227 498361860 91180100 287471627 275324387 499377424 92260180 931148427 373750210 357182474 144625177 50934092 905100629 706603780 843232455 862234765 914689471 552448783 961760713 862866151 948789752 904266576 869648362 600116071 885428466 922116268 746894648 597249726 637504325 80938009 713778010 84306478 442791760 980301102 807614274 253770234 396462582 195034309 251166419 248229622 969773818 48303000 941162531 225254065 186309978 771500664 447456989 756930044 412991032 446484080 919091790 421185600 70821415 836471498 118896522 818330968 577432941 983337060 425721245 332380091 567394246 565071412 995875392 713122864 886579021 303264419 279952452 655567125 734582956 414775533 262329787 268720331 484919041 965285714 177269156 271227837 102661112 218440125 684121287 368051319 179184112 314454213 46165963 330700162 761849629 916360651 535968111 261293747 677454908 354933996 869657033 5643578 662549034 522124625 112309245 886693173 420502698 544427116 350481163 363801255 344450272 114228763 128065648 898368535 197332925 177542409 25855913 210843200 128528748 337441393 425700603 481727769 641342024 720252954 999725475 859271016 994342822 606924086 466652645 517486864 538408149 209359661 808477675 501990242 899355251 876479930 790328869 625511344 786596252 290523985 111876665 352221584 195451238 281275279 162634412 188396893 377957296 912256435 468541150 176245525 699888210 109575246 516453308 348167398 778995710 21290928 773277261 985162496 244487159 205355720 548290812 757474211 169465780 443219795 380945873 352612978 300217492 234023541 427644008 781442891 502817380 59060484 50800308 488396535 98376931 954685977 373360838 850414146 894538278 637045691 380847296 445924953 437307679 691697836 4812773 389747375 890590908 676235470 245288723 512966023 439477679 707931230 903375416 138371603 890686686 342333506 344600598 610054510 593712360 651094284 560741093 846909054 376400299 190778077 814260733 883014317 198211112 663442170 667424879 937642326 822905215 467901086 710011459 788263177 538974223 996152071 856499843 423656641 62470325 688587093 824996511 699490822 597091312 621959643 650548102 280317582 339099350 504642911 128530597 945697146 231709918 149340000 831388082 499195280 601905226 551883293 425751169 734716235 641421736 699619842 194915857 302074831 559313739 749964172 542140193 480640836 441797423 401366697 988872501 957368740 925969355 272553756 274156345 359335203 128116903 529935054 892764739 335222797 435050948 445884589 427041022 100992724 614674457 191053764 745134963 389392860 119329562 126678312 140300296 491001796 942001502 792154446 580317562 182004335 397676887 82441306 404300737 519216694 899032544 47392354 195056791 527389266 180214376 103079802 10866867 584004233 597053390 436419833 572103780 917980623 324610369 323338176 544794255 499625334 831395094 472797434 706503566 305515978 953722859 386872409 853263551 361887953 240223818 950579880 660365397 915117384 776823364 336214671 634786608 398228725 677255359 277436779 912115656 564759033 597287900 646985637 28542633 220145967 979724334 982514888 598667381 284759250 910254889 202386706 953630535 574007402 867932736 872617040 153030528 412957410 986622372 937013586 610187389 995697302 308464119 139070786 425709663 408581560 273846065 211140009 104675738 13296189 327849383 226168356 695487235 839200098 957460821 477818199 612439723 211865779 218975073 585717469 541636900 426139852 54080001 921880926 343647278 230045129 148417248 17592573 289967113 31273343 635057639 454871125 499213481 703080152 226566610 641940617 422745175 51745690 507404514 856495483 160514849 927523344 605783256 457816930 354468482 408173278 242422262 680687933 294746410 566340257 180222321 233962665 434256352 345460021 918409118 292628412 417431833 457975852 930459158 214039672 120516502 729832794 748417362 619828764 889170121 592384216 943612586 646850815 205017836 137593204 8554204 818355911 224951854 114099069 252102089 132037963 21202543 603379768 363561172 237969303 380413789 283759441 74421755 534808478 381773834 370289514 794304151 225773406 217532367 355937508 497136798 247217160 458330412 466303547 622540447 500876727 398792133 768804285 577030625 398633663 765956938 895695273 55754918 807626638 967927625 215333686 72068382 494356114 426498326 817978459 735793611 793462574 735100391 219046425 375265209 320712646 766036517 368817231 927548768 257378785 87141609 754210538 727342442 768396370 477415027 96476099 277857106 450404287 521832296 753208827 349541838 673988602 635273132 394611850 583492043 578428922 827094122 235458349 489915664 882326666 317319742 777777349 339604472 989765601 757312741 252611687 35699669 763514814 786933873 482349489 863458372 444876860 456691090 890802738 774143186 110558224 637030597 776268906 51479078 242767364 948127707 728570707 165393999 233018194 541006955 41392978 610474435 778761598 516739464 286164106 182733927 739891539 722172302 919415043 478565136 526278008 235882586 39302244 579336156 881860004 740631220 661890185 633762320 893510908 302987038 591437068 356670961 203407387 236685132 385547254 309226783 491184829 481970750 258197959 408265470 840696149 965662053 836541674 359124054 304370204 584502860 190191430 178056145 640155288 514442787 227582258 817870002 158969498 697596575 377414368 252435367 590063169 867637323 640570874 123012836 39090650 82391917 733510028 479447733 268975390 450101872 30769608 921591987 412322510 456847055 606704069 218534247 832425819 596440331 319631943 274774539 304621395 681037244 992146522 566266776 739015139 205320206 687636512 835732844 568107706 856701825 314764670 309461004 561285743 609195284 87500178 455040631 647759940 999129300 763692740 308966150 351964150 159228386 573569976 187303205 384501267 297151985 638282419 640871001 751144725 137775190 60122776 955362357 332305701 711179367 919488719 38170446 570702697 594198449 715234650 832678596 413716254 95457412 820204143 942305569 915077196 214532553 223824960 501286103 362880271 462317533 440947403 379531457 928899134 659989387 442719924 503701093 835696790 625430890 236314164 433921922 709863515 772108169 244893723 137160478 823430406 443575994 786718154 509829796 489150407 239535078 186039809 986101834 596098283 441123747 522659030 758798108 863810215 163454907 249752768 701182760 158307021 250014994 347238759 547270818 641186629 366720627 790280662 57822611 55693732 960893467 97961248 402485667 419904186 654819148 308227623 677016400 681926200 67391282 588925301 244552222 637713790 570217579 746045175 905761638 280062432 852757473 722731654 52941861 489334060 498186822 133028422 151049261 750620604 139636895 652196687 572949094 415721001 641905567 174404066 164664143 255500897 537790537 963149937 847165861 733195155 600360524 25455593 180812534 203591082 374139998 750905058 216534831 892090251 642150618 878449234 282910412 559918512 674898277 560213804 720168951 714335105 375751994 662602032 807079305 245297186 911384698 495468276 428981753 235358944 438624955 26079620 251990449 131813218 104928587 222752699 219828310 620317148 363924894 431895265 989373704 57027554 288954200 88584638 538529371 649222650 777908009 342811653 67857437 933519518 92000887 402453470 451636100 475161834 55106608 145386462 984268427 610203735 367637709 147456358 966988585 610088210 223191164 792000692 724136502 597731997 185255490 931860123 102389231 842872720 404665318 501052401 435851148 211072133 580086423 286274379 638640986 625360298 702937041 159797251 851155928 411957792 232696698 335080940 477693611 886558790 744871382 323701201 2714275 356783222 182287349 465278374 425775361 754581161 812430731 972318617 232655614 703912150 176593799 212358972 211407111 190118138 54854761 687450716 362386184 535626949 663730513 628313597 57593319 351734250 857698174 908735017 590180011 676716169 112026087 775291947 384674168 643960175 451518969 983809825 438654478 684678511 106445657 131680578 19970712 548683502 597383321 933375155 686018470 108343404 898741505 825947185 345781672 682332127 602198173 847483947 26953641 68447903 615459620 781282765 431229200 472918888 849640572 150647406 424874141 794479533 330467844 685811685 163755297 256443385 196730202 943523638 650047376 754590656 25968787 504171560 207608079 474616600 994155615 544823707 169858081 890650288 24280067 33422631 543934106 650354230 256682476 541244770 488268906 168474568 991449258 711071919 841537467 358884807 66332622 707325743 147933335 330797644 840195984 842635826 345433213 652770643 617796837 67948183 782071758 454702401 927874434 340308234 43854298 599936119 772091733 713712828 893937633 797983742 724980949 2201245 690023896 987721333 71084521 78855232 401726980 993007328 537146250 245815887 943737585 318703227 186453929 863511749 86358855 811899946 600370820 957773799 565500214 431187557 942421965 183297331 738519117 759852703 184937776 582586879 240944223 680451720 759214692 248069029 278241430 325097574 696870588 429563855 987839937 275728201 619385866 577267001 443989775 38085186 458225886 300561356 719708198 750238629 531749612 118087637 950979936 739466836 685868376 126800939 277117560 169355661 482156339 266588114 879589674 466106470 861487966 19866727 471965708 921034355 808608488 427143765 401368970 115542545 93774838 638226743 395300704 179165750 234603360 190083737 405205567 657907554 380212221 847233328 993272051 375260653 125659425 110074069 371008977 343833515 658997922 302705059 475222420 864650224 862088036 601220007 544654414 660357406 840438215 235253124 993425471 289455086 866520301 483756758 343319481 933857467 783964146 940556742 540628610 933459295 28152777 816162282 777502387 633373524 467408230 306958853 524197990 85217212 497081818 235379116 931173539 307206407 504008921 152916468 226784076 708411433 631731180 363234290 816430722 817778535 428987879 539210213 119878886 737359560 528103777 441249007 298834440 111812887 510038903 475057817 487379753 927621094 637595324 239354829 649440584 172662153 155880892 393562890 391427022 865826851 934708872 234185674 947939723 920392803 449080733 182470636 131078640 150998566 14466499 245540761 691040167 519452112 543325169 649203418 481371439 588422375 192463109 135214974 417831922 174598684 222656143 87189328 621555501 512482801 813066096 213741548 388759932 757379133 437223650 430244442 932982828 404813051 257736684 125800745 802092628 167994851 380066690 963534018 30145647 341392878 151131028 637794629 141337477 292579259 576479221 305892249 610551898 593321116 67102234 262371715 236239381 310398340 920615504 77086209 524370620 814758454 893166546 602308575 461853546 771006042 84878387 586055901 885483247 858562668 498757817 843177395 634615164 514088572 745623750 193144499 104780905 597848584 408749165 343263739 731850770 79621273 434596991 814288176 762829352 868611602 437772148 96755247 680600896 327197004 262184132 61334400 982457084 375367714 319193373 443196086 140588508 791679853 748855760 643316938 874977685 930055191 2673564 104917674 584368359 470979223 870342423 703704151 99917004 110723800 303773624 708685819 470669234 530440178 448423283 929838723 314511031 414079075 68983110 802462130 385425203 898519112 382868993 365821722 708386253 188904651 557784821 570576761 864218275 47944784 796905355 745976001 271065625 609941341 417643985 320919247 264211290 191195576 119655241 10769889 93688110 542957719 475505104 597375794 842236120 883648915 408431264 165815468 850177401 199147744 137701298 91383038 254846063 551148959 641854096 170320447 169508459 448419118 830133826 465439861 651721069 706279718 487150804 446668230 741089140 73353781 513710054 682173397 266089639 753339240 340975213 449340784 12883018 195130533 645929562 5445580 91401643 628046339 683328510 465419993 776191204 572694405 969114427 426028527 846462358 162241188 415840699 95396775 502609549 63551180 65486287 367311751 982017285 986495073 938819957 994420353 374967430 864378690 499148190 292967797 41386823 406481405 310916622 304255033 628405612 427121305 103759538 286548819 755342381 323425531 293868011 51373810 810015415 765150264 118285779 144543584 597993533 705189885 678316280 336758210 508708341 880207704 794805178 661061705 565672760 26953551 703979016 867911986 411197745 275355493 982512443 226131668 242934599 635874767 169480065 4287251 899568535 894490498 688252317 576795068 90978748 952637783 907001096 218492774 35369296 106617474 861668672 347939693 762460299 218646191 369384071 991730407 516397125 538102664 958628092 699886382 400574020 872605032 35491985 977824403 726267925 248406402 474776803 847064110 897052403 644905831 871456645 545975115 362966725 275348910 630462158 962535703 922732504 549759821 299135033 991087476 70815382 588536997 556330846 491340283 270249872 421562253 114276112 209210882 702960153 98279121 289608944 813630767 55491414 158526688 347861980 346719998 94123884 331998896 510111589 250561037 67989352 950453737 395088697 73486214 674900135 977273517 173566346 732641445 323347966 824097033 100195159 577577495 729471196 63408885 579939085 478898222 70789316 423818793 717156132 200999419 119933333 80447080 850405571 423795951 951445293 697684316 106314740 666132204 14339432 70548025 440549612 130546790 577615498 482958742 141053152 465074853 985306633 232168396 997052315 126119618 308898005 702435866 400356832 150374162 870464855 158062940 297801940 399485684 933470888 88437143 325179736 161421244 962639347 618970775 347562574 962000444 763241444 736513808 744922776 366889194 160163970 341069402 752716605 630687812 85850856 133832896 919576170 131905650 446880232 50254048 465198822 361762682 159552610 974683767 333152245 870265141 878739993 563488111 324381496 935127931 485072823 525842146 273238049 841068587 265245058 861345006 110063789 35648596 225050912 815277326 172847796 487778747 973797913 130119525 407415361 625887009 612033305 861581954 661910888 607248598 235249090 505154957 560185811 130536631 757219489 168880416 651299073 943142790 875843232 647414395 437102583 534855123 151402676 383272434 593268999 594949598 143193727 661111919 508757488 763977423 58723432 81911346 348118136 124714845 800345846 757551030 273760642 349122347 977694666 374426760 10262422 685322427 724603139 808409326 316063787 760038508 926521996 981435530 892484348 493476926 626274699 951756147 489758211 382865412 448370842 598409902 692732774 765866939 204218926 204344031 762511387 609457917 375652686 851924560 907795574 994384117 202971633 528495 774538316 413162290 867615558 18991655 203521113 266404411 959629264 947456376 907008514 487594316 353822955 33694248 261606140 726656782 525197785 687251909 496356207 944265353 80004644 532519397 311587128 625947264 57136602 92598611 999454215 350244052 313076847 830279170 888635997 383507020 781374935 402584902 540072458 663884736 387682078 440390628 406842323 673325446 56633856 707387775 885714993 20689633 233965990 577165278 627210502 924820255 463460803 218771332 343436110 46739002 500615770 511281096 929060462 757519601 56903049 910695647 884033291 69834117 450410767 656953421 363192937 562895129 88713495 439661416 87100805 488134064 133652118 97910869 402544668 177244369 183639998 381076060 928364045 513027274 240354837 330740292 460616031 815644357 987189438 882915705 552418986 598826253 317764030 533803477 373092445 219874334 761274335 365027579 988166792 472521481 200331742 946764247 672297862 498692095 921643404 986910565 929410384 436883132 273540578 377106102 345346951 270879824 85947705 917746569 721668109 868862255 611179474 239635541 87102833 110253541 655291826 580919255 325458774 284684573 746920265 860118005 272967501 942134433 461291871 395632653 958552365 56784329 369604636 214823483 758624637 327249326 923786086 22869907 988485909 147163455 307214822 242710635 604023567 945295700 459397262 193831506 196522687 667256953 608461006 567793092 478509363 873930897 907098458 213731073 828305277 914310551 786896511 697587692 160474476 109201135 497092217 432475228 571539704 470595667 348061257 163216358 397281722 877227733 153420263 179276426 152015972 368742991 723921076 812200224 258180822 114847952 298968289 490360800 122964059 429429695 705909428 693732002 74687574 382069462 438804944 638080803 433128628 756454371 207234412 28389632 360679219 229453046 94422113 30166596 230423415 128346147 295526364 454850355 122467072 703397651 393135738 658729731 620695970 189177806 316572086 91978119 209629067 964275249 391808836 77293262 581616214 937423742 931389382 355080680 121460820 855510771 885341880 598683612 14896554 743465374 206470129 457780749 872024283 526776927 634218608 584875357 398152823 131527990 655451252 120388344 38731172 238730627 218919733 501576428 457937454 533601098 122024268 600538536 601420385 32771270 703042584 818267830 315197109 917724773 549427811 172070830 159220969 16918739 629942123 531649435 990522607 602613576 692497277 341491211 802802955 500531943 604527419 809168645 339280516 111432225 986531557 139817902 690963777 972589213 441607974 791774994 320474108 466822172 75748796 90015668 895325917 710659826 656067399 486348049 69894807 183534743 60242515 937442437 982422217 510503325 496331251 212439865 195876178 587823022 497169686 122642315 301292399 76155533 222665507 28805199 170243475 391958967 515072830 227388326 357294839 501133927 40307173 829078577 244789070 517227673 311311028 515605720 904956134 722570968 337563621 403287946 94773343 936521542 341483462 91853010 554251290 54626895 13851511 874439124 940952722 74897340 538903661 978567013 423930192 94850922 808865201 148669048 261529508 145076118 305692319 858194333 949216173 67137403 317084480 605643609 632805835 577357701 264523745 608717480 486688221 478385843 433533099 470441132 626799253 980635521 685228221 464197929 98708125 956362804 636038548 563052632 655052943 171215452 348621069 241925612 392399798 761265507 273654231 327208950 727894920 449449969 259913032 557763673 846655203 333293273 665664887 579438342 660068128 888436989 765369032 176383749 669483602 627379015 240412882 252414407 306524293 920033331 124375906 213109534 94595843 29513810 566008637 522209911 369230742 900940204 733189523 175687250 958234712 351557023 355567787 578412619 604942298 472267712 526072296 78175004 42929092 635714064 6766725 829190446 817517834 493037957 814992092 514705765 554671490 346250185 138244507 805127880 765604059 979768460 783869432 451555470 503662550 133960683 663572189 42008543 57204761 952169258 490221038 280341282 586924517 847478160 413750552 370047434 635673542 870720561 482609425 844270465 69436269 812824562 831732131 381976874 978283397 538702495 889629318 825047527 170138374 519204 87118718 865533025 715986113 3220210 248351661 699404571 291363945 564736482 21504077 929813662 916348885 732812952 151968075 743515851 962907752 917684896 149960282 999410269 964656545 154104355 339828167 723506899 39651172 740947967 62201826 692914661 639543448 776431815 376856122 62624078 666704552 738824940 452611002 266616953 108412615 382809084 154487536 360733132 567084801 660781764 956372083 191753958 376338202 148881267 375258838 580658758 700193965 853290682 166467792 7288977 77778022 753201728 917026385 713704170 131854166 498802479 11171902 62432120 192915609 177096257 747520256 828329637 235808917 350230721 46200437 9150582 159688815 446800423 584535294 44016622 662143840 640801473 482820700 258055178 494262346 808756089 25837246 638288213 810681307 827446551 530980598 829046193 547019930 907166225 754539879 457645259 709001113 216798935 837673040 231794342 585113068 865615984 97590174 473889595 45745415 87290602 248332242 739855236 437550598 708500216 57435342 639479926 459154870 994879470 902565450 241741286 911515692 436380241 207856406 83907789 317543564 743635392 189956273 105029410 155815768 270612520 496652365 572644349 126389203 810680039 646843423 232031225 317481242 795722154 793054704 153674486 865391298 403396225 504114708 631425864 348583028 131543710 621373837 395061389 111851137 679994742 430966756 901495139 75003438 424544759 293640342 234487327 200617602 677062318 240260664 880491174 43907279 94062710 463309843 44088335 280578122 55990361 233186517 158464148 137892298 106230014 298430818 107382736 203603484 898183110 897469710 630852870 345470750 831275909 766441783 151016134 108904238 228066850 12841899 414304022 814139725 481610164 950470768 588541931 33094616 391191270 491955701 721113239 513390257 12098291 936932123 335583956 501485225 715088671 873577088 558227412 584931088 90584732 234415386 573245136 3287508 678350633 967541185 102491268 727243176 958303575 237443090 554790683 241578702 389168652 175802952 161250999 568399408 446367876 331413043 892179715 522863534 390179164 841305130 378003188 92754643 624170924 643999214 930223522 419524619 916647688 71988225 799742214 996082447 774703809 661388389 563757561 150979293 940123997 27736176 412521009 155425387 824658256 33849635 457912899 114579382 108703013 679508072 971744040 438688586 846703322 897325608 227735893 859959732 47301572 351111161 314494946 982256488 242643452 370850028 8926720 52077417 458434009 274723776 338924848 524087735 783496876 22311815 771269310 853042866 279059194 278882042 233021184 94300516 838504859 940710701 248572900 133873627 167262850 746289085 182170619 382790304 281245156 7033461 976032771 300035369 942435985 307545582 809307816 136228615 861124447 726993205 103779561 770731877 70780124 126853274 343031624 980321508 163603135 663708294 921887484 201361046 250252763 213377119 562512602 850292658 102565571 194795937 928179476 772189454 263804429 619086425 119814030 585037016 813666609 394421194 719169421 882426314 165248987 286625866 927583183 466864723 361798148 276886227 578496069 330109039 339851629 408395466 490406671 414175639 133527201 721867330 590837096 42984540 942811442 555212890 466316561 374352115 603838777 959493118 915581348 986998765 400223748 357121583 20272161 850081382 590291210 872734713 935564632 862301409 758784989 228026785 817910923 292430783 206150279 194064887 762564557 425126976 624014139 799679642 859458382 25494675 517647304 671073913 11108614 172872081 206681312 871549005 372542858 41018485 727825245 838725277 517265009 851969770 264827161 121337835 808465754 123191365 544959703 874694219 498424736 46309881 187861345 620472134 519878100 529783703 693985952 926213925 620277104 892829540 59037185 385112399 223688092 482120092 786483662 901852708 995095265 854946800 263395119 187711178 19752907 423832864 679324582 742681453 830190968 729290591 283265885 623554523 828237454 784389453 484981554 401330478 807538232 867984077 844235898 446539326 188854321 391889206 496939107 777255415 758239879 213104986 317880292 68425734 966044236 83529729 754868672 218032300 77355945 852728394 3545352 622294619 149884705 342648142 917451265 301164095 186603489 797119589 321865572 502751934 752482393 700388942 218706385 570466050 60384314 758392722 632667014 889803905 980739020 216296465 212121215 583531095 59899665 931140312 886862766 470635358 113932659 698474199 929439719 675387266 545363473 711048840 126038820 562933537 257104170 357330204 376422127 341843185 49080940 103886881 14209002 894331096 715268714 647898994 19689310 176545371 163215667 210397124 622868478 223084816 37721251 546104063 975000942 733491875 832651259 395552043 49936378 685087429 725210718 816785431 954913533 231112493 598020647 78395305 738679560 642911750 136624231 431051062 829166018 174178836 105394671 602543340 551412824 77100208 44467931 373709298 838843185 952085385 20364363 30335067 711023985 550326361 943626375 77593377 563493541 689878179 520912211 246495748 806282790 133062959 935091359 746114814 931413482 634405569 576302708 197659434 577662594 184780817 292740048 872898861 103068840 872678772 903032334 932979558 436339413 875216323 493974901 863561960 458979776 861227242 616849526 147260000 729089834 211316467 998968989 116121118 241425479 398934920 547629180 528077243 995808888 657869311 645381804 784634645 875533553 509801237 485031559 859534801 112026878 293482685 473927251 29941498 340590030 918616992 979739788 154364267 894904310 149890890 543694423 491457129 490592058 342736557 479875803 20114634 280272196 361611155 961555167 691035128 787364086 778167854 745788282 948447584 900367005 592166730 820066032 641997341 532474730 783755833 247592901 504953245 206162979 123035821 221592701 295421910 277315633 494720953 740194396 9309461 123507973 126488244 119273392 35402650 363353021 106228127 624421387 787953907 906179908 528793998 794407792 610352257 145761077 898662121 789984147 729416612 245056254 72737070 96318738 533538232 905857248 579330525 275476165 935072066 7309421 40713625 598971559 650369388 564922892 404037483 589330183 547670550 279287347 865604192 869125951 484082762 93665201 418096021 974585711 118534056 598737974 824026047 745050193 58478157 880092498 492636862 991893920 281042477 830537354 689891652 663264781 959884736 117277991 470070768 731667661 828551802 909724357 133316416 648141227 640298203 153523810 999077012 451834605 735855092 327255957 829035233 398550017 864756630 24480043 464032897 977174563 47793229 141403621 651403784 106246581 961386322 944621312 667098091 151460863 543688457 876526035 468791865 840168733 903165305 972458390 592341815 311533053 876734725 635739610 736831534 802630797 709138850 180234032 93278374 360319095 483316265 452304855 11386886 642194618 882162369 852007271 5240130 463353538 148088553 355088117 283190966 342853830 7933598 299765886 995171240 552787373 413158962 782083075 80981601 963156723 144072968 819666323 388117438 483881736 918757613 286731722 925963034 822128870 312126584 62518792 67105911 792810677 681919823 315447175 902177326 702635448 708592030 677406239 998917194 209355351 615680617 681787878 991238102 688091035 590537937 152830409 211609705 977023967 283308852 723285866 455843141 841161507 45182633 827919526 354043148 833713376 447942531 43035727 549920144 818685270 310817372 924193047 943359520 485064124 470510594 421840887 931803432 937269211 36572227 148532207 548596662 670772986 986254034 725614240 21061306 925558464 66508673 223615565 601616882 292245464 804052337 74535829 597808855 917684693 162593975 12062386 366400410 687603597 490517519 102275187 650681250 24325494 496629938 463150903 322902384 86548823 373929221 765526813 458299691 525465408 73027883 152476841 486988524 854009460 914058584 303667449 154936061 528244967 596864572 249593377 263266883 225792800 205263566 114720209 694912828 857391111 281137651 726619158 217338395 864776287 673971269 757608339 127463534 352521080 209716555 809500837 91868349 250975619 705396918 124106192 786978893 548494082 857306905 357316143 774765650 365052953 931052536 674555783 684717716 536311325 698372059 658031698 239303573 737265610 97179758 513966042 432743094 246688134 14322377 671414098 713951794 160043714 810838031 945507769 181142185 110518212 331838902 316966277 247407811 905550086 933386194 10179675 734736159 477462811 58714726 581664178 645612250 135346442 436554861 635402389 130887802 434145283 228030707 71493213 793599606 609603337 483641808 94126009 361074442 156802757 785983704 370928923 628827756 141377359 305095292 585421719 328421203 466107016 312572177 944883521 930947628 486928937 707106108 431988095 744284953 881570782 108845313 955013505 77980518 946855514 608444572 404264302 765555779 995634406 759125084 54905084 978898648 235529810 201345994 958275740 712803009 932860803 465723564 764305934 258195098 968140949 966147360 748955240 696585050 555276896 96927058 944563153 251458932 937586426 326733028 66081853 952676688 680816402 254118821 743949611 12721799 500246122 76456635 948650924 446007129 172409499 470431957 34082025 261369779 641873193 245325229 415010255 242593967 511991148 843238097 294091609 70039282 842110372 909180879 953680704 334514464 754349895 359954658 909417122 182708293 836042932 506058428 986064204 648661996 324718613 78879746 286390113 584771723 32993291 647555429 943874228 66636556 833765868 776677387 109655612 450386221 789311359 502043338 755333795 374820235 597799626 960448485 143076737 113526571 12826863 924100770 794712516 164875865 407393217 802984754 723501759 213454072 68068672 295673108 323155278 985823675 325423694 669589213 855200628 107615757 727495232 824134813 983630257 939696498 632501957 667801661 996082036 170720739 959714436 74251587 412316434 159407368 137598687 963258220 783465024 175429110 400872128 899345469 460022629 482292964 857111033 746624188 503923783 851616812 243947654 775610319 241399077 18405985 263994159 128628462 445314479 15837984 6001134 731621532 679239453 666614691 124139863 809799478 789171023 523976693 965395723 522846663 540699129 761270136 670968673 851301338 940343815 17506937 827252610 196803465 469218180 208372952 991940507 257482707 598822542 100999959 582176385 536847200 842867487 305188859 747839675 123001591 481564274 635781889 572794373 280724119 491922511 519849266 824855184 425299528 21622962 361757337 208592237 671185553 599419817 180656105 99191399 465875798 25920739 334214806 673730011 326378817 234456114 509313166 901166329 403949737 403265505 730953981 771401050 66433835 798301594 88897924 652770500 465720592 896456228 339883768 2338438 768111111 690146332 377701277 425401381 877158047 63870385 719319367 367004216 669701774 151521644 159939373 231546923 849542495 617313846 202246098 420761285 730918394 712629961 134121541 574838635 533016193 776059431 709577650 519876544 886528244 516900715 121309071 277468535 456268668 463415390 261596772 109729383 122431915 835027410 311005013 746660968 920273784 314029627 631575789 77095127 462946830 346521558 624471786 966158835 926489680 36965217 575766867 881126998 555693957 532207321 854218673 389416984 794798033 419633481 339192042 868828774 587311889 405888628 877827638 39159753 566922613 104031974 668137383 735618150 499431240 615467258 273757271 634705854 553321136 826611898 531755835 383699611 454238611 394173030 498635307 359214974 977702061 117785937 918774041 113383699 200701667 568096266 821593960 317474339 992649818 763431101 336054899 935412486 448780342 667042866 436934542 59083513 163887471 27159749 174476439 929676904 432310489 342631003 263487313 214898713 406533495 605701973 93296372 873073977 541947042 805632730 20470299 523966979 936380521 619815127 826234058 611285550 990152555 604233463 456147752 163035581 703500852 235443751 872954790 608116627 188927861 875288270 898562910 971416166 328932315 245986997 856185697 711086434 843557869 241079906 601988807 644297205 219104768 549732809 502029130 688569498 494949721 233714961 837423963 409719587 855106413 76384409 255444270 605111622 530409745 912724850 468016215 621008907 764094082 333350315 343297291 240516631 132062457 317190223 406926728 931448991 175372902 135972872 690517819 680844336 94234993 148675091 44873153 698318439 339944503 191401780 563072609 805068975 345184168 918392427 553111798 244636968 394296612 417037979 238500861 565093373 741089600 159438797 784632706 856673839 662600545 999828333 287127229 891447882 34976010 563276641 579428369 103739198 290228029 475016588 680087805 677693786 625469273 90392204 394290529 729105290 321263965 9145746 193073100 679092837 862013361 688016578 839749991 112185455 800264497 121345909 665964742 953302493 575748109 966069768 135747760 790297161 869836233 100434291 429976021 411628961 345221889 982320872 235604793 86424131 906080203 948099973 534828901 76509548 614441527 9017886 341563391 692505799 573124883 834769453 111630567 828591712 776430872 568339257 638908233 734967573 375663007 535806929 83694598 707640812 210402268 544631845 138074225 510648933 786641097 173910756 294482499 180580062 7452528 64845590 575995590 302547427 333598283 919720260 57574638 772960846 644824598 447767321 189164495 307490210 519795738 920533181 895118935 567130842 951523779 980782652 257603134 4306881 524096455 149548462 340360128 387104247 756101878 32536879 527443402 259093248 126388635 470623200 59933152 216753673 477419060 607225133 440326613 573647608 366120369 313967822 553611896 731123938 81913727 701507556 210900398 818401738 579070593 51836518 524528635 487828389 194681548 396991746 333311687 248315037 909167735 743534528 107116240 829384183 145508861 17802150 745706117 962071382 277977280 45319473 864803649 535392227 800811041 833061453 254816945 198480194 619161386 231682957 445701871 808887642 282297276 497740341 686538171 323933277 553624262 428522585 229266637 243600592 162285123 529978897 413006379 595962259 51134469 16814452 523710690 311407182 78900151 611264999 336711465 909913485 747830680 338168605 276560100 96791190 934982500 315461875 578631246 820095662 721391333 527030472 830138355 733668277 172007282 446061040 679706787 764413031 979792677 756874243 889048882 110158526 264304924 40369110 486590420 588433537 900753906 454153458 469165506 658614997 125690522 626265680 596137592 795085841 703347812 471430483 777851823 301397362 982050100 104449461 484521090 510726762 495162175 695671912 678111074 394133866 64764938 616082625 547825236 272569076 515979830 41585364 752135028 318090317 752836288 988292435 281562255 952070972 43698060 991678562 816138120 388402067 558100715 663371043 687589571 152176641 141981053 668612270 244414525 118580295 536470383 279409721 794001782 568173299 751404237 932760483 40125426 102386449 596693596 922292408 93179125 900593685 764768525 932092681 309588290 296723445 906037962 398600854 294523034 374020725 380034696 839073259 969666199 6999785 126989305 278519090 828618373 46194226 854174519 497652082 471213510 345011083 562030237 783595248 195594896 695787887 305054661 928203896 556627888 29675605 610652559 764154371 335019921 459899741 215309347 762126235 949333724 620388797 942526567 714165733 690759836 780807642 569064477 926296040 614785311 928628343 246238201 982475137 586588887 767073123 488943537 815840106 370987815 199417036 896738231 982338129 933540783 146704899 795449371 20695465 131954631 275502718 266368938 840217621 229152738 813231799 712867483 213446913 344172710 717310948 884645130 787883663 725267025 93731813 554381211 130726676 567608737 745327967 675070132 342802241 286333093 72275114 978190777 66544798 793710375 277764583 442290543 977604150 216357387 351651972 797092548 164492075 268483066 80195771 420204424 883267386 522028019 109772894 104846453 361145167 254832853 331956901 387155237 465658454 302302110 294544265 565672014 88816330 154742856 319634770 141016628 84083331 862975461 326847756 438476611 300513072 195996163 520167139 285258977 278352697 684392130 315262882 297674015 993890460 771709648 441461022 105234954 399325395 296149513 851925862 956593569 488745860 311331435 283807882 86179022 831922318 118691962 839174964 256163610 20565847 43385964 654861507 290340038 191523279 298929184 948364144 59215063 991506640 997792206 193746577 463033435 356746432 20328081 512883342 609486015 526133513 650346851 381162962 185121197 70353640 867536663 327118206 430778817 785126225 785155910 314644493 17109707 708206738 1210791 162012422 67858475 879538008 912417349 536896228 728017452 652000376 160801578 7246891 920340975 728420925 609325353 336799776 136916586 587407369 663517218 6576241 868444468 492499175 834047901 550668181 249961968 812984948 494016997 6807583 975983575 532435581 81375757 961355976 768029659 860226286 860376941 750522254 718129551 207138350 917516597 634202199 48275084 373240571 245677914 837142048 34320333 739568435 285095175 879463649 701997320 503117097 316547281 218373852 660546693 809853071 126820303 841296865 594046577 306251151 519792410 942251745 949156448 509932304 583708976 724894616 787096830 156559531 673355569 411429891 949047105 127110941 535329663 897896046 474572004 343102820 343560808 719667543 830427092 292290390 577860815 245139111 477015656 951728548 349844981 571851894 721750598 976785613 519977713 464267374 297711370 895562386 851216957 676337806 32979811 191800782 554023746 153443637 166454001 100306358 684837784 962635023 132618765 78068110 417661844 960789851 689423186 951634672 89477511 994290187 345110445 28596319 747915290 9433650 314525735 408200817 805321608 718004658 211330348 701204945 156472752 703787266 296657391 454916272 369140356 599831990 558676695 128019928 634741574 521755636 439266530 720305432 421525651 379071475 339430113 558692872 226684299 115116304 204887071 162378265 886774123 568025432 985575609 687010305 217587431 62206522 122110533 441238935 815611901 466687604 543747479 896489890 575352645 623350813 316235680 379950612 105185431 578281040 648624683 546150603 476807708 871970766 189747074 749484204 466437755 596714955 339900691 608171858 169033234 927429066 200469289 668167019 847149028 425174690 677086524 333071682 464906145 204741282 345109245 14783061 503935391 348127851 233940188 447590903 624243291 687184043 405730237 90512110 138446132 450773876 430930675 519104647 389712707 635330447 652221901 619510322 71415761 859944659 948800505 614551837 200724988 732878258 867457099 730727708 243252245 87151305 681044112 668389457 916719678 229292579 704457109 919228323 440827192 619218236 382143314 623835797 580109118 931930735 996043041 131469728 935245529 244784797 979567304 41583159 877880699 549476244 685396675 21206296 344479329 439183779 457033276 849194554 490602253 758559990 469736804 962752903 873404314 798940496 231197687 493198596 5697795 991735470 874859600 427701032 991537403 267401397 305885730 797819086 130814186 429713900 915522809 109980163 769669584 652025673 580829644 559647630 676396624 369800525 472848686 828855623 899509007 815997707 956611697 470171830 272516855 282030541 953872387 231069332 273168228 295141492 131058555 487731096 419543394 497306849 645508853 1098064 544772735 300401569 611772092 674436730 938248810 353862002 339841760 803715670 772834762 457386861 161873595 787893101 855332666 105377282 961913027 207827169 97356461 364092994 645209940 575558788 453213334 736576942 551202507 45170085 282186021 389224537 535117630 51652648 980478550 746580919 410217114 592222298 802982276 867993400 457637556 561543992 847399266 839161664 949852115 302706473 642176453 900714748 991283132 715904129 698773708 489188366 364304006 659852792 887999680 476104130 827849720 765274068 649375518 253191820 477783200 484652785 384489931 163307 44795414 522881960 88401317 118490782 742294858 950696045 252698458 447445680 376662401 610525162 678492313 829413404 301241584 791100671 373708270 59649384 521981631 902375229 631124631 66869325 511553951 643362694 752586429 610675753 459147605 69624730 292263910 872884228 597599746 213707386 553149536 747351526 219979587 94870757 670754981 53018384 388903071 741498017 98162780 739384287 340166378 653776396 747897448 436159922 353207724 615911921 934301140 876926656 747171788 507789562 462361422 613339822 200189620 993462386 51717689 363375860 804958970 901808066 665892984 232987425 765721645 96872967 204551111 382681970 690404915 659394999 502020267 588975840 212823134 58548360 664484661 366938773 474865443 573428994 652836097 638558804 792494227 344923147 199508568 179505988 268864352 114456283 962900876 296960960 689740975 404778252 483196984 488878246 150247185 69473909 903818160 207749962 378515190 746796029 408740180 763902264 572581079 535286864 294127855 739201329 42417558 203411433 764445362 263243979 248306281 656545378 596748326 560160352 517096507 207385284 161532471 92110184 386110204 558111838 392206731 779994312 178033338 627097535 247730785 704244378 501739609 544543579 978944292 162444883 53177442 927351895 740737202 901849737 747732124 334811712 560732174 992425721 369056744 178552013 78172025 165651272 523651912 130906582 40392042 578493534 383863621 628767999 568908510 355241903 459733011 510505616 7764560 656520197 742276754 107899367 400373230 841301255 235527850 307903731 970459215 60617058 67104714 806495693 330462329 228235681 286728804 701197706 345019867 164257145 182061364 976802905 534205541 329947775 488656948 47217061 910278119 444111322 840773902 723264873 961315775 717475786 421563784 642110756 741777043 588071333 568052853 167211727 514147900 255999043 572454582 171722037 442352629 685652267 134704708 292875460 204403417 846337350 628115085 585722658 828303256 249961416 657521589 421672280 317870514 335005345 528423973 811527674 557656485 326522062 728233482 906578140 666206083 448238300 481206350 869732764 39405367 665393114 71677116 630293319 701168074 991943479 247371613 774579068 862867842 210794677 704427607 170503744 401227877 561358652 668708041 498624421 980537794 19296950 433250995 761968697 997739640 489857087 905426901 815748045 305626781 678829051 634020234 432657808 403075802 517867291 563491577 975727900 582539935 533518552 498287501 507997709 86083408 262388272 419753275 725889400 696408798 985694491 413870561 556977364 249550848 318155128 131177067 874098375 434317942 915236952 563697104 63075081 782124701 65366727 614804652 892348961 17648179 283488430 68227100 811146225 265684963 661503411 166488417 952136479 563341889 344225497 77114443 18450119 148971857 183771252 220654866 464083771 574715829 504337581 204491080 879995735 685390499 755561503 93664037 376273066 601122131 773914034 657190544 945688202 723092021 886996650 482974608 61364014 311793785 2269571 907506673 196308489 199383783 95872437 776362107 569072890 642779742 37455288 107707802 931918967 757666628 853765793 89426574 744326576 865870773 428318530 137342257 645197251 776363938 378267901 938917726 23054812 241473197 662528523 134563616 927444709 393844746 555264534 613877240 842290295 290753065 826996465 470685815 22189181 961522703 915917099 128786151 659618286 324488862 986376999 742472106 550723270 458937400 925983996 861650382 359216518 174836222 897839383 635955943 814960850 182953303 489467813 345327421 319593487 21508572 208918061 463383980 402594378 195020123 808001706 646866440 934783724 92777835 502024736 859182804 965833652 61378953 151502820 112772618 635603253 530542231 719820776 367602100 610362427 333986769 487824992 901666478 384381335 968765609 933977052 988177226 189277606 444402187 976609185 821376906 629916691 363911636 836997289 175397068 264494224 3469643 253149012 113123182 760875458 582812772 54076748 740087018 336026665 257335159 827598982 516046208 890119377 49585807 423248396 741024777 539083126 545079771 838875546 800867178 545772847 291946976 332944032 79894950 927507642 478660937 751943475 932041772 871673603 714211772 541998701 544151831 941070724 830491398 965458129 345036591 419942842 921632821 389925292 195997640 253297636 349278718 575459111 967666623 559805586 511910258 944026381 568108968 506329886 237688783 844175352 206583526 401480077 222654442 98769041 350395839 390846615 874120363 524186897 526330620 559134386 689021318 327553495 735997672 429365095 693053989 105459617 280407934 823644860 128301740 280612863 475790050 64273318 322688587 149204387 8830995 996028837 95241132 366020945 52792887 577691745 47702748 784003731 186205111 947033722 21277740 927703155 224748294 40870780 521555238 753903678 336145139 472174536 635099589 179378919 329975413 4333971 686656729 496042411 851298056 359422807 131100203 154176691 851600616 732218747 320279172 45176156 485220120 599121690 388179604 990071839 976648777 386848454 177625730 914945676 450424630 732515800 994077390 710212038 835202252 373670173 193186877 174562531 540354030 221075391 224086599 322262362 366896811 398908256 597356978 212116419 180725546 589683770 651039208 106872440 175840051 656673106 307065330 210572062 589330610 73824914 49444361 660407551 614295294 932425361 902277480 990284110 919450249 300770172 454074037 650923360 999258076 475749075 593063894 385373828 878846178 673470351 102441340 672185645 629581275 196873720 90842791 771159026 270790539 801061015 45673356 557687368 488284390 801872862 140336124 168272667 572601782 778257275 58086737 69653348 842187304 875516172 918929817 810169958 30020078 389979375 228674555 674108002 958184017 431942204 113372224 380040501 229795631 317165226 148488463 918199090 748050326 969473137 343850799 717924673 10563603 259057333 93789532 301882454 825976186 608072101 623920623 149780782 920508146 362961052 774731378 891247426 578811599 342794861 116879664 525033354 717701443 529760970 275681692 548239502 703018233 492367156 935996544 602207427 906988867 878428107 838656353 870110219 464907557 756308501 681169704 926643072 922752354 387789918 502024236 479442713 595196110 673369306 742658172 53031278 574966685 859706114 188520683 247052871 86206197 925458587 699771353 961811489 554907370 791887486 389917216 327489311 182878587 472857943 864574478 648068756 660314165 988314197 716767860 560878645 852661469 504409329 565992581 983708353 130674516 516769860 485229557 647272229 875537413 94703092 249805124 894244161 111132493 219562618 632849351 204704780 473044165 942808618 454765807 914591148 828295023 82073913 725280284 754200214 497151316 836399867 353585796 606891816 39793415 258136207 327857823 399760266 513067515 415492724 710214687 854601356 4640537 28393972 186969537 557864728 664823444 180212058 441263191 267922239 161223347 303780190 615701972 957331764 589803133 560566987 644430000 681633617 601297208 494146884 759432008 765415861 162908163 328721798 903280644 592529629 752625737 468288798 687922297 971566442 717403850 834419644 474054983 42268935 561015115 619405579 945994359 289379435 779930424 924844936 731518149 968169296 839013617 33080209 77516626 282963186 29837217 479187692 838915115 850514705 630732808 936145808 365469311 830320895 703056703 868554334 532292956 332278897 800849297 626794694 409791849 201181018 861087790 271078860 887057800 272070198 528580599 776201093 929070449 675133222 314103913 232899090 236528249 331430925 930951945 580419179 873235610 940743546 640320966 484446237 344988059 248009804 448041558 72812377 299349940 110310263 955398332 511462436 511327657 81105239 856864408 316298539 923273747 258501658 467949933 875066570 492414153 273789498 946499467 547288050 93611770 375772210 689325307 940531521 55645548 363145285 364669171 544551699 945147103 906946725 383736180 627492597 534813836 642422802 977590563 814163770 153782969 407716226 736021292 635123184 151351703 384851973 291046160 275425807 529181995 819724301 281832215 962614719 871279917 952057685 957795802 102278844 810894186 685672529 358560995 339994793 988599546 598970938 444437822 486940982 105145025 225499754 949165042 361721804 33059283 740591549 353753225 864616792 210776222 408366491 81663281 498541369 441156093 400967436 439801091 918829944 796613390 958614811 875936812 629274852 820324601 332360674 583869593 641297064 276595718 363624996 888278414 717291532 315639165 67907286 42209230 376165615 835376349 958877176 884310345 821258809 568816451 421556139 568237423 941414439 911357859 430805174 866739745 812366922 705717212 399916948 224700131 829449356 904764848 389652948 758506278 787155775 994938276 589434567 510523241 439970325 199044686 172533993 544923154 16633125 245796493 834583126 381989201 914678821 21596126 68804227 783222405 984474973 142394070 868298867 212897704 989349237 572920478 36569542 780024641 854713703 110729268 654693734 886555778 524979274 562144874 258036708 621728130 170931862 970806511 341143408 946204852 400931344 595460177 940263222 415427425 975513507 962159515 392025711 485979076 380760542 304740077 706216118 734592469 616185209 91318518 413158612 638843877 814173137 519572462 305784238 957767925 194391515 627182286 607882829 170510107 769600668 258971462 244904245 298550965 59762433 716826424 303695617 438726419 105215758 415019964 759747149 929936136 176676128 820880097 934088285 778994623 659613720 249213862 456255918 303743722 111312563 501747936 966492036 700200840 222891470 567771941 328223974 384260161 963604739 438011701 144562365 821394640 753551750 560063074 758693610 18927880 943795915 516588012 206223048 511074082 144486232 982026909 403623010 964747219 761131271 905496007 631648276 33173673 414074402 673000276 936266715 117233565 356949056 838092652 657417612 995651349 911633549 658635993 591382905 862934510 787556966 484022079 925766985 696215878 420461171 285605165 217909218 613815962 143584688 146485104 480248071 588946221 950151272 922241254 108565395 207709517 539302057 901709506 510618762 297810766 850372743 791959945 382244554 982441868 370765161 975537208 587754073 975103182 933958660 327742244 239355670 611634425 848582651 871014080 264532720 345560943 948822207 396503764 232462173 541700662 653613200 815222648 717495450 410312400 266310498 875809883 549082389 835206661 903862249 748588271 479387495 480366192 68211212 625982148 314659446 274400896 314646915 167703698 463287626 132077043 587009947 581015928 565245012 551709243 752506646 797629026 267584240 106250354 228026621 470424802 40936680 24024022 179002475 300278645 457818461 435169320 963400909 341449941 858297801 710405613 357706003 763972958 444401927 843241791 46276989 245769439 254944475 646367180 692399325 233433235 714099749 141929993 541622828 255091368 147530753 941102293 623296103 112280522 880442754 309384734 231348901 591943066 706377734 506510067 853843355 574843716 956057922 765411466 558833149 448964933 475890533 532957522 254753635 616544192 121935255 704942721 706061823 51809124 44375963 148634714 534921850 680708354 176262205 995167969 595745750 815931406 699921507 816182888 85372274 350706986 393945832 246067719 956568486 651114707 644179445 910131960 82579599 356829385 222343614 433925221 615021480 516793098 843186180 498898410 87140385 107314446 645114337 941771486 64507720 713657535 334752737 283370203 874998850 719491741 984898716 764475120 160785286 535902430 607726223 934319780 674168328 447442041 891782442 637278948 204721453 590057824 661637372 889773075 677331365 730361325 660900369 61513524 361440410 262138481 355138270 319892076 879655355 38456723 758427674 449520368 632037491 753368361 17405479 981206334 387982357 138558139 523750913 993330738 163838429 784358197 722629050 81070905 377158192 622905241 803172885 721561524 43596320 53072464 779410519 830906396 62163122 644342493 53631328 995051000 876187479 76826522 441629934 504271061 691806973 322301458 915699778 351974284 462604355 454588800 332001522 775778640 152247576 354556973 888174203 101426459 14388600 896001946 507272605 585041171 142422814 692713916 131870884 168240910 577950829 560451613 87961752 904924222 71944 94886515 124149139 704703753 640232181 799488498 920797150 670815456 197796001 622602712 933266765 81054744 103802726 707993953 831897527 21406411 426356245 795859634 61245941 695998443 103605027 67599693 297110083 825232643 715178272 819763675 201696225 191746140 297510116 104341495 654412720 11075215 494732111 545655331 958704687 269182507 236405024 111387618 146022128 757160004 217090232 450965946 504067166 918011436 844416960 721288232 169924223 763751225 687403926 310101004 758131456 901715761 573923373 688468710 654671201 13875565 758292400 745549459 760471754 353367762 933817363 846741133 460685916 700690994 32875796 696093247 361369080 345073050 785191656 973667456 288586937 416255203 748881556 108282116 168929892 273909016 53648107 862831697 394431950 326894776 776094602 125930908 27131493 713109505 475010908 702274091 335747973 100391817 342462281 805494240 735532284 510603161 902302834 543934707 831113196 551022439 485288180 480243782 815961 825740757 170118539 901418680 387531592 410837008 379388454 553851363 534455106 806961908 893003523 415424709 101152895 81141445 261600583 367364916 630762292 453505580 289034809 382899133 806084719 941474972 649196673 347012974 503904260 388311405 457512081 69407484 216825087 805924213 339742533 9970257 550801972 447584115 204766563 978660649 950918084 77715204 715101278 275106134 336013687 600137744 946548044 57237116 173862093 515676049 914484364 204891685 34832721 913441172 304844029 422099359 124074827 53807025 729867887 215136718 903947843 596522823 693053243 553225000 830900392 523481250 251751188 399754371 847783070 274652826 141808393 216436452 271567060 879478499 34174061 187736692 49524389 138909676 319370720 473828070 979290754 577913173 810281506 405261459 613564512 52683620 500728476 968908383 946024123 59251809 9153140 736095660 962958415 273284866 625301355 625501517 477674341 403494583 5055708 732663163 515350536 661620332 703615913 561655456 495892555 929007486 434093892 955606767 241208499 999878305 724122283 748696291 445972691 97960303 953951953 319386724 754068319 434567193 739147818 549730431 845932968 460719889 837351993 556909459 68822137 188972727 951535728 881993169 844466697 70299452 306923948 777718260 163696321 43793929 861320432 985632833 25661795 219772896 245775547 834894269 989877924 999481959 196941314 965951469 906707853 724931308 283977676 952137251 175071902 978371601 82054095 75401244 408495998 552832375 169006260 823773296 542996756 560600272 337712892 563875389 297817823 693781207 515714045 156401020 112767879 564454938 818408559 738279789 578285777 223898652 44900718 286252844 397753661 186656008 660064900 387208599 521648887 204898291 855925911 655525767 732286363 920154450 129696880 745574969 357355682 920751807 162684626 695783407 493039274 703634841 629521318 129542231 944053417 822828342 640848446 80669860 848192352 110454325 87138923 379146567 265373675 860226552 197884600 935952905 498693407 13889385 202786589 386077596 625090123 238678476 426451795 723106937 789217813 105121786 796370517 672809397 822193867 715546005 888907910 766529051 167845909 237716346 509906379 929736922 211343310 320175786 468678729 762206124 839049304 936811480 762067454 895891462 690273177 666123851 930586789 21271533 510148070 31254989 450696110 43506510 714849686 626611652 890160436 577104010 169052695 625267228 780037906 145981681 472399209 458796928 444668895 803145502 346719410 551479287 84860215 739700014 784589397 296732814 23274650 861112777 157100796 322798387 55489387 561173365 615556448 494272402 620487912 298433333 277725925 590051859 316077683 538724841 334145385 455548001 283386477 337215518 314050739 606755861 739525474 545368661 230404581 500756000 502646696 793002066 357587453 248836113 287295808 312381094 26363336 744736333 978905405 210782535 568278189 916405810 115409893 697409741 408592625 245582026 697066579 606758893 332122597 553409970 194874708 373297309 681270215 984718307 977634967 797616624 21891570 484841062 90876482 884621469 453664122 468460869 144587381 400282853 676890220 543131992 740164203 655689865 340881500 80314817 526407935 249349412 613013360 864713074 188178854 25882057 579051479 890937816 50570718 691132960 560228999 479378965 408919391 456553232 875867731 263737962 959876121 192062542 929450279 804287248 608987229 631256744 844533760 580149847 648886153 37305309 798791847 830040752 901624146 292248106 33494469 267441404 135568244 235265039 658959432 918636716 956983552 498630558 358648401 692693183 608556026 796592814 521129721 263482669 1305251 874903182 910149211 492463381 919126866 644502538 269433425 463993731 531858320 265115375 184960358 974535054 28607526 252574784 766891315 830825495 974241974 614307273 758931407 228798461 65042172 56738712 77621856 590251051 780823401 102022153 770431260 670790148 347770996 786501629 600555545 783911787 644156130 54908488 524873844 945624812 514283585 25965742 97163064 842171152 7393935 306287505 237783869 87695152 453582020 865291231 793147650 606327486 258850966 620050903 886073475 872625611 405698313 431971176 93040683 569911922 577132942 610598005 584042995 122116043 329090535 970441438 351149657 259503857 140222182 528380882 2787417 194137943 23221270 294890992 148791471 436878764 169340336 840360811 265304367 437475469 252517837 489610507 653269847 409258869 860040138 388803632 616899141 752145103 800560724 393216731 927253415 310112951 992621216 915312049 702121841 153978786 52665390 222961516 284860715 967514899 60440701 623736305 676193209 470026461 537777406 4835924 527328210 749068502 418325249 508140930 273005091 447703771 463931100 449782900 217569073 535602483 439211688 446612057 598454431 969583661 880237170 951292948 952460073 44920790 444339547 656865952 586376976 66329881 69935119 54765512 545757338 673998576 657035381 155335801 484851773 350679576 794724115 382637294 452712830 848619477 239730505 307312497 90174546 586285058 984221222 551977510 705365655 452818881 341881283 157147683 772218004 4720557 460406910 131379347 392306627 687207359 819707965 239016877 509678062 352628255 835668244 17446629 366550449 724536841 179847811 55931105 427032322 890862786 429795949 857620029 618045762 786730407 55646978 373488111 8400658 38542452 586174554 79386025 85882594 455990516 57597221 345148809 67257709 786774648 824492498 190486160 554075570 206712262 716893858 527994824 886991461 54624033 211077417 596118496 168422617 871552099 420541874 101912306 731701252 897300560 209398090 176160932 995739566 807399556 223957379 424808194 92338591 756379124 798446331 915549857 377287715 971771033 728578647 851701261 526707665 644236125 142646902 807800322 465132366 405761570 487136684 547799631 708082486 276443478 672804194 664542608 378175429 655184214 594563315 104473603 253639948 126039584 709714625 213962238 563719413 397889284 757852065 725148817 53085400 844844256 726461760 412373563 134767590 305148181 838137540 363922401 301171913 455835329 809807542 476135590 56167334 384973400 345020853 549111226 125357183 388852396 445021818 694144801 114545948 642196797 51415937 427183831 443462667 773012955 321785392 435238025 808183528 256450774 449236594 13358693 214421524 253977133 534137924 265114256 713868612 337304531 28729727 917133436 650793420 621343679 372467554 693569897 775539749 475258181 178028093 189153863 211820855 31351924 975346514 794528473 698317071 383952467 924647317 495100640 855546956 755906906 176498795 523758516 872802265 548959624 705574081 47984708 519519536 791851547 620828876 247696837 230029018 795046288 152001648 114553624 135941923 283570399 106769262 904855707 287540528 452197456 227004197 389592216 366638206 693965086 900013122 185191320 862504619 107437328 516705797 11805596 606156086 675314491 692004585 352408867 466060629 68232701 803649505 943274454 579254312 179735438 725100460 271811030 45533644 381841776 995344041 663394502 250168113 51474017 332787355 976948261 219428604 366633051 481530139 18913889 958176302 609360933 383026438 608247796 550732259 25881198 240823401 934527228 431357609 461789872 515854228 840292479 610799023 716359954 928397438 573808410 410454486 253123967 303719622 333700907 18626406 194846873 302154805 306341922 287253550 795522711 301243786 226760703 92229619 793414333 249757866 239857006 12406352 717438690 306191438 664202657 595012292 614109729 960723339 846204733 500333352 584152210 975644865 282304373 727441121 240416655 139822367 71013206 659649041 410881581 312741272 16040153 973347416 599653932 989888305 98756385 459945026 145306489 656784140 67337127 561114658 11144163 49575624 498761462 562063272 138850238 122589661 125589907 649208758 73421316 626684049 16805920 827732743 163991152 357720522 201854755 583522322 294159033 868160388 56891331 583453167 159846282 21293117 305004234 291241652 663400818 946694356 184341663 521753486 847494474 740150486 839202170 460561509 258250542 783367118 546443348 863364156 189921980 211978653 118463809 134517537 466648855 513371114 277628848 665323635 698798533 436435818 666843242 814529442 504620447 766638075 313117118 365272356 103115951 23995310 4712026 707959734 966119632 617996751 365053865 296287686 659285414 931712856 696475191 209123219 811129167 137102670 730200506 40135325 626675538 874509247 534057122 110576730 807955059 170351077 508074042 155659679 754444260 603229023 730392101 358249572 727064717 40572208 673175605 764616775 677345662 360724941 884840316 101534072 68678094 92532744 302884093 11089868 57959136 403685271 795556031 576663489 739270217 392546713 435955986 658135230 877029850 595538408 493046814 772131628 754709252 372236255 891583761 813962654 742786091 326769494 389047132 323708227 454703319 840165606 113089683 660953590 943705024 629471298 142177229 662886359 309506030 629478364 419306707 884571207 14382790 559882650 309574346 90883528 622669280 599586399 434095101 714878265 838265646 22986086 773302383 251780837 724671061 949880340 956162132 307513072 959971578 810026704 453464076 23371911 263421792 493066836 421305133 593827788 910009891 119603489 399555911 45414094 438830408 261072097 552472752 87803675 743294900 162951808 682001183 951402544 804104295 437413159 66839137 315840201 219731440 547853125 785531701 870518522 749133707 166484868 385887112 698367443 93492845 911500006 309334325 275201798 843010725 799924624 304721777 434056935 419471120 809341487 389384607 356463997 220104947 63190797 178371664 762610178 434769756 251034279 683193251 436876446 460935503 799425929 36294675 551734005 325473895 529744437 304537777 20894193 380203229 680804116 143528539 954229462 3048403 527227904 701505280 968630591 435520290 282490434 294404410 509746427 977126756 775931815 812140698 942279261 58700864 559892628 328128453 762963800 830826372 500681731 987768689 459780315 299617690 270448000 290846555 489920395 857210723 849155170 934327500 859854037 331820711 677322853 905226805 973854102 749682998 608464519 514128353 206895272 266277403 393360242 227520833 463197484 121526935 494397317 642591094 299365171 859900994 593092819 679537544 147839071 490352531 206122917 650348578 584882177 164480965 802130692 684856530 790887681 975820887 191306953 543439071 128679705 521073900 629420166 920909239 817060022 808743115 469566132 270654648 556533090 86456262 497583216 739243719 352853616 15671315 338309285 991129297 93907038 886323415 497183144 616484255 103925932 755469142 92613287 806757184 542013676 16452424 90564840 68534122 482140540 789100880 119598107 542206251 766682771 738816716 726572032 857312104 972128313 467035878 766442979 130021182 300633652 921702819 905904352 744680010 149282087 526974149 961588412 779781862 839167689 655862456 998228504 236048004 639064730 298820347 192150307 390523248 174397818 238785488 168649277 679548349 524257339 477321494 802575144 645138360 253835782 929194993 174988962 291838233 63385913 425581280 776054912 9263457 433171126 177720883 412094551 660523949 896487636 495122064 35789018 549099318 53617984 47888824 665743798 615522090 926419901 472614153 668658798 342304171 817243428 497350215 114947997 157092007 880720109 519643420 982100518 570357721 512460057 933549591 325703073 950717427 401336901 296592 650139953 373272863 144138506 887180570 441223396 499150301 199638124 879789664 984390388 897104323 53156478 31939592 472504653 84159374 234927738 328078420 621725701 270956312 993534535 681541261 462869464 829806963 314678047 764242343 336953285 132883201 374598717 183968957 721105068 837526948 295443470 128490966 467834538 928466667 795914757 938204772 91734358 116806114 383263532 735073071 654087495 763660808 190256933 177093371 746319227 175202849 369498883 14823487 796981720 26945632 861945396 509718437 496042119 673040413 575552556 647489914 128748725 50918502 994104760 655901386 245126461 543239594 662980811 391974140 389178331 327447624 539106337 158617246 537443564 138912719 282931304 17273807 727985879 219294016 537233871 305610497 28213654 252644857 335474224 435931538 691215220 977700535 563802553 502024597 770952485 476482305 879889788 90577424 933399826 65225742 374882038 71051402 14763609 580654993 290589906 164194653 800511766 800033615 606618319 652303476 889777252 73293338 814632789 469518946 75182346 653608270 971215484 114233477 607544126 555309192 185947582 379730859 583366069 638359972 502516787 811208752 972049565 758748678 821100239 257283566 129422993 20777172 185850690 907145883 106996001 569227284 743466888 195416775 631193469 846081062 894181012 549120358 691984024 303233341 875354865 205717522 173161838 890397832 669477040 773672903 347462753 428417738 662993876 550837919 853643281 58385668 589167971 20391404 538726803 563445216 893223355 761774342 463870993 228517763 634402241 368736377 7874370 442455123 611415325 433246448 662148580 283886794 505996993 599575923 506305044 66607120 974934381 484459284 322166107 756246449 763701014 21554678 438925589 769006964 532484779 847743914 325877609 468895773 47249933 250153999 970706907 456036329 645938799 617033801 291961518 146985133 59282816 441345157 695158824 411910868 537053081 476136842 19770976 701055106 700668124 920330188 482720962 771277288 370884936 381034498 342983269 437558817 58533366 517848034 105110583 995505627 395677794 725672558 909987455 179862758 843801527 931501602 113571323 906077926 822655447 52180917 131161233 529942243 633562377 657524323 863992391 159317192 196738994 448208720 455853193 293263307 716239090 667382413 217807139 761079280 715991974 285680410 915761870 588703643 423061702 801351513 643412179 969004723 528050625 906692861 693061291 615235114 778757855 122053494 219268127 586102291 553849738 289870476 346352222 225153705 856087595 716920011 565961459 59923070 445119040 706394915 632322597 305613046 295792009 169401666 135067122 182463424 253815735 840466052 895937904 251558663 184599809 542619380 723458262 166760031 657629995 483608593 362987210 342988484 873798116 18758916 912208835 328702105 744527681 221878958 76145089 439533083 949733704 653835064 133875651 554523210 948179459 277336251 664012277 269159396 234716822 410431392 124931065 484891362 985248593 195984511 98059410 932337299 66701845 821754601 293851712 432337958 261168941 616788410 138168762 230014079 277931260 376755054 724242589 572718258 534382375 404238347 965374161 881576934 712475336 773310406 3438586 113026967 728856618 226087536 876207387 685155775 360863798 823385297 443304651 163423105 631021465 182660048 696378529 794625010 927812992 284882118 40499320 167871943 642394327 151897910 29569324 101554815 277621540 100693344 437433704 538555184 405080192 36813156 328986922 430143620 232092705 393188370 155554556 654984607 941606583 280353144 548680822 669012179 292326295 114236099 806370386 711073919 169082697 30832767 57601717 381874360 635199069 189397600 270652176 348582408 770864407 932903520 473920941 606409873 636065594 771625187 565434942 792069952 916254307 870283420 510646549 101124218 490193833 442498693 328925105 939170536 863224882 766093862 652929798 650373050 802496358 765690296 228114316 903837889 187815347 531580643 335517007 829476876 509298300 643468428 423850956 749562066 924382091 206189682 960694853 699019818 757805553 190566063 827764390 657291414 360639627 648728208 957344115 90680744 930425830 282163528 314528087 434156925 901680320 681136447 936191107 645809961 678436394 315693137 293266657 266863871 533228171 731293227 526555635 896001751 85290013 421424074 464952016 751900760 142422261 548969983 244070595 186257192 843451885 133368741 339802841 150875466 503210698 433719557 455470751 66686769 932987106 465755545 186513228 772042798 290307743 963812663 77281487 53684701 333583100 378807130 637640681 898314350 644437470 964218511 407159819 169621935 454340507 843216806 393443824 209291000 11735598 153168310 426418779 264863892 139646950 192806213 269865039 266653699 457467395 561164548 293762874 319036684 71692654 216871971 526819794 290229932 231024746 621659104 780599721 859519188 672271306 765355820 605785007 108548054 898660427 855702852 391106139 500088714 959624521 245308824 836374519 325694259 791225009 705497745 569195870 72381452 109401086 846099597 943460698 72621165 892891275 654794542 213856342 46117089 450108919 932711415 101109551 308235946 42129479 975604300 167281665 363203864 540558457 144046795 384554023 248640570 604692533 798933025 818625058 312557008 421273029 529885972 964961591 399049330 83840541 605296458 94396644 215946662 88733629 181396487 189691520 774516445 94471646 772161484 196172092 517124531 193977179 595694581 283678254 787551453 560309112 840618086 247262814 250705469 179702728 256078151 701497958 338473440 408931454 724511865 966853963 128562407 378425235 806225045 20571764 747549669 995208011 181622363 552220084 842314352 303957749 894100600 769880475 49279824 751844905 423396146 616078219 377522229 521612258 645303310 273581253 330671621 396983712 972209236 571529226 327017684 729361335 433295101 275448539 587700102 277389621 810561133 611402936 479764101 840661125 104476093 332304790 459439032 204008011 761474283 254527009 192022676 705465469 773024718 656543772 669468035 944138097 476030233 716157763 298095773 821028891 615557639 492231925 857394924 382956338 266620857 33445938 918620275 724327682 539444213 435615113 58690082 693881732 556258026 8228439 726798267 465196626 271896929 68099098 987861505 18146327 857327627 673415456 495664786 739853192 129147836 780006210 102184210 739048064 757624546 815096513 54810767 508815847 792137978 321387722 795617847 864841541 246982370 972320978 172370656 175505823 343305290 89925747 523205173 596941017 989753293 539207371 292061556 965008598 157458927 469165070 482905635 185915224 731579319 542748946 4071029 187519525 149454260 547103348 934204296 824119183 342643695 379146211 896612361 663616954 578088739 697924607 280566820 526424169 437780003 318038788 674167310 924089346 201229832 309583327 454548617 859971855 699053570 488086540 43207017 430674954 847230632 933540798 167269580 933956017 382598404 122504968 627169650 780301874 666917592 707918293 568929672 281783766 540318557 213467076 675408563 325557411 882521907 296502735 504642757 741601410 261469491 347344602 378210481 977786932 671575956 358075023 547370390 177986911 738884938 91743629 421736876 209342979 123987754 203863927 381189313 157339460 492373853 80845348 280778071 69525401 636403762 710310075 595497220 653990308 406068498 661938782 78566523 417167818 940746555 289284616 832949772 531069196 563239848 24517406 200262876 241728370 710017396 16808027 713726683 965556502 117119174 323026993 533520039 958643882 560927812 845418265 852801993 188028780 375640789 254767214 100537104 895774168 265780894 620867979 190812557 629149415 440897050 167529181 475539326 77258549 587559597 676308761 71716203 74114650 347114056 870002224 423841658 789170184 812043162 631013436 477693998 841328945 146051766 920676602 592513703 52647319 860311771 324000550 907733137 253596956 156586611 289658860 145101256 770903731 127269173 152153398 292609497 490635751 256218910 510097637 447662869 686873003 980886697 458454365 497448005 888375779 704796206 129464017 949332562 410382878 744218281 372456370 543640972 847219025 11037431 73316775 868365446 598883053 439381703 479138525 849518178 661879265 706511892 637343235 6231743 999582593 654356726 697761667 19149385 890569184 805528847 391425408 449364203 319236795 870445427 901003492 842385911 42058139 781305806 567385908 818816657 205081165 24914040 656359672 202966902 185465181 82984918 749795455 437099445 282405617 909633140 873154300 363254993 932583026 202202217 841496108 145895195 595490196 506547206 773412378 341749012 130761945 742446516 3213817 400457914 988803762 278644778 486661582 555403942 61300268 596853348 573013987 284781437 588357388 67308050 387779485 59253114 783276129 222323542 68439376 208975280 583750249 479117969 71512369 289616130 366905112 7388342 654781037 598167524 691026384 670848452 556880077 837631161 242136620 741544109 156264829 157117156 691576150 446705407 433755455 787385247 31877324 975924644 279036269 96723340 663930845 534978031 552603304 337028093 863099470 674714687 430962501 283686227 809044471 452785775 21774677 386630523 371132994 301462465 885239335 593687208 654269012 718217669 799635406 783601565 821531835 935846229 97470514 966325375 867840930 184011390 946908536 681045484 972286040 293605116 674042033 262410504 765501816 984934021 720231276 358510635 969407705 899704827 160231644 623225427 170297395 581873860 18166363 17628821 376674556 522305325 53769305 310218910 127659784 182249706 404263887 87517039 100659098 668938602 419011704 868544199 47364483 629263089 688526700 586014663 662707009 774029744 767916148 747964803 531239205 161561819 865873774 104299993 637708296 528121614 635654944 663895422 312929234 770300032 343672680 394492505 853936181 394043587 814066484 869322224 966728972 396360493 47122896 652144211 902314631 493774860 965721687 467780885 401866253 407392920 359614157 252361806 377870252 313305274 686027294 1312738 896626238 640772228 656779743 359804200 945036496 369272117 603841962 751510664 479411784 295902424 52714536 479870238 633966900 871414497 364711699 326155766 770081468 276816393 873805576 721012325 961483131 523463489 960948086 77036497 783937602 685614760 34848682 121372345 368154480 634577325 726479392 753768485 395504026 363480794 922779303 441098880 10289191 389162787 605269918 685794864 14258858 168014935 130520868 558025667 23647485 255301117 785946554 847140537 595013851 867739526 727590135 470707163 623032362 249276722 206014579 793090248 253232116 677239235 632912992 18300153 347627793 100394410 855236714 928052806 317178330 732341749 85429012 652637151 660878471 889344906 857167942 997801909 406748292 838414724 215417216 377179094 65302236 75690647 361654845 975965141 781719993 352675625 763421383 691446078 421432612 776647455 136118834 728623448 631610766 146140610 356615067 206920254 586112169 689481686 56719805 16161398 498518529 732564545 325036844 668624748 98246508 476210796 876702192 779455766 231693353 851224425 880918187 803782776 346865048 696512405 454923658 393337322 695352295 459600252 450527160 497623414 451880145 118775694 491512371 770177070 140252528 460514784 867028702 119140433 268264440 693066198 988548774 603041217 440743596 783064262 540258954 307235752 226193799 467052330 501041615 778838500 845742069 204202630 313035526 30767695 932808589 610831994 79533986 914342532 505997106 605203726 748317845 755444196 840214170 421828329 858917569 971978209 548157687 771343390 842753447 445386831 460731536 499215145 43640369 384021681 982419574 515694318 37015495 761365161 867739582 179649953 555166535 589468088 504125848 163180673 525589467 195795743 386656435 721468178 186123648 41980171 555299529 697749731 104748655 715299968 101287516 371399916 398505862 629262247 504468247 223095722 188767725 982388661 940631415 103954265 583819873 649116476 268682130 259453477 74447750 330062340 798481303 46696400 514964905 574983236 658268728 918871060 397899114 86525936 901858732 192679393 719835638 71672316 123443835 602714687 462963816 140530631 458851545 679283287 282830581 916659527 243359406 10046568 798320387 752092916 295944600 582199172 795459962 126299872 450381248 49655528 470541216 507702296 219555433 273411335 176271073 747617262 574539943 374127030 397714337 348704450 724761881 853422384 284052788 426328368 279246678 838926377 496117585 854852884 912945521 566468857 567757053 283522087 23328096 170355632 282780794 24689150 289392278 677914709 512503361 910746067 31724286 852054040 14964116 418651855 704894288 704995563 231650493 35296732 797386045 703115446 924291108 386069561 412425032 154777818 339718235 392820045 534100811 97647581 772609882 55393285 923699595 818408542 356684359 292139580 247714771 711174274 394824567 93947566 159042082 391485559 291505114 655546043 414373867 714009171 488223250 356696209 351594670 399762897 760088370 394885365 365062565 178523459 502667933 799912234 535570474 554389209 483130990 369543622 544872153 810293764 917816509 12538590 371693551 931750683 255172937 610089724 137403360 60622353 865042682 564818622 158070035 175266348 534412980 364110650 665364000 24608202 572780151 854234964 516662789 763387930 575145865 924894615 582042363 501317174 476265963 809895144 949463590 457081376 815695385 195268562 652077000 340373805 476333484 584100504 212083532 753214443 947975744 537459552 292495460 236754059 588955007 17835476 643311267 851892832 609362898 114102288 411053158 530977057 241286748 53788258 799095375 405874658 812049151 644161277 776457342 721988570 192283591 120715261 973413777 870733853 9915618 53139483 845042402 609963119 203913606 497253007 632822988 591774319 472480279 998362411 891321432 103443240 967061853 705843547 514493794 954310627 47155704 515239222 351647771 888379111 131883338 775030947 272654122 979112907 919396780 253845281 587765000 739094605 232899350 696131821 745320200 412675338 844555146 310231610 946331440 70483827 837848688 500968157 592898580 375583769 348645344 124204043 690875013 611984374 359511545 128406400 223043657 575776788 695181924 60707087 965486506 590902250 302144514 13650136 411275415 859646303 325012800 716465646 998457573 72430533 507449059 925504235 532953709 479633757 543983358 965282145 217902846 60533184 502870481 157618582 98993511 711502654 244189843 987646598 176503266 854950589 925388523 295301228 917663329 444696506 780557996 474401378 430092670 788775460 151814709 905905030 954232335 380069376 161089341 445922241 101271893 322627913 660704320 797210848 439273741 536144475 660489647 166441781 819566702 891988454 490076335 630998848 342755587 539741870 204351843 170819920 1537126 225336929 685238291 484493199 464778153 428839505 669608369 813676193 687438760 675750545 609945514 340214796 317710572 210892802 164913057 930353413 149701305 22403614 334569215 899185284 964728690 677586558 238717860 267572941 592733089 168320652 109178430 329854485 882075504 202432842 892718710 900000960 936633228 93533744 635643434 737424954 125154835 75022549 341240362 443256513 747568999 417682492 596162763 300160981 503774296 317056904 320970654 483753926 682054761 676555915 297151613 505160685 899191614 425515883 717157281 7556459 267486426 442999024 76297132 66832939 537076778 355002354 542055666 551047729 663241550 874406269 104945961 732146373 928042250 777293688 959220125 9235039 310205506 132035904 868205880 289706085 800919855 387040812 465006381 96329102 654137774 987581003 429329374 95361250 244257192 627414483 168342345 851536905 548854379 867374956 791511656 906157419 54601206 855338416 177376767 27431267 660225998 53713638 180286167 570996657 858001406 858475432 232813305 345066642 952912865 262492473 512049247 246658395 318348404 406854799 99022093 813571131 35294391 502949542 232389614 558584877 537566808 664820374 227732138 413566919 626755280 265256179 496511946 98914050 6627841 131202904 851617041 572465449 940186517 757936 624283962 183032243 82385994 168967112 822470195 764472084 933161499 232660523 173271308 582372125 841610433 516035898 168074729 275736773 609297925 640153915 399205086 223830411 944730001 768257276 386177142 261159943 104838005 24171858 832111060 929097076 939817345 513691636 660152978 924114392 521522024 955160722 897850043 658589799 922859590 641168909 146563287 353887391 267286905 756275087 990876984 122913772 845751958 203844746 610770450 19857362 274770373 90934638 175078311 175485815 631056255 527450510 848841702 939724739 237794976 459866595 586056949 35494223 90971168 385097125 954486575 640883645 359319927 30016632 347562945 183015444 2956905 974865857 466878477 936646005 996906702 849520435 323729989 917550607 574604613 929180291 743979281 671570809 656131833 373063623 39302245 731123896 109283582 25482411 974300879 996372156 919157734 45201147 943144521 708868620 532424557 458393645 143077375 319243846 662051842 535618345 565462761 951951311 820212933 563205923 733941864 827537114 250588188 648525970 539692305 90086587 207620933 124367565 810758406 992235551 74856984 254501898 791080411 752488949 900478276 851597620 382349189 708510636 23187404 640016251 399773541 768389852 520811253 42817181 869896179 959276990 95112077 822721453 834733258 602046576 822541327 524274687 620988935 831589436 768034772 478130389 899806494 599343628 67976474 173901368 270775547 220341658 981860116 963881586 586301760 762295366 124709743 404133087 471001459 367508791 17484645 983399429 750881951 410034121 526550479 451879533 543958900 276470396 975842874 307255015 801937821 926691936 503647667 324478988 980746111 546743082 506599131 694382712 686834645 672776052 617328647 778012885 867892394 706099788 299528140 39037498 719512912 214899368 637665016 785993963 289333465 222614074 73413416 226419138 624623261 630465655 456113473 939429671 57200609 577762634 532666143 179009983 71438024 64886602 231679118 755931032 724069815 400430884 410869231 474651942 421384189 85391507 11550169 471817678 419015096 672850256 961216327 296371851 102554745 843711404 956366382 457074788 661554927 792717643 177902365 670070238 198413556 765787082 588034262 634592354 242493923 899515289 519409650 789248558 145785072 270653933 116020900 671805078 883714704 886061927 156090134 956834709 837884255 168333749 682997168 135684428 579461502 413501905 845631496 61199137 44987459 991855660 404869202 46772374 203802400 649516492 106529290 367485370 133887446 553054317 589351681 77881229 189118562 775582219 920307102 35866334 161694340 171284740 27620730 436946719 731313616 418962492 383921057 353225087 863827153 140680138 748243532 310938702 793171960 101530187 996498804 716451732 493341404 318868636 523569058 421888109 744272511 229628793 433880403 896364360 882437188 787171270 304928987 338170715 910956938 977344892 358924753 49699668 524480454 567295082 281576823 228706824 957116537 210179232 322687941 584503756 427277384 753075686 370336171 658661114 366736460 165359949 528495081 467684493 341684677 267080168 174652774 41768660 570996475 620901403 856507853 876808713 833321764 135173079 259525561 406076923 998583652 131615824 317793746 533679002 762955959 925278425 426934289 804794271 62930339 884422235 734618263 480757398 824960477 869518453 167726374 106819356 973302463 827357504 699227463 447423201 848498968 634843124 123522659 746008812 214770784 637398608 670623078 782723395 125742119 611763155 93866819 110704337 496143781 659741122 414045430 857577791 103144600 10086197 707623776 537703046 996581430 517713966 8068883 371277638 939936838 650629259 861069049 270087093 103934393 109891724 199541843 656013522 279875464 744149543 699308242 289936098 372047480 506756464 593935570 728130611 26117423 243973590 147122423 643241875 36548987 775660673 721152991 413103569 653458456 819100968 177831928 512010675 67042093 628181145 666011066 375082374 889946141 27766231 321468192 579390278 180108800 718477084 824614166 955865215 227338079 470175476 297263827 417570442 217032154 797269671 87223642 89535110 603915896 136954365 516389724 374089979 49919860 956047963 606905775 454970325 634902637 170724116 7149305 347249304 123545687 10196290 369067325 365259764 668596573 483742361 893876355 483831573 143458093 848843166 643845737 370411635 354083589 812340079 713538342 115815429 946252481 796042183 392544631 853915383 175012491 136375214 208414019 219960891 796817235 465126975 751358611 412765950 799299065 103827669 732806260 53817423 143674419 187399884 965458262 478015491 966195865 34212634 901939632 965727525 9556177 78181767 824479345 318182647 31633016 19224885 203824272 6660263 3409608 674896676 723064832 79903035 655339960 134771859 20130321 652023182 771200293 920096777 355149370 127080433 860883107 996916255 258001506 488595540 471420721 539547473 925145464 606524213 46689591 457635636 14039565 447542745 81727567 47644476 350272526 210980924 419420975 238823448 21504087 263791008 696601294 992493823 498805606 282909842 155185355 624241743 230624577 913560386 701358926 189427938 257230530 745449046 971466283 618386980 267022135 907728869 340535976 776928599 56797344 310819267 492434585 314745296 762373109 407683131 328687146 472409605 346695512 56368077 408705477 159929517 632275473 243184246 729458427 806610317 146320448 9695754 185224832 181204647 956119133 612369947 974104016 372197714 331599204 415073513 985888913 473134099 800594305 506782166 781942615 837544205 766223419 651310101 77062079 111380981 184036653 446121064 273055685 213715056 804264936 852779738 80182572 506036526 544686635 253806736 372121268 508174239 676403478 797627324 337543261 16254705 454232331 272861771 837891615 732895534 628160133 974606088 983383487 506864152 970823148 944151272 4104393 871467057 79180096 777445464 659646976 926750869 716188180 840968588 868515248 188791934 862523371 289136996 421514297 808179178 453573700 323985308 145765144 158847648 894656260 398645162 16896554 721986127 369798024 53480180 922514914 609848093 542244667 616616274 812867612 681483652 696768148 853028494 799088339 449322363 977080112 786567604 356102505 616307290 91573420 715256009 849276356 841907874 868973381 851293446 119847193 535665214 258093978 678002011 479461829 153125042 97126145 163132776 77643130 949053669 658925391 961389079 327621618 809116422 587813777 395563189 285881216 38157638 953366266 528001010 209409958 6263009 67733721 14525762 868909639 63036545 815516671 907003029 906580572 409867114 212420822 605239228 510756057 771345671 271251473 325373630 14159570 513377815 877328262 702689772 352439314 598569810 249122210 219787905 783923936 130521192 982810242 863637006 691589330 671631403 610910000 566036993 380928358 681734509 418780348 500324782 344551749 180223303 884728382 832720686 470254513 618997504 41924287 954325277 668782198 994644879 873190702 262409539 860224481 453594130 699904174 39443070 268620286 763917119 790551064 678098575 134665047 554219540 585859672 584651854 550512290 415737526 318446043 565275977 597568672 576215723 886490634 633662827 21543574 661751360 833593326 210140631 418481701 83285431 52502532 412809460 3893301 191015256 811592863 67361545 914534262 380374271 939884296 712659679 583260052 132290305 382558843 480815549 330026249 760492485 174115117 862677307 837194663 181483797 723433438 269622104 84546959 988390559 598133046 102864516 173245213 274905158 835287792 818397260 171199445 453706589 469489290 105407972 203025924 872077133 918239172 40141104 309244809 365969142 946516666 926665502 376297347 71523003 739829732 457256917 995863701 186842096 878268686 955431933 778782255 636758870 654351095 106452461 831565616 624271946 68690019 105368987 791852349 306596759 553349462 46717429 227542767 470237926 955903553 747964515 305380286 613151124 328974462 611857820 953747145 963544834 328108561 664377783 387907160 189939658 298399301 195703160 829355965 107923489 888010737 923839009 448270382 925790086 76134292 388202642 291660781 911762644 828529261 936744867 648171973 759789399 62641782 939078375 598776632 403019033 151649603 375833640 62489463 462847972 121648143 371296787 339667216 525401760 459987694 525447733 935443453 540331975 827142762 863553521 644291146 696978545 800805471 501832345 271771449 722451661 343361644 637217019 892642751 971914668 452829363 242260119 593514770 165683951 523501634 342621531 741908380 579854740 292290623 945205611 14411160 789962612 695575040 196379989 386964692 984518672 525749962 897738256 979604343 649916793 1186628 30520825 573968406 257885405 373354476 424773343 472274045 625759113 16996368 283527045 554373757 340194542 294510204 68910843 210143442 76149502 225345592 215332290 472441219 845358567 471171403 586487757 992022120 389336192 859541100 715053165 941244223 934506213 185948658 45216653 418071454 510104391 396763671 668965328 662113464 977080995 548056792 493650758 313751172 897507188 903368158 533032718 681287436 891509213 170384533 540568187 754379451 761351082 564235605 870053175 656665899 902104777 950908935 973977683 762506675 927682189 772996 937223613 747278885 765973066 839956245 790997336 95778584 323515227 187081598 573488670 636486819 957539875 350630776 862200965 261584766 559158193 433430753 341364617 49134141 158433425 121871595 126465313 624862751 596267980 770971427 193641041 588962022 308592833 309542573 180172144 854140551 896812523 979223482 999410315 938739444 197976678 246139020 584435956 731890259 835879047 346706937 552702566 48851469 338806059 951505376 277340134 807054247 351244656 326826914 623748123 582705063 317045678 182863088 866875906 800845799 901819799 298148643 837821454 438265464 911006225 607469856 532883610 407371897 552450072 280460834 99918753 533036062 16031077 998941865 95993303 452380273 307272211 284329702 145614779 940282386 885420406 64908877 367798402 998636926 420079335 996527732 798404830 125332131 526778673 211974721 610820373 181400087 330166959 20825030 938868142 48167258 48225019 408944558 1928974 929315357 779652821 925562287 56154809 838676404 782744500 798428068 433118787 738856647 377373980 509294518 522649529 933013699 84006409 27212517 302837525 383391027 658581134 713074862 861156059 639247513 166126830 882595710 234621117 108995385 993097461 695739091 378612890 50606982 985369780 440198899 155210396 23154502 587336244 898010195 873115629 758018108 862817738 836263888 756183737 214781089 832272190 443339642 230542055 485555199 867572023 230621002 951080898 813132809 666501156 834483645 563534947 788200794 732403312 727146768 53203131 498516614 967742737 442900892 384209582 142728894 216876866 902803667 770705272 561551144 325273948 742221414 581439376 901199479 926953235 893039669 824263498 224827927 858078597 377335755 411536813 212349273 483037889 955972047 316812723 332054910 207200792 914151991 266237518 367667906 417318424 240709232 69074671 856611393 661237499 44867862 475945874 894915788 888151813 804785098 523568524 890574270 956679015 870835775 931424674 10874805 832782703 731133512 492570073 488034664 835063819 980237929 443355477 809284191 135538102 264410013 72690312 106404542 643244319 238126466 324292144 939419802 522886847 646623920 58971318 793160758 408897079 162668364 346529454 454492198 986852092 818910599 921633697 498004370 644507687 129084737 209579639 914943516 802912022 878125432 321147854 105273996 561657960 218254550 579610253 313435599 893102953 587204580 288520904 997357001 940588827 368164329 101980539 697384769 334824266 531364921 692164797 58555399 46007656 640283010 243743635 847622824 507847537 89477386 272391994 209326127 682691213 457724362 924428648 309839716 221041765 803285290 921671967 154549184 761035177 787515816 472965108 56460943 558618212 772315804 276892888 922970278 848601002 613565534 492936048 836988367 396900384 528572096 409122425 204224680 404077818 288757212 58614100 251235161 804214337 287162702 488643911 256411255 694815343 825158618 209668095 682073795 242555454 537235400 7964864 398503153 747231037 339052142 556406527 322153162 586954480 57599083 82632488 818146129 682562928 556228872 69949042 864719314 533299246 296024952 127689498 369101149 219552224 222041623 433581316 436656424 533632151 232655625 117933577 50508201 667156140 793872797 434874959 515866825 684367066 559490894 42271305 291525112 888329075 430630394 687397342 651875839 226412134 833657596 447928591 137141283 390843826 723197613 857924145 782678371 702812741 827889132 547117069 354628193 385921499 472941336 571570793 154172947 125017485 247572454 749564681 703054102 709622168 445997874 75211333 482099851 23300083 382371456 27457556 826180583 745120475 851344757 30718146 570804225 737894658 202990476 510161863 786881682 251710153 430430339 187383181 556769668 65287078 433052767 253995910 519209036 807230808 603471845 17971123 922638662 290738781 315102620 656716106 998163067 560631752 620605919 111295127 565371629 819939839 330880157 685977447 377890972 25318475 704664848 902988662 637483327 319291220 57695002 716578142 228305180 167400562 211344961 598872906 554914185 950883632 336383871 213027171 217201840 177820056 244466390 495005602 664458410 649983633 935347457 991516313 52675867 865119028 3780740 438974129 57660613 3913367 186083320 574057598 627335058 855586580 841347768 169300586 384220154 345501980 983612327 449726721 965128118 632621879 51698031 789091671 838349812 396920117 128836530 197274958 496268069 896048788 76417605 116121225 308940813 583873441 610027324 874888446 634507976 444415583 545004877 645246774 791350170 944650348 820973298 678631428 905665958 329533013 821666958 442568928 238645606 463024896 671517697 995711382 723300492 393493606 522755158 558457458 79456408 606530099 521155572 658235301 432104687 896285337 938516208 200418209 339735866 918957913 390647952 708944958 327556297 17810511 640916105 470019638 474057587 72705016 190428310 605265711 689894601 840683921 108423897 944405094 526439258 177950671 744992902 124457543 474629519 37906666 304574027 828392824 710275431 124879365 213270911 310530294 800068580 726277402 106232687 407318475 573356737 967758465 51124494 32172103 71700903 891584057 28103654 360845079 139023126 228333191 248684907 908601462 849239759 724322360 396550629 524798033 61380410 350187859 47226533 710874228 794242435 558971707 648643198 467662472 9924636 726872528 619893681 137452629 999345398 357184954 275095425 421778045 87333247 546843888 735253901 491159327 511245659 797753649 646850175 584539883 386502033 462926133 355833553 611369785 219513082 238190106 540797545 543831527 245189559 577914146 464032594 232542944 454592278 960751109 530272927 193136201 608832271 926104356 981253204 880702262 608470177 650172279 601949187 403553950 900768479 947508244 106197427 632262376 285593134 918429970 650164250 814628990 414724277 809110351 140899251 772823717 577873300 197535810 670551225 579524608 9461799 365402792 34607134 221782460 508634159 265272229 560046564 266446720 495579157 963703137 816109888 802969012 712780610 126698191 487018460 813690062 324241993 146918990 418460591 419457548 966543828 376216754 983634311 641425994 115512389 973693285 515625678 185503194 78920449 604667477 84052566 864540357 889144805 468357300 207402083 223246172 357056461 928782287 349996674 628081601 16961309 87756023 742820014 96163132 622753556 617897802 423147953 852616205 52170128 140975237 560547655 727578302 468203180 972620191 553753689 914680086 797904424 921523475 213762538 41143645 841794429 372308037 341262178 65643281 314896491 321836167 264630005 148434517 372144244 2221844 435631697 321994083 777977463 999276181 686344582 898166948 110986167 586473254 571366408 160319960 814301263 282328365 123096202 277891646 748071366 8192946 115674580 842017852 33255542 557393437 299523576 359994935 834159058 873316861 225656499 646519802 577003092 879777037 220598131 828506739 841369806 713019215 738721378 483644914 859892543 158585200 690208129 405233744 621603775 30280876 576213938 902199310 475569375 399160909 201695230 1529942 861533850 668492359 461091459 422753031 753941088 786456072 579370846 44367432 997691576 155840402 30368573 880557268 713498998 558283339 899546235 52828383 814890565 959477616 133873001 182498094 394747420 6777895 252655958 49190454 966535435 798256532 674052451 486115051 687820047 674407133 130128946 816506959 777161264 697838993 692933058 424521896 985104399 582135036 297659699 263836215 651848236 27928503 918420632 874725652 472251877 757662342 957421523 835184099 321520398 715026496 397923992 364739992 69912653 682880313 776452751 783235091 931486083 920976339 298937266 72098556 600939905 84720672 595184997 439040551 319636640 285422957 281632216 408481539 574947411 993130013 479757427 839847499 238920470 403117058 36059871 252291241 675141807 990282757 641974721 83208353 409700004 273659534 772433572 807648838 946545539 7678079 309967817 38884276 418441183 387340462 935963052 77283240 198698869 524686442 596215375 521614986 784289237 213677758 872136499 213137694 84107673 456301370 630036164 923839638 332575314 304439072 205904844 367110185 248482703 27681509 931086574 644276666 546251767 550666076 820693728 412712045 572960203 156037525 885328308 992978217 95625742 402622876 782950699 638588277 832580499 323997837 28741427 89571723 697497980 205076405 599293746 143757120 23432577 854770357 764683361 765885874 513265169 869756764 519541570 600738582 944149255 208486739 431475632 865873123 813995685 792013857 909310338 390418338 166505235 594846706 559212846 319031947 500761125 2494624 556353593 723808065 254795127 557869180 657010277 474048779 405620164 700554270 961326855 752442363 891523793 976330999 782355084 120731373 127629562 841982991 373514222 679649371 177746386 295854469 925267777 791933782 775050523 495037380 956034761 349042390 469923585 58213925 901351801 312164184 934165580 601501928 607467558 352302776 590673320 411395348 454976362 19656833 452994247 450264397 853439776 508092467 111642222 279954082 720212886 576252440 778867388 325753119 104737453 841397748 888531489 355026599 325822515 337877989 686892339 196214091 412445777 955321039 44596653 859528121 482893572 358765168 529297233 616950606 656946208 654352435 426533174 993254389 754864804 204470966 399389268 650402146 103916628 129988443 360421128 613221738 865788367 109027644 943115868 379906319 265989379 288144652 588217241 404464418 369729872 873431267 783139602 961521314 667814630 302510777 384576134 291750824 353605525 688705406 184536268 709607291 405150861 382833220 657818516 6530327 650014426 918626493 271024625 292777165 627820916 725368693 708187199 515538254 492320792 546677055 494995241 665985114 801374604 846041514 192165188 157323830 841066443 381317132 645790215 91779334 56275780 674558557 277952658 384095243