5000 46
774180968 527471084 618996255 474538642 507027578 464626638 113436943 748596638 156587214 386972220 770097021 418414369 325896121 807801355 675221008 185053459 147138159 397531544 390913728 694039389 553811426 368624512 953701013 159756195 73244563 701756337 488599848 84867160 673723403 776021109 470681555 737775503 304078579 248504863 576529239 561991557 701247933 359300178 519693035 923958249 548698373 456856079 624805514 381115354 981988677 698783936 833024210 915521256 18227705 715210472 338216635 446816829 12598377 807369400 676962139 565579748 411993029 179452340 862850137 836690297 344316347 52044621 520732993 436236170 71571251 432801413 251530674 75500854 42495159 629284345 911327566 994273924 215283585 510718786 72408477 654014546 546003720 806476569 715583733 427920833 316912090 769738920 203091220 335894165 693355002 53511861 471187426 641770310 718960026 298693507 940706542 612049690 624960491 525368613 140908931 420745751 820378692 9887734 135744936 678235047 984383141 788951038 634325862 885702876 769352710 608336373 671122228 293471415 695123026 100932259 88565552 595543540 923823371 338351683 709485625 437016933 372606300 816808864 340226369 931450675 956809922 178224665 558583990 535689197 802723811 640144980 489878596 527679933 574721213 819867245 966343165 869927918 323946297 114653568 911943463 17352259 753667989 913865048 227002509 216231675 8453014 655708102 789733036 548019246 31164966 267085104 327714581 621535035 453087132 732642975 125833403 952129014 402364246 548387790 95873508 154712788 643923746 516232699 460841027 15065399 95655242 957913531 942613764 578610003 937970088 833065976 61280103 365778784 428109372 342561346 196159953 259710968 766972332 875191101 521687449 825460008 726347638 353255 912674610 601883164 727591266 617835439 290424641 791278190 189155676 524326927 767226706 108888626 85819694 873569237 878303144 673650512 543667918 189807947 657060143 544689998 382049816 527140188 832771084 714407478 878011709 315968206 829921447 202249256 544261542 880256415 712612012 750878287 154093051 833134735 530013455 705876198 724451548 877869499 182283386 593854665 565947723 762335525 142447842 586606075 41755015 59285850 848735551 896797303 917228866 530593136 820975488 892025195 932738030 63163878 971338905 290543487 610408685 817646751 216697623 374999061 583184791 807131682 100477006 873353807 490480 835525978 728056159 76582840 59123827 277238983 260216036 676718081 715776937 469951761 596150104 283165705 759267347 39377746 874752792 281473660 107474968 368749099 214978683 808022931 679248624 331765448 993342032 209048642 813083070 947326403 739833482 644699322 404357277 331506897 569867237 79186850 201099769 978963393 889114013 644439898 778865177 684435641 58384357 500812821 687338464 356150114 510671093 389777774 100431950 623891239 291928829 641001374 30939023 214766759 330180957 245306455 194635866 89375814 968066428 917162204 784540817 771083048 347773826 844744039 788170076 280791055 451437603 829778716 114650953 659261611 835453205 727552707 510814301 969806053 696786376 33399462 850887658 191649295 290284613 972653616 102873765 465602349 931238148 278486204 592197078 827054447 115143414 900658956 308822278 235472234 330063870 891769540 64147172 940236242 63382176 479966372 612724711 174297465 963984521 469125153 14669494 577449727 236896943 217393868 654445204 597607466 693075915 849306857 79713989 439014675 792374580 245049724 365521719 817037967 802444464 324261181 603920383 949660978 144999824 168918894 480296049 677598799 462723153 144870813 328017611 513386933 894765785 130875283 414612257 277442607 156540941 651380855 105877514 989595777 847667111 57149559 859739682 811037572 527096219 355120337 763739275 120614232 49724829 473378824 429084012 105115574 914039128 487382705 648638880 328914343 275986470 38984098 876190043 535173053 19276641 302146915 783987069 109187603 776412434 992965878 121038797 745471149 333014446 608431416 797705066 776409820 164270611 614500162 441529417 342308916 818124135 496202004 485858099 795215880 630973828 452387170 432560999 266565067 419902190 676469746 842627045 976053237 915939595 791817805 580010753 601627462 10463 67725253 93200008 940759137 167976026 624625174 234545876 555120127 181928491 888188637 452512254 837294532 305172673 350340041 402594096 738327307 769943049 442915564 869317003 360083011 289716124 631932008 866051850 201361102 328984525 111311994 875505276 355110057 383054024 157499501 515369825 48128951 879182375 673258952 882119908 61996198 912813590 615388219 434294446 775575641 509270415 929467009 22993141 509113890 229650702 116481357 192198931 826349783 692901252 708234626 105792215 92204254 744479015 35477703 612049439 937594095 71116625 926498510 19758282 608805324 960699233 330969910 2207881 797199158 496268706 28430997 86202316 175574573 215297990 282544182 972235313 263569695 504963074 799926219 894649236 325892514 529908762 776723658 393541914 366691201 205143179 931412219 340369491 517111298 527833116 131556313 398944069 442261487 759389629 224915246 92809706 419037150 187411317 535648044 836310708 381704492 129109378 180518404 880084158 868786511 528922322 475239280 282221937 907832474 291859668 327066446 38009565 963051473 635757491 783956732 664042105 597659244 44768798 682677823 162018550 751426655 77029630 465836496 382982176 396147165 410504516 574672939 80411980 769375761 970457014 660186466 725118581 940107736 185397628 980305610 364609142 773096424 403053671 554887570 704401572 950380074 793347843 771203347 614727694 411841085 72697649 823216329 519539979 204482925 749476749 740686303 24855610 14943606 618004502 936388035 237395659 38748026 935131599 298091275 886040067 268532180 802462548 691127329 686238585 169903714 14271830 51544569 187296072 660455548 33968266 870941845 898534744 345750457 232947683 904490391 618613822 878484763 761375574 407362044 420793385 224636739 459789861 101166744 71605677 301933503 329571370 926632903 722409658 713080016 624725150 446177200 556791707 346607551 512858022 440639594 373617673 85566855 727352240 104321 689526358 975502834 799857790 656476405 114659690 707357529 224292317 718719054 956543000 750023998 898043066 548262230 112968487 11977734 308216896 596977531 629205970 562361791 764934704 360109661 233894712 767195373 658251111 215138890 529050975 824194418 138944700 51079675 68347933 956035694 110735177 460932478 955191343 116513092 714620650 284888917 345771974 56287499 63264228 103806959 885524184 943874442 499175417 422698054 807874019 231059018 409224992 253820026 775381806 215795491 851180000 973443483 652106694 566259568 451312886 339872876 784483407 728495014 451779835 291319461 480564192 189314207 257084692 252730312 103980303 523818200 354264696 23413502 581092252 842537399 577293253 593345154 452507468 595146093 853383515 930054816 537860611 255248539 324963307 790408841 9368941 912997242 734265191 114185486 993271328 260508762 187884728 897708509 490483602 695430890 335159924 816761537 118878309 600190535 263487591 527009654 70710664 114496025 128875924 249766182 197155480 676700594 489930189 8132539 85452151 224019034 346000886 114752284 689361308 431870194 514195532 313397926 909345396 53380019 709739711 276092343 778766163 467404387 440152513 772376657 402636076 58896253 270897086 741436194 192204547 845515985 250887032 736875334 839863373 357293587 60626995 117508586 115802216 277435998 250579281 466935249 978498584 146554294 281460022 408673917 183636626 496423858 419520610 514109551 211079278 813756652 272290021 652852261 267807539 625036239 416002283 148827156 437961675 85054563 900436898 684968116 439387594 562719239 139050037 719148533 686513943 417308634 557616455 958643027 787599609 797791747 600096887 209298064 656065390 228581123 89630032 695420502 372498999 269990143 54718807 358664634 364980645 346905974 970311451 574508415 219312379 947150583 313916824 507856182 620646582 388889387 444314604 116171040 135126557 177874775 233225044 883348814 986187507 485379278 210257743 784221406 878014860 831753608 438456880 938061798 883875434 227772780 25935270 176265340 817844744 867816420 345142643 921643383 628848381 15289198 341833589 265539897 779097790 811397641 100369583 61905313 480907516 208730989 852107684 522527585 53395485 467847905 325869608 671464817 219061181 130520005 300658267 206455281 550124730 470463212 867638801 525545191 157923929 675785556 146108357 341537887 868114447 450711486 329601149 715947307 638074181 709968818 732818421 254617984 256663841 748149089 980949162 634119703 149143856 243700299 896602554 177256574 28798426 735796359 901533690 642100883 190218976 905552771 637583921 436095673 930334163 105018800 741741059 257618874 30013699 44966968 74907145 313283301 1753313 714187692 884160441 547119921 952360067 249024816 242255367 436211978 728705145 178644032 987167587 593311649 968069440 664490166 850348618 980132454 757434833 182648428 575448079 228285720 869655762 245992271 375241570 77438341 242038228 275239610 702642417 553743321 640019653 464612732 331808777 715666816 689904941 636139788 354195809 491414742 662004955 903749087 209559545 266768447 804376583 321267150 203391410 193543999 670287822 736686818 496438685 989595148 88516511 442776260 722756516 412222442 362367095 351179232 409243165 634278086 648993623 227226729 202098524 496318887 440361714 520950820 632986364 394713735 651082892 693166091 920030027 975268100 539693502 13664259 614709644 281175508 41951218 218561396 980059491 586475052 116673931 230466398 204607147 395724742 595306143 76226880 966003895 723595445 715306325 170656551 513664100 645183157 157869643 533565264 716292197 86516183 653767205 135709472 522471913 691659066 286162879 685792558 84612170 260150987 666948514 235107318 86347014 854711207 512042950 729690404 393238184 835576347 123365900 322764961 592582691 390074774 765313435 40362615 436559298 405796230 42817559 107630233 352251128 587626675 167724332 620284661 650278779 461922528 721028969 693328735 305325674 169908874 87549047 361769611 813320930 422982140 628012710 1906964 467506539 701927589 9157900 559129759 242773025 878844630 522568948 194651890 9842734 408135698 623465297 914400224 885773049 885300234 54009195 482601630 172806776 333492858 91496661 341228688 779921428 211594692 456798113 948195961 464859877 271815477 734190940 640461284 741744417 819672029 848846029 184738655 92861129 195051770 609701629 567882064 40429152 297165730 958792558 856007498 287179071 161119380 835948946 765911792 178085219 635374088 223966278 488820478 938513774 347070984 395734464 768748512 271308059 175993156 962376025 118155030 666945265 438249302 808965930 960836980 765383430 772413956 578843347 110647312 88182576 87850511 25575956 19646273 174227258 367772319 293832305 556465685 930094411 680687256 142030087 918514658 184007402 688961439 882605856 427962573 736198484 684427862 467664179 579412446 193632097 95789347 680660963 951845227 676930893 207283744 937712922 65130147 216407971 434982547 300389969 583857134 878338322 338439726 235309972 698078902 720027054 68714304 100275017 981313974 401924182 332547614 670543540 195445325 435947504 259898193 428604084 973735697 350829233 462055148 744515738 442881290 409245059 570971946 142264471 871619632 310286041 377592271 484725983 338726161 147182067 811208153 400132927 851350436 685228801 334313858 907002213 844857209 500947254 35475449 235915707 477154959 590083884 549127651 388821768 697607862 625898919 642065585 265134131 325670977 478286388 555491729 462228098 374882396 870358543 968066659 732541813 806126443 362426265 489248087 342259201 663897038 207181860 168036431 16930716 417866248 809526293 718008614 901840030 166753311 275254592 898955565 834062376 680287041 582567950 239513051 429209897 744746062 789772081 494786084 586761062 589028118 739689034 442288804 981276636 767883035 201204640 437473612 637631102 684956649 885453969 793980018 392499701 122111359 47902071 461801189 612603960 432883522 624978016 876998858 251177214 302159049 494219014 747256951 535043395 586704045 10455895 469172043 439422224 520270070 507849122 702586030 274271674 967949825 136386203 727555423 344909491 377864002 412696436 211626375 826134743 761063614 715850733 953445537 304665169 786742334 83227768 79727988 106221540 781477511 900283870 436045964 55141660 573872953 966019951 469042411 305536540 972013564 779291452 251080564 346277890 376446087 628568992 657849957 507995709 398804884 788485749 755917666 515821663 825859205 354094312 372789173 753277002 86985194 853470236 863081063 232968686 365098983 244503584 355935680 976090136 335486376 799530631 783260107 806291662 452301062 745599915 2571264 517840695 542442392 369228272 387196266 333828832 377010555 633885826 980552663 478304561 930490975 4269392 993010677 720004795 88679847 696121526 254941333 223152695 102856649 669912022 118821065 512574896 323376171 962216210 992879576 184791797 914624190 457246221 563274885 278118451 615723926 33148722 420713901 574269043 727733113 485134311 570936726 487253169 871218097 923990012 797585030 344400376 329298658 814226233 414529118 293567646 155245502 436620688 544785955 456259186 241128993 733195668 161372463 850614168 681838272 621094696 117735189 242964726 529042550 658667770 76517044 204141224 661312172 323031536 815658015 166891777 309968453 165468778 612665298 58869260 812334036 445902635 290413104 786677601 512816623 686744013 585101962 548101880 940688584 230819439 979678515 547116116 139690230 973012649 413475402 67301834 609488216 626863876 495477302 860020040 384250114 66425458 754058894 733832671 455245823 144056189 668009222 915625434 556806197 422691395 892125456 380923868 682223864 113963180 133372143 723165122 801695214 180823953 395575133 215195334 422782400 502221691 628283547 454561586 272021624 323057272 104340647 458390944 219084236 153491216 796078797 433613874 197778370 791358077 618548251 691969801 308101505 159547706 649873968 646986487 218652001 936385218 734383207 359058748 334508839 399100329 103613217 12663298 449708191 898988707 678306764 506758075 354827846 159909533 59354470 57688823 98381463 929438374 983026567 191415592 665190303 102636611 900913173 722296085 301064734 831534731 404844302 942741563 319776658 764648631 940857300 263943609 391039172 937430268 788311694 184251968 560101284 54102452 951333513 965367536 329896308 970090445 741634568 644405256 314753511 878941173 879487408 203535209 8428678 844725280 790186176 782811185 350440676 7842923 564365789 208657703 854128837 25135725 772036558 201978972 397601446 591900747 300577962 641813883 497935005 78965017 295301186 447041294 109255878 827652885 517073789 931740158 854919975 317482393 436818849 769115471 281362878 926094965 742362449 44557821 106623683 433340519 115071315 415817901 530742741 927496935 343916513 335064467 771612403 456784560 812294177 53565352 169531803 241789542 166720222 483239223 704520114 624568215 533360377 157772374 340373260 966604520 743346549 240160131 851391890 656269643 457370071 378380525 343969915 614688085 3868640 275938429 891742045 241768951 950752471 413528339 711488425 562605973 567519450 376313343 685385025 170718745 109149413 944166506 164183477 913325946 369660670 726150885 808504776 541035851 928849847 602859635 147726710 827268255 832046355 80377430 11965000 30794552 652992164 986474531 757534504 600761080 699388078 460063630 370603846 996041900 29750669 373013127 617916457 906314019 966311148 412331040 432342755 368419519 512402065 46763805 363115305 321752294 571359487 750651785 507983746 71852486 140571867 912165062 598444034 584558173 998269976 134238388 325257346 775144496 860983756 901475059 329945873 589407486 825357448 980375300 919250028 231764591 849319464 989088928 138047388 369936585 474614802 251671442 720195658 919294543 560039410 312793348 244513981 805981424 113044501 241538873 769843533 690303971 758759301 634995701 844309858 790794644 460575852 83372210 210991396 61856067 904748190 63688330 488781043 622321980 614779506 523858310 557594615 414151339 867601748 28471609 26387960 395799810 120145506 653669870 750114175 437914530 879939503 100392539 84425903 373296645 230475829 690683120 387055559 532799751 93675238 512618993 638923356 834743296 454767270 839994028 726693862 555762748 571148568 984159913 747348811 985059697 101875471 389086866 876829323 653805675 368217395 943795696 512232143 664908580 525569521 300406907 235367661 709231243 651841214 602617420 960665286 624884172 935991776 562039652 319676015 657225942 969861615 128688682 683929945 279127887 262408319 798530731 535672305 338257372 314144143 88350119 709188889 395158073 829645815 77674996 694008985 197923259 85734236 332490821 30475183 863446808 268371642 388412197 145479829 552679980 654346615 251647359 94729701 286773891 678175195 613984484 581415623 961511688 987663643 51374185 56779643 400393974 268853144 465009940 329737554 460213009 215883111 572639037 636852058 164081286 545960930 824820041 514926638 962022206 509772307 958563740 67616249 803693177 419300549 218341266 632062187 272452756 361459020 666783655 43405042 286506735 342141679 683372704 319556195 548898250 150845217 575177066 610248906 53802475 898171341 497162113 442860346 793764761 283118796 177558113 202837803 43728087 97316666 579891281 115515994 84293064 280460020 512350304 950595365 283798676 597807571 681916229 845777516 592422379 504824167 580108966 216065361 634713551 771550491 311782030 412805354 961748688 509843297 724078150 381805113 941187437 80318016 83151366 553027257 947958935 407320546 237544485 866649182 316760042 465048187 997367074 10471637 463292050 60675145 631718695 169976438 431112600 668118572 167480788 484364072 945014925 366326256 270661699 518587592 812574173 640685799 8644155 68013213 574426281 32479608 772602894 792810049 412457545 978313065 374120253 624167913 517942592 318147548 390483398 453473119 745321539 198562665 6220961 143525668 441354611 858677574 778649921 466898643 293332455 294323553 617031781 862652498 522095716 453256575 319148248 672321511 51820552 138083004 784829953 697425377 459240077 638562972 618299059 79599357 113231258 227453323 433770142 329487169 884678195 791599154 339650223 941192092 589026294 772272788 270118945 244283923 535711424 867025572 592986724 223827943 807779466 827192708 297345331 798161565 155372092 278371205 936517778 202137621 284457257 361668353 531197388 759717828 563078046 905095056 322907890 330988028 6943574 763482918 89749220 969668048 507791118 117959454 670200044 795461067 737261208 496247166 567871475 779841400 24621587 401129219 703494855 159478910 77910089 567045693 234599264 484973868 920199859 669158275 803118509 544505666 200438854 585931785 982409915 693024649 423751025 315570979 304362540 358972653 196226368 429985415 635807141 901591264 280818839 264189706 439412820 622190928 74300390 762199612 574098575 536828886 557994821 96697008 284489406 255652650 748341431 242659294 943954077 766932387 507012346 218328231 506505881 3883758 333088315 737887110 590159393 793991099 55188250 791006931 913820429 428340540 676514648 229008108 335010038 44695368 593747285 586499814 154763277 50066550 193107013 616238806 995154408 583973491 171370963 182207961 941932773 598789985 290695450 29520712 596193936 334837149 556048488 138957888 894757973 899585595 117215204 959107405 729169496 526293616 904909877 81804611 305571621 564154303 454338651 79658403 616892087 552416917 641960648 483855508 198375405 372519543 429720540 807018794 526354408 170368426 831806411 261224546 551976337 28325198 348598612 635061763 199296776 357831755 232682183 177554197 215775292 350358001 513551586 208492320 692259988 734598835 854104124 750137092 597737837 790342061 241492003 283797002 345780142 19132598 515640430 26634070 992852078 172637782 333458186 588066791 545532143 84381261 755716505 137184246 125013253 869049673 784989473 915463535 731435883 643317742 940808600 868424836 967205142 425143416 506599850 116265570 279161439 872067515 62131496 740944222 49656455 633983313 248934607 457341511 836690710 22744251 283782700 219924186 365226910 406046279 990312286 320882808 663239924 970836201 392485265 347585998 193114268 974485740 662510410 905905521 223513283 349599155 220646343 844468994 915139421 471878240 637587316 454903341 537695265 488807206 35824222 387514829 195375762 877358167 586654447 525091767 620847278 279212301 719319040 635075743 509322502 762756805 288627875 474822887 665643117 758950713 865983454 904668370 113931691 86604699 890733091 67233467 101063721 335402906 265115682 354686727 227014629 162784897 966787768 140209194 239216885 626329262 67696338 602743122 935818309 657063799 139234813 913461448 640603721 651362407 762347171 806159169 923736671 635895594 278076001 164359522 302340568 607248373 473856299 593534235 104097507 143733718 981346319 891972002 261426499 184719921 674119742 983320583 626839777 7526386 711573177 104440706 118994695 703387036 259943712 504146512 340017175 637473768 680404812 783321725 357200991 950602488 906951644 581066033 645696587 887309991 591692029 712867213 425196948 508480846 53951290 296598465 530729749 743346793 144730672 348141647 502387608 830877770 191776373 52713374 411574403 143132275 544909646 257898204 262264989 926463963 401840705 491146640 233988455 217891772 74398766 119890256 241465184 503395409 919736813 813670282 262037922 409515925 200647217 203094507 831849128 956825948 929237583 604001174 415988168 495958713 398760779 993698956 458991273 418565306 552472043 116962785 491880648 764609855 888219677 974069695 844158159 488461209 240140417 179899946 542297697 514435427 285259206 718461700 774121414 726755228 123709464 608890261 878097840 191627190 526620288 367374784 452142964 356474394 897310265 295895718 213040528 255012930 561878654 173663289 97024548 713612419 417553904 441848052 203723034 749249381 88582522 522693555 450437550 404514835 275917906 15950242 386859902 661758515 432848664 321943380 86777534 774477572 496164442 891411424 416128429 656343533 191306162 914434025 639057224 220117455 476597234 790740811 193747274 10573200 411938592 67544538 599669579 15150987 768975351 568934420 195923724 514098456 386484916 621459081 515623373 16894768 132453432 525028862 803440286 599183778 774239765 156655009 113715711 890634225 456259379 953725765 161748906 204703782 103730732 561597082 548868629 55017968 235490484 749285327 318267482 6399919 586614525 129015881 84060121 608627708 556300845 215673235 503615981 907306537 363000079 131891289 873739296 315379658 441521808 400224940 990974956 383992845 282740467 669008158 831720602 100655552 648647598 162035832 318307583 634774696 657530741 247265324 483719587 129712352 362441768 949153193 11863765 735822031 46983073 80721732 454872444 180651515 282249062 12874469 268430082 317200150 815447275 801160945 494980842 386000765 777064545 804209271 952205788 564342518 380669697 926906253 409622791 66760064 987394131 437747733 307016321 595986317 19925582 964717880 591768055 324197543 576703356 526384799 149403501 953739732 737098084 562534585 852720942 248873463 56596338 301701214 402100608 366150378 397239307 739067056 984632049 288537643 706840287 125854252 613120741 242425332 338305984 22560029 352614060 351693551 933295477 350730367 351002633 80935143 48720819 8017019 174894486 279739908 662793312 815571289 886450197 90425285 294599286 902890634 936840521 584399634 13954201 432994489 761859554 591666095 749338249 179658211 488155771 725066860 309876175 959922725 465027485 999726664 600640300 386475921 816510984 348795044 746882708 370870902 596981443 708159378 815328196 219978552 794052565 307934216 82732750 153755299 144691261 137273169 759168414 703942537 360348338 724543301 145791008 176732891 731392210 404954684 55632873 454089686 970872575 568038113 36116930 778317544 375035719 239858243 335051497 778926532 104121287 385276804 881730500 971756644 671896736 935481767 643499860 882961274 523864750 293609451 75793403 437312738 397028514 855321106 537166834 614039004 650115640 235565275 24388153 964577254 565079161 210272898 328722901 127102711 292661388 815973904 982735120 142285620 444772290 94017506 297911011 781000357 730953505 161899773 701585668 585098856 672852792 282411984 161667610 208339015 857607046 674280324 187785981 56330094 170384975 26930766 67590574 651156849 287550121 361717131 623542667 186197732 439201690 668694686 692086091 56644934 364347878 808204314 959786059 902119873 649529196 625752177 90990411 44365173 706325377 489183130 424247719 775126542 604457639 597353780 978290982 76581395 441956521 831282603 771936641 266516269 51884220 864396978 796751220 301208281 122944478 638365800 416489310 846453180 6965728 752932169 436246858 824910556 964702174 812060141 642775181 137247677 650762210 477780297 668184297 63892550 739967583 142002380 776895958 373587654 728681605 591070679 119854490 363900346 999700319 42925048 837931921 545646387 897758352 805359028 740749811 158261231 835106880 386870355 760532548 116857116 130462031 780554597 133794106 152627034 628858911 566397575 205884810 334102672 11137736 341656406 852584124 182831863 806762632 313118349 145149639 511544241 188958239 957889098 307346037 50821578 211129092 248494027 839744504 315275411 279834195 744223255 5635462 731297600 519114122 712533019 247201591 888170160 744151491 464135874 635842618 57876002 747934781 713235209 932090167 812999939 422939123 878031561 98905218 778189972 98795462 323179875 14346613 387908000 861208851 696565263 958341688 172815744 581041227 883412744 591841646 727497763 163600471 434386804 292931745 277136487 389439955 666453191 412888882 330984879 975843033 849434622 628344539 287657394 92350842 489095906 309486043 265045267 392166959 14014442 894353359 417512203 875331711 712876928 287353815 419380283 978916188 918241478 365334581 19075723 646998217 368061132 840017231 791062029 394314583 889350102 891305402 389352209 125658558 743774035 546851274 957636999 890099962 846321460 949678453 485738122 873572280 739940692 114354360 295007925 794796363 86624589 33584410 95054800 98648141 830185278 852041048 337740356 123538920 434462085 744779973 955445116 744918311 460781663 1910533 107562783 624576953 915722822 195676593 883657047 798582545 38300542 520434511 529743908 444030955 448186754 894988887 676992803 193602037 971459621 266555558 636277552 214733543 511166938 542209909 115933545 337965130 130696025 60135660 344253638 290243133 210624930 28150402 243555610 930328316 63690542 427336271 860819345 482791549 479219189 80007407 405662491 879955388 46784976 324641744 251589583 743977316 402451805 56117776 251746220 847117402 399191942 931844288 939469593 730229655 297646648 774402296 897160195 480316068 288070904 194318478 826691981 503456842 153317393 371788794 301013471 742435886 61528510 723500346 593493675 269201976 348370206 98974204 766830068 226311834 944102606 992886266 980719136 912665250 71400806 539934266 615313355 931154412 711513189 937654289 268290290 152578505 227208735 809935608 772491738 832745719 282501404 898687888 714660855 735894787 540404086 875654472 198661766 554024020 247683839 309192802 620822188 789594012 423058479 126875194 383465869 520029215 16652241 993059694 260099689 149534988 278865427 254307424 982298534 913228409 135554534 423254781 615198219 272933633 554687519 672882606 78813326 104456666 129314492 431929843 670887881 406976217 6415575 514074004 681764616 106704997 622241398 298215603 515753125 267812569 868033089 487321387 67510141 587735233 138233749 855232022 225365774 650912111 372929991 926652965 802711168 552480271 820427077 117336104 898846189 139055044 461619273 136277926 767497615 802557670 942864922 183011419 331595942 124077123 155088755 23981717 924273059 656586727 90842360 229266409 277338541 30229134 243190554 779051587 646083609 6270229 646692859 692399422 632751905 824053479 419489480 772740094 944895756 539088521 193349739 640345972 58536327 209429394 978501764 718650985 722409891 854500967 732592961 245979965 748350006 368617151 130599664 872634898 418896083 73823383 758062573 794309326 956528877 852113163 597103834 872238315 363319808 708827043 733874041 17126903 995513017 216723128 848302091 563408629 816909736 379833124 576399034 242081611 823536307 906322600 607584151 645746764 421795100 559535946 563276218 280542155 952557783 414180824 167041223 475316157 44228696 784793492 507168051 359906206 722028333 780769368 918078404 935642363 839609206 565886863 574613618 234358055 610853213 889855065 3413884 416052826 422571250 11501112 463283882 852787661 906847423 731301655 996712038 632971474 482823012 701080515 174885881 332163915 598916836 827461644 657355024 771767080 164895061 533528539 565695749 218579064 883518935 127801616 601312508 653728147 818587001 18162458 781132012 532849156 426519735 682049328 642845387 81628775 431416763 542865677 560880478 19319070 697200030 868278133 802836369 168660301 953298429 389575613 269951542 511157810 704023635 424626710 153046884 247036882 64727613 785716194 71479711 172780574 794769455 36604658 895138337 555569129 356584504 753082395 723219100 93081572 84834737 688124470 683480851 437642817 995728534 525353151 230754286 137398858 350518334 545292159 716020631 777439776 899497573 579992343 939712573 441746447 115926982 222958104 710576788 845869700 929328518 526032750 926468872 571090089 899487297 352458587 730531832 709526003 987913986 518235886 251701636 243732228 376167493 638751216 431048401 137726009 672256445 42613321 636498865 139300069 45046419 928211561 909414851 436010380 193809815 903814755 654708811 897528480 367507024 565751349 519187704 996012008 717061949 88092122 33502491 73958214 453777152 982398317 493154780 937048435 433393290 561447154 125817305 270516314 3020859 538097543 452517583 355125469 160900570 694438200 234106928 694787664 89454587 906409509 350014166 717709288 972162941 419674027 827748590 338780251 296216797 223983014 569398249 575880801 271055167 632144615 135146278 388158820 67692641 582074086 48243591 990520496 164121761 550372761 238869283 680791758 392599168 549188184 615720729 511963397 687149971 229870687 988096042 496684413 665810672 310233443 103400494 192323097 982512999 653988752 917125498 697938135 6667905 588056183 775683591 56945885 325678037 237703428 139384896 648604484 913770402 940751926 962880594 193092282 842618448 187120749 300128400 479826620 631884860 87160606 421756858 103618554 310590132 654660842 36891776 966617831 197943805 563782773 842778661 972671699 380582184 538794158 521876430 122985284 9469412 427327581 150185842 920113756 753986446 255462564 60765996 654439326 915750423 872440885 905741955 26294309 541299739 994488604 704770538 772557103 523908779 232864411 32899095 33630161 713011640 818434004 955722072 658021209 747389060 850750542 989169263 463046331 259172054 534141370 664987809 135080031 356697446 915737010 912479925 633160364 421150226 964279939 630538797 421016414 849086447 980430458 182765936 612986372 323112526 779416462 589120366 238596004 814634425 635973026 332162804 765844417 435529914 981690913 164590948 159069532 79028531 556760745 783410103 631486324 559884787 407747797 1617883 933329425 457802044 498494530 441972033 131981854 696577952 436584206 638492911 421260498 604675089 268761152 969242919 395789760 970072145 178015934 575379319 517209948 600794816 536463255 37795296 661915169 251284480 865875823 419552523 781445342 811518701 588066158 182437801 423913894 333610217 777356469 776809539 78101860 979738787 73540586 400991673 458713680 967314916 424993914 862199650 748793167 956706246 585488387 835715147 238399607 260213208 703809818 587968951 627015740 268653092 315481572 595206197 603117845 725990469 333250583 495655575 924999613 650305360 704304211 258374649 973367449 255221653 572492048 885569408 665807489 37352804 202810696 900340113 846903371 749780611 357690063 752745135 41245574 988074633 235622644 457070179 547056759 993532124 74906325 839306227 646104631 196043731 662102893 936917097 110956916 481714698 343874334 602801809 732484629 305945292 231246338 12163299 658717885 148252171 721264835 40945578 409214866 289777796 842838742 821557401 918237787 833737372 54894543 340579264 597739608 178482591 280488595 92862400 949170788 644599834 24801282 31386454 861986168 156272790 858500739 366343334 93753227 448413903 643064828 236159283 48065326 615155663 552519287 249178797 198665659 856778634 487101948 851759767 558889198 329999688 465745751 172951826 666466406 594062798 369318235 512607654 823359573 81987156 318946156 103715135 339196809 958376220 323020455 634358809 981253864 744040024 375945793 27724290 808131432 153557082 530962908 130542241 189377738 822147276 102319401 407236996 517210120 868707987 981462760 763725545 133091286 850131175 405498875 752736286 347742552 210775344 439331848 796549406 454403616 570983335 317709365 382457254 188116048 350843656 687901896 13205666 427196592 570710915 92325344 254839799 346976684 698906496 661675630 926777713 136673454 503295251 237043140 109554761 953118573 346858997 161074514 569906134 474774328 985024753 515585283 710756331 278323705 229074117 687337723 288558902 313773830 446120105 325063497 857015246 654468044 988980862 540080310 4902596 763985370 678844219 278509720 934661640 702199181 703724425 146947733 317516932 748367037 815986319 355136295 350634816 287337959 236111755 222487449 972115682 270519237 432591555 251417490 278515256 341221862 845181023 366954616 96070446 320757932 508149841 9880050 819010441 700066463 567059264 465720652 467300842 92854941 271683375 817393925 831400507 933683961 140291590 316422109 314940616 656681234 300116386 749764236 153660412 873573857 953237927 210260773 322537205 784453097 464405657 767241130 669001901 145294697 8734761 632107326 537697696 685904651 444581607 680484822 963690247 262676382 977699830 687303441 583378167 447430161 462373090 579901615 980852896 252222277 458327672 681663626 785775225 363454093 3598700 797335908 518630803 7645697 479677306 630521714 513087724 497258055 901630966 651940617 542912487 922289281 725173206 920596575 495874399 838956975 36780580 668596618 729050765 584808940 795497809 438652801 485354522 484004129 555512711 838065941 131094217 111451039 309609325 682624202 85285044 968785903 259627405 804328743 223588347 197217559 281608223 57328924 866668127 859433379 727470000 375457517 453073382 694804209 279086932 158977105 269134886 984588245 79632434 590474401 771093347 516746949 939897937 775485310 41802069 447732090 906250474 702151624 583338566 268190072 888757894 233337964 914875771 954845175 758762095 598117061 156498656 871017049 729544285 282920073 720089293 422903357 189773730 667108732 928271441 106964379 846984102 382885021 731340615 642191601 386483877 278471439 596482150 536760082 697143039 540247841 818775617 633986899 654297705 345816042 608777181 908163511 902270135 2082596 935188501 450631364 998330483 687211894 27457877 420397030 535126484 685583740 959054871 278725962 236506660 45184125 850808765 915433903 43191627 3022516 59835390 468095786 754191811 979728704 50970926 541776253 370558861 624541960 87156606 791458075 590537113 246740093 650381544 884450772 671848913 832766152 752483249 57312552 542784042 445136756 939961661 317884671 771413999 508966332 179378722 584863165 21530193 49387551 436578696 561216697 733617425 699338726 65296590 852084771 674499285 881125933 253856613 363740925 821876030 1867174 929045822 797409086 75040963 67532832 188775208 656180644 694114819 601227240 527109814 53392255 823598676 821643931 843370879 741244785 916154993 412849004 534378266 259876760 401739538 42889805 135451144 253559360 384655780 481039450 576585882 949479963 120120467 223625164 279938189 720623302 557187008 177272310 44794414 521824223 666177940 273124028 868228418 105959324 494872148 89973555 198823868 434523536 585566603 581464055 146156930 985993217 830783102 740425551 547391336 63016608 669213033 287317240 198617948 199311887 473542274 291706544 964354857 181764935 649314605 50270187 440041684 31311427 657174512 967873488 999687377 894805142 564188343 82058998 904165979 596479739 662441678 596399114 647376374 956913896 903099919 403093570 70784680 666777321 410139847 789737986 327174638 229551056 374239100 22890926 208649345 844453649 568850222 640307675 424965429 624020766 279611268 752018270 800726912 349054973 47448324 937287157 383000427 238304463 576322729 614108392 195171949 54024397 182987788 465716339 328017520 51232483 954359101 102940162 151191942 191789089 488798858 602757988 939633132 50186585 382774030 347212650 24129862 55036300 690742170 245197562 437393419 936096883 476532200 496933034 565972320 731197190 581559745 577835813 65894322 923595645 557915887 547608499 153187294 399785534 752555306 495091097 816866732 259488813 232434385 874419959 502284065 711187882 842580426 779146019 245079042 302439009 574778626 129928459 143054685 652912830 567956567 989766911 521486904 203253591 159760822 332523476 268561980 351597835 139519342 888672886 577979411 382911138 922781497 184757735 710328092 945257431 888443741 300341982 684919767 50674907 542370323 650203576 238681366 235474185 35307250 526572252 981052605 683886762 298468449 237983530 227482067 433691630 30472627 563082695 21009370 152282933 316406543 426699739 871552622 559110053 692697240 696414287 223528560 840410821 773159364 133419466 944479979 297035753 610287218 46453851 722679430 972636190 951912737 599319534 135846310 89663774 209757363 61621177 477410971 708278460 642148513 745424490 893268878 371276007 882161192 894249655 407989455 262811995 741427623 96876989 482258610 204813619 504508285 580587560 770458605 946867698 405500549 224667818 535525454 461747039 829161204 135670824 315393577 716026810 274683950 986998259 110146965 390158300 577638306 563323969 372291895 814034971 741391721 55360796 466677455 719997915 548982743 673854130 556981277 843931244 246029456 209115622 93779814 543077224 325569866 417224362 8704591 924722556 749180294 985643484 294996485 336558637 486771773 663394074 414432087 85878727 64831991 265068986 809391944 931340344 390286052 653355094 292099879 295289555 236822186 72461505 610479961 939536913 516747636 428775769 983447849 45554014 831442522 287583171 955559929 378872601 160384578 717571488 477205068 450669219 862144916 770023070 135866064 948246591 708369993 715621187 554217596 49663232 338470369 615564230 381026789 135116776 567416245 436774600 105768731 301151480 769451403 388627720 88500 843753455 508653766 175234807 874779368 169990798 809660222 560137293 501971311 478906150 34542579 912220210 819631309 346382331 954776721 94465043 892262022 274351882 95567533 475579922 965398293 272387888 359656536 358913363 849255603 269013481 180535330 8597055 319652666 231950132 85952490 244789148 235790587 899705123 996849980 343354390 461289594 661161605 4143538 268902030 451092697 555964455 34486567 69429579 516814845 42437716 455909205 755969136 386460348 599569525 655967323 972901132 618558735 512279091 371838968 497936556 501274415 126040341 93138593 791420173 662762117 890982374 355098606 166086884 787822825 778166579 796140464 276435409 194515457 173686135 250905217 747520462 479489899 331319237 75956816 325620844 96952767 610285398 109667904 518860431 662807977 333257308 263652573 920763737 722860394 421601741 496396644 875305190 514174748 478961538 167990394 725250761 678522887 920496037 747711601 437423653 584292278 480878370 456510310 611811433 997083943 742756691 683248811 67367981 524053223 430887956 433628221 627204148 771594092 274505600 820889647 924132647 220199301 254569070 153551905 92822068 370806128 784360683 498594146 248015360 714937000 26798790 256746617 36095025 891968946 638869077 156926791 764293269 851500822 525334035 968106417 694500714 433200845 132952883 397922121 138298282 510007142 533197312 784370348 970206407 311444121 544569276 951983197 40429071 442217330 737008727 925530787 418742342 479354788 302176728 458363145 709935158 513841234 677672063 786036557 75529247 191065693 13239785 349699240 170064076 484071793 391277573 985991382 13818379 912836519 892307111 11199262 583336888 888149437 578644471 26980600 20905403 701864087 513588628 329743926 412922485 96495528 569778401 269275869 820365859 808607125 582093901 422571078 694398269 492798647 10914954 791867519 338710725 704164384 937901551 508545627 501708434 616931988 552998881 779140544 52368570 571277473 605249173 450523262 520780168 618303806 982081346 399083237 742205890 638014935 117856045 45994863 586465713 6823777 570351267 968013459 581494744 384151640 463784509 670434950 345373775 241523880 704350694 883224439 629480371 960159357 606117052 338721299 841668611 844880270 312735470 542633334 826018287 485061831 312537135 229940846 78946002 904766394 765238423 687215968 571265700 85543286 232298519 242806270 567079065 307251500 781499136 213620960 858150462 743294566 270031814 657398196 178583935 931559791 460574937 55349789 778758537 311437451 240976065 123089612 324697319 638006148 368492355 392951474 158586156 678543113 610049132 211466233 879000380 377042515 274794242 401653323 495547188 793024367 75202686 116279412 662628928 244232214 793891346 759688888 572054325 110856105 937829193 487373139 851422330 630322206 565402308 492136046 218277896 596919625 813599170 56807379 692397798 478015303 382147969 278371299 125699495 657857510 341797302 153881206 960454269 448632884 318890084 75026185 558156563 342990831 988123967 713559466 492202612 920629622 443581735 867920008 957642961 75190595 962342158 331044661 340841753 405020322 255780472 464032190 531119894 772457568 653705671 477161077 630573545 347778453 738596993 709360263 675907655 422174254 257325509 69328149 241155729 927816578 792931141 145196505 870682603 13569736 491194119 84234365 489285717 248434477 593728411 169047638 469613957 604126788 562936631 289783058 984914116 931955804 347741681 615964082 661705381 317831824 329557945 509355087 316100121 61489688 191669886 194424161 539208765 273821848 447329944 747264295 993281121 587553247 532881552 526514288 803414959 111483442 632207953 836577134 730583410 803205809 935912265 770095450 147118837 5664510 898280304 984098603 962740658 541658798 890515328 192172314 185774213 373514217 564758223 697581497 376736001 105500372 915495830 68372926 344558147 83656143 180668269 343121684 361951756 913541205 911511277 858740488 260677820 678004184 301566788 775498880 495593938 773666469 474074668 572718989 107190961 178155159 596718645 459353525 903236762 433555562 695477756 368297669 720182425 592618406 342609890 319345386 757142806 290576861 229006366 146492551 333698386 63339136 668174395 693730905 789309973 308295803 836746283 77727066 304653981 770266283 935691968 316707424 307903748 771746905 203658140 527502062 830988405 658350999 800982225 912724146 681349838 65553860 50982401 314508944 583174357 900331425 715082857 346331397 718126352 302390385 314917749 764814938 707974153 931654705 548427581 436524480 824839566 198082713 647280178 487501909 447946281 578052875 115218282 787838629 473521155 185724044 482431395 245844696 516976569 473245799 545525174 385570396 811013560 197167595 855776137 318211744 599805025 876671774 207811759 407732724 427465843 810956438 702386381 877971365 815273796 350313568 546317222 706468618 18300043 741874977 659458454 982373695 262385873 188948578 851669593 72045618 148648373 295850806 66268717 771042981 606664763 990487643 661504807 859616494 746857340 212003960 857238583 924074276 389231308 211572145 635703057 184564502 314499025 816380543 288531536 176716463 9347441 3783088 217473644 315347136 476208519 118965907 795422851 362324607 187602278 607910012 118774995 407509505 34041675 561123682 582968146 815214710 568742817 904381165 698051877 919038698 485974958 909419804 331724702 153985770 389239192 86064909 728857543 328406644 705120943 105528352 48605555 130091355 843992080 637230784 58155378 454958725 384371702 981442562 74139240 843512610 641740109 253984082 475346785 9317086 828910351 152630699 769911514 959587164 392995000 298137394 95516419 41159526 686125413 587330209 727350022 283643663 760730102 262437849 230873844 706541243 159038598 546394976 305045633 746779514 635340713 836752671 532610404 76914404 567067436 581717246 146483730 854607457 580216126 601665895 917916290 840730754 49048602 976846957 764596814 402682651 549769954 23439003 870580285 254172324 802704495 521859786 440534994 145090588 804999537 619640021 193743751 548787105 855490773 145338233 85846429 979032418 222879373 389366987 871381792 29411169 837425266 941173335 767141711 912555034 196862733 413725918 566628521 167073812 569072183 50345283 12642820 877486217 455393977 544902440 448296687 67015918 426322199 798978898 283879589 403584451 31636245 667517229 377583420 33036248 229065456 249676946 721403072 30549561 498381675 123307465 998457412 890195385 637673884 219081755 920363549 545669431 38313549 590222236 976834687 352117336 906749386 545488717 710587498 963543488 219041188 94440706 680293261 628457541 935019429 702328232 973449894 329594100 343269864 425805834 425555768 809032071 240868664 564365994 171788877 175660616 918273874 377758804 855510324 496960956 473799109 1469709 502957919 58034826 740247720 812637568 564761448 433178915 701261901 396895886 282626584 442234487 746582014 564427316 875472015 956820329 51694658 481587673 247120162 784239255 680035801 427553618 482504967 860857044 90763730 404103658 772573424 661277902 587220502 345109106 22601816 925568976 974793975 42686149 606822639 244119800 521251473 904956947 933820809 130907707 887662415 788565221 100655954 538787630 470863170 475035248 517747634 600838479 580841198 440425788 156785637 474217219 276495030 754993319 120936209 60792605 172493693 748388518 809971222 643643689 725539751 920106698 16445380 32965915 213906596 417330754 680578458 724387691 435737184 252615798 493585710 580588118 732659095 606407545 479716487 716101625 490663814 758874426 311219570 220795906 513526590 137778495 144601634 559602195 603491910 241647459 405436584 646944013 982082912 117346379 608331624 485285078 989242543 683403354 554850940 174636282 715324232 916850034 987816436 53559592 585971022 522018693 481431436 190241307 748760813 892808328 281198231 892387362 922401074 937745851 456092178 724039805 614747144 337439196 672130506 422014407 728364151 751910704 122480883 193650288 52856354 337533340 48546545 177809111 712609577 876559883 852303053 59500512 967297006 2067880 11083403 627842882 993015257 827819221 97542868 336773902 608175350 562555239 219048136 520278852 922979495 108849251 953376498 569289712 287887080 477173955 929740527 935418234 83970018 840046454 770181669 109212842 462266182 323244155 722548067 126692681 306614595 670608698 316271168 17210062 892955895 353908528 985980878 702286065 516859920 52779433 859055286 926243170 694044570 317973973 499845967 42225596 937509879 527645423 401535477 11245549 803579904 967591193 512252488 892064174 720953443 78191097 862050601 719289832 936511697 863444872 905010860 430414321 295717213 552042748 531245570 828528091 214111789 738801949 122861682 202727176 343010545 58948031 141200626 405076563 457725325 400476821 894195103 940023717 565577958 759634091 511908585 381399503 637403822 165424804 249357340 569792667 397381169 254835115 812620626 248046574 427747381 762930687 599675549 799798403 872481950 167691384 134665362 983950666 888268602 408119444 703208232 716765461 823829235 249840837 413400968 843679579 565738715 38186330 790086875 235110850 359368810 326032251 385527452 119460225 271717144 139583473 791148815 340993095 677654142 402006732 894238474 518950706 993534473 55434420 215143664 714325789 985485760 49981243 836227816 163850508 910736227 893849670 110394828 303198553 871347721 724218283 635249342 918558484 973842132 933512168 910841350 501972822 413268393 338207921 674922735 894813693 225199698 34058023 793083667 213161295 489832842 715533183 766419601 556263670 824788254 655571637 483056468 326947016 465407137 27446313 524672894 885056695 882542208 117390378 461228429 895586019 817699155 539253234 295834402 374821051 962645761 102038513 456722564 422282458 602302101 345081611 292147695 928021863 726975106 572595041 462837539 86102617 701693347 459613540 917053573 121083831 880061795 211576397 770129157 772481893 952106515 29017805 951646349 673831669 170176736 335322315 826592926 693010675 994466411 222470132 894868910 905224822 577087992 879912084 874210653 671200596 405594302 17896654 762017172 647532816 639957433 264137510 320101094 544645089 992902382 466785288 42924159 514498457 981566393 905980040 661713325 406736681 573370261 70132554 817816691 205758898 271610271 850641916 724412731 167180873 960671301 988807297 326737766 128762215 424336984 809370154 87017437 997896855 913344540 209747568 403076543 191303351 99606931 642848232 383278345 90205647 820339898 350044068 249237799 212208501 893115549 786152039 585581866 618221166 19000704 191618949 647566191 441840978 803214873 941244497 299385821 801433211 41131558 917255146 871303461 908256710 356807038 448628667 145622075 318701603 594549190 768372816 945506490 247671891 559358863 690600336 374881916 132357042 557913089 616222482 763128017 923863045 172315530 844076902 209603729 343149472 629937386 532682450 172493542 949300786 187390109 390935350 370057164 920706858 792924380 256927655 192427548 291675909 486651279 979254484 183700027 412850233 82839502 323848041 711994203 537242969 269591545 224556208 511385085 250644600