10000 10001
523952798 575297153 826990285 142290123 1597082 240471851 141727190 115020627 464949157 802696556 706059813 454557806 731200104 186841624 804368332 133024397 984686000 509275438 505047515 38403894 465500953 782491384 829393953 413225844 288446425 713903034 109220726 231476193 120144660 769176896 434273039 568083239 226914760 806985933 687694039 677467335 821945431 572191771 657468593 509895903 826518954 162959836 611729516 312560906 551207279 998100721 286147731 787693008 594772637 38646287 187098975 606803078 848659275 73931228 783656167 721040849 630478293 286888313 518103221 582666185 243728876 902862437 375970687 538247025 324399012 147803251 509966900 114735063 124314570 547671006 738384785 929515866 574857057 617953912 282020260 622822042 900089569 191634472 188585239 848551118 49844790 938268647 281384420 145907419 840932000 613792859 284891900 23964274 607301256 725146369 141280638 684628036 574684820 856487813 581885458 217280228 696553401 223526735 524977086 623638307 997452841 295718918 611749406 464713944 825085413 972892976 525543744 888500756 366964102 698191799 924362271 497877387 217593938 665907346 534311022 909657441 198357212 270103220 44411558 671061288 408221979 17537403 355661748 234791140 761566685 802558622 704090703 930040424 911378258 131838916 20346853 208156747 528419068 672801099 11430759 863947947 594171223 990379019 555490538 690127310 611402577 754678004 25417793 386502147 5999260 913484892 321956842 969440893 309128346 399105968 962636283 550848745 282945164 996179109 918780898 716067861 101990978 642208052 608015045 511457663 517423167 282945917 166012864 216626587 764316375 333809271 466536293 425145737 891539442 883735273 402460455 362257067 244403003 407073448 52046883 784995154 745383144 968516377 350321588 727348415 878689040 985076841 239920686 903001483 75044644 678022484 598113168 786306727 185818249 82709679 876839268 77441941 334619888 748782556 966268839 255774769 454067041 311765016 702085004 910313773 164025984 504918207 45701140 886157175 299113196 289483518 232188427 433967036 744952410 595821791 903960157 450181927 246559433 369586397 103182146 571755472 914232335 973258727 39156084 196626400 599048889 821880803 457317092 684008891 609662130 672227671 359105776 936176369 250091214 407123705 886007156 488000008 795156437 819978211 37315913 917389164 354409073 725531446 456966511 97400687 466967532 24159115 248023436 117920081 374683243 64637394 859139404 334156925 100228210 60040154 298996899 537198861 590236839 978565191 418619868 841607954 868245464 399671595 947781367 199489932 856225272 830374665 538282851 787915168 23288297 52682755 786235662 729720680 967881465 388020784 381163754 850054959 804120591 408273721 446500840 483493159 3942981 672878090 208129801 824896652 437482754 276165545 133993406 322100719 45156192 431489947 695688209 864153488 927721654 66378671 232659430 827338007 619437891 497428826 796905885 522097988 838640350 97169800 15748298 327061922 908391778 4863530 734620647 696456503 555471131 169491999 93500334 16902003 107673331 401090520 199331453 326170865 868285575 374407911 435140341 361005180 501194895 173151498 57073691 478015435 824682311 462615158 173827166 813531718 84417210 787717675 229906547 425007249 17213587 989909760 608898673 628141583 585186613 842683049 185397624 733894872 495278442 455794684 645359384 708495205 545080658 123529080 128828796 29633223 652346116 991963061 383264181 348647475 195836999 19887772 350502501 451219119 751799196 935977525 443244875 74391485 965625267 638999715 163920871 312309630 544797301 816270831 995807286 810160813 20915043 995533440 558695606 289214064 373661341 387819445 236549291 340081645 21898160 213867680 140198390 230415737 138828076 356923567 690670698 611541120 54573277 696733919 466748238 557902219 347131541 501458070 767047050 499112184 87457898 287717889 664204899 476041242 972441011 672891506 833360296 908020125 344583770 745174091 609188969 171187417 192994659 670758271 10198562 40725750 271414461 547083319 546921147 642336480 859313768 381565623 951882679 687381634 663777648 193336383 755894185 24594902 150589536 601330531 925400493 746714235 640292167 922857032 864150870 308592222 731840571 637534482 430094957 120024962 248065997 517298201 940926259 828946657 969551388 49627807 754644718 80963125 407922610 275714554 483362497 352223285 977518586 142928390 448700563 798985641 762644951 23174942 821327301 791174199 229357882 299345384 929989163 82971761 226298231 280108519 469587882 855075501 625138761 123315937 102286495 370114249 436740956 429812187 796018955 418721792 23258110 963150765 156671246 96020236 826397631 521298886 877141441 751156131 722417191 245962854 693115342 735569131 944032393 825214362 172643813 339736666 310080085 781646944 884461156 516751342 310516131 141124954 358648078 692975819 60813119 890318995 362780882 964415444 845575072 260502208 41782593 919216142 271157591 128400753 848189024 503916093 855352218 302447044 414471285 592630068 226055146 547956524 918243700 44560785 907823598 724763095 673130810 302274075 747068428 809605881 649872828 973566286 242482962 109978306 345996031 899261850 754071824 919631984 984137318 923708357 636241962 116082472 858462754 785020745 531215950 862527421 786389716 838209799 564845783 624071282 372709000 143851550 463273331 13740628 12961119 563933377 92099873 771875603 553839914 103726677 493568772 106864280 957202721 376195491 291627274 113106392 552080424 880782908 543138761 917451731 586897252 692768437 787178326 986619794 680788155 822510122 604532020 463420123 254822374 815079438 38689283 46166008 94821150 311961720 206783135 886439078 601872965 724856432 169155247 64740405 23726065 411724487 509058403 137922159 573208448 771288402 576180122 172029058 180466593 156799631 953868522 966647438 102726857 549446443 80737271 312315645 818638264 270286578 589090870 38047004 281252020 890962772 565742520 743795234 55649196 188249414 645641196 931646519 877257388 814290296 539431875 24140394 788648615 574233221 145712575 337101705 41759207 36221048 532315956 723158180 942851976 243119938 641766274 436136699 301460628 139307720 125446402 601532636 243249578 297958145 261705171 536339357 965651005 771957107 285479797 222172816 682694089 762748204 153764967 465062096 532211106 478263395 56237735 112245080 220747808 497392354 603640208 138456418 211130716 540208073 67204888 303264555 90760431 870765134 943529426 897254029 314629098 629715908 570041642 14854763 201181388 686000499 492210281 996260182 362035802 735524666 506856202 125494673 793855666 72046201 939157834 479062672 184662130 990232064 40667466 819040632 923039289 830715891 560113429 188129375 799173960 289273187 590274561 115234766 682302608 378853222 29411204 445351440 223655534 424027307 725249948 98832653 313329279 73398155 773175792 2662967 942828195 754499842 876388442 453019667 403877070 205705620 24069802 988321749 374723199 820645013 102194370 124568944 890294354 209924157 645702677 626243779 290208831 359371656 908790923 894350763 669341636 566618962 382389969 816189101 924358597 105685826 125377550 641911210 732123404 588662591 665082589 159853942 397733853 172381215 809052626 521657571 845577206 9409709 701123399 741694661 556941316 877939965 705313763 490471560 702464283 791048576 491639582 110528382 588865329 23725019 936813597 632863620 559840728 697071930 850454921 415876827 717305865 339621922 227992900 550386565 170231092 246803897 514315477 469376602 65267641 257050491 736242062 787042340 853280763 499727861 73998081 878159519 202693439 150537183 34413251 22885931 433378566 414504727 562364021 323490460 94982259 74373423 104488550 498036007 66310373 838263765 466450764 345971125 980090926 188904565 421592862 969343501 936687219 737104985 702167124 545996054 224960546 457994029 128224653 234347533 995773799 74533223 395026721 517662276 573078828 86036438 81937780 189570620 256785152 990735110 546279807 835762038 391686601 828150469 34163805 497098093 265808819 255881230 152205278 23837605 806401493 720058230 997267863 210706217 759335896 905751859 750525516 74950402 358562303 747384302 826879886 681926708 610928493 691411801 628604674 168805329 778513853 673594119 550192787 486352303 261396649 616793324 15516332 91499699 202506634 377938194 635840961 137795019 103287896 289221114 235150929 625856259 901823924 474527758 381222942 437995985 190202497 53674388 581728907 707219917 558654563 576905833 260024383 86601689 615706347 970068876 14528026 112493528 224116684 597869169 11438558 544058926 189847506 446151815 544214116 643519879 521449831 715298758 856029045 902962635 842355110 252801384 274021365 895806727 332522516 926113058 783971132 793188462 768394364 987526823 453402336 249165979 428331984 102946457 673412033 810386794 290229146 331224571 723400759 422665861 74088234 602864474 920724987 583706749 51962919 540368203 461626493 55269719 985621470 278524404 214717575 477684677 815698463 430214396 716901237 166562392 16867936 62384713 631133725 703240582 432207548 847112762 403386125 781538040 826585305 1394382 315630481 9661592 614149633 465476488 751411807 523701925 227675348 682546778 285165919 844189287 961667179 481496244 272981046 276283695 108413467 272266554 932702013 509785194 102380355 426912027 797916654 231153249 184668977 334087057 30078704 628959601 616496029 828122446 312276679 301999424 214769563 745747130 880286479 164993872 513771300 941114117 302943 219024076 838087263 405494972 630469643 363255231 466494334 804574205 161108177 429718406 82408175 867710399 402842894 365076816 342923103 109212445 317545227 494035490 350511373 218849273 423894074 377873703 108825799 283999504 259755809 23858110 87500573 84497214 243318570 875398612 237219149 450525491 825292010 874824028 773957930 696815840 204343098 414153239 950713282 540483123 291308584 946392828 170330477 73171726 118473726 485622532 226404872 830469498 41149771 689742142 541514138 756183454 110025706 582495718 643345928 785842261 923814483 180412553 432229755 145504654 114308475 462083332 184882289 581759210 671432716 345127420 347066806 666560876 564099679 281786351 284705533 171589292 294148973 195184212 539174000 684151857 342514544 823064243 895593818 79586521 516896874 521392826 775945777 914149974 774868701 56152294 594356250 52252045 242473321 849495574 213463871 33911666 947939207 296545298 719458218 454898302 793395379 508463965 868094679 506188555 534326865 330192151 709481963 183111088 308568308 384573294 29697082 208351570 469285910 174001102 983723896 755506825 898129538 850197339 69799614 891718193 121938103 962049986 260150151 547333565 987006551 287602980 75924191 297365093 777842436 906553028 962575774 729388004 241591876 810749702 275241366 545452416 50587868 316301432 217221336 598686483 977868099 487485841 507010873 975479042 100657456 249883036 73993066 179822109 533455596 295123447 101335496 76454811 483011964 104061590 650051201 815169617 550398268 807249153 111327123 350780523 897023847 906547142 90910228 906754640 427462165 68332484 322762330 115949623 753823301 828203537 308586981 931467631 454655979 930662753 967904428 504883459 158009970 46576410 773279782 546351170 727830361 602225673 423369322 95125372 906459703 452273595 506890469 802899502 740089480 31099918 615581046 725712565 135926374 650341668 657839783 574799691 812873843 18567486 514930787 656924018 684600028 898701615 815483744 344540016 820298053 824031051 642681602 593389445 440135087 711609194 919019975 546114740 794422834 746514870 37420481 961040205 930016857 669835491 244173928 314300589 807787028 607688170 199436381 658909068 767735672 752370228 489024977 31928864 578901636 730648830 943837846 828010507 91456671 346119413 775504210 847312792 301885431 606668865 722915084 348171118 37105645 730773741 920115978 648307088 909373021 342510860 198455290 111997461 632334236 927794398 705003586 503083770 964131159 435603346 516503177 664195405 185761184 388969074 368984635 977006536 17207401 64478105 139920343 208608498 617177716 769886305 246075632 644697636 232508030 123779677 202762685 687396991 837369886 536672032 846082542 71129407 115602606 913558166 118368662 15340121 715301223 157395705 396581557 949205018 400312134 822726834 49131629 371163395 390966927 603775908 486673920 301605164 189889744 634628809 227605523 697005352 255891778 581667476 45528591 524936862 129464032 218549850 354820344 797854766 520409171 221075144 470337331 32505448 141885667 236496766 47417276 25232095 718873096 147735284 118399371 715144925 900209233 964449166 788443681 929834719 840463536 582432770 295901211 193894253 224267845 646889753 32089689 56500723 699846188 174283093 847724211 347911329 568344837 926797555 19964111 922392566 862450998 597284623 274793945 62437550 238933270 117535013 889348205 22957518 821556415 856898931 992433775 794950658 735082761 976291709 605733164 327971950 192915842 36911813 883665722 145076836 488256723 940930614 411999552 36333928 921415173 558998481 50529714 186486126 245092518 764141881 813928721 778353178 332006607 320206 987092808 12935169 428764971 381419629 917420196 867042549 233750401 278766348 78440606 771950687 51654959 871107347 637107677 747248072 871266781 17172844 586526179 371101324 384173107 479675450 705742020 768073482 807895870 828435824 327276438 883007627 16095976 772184027 670595060 76454727 1982316 100925597 528293908 665654231 230016182 583004313 752487334 92772387 776060460 222695937 915928421 431722870 507001446 505338791 815983788 534690346 390485545 413337087 236259646 721037281 115912750 937017786 218124094 383495049 208992171 465049640 873924762 417111792 993391359 755045077 153522859 581973736 76251244 205059477 133781861 790084915 47982478 407064238 811808083 592209126 859253484 392596595 470690796 688876186 941757763 82198564 58763967 334861748 873932334 80656048 922429329 880276541 107677724 932820777 414404440 877378690 60207641 289574669 59218009 42240744 656277071 670913892 281720605 619292669 991467606 421801649 285415316 416560100 902773568 307817809 594294351 688799526 689188671 399798270 8015528 562997777 543092481 553423160 74831716 43587810 214335516 955111995 287260212 364733622 529157114 384599793 899289133 66443443 186454048 847538121 33962266 503539093 500627882 570615474 346886159 577450545 69965055 268911233 34173445 31112844 663985158 11295307 854924584 955394102 633826192 435821904 492828421 23087454 915557726 197615824 860157876 8535329 335372399 572642291 262341090 71296352 393279559 311018373 647355960 93985574 419979535 533575023 912412728 67162217 273712277 511917841 815803685 599905325 287472142 272042843 538311739 948072910 177789253 818412303 57692466 972896977 151790559 627500647 17788772 413519916 246271841 683408275 995382412 628764356 3776688 228803161 626076084 345231764 456951101 961584828 135208733 733524889 625645511 784079545 912877460 385487940 496745110 19169292 139314620 732312909 294656030 879778056 105839428 797374659 453802505 368029499 358914418 786246780 797134486 809121853 53403446 371391606 7959335 774990940 434394158 91006296 780411216 259235082 487643654 374712608 618033576 144937158 25187509 886345841 331303680 76472545 665637026 593158876 365857745 198605642 35523824 317715783 976776138 273296844 890589407 365941004 467828734 216609105 165361747 974449290 450608296 785586085 231003940 714751485 101491238 538171371 726452216 700152572 997650989 984393918 522914747 182975899 37959314 629686344 11167373 189721145 486768800 766255933 966937050 432546630 164129032 643171140 815143246 317337358 65854537 221230324 845860735 606143487 208201393 770202426 525592012 203636910 639554547 271161126 85253429 553381942 667556237 607074390 728181561 776198546 658055367 872714724 20872764 154962146 211190736 275043769 841216267 102110050 574073791 931046070 718545508 576764456 705330570 494873183 617915300 902613440 57204748 880385361 467217659 532725827 220336585 943100467 62289955 441285940 513824134 87786760 23311342 240235486 381538751 770468179 245185899 847113767 887586584 20981207 86441157 40420493 729593532 144415487 488078962 425846526 597953356 886438193 646116133 685394333 889236234 516513362 455911949 581562821 251145064 180968368 813103353 189409845 743589556 292613711 181604298 428847337 638255425 714405542 289056721 648445683 647708214 866405518 796502021 651452793 977244769 492348229 556754865 789216790 299988011 369734860 415983012 200082000 22590126 35382940 163684453 621022375 104875329 97499908 172097500 105905029 883689022 81602368 205353913 444814351 970543703 748213577 203051201 439619810 855488685 267362782 545496020 766116725 248573956 283752502 986544197 163320501 673038419 774197859 839170164 138092050 584130905 275961233 412885506 410054139 355110609 185699893 803558936 428043914 519127750 259725738 385526516 955649877 967697533 606635042 266683018 141814035 270003520 273304842 161736534 664489886 710381659 525909801 413636430 839682134 559855435 731069534 30604190 671464639 909771197 165275589 5924064 331030751 991526327 657455326 569114251 598198322 56425627 603547851 975524153 705708052 919577220 277709690 45689857 193381921 512067549 816480370 355635280 521176044 966881194 81945881 351892433 103884634 55731597 301529491 492054841 794017547 885311603 208313275 39893133 479356242 166343643 699284003 601174419 820182305 793612137 219016145 468670551 266634216 777129120 287819088 270989667 647087879 262785315 109769236 823353674 249282169 485890784 585196069 420816062 209844626 703212276 297109624 267347474 335679767 435921304 975439238 591934547 181677281 802246297 7435863 406005890 804958832 380448099 903832086 898501118 249035059 4152731 210887220 134646792 877165670 786189505 483336909 675479170 768274439 394673719 333752209 351648500 400543087 921386972 72616810 70800307 65428380 18232895 559145811 246506335 359886242 636638363 869801555 589482704 835612684 500263717 38863489 332950195 199857457 42321202 480495646 560458928 493372582 652831148 836689167 583304827 32037869 385286485 344155591 938591093 659601727 171570237 562337105 855170922 700066115 813273971 759339475 469558030 810534074 760450549 270434126 576077669 195991200 124146910 81216978 995605162 3146542 775368452 41778139 914980280 807269410 710159361 249175639 728403327 34758860 201512017 56340311 475180192 872564406 877003336 864468610 682482964 440631367 316052228 762804937 576918105 423314747 306211413 151323109 125135292 586389431 22884952 559409437 65430680 942383958 269862174 908667515 412856188 371734719 317810064 298133755 874583953 149437836 946134595 635668743 639677851 182917464 213595884 954984455 756484598 630395507 579143289 464751598 509478417 57719872 441741225 82722179 504398801 326793489 242235330 361993183 176660931 622338486 466541131 533337624 877890008 848720965 204521512 483332585 559579103 694198345 446851011 557468937 926762683 879085846 73699616 308325287 779726436 488559447 115750830 481633328 596562285 636606580 15783230 962494501 944147413 184730425 733110181 660888436 393683797 652006044 368865668 648203314 628275191 809250159 742553681 482617274 489342678 477314950 895650121 640261759 146984941 898801693 643277542 246242497 180882276 293130186 802109194 910667204 690880151 616782319 844955363 173798038 200548259 907968185 55077715 966649560 454324649 967504355 662093659 474463401 838627035 541142293 223550803 475981067 629243784 475300818 981536524 716283100 110559000 177720198 645980269 684548930 580519664 362850390 595291765 600693516 276473439 129909964 246696738 207171554 499357563 537435118 753480854 3902550 292115821 52558619 69591494 482294652 408877148 235192114 67721527 310252482 257982858 747104570 659391304 512351744 501541056 237015154 686074717 238799983 45522933 261191642 495662761 355098234 116292098 613000540 390823585 109157619 498220866 618144601 90788408 607393931 800624699 593365900 634502171 178102631 618370249 799474011 3900372 243520540 92033661 225687334 473209336 105491297 408623161 406262319 551906921 185795187 984617244 213597349 474167919 482277063 228069701 10650578 861011838 623985877 742486393 842999369 214955132 323205592 149009057 90940475 112163513 820850051 855666717 216509927 491119794 264449346 857201990 638152505 455817772 925480218 434275583 243795248 900161814 255816253 520647740 199104768 840140539 867600280 50887080 222904670 581294839 123779147 843618134 858475081 915901342 513184387 830296131 783631840 154580411 968842181 534536443 707284497 179835309 521327723 201718869 726459112 622726578 725301105 950982646 283610470 553151388 263785172 629758101 776346118 411174237 714645591 640740639 80919862 28152001 643925211 174095101 728740282 543244201 479091395 517798545 140725559 123869508 940520929 735681199 285809839 851954478 370332346 633168198 683314144 710782635 228304187 375784954 618350464 334840872 141965615 733602188 465790951 40000644 18762381 205956668 722161860 712228691 941031972 32063388 286424327 132266802 12551870 103598509 275551200 848559874 650845308 674343784 611221240 574996368 134385206 117958277 514617566 77502860 507462914 4488809 572179724 193007129 264851326 1967237 379840493 139557447 50962324 375232881 776626444 214523267 671896785 685802776 954525704 490931285 817908466 976887542 287325136 89676206 69763060 654142253 569291016 45660202 62555701 616425637 551370034 772513280 887374165 36813592 281445384 521873018 11368689 242721221 343301227 43361957 269507200 21990800 375974749 295515197 816494026 6004511 887181440 969224241 342081312 804246111 75416458 455715473 141899085 11329301 896896615 139793395 694154976 998072637 636622550 681958603 15786699 976512815 640424336 809990286 296649818 361386835 738188006 260476722 28545685 31419156 353586312 427424711 885993267 88415032 681305600 692916813 394113738 946782679 530955206 599685517 595073088 239039716 294063505 394115048 76130763 864503564 130494080 668309333 839732245 904311770 195242067 34039931 972302388 826480268 643987155 499760650 183689438 203302557 685228828 591504733 661843771 110311098 111435279 358965833 271578303 960242409 491487 276626442 409941182 399051893 13249589 845759310 145902644 532385138 31903927 258969018 36794585 827978518 582266916 765608470 502307722 84582282 121040348 699249835 321950529 906524047 262679691 260686039 438621751 642565462 796326922 48119007 117692099 96888190 476413709 436773054 2262446 492160649 897789732 937635119 992597620 961971892 564940910 243125378 680030079 710103098 190323057 424207492 818767916 198294174 79453918 245570874 687393512 145478416 534746519 354319337 854835174 263054731 104549205 697247171 359615833 727122196 735776719 79059030 643995780 376768290 303392730 478490682 250376896 140154497 980064493 893170493 771923043 104106443 331418973 129115017 895843546 932974552 337774875 11168531 518042180 169917751 500402495 583293464 841354143 192514123 15230065 468949131 384186834 330483921 987511821 540829597 54349389 10157225 534420237 391815280 509436118 85078540 108734044 992803833 987461976 896932927 557826343 875596449 228904483 681250364 777468625 155173940 565342879 257044691 117172021 102838005 777866267 899004359 444826789 299620563 452452739 479582499 353624188 684142255 578551570 121734027 480080809 135993463 872643400 899086159 18356070 887588883 457092362 93473000 678545633 133462370 568461278 865847844 510409702 172125626 752897432 274586565 106739847 126841653 822880656 77588346 901475469 187780860 161361435 132453986 71172120 303217515 220021369 100213033 61235843 843742634 461004543 193486196 37728666 201321070 123849605 449555502 700786647 351837241 158401732 894459136 137338114 743849925 590401404 991047151 610263964 122333938 591967685 19350527 823326413 960705973 961559988 651146869 299907030 237974233 293057710 324884768 941361091 983212017 802933671 19235342 735884605 366091465 149878989 676264587 259994633 930771732 452279631 88661291 551041418 544800955 92074747 528999949 617900528 313394695 426864045 6270461 584862426 832013733 889118406 186855480 190421368 506514543 165351583 507877254 336897407 445992568 200853117 196557612 543711710 753046171 791973487 40981228 89901442 209957978 114351733 745667033 216739037 466532437 734400801 135464134 874734070 268909755 239323411 213459414 762716234 545505056 90074479 204105944 160888853 774354886 391600732 62164217 519717537 425194424 734356582 774053769 491832223 625714677 587872840 361542487 194112568 202783569 547279322 203075290 849326014 759801393 973167220 954777153 796692593 897643873 520306264 324215845 236896632 668831481 85586911 84770046 427418281 993700914 400231165 774407526 54240432 173739185 97809875 488150330 470185168 575087345 235139170 154652830 929158505 397923722 801677821 785698237 79554170 377755838 172018253 704847717 998865957 102052326 798572452 538641073 985922114 405334010 559903829 149111248 55078908 521896627 783775553 511702604 916021939 252720632 216685833 227692376 22767579 44818343 234462913 371966090 742925532 558270980 865533520 741296418 903700036 488380133 19083227 979785328 142612156 881455372 458154256 675714547 265636685 322912858 86718507 426362048 185709135 726529750 206643903 134275872 120918236 498776952 525658247 510873759 431774632 149527195 188385487 846520788 985210767 246539905 561298841 257978457 263118266 719991506 753060227 305691085 783959147 767511277 870196075 866024842 253409415 800760756 738403598 570427307 508158123 148398131 323365731 234044475 682995236 517692632 72160753 392876963 893032661 117173463 65113049 419848038 927105996 572661480 834364980 477441542 86851190 146633474 431735459 449253606 134609090 525645347 77409008 448948978 552662417 218302758 669653819 529657200 334635570 881505008 778381341 596886766 283048510 853871769 382865086 641533221 458357474 766184719 941768668 582723330 334149477 93310906 414490919 952075707 28753976 218927959 484762565 456579115 622128922 99157037 624538637 107696923 953626825 695837241 233591532 892905894 656694058 65826765 486865814 229573635 784900287 728774818 994543595 283428303 845284835 397431454 248390248 514865797 744834585 401712293 270931092 130111850 918459747 121372478 174262706 793876423 584016765 463300521 266819959 940687520 982220831 9604029 857289037 625367147 747687286 400492837 94725952 933179080 211622757 232834472 455431546 459197043 755385586 793445534 891818165 377768990 256741830 150419459 621067967 812586923 725241564 278968328 814231658 780486589 448879673 297794180 742626129 49386104 339124492 833849270 522968184 488046326 110181473 440875631 548771557 757358874 548467881 435736931 23001948 590428230 601599322 446946614 85202488 163523471 242838423 556564319 176871197 427634551 42360455 822639545 881500755 747564079 579341276 350027489 806258926 845779030 308249520 69979500 829969875 731982108 656424412 621514452 386970172 488539359 605639005 219686206 974620570 974004528 195822825 53653810 72229967 99139351 794278472 660896188 325551977 149753581 695788818 226488692 204375629 804601803 28842331 114281707 355902343 275145817 215395477 615715382 891171451 354951382 696798503 869648722 27462583 402561276 120375050 530369457 225436742 370243356 525006343 616748106 55328120 184416051 898174305 365718596 661201168 179969458 578478479 615821697 143429972 549832610 482783066 378589191 655625459 493059771 287388311 21869898 540967281 521316965 15070894 8069324 979535560 850969663 797414962 201729384 940611865 255106690 665813281 228841870 856057212 980177486 149023216 179304603 390765278 909166379 37567 953666692 408683825 971972528 672634900 231590352 827978190 354656400 962681685 654684863 884495249 750407573 42607668 30297398 925023380 599675463 635811788 759405118 969360370 191433021 840391246 197266543 576445618 78338732 815033151 315468495 372503755 197801378 377724940 979393940 259867228 181195938 85929483 825683869 959057738 346357979 332756768 186706501 25707507 149390915 83342603 581142393 131703131 801803237 534103601 844736117 962938529 582047635 915542659 943130757 325052380 228242349 365656798 997016737 820303615 925951160 197250680 475792308 33279632 16209735 350113344 931854500 21079489 765575239 86347810 292455133 581119487 427562044 470804095 712887585 342734091 268075172 885155973 840917280 67748745 363680279 117384767 30546136 965596439 72481823 457646250 633423632 300541909 161289273 416810945 499260077 294762888 424626743 259929637 335118839 109676988 63633349 50141371 586144722 247511217 137622786 196853849 950635570 1670292 846013544 22257257 563001375 325593346 819721609 35064889 623383630 360622366 300766841 831338960 245407110 196514102 81711417 286613272 306911665 416189995 77757140 204725302 152583743 782316284 656960146 527056002 492401609 162517421 320459877 850432075 32944342 551302034 842355314 281882483 448598229 997655192 801974076 449116563 366576552 377306367 636553981 865600041 521417153 57765533 80867075 286406870 565590646 274505038 320287577 3729467 438105079 922882102 292675685 408500439 171071028 480171135 435956110 143397819 56345316 418158137 682640195 394758126 940265977 209218422 61191209 200245953 128596579 851918686 701395553 967404751 716071551 910149465 136606872 157625907 585624105 243568516 903490219 810752814 80109768 307585311 580515028 639412061 492753350 320020696 707954096 383116705 160846680 338425872 28885253 772546916 779107925 484935347 993297266 243302620 607936918 765781085 438223328 88237029 701494621 283567144 997870009 75941268 567983806 244343942 694391235 725366055 101388310 232742487 20272386 381430528 456463913 860961550 222353655 608252582 478571723 449622370 199827777 882818344 876768804 771019391 840568382 837758552 869727378 816068950 516440207 508410303 304158788 295822949 861081947 575528861 300465748 73517398 571608336 432637284 849618844 972619171 149574177 493282496 367378579 860949937 142305244 122510318 332472675 295252695 832132481 869434390 388804641 556184487 528761121 175376839 835424845 643879083 174935108 680446823 275267746 776960695 727714598 465358572 322865629 371365371 470022363 700980016 343355280 286837889 744135325 929089411 826716356 476756247 911582657 604988974 196540548 391200897 803008244 572493406 68471464 355694678 599003538 240415217 63806724 886259250 722707582 113591384 710463222 121086421 569631917 172042833 993186891 317718162 642777089 718196928 812711459 722653522 533251903 916890364 148849674 962952015 553204825 168328755 257584605 240356553 248026642 175839401 776474284 70964199 90574530 247504892 850058418 551669685 539333724 153671078 451077118 214241524 922806383 172989424 384958232 548321302 636462384 590738020 739878811 155513268 58417759 289285635 466734576 428910285 562680443 343926053 878713013 682729221 205151727 537076790 570472018 495254723 436703697 660225737 260363749 581138949 168479428 871846787 583574111 185249176 559124677 831366802 656697603 394876463 249877072 3157112 575529165 352425685 961692375 907792350 135761358 379671510 80242036 677701961 61879793 19115815 922364278 915625992 82935213 29565830 326203440 5821503 591468022 474608126 749395632 190414881 911084451 707501766 47357504 735899398 881146364 64158417 619436353 75383717 457813311 925530954 419280420 71256419 167286138 331768965 328917360 695575697 484151950 849023109 362711219 857674424 836002781 230284407 926966385 223565349 518170485 473607839 664247236 323184381 955503637 45630966 455729227 553405503 24854916 248415649 288878198 736969464 649239622 364442001 333823265 179200054 312262445 305690764 759889796 372770139 481407213 399486635 518389204 212119863 550763758 590726366 507638041 103967915 196268832 530266143 279250935 578965283 26485880 719696526 618695190 996656154 845130947 193634753 488140446 785968269 357962550 701832823 93727515 152271085 227420279 22449114 450217019 105000034 868415205 908390984 310125091 958158026 951639218 688812896 296284666 460881898 541656471 438868727 506620909 74026635 656048772 93528033 283181359 393152288 506390518 443273266 150490716 889402202 936865836 733713274 742482213 233158482 60169842 969284323 179081232 234331716 824150659 894166760 988981515 198953125 992682486 10871808 10155840 607146573 289961588 180815276 658183700 929478554 263807503 941440479 171703077 645488592 339511233 135960458 543014474 612156073 14165899 581626612 683755032 147539529 314519123 697885861 548041901 183567757 953571839 355549237 876795016 867564574 7245202 456088504 65111984 457799527 603817951 442043281 145102229 878309483 93475450 915739425 321353627 532937945 883569837 148964076 247730617 968004858 22789422 256704680 712378464 146301653 174218676 383555426 781365584 230245563 843839669 870360776 65993296 683225939 724787846 932715209 536268704 495256764 179794427 665200680 435752046 892029325 733979122 434344946 961174872 94383016 459504314 134895353 949400993 607179261 957815584 447695287 609730289 149284085 792811942 879002981 24945641 724985801 934604201 201582198 281015810 861584461 779086889 38457304 237196004 21270543 773079247 957491703 687541247 884318596 559453452 947280032 837950540 509398169 626635058 704101595 653005384 841878459 570284527 274027049 578334768 40966962 605631777 838054893 269888618 938039936 289016740 982040446 518802570 86246920 482599930 654719367 869274187 529140202 489772216 104454673 118013114 585907914 973721700 704170873 221172891 69866996 661679576 109169931 214804136 355838304 552584480 356029266 684644630 730345745 629657815 87413357 487803925 483862535 326296604 984034911 487291246 817712614 282349211 115434975 484105172 43418024 48636209 360474369 496246131 529549516 929709719 823966632 201071064 170257947 285047607 497851365 904134962 148801181 627730023 656785309 820942189 658939501 84726742 559429108 964357391 999205260 261444905 566935700 281071065 91994024 219031829 42511104 74131719 611322077 747735494 277087770 603326645 918243632 836952258 277790902 15816066 590532714 893692848 198778926 280083812 463436514 750819341 242383346 141322781 637214702 360766814 461840855 209948748 122137048 341196399 241678173 42824287 51844462 145948592 920851164 714808993 770988496 656823838 815576157 15167643 82432500 503982252 453234015 222924248 449900685 91375797 436361010 125615374 232015546 329833901 441557780 980794841 768055748 323319522 672212004 83544860 842807406 432485638 681625309 557450813 523638067 675627562 104300043 456808834 953253853 134067729 415723676 417116047 808069243 659120999 499376347 520412623 100753837 640431901 714679920 277268053 347731321 792803957 329252480 519588524 604894709 565583183 844268417 594544738 980475515 246668352 79330078 543097080 696950278 639991054 450405597 341991445 51436404 111766028 682389952 24996733 529466713 920825205 472642811 336552791 175522933 779259031 5143510 48964570 308820785 266250752 215516127 364686888 247722888 373831179 447085325 111036473 347943015 197686785 165024668 644114489 638927535 107709618 248700290 500351519 687295009 708972316 309242733 583481899 866204951 383647692 151011537 219577563 304002339 260085712 16342309 293907840 426740697 189197582 288216416 71966440 264898401 295110147 921050341 82350941 633035396 295062175 528052784 374764107 268141455 148900493 245182124 431051814 242256332 574283871 926169596 883565756 391296551 442281847 999217154 660312733 940702741 452169246 222764005 501752701 644660901 408194972 254821608 471481320 833660594 344724418 900222384 740566529 782071994 357963277 879339704 973321670 5292392 531534776 357565948 572613710 717124651 187957579 244267288 543554218 832460882 811279709 14509441 876855209 700518946 885992840 170587995 349504050 772985725 926525554 885706276 330888487 939864862 389877885 574531502 576532098 676963710 475402987 77624859 876818621 171398338 220881815 984616745 269823607 66253360 411701820 755106754 361820316 837152745 682957896 47187101 843797446 308674041 225397304 293386135 249973700 802185810 923593957 636295287 748057321 698929289 990264754 963222583 712547196 243752296 4680418 220037888 859271746 837222951 882234789 433475841 914517836 641512510 914154918 579621662 162427102 720453935 553877694 608605721 903210294 185574239 791535389 61332073 313201981 354606626 959096786 388635610 559609712 849785545 274025784 394764023 578790331 189108068 259565727 859521706 900703422 949695401 675158861 194130294 811079524 287023257 779470464 264873567 755662814 115759965 730983119 945991808 118280458 61836161 73292193 153010279 951968721 693521660 720186841 101724932 980856091 351355388 540177448 624117561 904533618 423172911 725980164 538311590 35330627 947508435 375722626 832981743 135024276 382725108 881461599 164895800 899513822 16263628 407950976 69788457 25105720 68880491 726961616 175164940 760320200 989739406 684081518 74967262 62304964 274178471 306629970 164114346 913222740 323159941 436880749 142230513 725785537 135164415 311502768 799507114 827479542 790423578 847019868 324019722 879544909 453396531 132498407 287008846 403953321 80659835 281634476 520784267 455593024 205495600 671457177 181855258 917035051 694443937 567433840 104437935 401432987 122490859 365426466 320586614 16019202 375499624 2391373 828927921 682335111 801789423 305627591 726932981 808868587 167771245 747644667 342498595 896460284 398355432 823193913 651303665 275348365 197846213 364035093 301576056 342433429 991209992 244047812 13149342 876091660 708539120 155400506 475079713 452021514 715346116 920382124 985981781 111783299 781065880 845270595 296210012 922926430 502928101 471906143 37990977 254296702 673814036 438779138 671206926 695143479 860582855 606255540 229481819 946127651 67416649 555403657 750339289 748102724 199889604 312170106 912612754 521303799 99270423 465718580 938813163 689319273 336090465 532136209 559067488 785099804 583219152 145093401 137984010 862218148 890007668 37691189 772072506 710069527 425625108 955544947 551164326 531256765 391383457 350236905 705178288 338584166 674004930 116034941 488410870 602293241 771823276 896943061 676907164 610493215 806470282 503286052 765061699 125870113 200507972 172684904 850638897 132766122 308978093 396859024 268107324 309610192 624177891 192551518 574452026 920458698 148611515 107156149 182839082 667740606 945779380 443823168 106204333 68953581 943899065 77859698 944446898 250354952 587228301 907233326 705935151 33425923 924731278 549925404 643660308 184136995 632987832 169492795 51611708 109983289 167549571 629837901 971260296 257461894 681350244 114213147 23242969 85328076 161078869 979661626 782177505 997222900 13243353 611317362 886835474 7393667 932317885 242326059 719268102 754414522 258142408 902514660 85444112 186244573 726069479 109428312 400402288 96411579 935230050 857260803 42435702 218754748 931931768 429923228 348783505 739251787 260400866 805103460 447890408 86984755 175057367 539920193 474171076 356678378 836287155 601055679 73355551 280677426 826230653 617523469 915758542 563256310 240112094 517508527 619614152 584441176 167240952 691903936 434306063 75683743 414576940 10219447 112666422 197004899 181435246 30293183 751614696 667961094 133351856 614523346 792138329 479264379 967443360 346320035 460702266 643365102 606414594 598029844 756277525 426193897 446960879 351467243 258947444 230878601 180860683 863734003 166730666 146143189 535847928 262098754 750224284 97688766 144952289 840663452 515765356 894547507 920535493 632683017 740488701 684731674 88936098 318523166 992391896 137102811 814476963 303489144 566147762 684150357 183743421 865180988 517878996 54591142 643589218 712377021 782142479 153385020 512350031 357908449 205783948 253490617 227108150 795803137 799379476 400988521 814540019 275136482 889405132 340469903 648579938 134690243 494347680 42911934 69018642 121404964 69941265 196374741 512801460 366213852 89052729 584862501 116263202 23950327 49245571 273120976 152069750 494382295 213338219 968677758 677001302 785898751 242585966 601037823 191288621 729297260 914574832 764562995 284152452 5741799 230103537 920001151 435150958 884733204 739053345 740440716 675640056 77270395 114405536 54764862 966236466 952468044 645360622 696255652 570629425 283800599 5936567 330844848 553034956 8539009 462048716 953672355 700238459 417564350 987650200 33913903 871264569 695291258 82482001 136045306 346473564 832950134 570083292 686753440 220412706 578707794 304330420 209098563 396527000 421545586 750482000 870753630 600649230 838026019 889664528 425811934 650366738 917276626 922488745 158042078 558169167 736955585 269638568 341046079 709289429 18190356 215005010 455596713 796166866 357728702 374827584 201675173 814489449 897303271 651642981 385578497 827587841 897696290 105390917 222549036 378303837 477789803 441438448 155592641 869505065 288655663 824968542 73254981 830410672 452274305 913545990 348897645 186446036 771837081 290252273 782859323 318780060 574360206 46191893 217012212 844957358 757426471 357962169 422779418 624453004 737875779 44104253 816339316 60125022 10289316 328945572 119908663 560778381 297508410 948667776 265364060 215027908 751142179 511045551 585576597 117291052 671442073 205846936 183546247 376229808 177191066 45393916 495076880 144586300 417103550 869348168 286927846 665522020 614616908 228898717 606228316 882708824 872150666 653254549 27688915 77730880 35228473 480115451 523367287 159064166 349080058 150822265 295590848 683740624 632511054 377948237 206217948 476332643 295756609 855035742 312687707 543670772 47295394 829142312 239169227 964333143 796432929 571617407 293854947 657374841 223530827 97695068 559777492 815888584 534953890 976185181 162931719 338201290 176144710 472395806 33927397 14348635 536873533 701638896 616996042 180228103 878053135 89985537 101312946 787891032 421105300 494130884 524795586 626124735 395821793 738841493 34751200 956423408 167055341 272177246 332818065 522439056 445455854 955541382 567124581 194403739 712792978 205904125 962063542 40688511 828217678 731576457 36646566 832195112 31381198 913652052 565982752 861683278 663658061 453143214 143380464 575381304 350797913 426030572 288992327 573452139 153431092 598525401 566432212 424598614 881490603 197988426 411462051 691129798 675083668 349118929 80695718 823418347 740483324 58378747 163351201 283407870 956335860 691398074 917494245 826705055 942391928 398484853 63337944 200918368 118097100 456176825 977313741 101818484 705069639 680209647 727567562 175763609 349964654 324266389 413544519 995642480 454948204 318046181 917914744 813611117 331841037 329313478 989545058 594124449 750542867 936008640 666452241 495996347 545676408 875017146 904562863 397060934 861024583 464994147 137813795 522300921 258850193 375803682 195747656 406219496 115490834 45336724 112959268 266996917 467503597 921479431 476400859 397984768 351976666 247433109 126010033 306643106 721639676 752644424 200898823 395622474 478785077 813388833 374926248 230036227 800597960 595780568 952606094 964500274 179659333 993528796 31412941 73926684 984438305 787593174 242239170 625389695 449825115 25812941 842486561 503750818 205819719 317507250 180694471 124743767 73363208 203523311 372726998 852259350 532653909 390546512 34963339 693626765 425190527 248778329 822069490 758699467 981830251 202576743 210231693 921649247 48455470 182753347 551769137 120191923 802775467 367024730 160791521 729631002 62686050 975722723 994211437 759290157 255918707 497840853 220480116 669048681 181614519 505115115 222300144 278612639 294481405 345161500 104750235 268382391 180259859 498053674 418411733 22820805 478694283 70948298 979038807 852529268 945087433 859048069 996140343 847251039 670813110 457041848 630301226 468448562 119909923 854431864 557143627 85426863 206009380 944826376 739597115 4084424 819353633 284380971 942612254 675099718 719043487 288390105 116529007 380690048 727441816 862084151 658150587 366958465 818438421 634249684 658001688 482568072 285493457 241150430 389664653 670461177 491547187 757577027 843024545 690681570 160332481 98495603 684235649 653475135 229441465 859730120 54970720 944549284 503693258 562466314 834923596 258181034 826990906 293948711 970777076 50066526 873215250 306259486 100441382 301739235 327893851 72230600 826159616 811256134 279173871 812199288 468221756 744818744 625677949 309483149 665792965 62277344 285380806 758302201 500245045 833607391 733927123 277667225 860400238 666763856 869751264 743426023 750124399 349306085 152640541 233931678 467835490 535998830 65700867 181109089 28535017 996025802 254786752 434980660 266124660 321311613 798610241 132056096 259229956 733662345 177543764 599209376 764392398 392163714 12771855 687582761 777308045 369452128 207548699 869955579 158162080 249335146 598049866 195262578 651718519 99809386 766024777 253031466 949945562 611188503 3314159 408473204 293610771 990814143 543274758 987404559 168091959 955343510 83682870 567782066 502032837 396637819 64498884 877602964 508557143 831997949 777171896 616594953 828699602 40219969 222838054 623524282 727843302 165691106 667172087 4145818 825416851 91377736 75343973 320102186 353679103 897775407 216294706 818065504 178655879 284169422 148975620 171224363 799462666 394348187 311678075 189518650 844762626 929402417 983733846 112832517 149547200 52040124 926053643 503180029 339973877 676746030 51274180 183733921 666672546 232415646 475245593 223919206 822212831 262382911 237918094 703216510 355631269 419373569 57265093 496941821 456317969 794749331 344431785 532245003 971229395 960517057 470187964 879768551 882331190 989487893 215830963 764665399 182064698 563748414 267139520 118667431 431399676 405544477 745771049 966127415 550285609 498051864 74375918 123049267 780094521 292609361 741451535 54757323 151821398 684888796 679228236 980298087 981587469 19934277 576208520 61919800 853860212 890182423 149528340 88928100 957619892 422524853 174067878 200487335 783779159 861116066 361136240 674050038 742984111 220382299 861645637 679898506 422619039 429255016 523523558 7891640 507202247 892356067 448442756 833197311 87107958 783456647 414015317 219618855 957367273 194729258 964333765 97816687 596805641 113780587 536593150 329353870 872830870 687791143 768646979 249524413 787540688 369816881 160378750 821357379 690837957 202475104 20218046 242207404 895652818 342122544 454056596 46782970 117820550 272238398 205374193 22203391 840711281 405107664 571980378 63232812 999564520 353891900 23698075 276514306 362326361 761605428 130245146 740464339 966829949 425428974 25083293 212301908 946502571 986475084 440037649 418813361 357572537 67422808 925889600 315952745 554037063 867695335 680928037 126467468 289738503 718021511 61456472 1616846 258293275 783814449 804285038 114073418 227600912 189634441 205792434 523194347 954486290 373480103 223373862 743492513 245983029 574736337 221097207 257753181 244963286 553897070 34261014 669103925 532217270 216631109 117458426 424837617 323187628 524901854 115464700 178422516 691986462 478631657 117458988 408854803 636671017 663393631 628993347 53599900 975355522 573834582 933713706 753599892 141896329 544675226 199149957 541670951 181115535 413532664 424305386 873323579 832046803 860177497 462924797 489189294 627926144 282810424 56513923 81309752 520925747 535542721 187611252 136603199 203150851 76993759 652508165 530839825 815986093 9364652 697748451 436509833 853644151 840504666 321696252 78328381 291996788 35914543 659429185 757131694 248905287 996496751 625969861 345392415 471260842 580053573 613376888 585597832 89224849 779950689 125529455 811619099 841853933 685395728 287977396 500605494 642785707 28036430 173941256 899826728 170719399 645164421 897888544 469562226 545405759 740928503 123174637 958454746 324289404 791712622 500976137 340098283 191540253 217933401 669748999 285955722 733780458 845875938 852181775 918534215 626248495 146107674 658142285 235004105 304767410 795919386 279601301 55487604 736621527 274437369 404131062 259747466 280647331 69348964 719678474 264517687 667504340 827568382 896912912 857421440 815835786 163616979 181702415 752877468 179984895 775167964 533305901 723121843 858981193 10793067 941187037 856768493 641102299 165759549 737196521 155134278 637178104 314555933 34952767 727865166 998841084 782473333 417593124 989559814 722643984 378756832 26422796 502253743 161663770 306064860 300822623 241918396 459623519 374753325 795612689 282734442 224340175 190708519 769463834 2167614 490546446 260739573 526015071 301163362 841219847 932541306 864975580 658099489 610663242 974955301 616184216 831204141 473506281 545074202 368368103 176904971 344434743 137677520 596488498 343088744 329506481 601673380 226014494 319928934 503871949 648144351 755769661 266069848 671586572 732442011 4129915 48853172 768845262 494644757 516122285 995344954 382344109 632212980 336903370 250067342 66602813 878696967 187566096 571724271 739341307 339588874 617535888 506064558 148773489 785278576 560325293 473355164 681354162 21406808 506457679 384077245 625439590 717629331 721844475 179698995 543243442 96281478 958392758 71627547 520404975 242108799 637169413 30978660 39163955 711993465 929312944 577214174 234243559 891439378 409022135 741942581 331017146 690817434 84746940 604512367 96095190 328387233 986787815 653441365 501235965 159324559 912758305 956419955 69016602 949328140 136550976 907217222 962058197 734154830 563837293 259277745 974508437 168557912 910522084 223894518 8823883 355301265 875294234 200486496 467938972 932229692 286853396 420348194 853443833 941426991 779798048 147365559 645616649 973370462 564660136 930449032 614155636 228416815 905785737 968955713 247079074 321638146 772586208 785476109 709026907 26487467 772783712 236162639 6810452 219953052 6986902 304268194 324042459 930849723 843799196 146595185 465310767 956010835 675810289 220792084 263593269 785039149 856939106 18488668 29105779 148720482 433075904 224042196 277652650 365667376 401892965 897454975 857006035 668916960 755809859 54422800 646670584 400844513 130545789 246288159 275025183 173509599 264033435 593601381 658897247 175708043 510052420 222092747 836141952 622382123 896222559 429600965 112865437 751593596 906481647 185990820 674405222 628464802 425363125 920254289 714073925 926148980 97058106 832291427 934933405 399397640 286630354 854757691 260616500 852429493 206304254 462628970 270734783 680067946 207643671 174267199 72682928 211187620 47480802 106907401 795646008 753953959 7254856 238355068 166237706 638928998 445796547 368109163 250631586 219383303 595335253 96890461 203899184 639559217 185609371 833112785 724462545 889082047 586849636 328418275 352953958 994718433 37075495 12362123 284454430 887356672 962487408 717633628 882840135 723907630 555219089 694339416 718699056 160989993 307086082 819405805 202819842 139594404 6714687 288216955 939688779 128997831 970303496 73234135 790556307 289417364 76907084 838813210 802759471 532468599 80900619 987350037 277067568 619004163 868537393 244743729 103257948 584679410 772105488 93204143 274073012 533100218 519935842 139502297 779124873 42295074 961521588 978537309 214595603 333990324 263702532 271621786 606143643 675340551 494296881 931937608 815713898 35981382 115982682 426567332 65186527 198245481 852591848 455429374 409522555 599229023 192267545 881359776 687085467 658414005 403772512 84690963 856376346 869329432 50635337 712803989 500024545 442331808 407466141 699311368 183496399 783967122 145378437 129853879 984460686 426045071 500976967 874276995 255448321 556728683 953869430 259332533 578442398 430595226 275834773 156197441 246757347 29126029 506952208 271304026 521519214 412240844 426837047 777882814 230798910 734958194 211051160 787981906 430885848 496139608 630742115 161891915 482376507 67488811 70229613 678735506 528794223 941752666 589506061 332423082 559818710 51814235 357847750 112027026 317682865 80425360 230314918 597812867 244189607 323142102 360670725 534650495 824722899 121549692 234955348 99332138 222373447 257073172 506070063 807814342 250675835 989746159 216985935 422933774 339208207 163303000 895010191 232889829 740369303 467296965 932839034 971697762 188200716 868272435 155616377 132641622 614497862 325019176 895487344 619252438 231057796 704595697 205675459 925581015 363113042 260155974 624752669 207022011 675369722 505216501 892905871 645097285 898034063 948041030 702789339 97827870 241304273 22480524 888816491 686921995 498890943 128563123 930096348 155506905 512457675 8136915 659572065 924972109 438613032 835296493 984076459 834856237 457635484 399199997 319184995 119901016 286967526 243125638 848593165 67990370 689983295 313325109 965634702 410314714 528389412 30472624 480969175 167510382 218046501 189463456 396383178 107436275 1892754 579378908 164556412 11177279 603450121 834955129 850330656 900974695 740264973 953177662 155188704 378569476 111142997 623977119 936033319 542653928 955226734 973720197 602241304 117459324 128635000 977947274 747660856 117311633 690516762 767122121 163190986 465068244 634899135 826888861 221698213 368267491 290245546 164389499 613393764 64181701 12743057 805788303 291632563 818406034 439795875 468524691 89579287 666217536 227903323 359048610 179105076 75507287 745053534 249364121 402954277 276628706 146626197 264445009 376504747 193770628 240035421 796744034 71223873 955131261 654849207 172751383 982606213 275301815 243619474 86118363 500224443 617530399 671286226 129583443 483076113 265202167 924051229 374983402 73673668 202747093 842035360 694577605 31548632 617944383 168865521 610674131 942708648 132613585 4948175 219158739 355877182 103922706 294107403 639714829 794871530 650968844 349079449 651936932 162952342 987053817 354183166 348145909 811170445 643742405 634421386 129353205 497012572 174402652 282291618 81250349 972832896 602443793 91882835 558429945 564048321 349342012 615277068 304914086 930965953 641635178 61323157 38412838 779547798 259217210 720449173 175660020 247363391 371240382 8694506 229277906 369324467 738948885 97562331 73170109 453014099 641229177 209046766 540003025 756248633 430415571 531834451 980979483 635141348 926585621 745368223 343745275 340647252 857408352 122026095 793586727 226355365 679709692 893885749 786952970 339201111 809444051 34342723 933932126 698575072 27131021 29950884 871150667 221671359 200403476 307731245 104617686 454315369 410591011 291884367 263630044 699200094 361517143 392858215 60815419 921184131 58899796 206635853 95402046 210001071 786545760 109033006 890530956 55431306 817788677 69583950 196301137 261957555 108826604 270750755 107434030 828065772 129337025 690996025 970736773 865245454 170415821 16907486 992684303 48941522 127938551 626955848 327777099 550844300 67149381 821342335 896786307 383775913 974628002 629091408 409440429 510719892 995173352 364747257 667744811 838013031 971898625 864478768 83357794 569047959 248292003 590827622 128064471 751564804 199247896 66199007 634897196 980724579 589681828 96281717 417723285 271686494 645590391 352566201 25579228 367870624 294061167 568443345 267839092 65687490 81965354 926458476 936813249 275873919 206482905 199958314 838526045 484705537 573452835 780144243 398768585 106801935 651477601 19854503 711998680 295796110 586322479 450626412 850907738 981918256 656652502 539180259 800570304 862856600 958233002 496330358 792742584 697527030 529551347 481690442 742230598 190240940 256025625 76742993 700649211 518057445 948101828 525639077 495003200 538241459 704639463 129071859 386692301 580485356 80810682 199264592 874823378 223955018 669482538 435294347 305418870 990013429 583854585 581826805 518638635 308409568 333447848 613072329 581733869 726005367 969010794 946071921 901602996 707670167 521486771 461880242 758683717 988746440 729960124 413816564 892212198 232982565 180409438 79971912 825534086 517413664 533419385 652751772 643252444 591218781 662547152 140189399 148546451 500363396 717004496 473064933 444050478 669719578 216683911 610526274 59239509 426225510 403014954 358320376 981952594 864792827 929623866 525963697 776569276 920571879 213576429 562749534 501479501 685511627 277054687 103735911 22804427 785295642 64230143 111137504 808819840 766988019 298204259 384595703 711517978 73655781 52478037 490417162 243401648 517107981 416960588 221886493 207933212 990847013 395897092 664960231 968565131 434703284 189744786 724029651 38357210 475310902 624086765 824019504 593671493 293073453 125625557 343331328 578759880 75269337 648028962 980748413 337036698 233856641 258462306 26855322 514788635 267335402 983498232 305061774 928217334 345143996 526281904 946173081 727402050 921105371 73728877 463658962 211976664 98986630 597111161 231020782 355127737 503152792 600178192 925839281 901419697 544295415 203378876 548082699 259535313 242222061 136010662 311188223 119699023 681247100 966318728 492824971 798291828 572271058 592532377 39979949 155979998 570327134 279864089 377209544 833165207 737469189 549425744 629103237 919957382 376473116 273664831 129665068 559618151 912280060 340714806 92478844 104196493 160112574 344499122 667452380 977524669 232749892 354465370 654899922 715153506 861960069 127273049 286680698 9419620 666072205 680845472 91585513 692685790 584092339 380696090 121103755 879000029 840583334 872048192 653166786 687515634 551455145 218275212 433341132 780049758 891265900 528882554 284216863 598381468 331235647 230339874 164519044 102714200 933231852 846676858 458616907 286021005 318646774 515163479 982793007 545252140 715934316 321943920 203026065 453065850 50546349 634494335 15609173 3536521 362512658 627363006 627740913 709678482 636528374 722765149 997855743 667759615 281261761 379558314 73263851 507913162 1438903 586949480 159287272 578819098 55879530 951557475 134025682 403620708 590126464 531600708 308810519 635728245 204498186 579872750 47227315 536337007 974342843 145312676 109596491 928940363 661390198 695628568 879285844 638236700 159641491 42013206 805389618 753613034 148088048 26443091 261785816 332197177 782817847 110071639 929892081 936802707 638106592 883478785 440676542 150335678 9246631 814652335 640586282 37278896 297429465 335242710 683479778 21137987 41414540 379573141 501709369 792180686 932519440 182027973 943211439 694002611 316172533 388543496 832091331 22991627 295015929 107479061 181922865 733308366 757666577 354693199 105799238 910926641 714148194 693720196 991758744 487455897 552868166 188825958 384316762 202034181 955490539 25223199 830962520 84713857 555085842 368949130 286342476 576687816 74319998 622996312 861868722 761789651 348073242 104225290 175583961 422859245 310935629 821454494 595874680 162820128 64518320 34408710 521909813 768895034 601603427 868987877 257674983 956108534 141867627 791175916 172994004 880310817 332919353 908878120 969925264 72905191 929606110 78842085 95256894 906089909 456472859 731433451 374623079 612345350 967109350 193481058 372418760 874978733 131666055 948344845 489475685 1380750 113600240 815119870 416093702 183780832 286849698 264539016 723695073 514221983 96372391 693814357 373933113 180016425 641314873 845341740 245530253 95887110 223250701 956442314 620056107 36039768 74614537 193447994 720669387 551637436 567008837 517355029 96974510 694194308 458130148 86297921 332110855 551869709 162320797 898304712 645981102 382209276 882931051 308271135 372293022 245110111 8180922 56263530 766959765 395775650 990623052 824643113 167574746 382695928 248952277 346660990 895258781 153718289 706865217 818481119 121685656 252353984 585509917 423784991 372664833 162032963 995388082 207230569 476637571 400529727 161661216 844162054 18869494 255281810 211751025 127001814 461237733 898467502 686198589 677556164 677354785 243767976 75547620 901739017 21497160 598922726 942813359 271050309 838912391 443753243 434416392 533723370 951174233 659118903 103742865 836803372 794745171 708054267 731688098 193623857 4731937 925261467 921466101 861998535 116110077 166161380 666706167 106954530 343768009 291709745 866426874 245481375 55575230 619455869 754154613 631919949 443024019 761304889 301525193 97172184 506432288 222638548 889471092 147951531 292363936 720550244 342296119 691606217 355574552 680604118 997598612 463878928 413253057 167946293 362533603 951326014 331436710 767851378 217370458 713136050 565845241 956768887 970144960 281783612 646532378 452818035 683645774 220435619 170514255 773733402 321969326 618882178 944717203 407901059 699278353 488350063 831806198 68528800 219803259 493025566 125164228 962201145 663306998 107208950 129343352 83746030 90756997 215946228 385052858 276604799 403488968 94033259 587912295 722602801 768185080 367129887 529094596 245739037 966923681 542285964 645946865 461789042 599788679 409779064 274008472 131161265 842979047 469253496 295703923 708201671 273905942 155904855 217696511 738831622 411498233 963591912 116811007 589045427 802715091 348239612 266756671 9704156 465909753 531291838 98312051 294470867 786664554 677560399 244802506 621566037 949604045 289395118 148460118 706513136 157135229 462641727 188706580 469262784 975640766 814977565 159911809 877455845 182603710 957862780 15858965 979201237 149740672 168512547 776103232 392870694 488748169 189862114 846184218 833688406 698994108 930479555 255912630 636368900 901531260 984982330 524590678 153604968 682249238 734654104 312221444 305648117 69527382 789272135 460954497 414007813 434756415 800946590 49683631 354110715 514677453 913386147 119354370 423825189 142607489 482431552 130077366 175241929 910553319 591433321 222588958 466664833 931749287 813853676 372875975 799395809 484816530 419177237 462271200 237759500 410516427 414462566 643904801 95893268 964780013 664316705 527920169 597908590 260029256 584068804 634034469 786625527 655881575 475193443 148474910 201191652 682186176 938383027 544723260 859375148 192633058 267778126 877112094 264959132 219116670 328001211 579663970 642553757 230882381 472221448 36259449 685178943 516313936 332828150 138144812 869415446 390290127 108283370 456339170 513856156 310881793 741616927 499073378 466109942 809624911 484521138 62553818 470981572 238428440 691733276 229275862 746844474 226532860 615725318 846457806 560644910 67208274 177225790 741808463 532294990 406124363 994728167 904007758 202654297 781063581 158489067 204614573 65540171 794567009 995700589 547236925 250398555 179002627 117302368 485288115 114245429 174173030 210881210 47011043 352262469 882831968 950063600 357736225 572315800 266709863 420966778 866496789 66350311 611027541 120960106 760535603 779487652 957760336 250266558 653346983 694546862 953998948 491113871 976390864 597712627 892780464 552637325 754608310 513466424 72897949 507736129 997810180 93437333 782126846 732057405 735149069 875101045 618601245 203049807 241392311 611459455 700899377 95769336 371652746 470114917 252931357 211646693 396982877 263249671 466027284 699455906 630324148 991009120 430829410 54115564 908688807 210307025 186112274 411762938 197680196 939110819 748670690 126931861 836048922 390777000 632965854 57337542 193732079 679502208 207826461 147993163 15641631 532020779 321890554 739717964 267520119 271611235 950255515 788405121 870420528 232948265 422327429 622569072 121739833 150341319 509277383 285404804 171035229 950116230 957856375 540902859 415274782 521905567 684547125 933213901 946257968 619260574 57353669 503012762 325339827 485303064 642127511 210037319 799167874 99450294 89134530 54626985 987161347 289572501 111127460 708165293 55666012 720016241 898123145 476169620 204060508 558974539 460615554 53806728 219311615 58661798 601440771 825879590 432975984 439775627 174551890 916719414 270331312 68103217 475543760 419557986 940153818 124540128 926686310 743878041 599785450 55371363 601768501 655684205 84307209 322777593 215715829 123309419 583480956 400763954 468435898 328138034 905400872 88326997 126335668 192045159 5312881 434000201 144611653 88259232 807397639 107534551 385052674 130075095 187074931 433100114 115266896 184420829 792856761 954587209 450528698 127518131 196414031 544602136 10459460 76045397 762743216 243820077 454918101 158053010 118013361 314602554 82405242 917542731 583090297 87599062 611080078 717035068 868576554 561364303 710345300 764536515 144614504 210746889 66781741 51632930 94796038 462424189 148499489 212586343 803467351 610116615 951313898 350150144 135406429 174853684 219084935 143009825 303203301 8733600 662937995 460881672 958305546 358946199 968918914 660073839 802772782 680681573 881489852 43994802 94334385 133436396 593388088 729697491 948646152 237090390 103460259 20091530 909383241 838288590 47133872 886658985 235672997 419171709 855968992 175008860 736516935 143926740 381052652 777774804 982170693 121989635 222183401 217232469 955385897 417640131 381560043 800027722 607469500 166478516 235536469 54050073 259620551 986021800 731213329 356636341 352685407 84209531 190268936 549544370 204998228 585373552 801488761 807059442 256591869 540585962 403921075 379274311 763609802 500825261 140941585 202999388 537512584 413680994 204492514 491808935 22740823 857574144 280285095 557056964 570326690 602473800 451889296 639714459 627690249 182492654 777389435 892128913 59047863 413127039 225475901 272633104 302859704 804883795 2032846 938056348 360235630 64227093 190270269 265857493 227619749 149214285 600255487 731234331 112269426 617216827 668643988 801115954 283053347 504537978 89907527 298248541 993425364 865154011 246305131 746888652 327599797 950557854 547331556 319617217 88649948 64527228 189136981 598817757 301831547 719972155 558795166 649599055 471680006 12393718 879196102 74674247 439448911 232250390 386148684 268311694 107558254 491334337 182565807 184747816 584265136 20374963 949371359 16672693 382704840 154446686 725807693 35508603 405710577 9251690 882924289 924689690 760967465 60171049 633646587 684973304 413430298 807537675 145070782 54814443 22358335 927432561 455314383 683013950 57163319 472319610 463675967 366778709 621105492 3445373 46083942 351360136 561209414 593137670 982632906 650879771 442894059 166487732 968195638 442689716 575526981 157461169 200708137 367845637 928203322 245211261 98909595 266693335 887537465 926737591 668413962 589414059 950271832 299499392 327716654 4115185 558572065 514461701 628762318 322861540 584884866 216660892 804317817 459827969 396839322 710590140 915454788 91404222 65344359 583232646 49930519 526540602 393511091 939780328 382651674 790019641 323270849 353009764 906607202 145516870 855853892 349170393 711524135 422934005 668302288 69039613 41720969 20191008 935490335 61036728 993765249 59733844 492088944 612193722 420164137 193077348 986128719 501125340 64728711 540564406 298262841 217080775 985201341 903632430 711379329 691852082 326092612 611302927 49160539 76146497 909440268 262513914 632448364 391797980 290224757 433361288 679359393 617420754 480078168 824411204 254862914 548939941 570541468 827196414 233037536 937362090 894935688 862341704 629416529 188866760 54165573 683406295 819984521 151371260 958095977 67390545 476591188 978822263 475085794 280516165 537154795 863831297 8734420 178640593 565461518 534026248 358626540 439688743 849834977 62851010 668666991 210818205 188294476 583395155 366008435 977223344 999352455 358896859 515146460 728524956 803463364 23300876 318461835 967249800 667842022 764151227 710809787 379710792 489636903 291256069 915349635 368289137 779197255 94579618 217730360 897656882 930141062 786121844 144334613 240856054 761149489 597238838 393727141 620137629 873152357 216219141 710515876 622646483 345220526 51611696 401390899 431997859 222846959 877919563 564276344 418838803 427006306 672747365 682469458 736038766 579311656 133882029 763073024 992187085 17252114 997333080 504599055 890242169 273320750 277102398 858635907 288752925 447565665 64206823 465888215 885233397 764075785 233922620 840965806 2184190 839390939 713332194 412959082 42606548 581412726 120323765 947443441 514810385 432217108 49751137 996268247 59215358 109753775 772468063 91788594 614528443 764571021 395419530 399195618 313384284 58286473 6650409 854049005 856161489 260636262 421759268 58128530 838378754 356288255 445111552 939593315 141598426 716891164 251164693 368266407 876395779 926714893 349368288 911521469 217794431 208418361 377473079 5181286 333771666 613305621 12069535 106617082 945174015 361120265 29668278 829318265 685362290 721923981 156377781 890576239 946967088 682423131 212454690 866809289 923596436 449378119 239177925 518972904 677003357 126537819 593127498 363609481 68476898 482518524 322220426 517905896 288147781 345801795 23022798 665400107 25412711 608253633 534883188 147267617 848311089 790484185 591067837 813311587 289307617 448565393 248027901 874343324 321062057 58764431 338993463 481512615 965521806 67005779 235264328 52778481 92842173 46074661 476036225 96743247 27423172 382094369 815140641 463025595 609629974 822644026 915035784 238767798 446272232 372441100 283587075 217678284 661335982 758431390 318213991 167526991 624213709 461674912 290787541 26498224 98374388 979632766 337891382 466297785 596362671 205173193 54756607 872586530 535555696 508788477 973587649 732797112 728047235 913481150 151624246 365356747 342233573 617955882 840534788 272378455 321188074 617868887 807107879 568917612 156991265 698836026 56108944 489211762 480591492 893568340 785657077 78256477 680577570 667762266 442380173 379993019 215420945 293060515 126145880 551886678 55610828 67937424 302908795 378105995 772419887 276104099 661925243 408444181 82292861 976314988 601433738 933463309 154739256 167090662 427907326 319795118 57528915 64863108 190630046 930264626 878452387 293424706 808134066 566234786 241217471 3997652 978243983 351112399 303976864 411401344 63143043 555878905 370862048 749799717 535014223 596131223 718004934 36962026 399632419 803131189 447855346 425230739 313163190 958560849 96419692 921364984 794121528 203460825 22596905 629031120 781837307 700439689 91900473 478154206 202459736 607526518 375570636 180728406 78283919 25148938 341643096 729205567 435840532 602205758 105350864 797773438 168290031 800108502 365052117 82265560 203524816 161362050 208782433 650233114 423357532 237051845 780051843 371490716 248201257 316206148 722131660 567620494 121693601 608101295 423605094 776653041 178726928 248282186 980029101 544149176 182660211 582074433 145156169 750367011 832192545 157838902 182150349 99566574 865892146 305140155 934980825 410219691 585508837 583562729 662307450 468626304 34804321 195006069 356857501 60932768 607969398 603354339 755638150 337805049 528098283 49975726 202014875 978890138 520579592 707790093 475958906 324879696 257288369 993484314 889834130 13787605 474688031 666292650 828286667 272960434 362105540 489575441 626364507 570533384 143963285 890133124 232375778 153431857 91637148 436172490 769617726 82552685 312980354 978146124 136521254 956576135 792749174 121752803 885284055 611612493 41686799 26765055 786347773 130118065 427678265 245062745 817637631 47345370 360446116 652020759 380922476 943662793 227728293 207032359 209631400 84846748 691308791 757585971 24579622 580899036 99903641 173784819 988260093 95237421 808451129 348765228 339355010 970030798 399706083 26601153 242372205 515873939 726889958 971784434 129795219 899002962 503273243 753530550 443826569 374076961 383153135 458472371 646677461 717574983 80755962 455038036 608738785 258747053 914786534 120800002 413177373 394659423 31935406 468926842 390528410 438853764 412734298 352167199 850802636 513467418 121778017 708059935 713414505 433871305 806583300 413350858 64722338 247487797 802247344 690450787 184880659 304088606 981363831 579570421 615448795 718337963 667818941 377255714 831907630 454057753 116850570 621725774 359793032 514375809 802677431 562025172 318787091 795516887 559134326 855787149 528958190 87803311 850788258 327330746 638328952 909291237 633785998 908924399 530940419 814344861 450286923 290843471 913593817 881592711 198463507 407821090 590032344 561897395 592179244 25580719 483873912 796229755 16093904 341873148 653454250 283145073 902927951 726148905 845239532 386191458 827002108 733731188 949305895 25493402 514787366 350639514 112075548 895476428 447403592 826408064 285028855 158327992 446709806 968827892 813148542 689191306 21798423 312131380 85180782 727839999 154397957 721008729 758736497 507310325 544774136 714734108 806999551 877129052 223952556 83233475 786046843 380583372 261805594 362814129 535162045 503138177 791096704 602291084 40733321 820648274 503869150 96631508 957987293 211491206 220686676 268770816 48251481 504344176 435246292 517897144 964024064 188000404 918306596 989845348 238253745 251767914 354538870 171329395 321176490 151709194 937050188 662682043 56935895 150655541 998327868 369188378 38743525 304306398 165789631 179014991 372355522 562018677 771025237 416593063 694013852 240159038 756054606 59002010 623350373 795669116 311900249 247329596 165817175 178492961 922393964 363066752 247582908 12952964 222713972 507253277 288118970 343785012 218055839 600267704 226472344 750017618 101476288 847379156 465086095 677557799 171699666 286576351 477741942 480069712 694544418 397692189 605126731 199694470 658051203 942027963 248763929 891042031 194960418 80877330 56753394 666425772 50562377 744878631 89552150 120281570 836616450 43696564 9303217 487144013 211905392 520749125 846602323 649561192 379447195 605418570 857453661 284911680 638739102 807973605 193771199 816838030 364552161 157432519 928750095 919654767 141520440 293477770 868546742 230724442 990492214 134606404 810323994 266483204 361212025 849606392 565715952 197140120 54972789 330662662 182301324 585279142 360571120 689979996 350656706 804187345 141546115 74890716 667867375 962645093 157246007 871032809 791064832 114283354 896320939 107423794 77930797 246881064 76161568 61880491 272971164 535168613 512637801 7851240 265872037 744954594 138247073 542197260 153304121 919422839 734564232 36969134 216358938 42550318 968444861 193743862 396210297 405846480 59830320 883916990 1850315 181216448 457218498 982313252 234527235 172490109 58741310 954360579 574858589 752052917 346690777 336483037 85075226 629499008 650786329 646511183 442905524 36558770 221965038 137081225 727950532 575506480 63623115 585545864 138930739 517339427 72747305 116922278 910587279 267286817 971841222 728768774 421243003 48520834 991546761 627809582 766935729 851733754 493255462 239700032 760746205 974111355 726638042 95538748 334709152 87457276 330441872 52844670 497162465 26891315 14529300 341846927 163805035 678709961 673104325 381729713 251105596 799491231 330917907 58964564 362878461 18135599 673768204 440752036 526796634 883910769 10788008 222415819 293122597 443931343 909076434 272286752 540881244 408168484 448913102 897011925 567817843 24665342 320422013 293910887 735669531 127514184 41103591 624388120 285615192 739307455 950581901 797753550 412903716 57220739 766804581 1879665 165607640 734510859 192046886 560047865 131547257 457724054 228273679 317465318 18721572 840441654 96815736 500341994 423609628 558492588 910091406 69288017 43720395 725233981 437725304 736045629 433200900 856540322 583931774 314155477 937211211 461517793 243828180 356519773 591301038 852986714 221448039 687480977 767590322 31095042 135201960 841394603 51360524 21853366 529376619 228183975 580379315 210303592 503340975 888152766 41575071 107388078 729200947 488445297 631153731 29743544 84748536 394206219 134828401 138908470 550760416 269844079 239109633 491875125 932605249 685767373 281398524 758861258 145742621 442586007 805053987 982113916 194282368 840102663 468515159 27332424 887895140 808455016 258140636 205988309 922043386 692608867 396148696 414063184 14515111 428165316 85403226 261883115 119780720 750260863 16774804 50692648 106609650 726326190 261493887 233546552 458580867 955788599 462252655 835618524 586432932 116400674 884992808 673577774 510972656 736986348 43358270 768714284 124634388 829265465 435503341 356654260 901924364 812715721 206260412 701019353 967386106 275559602 923633888 101576435 200170544 430959939 976877816 808750455 391948409 509222733 412736581 896771227 890282934 550913236 714633489 721101744 350844703 965556804 913945449 54591077 227249891 500624878 454486397 246979688 566943357 315467974 493606695 200249430 468689652 624348562 255136309 920371663 22213936 834339400 896402771 598577249 859530488 903592304 18248848 440420778 545024019 431933738 881258037 599917269 919658906 435705522 999125595 7464100 171413286 85554489 837782941 537182099 682843806 271527451 486603056 451606709 313054146 146741457 609809913 899263028 126259302 742313781 518642524 81986774 630206240 872370191 522452546 155129380 77464439 216865196 333142332 155543350 204544243 155409149 573414310 530312531 876775495 466216934 583946855 830687378 804959804 885268744 748444872 623036902 310559165 911051806 865046373 225497940 596238647 274578840 952901942 815458952 443226544 675098648 3053808 563016236 528231800 977412640 841053085 285164099 808701015 422345515 621235995 794231243 555314814 207471619 424388043 567776058 146127128 577561149 836556077 221739596 457097931 519954537 255887841 912822794 443680974 3867729 533484025 387500822 258123370 574795540 691696664 222651301 849685637 634116179 951184758 321080897 145336026 590660397 34986986 523618501 708294466 335894132 658624572 739099472 233857128 959945801 948845028 502321091 62708505 692350153 42530214 278056254 85947400 108187030 936750832 186150202 850854625 715555672 188638480 57074299 178074110 642403951 571237064 342795864 273394955 365885834 14564274 645901888 613459300 511919964 408041857 670229001 627969012 56767954 766995224 287331525 811664496 368946349 402010957 321327240 166667341 188160297 339672677 941769513 854177744 969100641 332729427 854028688 755142244 317182990 10966468 167513430 389783569 839998312 178491108 734689874 819858175 502072104 36377673 14407116 581477757 308814732 140417370 421788765 913560770 894741355 347651751 464513076 468378550 259195255 792652583 245227675 445012420 125089070 284569687 422563997 886818268 180608896 711692051 387062140 902673084 721313407 443909277 935870500 6534093 3174758 412475463 726481194 275348106 217491410 861005756 683993399 720060080 799105939 509366239 83428780 419992490 575387933 855209984 22809717 755875992 719263766 554012831 559111053 893085231 887796766 344324318 498764097 767948177 690094878 391416081 272005131 909515672 623977520 556491913 274737496 601778607 222271 624191484 283161296 190686597 40307499 108833683 273181545 80415306 333028013 171775373 583248975 398502750 80362870 43676115 458391519 901380918 860507443 847149110 581912875 303265334 931369801 185859978 698180423 575682322 7230930 62986478 250891840 100270239 273358240 680913273 579430127 380511078 545719495 264228876 270640606 270562237 178481785 878857563 293319584 453639496 260795304 936370179 416401102 353984112 914130586 430743917 718401812 583773363 76495149 524743991 646817064 143640019 677179334 984340460 806182413 826193921 581283872 44236225 181295061 185511897 443198045 178978085 908405118 195518593 299884226 51817549 176527548 889272997 952933088 246867031 780875214 596431225 187309396 228918407 350528337 261865494 512122451 225904491 192081874 149034050 173824376 132927686 138019469 975803417 935622137 470308789 3731260 378323938 358665590 527568629 44691659 655879827 75318507 799289082 176507544 133251509 358727412 602163862 104827637 63497101 967298935 981644795 938735986 142242713 90759834 762259334 209380382 170878761 499449067 862476184 111244863 361681309 935736019 890574010 408637730 731460020 969538135 263613137 76022120 282531225 282071236 147441678 315854179 124081163 915024157 273375753 328313972 958875862 208722830 719974470 284640144 168883777 892064876 26504703 947934978 730143227 731325312 186627913 881592162 123443238 687907046 665448539 187118281 340067364 494453243 84503280 811300736 641733618 753680516 600275051 171679652 979393474 406233521 163964192 315843630 56902992 43134086 951215016 982807362 585962936 180098515 285662753 171905053 301714144 542468395 149750074 717963689 56146687 360586790 43982803 935140748 729441635 2504137 224694464 873323713 186267352 605706716 797796524 120463850 1825601 784293955 472262889 24411648 630893760 82191617 260575497 278253856 457835319 489335123 162557759 612533400 148566958 753722840 188239796 899004087 248153877 844651776 164210085 528151165 253632538 984588004 389725889 53899844 184852055 283644168 370394098 976691411 1664819 376958638 669566001 526583546 699143920 415190867 518144740 864541725 375014364 560681016 239319075 707662160 616143210 865262210 356311407 873822749 69146207 146735653 93725651 664570071 32935468 75911961 290384671 135770979 464106222 651312016 330640612 560980807 511159049 859611050 260697991 717751641 937604464 451862219 438189955 253187271 782040072 663979271 726342616 229252537 102591452 962762739 443340665 136370315 465770696 808750123 64665575 944091225 674538146 24472073 785256985 62331369 482684080 951044779 764123939 446387585 706881525 826520871 296962992 540282598 707300652 367868872 413396121 355365031 524171156 558791433 936716180 112912851 310086274 27936688 7425434 281415535 305480106 656524072 279539240 992435380 737965630 154216859 251508215 198185682 236970139 649356694 466156846 593507225 935042695 350859687 616098789 890711204 993075473 688002378 969449611 926780703 548669812 939370954 248007295 320839779 880185984 864565714 246491113 13086139 986974239 977795122 33760414 692611926 94338801 496463661 82231587 577738551 690604698 593245146 927402228 892098872 75509131 920376353 402837594 241065632 7324862 851478871 30691233 541591360 277460487 636357074 435704822 716577762 68305070 170368994 100656520 662037744 238782086 151678310 778368217 631453513 16857725 951456929 800441931 511739656 291062064 99346953 605838347 822652034 271405010 175415568 982892397 652146506 827824423 747634407 583911749 670588166 758384520 880859281 220002413 931577285 38988478 16277188 649075153 63829092 446105573 893516121 109503986 80643943 625481377 750171121 859550420 768195291 714727795 325819101 276499948 427266336 190619339 188059956 381018644 79523873 956796365 971001921 61853013 6596530 879970236 667727829 876566039 968045393 442539118 449679537 942146183 249135734 155756236 189851327 44000810 43056897 604957100 121590534 182578934 406522367 39284796 90566013 117314956 911468736 287421245 609252219 247026423 516999663 714932177 262452281 599925369 526851419 303657804 874970995 662950815 246204158 1532023 222070757 123008345 171590558 948893405 487873869 535962781 496861644 312601110 328236085 139499278 740922092 432048141 95133058 130019599 83658230 232690333 941657330 49236843 726325793 300854307 779618295 104263923 285161875 58431704 326410365 997362903 167978412 889252484 957702612 683320117 208611521 79313466 433976194 276728252 944710414 155386315 460704525 776609828 316759788 917644441 751397380 125848261 358318964 546908391 184018843 867396200 473251183 617896965 977319212 377274238 713698759 284591085 232735579 217721243 642324767 486419252 156085683 545467735 929388430 514118551 81440017 113387314 829278613 531080131 59398732 355123160 328669559 314155356 889819002 684608914 420964442 895385286 283113628 647814559 300599695 237496830 513579039 909262906 417402488 54259196 371786758 781978008 525883370 244503026 395889058 721333925 81725106 970261266 262240720 853140794 430322866 814567702 747815919 361754172 77610272 412799752 611138687 151121103 475841591 851191523 504285898 311374125 118797497 64075960 363994689 842221265 289509634 283538769 965105418 796320819 514092621 586230870 7838840 883655179 653158941 976095826 119467788 767310496 816848731 582830688 949786591 214278402 490355733 404338207 261911253 622215924 734126045 148644023 572316812 612650196 360235103 359912168 858459476 103093935 534980538 434189901 198455419 607932375 16489844 743250320 486802243 274189468 242561226 955791501 636848048 539942486 17589604 747220764 429288248 128268210 140620037 873542672 351060182 786648806 355141844 136135777 329355459 344849453 385749973 418393889 698909271 364653864 197267518 557064847 635503286 297939013 869210125 658475489 112602329 941433994 31259467 660560784 80985527 568433329 783048628 175873152 590606885 112292720 896678960 600477887 682555198 968871874 921843139 666277380 245388905 37584488 131434888 123117386 849436201 161342557 176592519 675505823 202413925 610236902 764438112 911358710 345466688 31751077 553005794 117779133 958787658 666993285 297700501 860666046 913806143 676488637 365618718 546014549 432202251 458279 331924075 423884344 798249118 713333727 258198949 458582958 955170115 307064639 963034714 948208859 466274164 87883396 156999461 281315778 502282685 703344774 42052740 460501565 488573774 977936708 357840349 179460578 34077508 909081020 343529636 810174217 924214423 293974293 66544749 499472239 330445929 360070014 82091964 713799824 140802463 679679870 589069164 465126369 491038485 742096158 798604573 447537724 184800686 7435090 169162240 327637487 576791214 883293917 242473169 21112243 445779768 647638328 386600210 169228053 765013724 314213123 498420169 938519523 540141363 997172895 242873544 601661096 367108703 21723664 67405923 256413132 215772556 111072210 743692619 848388760 294272298 364810374 639782810 179435148 145134528 655779384 229620330 67478963 898909132 164937017 473619356 609009116 668608535 536007480 116718840 923713541 535463089 286169523 920631388 69488014 836180821 75545935 370940816 341225073 973627499 465323963 270687816 244472876 721606544 445199169 266717201 634609761 868350609 131243988 695268990 849104414 626641990 743739042 292771578 608724396 559568442 262345357 615502220 119794852 55695182 113245139 497793252 135674001 906117951 84689898 116784173 20663014 686316745 792109920 743302737 787168201 284580963 497382046 410045964 435172843 518660918 103954163 279663871 83744029 598745015 440314345 882427389 30219347 156835089 718144426 655900979 262049669 69076745 958382459 887422677 110872025 605558190 195847678 698352903 620278606 173857339 129776621 939250465 305586079 289759768 492779019 140283925 95131345 870472688 460489689 480583099 914519215 532889718 6226564 321199005 16304147 820053515 714098237 309323815 593463194 284479402 866557256 182966335 771374530 135393845 128678079 600946104 467094147 944037235 235604998 748490827 786173308 491010832 112813890 139142744 765053026 62541130 120392999 724153308 37382085 834951931 355758592 457517910 35766683 660785449 797395709 779244752 390260837 749544203 686930742 664467884 506316066 805370345 98123901 349954982 443346852 866970555 199949302 486028661 737569910 686469031 184272142 892063482 686399868 628297550 269401188 641341753 242425179 220755809 215263473 124303149 720872690 937534957 520116758 200991680 205362316 324538633 436226954 650090807 569380570 584574300 8029244 518109643 603849739 180315236 406129953 292605244 760666516 649675559 835530331 379116076 558856863 748109904 749177336 229059069 355024984 211301663 129869106 733403484 228601219 830353936 7620360 955137730 323743277 627449633 138405947 339948937 979481710 333328581 484254605 136843154 423413877 926448695 793329927 515303403 324376896 722218801 142652793 316975516 283622674 591880055 792165976 571833289 231452687 664986655 849872822 236013217 48453854 214683212 431695559 423054107 243777686 850041018 945402677 750454731 282417581 149619582 253523631 736281942 503815492 938505794 624791135 873539700 921332717 694785792 359088385 19641519 292344864 378902494 377540491 651120844 518463398 522493380 545389990 169904791 665942184 100772757 518763844 311291626 237531809 855258897 621423738 38772638 856150925 697158062 951702984 920386048 995936716 230743862 478927105 174763231 163463734 43706496 826631617 101379858 178430938 288379849 217145278 698288743 397847486 288653142 747753878 188105898 673151923 737509780 972156116 152813650 356368509 86159634 645137941 695158702 96962561 665501552 982521463 702051331 57908859 997626784 883777696 256077508 756149897 74624809 798392514 155532133 182577480 621370802 812875562 789121500 717305495 699462375 23147464 757919525 67089135 92503806 623425864 722431694 662071204 468468016 159654558 278085812 217093066 456374976 744214683 714961119 63847178 838791300 76604973 870116675 586409811 437808733 61055714 569556052 768742846 40082595 982957477 336698991 940151701 741294493 428505490 235625691 420071580 661018948 101317792 621368332 102017853 690794988 438509759 197972799 882834422 190185417 232703836 850631796 711081354 73824384 281429425 723247991 73121289 173884534 382097369 237896214 291962533 596872027 490886264 86119623 258630318 652723877 434444470 106964087 302839175 37593398 70040409 462305949 243340381 368281993 750781788 13088636 557118315 614807813 520601721 867389095 66659121 646784394 206815572 731778711 596028262 439998223 480723069 176392646 240204063 990923814 651464262 960782444 25488769 89344250 985023972 845815977 783114356 695996752 194796381 309646700 589819972 507605622 557368524 560278371 337417769 141268956 663020538 528541749 784454515 281896266 419841196 942032778 898408353 531304015 454028049 12459009 749727980 646311360 740766119 270456737 478494020 631077234 577223488 404920756 50890502 732969582 222246725 765490253 392015412 710680290 995893614 122941761 99957989 288899002 140189744 782444756 222343095 844116199 104382725 175076752 250568071 715952604 769924694 262123449 219460470 140227606 325420553 578906970 181633215 815331090 234406540 78738874 282786825 364571760 186164063 251554802 35161407 347313243 929607466 84321490 436172801 816595138 403276329 649261146 254304189 30858179 444720379 101350121 996260309 432612222 540505279 239515538 222987921 898063152 791502384 160967745 712085334 137447180 929448871 214412284 699588643 721563515 978028730 752663023 280588264 429139351 964925672 222830437 298334944 183247319 590280110 195078066 36217329 412598986 684877745 453231005 105892943 418683017 208670340 446492986 408478967 200216092 269946409 107770061 745026457 659672047 779010990 506335982 776444851 91779248 506425538 593038443 272868722 545108212 404533801 745508126 921150186 83825850 81722775 820073799 58277308 785152350 924931515 354781817 553955863 125882142 599068527 365663049 982622080 870888075 560925491 365570146 467055940 187238146 911410686 616174233 294726450 590065966 818677627 272753276 345554896 877273810 180685577 770391105 290912604 601933019 114755653 855148093 644205184 640253161 111572869 759759651 180290163 43491231 314302804 221702872 419072743 904753918 51894190 790999800 251754279 281493370 568156919 370451813 302074964 921471169 495191179 129125940 230784922 543267592 423803554 842231990 903237382 283869332 388376139 942739772 15574705 582921976 350954583 368417819 545695154 211391271 576723042 90488978 952596167 318955497 707046883 904636766 988719894 869003525 181699089 821877656 578850973 875957054 273856445 284326988 382811119 733651930 960467081 40675694 149737218 107097011 287014379 520412849 202852467 222034149 754396583 244334087 339964574 583732701 152412854 360566205 780352880 933455739 82426993 14303004 40869761 244210288 468124856 595017414 159379781 901354166 993939474 983747680 170908696 383595976 28490576 64394424 170374802 666491800 44422556 34660261 194066582 389950629 155830308 721664087 282059904 960765858 548177946 237989047 899386029 184312351 226252094 527160311 310152044 774456893 577090127 107824230 359395827 325155317 791995905 849513552 613879246 228696505 479078347 259983618 933804997 73552508 404252119 504981202 824807544 49960543 699714649 183142009 849974334 799995263 784644144 364048573 549541450 488061655 21446505 238833204 590455209 620287369 640682171 915207571 257864814 160074023 746487661 64663814 743263418 898391628 853201631 809230513 283933033 696984910 340598723 41869612 220319647 677472311 937656998 926005216 956448039 807381115 61946891 208849768 513508227 118180082 151202832 108060970 341735654 249682986 549847250 45636123 56774726 288159942 140817602 810358717 982473806 454326151 691524954 319949465 544741198 960009830 707772790 390841881 258799152 342920333 487282882 702068836 204690127 963885099 178850932 165991589 240675244 144503959 853863285 363102701 306208041 192622795 65775211 454293482 798949642 277644755 184582150 958678713 347768648 605747950 594874098 431106779 227485596 155103680 626353910 482795872 394751380 993599145 812209015 394787527 991534374 638839306 335366139 107359433 57082688 779988388 895530474 543904029 638662970 668841054 15919750 443395526 309258264 574541360 410606324 868846795 717461729 275583236 897284900 35162813 266533783 671286660 846721147 841749166 135875749 104335349 28218715 964821138 998112412 60003091 206610410 242901524 23188114 131666919 568335991 738776708 303077555 145677689 458105784 538407676 68726512 660338819 777684971 471304627 145428972 980445816 417624572 217727370 29592931 217922635 151362518 934988771 709906896 636253239 433637337 610146043 88389268 109366574 577079205 533182517 300369865 719435346 2097147 463465513 261738131 114054006 284500272 281715673 211141113 545634746 518660973 735974904 87093685 902304690 833483695 103141717 827058149 45675022 844161201 306411253 253726765 180011929 144331434 737042913 564312233 669595608 61590266 131727746 881153705 149581458 310390151 720480577 468315144 340443693 935472333 867872268 290239229 1726607 250333640 481760456 66390495 608002591 476773772 70770616 489832449 749481432 747783069 456538820 91791728 132174655 360644262 827881636 698012271 251643296 572933538 217524322 288127877 678886303 827263356 111908301 541632313 235697044 899384507 693871832 801803305 809012219 481569253 197834411 290572980 169146733 247067618 871077547 816547482 739429541 81484089 527307615 752475093 143356724 818242755 459689244 532046136 925037805 407260986 22809909 288089473 381095486 200401573 695734012 729124349 95992902 282468172 265430716 106036489 737349228 609023980 107229501 87124283 738842797 140977925 369080144 454937049 310064806 664225424 661234079 190480253 520268244 946907346 298106912 502421474 54714113 831347601 254808580 271081036 32231076 298219266 646504482 654579446 233471277 965492913 121502261 347944895 905881229 308043549 324569495 647409319 474008211 534969115 666181036 342000508 185718944 306766025 721988366 437717365 897431531 168964141 996323660 860413974 710286666 771596048 583396923 343304679 756293057 514829423 28037794 53783332 226129736 804652832 436040733 682015615 38188637 461588907 9179255 513056385 660184646 22480264 784775855 820001559 248623437 928802481 14060377 321435594 585701231 855375528 451102516 543867395 908159766 771608681 140125572 959479638 723369190 520565377 962010292 843089199 876594534 359905608 455778604 230197216 643968319 739592015 391312711 470368508 53837261 78804225 909533761 371039843 710920391 690269729 627663123 27457434 26140416 237224025 190274001 928056156 808100092 193964281 493226590 612871147 824277298 361790357 173760611 746974862 841272939 18768633 91771773 214145158 282012205 119422492 416094258 384578067 219972866 136105110 130682524 422062674 947002156 3872927 438768365 46544086 683242169 217382203 863226395 129784592 796184015 340579362 501314759 451689841 915981576 510899802 510579061 160924644 687530730 231742743 474319798 798923830 181572316 434458835 679620003 392703443 859898819 270756037 244884250 15701575 353061141 510570776 494358417 229761958 835971256 95183693 601129453 827488358 833474129 656637178 185971501 736579231 502671896 709639331 523951525 307271207 299462979 41518047 382558224 389571035 66954607 603198633 807462326 378690547 535767557 609424408 45044180 747486284 175251040 290483575 164017765 217557186 128555175 979299340 210822743 46314106 445507730 137990994 413875467 702223728 354774658 341918055 507130788 819715383 365087125 609405185 859428542 270098002 587196825 191974554 13325494 769645634 655863462 941166271 268841254 370587884 349009335 73391818 31038305 893456082 956591556 236463175 255311767 247195300 248924966 840505700 576526824 123463367 682990458 485825264 750274600 445309702 3932335 843572554 659696833 127653200 287336306 74697906 531725920 68499376 582072580 282676638 59213918 881167451 224595411 204515768 551280064 633566589 302390042 257942562 697519685 53605500 686489597 783749884 16611330 257392672 584003575 123455758 218075317 214317957 448760391 15387539 407041809 839902152 443416400 398528608 827420054 552638741 152363938 587500720 139312572 496164868 490429492 363835711 979146675 249957904 846908641 107808846 709866530 949137392 140617200 656830445 448266444 96265265 825500200 907795305 720723330 827462335 30316632 99866735 570428621 521896445 142046641 769700790 828862180 559886129 156855582 866780214 532477547 790483398 979531673 625737157 59227829 625787219 597849272 685117666 514565746 553607860 524641364 691662010 148375280 634182084 303640265 24768816 457233154 769563261 108123359 87832428 890391857 559929736 303408050 11541753 281115301 267726756 203456507 173309456 187613658 855779378 906780070 329056976 163403950 585024833 977790382 344546093 286436312 863814206 843610609 83031620 478564124 247093528 697832388 248889210 354682099 809625028 103423579 928125547 661893169 674756760 173910361 89699580 511038898 137570291 119245478 303153657 726779854 777347303 911226887 844951489 287424931 381269539 288947868 556917157 67694534 664019562 58626998 837604742 925016405 437696809 983517272 142789961 85155831 247529714 627580576 390689867 233430456 38033413 68231729 782430287 298968247 572628016 508389778 480408772 39189194 439724254 63443503 707434933 172023011 178207461 701575882 168750165 7216763 470715077 233960194 859456186 877049618 286313712 554975059 342180832 934711307 477874117 359862051 924837359 7835521 927339004 654032361 701974670 743157033 126169505 419487420 260643056 957859215 463450770 863317494 935149457 93172366 557502207 335299462 545643278 213333975 412589118 45853218 56145596 297543845 212786324 624737793 320359547 82409031 412145167 167280002 781174526 619847147 301106725 190576140 273573858 716511134 888046220 147318841 725990121 206492738 265638719 311796908 314411243 536661505 354484364 496515869 567766127 466748167 217179498 169599929 515769301 867994345 916077 647868612 804852808 232146552 794718699 517286060 385215711 184873873 39722471 475190850 679354442 210359879 423018763 305250212 991084886 119412691 156603068 872365219 251608087 529788732 590129771 265770402 554027811 566500746 50453513 559869760 530512954 616053226 724981885 839387078 338147103 280787272 346454951 565680052 160726513 867998566 656909718 562906019 266248508 542914742 156595924 388485293 457492618 926903973 543856662 345406517 433277282 860490423 503549152 471196813 570493210 389577805 840018160 726563673 529168899 16857880 11691341 107323009 576549124 851559745 538909506 697164894 772493053 431561927 158518857 450673317 64429387 770031635 668078145 963751883 835796851 623315745 290390666 550462833 133944522 940446224 13193082 656671842