5000
97940132 796735984 155830995 797880156 849699180 572228414 517289684 576856609 736567650 924491231 105421905 187252484 302551142 739237248 212903500 741907136 465734625 471358195 812997363 531163860 460587861 723862843 273425937 704210822 680924202 210713267 798359031 327693929 715003851 403076311 870646954 673950215 267020237 58725008 191376846 7542569 215844915 697623411 992359430 80065599 330111664 499959461 767705759 773467190 724919843 98935841 959333915 999834287 190894530 127721221 212400581 766267156 993633826 217035775 20033275 996050250 213594860 466023142 685277149 688969601 22220384 605196637 165291599 863704288 217599857 261100155 520916469 990785047 713573007 9706706 507132055 462935817 176776304 250009758 675890955 74511159 520861782 853409099 197009923 128153691 282819085 159104586 231423983 798536474 813038664 133109098 785608036 848773574 675720756 844799775 742420727 789800537 483501845 455495682 583138007 518102944 698157681 55643026 102334464 879753145 73171756 365045816 961965817 856398719 109504687 455380068 892989278 491093074 982976117 549232293 663628594 220005208 338797752 153090864 825764470 929186405 778413655 116853960 776605318 381441571 912012234 354722651 502635098 266104434 707426148 892496173 131086891 538139212 820239610 94685351 900405579 392878058 420945974 338314567 253152573 878251781 798203601 238447774 575604687 949880767 580520675 678532503 490137300 692820926 804196085 313555511 100370897 165177255 347153885 742281226 383252402 460500230 910269936 16992041 864429627 271241248 137929040 856069605 323909451 231837470 197778534 604637226 123483778 891694237 215614496 658244650 393346776 574654145 916950064 845790837 317818453 773746138 448391987 477955591 906824791 403855431 612724847 919845241 103973310 947473896 110474991 660568899 508739651 351484388 673411102 999114754 425742307 408800077 438319162 534224393 945689794 82046774 654486775 650027873 625343947 463028965 44911201 829926155 778543448 698174717 706658273 348165206 538245217 527086888 521258231 371814713 894185465 224526256 261296712 30339638 733521223 416960244 274517791 593821616 645342549 866701966 239817130 704786973 560269483 549902439 900568802 495839534 475741853 859687846 658891898 988576649 897925727 773135969 780685872 158364534 529956715 589201118 676408587 749617596 980599041 172069550 947136349 666069427 151574523 551018071 378862735 59916822 63490474 919845196 952433427 761275236 350941878 613447740 821624451 418060233 536752510 68777944 907291842 677068244 934558227 165858653 623035158 770537626 491031069 808688923 146018057 815891384 455196348 330431561 949254656 464098499 425910761 94011685 74434445 586265155 94950093 680701365 796887395 145764261 448410413 54558579 124985001 584239581 979230728 100648828 831685602 343791065 630043755 543882093 418607114 107036471 366288102 834372489 401856896 881549589 562721729 635681027 545894360 187096321 210009014 328593683 229650183 899155519 480081150 113118339 471671825 581611780 485079074 484240805 867071682 404368583 95003601 44245849 102060171 970587448 808648630 666433486 252570434 53973850 991028718 132333074 32493713 900807298 371270733 276223712 408107548 643685014 359819544 634265477 590264882 429738454 318403392 543033141 358003152 397282347 731538795 734722393 816341294 585557011 991848617 221916671 617138780 542972732 795959659 626364397 738343221 270702787 454236936 852537344 75982486 956480572 990016526 19572168 89570918 860043628 517576726 422653447 472828319 52746899 277041525 203946757 70034256 982697190 108723947 197300872 215303340 874687991 281941334 162567005 874321917 16100819 868588183 961867636 52056088 946382220 209832768 880449534 83973123 542111776 311652390 881077312 577728315 2484230 697299097 181668238 237473280 182017720 956816460 539425031 418706418 924678959 330185080 842975124 378782204 792408282 22413553 964272351 312937522 300994598 539096866 519870209 127947985 894137221 813407081 838429064 322056749 21087330 474640154 810641893 620876467 766730851 827943653 899725552 710411569 294066730 765652850 22226182 523521304 865842966 39041811 510057991 735410904 715207461 134779254 135622495 361467824 397361337 801208429 522614076 344209632 396510110 865783694 390284892 451038269 878827293 729979445 951117937 541794347 274593174 353820622 434033644 459438539 791380244 843117537 496563801 76851745 416462773 299591489 962510462 516395634 38322981 791618444 808318766 564079192 540960956 675660077 765658500 19168842 72691706 840961747 936269520 587081497 909921106 452384230 836403751 791683045 571459089 362799584 531881002 703785273 904490602 838299674 855540063 96135020 206312212 536760512 53203093 695989496 450186405 907760124 986110493 576666474 450471462 685027461 660295724 574015803 460600584 21598033 428142466 134038463 639245632 436350613 560197009 145406630 594701861 728113303 372411958 720936854 374890146 163939355 26248706 132675665 828110167 19350969 127390453 402195008 440705224 173530458 277387816 403101857 114915686 927246626 429557208 616517452 505469735 596168944 667338914 608414414 384632632 324188655 57647357 266068213 460218482 556858658 299762548 129501323 976268934 848872065 324507149 502016597 255065041 461819271 315832343 756626370 839995001 107875424 123249472 855055545 472493368 582943469 834572578 606141950 717169311 723132997 66329076 662413830 950117564 244124438 272387006 895083822 548300137 17649127 895756577 576522942 26208284 463238766 811195929 422133260 278522660 274548242 391587289 698974179 164473700 988132903 533288448 391819529 599900206 221477417 728519154 660100127 184087527 819490595 618390855 751915380 921476605 210178889 4178729 159513403 800654039 581351612 211203397 818398306 489437990 534921851 13398487 945925333 243494636 471824269 674011606 968967570 887590287 487183808 670108588 590534814 553209476 201131951 147028625 895698388 257938228 772287545 410569961 67379799 726861410 832921498 330678204 846587036 900851004 980485222 307616871 555057188 610667711 593086325 491571756 280418264 13507710 557512888 931926102 644730252 720758757 490318650 215408448 85389374 716116580 762395957 92417827 30106974 865217429 216011416 338114260 186223445 74191303 76521031 317571000 382539286 497592345 302257060 112561711 5410017 606417154 345130585 583535777 818515628 492578138 954202500 436358788 272304313 812584524 999095089 859275495 833973968 980220151 886982915 688346310 865681436 456737115 222127507 189019863 338869911 14686849 174167267 223322222 876405016 939308902 631488999 59957288 399379766 699613869 797043976 874164123 233878666 697188553 214306171 710823658 324515673 21382104 356845591 152571987 289964985 204346730 533725596 595952005 908537279 438824038 893542097 864267064 488999611 890625908 416465998 905493704 496369855 424637340 18184455 992019553 176841423 12101335 806786778 68103463 744067724 544806345 653053449 801819087 731377678 589514528 751127044 586655409 346135832 308168893 970943785 243449888 746355738 113869302 408376197 499531106 643850252 354028452 522489822 255550003 530335655 703043548 661105043 987508648 673691951 506710730 384944903 102256735 383410353 58152471 393288353 674719019 842939943 614146597 958696908 750399018 518299102 399448113 444581370 173607354 758821179 942766110 631923573 142956189 529284653 902488254 867180287 306856166 469493970 129947742 687396249 726963883 481349757 911706801 551981094 690950344 553085696 345831208 363593244 904517992 797257034 868008247 445640610 212240210 635149222 481171746 194415313 768297508 725213526 636698196 574046026 895336121 859780957 527123209 395558503 447194871 938608405 903008216 921787301 997690139 193938914 958803663 105296995 784977314 756766993 447092138 503843612 522030805 625286222 319451983 255464329 898225092 576159615 798971010 398403773 455464210 221026325 422597082 161532603 595525674 158648822 103971820 382928418 987159152 42393879 735577483 721210372 160210483 366974982 464369816 61469402 939718242 150217029 118727935 922203733 340714382 863987774 330048404 408223871 815974119 487035283 45289134 662669198 666472038 605599477 982312008 66689872 489167344 142667619 935198532 710780067 985824877 751104262 846474443 315205836 78704889 686895038 344386754 768756677 161931047 571898005 3434070 529725134 321592228 762044358 663387115 488824907 190670464 69521190 993424917 228389347 153628750 401466901 525887791 349159875 366649460 153140701 907614702 584828848 988852889 949727928 352597486 390312087 453802740 372348402 540011365 422749177 353671190 785019024 332663023 502358073 579803426 341436168 347687462 584375466 368481982 106805709 599963077 314402350 742437652 276758460 540240936 939945959 991708940 496607595 372289516 594296759 715671416 721738902 377152150 327602445 726733472 874835538 10093641 102177714 708323154 860605674 154018331 532021017 229120359 863918536 915901552 585824342 228027375 427024335 468500171 257143694 888573705 982277632 152406505 44612934 311207190 977815124 414219078 691099286 321105023 437772438 822908660 884970474 889345039 12198128 564328455 393668675 965140520 546667924 599823300 984551917 703499301 989803853 154733959 586305320 762501334 670141306 440100510 605853323 943358323 776318566 899822787 422321010 139981659 91186750 484876155 367496500 938415792 692725881 518214147 599091984 270467720 251785232 466771947 215924504 691124360 790517305 996141689 734928350 540124758 94898701 222043212 986932852 406979697 943725228 738588131 118176970 262981244 874190236 784213365 320984794 919830125 738816774 654391300 61737986 581138627 786402887 100523387 420280906 783892333 210719398 71129803 925716962 709156607 666113496 385021230 678537446 464423756 155798708 582602428 723897072 590140601 960113190 572224614 963435428 49096287 240296393 276603798 334358948 979898629 905898774 263607972 299352200 591168438 805198790 847433187 818403496 846054899 291136591 114547091 104093949 596961984 317332767 725882986 56990449 628272772 513999105 359770392 595044517 888270618 337395563 98492830 901068256 212021192 514634192 217819599 529445036 899689473 584401555 267493982 688462287 457922263 866848228 728570031 784764915 257081467 674207687 18287880 122951171 560899991 322069775 147713107 873655266 312886669 964276105 636024964 870923765 797690131 141969484 76959735 727031544 468097574 832907295 600103600 984614490 822988407 530686136 43690283 358919557 87195900 316831076 810118671 820776951 632284500 593215436 343936402 902193307 969079320 25856168 508736376 50526841 429927490 443533771 245515643 523760815 162794236 89388938 701641344 369115801 794853676 193272949 361745041 62670719 747504078 716840928 748984617 989166866 70158586 763040636 914405052 325737974 149173310 495178180 881000749 245672932 476314958 671619164 365576877 676925755 440970786 939649430 772347294 406623876 778771895 51397986 943873205 820163682 587682786 523372636 743085456 296040674 954598714 182480702 226196993 673353353 156402509 676254710 851752137 82319889 840141870 466638503 482321059 971370851 744147356 764287191 837545351 507977106 191820947 721212141 893696780 479873746 633927956 752503527 883856272 519721921 344994991 157612153 855297507 910359147 850096582 376529601 71012133 22156209 56255334 964934052 474037883 45467512 724120615 793315862 725264520 78628919 33295119 368919475 448359912 52635117 496016046 364984165 419008534 647359670 858851663 841667432 254164104 997027074 622740110 503540659 35876949 346656185 12851608 656673144 74041946 267377513 963650720 745234443 32478991 22264720 150377573 418728848 310024263 4462063 181839443 581925072 531374049 255677980 207036259 68133608 222693041 260116093 423936799 502839239 464806908 94136984 569320486 430289007 625975744 97824369 644445695 64198002 392542696 672047082 44755450 448343106 543141453 89132124 16249694 534117722 603648913 639025507 407585234 130642347 915376751 265756571 137275542 367453262 860186903 643369319 598820213 280642710 362380363 810290323 665295650 103319336 944882071 258747252 328760784 233633883 134566141 512974474 927508330 10731733 651120976 997362694 657704062 907148699 561371916 469507928 550228584 60764758 384260871 355587517 83791744 526625684 824593359 862946785 773341755 403376977 731487482 382391594 315204251 414745166 9645094 853276718 833906747 684247444 613265792 478885339 62120211 189199041 212084972 813800671 292711479 588584952 423318971 167534798 144103900 682864662 993300192 63465848 289645746 13828703 753136835 207626137 868023908 861693581 998224582 686568659 104791446 627274458 890338164 664742399 749681670 840294426 398852641 907324342 714756531 482061995 673967366 566290437 521961890 19917697 826781060 528300329 984988 860920506 49631620 741407848 760201985 723718198 896724879 556780551 745325185 507467835 235479874 973794640 857216399 343649534 251764638 518569503 414838765 822190800 610602149 232588946 749323547 585614488 944280462 305632600 674122969 963775295 414393986 821702590 483721329 479541229 526694922 931342190 143722709 989286837 844220983 308581083 394391765 840991843 97223374 802105220 701881431 320526712 505860555 438193221 68953458 627667212 733371252 85562099 690136628 711567845 359721298 394808281 135572665 31401952 383832958 436032110 153107301 363909749 642992550 484010965 414151438 85442167 204402889 287079102 236619111 160848643 707976857 282241593 373634993 892414554 41026588 21572560 243908288 845174186 14864571 529520541 700615991 192309553 961021151 446402578 672875608 513518909 132323526 680118040 655170542 865259687 821715468 225573812 435250256 642849637 726732274 427443250 174311854 923426522 124389329 638519307 819166255 503659730 500536554 187201374 24583820 460547805 892220575 153505183 603112352 691569678 871996590 124372298 516620594 604295204 343783972 60991267 306597949 284065473 35230444 400890308 172605182 25640416 73996855 808531647 568785583 137489402 202427541 881007817 356708640 129786825 429373471 154203640 658322319 431872894 40522850 475599264 628189365 465410122 720637671 912123814 992405453 325297167 696665327 458556928 809650723 201621169 309088594 323983941 201132076 364610586 587374224 678277689 591877121 980957007 140378181 624616556 248947569 592963222 409097064 898577442 674840500 632255860 439370396 976497496 407913910 416529490 986881969 739882387 633600871 812806233 861461227 304692251 963449642 461698013 810716994 199565112 705160350 84485399 781159995 19609918 971017533 626199269 769333324 717008495 344968561 175133869 329538461 465819840 388020816 939529591 794213460 113027134 892067800 197800463 430314370 961676769 765456370 41883702 506915102 364177605 584819866 822335362 825121253 424196476 826540509 933832193 994932419 991241840 467560710 236199474 308197528 786356728 209271452 758628407 590122856 47472804 391380035 443430477 711924942 879062159 578493626 957069815 35939553 183693104 152694125 850967787 379783690 948164728 631428962 753125894 945703974 282281045 820003094 36027630 420017018 223023177 610775549 912949139 213909162 221122073 345370137 940174064 168292861 188815718 690011478 560822266 395419579 784690487 635253302 844783849 396958405 721136101 32442532 679439595 765422521 971949445 985329220 89075206 666113157 576102394 149317962 359624024 248531297 916589859 636765112 663595217 127649224 245010030 722119736 379669269 236729012 664083892 644725076 469599714 11884312 526993571 276618329 750173998 450067351 775688687 948390970 140613119 609954135 306343581 156489760 103582116 11460092 925420123 961855388 233904210 169484701 710553443 281047614 767976127 236139686 139027350 511193836 585053064 398376254 529528612 352368169 595220747 890594913 37235158 938582643 645351970 37489775 409519944 775120329 151544258 418532631 209145623 945439826 790995192 437332485 817799730 276311439 649809108 742412806 712527352 13352864 733972754 182180539 859697456 203334454 879653409 957259259 153366729 554855100 476691634 405169229 520732969 725756477 278517348 814512926 946466879 549744969 539192842 465009642 98541231 993096931 247223840 35534364 258285202 714321716 212032405 445848409 76053482 221610012 650212933 128342429 670478417 381626139 774456551 648040461 282983731 257353776 598921395 479393472 668040658 724496228 491609034 32170028 582655898 782086368 768404193 582374898 859096744 507361332 627885016 410250976 625866777 66079046 834162358 293950459 295521592 863718739 58362128 914282034 238365355 710792950 488142271 276721838 184152725 75732556 344133289 722754969 646637749 49429257 27399220 866251673 235457567 197970780 938534985 715261332 346858944 16126968 182370106 832416260 260153234 74954204 528835132 925017510 500984854 139972337 575877156 764993086 421388087 632551513 285371293 176367104 419540999 563453195 413070085 28887607 556733623 54850042 95409359 700548836 462987147 393065638 674415637 6769058 164402145 147127470 335961802 223515616 472167973 790716898 626204093 660124197 248070455 995993603 349220935 615167717 655089001 106302322 895812515 115305045 478905582 323712356 805930891 542440527 566115700 308334774 286606890 814295110 668936741 108683370 498317131 108963481 33640978 762560108 21732067 884071497 638494933 602364932 617028856 300438856 26221271 765989077 566418248 207916239 849908208 118277887 592287701 441324902 582497639 518726491 804020544 916856278 449487113 869485899 883326742 997756953 993880410 521657789 833239467 376684022 168090672 25613726 842845639 469921603 632726683 912386546 196876701 148827933 604911747 31763744 151450148 904581002 7476697 406986947 928936457 861621449 203744119 464613532 951453040 658810541 865545513 62952006 253233687 192982412 284096397 637866643 922689888 506437916 663391017 4250024 59807426 36226981 273244364 481125173 476750271 359134608 889613270 117527614 859282331 133364918 619088255 589269465 307417837 36739922 721196137 982026207 351048827 717110504 347798610 289563497 420427007 777862258 372154571 637282513 170481062 277046940 862918783 964114412 299116193 358963605 205551772 925372720 213683729 293678440 77476784 863436361 557986529 33483619 985192553 295198614 699009861 133279732 408740631 387546003 591828050 758078419 708252926 605926037 915177823 816465116 315669248 529861844 130311330 145396700 972687188 374522354 100358999 303136541 698911460 226778698 106576065 823036594 723060361 603761876 839844975 639968679 930609639 87375074 163401214 265118784 203990697 673612715 285951891 854196957 882016953 926917228 956736878 746418936 93664725 275928156 918672816 763999694 932861429 562102739 206708422 959197841 720056481 781351061 573571915 888684696 342857876 200830510 218244995 770764729 794929027 148543664 646920944 249933573 563745400 870370446 321128795 369927104 671608232 987582770 901937254 67476717 452660645 45462288 962300652 292066150 545388143 90871175 597242286 849519925 367806056 193232462 625227461 861106600 590925997 945518397 670707386 440361496 788057223 244780873 340509604 58488339 873602732 423378155 457655107 581983598 208425159 946777679 322955829 297051921 46349623 422813579 220916098 141124284 214474256 197788090 538690864 855575111 674246514 921039286 734808785 57426702 413500189 949723588 374602745 523276517 377862524 783845862 868000784 225912536 118154998 527635843 874398412 602318558 138159552 57536899 466674566 124605728 237978954 565387270 277434381 451591680 943482740 665167527 26529377 761401427 106115079 544349553 759211297 813042235 146571966 782745356 101863243 561695661 651074619 452898434 801949665 292159065 718018087 209518294 80940959 177323467 278124088 181272085 662272551 4921409 694005996 946726759 960832890 596295311 99352654 678094478 800392851 787516732 248061222 36797436 537466787 98300304 110092609 620914943 360113688 265314264 342038513 62576598 116827522 212148405 291252971 859768941 319717598 186450498 75177316 820718207 97974009 634856454 199603030 883028929 640694545 794500761 475334136 916811712 232898535 846352768 511787581 938477665 522637485 38086706 178154680 460759663 601830227 858982658 329073007 983437948 348060979 973090754 887840607 868037623 913524159 944693361 261622015 178682263 452352444 30387911 510631738 937156884 710802353 890719269 644129633 238790158 37567108 766264852 698649098 860058689 863875061 609885681 426515464 751189480 920967152 25078527 208159867 784118589 675311693 359664436 895252923 478273923 332973349 266274636 954609856 483955008 553682963 687938630 628385480 753223355 835901902 415633061 988413432 762978322 151122874 31656128 87559782 523499906 562506948 512105929 54777231 38367183 411374261 210228213 601705067 354725833 576746519 914360357 434560268 337435252 9729574 765142278 786418002 880677246 901569312 626450676 328012658 694407717 201463402 730473114 804666525 994109815 258533969 162338 147285091 605751714 232941198 471875582 627965384 721462849 32246925 887739508 850945051 808477135 956296228 353914001 146309703 512599596 887402559 40913548 776435232 399247673 276672456 279978483 435063332 278808593 348720982 84251438 616912103 990615117 66272438 822616188 783363395 837567260 943986202 150223937 230969771 611877450 799475090 356141762 437086499 582455822 802771005 202986132 352963296 486142499 975567898 402541352 697567026 569741613 625271701 466006706 599541568 293431469 496770071 500008195 289670573 773303796 498374115 801447337 866552514 818238920 87896615 59741972 4258578 20520988 666708300 788052052 440734238 726718349 841014100 774662257 53875212 870675608 260791320 48735045 24067191 586377456 724039333 888119184 28256372 272643790 621726441 452160273 79751019 801790873 238886346 171887608 637196835 619413800 565348330 847035134 589812482 60891534 675650124 304904662 202909887 690347500 284556976 79420994 465017724 616436712 328779370 226439036 454673822 490565820 467126604 844036075 57211577 108677470 757765727 971995665 112313912 68518963 869524843 815462705 699642548 680409312 38615330 596256118 697162302 324552972 964162085 355647614 653995045 435805595 793245885 765124772 441988788 263198704 905662830 164845466 907793586 3948014 750842924 764596791 207659105 286172780 509134420 557866586 406062528 833646662 835305340 620313138 611831842 57773489 471408531 762356 836221890 929092070 450391164 441617896 252557498 970119381 416930066 966633954 94510723 988436051 144212228 329014077 395172283 290714909 889827551 750974083 51431759 840779446 321071030 227456186 973341641 949787876 610374928 285119743 663638490 616471869 274041800 387291184 145753648 272729318 742733317 304295046 662925731 848638859 364002137 663641433 801118751 251290683 685263859 81985077 900220728 549655456 838321665 308978990 79300161 991058970 918300384 602971340 256316458 739538310 170760731 789875302 784230679 92636564 695778625 499478388 685293544 923505621 478775172 860645669 869640904 589450929 446415732 802246557 677441531 330382192 351095873 31042764 432693560 218845014 76292478 942487217 788848307 364212584 457451150 809442408 734289305 471938611 232765921 836646863 165902157 245561914 289770593 8052610 169536295 320543473 639543661 949635256 751438981 574308244 822234276 893497271 283981132 783542679 429630223 563417577 629642182 907163180 126691919 248473389 13425645 84824917 938182189 464493512 925865543 564488147 974112658 435458703 800846483 345036987 631269527 650062708 782391910 266444680 641500405 110488560 100228216 157880499 70156192 104253774 492716639 435614340 928072156 735905435 109090695 777005420 606311802 400854927 246537492 775434139 646627044 307346776 430055254 621285633 954847404 186239688 17653547 249974701 168166591 213775712 715977755 182582858 341343361 462840952 309163205 151267166 705090180 666030789 390515468 740115994 832397948 92290980 231434715 728631399 111063434 646296998 141021696 381001598 381708648 750085440 240666558 7965270 754839367 823764128 196616396 449473446 450615118 655647479 614703934 661046001 81030781 760949481 795141144 965448733 195463498 18191081 896112393 556124989 42634308 425897582 265331081 206073846 860789484 288332393 8971525 108084338 545569216 360029812 525460033 711644273 707087846 391230373 314932625 785484080 97123088 770299343 955497362 723695983 384115144 357221632 641648400 319252873 169679037 803625100 280829337 61432348 577824006 20378342 274353769 391835657 335102407 927075115 975933256 818345321 852315079 502334633 539026957 84992824 103927593 873538176 825362215 75473262 86333024 569819296 633415469 552519683 469701266 364877982 155967723 111107897 791434109 801126757 915836041 379548153 618724659 828145486 249632575 373618784 621632463 158889612 382121185 1185177 529518371 387657372 356576132 184467670 728574730 379152786 326638504 32690962 731417908 507800324 608397111 310134892 850257437 382816182 804955138 950650450 447671707 98577262 171795510 743217286 772528249 807257683 618341789 584480329 440378909 148279709 809775568 316817743 967070958 933917051 748980538 719151800 197085471 257137034 515988855 621758713 158970096 552629774 303117561 139479349 473084814 68997108 388201270 41724890 496087085 83376179 85217940 207813660 196587210 818689425 403380626 777369906 317499290 586906550 290350762 465148666 91663759 832515225 779289966 883295494 327347907 42391530 964496399 265038299 105468627 210845244 194322469 766458884 599830544 111093018 406076343 904635270 468025559 147425138 735263419 45828585 322447508 438799550 181749429 763880696 529558848 639483026 874604643 516770380 285505616 500105444 267826216 898266450 351517091 481061230 411774716 134306262 26830033 935918359 39236753 177653723 137692183 17405322 956733367 459555814 866515146 562595371 102126142 889908612 700268484 304828143 27150535 115715578 941977823 500585357 929646170 301799316 41415133 326291789 716144145 803556791 51499905 518798950 535438874 539604122 992509207 762865884 653997981 365390827 117329673 63696447 188653713 525255728 14174780 162025869 597065668 249220927 169599582 63798669 828654720 228576477 753084229 797717835 762970527 547707876 499222375 934552605 16500203 457572340 583294565 896709453 458301205 451305004 879214404 371312509 486571885 509914283 605054538 239962835 181757595 448943853 411869507 976071927 227748579 809877475 741711820 985680588 519273398 60585497 617040649 55820573 158816961 432865405 252118209 826251786 391705859 844747598 705165707 257707896 793593035 296340221 933354737 770717448 950762861 417439691 123329984 670717118 153466473 294565245 87428848 309679126 670289179 13354490 722132822 781318078 257087627 520089919 326375887 478954022 841311484 75381969 117183711 705196690 598100294 55768096 159921747 559308627 955930037 957513982 61464726 453218654 945943189 390713015 711258659 259786250 366777919 338468805 853597536 891831719 635411717 863675642 546296348 661695689 460779145 128678391 204260476 710155982 584289205 850154836 878816275 755491960 111510467 861207907 719840158 374809191 779782649 73480866 520058068 138558765 678255388 906964507 221623996 381161666 314483262 909820516 980357271 272535088 536319806 490442524 160075498 739192863 405656691 260687012 115061245 377994801 394558728 135424266 14500989 375212376 573224876 830548298 781745579 502145031 525953198 553914624 802984931 443993596 657298736 986204093 541662750 398792875 353403399 250503569 820028030 879615985 378942545 580550156 9954257 121679831 442179764 974692280 714918747 121896470 154237051 418393912 546990972 653595302 453407266 246842886 197384324 306686796 667354110 698885397 620703564 60693225 52585612 371336481 350681807 272585192 505512140 748297848 32805929 120421284 728144215 211249947 192701489 819259577 1397296 353950480 315820549 457308655 669986949 251792507 271775401 993343433 644325410 400013801 742873172 526778570 971784167 29584933 558024752 777702031 989595542 580574487 106451349 245088212 226392215 644611962 19400575 556402521 501854346 524869567 188070892 948058864 545307728 41997652 498097757 881528999 349198605 317870859 175402537 129267185 266146812 33493966 62378584 84567767 803417042 731195840 978123281 167205552 607119887 369581618 165798305 97030871 672380313 913908116 69328508 936124474 698698751 914267522 704301765 355836926 839794331 479262702 759118875 491897835 52542474 919733529 529542359 679013170 92379956 192856195 858067591 608818791 16432559 928210932 417535261 987703874 813200574 609047016 472293592 459808581 820461426 254664583 578045703 41173990 141373963 61600199 230315002 463494474 195650528 383781261 459273189 837000025 831219083 579631527 103853429 85744723 783262488 59375340 310697943 210005265 522681074 323218630 371605079 612757736 592185326 81455458 262985866 36173202 593694940 610037427 79793385 41979843 104123568 779344409 188947767 438154525 716921232 42718319 863740967 535416335 666843360 111880064 441768343 902653688 771140524 650574935 839412134 290434402 149064413 637750943 572541026 680858088 881925944 515659980 753391467 41415699 504618950 982376890 288508550 39436037 4757108 97552967 289378754 638423034 548051770 278204086 408532766 973134765 401811197 327083 90470546 307794190 451446250 238411813 893967260 463784761 182133412 877658330 873093125 147564145 447395698 391894297 930717980 770873331 872647788 296602458 897940569 303917793 443328300 578821532 382675240 21183781 704928743 620890981 864876437 746628217 534757529 898237584 467509400 427145631 211503467 828476987 152606544 878729862 698579526 912479085 394715440 429752055 585170023 570829407 21745758 43041751 325348744 857566862 436556244 207062517 217916697 445450500 378667050 842862422 881022210 289351116 797634553 748357532 156400219 24627797 195937801 915198521 575128658 649223070 778686337 683919935 486440823 464866451 538572747 516308870 19096552 262068597 156384385 605618750 490074332 797046603 798993094 13373489 882031051 385148481 464109078 124387904 30201176 686872367 576765275 708584395 628619998 743617176 847908107 826092376 897916478 660474431 980891389 122011494 658803569 193462232 678362153 589327781 756034070 526323997 913937787 657476779 402823513 980261493 760023591 816578329 464937300 96435435 804009009 693263710 28826877 553002778 888207076 794685131 83449192 6326704 825961551 900844131 350222746 808532842 716377752 612290422 708222206 349395257 399009085 131237616 449679477 304619498 619553073 708172213 183683151 703410619 191024027 745227623 618979869 433279884 717000071 408387235 874497585 177563364 996620116 964402693 185269516 77935873 658838708 349853494 340941834 370543362 216040247 12785908 410907295 935842849 446181715 125229691 471914996 794177028 978916773 189888186 645257646 550281886 513171746 898529437 626867605 481546838 567925053 804569710 159929468 600590228 589028787 954219095 160567068 211437869 727027457 513477569 802576350 658731442 536932179 121501625 926371006 326053077 394771663 452882935 87800236 22214053 484610904 994624157 866716416 989628673 181202561 678209779 855844676 722193405 876236919 42704288 280522395 110855457 385438261 614229155 989974575 574714846 242546540 942464781 534310798 515855522 201778406 638034431 41197988 500299851 300265154 560595240 183826558 121570526 249398414 564078274 618836649 327972592 722993877 739623110 20146963 933905717 374428573 546022319 882930603 893787014 706375014 588639241 669535508 342869958 813348346 960843302 38194544 98198112 728574131 672158657 525408167 94642186 788006027 74293988 907456075 534546627 50480878 390638004 35207422 832272100 803865463 874844521 390358538 83104805 182363631 832432696 125975438 968450329 713243807 510912905 876181739 929150152 516125877 202850611 805269181 919085719 996437288 795665344 732819802 514644022 561670871 809079090 514086767 299476420 57722509 364652379 536358677 174565638 874349979 458869340 729211403 593282131 344300815 691132208 921523503 205586195 694740838 208363782 586905767 204751635 744267021 268722473 655723218 613107970 676567983 382259435 669630929 89528105 4115274 297500907 728995430 790403040 989440419 232834957 892559696 991341752 762546253 421355805 326240088 211052346 259635948 6703228 107882474 890128380 999122830 211382255 194591442 828288882 720112092 363162516 327795344 569100008 913566869 659242752 231718401 83634768 322872434 250387066 884019323 390466696 584067335 548235665 902892484 545097205 639775454 328799495 718377011 972388113 766109398 643553674 622627301 876443520 407581677 100034187 279782184 770794906 827523713 728404925 600968124 124460230 495964141 230117356 876066752 683140378 88419468 482116946 280850538 425751767 781412239 6818392 414472865 46355251 773331137 917692984 49401301 335881682 555754394 398684559 744709908 762047679 268778241 446216180 800802679 856098019 132031368 823175508 621056391 280239727 526091344 889349000 934293795 710474932 28814601 774045742 376202136 375675582 929232158 249284188 945693978 524364308 903053785 670982718 403071283 221232293 516979476 390040519 925645971 164912128 436346634 774553735 326085412 463789339 735846771 583027686 254530269 267465380 807394686 161474590 871163341 969809925 722402729 440297010 846532862 468308858 437318716 119349189 753770948 594214355 864730286 798177021 220805512 609441317 891493800 96933467 432896060 361601483 80430863 420733154 471038599 857619949 780437498 157851846 314717446 71845302 233065759 507905464 632812674 758353624 114515830 622580040 949061259 196292203 942081863 370267584 42909875 75433405 340240642 262575662 923676434 115768955 156243688 570871976 534588208 462291459 310799780 573654405 475263498 203219920 457676256 705557338 18714580 186914445 334189650 127592905 880333997 772237075 452176574 235735381 45141390 589784020 153676730 954782427 770055134 541902449 84684111 644427481 601173975 134922237 573013028 178855952 217116189 412938502 847255441 518541153 460479433 179962079 310199808 16384028 280984899 891984820 502009526 112550474 605127421 487663323 83287443 738963948 792522930 214299084 358825700 500434473 560381007 552406222 644741979 635621758 695660272 626686079 702670780 617877890 901815348 664093392 779984801 985979277 273812120 717934945 721186731 996857543 930706639 796454098 545113090 280450366 603989152 546155431 368199931 325842660 371739632 773343472 489030738 929203890 508066695 482011168 809703335 734777590 406673452 560289681 833906751 566983942 738996754 119566249 395229258 739707007 509729358 182821332 114983857 561654923 600569077 5046810 306902273 602831484 293894416 364152067 479129103 307851034 914660697 199764048 107076024 671724292 682639198 758329452 823019996 136850012 604914670 571472308 48506802 847366455 767188629 657110617 817764204 237374284 905854382 733500499 906097578 977114567 830630598 266990498 381969826 354865218 496094537 785673108 781070001 357565201 407205944 832048648 351897129 409805767 144733396 160911618 583590754 438251732 960592828 274342393 891203584 430785279 649888718 426107412 693801378 405659615 44792170 926711557 958216580 68297414 990681216 979661517 838666152 927510192 761760481 230996625 306742037 67097842 580777574 469056379 418361063 970448987 40201695 19653045 124904469 235243398 192248424 911871269 783861955 183688793 860171530 715986588 382394947 784441834 545269239 521331136 617145249 84994053 725785462 217368180 290018737 461383483 665249201 197396580 52467982 947752922 692771355 365573050 116546476 418490398 520295703 255349655 768779641 572188815 683255074 746975616 296832319 393775001 887602440 617344410 932946926 369483197 420394938 489519718 937916272 325823395 521726029 48094833 391245159 218129669 150639205 292136117 238481851 341855113 43847769 318024379 684178084 369353817 906442093 407451034 514953287 817136590 369537528 456621770 281305667 473432003 865304297 77467343 391683600 412785846 878746114 258706689 868289703 958516952 856379302 706111874 841173700 98539978 289949432 187915517 530960306 801406814 923844997 303901798 301172891 542700430 442038688 630991308 279388879 100298673 922130021 388263203 169496083 170090970 486193441 963174388 127759551 73351105 518220725 212472763 226757634 834101529 437800323 671021869 266839669 171714591 986445395 360207589 782667105 511010115 912356611 567166581 807682 768801901 578674755 804694592 657963756 360926003 969718210 622541852 630151647 619069464 606250121 160589402 363423562 215547882 650012280 514630561 610571753 448500680 327128608 743239458 876285584 144750916 874039372 971173693 413236878 414726189 497265360 129211734 871929902 877630596 451268598 539284882 536802239 624732930 174160695 849969612 525988782 106726019 522128433 168051175 517054696 601084346 83788512 602560044 384706384 717325044 621165036 840955455 751398215 372419049 179792110 446753998 903039753 874232594 125999794 982578696 924869083 654339497 670124223 425933818 534107059 91200297 422999820 437026039 41200232 502587797 717213162 422374745 94653918 1259923 563068735 534979329 583160029 278808696 251273054 642723890 410928988 953941131 115586939 209175884 10647746 185114665 180590712 656621700 389521147 793250786 310515132 692116383 593574209 240534782 183282389 699770850 3342123 388864587 757593999 326791591 230546831 801354041 520137236 332681047 751705154 170935517 702464666 653563873 172451011 531665793 651245572 563465347 65226693 169544874 689441740 880087922 650870910 567913984 437543784 711024833 905209772 516718487 636750963 91810979 795255441 687768469 616839705 859014186 761098133 21248174 719097217 916542693 295179909 850395503 442731274 592710392 158621801 395798290 699222780 474897179 138118179 603422034 421309563 904771167 859076309 504578005 107013562 67495893 245422905 665110419 44145101 881856250 95046549 818449395 343780477 26829219 8123641 559495523 90652262 680843687 12671082 121332486 481875608 453316265 311676549 110086954 756481913 753237742 299509590 221444400 843792574 262929141 899662578 398432634 839537104 251134901 135465617 46793997 199616452 53030870 490587158 697874904 219754600 102738720 299979151 951367674 381100514 544739529 544188922 988085931 689378302 643992857 197760669 197761165 222962381 657788165 405231448 33051441 308378442 17862850 543205327 290047943 59687967 81900000 486763016 957534647 681285139 625908214 893737013 768761654 988857138 646595664 388346860 700330808 250290384 307930411 978710491 275232665 560688327 977048255 578965114 665474267 86327580 314932393 794885900 296403608 781174366 491764805 240037637 329317863 996297102 964268819 958155756 288716932 611818085 11348409 215263393 997432918 443290888 198447263 520808506 685441409 605037177 329788755 5040036 751747419 646524948 700145152 720017378 553692182 178133183 357202622 695928277 49643784 635504209 258303518 91265707 443957356 731285053 681290184 746194391 248494309 112783353 106006668 182963825 793105858 574138983 664437625 50794701 808827383 300620984 591567645 668846068 315136376 756151150 323232065 106032444 88324718 100769368 102843860 891358594 489431054 120166923 753852112 937544550 172487675 290536541 157738570 799493441 604637265 888533351 105973971 723408859 398140025 857109799 610677037 457384900 544290533 311025215 537902129 212962679 141971201 189953299 46562774 637239118 218203549 131522533 998089200 53418576 563838389 477261169 926392969 263186105 692591301 778119277 173612330 283629193 59056994 488841453 662580598 140112774 81426205 614950453 192308381 773619558 889543010 298745628 859485694 158914318 826426288 66724841 950073112 480097252 756448354 116212141 599770982 173758392 620871242 930495186 195819340 845362723 359424993 535368698 898485382 332766982 528954980 646529902 301158442 258807164 288495346 538854919 988591990 248339773 19992758 898969128 63670706 418847613 38042927 556923044 72445519 113323022 170501946 57739824 226507307 464567082 888240211 376648198 21054025 823255078 89609268 958868449 887197234 2424318 979266065 886506806 763083735 387789191 132473404 278407157 73299009 945055383 570689471 689316978 578582757 176372620 61545552 982590196 951038719 132430882 158973999 680812706 691649726 280011191 623865421 103649097 845065685 801017976 296225006 640827880 997793813 681028437 258934773 986756011 300153119 447727659 989148697 547406568 733567939 415483015 264056898 300409175 449166607 140991300 623769306 26419898 227622725 795939389 798160088 106968407 632804221 537379612 777346722 673144246 167850251 103140248 574573999 693705307 754991147 847627263 501339346 628175104 857985428 516548262 439041553 168040074 159126143 573766215 889976883 89261369 47616163 698447595 100702454 745046518 358043759 953494408 691050046 427775414 635703863 248071493 804805059 227415559 637386386 861038173 413400426 529023772 451973989 466327898 600581817 802769675 994684088 583045184 560563454 928130912 470758136 364610408 408115229 776264707 236108398 239409909 737673017 620403079 554183027 297309043 50476423 501750889 350182082 952480639 159307635 805695465 832980361 648439854 687928568 943634848 252776881 775797753 180547452 688244762 993648445 210089135 372632173 717807061 1732723 765707850 655293408 220872747 150940186 895692672 788205511 591366066 783826802 77864767 929950763 906948804 12622893 566246416 406082185 180864543 506075737 983042930 400135370 712541641 28404398 288642542 26026007 412135979 729879418 26329073 413892310 390732191 633201299 306947739 569096871 98991737 121273009 797991213 718066403 69013739 897077480 281387956 305908786 907367493 374398230 850335267 731900851 88425772 399180762 258462132 174072991 945972899 806136982 623621881 240434555 240539068 675240347 626132021 550051970 218492233 400726462 688093431 850773209 551602746 164111039 572533529 140499232 364958848 749538178 187303547 190900055 599946014 776605265 398731392 189868579 231415966 39375237 362658308 131507664 765115595 255815336 989513778 699772148 773352758 731662373 965983125 944848161 732260956 701074011 939624656 397305153 807357439 556352651 516370962 291530951 595475771 698574070 494900160 394139600 693867422 448759009 143467524 907263830 989214358 159617222 897955465 27932675 654187274 773841075 422488610 146767368 531074086 29450681 736758914 105418905 47385745 337691895 250552814 368478747 934704065 129444297 111568495 135757502 28926449 25672999 359601338 12904537 651363113 390397894 787200500 540114974 372277906 87177364 80238129 785455620 753000040 267139195 425524988 161942339 102581768 933461385 541907158 769218244 747770122 283076049 360899529 891526239 816172839 824734237 320847260 379933428 235289656 186692504 462652818 253349385 289557405 268278015 851822007 213029251 782592099 465333599 328987576 103300583 72866284 369938967 842867965 456125362 351062231 818848419 599594059 714750639 142573677 900444120 268075301 464901876 656906384 858476565 849590913 155877825 182682890 905550774 415958589 652984914 515575762 875683608 21090336 101031676 303431328 763022409 332350512 562984356 838150698 715393318 220235675 475745329 124595184 646265489 110621284 190990559 445835233 574033954 183565610 450826807 826771397 310919273 659657026 761268315 363256997 518760735 742252282 309085314 851623735 754841308 194327739 690794207 179477491 445162699 604773380 233690454 726915697 40291830 598038538 192843225 722196372 199242900 914788268 796105171 292667990 59644126 249835894 930824288 249779806 375250974 783594128 544515195 842021170 991186036 759398939 352728640 575228606 144967199 882536311 965358556 769202732 451913870 812556271 490046615 805535052 94712468 345071567 5585920 775094271 792210112 86509307 4001111 542982720 535891817 117572306 156116799 918600230 646661315 43208063 292522970 707935555 428517989 609701617 607827241 928250694 658030400 285537081 909729948 561567700 853785060 262962312 787902175 555851319 676645276 441261549 525654419 104915684 185529167 4031562 381629529 774469600 646226422 947301562 47911736 110935268 999240577 782521113 342850474 283373867 396149473 788507299 468020573 549819464 927532050 482829701 126453139 823997382 200585722 585881484 146285647 201505665 326343011 72285497 745606161 321090216 695038420 73117568 500787305 556111289 657144088 815387780 710848553 38828679 233165280 511135129 695179474 153682862 958749034 537388493 606294962 298899034 285782122 424944741 497521863 463142744 262149819 915828404 554846106 415671551 898387032 841096311 23134713 903177584 881667095 198928095 562374188 747811264 297971798 552530010 312070721 642043382 303712010 310000105 556513982 194841712 795235123 347180602 401940181 664836169 248467030 502306174 355765755 127818610 285948557 628175032 206349786 293981801 484157274 893438573 258616266 172013103 849970277 753013807 576411631 201299729 973064602 334445544 916097473 558525070 419315472 497656296 535531161 268531540 60691148 733661386 50720084 36209036 418062707 890210501 181916986 432480044 772350075 654002993 38100889 278399203 170116474 985762780 562407266 656416209 159265155 161396401 569605813 871439774 677778701 60809784 243777142 437851324 455116171 295179595 305518461 924454424 729726527 186696198 570233044 648230587 504715113 622620231 791704646 428146700 772331967 990688823 935573055 803000 587595501 203747052 857325516 191620369 990901881 602703694 235202165 161188658 596153735 112717210 880341314 279560665 70529179 787680412 727751053 32668718 730083849 492893348 269038752 971835371 546364960 114793329 561481005 656682568 858365115 757360573 526788636 893080604 82659990 674296432 524637621 414554347 300988668 261428249 840543108 922274912 235262339 689183111 647370233 59648416 840384867 964484906 59301473 525701644 147803112 211342780 980724832 744415953 127366118 174154189 37035709 405415556 442674851 940876532 78954219 971962780 483015632 230867545 137963311 230001096 63739441 789244679 238457728 414006797 465872505 176156175 834650764 84856554 364655472 670774310 951496750 261145076 195676636 866723651 433716290 278423512 602290514 118897654 441525560 238674672 233624602 239394295 704167639 288600563 940561490 188621542 122043316 63911686 166718597 146448857 899191335 705397611 404217712 740495292 730701594 908552724 961043665 139005373 862733693 550020497 230247085 267416954 161077321 38663547 640300370 314224516 214624294 297754228 209963341 521192922 629141927 204992688 952560393 263728742 931948048 212364112 505605495 779904570 88688318 174445487 930074460 781643593 898807033 348803442 720027357 476742646 6464821 30339745 417381799 540309540 633349888 518990566 503540055 81136113 943407083 142036637 73901762 64677357 798162273 701364869 992077777 227767249 249063439 392704555 208750628 790578673 181767226 417519070 454657533 991084338 318979505 787788974 845757467 990546024 890470997 999965983 385582089 383327066 650852229 64710360 407551797 128906632 231392269 713053726 194025032 391689064 982046702 484169292 621748388 340778783 469843391 725114143 888701696 559310769 640739883 330705312 937447821 334608829 578801103 904493756 974601374 722847677 530855456 86863297 445503990 323879790 564315725 43830139 897438346 539803078 569346371 919694765 103376478 850499923 832468951 939268962 341758320 558302928 568456495 674275317 706157628 527178516 78325515 170707471 937948507 292878927 356134767 972026324 4373097 810602254 425534525 298457229 275982082 50090773 379259577 675557115 854655110 915672538 510804472 889381791 872925165 113333366 164915406 304519415 24088199 792210334 671871294 593241152 574494195 166045387 524682444 626788369 287547105 731942159 951840431 746561085 708489392 3515830 676965405 832921148 532360466 361555523 33161881 816036259 417616262 941956741 188328049 874726940 57200285 909223279 347398049 589217569 356322178 623983883 765619573 709256563 861922036 56628681 41074209 382119684 114254608 136843055 309773778 302110135 353299811 825643606 375485384 820392713 677180257 722753433 663701761 866300316 783726927 562315101 789783149 944405341 33420962 534096694 375701516 333067053 902724792 60395064 748058892 638535291 429836597 517219853 592318738 951226230 164605636 527813225 149286631 880184562 54767060 303953927 226073724 935713032 183311863 142878829 754963625 356378506 867082360 564550107 671278286 545698995 684532644 506018515 801071528 794981078 304287802 281978936 911501992 377718609 228775212 633724247 861171537 67691055 798663093 117355328 314574409 491563025 632596887 999239302 348684055 121994192 984060619 438316551 846587830 196354792 388146075 105911716 570973606 812362570 471069663 955970885 883493745 287139409 292170094 505063674 396121044 39168439 447379875 819214283 911517034 32810645 150869377 119653789 434890508 968889571 517896952 646926849 524889603 811648368 446493233 243911212 658383269 862645855 368445234 593087470 628238284 991243029 81182112 314224414 692450089 965675287 662346077 962979243 826926524 381391233 597541609 802039029 424415370 244305333 373212537 130015009 106874636 602244387 292809023 487070230 824945024 531734493 744079287 842844265 200280948 997752298 635011048 435639815 878503740 357169632 603658418 241472322 762028046 902293475 891359158 582877193 621659222 922595134 445266233 916555511 422105215 71062977 107588368 439276772 379803028 973890128 859705744 465351819 677017426 34201789 126124445 837980912 620020358 134471240 531311110 348526878 470314893 715334109 20508122 976067413 814639351 737203434 521680129 917239183 513716984 63029367 84720949 235700210 299119306 497477648 140254720 92102427 621517668 370436905 208225601 268710706 755515358 649081416 199975151 498524652 450805064 61568934 572374924 324655069 912749895 485574093 249712827 553455104 221689849 339257688 310297305 705130277 479436433 445413089 481875306 176440170 505631038 394797975 314753072 2380665 308760724 686351036 886128722