81 82 858971617 878698750 491615440 979927020 782512986 197320581 646898595 162420214 195093866 867055969 203763078 850231801 361381419 396689291 415762110 941416619 341080959 956614428 323634574 692534252 705005504 362298047 168979220 212860109 270669027 585868316 846040146 877064695 551033725 837769516 235797727 98049844 959063562 336449527 674737347 46850195 371639622 863978630 241342586 986295813 149232066 904650636 197873108 465890067 237974298 553558566 640538747 605748099 751135466 910530638 215777891 47037529 498095893 819495747 956732453 229112807 177129042 815873991 47343803 755220071 272171767 80088678 164032088 469398267 577196479 330568467 545235072 435754205 89231185 865761968 626107990 817355062 948620099 993674803 424802632 23059978 719007592 112391378 64667693 241752400 292404285 130159163 38 152860750 190483536 227842503 334904983 387008762 814082334 787864504 972582241 756031099 388391663 308726079 888711943 927932320 803353811 972252258 721999504 724050363 956937271 76783890 672333827 532123490 578090001 521115384 498706054 527926451 376386312 231876881 232938338 709542830 180136209 400582971 3754954 579046079 847963938 226588925 550115483 606591013 797161065 73 342386771 799648577 218514066 779544094 641221830 10976174 650532790 83319062 104735976 918799510 606723591 603304032 621351700 287309928 133704019 752947566 106144909 911254643 326462937 632701669 819813726 268461020 377675159 162468391 332653866 58650679 187202437 697577238 664859845 543101986 460019198 954279458 728912920 535172420 470296456 336331338 576343717 706435064 707375625 847717134 84289946 391916818 729098360 87725244 359542573 707433227 753715687 395307748 750673046 882530842 109948694 264792095 148213411 326469019 826815122 658170875 69320454 497533523 343902909 315849054 458971470 637425323 59643701 836981205 856545075 467952258 345599162 991292313 61258706 458544209 764851454 602806305 647912486 72 887127012 696088279 919471797 889276799 822895598 556610245 976399157 176385278 495964938 581798438 790177993 439667992 319219814 22569459 858716416 195883094 83930097 278402884 472063356 762344356 591653298 34405398 546786324 126570654 975351808 878793700 474119052 356357705 829928735 244677198 343038862 130037814 865286163 806629023 597644218 385212659 652755599 943694674 890165510 8061740 807624408 286973854 809303223 61119105 645498029 320803107 994491655 303447936 971067338 468230879 707485529 867770612 309991280 433189886 52325963 869088062 664773072 655966681 84829444 901091629 87845618 279521629 763128167 47382001 603247130 178617768 75751623 124512236 511280115 233275094 481280230 977767749 95 202680843 35264566 426034950 205960861 527654373 656568194 683317783 90941582 891265348 675514744 953859658 44965193 728336702 877232701 76244939 184527255 656864277 240593656 814921500 311129066 646526871 319533380 631008412 223816454 821381623 134411991 726081261 391026436 821362688 72933426 491182763 650653903 641918953 478962416 133006989 2720716 832723569 782707839 11922575 131414331 667318351 415432470 733616869 853681737 163314917 462530223 900236491 405802620 987550690 381652388 524290975 226658861 435451831 56250536 688718198 280866900 532791324 395485231 247535677 599190132 714052230 851363818 14844478 42634534 531241829 471383033 796265293 342962837 808686087 418032050 980608436 748481486 234173658 618074977 534642049 180631622 126939071 655216161 365528229 935007466 289710560 276166062 397574818 133126838 608547279 110887763 438227699 102326368 63623635 577882123 992552065 265208672 47720227 656354977 272389588 87 36015125 429595317 617884575 195391883 643030778 462903878 588788261 785086616 287974429 594531757 566968920 631806904 307016068 431006669 313279198 906314915 110330375 501765644 436903728 395381880 910541064 463742968 144107908 961248306 111923188 694006616 945370731 273795058 162600786 855914339 708004116 141821315 697749599 175938303 110307600 799607590 816417304 839671264 657468816 755488650 324694360 419621291 893648408 141344909 5403653 741610161 644879402 733789698 596461372 94224569 201469718 788149079 911840200 423053365 827258078 265924470 541210211 145978134 690699912 999653319 629699871 788567473 733536272 889283641 489002001 164810091 546964980 20164609 230695239 676709640 3814503 509586311 812183707 925390711 978889612 14113345 637479509 978430391 392289889 303894106 702112898 218028865 427463442 181398900 474364094 802314432 555384072 64 406885033 535613245 727189929 790553018 348592211 284691264 902699981 783998690 541157240 822222720 386207283 558943793 54077664 440852056 31180605 897004245 77765612 862424415 410101028 656943458 228980286 371641369 933103489 888849795 143595057 811641839 998704950 390296563 245347699 769084066 943599162 42281482 336696720 240023733 76197169 974777556 755869766 489025358 795477757 996791051 112432072 791264972 877486539 483775067 977560697 687081823 868190368 805022892 874703476 248513020 502136379 306542811 357602845 789218693 492785674 459738647 462352457 531229335 853997470 813530078 725276587 260787079 513451743 136395387 8 861685351 447680330 81189825 104624794 834899134 522423869 185649357 935059697 76 562236665 958181512 388304493 851315152 856130251 559609281 78142356 916219056 480691576 902287131 584937202 927143117 819230411 489600824 229775346 86358580 177106837 426822341 399028140 68752339 15275802 611245842 787755014 359561786 439525336 755182564 781807449 835721309 175581471 520009114 477555771 2747817 44796558 724098434 829417831 817358588 601592992 127008242 500619884 227629642 178300389 489464281 918618081 626936253 831250252 377031196 700081 275519843 135336707 492469549 906275279 595155513 532879868 289152131 381764884 317394328 818816621 855949946 647118561 589270240 914023039 285010207 661159152 975933149 199597575 104404761 827929295 198602542 356899477 828925319 529502784 630745437 75343332 691782172 730208581 438144838 93 668347219 835999710 529053075 953270338 799172692 32269554 265249802 512170665 687631624 276552215 647840069 742003912 163928582 244011351 122393568 887487656 393852439 968794203 890923253 729382132 385951825 999759213 478252722 831569202 27815632 828637326 679950904 202160310 15492417 450252391 622723316 941473697 773893147 487507774 645059761 868413422 495742873 73640490 801047968 948723298 382567305 720880746 141138400 329029554 414337586 270337096 69852178 701775468 156110868 795053448 140618510 656637354 373329147 328185915 172795744 351621296 964484147 227189350 179587210 146118960 852673254 491748749 832288034 556541417 279248530 89470140 278230828 119057437 526159210 276199783 216713450 473151621 7982111 508263795 659192026 356697906 648447742 716263150 526375847 933649577 516906820 503634454 900422662 584447114 10148791 499093286 254568791 172119414 535176528 460112293 684812163 271714184 525484713 16 544101737 562297472 140770121 430469837 665421377 86432011 629201544 92441048 919414058 439278301 812822895 558089384 788893639 818767393 679626696 737632069 100 906655310 183286220 302363371 917945729 741411926 252803584 394634282 301515883 976435264 456596092 994371689 37362334 959404367 264064119 624344270 457401582 225201022 820549608 394383296 703124220 243025015 197711236 43247962 685169937 42531909 488520260 847594195 105260195 669465723 757488857 412032963 197949030 770198268 988883592 489975267 973015777 512276667 782182793 97945663 52702157 728169419 87850452 363717101 806557039 611110648 42206583 305055249 611365878 720619752 821320359 889077561 724584057 584367313 52307590 677288250 209822992 203852516 424232045 516179504 420362759 718532514 276400138 146820231 370437990 435640288 317461164 78340581 798956941 951012578 208662372 923876657 26975789 312324239 394901518 395933472 732543876 102990044 936573763 750526316 380021687 990510980 312345612 610650662 767908246 824731729 918275824 296860434 34923997 690771579 627345471 366771944 215129822 225506402 93507995 306500976 312092907 63429331 819493700 531413225 926114119 54 235941228 802456163 109243938 71454177 301039696 995499289 533047674 438606445 686493163 625351974 180136369 410786587 57079982 563076743 215218518 47368908 336449414 668598623 625385026 225407832 840135793 753551021 82333354 451147341 261568132 51467820 43302066 521962241 924471980 942359579 518609056 936669385 349161690 90552909 947242049 929450854 111207267 424195098 784275090 446248601 275073032 405129979 127412627 522654995 796707455 488445682 58678923 503906050 351008326 551426830 549908939 800109323 841379334 990956096 89 769441827 586652658 701043343 907448145 278868712 878466308 283056494 573469690 592585329 319604218 376395421 958684407 478687466 371171407 587951061 715048410 509275203 68065001 105422353 946061593 928619334 108460463 409564811 447241126 846413196 288653348 676400261 786744914 955054680 595606531 692104927 135729750 282401290 86341306 822113070 637941570 514966498 30970775 109237153 180298485 400137996 798125245 399564519 671022646 158579107 362976136 484662664 941032162 924697511 58801845 582256524 362003381 714239965 494837397 180833383 747681819 498047645 703014886 255462194 1553830 895599157 313502537 911507451 969274419 58186879 874736500 660536748 492826479 485080050 905153599 368649412 737614822 579269869 363333063 263071114 571574926 879989273 833460273 717400539 699868035 870254365 175681833 438137227 234436313 714026329 444648275 740001241 248846424 122296525 19 22156725 551755468 265751663 577632166 500491007 197499709 6918800 419028331 866079339 191025979 691031316 844229770 21007496 391720823 607735323 594296579 281365885 932582364 919630984 29 408891357 744865090 222285619 515803272 300145410 894645114 192328334 257459083 414523816 257459478 833132017 995138259 750041779 340612026 265115445 325292732 955031523 820312273 124241664 597362980 255963109 500476724 601037052 577693389 805740893 483938545 706088405 443741475 455352567 98 532551423 395468684 661230103 56553199 142697294 701683673 971493684 274982147 772680448 353372850 190718909 658824411 468202721 187229322 594091382 745569145 159521896 593471143 294221128 347178821 979711332 3295165 314532520 500291564 498070925 587063193 159654627 662268238 997716661 768344306 817598320 692985081 377730130 887748488 790744728 621939452 697628757 983890918 946551273 931359573 641175574 411695875 571153155 73723446 245886807 237263961 490065700 872212661 91036524 294920881 84808185 988717008 877655818 59449615 394540555 362760643 96225949 15512855 598655638 492218781 625754077 857194925 842971530 745511014 160229550 34778103 710828345 139960414 625292654 952757748 748878964 487065985 983990541 258294525 281953487 48306691 981270277 727606186 419339074 388560204 985029982 56880473 986774113 379584390 952061042 940697400 769306244 582566091 675934107 135898527 236351757 253568703 803014184 337822161 93680148 931800922 487154867 234553717 86 656912747 871323457 68603188 884017782 27601667 735687082 536774457 84092029 722314652 163918685 968949363 78672886 511710756 179965707 546708317 454480044 970055086 822495076 507861493 91876145 876071983 935578805 586427530 660176131 895895854 565777098 981293874 420570808 10524485 316066765 551578115 137503243 498932880 506977715 440484133 125561173 742857290 641489304 500841029 63476158 719561278 111997153 916199580 199180627 770831833 415547453 463638509 893987584 749437883 54302347 834727998 565954181 581053524 732201332 517415812 569680902 584371661 506373037 456315764 556915633 437139961 457476475 583832808 176025724 434799788 262346774 8892652 184937953 355951085 974611087 707260784 16720185 343709253 596789850 257910505 503880007 820754465 741942337 311811130 263411940 237836267 619633843 810211607 914002510 580463400 448807127 65 406345402 968671164 963060290 549650376 905754210 949626384 445858229 171849824 356287650 58977456 504217128 52892157 520965411 60174045 654108931 476154067 274813904 373738387 957657899 551399635 597954544 995462628 852624455 784952711 432174416 818261150 921990616 154957311 96996420 586379442 341918684 300235615 295620751 352072098 984259979 681279331 799517740 359431288 559600090 596700600 597194344 57973807 317444345 899311223 416814220 263556175 6321457 780839949 516513349 945171561 720451058 34551895 525571525 582469212 66375488 1576025 851586527 892081969 285699045 944600460 269201298 131941658 78790020 861130952 155207402 95 513391653 200357573 626828614 179503147 749604161 716451020 448968167 760535430 132933036 202328192 788218071 191535320 541821276 947459039 826419436 342708709 655540979 917604603 625756097 391918300 789631191 254751738 932262260 874784222 611453772 715908800 679604153 500161757 46381039 658971882 455828221 640691338 188933064 738189189 490885978 264960721 261944140 590234076 808838949 910494102 887839761 538345443 575284753 825229482 181361181 575095330 533091194 648713731 321440259 801034344 665011351 233544636 529200678 512470026 361360470 71262771 868630061 813977759 194243245 429361951 784438141 434457595 518976571 247130037 431349403 893857225 575254664 900900415 835783564 756678710 973405427 768128315 79222957 826070042 725098089 410690483 362291669 138292950 405310710 207745032 92417342 340519656 973354996 395169422 272445419 163757021 522972627 908883654 969863194 917583863 923877026 481057918 597477283 539949985 215813284 78 242352325 487507032 532490141 479882217 355292299 580090191 208026292 839303309 194478864 891060819 659784989 163019209 257633806 34227119 594779177 330324662 603227401 467667170 619358946 290116875 202168987 350379004 199425068 928671201 282105172 750075324 463626102 74327042 669120719 108834962 636464376 563778752 757332095 178192200 918309412 600772134 255902568 845575067 164059796 585437686 403226331 737947766 295282944 892312382 818765722 448648835 501981117 444296076 876683063 353280601 7342299 640022376 925914401 107168897 185900374 473303599 280273177 131133940 660483438 183886269 661239253 251895850 575720593 337798024 158460010 584487831 895301505 662381380 709014437 109215989 246888151 446137061 644356115 278742669 346517170 136944484 519511402 520769019 84 827392229 85590664 928904300 265926589 8901793 320926030 631094587 718800867 237383431 431296106 136529802 729912215 146070166 696871022 892562673 580345356 242888741 680706675 60333748 441132592 314549816 788145575 3942383 433196706 988254886 162628388 984774551 512224710 719645839 5537295 173244103 37532415 10533082 604641899 35497872 372640500 754333273 847989281 912731841 445140784 221560148 228838319 638915275 395449073 85778826 220273749 668774682 205762211 133435462 384669541 867319330 958703417 394025112 436562993 834695483 615896204 53561475 822791588 522611479 350767039 870675996 686047163 470990735 885363680 88713326 176141151 898518531 121294474 820022732 963307809 827158356 34917267 102132302 194804768 157362936 840801610 948002105 72024779 995718282 199025187 476977979 688776391 153039050 474014074 31 855712176 552803546 150092290 945324637 675275901 546705256 405028636 654312045 112657360 382156912 36323903 449786677 199197161 307326991 462398744 71214162 496393905 472085045 132653361 209563425 723764308 621330736 396435538 629100411 439306874 820830677 769950765 832745238 198400760 88133676 638566853 61 318876561 101924501 649436185 147275124 939025504 440540042 366491735 264917928 486385820 20448948 67878985 581913228 882744192 511810915 606948287 963871667 316467587 451287087 452515862 795252627 249912722 154376807 959580062 608742245 852376727 936566544 340196596 62930852 891201483 511019539 387300142 710286990 276815872 943330935 730605342 573134117 723917811 779744439 423715279 384587212 164119577 512277909 738539051 290040005 111097744 674947786 168588359 140369521 86029653 274215911 934367079 355172849 519796463 654460647 628837212 350872350 260472696 988184236 322515910 663781957 262246632 80 21179697 694095096 27193864 526553016 869045022 549692985 581867024 737873777 803458355 137881484 173616502 294677985 266861200 621678352 89756228 199565806 629524653 176632818 364802640 643261644 58157832 716607264 640811796 174830846 155901402 297672013 453361379 96189060 944610522 396216598 701118921 884094285 828687002 474938352 592182451 180839035 596357535 718916117 321735956 650867205 727370576 566126643 69776884 279603063 914002273 623001057 139570027 812506852 853986416 815085827 111136168 34271580 827542012 916702144 447067948 147636834 743268981 234975133 262822818 715637705 213387144 548499588 40006460 158819765 791202468 972493797 364176998 108631706 877979979 392466693 378471954 211298536 752511260 444801953 82556021 47449970 15498368 355982407 128840171 881316903 27 90022053 320468882 619853443 582146168 289865880 616303055 78055465 622938645 621079507 959720327 999305004 117174761 516551295 776123122 527989755 308919362 588404949 126098483 419396315 343861508 319865598 324997448 17920473 784881933 286418244 703742450 962441196 31 967948789 969800222 198130025 108811536 131747018 390446251 41631149 610706256 680361015 220623875 326963039 877045812 996112453 165239230 519994232 366485496 777983759 784964281 959217 306352267 733731413 861743880 978616843 333587610 201120076 455116045 643687094 764862983 535346423 583079631 236860077 73 774924446 107924932 570036595 686878175 225382926 690154075 351375044 169033927 844004680 238760402 549212963 838074095 968463396 991797632 974224817 200834953 24670266 93622871 569296266 474626855 378508569 170905231 19522740 692125595 531172221 610928871 291961554 658758423 521383135 391224205 549870925 515753500 237794867 888476093 955144148 291509447 160056310 515296013 763294121 705296756 991419296 978553762 166917054 563274209 646979389 580283512 831891036 954628246 506524383 323484823 71532139 236951563 283164848 634671639 820818149 275935324 827927416 726883501 109680162 85148700 917242562 296286754 32607725 927736712 813964955 736509094 744872142 869422732 380728218 297428961 972998216 248344679 939968982 96 794018761 524713650 586095677 637013059 44059741 37487814 526290356 870022632 429266821 27091561 312907822 390321070 463045636 789043664 360543611 312310917 114582966 848856593 197404839 964088044 645791734 926091495 876580776 945311419 347664958 912597377 669791121 20168390 963115321 277191189 34390208 978086542 696771301 13438717 769756705 515678219 341108368 75454691 762375689 87902247 844202075 121027899 979415976 196887249 963429537 391353174 503350346 992021663 966513369 316682003 891723178 451703544 764905770 881902687 605010577 445147011 406263949 858827316 233265934 974853585 924870886 811210399 339182703 910835153 241312905 284250429 74325279 542488649 181652965 13679728 355917326 104954413 59855505 190192917 845655722 721315568 548304040 195034101 101313088 832515519 535513863 338450007 905991355 17410965 366710720 322966057 348004361 846287877 616632812 708667733 159615325 949550355 144178671 492031361 344025770 453282357 25 424665780 36449901 383727478 676484830 496620642 215555476 957064332 873467035 236993294 87771641 216054978 581173939 172924702 873965961 600875308 176061885 836813341 454013418 249500304 200722433 383343419 9536148 870417691 332240904 142662684 80 217441306 753517801 972454804 833053112 985357839 811234869 375022601 812212601 333970964 435853663 483807700 76144328 354640973 438924401 430948333 269969439 68838173 209110892 650025843 747579427 546793825 675449526 942797262 921661510 786474638 289757874 992006781 739280403 992127484 268696209 645961296 611669453 467773200 141879958 740452381 894861816 313219398 403536337 726391576 907678514 109713177 786472460 316392208 63134137 200067364 101991389 450309648 437223810 257583955 623881458 582180658 419260640 620493154 556661249 681968773 883834939 450785005 273016708 807633727 293236153 76882234 501628997 556477570 449492672 943007346 199217394 410354326 193475873 477511251 335454279 369760798 465804282 471584785 818803173 719179635 556036522 341294980 490230968 979777054 71345969 99 184353182 333086292 237949765 373645504 41009045 145126515 896743756 944444307 410267263 37668095 853008652 470506208 353271189 505216511 621307771 502780827 79228773 541075247 943357292 633729992 405459805 821861717 891353252 999972755 301942682 475810841 993440605 180215838 662320542 155938304 61529299 524722202 790068902 433124590 509741972 914354907 286464173 866809577 535286455 932594524 265897168 282359139 202282329 425042953 481047674 727539170 745181085 73642438 390787753 189290430 547029885 238130174 215601726 800441172 660444945 774855303 867261059 980685556 663694077 109636736 147935193 482239771 164009122 30126861 427535536 812085285 743445178 706051665 103161679 906489386 588964528 334356339 687021163 704065131 30816978 465593102 6008578 369684169 769557648 159080028 317188852 703078352 57249217 262396592 706754939 161531290 683936099 678504692 527691824 581801381 372247311 712836628 675847747 364036291 617661200 348828193 585200570 921139806 936365048 3 565596990 519405836 493777033 33 126066509 182404811 510448809 932922508 94444337 97431712 126095913 148602183 790802775 792298915 662324136 38401475 252632904 321561237 290088455 162668951 865970808 463697284 885251684 472784978 742430182 240425392 677992273 258180929 25339206 967872297 20420190 896964086 237261697 976272058 377992618 951356868 63466699 57 664672747 249733995 498570939 834080446 976315889 68607204 258128844 690169316 805585045 531739297 268037990 488388714 722283650 595906374 161215303 166531736 668182509 918784840 32413083 111975181 142371325 610327437 650972579 416470146 195708413 632646057 376891126 509679644 544253223 553524877 305656035 925497230 179605949 177504413 344351206 392052821 280903372 920136985 733394136 250289694 826478128 719428933 471537980 542258224 629191128 171885874 902217911 236475192 256504867 321513558 829892110 615607889 459433616 285770158 896239058 172827873 126018772 18 665912369 504854358 363636755 825343695 342388105 898206910 222682901 997659858 335600747 512318645 836780638 255328672 687732096 886587432 276231388 411653301 297937671 506447958 91 263163965 170724052 31114762 431032124 85334107 921273119 740310997 329572738 4563506 928589872 999250748 324303251 990736100 444603134 838884940 381397315 428757341 292439288 675998015 181016212 219602574 378697124 61534393 821498989 306547096 76740952 242121351 237258030 933389695 22491082 228905185 609103164 560414106 3373910 532597911 389298988 453889873 455798824 73837107 161502760 290890619 738296445 425146978 226270771 519124166 778669143 539145479 762054784 370722670 198362297 316860937 179803022 533007078 567180627 819998541 714804920 35448260 400692374 277021341 309533235 445375600 539591708 406821015 12065907 373105790 284147905 284850021 620474069 975177206 886120756 178810756 682530755 200992247 348925196 549557679 250712534 436982383 625600345 668832984 148127472 914603646 33153617 991612717 896448409 890821806 435929678 470826601 133167883 450477102 326957699 706799226 75 525966708 943075753 781185945 929731723 846613827 639159658 639378660 897999646 582928111 453625073 112300574 544809052 605374621 596466746 841226277 432217423 803905990 436765073 4976754 829988872 295519924 418955155 765936404 227848341 245145181 449566233 370795745 246633883 373105063 288861153 18843849 892965672 926571594 790704400 640324582 534419013 805341212 771784515 1886571 822103747 718483830 250908761 550583646 12675518 468214438 307500533 793237210 817124898 326093392 140666557 63012819 33034092 805248724 378531451 74484222 792735287 493242821 105997230 371192970 415434792 531409211 631850961 541101367 338642911 77061503 793220297 532726619 125342662 237682550 85131351 111966069 219895686 452153701 349966588 914703777 39 612468988 427274712 419297611 998723864 440706727 373693760 621468760 698026600 869758799 137356934 762999662 446715375 646332037 983583868 121114621 735808597 923198622 553786984 544083615 552357778 993960624 946535175 737644024 691400930 991820520 281060775 287532319 728590227 748910279 132701420 92263952 286406804 772152741 417695820 639819002 923386590 463475266 409839368 480719250 71 205387643 40186998 178704123 852326022 212112708 357374824 549934360 157097902 751772776 251703593 46046523 640087970 854890985 614163014 127745530 344025916 298453308 473169732 464629654 702401005 240671117 818585528 875007855 25595519 671154263 216895521 554460739 836136195 595549491 570933931 997386256 412766734 990149434 295144965 785849734 856687100 696892689 874577104 132456474 722899546 176961230 475237647 50877867 275790094 223148501 387761907 841177136 623057442 717273610 824057014 865204263 970106426 866037159 301249989 186322160 950143981 171902698 23699901 249611518 523946296 710708444 827108032 616266444 880160989 488771369 139019064 408620654 392752989 277106033 652734579 491296688 98 262112645 849629768 241842250 9672979 913604966 81372132 682495009 942037667 889931701 553856514 288955782 968674274 454698793 810342176 907483535 719018253 634539331 186543831 264576185 505496829 901921109 441452086 128243373 103609527 770058110 478459359 976435216 37233552 550598909 912472694 287441634 751091511 125746834 510008324 904247626 980324915 944966993 786613446 133916806 918861795 145596266 789930869 644510145 701685805 799590390 210656881 198355855 480716859 3337437 53918696 458153183 324652056 814580036 485334424 839662070 598879501 703763839 522829425 264195960 388293783 538005075 638159253 685362734 783237502 659925618 75203335 697034547 882228431 529634546 793088080 565734446 142245570 258981392 335090676 691338293 505477489 959980415 784667946 275074285 775878798 3885845 971897491 384704801 970273648 489291725 217840038 593969562 93644512 269536175 85097342 480526009 155690092 151373115 273095321 878032419 301785398 18146083 876371365 38 151024852 679609290 246812505 77570799 148834506 230668509 326104038 967024633 84487817 33842180 783903780 954172041 455443326 337533488 250783691 401376965 201147569 680911316 920416590 618030687 991711630 707499084 753028558 331690118 689919385 16831518 589392123 719944186 100031350 283186918 112382882 198091900 161364425 103482264 477675117 984164350 28530794 328176135 14 167879394 172419869 712391060 470278752 534755542 460584128 475958298 728983597 551296527 880806122 830781113 308297399 348819677 706372867 94 347005540 812945286 868092899 980956580 253757801 308091267 534338422 888494858 541612107 48286295 582740307 463820114 454691035 757535301 380072597 634856882 290465102 600693625 418130053 792178662 482060507 106242150 464664163 960511984 426117558 688433537 284846710 491470655 846737337 460252558 892885123 165014689 575094067 824742609 109310714 678573905 437257946 817946672 744733934 218523440 46689349 304538865 780099584 803302777 8389372 337080909 881434369 49608620 81617432 160574651 876422370 755076114 624640381 694430014 258665796 549230127 859128045 253981013 305500292 745374962 652438064 572273195 807317284 651280084 379132592 235480743 694614490 567602743 690357838 89588304 187014970 798941752 918961251 419490046 54912127 570207553 705658285 300335908 684099719 964568439 977593308 415279868 128880388 8065214 669464577 690782651 607394245 361751502 741308775 686291596 198734803 133922889 504479516 89201895 96 700512729 776069002 542452572 675638870 40820103 487555630 528024379 88313251 4343916 807493954 59695898 230267515 610226684 588505698 744461504 149104252 535500772 285176134 648454319 411502598 253749674 572702255 803170871 180009120 918822043 495517498 473512271 531822594 186671785 777339649 905046121 711597695 722665908 654395829 786945181 908410931 920734056 729361938 801012402 618710074 173087802 769187753 517121 999487356 564681614 463871371 293429363 599089015 914109088 910947226 189300775 327167389 323421952 620086400 517947994 365857403 619031400 625410209 235234245 643811940 440695580 36226309 70760436 424222806 20626947 72446686 856972753 207983921 572395555 4401312 19683927 751987213 9049969 291833791 883150530 724335000 683472699 300322409 275348992 675696454 120284751 9435704 345929081 590283995 765694529 144828894 773329002 15004164 731066827 512483925 565688454 156230958 404317161 421258863 571648293 784810637 25 216746916 890310095 484163884 93624404 843336975 460863484 794953796 469101844 124084739 747165573 105040309 694213070 790451498 748538745 337568345 170387480 626774241 86554793 428229235 700966761 959500787 147038928 261817922 31323056 59342980 86 792288418 925996327 487704511 769009233 111881926 333763705 158374092 584448290 688919180 411526403 786368728 438603813 983183633 250515102 5866594 509742117 681367796 460131933 495942370 620054076 198357618 59042357 258452594 766735487 905921680 510104472 702258830 913047207 984245997 858937434 873416362 260967766 946555871 369558897 410343552 595377261 856175461 352231871 2852008 866235543 622640001 522124457 178924897 728729891 813483900 395414933 142383553 483681356 364359252 5961350 685984336 235845127 811578370 213713405 482129927 521228393 897759227 753772015 806469529 720027787 389654004 680557198 386262948 909942752 66884054 908129247 976524405 566523161 677369290 414410097 838097181 738743517 462516573 669600380 854029854 937645880 850698150 197171380 132768415 607403401 621824468 285206346 33307847 400675635 415705500 979300002 33 361871611 338131507 274389833 14320492 894686629 368729051 219646262 658483322 951346490 528328348 456007901 608615760 141714361 405313564 788326090 486254145 929795491 433955101 652124588 496289910 89942829 837292597 466462891 659607236 417838219 150577931 483882836 918006380 44611942 174009553 716031165 153850702 745227871 59 736987558 34531062 686166718 402317516 106158786 992559971 304839110 418218864 340784222 766095170 137089234 10529895 624658559 936506787 539663766 148188812 664959688 170892168 604604299 657487300 154160915 575545680 3051948 879873769 879732764 132665198 414890966 893538032 236247695 882713611 394950850 383259423 234591908 495930815 317846971 862289943 898423586 224964461 877547888 695201103 990896429 550964598 694266499 135244977 841988753 601756180 331513195 242874465 819365320 387469448 36143033 355078605 691843616 715227545 965283387 958829614 107247124 168930743 470045226 78 32721541 15809682 92907932 440182124 223670820 618306325 421726976 887025374 635248918 917197545 468879778 828661766 383382379 540048084 78211137 936130448 778785516 551358155 420870418 398519076 491032295 945901536 618913265 427813537 464935076 842373011 598545195 535235554 199592663 296284988 602868236 350560793 876622987 390389017 719908824 606055437 331929135 338643103 66931938 596619144 806314958 282696413 435709060 175769771 658423226 245045794 603093398 849056931 329355712 108370218 382443568 984009245 760491508 930376302 618054351 503228512 266430438 980849815 704609376 981628136 613412564 256798240 386653170 358920591 974224941 632941093 276919130 44472207 528358376 478313894 99935022 705752252 210278177 901596563 741665791 586927096 958187620 930389512 4 752473098 73434218 186969039 152802443 33 961772137 502057199 135884504 832451371 689252730 340776675 827630204 399912799 558208962 540594974 848628775 36537126 891868239 293361628 480562435 657950656 893692555 399341190 826335634 415497016 443459016 326939124 930055717 914668420 126877352 442846053 94098201 198743379 257042724 619249740 30237820 865562662 783382398 28 345049032 754998550 656137743 118935211 706449909 476727721 145109226 882474819 462310758 595644786 383493127 220725365 417234463 778966654 88854816 804384353 468163152 417067964 96863054 348019359 518574342 336243374 761296812 378120641 806125360 39444170 478710637 225323070 67 678778011 776565083 652179857 79259699 809501736 324268837 288996917 882234688 258742409 658386850 815311859 560838998 101532714 196479192 677345734 52222174 11655192 840200729 206031143 827673108 841682240 602336647 894912410 379655316 374285385 885665117 434532125 926382110 180679924 938333543 386859823 190870511 986779377 7652001 230808808 53899255 902929567 666750950 795205256 229431406 319549460 943888974 469659055 89375953 899416663 530622206 649441084 852203962 955973113 608001833 348711917 552556261 625601448 292735992 43276520 914939371 826439410 168205265 266375615 167173207 714602242 521527973 793585082 486132687 714524359 322651452 304575001 32 504886315 63951486 615104460 448933686 995026611 298063052 688231934 135219227 995466931 394895959 253089342 615099058 500150197 382434059 616944799 920335412 61557270 566908544 388698549 647367787 475784711 875757749 247991336 632795279 862055960 798285406 610911674 583532572 178016880 134007657 780675476 475348818 62 218514922 408557725 681114041 198576671 417102184 136995674 745381853 375920554 875989681 860260925 284517483 767369085 836419813 889601918 904527908 436274703 612364368 399830233 265387903 188171165 132298232 908349523 208111612 398712476 579557079 571912852 924117791 464686420 858800207 360835829 512266563 686135688 219506015 833670685 672414068 767089241 239573994 165834624 8235997 844083606 276701994 546854834 585370813 199261253 755716109 889454531 23019400 255854532 567900012 510860963 93044563 532741434 950604180 557235359 992245422 166663288 682128704 769371770 747928609 430002356 554784395 21193555 41 665368481 719297236 420203566 372319573 33986115 268991070 502101468 171949291 637279448 758648324 769548591 622637818 459641282 89471104 175296012 418209702 70697905 379704274 226707303 867427065 416044392 788403999 871061965 25791794 848019890 973621260 713073334 979877889 192139488 488118953 590071321 115038312 893244652 325870001 174458599 969029995 979238126 125166436 888153360 879009612 730710976 34 426101879 313139864 270900397 973488870 240080381 877527842 708031380 401651979 783304346 959555113 42962335 416253525 225104257 447150443 14147476 266782336 734832054 971544621 196046189 23924686 423923805 239317559 521781452 872825146 210529189 455494294 709550135 845565892 124065648 122963057 224249945 633756177 237233474 188781516 54 680392269 327809762 625582640 232458930 198644468 531394447 766233626 662618949 663768666 584944580 878756514 83894914 240946549 41368090 39597953 131010801 493099747 839474539 945653463 890206885 191156676 698615946 963142063 442047280 680148677 217884186 557134385 261939628 785887743 656149669 629420000 716440762 809002009 967574121 985668170 740248754 219044156 562964458 592961641 142436245 930813266 199799973 95388955 179270450 390498001 266180470 153704484 844279794 967027057 57743445 783490511 878145289 810323679 332969283 18 924833350 171011609 632420711 281391272 90746135 91220175 768746283 767822303 627458160 276853018 88762506 229708123 231791232 317493629 916076974 805988947 6992707 767438168 46 713499967 687667379 9645199 982218337 379280179 102170194 497268209 512024883 266358646 443471175 429393639 113508414 236528309 938233353 217521017 559603299 795024666 217938855 101244861 110733013 626078467 349512881 78924189 656931605 996001631 342152207 41178607 657639737 110131180 298455845 10108108 55788082 629130624 675691724 616164379 51370287 139056178 366819656 949012903 326562563 64615712 485216135 540416118 533315712 406638505 257610026 29 259866234 859869239 552065835 156568373 944826735 965946684 493995001 744999438 986080018 882466466 920481866 422699697 321540183 719876517 677193636 252465798 872531360 404655736 526220694 388278008 497683729 935322018 204103525 854460277 76365386 494936246 854716026 810754478 234804481 60 754239928 642407871 244689996 552266547 507098666 953375300 647434643 107969712 103342256 118485789 601728033 80644105 910878333 700325047 189662262 1606403 862622474 21335391 576117420 667735464 501676893 849073568 415389617 18707341 956640204 929407020 978665797 544762805 497739156 459993349 550571512 320743706 545769709 513947676 250010858 198000797 90603198 879947066 104196379 714472830 128696303 985795480 520816220 282859505 535600492 5295489 165669678 105156167 852536258 588128695 268139013 114558039 460140355 669765550 939437669 676358691 126081119 613923285 677043117 122697499 86 928811941 598252700 321166126 737384018 410905384 909671460 592198917 667191682 743377446 697349230 165078793 975827272 637994594 606903991 722944506 509494309 591743455 691142498 463532051 714191934 690491875 694482915 179953847 502512217 422686426 340549673 655904392 900128172 705095789 237928985 754964545 481341416 472735883 631932590 859980078 471764181 556813341 23547171 680854081 8963483 706570167 460211029 608528933 794397396 610682225 317046923 621504778 813222038 820118950 628941586 769283357 356122944 965408117 417236657 854445382 775729792 943070377 17584519 995439708 459996815 428456440 29895657 127602521 55285984 241706996 883862607 236163753 94983751 976720620 471602880 580950200 618320347 191350934 398120769 905021789 3289888 755709010 158807103 37012045 690898194 902359823 132765750 185185306 176901438 313973010 139564885 6 119653653 843149491 281692239 918224681 431970574 119061581 67 401803371 842313309 304581190 199531000 53976308 274699913 627104569 528000785 880359572 491420164 811079223 56157253 674340310 346295297 993779445 870811252 190924430 133785702 184566141 854362917 376199201 161126485 488001674 824432195 726258814 222883419 31845707 369426331 675380552 989919712 572350590 278099906 477174812 383803594 576190991 565346943 964536535 655019428 285690134 199946558 276627314 699782764 510061855 127118470 175529542 263604820 739543582 832716875 127940499 509575512 466564342 313188160 253416098 3032081 373624902 51679802 500866282 112100615 855044028 570528145 95416138 37350499 344715241 960051545 373151606 265836991 698967472 18 850074391 759192814 324380596 618134711 650855982 364807297 739865666 640935539 132158779 206950441 742766393 639181123 764236473 905502045 952023031 239422737 409718066 850152745 50 929151409 361623084 166258601 327282570 790932671 882635800 125787164 368401414 644455345 980161029 567770659 486154693 155988307 578589751 396539713 516025194 788119719 211937097 852643385 423622101 333784128 628819087 178397161 429860178 25269290 641964202 346946274 272924168 448538524 23561689 293765741 388995570 589513281 445826191 574606876 571979093 665235816 494369258 580941827 339255573 201519077 160407156 571949155 752724215 562394913 591115350 966955804 818900426 126198439 465219713 81 949351549 481857694 395108252 958963365 219530697 888962024 956915110 424737047 460369117 877417839 805983369 211028237 317478542 938985593 825357915 422624016 734380454 368185473 932613838 373229972 621035332 45351380 930684439 618652510 311275325 338757829 802512317 182218534 356244250 417977116 478219456 136191503 551818714 131762383 133102334 545747250 245626342 764725189 70927472 967461305 255153833 2025823 952573809 940276096 263968905 141224991 867642659 727337569 650016285 993703848 450477335 491613576 777156015 999962975 610228683 66747353 998186353 680355625 702700540 774764444 506911890 3418437 642576142 134964275 698035674 875681298 162323410 213115092 43330056 75230423 750017459 460478210 421835454 935795670 94784830 755135702 141494779 970923789 944631295 151282924 459996875 89 995076144 752463913 886250379 792066463 254887013 686809168 677142922 744216537 449990383 383081289 594298026 523517199 376822248 350764733 907699423 577608015 156872272 722597709 307756861 646284166 453382277 796625861 83110692 23574893 697873222 385097142 908861488 275869457 863022110 651824307 231176786 206684845 936406474 882354405 552463823 196534922 259267066 757041990 601390977 86118835 852065891 207439420 567132854 462997928 198202565 202297503 408444056 769036001 353450497 426684137 409622057 542771347 371526505 989392627 22045572 541416297 593216480 407833830 915543531 30970629 962235045 140650247 93578225 31669544 504665381 478218074 711718099 645211322 698782307 564248637 724312550 442762050 593429624 838064664 718402319 953299802 961001479 141313851 97609745 10566352 463582612 854137748 304004107 949401678 388290943 238042481 997901754 994011030 334169887 90 815473018 758734458 68529743 204258384 717943234 902621691 128455072 959854040 710250163 539865354 439021382 324840428 390187731 734111937 407526155 845687793 722762838 938602773 976748412 882833238 827386109 913228856 647269147 530292695 555235200 724596094 337958439 570944409 541338054 316960823 692080292 754129389 247291641 675539032 471595453 196099687 63351315 672899054 349474693 93700389 888503435 727957260 482685171 972591625 298464131 809301271 540970407 77004326 475948596 252341323 281077494 211496197 647495123 821061276 431555781 239299249 996191786 638991493 913464905 603449805 354258084 776972173 94687606 655664333 689567726 305401548 473288368 84020726 154392958 661136933 235694335 871508410 178462369 876748127 252215980 634710123 42464389 987349606 849605263 191344147 438015184 224782755 274559577 483504800 730032761 405542518 996144430 306525100 305721500 526191263 84 774017523 628164667 575729007 90388673 512062198 922007517 762676350 922648078 855864640 606707621 89728707 443999008 593324917 59098734 298791972 344667654 209471171 156180002 187454959 997412108 55852901 897996815 608977954 611100868 419085660 505496609 946390134 7509908 158092157 841152067 598402042 100230966 358406217 739546322 137676444 49856165 829997734 599297154 437028131 704312379 427667852 167176540 301065580 311862315 354696144 982823212 358671374 206608064 387927591 574619856 412632229 651119324 357514010 822509286 652925873 410627529 784851644 536922040 900574509 470160974 810531924 117301358 374404873 395154475 329719689 86203971 65262587 53783108 603050032 215569032 85817104 817886868 297911626 558094320 559975442 695434268 313804083 929057828 458196720 175450487 864309337 560090646 652655566 935839688 78 365121580 529584190 441651013 798162230 798854436 316341750 283865099 140291238 833030010 776922300 917942940 420074837 264511594 819186602 713090150 81128707 836422516 982584626 267741603 917088418 529702907 205612609 295824971 371812805 577559784 774254023 392176557 984167785 923777790 645791196 113220489 952798313 497994747 137154068 308821068 580355986 879335983 783663819 190363110 717432832 391766187 313084385 556805768 944126711 524688711 183306595 214034987 93572648 253141307 95927807 902811592 948238104 857939601 805081662 489354396 831301915 260075628 730572325 758482237 340512628 915649510 305511198 887389347 780331019 16123479 760473007 573947708 763830637 122238210 436220249 641606214 988983309 606895871 87358867 936461758 560195249 735541224 619982559 57 738176123 329546143 311933361 169658887 802183257 320915427 559043258 671480525 94764002 351718451 502459728 296727438 394248664 167784422 466550188 107784651 955535498 719117325 367180277 550585878 215753324 997294092 557145914 200532938 458360580 366635566 327107355 927754888 496253680 52943508 89930386 456673403 754465401 152489877 369054509 313728553 626411503 629843000 622258131 293053741 639066759 262016823 592857099 787987438 414048174 597386714 782052872 787949567 145866852 127589717 446531998 429062098 103149024 266013978 150665623 810671330 565415678 93 479860893 976089132 612457930 852587666 326629834 70284637 945697174 956829432 975101380 763304775 48581949 598541913 16127854 112501072 377436395 561733799 65582647 936194653 495071354 343604455 428104460 702727635 174913147 230493260 207707850 87990258 737754778 685925674 762596365 981288292 106441064 496962972 613571507 236149954 214508289 506487436 253878142 455656513 876280650 15239124 724645312 697556316 940373828 411477868 217094558 221775525 21679589 349876928 127247270 300988437 985104130 675641535 95440454 457934145 544779176 836502251 343632030 217254442 859190634 380993341 536007958 286061556 925807755 177576521 715397423 721173050 189063514 133937839 263613807 759256327 7237530 626558396 957854021 365884942 148755480 19031648 935987952 821082128 927485935 288215815 67720803 223846376 533237423 35965654 547590116 470425763 857052870 416008232 283642629 395499197 497100797 220615200 744439371 84 460161823 510977300 649388719 839242581 932521007 427914010 156031498 628444514 434982996 612803588 192922744 188449137 402939435 721522349 823680400 991330921 654516156 531848939 82420421 437180459 381399824 144530829 404623934 722359138 612296736 778567282 123228193 474844374 93929960 40329217 606614669 353419280 7629005 19172621 624367413 996005613 957779224 28226689 420183209 102084974 929803970 607788212 404225795 436057729 854926883 362797799 948728187 749853055 110768144 570329051 981005640 958994258 216450682 454379858 726330227 697184422 714606719 950624154 567997380 227538671 789669632 917638758 117887586 253379519 881704112 207585401 794008490 300755415 870073022 965426248 459111108 603184764 743282738 11431169 922923782 287190114 623283677 997409899 925817317 635919590 683392324 887198324 229787155 673393440 92 94779304 511739532 123274907 736179706 138806294 370088336 582529944 900197269 112774326 100345586 374163646 736380735 610045783 749406951 497026039 4272757 758309813 715205690 723661577 985571348 64701485 69929106 62458670 707994939 772284347 595777366 521574158 26903485 272790773 956133917 52980656 723370702 40584851 162379650 354473779 815022460 44847738 371298713 870119393 969787045 445291059 124473330 916363023 921833177 702630304 712260501 119218561 301508903 977662304 106607344 804574262 315098595 854286234 638460821 124425839 459550692 317941351 354213674 853644681 798056279 137504677 30551603 222491683 575510027 719123571 24274863 510365128 563614897 816666809 496387134 40018228 955111541 5495633 234817307 593421060 658835662 779941367 348410176 254016484 146463959 600483476 501824970 124152754 837236162 253872505 807724695 899286584 1400162 551039685 270673413 984939097 812550557 22 578304261 908753959 634788656 637633241 711899891 294237121 178540479 828046077 715244605 467542496 951866298 544419341 208809522 655858589 397205083 859023145 803074830 204229760 261490874 150686663 383564343 460417161 70 747677453 481918630 671999420 58106149 51764867 598345384 209763299 675723796 24341330 520487439 553104430 440904329 484007824 473081355 633246894 244787136 920199503 932929070 82812598 781846506 458764263 917127841 144742618 956505444 663138403 200855455 657274652 359901807 549544811 30984834 900504781 245446631 882947393 547786293 120239739 435343714 736826844 136709937 292505172 747320128 897446596 910358801 586985684 427500992 658059108 973899363 685898384 139704356 548775127 457445928 735331088 426461212 313274708 746658293 801596021 345591488 848466783 74192486 599602892 359174420 437462111 850570700 128721690 664576068 258307025 703721252 178940280 701685847 383339066 52318420 22 946303241 15964221 161751781 463608244 858620004 442119676 432526300 52751693 867299153 179037831 152493100 946069516 314118420 165521774 998186572 654361773 344238828 215577247 65448778 514848518 543428368 196193617 78 233427666 124594944 281540241 6163865 476066946 172864022 258403087 330106287 838828116 878556601 770869981 261402960 577787278 637534785 359253391 620488329 616840524 151462872 813310620 366572439 604726741 835891457 482823851 650831359 789268564 748255957 952870528 58416375 133967570 219948860 64032926 673352430 248688540 60027355 595626236 641099216 933990783 406248440 631274221 395422472 86495923 370339873 85063817 977040519 695188389 210520389 484155637 514977714 969290117 541122252 540396536 122991375 125174726 946031554 169777525 709589778 341115518 105404314 456338837 320925095 872658394 758338270 367445488 84413166 755334689 222731756 441239503 642640717 778155121 449168113 313958817 249839372 499800692 564870176 552929224 848464090 32359007 985949709