100 100 597153626 795410134 455717535 633269549 260343685 76395671 529548709 207439731 481904226 49019466 993569255 334248838 927035883 79856909 978353852 926815748 701931489 330239750 787301772 427604544 67087324 149300790 953360340 800638173 731632397 841822939 370455890 596709080 561382157 927373771 50991008 698066328 761622277 762597409 86356624 375458841 867160528 37032173 350938189 872643090 108274449 350277097 218701658 66392019 755474243 103875207 868035696 145772674 847424392 894056214 597303410 577881745 443057987 911756052 156166395 635215669 573992891 570237305 746662120 156721308 445631423 937802320 614405125 393886833 631925277 274446581 540900791 595944260 369192175 308036705 158462925 76680589 935784816 733365469 231685022 478715830 51588536 99397029 94810971 134988275 84541771 509491607 395760552 727847246 455731216 517165720 757072011 152496706 969310226 760719691 935763898 623429853 592205396 552229884 148410446 768434845 633523814 648131279 696434734 474049352 100 255010821 964540031 706963513 241334047 311225706 416300096 570575727 798708098 27179442 855375977 598834943 792324425 232667722 606334897 286870183 504115456 369903583 762305274 617965411 645979186 927129575 889644139 23114205 404713942 440760199 214594197 101492304 370995625 510031209 911214767 552777944 649677112 685907479 4193599 549312020 158541373 870315615 953684562 722332341 791391825 553060216 762786704 262006291 901342017 5226156 247150292 531584082 6311730 330637420 107982199 395813599 24970419 206416034 353235117 659510153 376098346 825564560 828853964 386840870 752958815 56300596 454075089 860395426 465619558 156864666 637070825 867400749 988121566 779903479 820866509 847531996 262535374 815345088 21524616 463588402 305315194 298753882 137660186 928889037 845026101 307441420 855112413 265077300 358553970 6513955 435796763 886067066 843460262 750895483 791204326 364135916 67681628 620072031 506021456 211732804 834243062 888851144 563122246 129740462 213301223 100 3620118 677743855 364328077 236849671 430444565 406234503 709583301 80628134 581971848 744677969 503698124 599858347 257930323 740593839 113679367 432553513 737954927 224152537 96956982 165141835 682622620 40492671 446850648 436054926 23576049 704400889 9024685 136694042 789508223 885287628 141816618 315129407 387033269 517424483 771901175 304783242 174191471 212522143 222934014 223535047 913078706 107319989 726202528 119116721 528508629 813996345 422586604 373215683 961696622 796350556 724932139 245413613 180827584 33083277 685289286 728605239 131450362 977269036 466814036 627840990 313950619 920899428 525074786 997817503 81980577 962149165 831082740 278801732 678107582 818244830 889435855 344412432 805409414 953998233 501249310 907059182 752249257 945703886 517486231 223507884 597752093 330506516 194955677 802015251 960125542 890057051 560688910 875958475 623649913 141723128 944048639 715953927 874140873 741120797 179889494 365797110 901417832 297257148 702138978 674665942 100 848463267 700063162 251545584 772830843 533804676 981853433 321285203 564763969 126447069 656971722 750301842 371158036 633511498 151900254 173699867 108060175 435362604 293827104 607134164 171373930 556049220 715729905 168000203 296099542 204089648 849985033 191744643 240156527 379724408 104913239 632834917 508579294 335213656 398680979 389581677 980102249 15310302 704001946 565914893 976780389 855833058 858236469 759913018 510025614 374317637 643092800 890464516 159368456 530903068 496395444 360603512 920974615 311171721 827434735 750679795 10966712 860976894 775640058 403201739 735121162 478668513 917824082 954520682 576260794 664218431 788161706 244691076 863740237 459343292 298810529 852366174 719612157 207414450 575882361 900907715 942453253 208669027 555235477 616088973 782154320 527592654 768712064 237146448 714299399 213559257 707930646 416259805 903379929 634182419 436159152 388043473 275275492 787280796 323131941 517433777 490627221 562693387 959388359 557433798 433758558 100 80997080 367525157 747493678 699600900 180584091 438969388 87163835 238952149 71847058 42192663 701380418 83638400 496535743 747702616 197566398 334521609 893817700 978999192 737518321 478301370 579406752 871763859 138871538 521463058 383405465 341138512 514697254 687212683 172482896 661382570 346350002 916139395 252757332 587028197 80228093 458805901 274449806 413358223 207365161 316997748 656988932 741777651 821079255 486878529 334221480 704255476 858875661 20007691 273451971 499929391 330139448 431184614 727485189 400795982 617232776 98611207 423424206 605240353 343784038 801575225 584424414 170526665 595783279 224861871 910752126 111801147 707869285 110537987 944184031 782988381 425140753 771221171 271327948 552986045 200277251 70628569 286103755 90678422 649842686 144068604 443292500 966751681 610096387 651609052 769579400 306430535 161861712 735299590 556464454 459447791 381575346 62035004 649610722 226209664 552667009 352661443 924224075 861417662 33742790 423529912 100 447047082 116668524 645302624 284860344 346982638 457429894 507577929 285702647 372085942 643334376 590232582 432936345 905418587 737136019 533035641 252981 236060095 710704353 194430425 378643588 764679816 122581782 717973882 597309107 29589214 192232851 720671559 818186111 154282520 403667181 680818770 878927339 842830514 820630741 111296089 191198146 446477864 202574734 422824054 118302015 981635521 578327278 20044105 259563645 71355449 60577465 611851303 958574459 113791243 601599344 317187423 317332286 66906378 97654425 598672858 735452699 660249283 481303992 758706221 808747142 829214347 100017944 988329591 839428343 372242784 115073212 195528592 599440218 65132133 329836870 992022327 539212972 36071321 853560476 89829149 65014589 229070464 693437236 20312109 949614029 136724177 831586325 86855458 940965464 490084810 5008788 205476751 18040047 341247449 283796763 633240520 824220171 234040056 641416562 443482224 759343769 858121061 518055827 201172596 248946965 100 671066826 328524378 613329974 789465492 747718382 878968477 205627933 14291767 749823292 167047239 452591837 460795445 120227521 45400470 405960367 576900915 770724722 424803530 120721935 164776938 167533602 406715897 67433021 279791245 656604750 547585187 588592146 807673496 548468058 611308888 743241478 521666716 978995121 132792900 574798471 643743026 792875500 330603079 145756136 533290978 461707068 139643274 652973658 634957729 920252205 927442761 456106601 805464055 689338254 848122261 653478562 334802248 452502793 860027250 23684846 879778877 226894293 859371581 802728878 562784966 756050826 679488945 259517303 686457128 319190312 10373070 342162701 505181267 969886652 295327395 401725179 696298394 412797776 343745193 875518353 393810824 132327005 566015525 381872635 138117882 241633200 154482302 967474878 304532486 898373424 963744695 768411188 812547578 313475931 816145166 66603996 494971260 415201176 169179730 337432657 167550860 123683065 713782268 286107307 639376743 100 820635672 390561912 206967008 296756588 610949774 325835113 163436062 174606588 280181728 321413942 516072642 960727333 78755576 314151329 858840084 266059033 264844024 977199993 871096377 632432669 867939698 786534839 55003400 143529260 594608441 863949052 811689138 872042352 297157382 65341833 555867321 55403521 534527505 689087904 696885397 923241556 978734269 696955909 670749566 141481849 297600447 407754057 337729212 10482225 226297566 240899357 239583735 205139300 457033919 758037311 591438782 624450753 271577405 279463600 885794349 875706863 98870466 815625543 991388763 46313763 288636025 816999400 120320220 780962861 726096247 950322511 311664702 449193019 573991785 991425801 464854010 833366609 702197443 911523424 86679433 829482566 372021060 36656738 85266541 910576510 552808643 783235716 910687508 987103409 563965811 826235518 913774274 993202709 242507459 39000458 18726709 379743480 362136374 99592213 172468285 347208012 275999448 748280785 815626239 611910830 100 770019629 946398128 964163880 782977255 820873789 283599064 947597380 555636466 502825744 615822649 918162694 696781990 136192563 391762570 407592879 655504125 232510596 589229296 373244020 399871307 211603722 699405436 620559311 222913586 52355344 987849701 152535770 275206380 87643365 146605574 491212784 60281341 781481907 277744216 916094781 453369803 335170066 162997365 172418160 650348982 79789537 372444682 878743790 650728163 998658217 726023166 762353874 487507350 938603056 94889584 438074103 318252474 750435549 70276965 103607747 558838414 726101030 406222582 158304039 510054426 759900712 347032271 31010225 278981641 891613365 644837079 54633795 17545942 273930267 816413721 44843853 455331336 911988410 754742302 623403097 665058398 570546111 164433177 744489794 827181449 350849587 978867385 447899595 257745631 297571941 644336251 814501941 535649839 386301997 762296842 144186069 716530283 342328228 53437226 118007498 353752156 383434554 97908083 837950611 916694086 100 600421129 465684448 892137594 618415995 577116269 214149100 189188160 386048420 585602430 809559593 923934777 11554337 533803042 305026762 399742196 730970003 542926299 147237581 202531897 664915458 309449853 993715281 68836335 227521848 707189519 716187063 652635247 267500791 204188958 317806960 850446594 778953436 410195291 427940182 71255784 372147502 161172450 487587189 815732486 309495371 763184848 572383497 341322226 656430341 804006496 270275172 911798240 820337872 378567937 238935986 463146263 287596237 895987672 30195167 810403088 385610232 748876387 99969572 130244745 161215604 347431889 933878830 108609866 809119101 632718399 657404786 675918143 355402072 687594876 201894736 600976123 407953924 530223475 298778007 749689489 451872214 805347723 95128022 86528399 531433147 922912145 525951646 692225163 999946695 964627917 854543595 233202605 862745348 571226879 578656765 158900143 207025534 92380200 760660141 25449972 346508386 516445539 761720782 258411866 379152940 100 898189147 622545745 116341589 844502100 364264482 345807103 159594435 998593349 521618379 77500606 894705139 549598630 7417705 410322914 29825443 839658398 11905165 582958897 266303884 190942291 610931007 124592694 637294902 567869398 29459946 416423480 861093751 372275882 264228934 113585565 981808434 785916377 868457249 802717745 143360049 457242026 984464563 634200901 680342139 668227718 124019750 178883851 601222582 277029444 145505538 609354882 926238945 821823121 71172741 734128608 113092777 833811749 407583476 761147653 556332324 917484779 911166965 531457729 99396439 220566409 602711804 760536741 293897433 470913812 795669361 193016876 403934910 4303587 178146131 222004919 304492077 881602568 124941315 507583371 999401032 268323005 54634400 573245602 962592657 66922996 644152374 687518416 211715437 925123151 456291410 97836562 719351481 145939438 603396845 254647553 833625156 939802834 857774027 707986991 835150658 26297813 832864827 723505288 167462422 796722890 100 888892712 924276678 417983610 677653302 659573890 191248014 802471325 170732833 920540691 461779824 159154162 963900994 726356591 912878760 752312467 190319436 995071741 819304325 640243412 108938114 55301720 751584319 745406446 491753175 403564964 524724383 630982042 645329925 35298601 100082291 332758908 106582310 455317418 344213210 589574973 820430991 416258501 265334954 551089201 450002138 728766214 42945616 55191185 226048734 885083181 130046464 409260977 55845555 525819562 643705035 541561794 62938582 912778906 126748491 626180383 245909165 427385109 828600957 701206153 613391110 494996522 598196987 810609467 349807729 601626920 846762288 159756658 126623576 211469605 461659101 367625320 308702065 719211704 3635910 603770237 920128120 398171485 566264284 902100324 27251147 196333093 656580894 434981114 24827944 121261634 152212537 149514345 959482808 939297053 556607408 414292733 775147750 413160336 836008648 861044958 18896590 902184636 754090039 661716081 760250368 100 601615960 739870615 652100607 665359740 986428291 739181932 896487694 319134119 997053886 790953543 618309073 534142291 120219102 197241004 952321144 609764899 361519149 782448046 627749564 129841767 909432290 620712202 442317369 813432024 873988418 954226886 798272601 646458928 25787033 801097151 997026600 737325416 626922369 916555868 438142717 761481367 436489245 750446624 856233338 459804759 849293226 470958256 621329052 465852602 158081957 748971441 803068490 41152502 358039809 230761621 167357510 437483651 403323740 584745604 367795614 132985357 475603076 943659917 195944724 350047140 646781223 562105632 335100351 665192001 45596726 210493114 776580138 848959879 713765407 564809453 515733254 564988829 907247247 759222255 404750722 179440540 366344209 325987027 291314586 150656332 378552588 127042768 355107775 300297551 891550826 902227499 841705441 845104005 727595238 674551693 953796024 116331611 921335462 705061470 200990126 444403145 394088329 474929284 308070700 648048514 100 391845745 391910493 306350571 31295863 140253103 777708643 479016002 191608394 831818179 678011046 873669428 825675060 595613825 547632408 993005591 244962454 77429754 531162071 476596694 18966240 703263575 444353801 960059686 286263918 115887035 845507497 131212877 559268601 409300239 138006118 271813733 425930025 363058965 314608979 861237547 558278844 488791771 362802952 14511586 780931946 636724901 11507602 735606896 965042581 856413106 130930945 490678580 232987496 587662906 553973795 164617351 885974599 23581189 687494981 739061303 34433906 887780496 316845348 425503808 549734143 104004826 413132039 650037052 301657097 80076735 534578572 806936939 973887185 494406059 536252356 918286329 184707033 325420213 412174830 231483308 920314864 853474173 308404235 882797340 205259574 959456223 708280980 40660088 895481404 278813882 355869871 350639933 890005654 517276711 311511577 86588163 371124495 464296499 948194988 222570983 965966482 809687786 242400706 353675110 153007826 100 9182969 526270379 276434340 426866141 492096875 182743218 816492530 739888443 609087651 193817334 664512798 18081881 913462335 394610563 652979733 515118730 676271055 927631503 984510120 384789309 432760851 37263096 46743686 480281756 811022040 63331005 888972076 870733872 860293350 199280541 266550486 739120925 492708592 439245571 512576299 545708014 839728386 621979850 615000250 314894065 333295638 864416104 582242109 440715050 356929728 852174045 409050614 313828110 428642105 336196517 463348322 775566851 251748636 605303854 568893555 218510149 851909215 904353916 773118428 428743330 983541717 90143676 708277060 380760879 276584643 690578792 905775742 597073696 37751145 985716797 894420897 639691380 776849780 313300939 279176656 700108658 115440675 147222278 406564183 997071805 748500221 72280259 530644259 675836437 970820398 244342089 934973742 531164586 782926969 423677986 134053464 447754350 528153251 597664171 475752939 523511884 401599864 327714442 921525562 817697838 100 672162158 570818971 907327330 242669256 571239404 369936949 423380171 587625474 153462948 904533007 658546284 448347964 146116884 164411747 981381237 50672284 128436794 810119647 274171524 624680770 414772680 266754467 239168476 997677003 616288120 327849425 417446565 750943587 462861139 339504795 497792212 545739490 708374099 862865850 321372346 680496358 609868073 372332661 857677242 308572071 851359322 976538542 839252433 598669580 455998115 258942460 152004268 700796959 726081662 457596204 423389650 633644031 491477212 513669880 944010863 271472376 696855147 460611336 341566759 922728197 236401085 546481402 82734093 840137854 139649096 864015164 154359797 334916933 113224331 123787869 960672744 628333802 279632959 436877868 716123079 921869600 527830335 791079612 78856656 202655459 527852299 698404691 195008976 272500932 772085000 908721049 724374625 885217433 663826211 388224271 426863714 200362637 263481306 997710883 104836639 150558202 112001340 871038406 311714193 550335637 100 51489354 758056008 502241222 547369518 417221617 785684059 103329209 631079202 848611229 147989327 529794779 695440255 202206793 830079388 61574021 731370573 630002803 259308905 723292737 318432934 911205787 53885742 535040608 279970266 623479624 934872552 721278576 444374609 348458571 260321764 943391745 726417488 108400580 839715745 882040598 963716517 504332647 529746206 987472536 941491209 265708626 345599075 826337564 474269158 689664378 417341425 647916928 597867547 420776138 384442554 537531968 141838043 525564801 23191269 441111272 519742053 487904877 805081461 539484148 684615239 803300641 561488729 724233434 90988701 938582017 682154094 792824725 893976626 227782667 481151494 970141798 1057365 788479888 815073784 510131122 537215436 625283657 839482289 577384653 324520623 782054356 405180452 271866622 220015354 663308247 41664514 813712020 532532027 419527934 185435166 272125424 667949702 483540053 742599549 996950023 591390630 332753686 413356165 867668606 538886742 100 167990778 794823213 464942436 436346313 705464657 783687862 932415402 774183722 643010940 936271124 127506353 297805628 750291296 586878869 934583248 867123990 236808516 340216010 925711641 738269773 990290884 896904399 869419990 883557312 157561529 4676393 464861540 297259124 308458108 950213263 83697649 727208820 712659668 767962494 357539034 195135247 649119719 772710153 179167180 240485147 838413224 597264354 312713628 906279451 405403903 628992431 917090429 158996805 487033832 89378633 382438868 546755203 546666427 962044158 684740648 599116776 827556792 226770122 766543931 774473707 498238031 83587821 731735221 574310113 860887071 779132171 514741388 892513569 100796315 106839871 530880112 573096300 534067367 274209311 780039933 256140296 150376754 994174897 185927192 83022722 833213595 714172920 338990961 104062968 742855635 96343110 528136884 560069632 82735433 991889090 871479714 862457091 64684441 691159017 854464561 978903452 369897336 619283039 632630042 208573048 100 608210260 184639179 965860653 948447696 407777291 606268067 582017553 230385332 902490752 128952675 45851379 864324145 34879548 566596160 253255235 190298147 964527248 98381219 393016015 552118295 991097201 727221455 839232353 321850262 863068896 58263628 443285487 723312436 381765497 629157466 701981405 593193332 737733450 797099443 83765844 614314666 28594283 342783598 384952910 251631673 664681735 296897654 207965262 353643880 639036915 687599581 604476478 823316295 188016293 108672827 22421687 810472797 720163276 426674012 993286996 967426246 423983439 688742820 344502006 655586875 86146852 624112151 966521079 650838290 29836203 430933666 569090602 239332679 865786849 666798558 525108135 275359494 385658915 564114409 370899682 88831390 860238869 434994656 332241069 612409667 763178890 249155974 293192538 301840323 209838290 500820737 772805967 888881010 600688707 6011681 54726827 558167304 639140128 698219357 535562210 125158944 956081093 903313439 478775897 751119006 100 446859751 367429938 668785411 731558175 419536192 587100332 713373142 819511026 511610618 500555978 969667931 823560188 2240399 783919492 986038906 737845566 478260237 958893175 522327126 480363299 831804098 570987159 27034476 722350999 453272070 733765047 875699941 351679563 69171529 259473348 380977849 816695820 791024686 109896362 291700604 917026787 708273069 849312595 214006474 603397632 5343504 394207562 597372768 523383021 881004485 836465557 541988360 919024881 138414066 527900106 376807635 406707552 710110186 225620636 823767629 63659854 84009599 102687064 720637051 29216899 850871095 510770967 291261970 202968047 18421132 775373614 443718705 140740547 25890132 884331625 191352813 624384676 381950428 406721539 523386209 719109381 803610169 960790727 952185643 804112665 367447048 156216237 15954589 435801615 858277263 861811918 455555585 651755758 950252825 267176760 727718336 117052016 545754391 529696645 620856746 529694508 400946251 311962104 541316305 681105427 100 318718087 652428751 951974282 644702681 257965900 636843375 953707361 556253467 409936727 932400544 356482454 595076469 79170330 792709252 357190995 374490209 385779670 886571593 713480731 471190500 172117542 131491218 108388271 3987224 273075276 149207507 327565321 265246560 465316782 600266992 464133250 614207364 445386959 538211761 41718221 936823681 43118003 896962683 496518870 435074497 784986439 192607816 715324833 287518766 328788610 260484459 898318730 48678061 468657435 951812435 970680512 484441980 661683044 718609370 731682729 872217323 411868054 887497399 145885725 503394850 980856835 694177782 621475086 455567428 724070187 398551580 412362147 458312495 786112329 659621363 794976527 642772328 614508860 506916396 736239748 809489780 268206681 429734491 386759424 424827090 305281928 521250229 230825151 12899856 134000507 287447532 228889298 719558316 197113704 130211970 872019884 293100079 925602443 121115764 106035614 176333510 806963213 781716892 793486957 328048836 100 430537078 377116221 757037623 32662063 383000272 970093980 793673498 655623450 485409023 134877692 564368773 249697429 519988244 605863843 243577228 893424931 741984462 719413552 597540626 682070260 430970516 622130210 430579780 57718882 106964088 110177142 113591609 578203064 538134925 444878983 726678923 199176541 615175913 1698041 447541784 744331935 242777069 767637937 140845156 495756057 405816732 692352585 400679040 666331132 59964078 179128665 234085925 125189957 638698147 482108114 488300870 552616485 512905310 927304913 245992096 514897966 834828014 561924273 590606686 112313887 241494730 143738531 186773003 473805493 189873496 661323671 697427644 998999951 858706195 480983690 501312556 934964844 227806287 716057358 420204926 621277902 232625380 268954409 940463595 325398383 284713522 521278578 515755549 745468296 484482157 783441969 404374383 838940925 945376832 576375135 543731771 600713650 459351594 349190600 438707986 621273357 440922749 865879065 827467828 430986377 100 175959255 379765839 475376207 548723872 542376642 907097624 693672136 533075739 645729980 222838237 133914509 197455380 354251327 63012040 436123762 150246767 749179914 432551478 316299438 846647138 217183980 746152499 795250612 37197114 333054939 469896078 761103305 332703056 793085917 220838611 750016111 483315404 196319768 978849060 316818064 52802058 109154915 307021309 974738124 799862624 337316049 544255425 741528439 192310781 765123273 98380076 607214258 294428638 389125161 223686216 70448469 641735298 716402633 396774176 859432047 210066914 825772046 162125125 292075427 271367418 762938086 646562201 233252476 164926852 497621522 29869876 135089379 705560807 131611468 993360559 741057014 54423053 866509691 961392753 835799942 272412993 350407422 627765662 752829789 299051301 852112835 644322064 628828496 275485704 424234035 643531247 294455453 827968644 632454969 971936163 432592951 71640044 945376964 266550620 450561128 613979514 989015571 306804913 74744819 957678417 100 337967812 553119758 209548450 438716723 137140026 326756652 764977215 735246487 908806478 292107365 34066869 969400998 340180117 292582856 272259330 435124981 831104118 424228605 913816046 543823183 900026382 568765069 532826941 28922861 102763276 957070052 224222401 174101782 142795873 526751670 89252971 205214159 213774830 512457196 854406848 450196079 478518260 758602996 222489568 423183188 836405920 885344691 796269003 643782000 556588306 39329027 939258292 642507874 650177275 663741774 135347744 904139199 638831622 665602671 458501755 792693110 777067372 575123175 914396749 249878381 479475061 140123315 945194221 915285945 328552532 243758320 171135220 595888301 798037968 765402341 784876796 495208117 157134109 804451192 873027616 655922137 5455370 308573104 186097059 118590074 848129952 626394499 531492507 88235290 264386903 698273822 363203338 118109798 289351527 581979743 984322565 741739064 890526498 506710743 452444118 575765134 10702192 725121123 857879574 706873564 100 683883295 413161465 334051035 493931750 736690939 500584152 705122984 468788627 387011486 312520229 779874491 955127678 196076659 867984337 117811810 205960601 56495160 904684721 837520337 955552000 430195255 343870136 628301344 492426014 195918099 606419072 349986635 627240372 547821894 671718127 45995534 865345348 963007057 580609298 48980198 695212940 492206494 339326417 240027662 91317660 917669552 579034126 912887156 845100909 512613443 427896408 261243495 370747037 859928923 897439928 720978710 399628873 498613888 772991270 496598760 137846252 836617573 348890366 822218388 29733811 712659911 363081127 22928902 218490506 692554408 351879300 746611966 873054191 991653305 747738805 487705453 935795887 956528 430462241 952679926 19217199 218550796 753798285 269232146 358839111 130596572 450748771 600771022 350597344 691587855 749057805 87658038 791454714 838349181 102359611 213902481 658386093 941158872 617143651 513409565 346448720 863990670 682721335 381684239 465851635 100 974561588 822411596 839039307 308208575 267225779 583931594 59209655 593389709 851531366 977236282 50716239 821463404 960642098 371985963 597259874 154495057 680520226 69514004 936823947 231267919 167230206 268598600 624823801 316146479 574811027 214195685 299492512 693206463 843484314 911633361 105388332 645410226 16467409 659115033 15433905 134171449 20270675 348824922 951179631 703336376 137508430 828203311 894837987 135065480 121669583 508247985 1346026 815512481 99722031 325600629 805866883 468499437 999087761 561542767 976745915 96432155 489478126 276469463 137256488 935560670 290807258 942375574 652786802 220447848 244187514 908063624 581379910 540104506 305221746 613549556 846295432 257862999 162957602 916731692 289979569 510089785 42348509 944541181 840014937 661738650 765278387 520846779 563520709 195945724 184558931 910699365 117102256 716303275 194244329 820121141 156808715 665555648 743316724 747977133 152650765 894304638 395060634 185050177 333033236 999472776 100 633755008 813135476 824975888 261342927 825059611 785707379 882793886 48883014 566439425 559572612 671201888 776591534 32601593 648306230 204671499 182534885 587741212 229444411 655180514 819552543 149627045 456138348 733904429 943293166 588598963 980677026 90979597 778523832 621693656 57251604 146611582 491004713 352324406 603301733 92669401 828455763 651641909 819683243 936158856 845930699 716886911 514084980 535418103 881108170 556380611 587059869 811035582 65330863 7033344 647286967 760002247 347743016 681065894 885148210 587503033 802449909 98389170 594507105 502067158 491944488 562520148 602554203 363057748 451220876 999491077 825821225 952935402 929530438 680779630 200047378 373552157 824725149 486550469 557612707 348613163 702617831 786906443 967665178 787741611 884509602 620529352 5509161 95633241 807727837 668428944 937504418 553316870 621755374 225365745 586329004 285208686 260018532 899372444 576605256 290652917 601996653 385822683 177538426 913054328 705987244 100 423021073 509502721 742334856 802609225 527464608 126794027 357668556 819396247 441080111 146513920 726476778 599807198 561872480 510430065 663495794 885187543 739077748 350173747 186734745 862218493 701820648 800089973 468618406 402873835 262232320 907012939 306723704 585116003 618956306 732603020 970836048 217662890 655575796 139060659 334772690 188386237 358962899 580770464 493571065 581803369 809187737 301988733 179342968 495925426 788108812 503222043 983851902 396116201 143449452 438124391 158411247 454850447 516365890 461219448 121385273 452483810 679873009 285884180 515841613 976989375 468312459 654419300 252688862 264893111 597331896 109898434 687019985 230291609 823318524 380360866 366913609 752369001 383358880 120812022 797972542 461783128 212909105 709380134 97371213 75689405 180491133 469589896 237116328 751965335 472300599 525642009 216351614 606978868 468101418 523988599 68152407 930998028 652446632 92463094 771160874 995181768 918210499 129153744 221134496 358869540 100 3025461 401511866 562336818 632261542 138298471 5348425 477143560 240039195 9107053 730008345 546775593 832371425 924754350 619172800 139039504 230170748 336641919 951017501 742249722 212892170 452910453 142934033 536820694 72150525 437945919 229393289 904448155 262837636 532365083 112677907 638874964 44127862 12449012 533413242 611567181 6302800 437167846 928735671 137884970 952657117 686205028 682081520 805359336 444934342 983132048 360640657 837927134 487124457 524511792 446372524 466873389 191707818 848169052 884322612 450226717 255886158 316462929 890671441 341263320 207436554 379680635 239097181 600815645 760014268 720604937 20489071 366414464 509705500 435026815 312868718 897603858 809050508 242540089 331585056 32150816 909146892 2764093 494993470 78556589 164986813 366071741 346641860 606232369 381786538 112324775 425077516 859967731 46422060 537672416 865498851 402594110 693909359 139639217 563112725 822302566 254260835 708965286 232520178 588959968 221721555 100 954848336 635425964 558894479 795620275 439652883 593549953 97957883 54343670 27829631 412908416 734761683 22437245 427027667 340253125 594648952 363312133 22416816 27716439 923573169 6773181 297354134 212300023 895821199 892215222 24923747 724595921 95722084 786344413 519779891 103981479 318341096 617211526 10068612 343769373 4512873 736061845 286736468 566898935 378696459 437454023 172002512 119364953 938228010 899430427 739078388 433255 805375139 346264095 80684968 828473249 628844645 424576097 741730590 570072329 205890537 122380376 621131790 770990209 328979675 490809192 830433707 512104784 578633439 656742898 27339606 871529207 709673638 837131452 645904464 293771436 35701309 516993164 498469467 224868512 228322319 680341540 447440796 122199168 595900837 492954261 200594382 62584636 10195067 884357763 292679224 974490521 534137044 345700647 972732340 612879294 476927316 481338696 243898587 567188851 481883611 744161941 54025112 606137263 496907977 929400148 100 324397219 437697970 913957074 701226060 61968825 283297523 753913700 195239352 496647037 183009588 186646473 132772672 339774126 476232000 531243811 516109134 103799046 219995809 803591726 550463932 921872923 167950952 401911796 793667093 657526594 118517080 723103676 314491814 518401300 486251732 556084487 660785630 283459701 537802241 12458108 59077800 626016551 514701646 946662477 983473689 223659302 830798633 292132567 771002449 62214930 101539324 64314535 957431349 780609071 947182378 160941583 857005504 273892318 862877199 328438451 166505762 493207492 613972396 358012891 484550639 855496474 896182096 799335872 51154200 949335021 496265160 4181068 459812351 115067559 572823749 873059384 798876630 973325413 524959399 103707003 715016937 909262407 621404596 686897581 266021347 571877344 295329374 978951502 34726978 440260431 719754581 1274639 967810881 937670952 661132289 357485971 353840398 252660151 436866640 408430704 823282091 520047354 139511155 280580175 264023177 100 993341760 299061542 14919874 687505706 976383358 241855827 127018878 39839702 229677661 542004172 334630150 98653578 593787655 768585923 781172080 199145735 7254251 582603331 945995999 956711875 345265410 321447057 25826427 457652912 412286765 590892432 638306126 837959882 705812806 493514279 62238643 212834987 475638730 212411045 877261660 576977325 219277922 536104519 441567811 843130043 170348398 312117606 573988269 394922970 600670408 971628266 118668248 600464358 782063196 984077301 88437596 872632242 32922498 31038876 999054141 74952572 202986018 86444106 462351229 302985084 289393751 643741381 751845193 971613928 478382357 735257943 921051564 375850499 150844256 974080509 493641610 151282326 426617749 324404178 849319253 67165068 78393950 448585755 957548426 392517766 949379326 828245025 153760335 118272602 403117389 875170238 992939070 680452811 171244971 676148258 75649502 498134364 418437274 799293201 235939907 600346941 156274146 842113140 991610274 997904181 100 708769298 423895261 871387682 729858304 505219464 901916188 702251090 744672446 446491741 146364949 266375933 140233621 19843712 139232224 167393388 675414836 902879213 339366109 72729859 509670692 965900421 137086380 373403458 113652057 678293353 896656691 544218806 900177581 386153295 317173577 52526700 65352035 794885580 536364843 604488790 429800841 43371788 974541002 270665442 112328799 766760061 834041017 78558524 92428666 89501460 744149124 172524754 165915963 484483488 662506655 481147744 794734883 777763110 118225510 761033089 376237596 649561034 668116154 565039663 537540335 316476934 1086051 282332309 141344232 210658852 875787317 359068853 31777342 75556175 603207016 213373158 338250096 584997438 416603311 674159751 74790858 496675217 787016255 971087486 563591463 54758658 218327392 576586645 805453470 697298496 336168033 340535189 424207689 304115932 23026775 424193346 95777636 413793005 34130018 846826345 781888818 975800266 135149441 870229577 601959122 100 76376557 244280320 589183297 647501352 402478079 962940264 610949834 372536336 548650563 518346191 818888014 929020966 435022262 910436282 949727237 947474343 151046330 366988771 866148379 311159201 75587577 138308998 18497888 920990758 797807981 945932140 32761400 826406571 406445766 880058202 416085368 682296085 718540907 829759589 711770400 620385568 416226201 286733422 232375366 76869557 710168358 329463950 114596879 281502477 119995653 127086357 355408275 771242963 966216080 161183511 262756008 512437193 456618460 399239594 908195716 590372798 236340283 13248574 163139075 910607192 953593090 387829254 911289877 953018060 447986971 845997753 901301020 572479074 615581549 56973284 23702724 323797450 477563531 403917054 536399709 132055354 223647489 993481078 639827024 764296020 502910396 552870738 719239943 397058354 73775151 297029607 896234512 962026728 704761853 821593249 190102925 919059960 970578238 893049601 135245623 402789685 574448831 192565054 513738891 531803641 100 679602554 930967846 944773614 130164418 661042144 861282811 595048921 469114268 368107100 695333399 339795208 439062612 868237198 58625774 665443942 3801323 216922844 554600873 421068319 918668400 331145163 342811933 332147210 720313763 371108326 493685781 602285831 242961023 860191598 864326302 755244577 681834881 347204555 477698632 90906859 945756154 54856619 517043682 882236980 24872288 41698746 373044656 32584135 514378435 871163615 63911431 705205113 802430959 757410190 488580428 704014417 349779553 455512235 900223745 808175746 418480827 598144674 813573862 835018797 201338898 658370714 847695261 14444697 60290739 269576891 411484774 97827712 359513281 674327867 283668207 710212902 74614879 319863382 434423457 57347363 117302326 602208951 975736371 861861132 392930095 914969811 78338542 730953425 943071302 120642666 333099641 335399420 338183093 277876960 410960614 595501334 669772405 870000653 877711028 349812732 304512405 631282187 406368012 836363428 70507999 100 895747684 461039806 830823697 194947010 896369047 444666730 889443188 343185047 202459060 220725974 697442783 339597653 913126103 723687709 108036996 658574588 190640753 169891365 907466436 572991159 588482816 935905361 472124360 151611683 794817176 699316236 628718540 349558936 247040200 937661808 689968867 6755297 357143158 931180701 175742096 687149038 585898943 524001206 660077696 982621757 888746234 350378117 568768950 426797970 391139587 490850423 593032408 694739962 110213654 863348275 249068596 647974920 27448939 837048629 625908967 763572275 321131605 658163569 827215654 425306113 90025064 717668252 717746331 35859328 510553942 542188304 858797874 272732578 521888330 779853244 736089567 683783566 336769493 26625736 593969385 510407450 262414633 509858164 820202254 140249950 706256175 357284873 534117660 766117157 496635560 909559138 224099229 745057790 796203629 550688708 211422688 205415954 160018509 917984017 335937873 325879787 720578354 184939419 727617524 57056448 100 897801298 744052194 468080207 376968437 448572110 316757003 495630284 562914048 575090379 981621251 164036546 272386008 154280720 312488395 186459287 502502275 201563906 853033539 535362753 891673783 850876601 437397505 827065363 86799270 244560204 527088329 710157852 519523663 52538475 785886148 414845693 159563207 975161997 337353881 542987886 565439169 659657014 484272834 971233661 147106356 266747318 420474576 83717065 38170690 336888900 268058421 90074868 102256019 381747523 281990978 231414989 463737125 431548740 932745526 620833606 517625371 645801827 181526952 433800973 118211835 802013029 699272459 103363815 118566409 914459380 449136253 930686951 798503079 994205470 685160731 126508227 764731511 939959346 800983308 174506794 766304765 106721555 619944832 968758087 543455369 244339779 973047445 888699577 447373822 241679698 715353107 64685259 139990200 737502212 629665434 839949550 883352138 651886118 790688545 875759182 894338144 324756048 161515792 877784605 193007234 100 173491512 511446924 180392665 638889470 203306366 479437214 150864820 469880252 108285625 743787248 893892026 308905286 627534467 725120284 673617320 427822561 138335422 484770032 670806569 168306795 665439936 977283987 859102820 543000610 942509313 906699042 624196597 403153231 761805075 975058226 516379381 215844083 686210550 695552335 679601864 74162689 410442116 262781029 303893017 643907890 247699917 88918222 380699429 548518214 26372118 774965395 298169189 819342443 210871759 32355715 112359935 70497393 520243749 72703049 151766047 347094418 347592836 996500899 111812755 548857659 237371295 971801733 845143379 393797455 139773427 694120464 48224198 446759543 974256318 472703014 537176855 49568348 622001605 684157113 884951057 979888312 82346931 888287124 961638132 621657907 59442261 314850324 707190406 595281845 325831132 696897010 76281370 998798591 618887392 462643825 596546210 536494942 202497527 564380851 252387423 657957158 756281681 870159491 217049423 829015098 100 664092103 865896209 65946598 160246380 203539164 837164153 161008540 851079824 323885506 280638975 914946714 85233826 968837646 719561982 100704984 326477948 381236711 821900120 810762686 554411720 289161691 815560943 695713037 164495522 566070203 353986979 310429222 610478539 105705134 115746778 863249742 578512461 498430119 475448493 187946822 932679188 645800963 888403698 21135796 160837571 695267877 945090043 914407706 565491097 780398673 873140953 551888871 303853769 308172400 708063521 632293071 765789228 878548323 85312216 815279027 79229684 755139573 854683899 72679771 238816804 391976127 543059778 898208416 601299354 209967481 243266016 405111581 874313651 707418149 154698080 784795842 639612114 256709206 83919838 326139842 863711019 197393408 728498552 436324482 862526062 487814454 315773788 423518628 351624962 55122195 741746654 974007104 197287806 737186438 930511208 401630825 98925941 180193061 41043123 336354419 632178524 49380827 29224263 693652838 660901089 100 475035832 336044451 781294113 394396547 232219279 67759144 751317465 387910716 863062401 184824138 123207780 501996842 677240539 257360461 516756215 843890673 122129577 537945510 85582949 618921701 784676526 12657387 682346217 883340720 996373236 858551569 941287026 175158720 434297461 403070336 567996052 479377447 337407834 693839410 758956159 438441990 686609578 833219245 306271927 401617309 532405449 713724695 398656303 664555173 385043380 801359478 817207947 700463370 37759035 902440033 189355633 566851036 451187638 847121182 909966273 209562825 214888537 840256168 233287942 744727362 290067450 944074156 820300196 776828114 740476785 847942279 808386485 102833128 667540993 108555651 323799911 628019081 281433731 335448681 618825330 223518198 210238847 348030891 121700151 184727544 231248214 941785137 843052186 210031906 124020264 948305989 641638633 7718285 569966509 62724104 804154308 718632052 627170482 839150079 718213330 553403231 963424510 571712274 137578289 937749787 100 454605153 889977758 118725742 594802951 828876426 140677241 52184294 841343929 81295436 297237884 122533831 625352223 243580644 589048797 670995217 260496134 757781150 754826602 353697094 805875449 760821101 13570398 535283632 528166847 719796555 115052838 117104890 591776671 603814268 941607049 93720576 381654256 54038029 155754200 500146222 760666806 213296559 887630962 760898355 341069653 522878050 249748604 262744700 734462680 786921823 549067331 434858801 349009143 359473229 924357721 171595653 454976394 766714365 76630113 87401086 637332001 711495594 242625397 554808515 240993241 678158986 155453524 677874929 132780002 239264095 227028943 250509080 58613121 631764145 482194108 746763316 146295405 383851583 432200962 559086075 81182088 568335046 523129775 863676276 541177768 663380237 219532465 906147822 883644804 549637446 631366073 586668233 790078715 437709939 578913435 414445688 653463978 611122506 899134875 900940988 53091946 680809623 925098567 32983443 5741921 100 914739189 658678848 995200888 39386821 276897707 281624662 459460300 308147678 475456799 194405221 110034544 299792295 131084972 967870480 598350245 435696498 401145712 50203869 746221330 761585532 47709764 376572998 947279862 358026384 576511921 412328172 636204134 823411301 521052170 694400699 196047537 272134725 968413050 825390470 67607453 554779522 898866004 864434299 601130622 364756875 821974003 575848675 584923838 251072775 898365573 181922960 409971021 682296459 210640371 269408891 69754922 351085589 108228346 984734563 305258714 971034870 519114023 105252323 369930728 134129364 537679252 339531443 736044460 911435070 411763289 665911562 298015534 59097418 414879461 109032643 243263124 132362702 813721868 854071766 159713817 101931895 998855688 549087170 805703692 719827736 855209088 134174647 298601579 51944871 746500538 608488986 683645878 886135971 338642352 267988506 999971734 101982016 396132655 668468745 670419010 317937440 896141874 734321056 219288537 701876378 100 890510371 361773090 845778386 582627508 278008230 656172678 352974606 736071392 436769539 840072976 933336620 194606820 155763489 31340165 823512104 457556981 270431338 293209973 285698802 493324240 458666807 891262846 20828831 374034442 787773666 409074745 694117354 81801582 337112711 738384350 761297601 462150042 298585370 871569632 466730937 608594235 102655852 248401264 198794058 189621941 269976549 169083541 164207405 936745296 455694492 911462431 179555631 659368214 450217604 938620452 666663573 16751988 246859706 329634983 249683960 296820892 536869689 412271819 296262558 538093659 93322896 510021642 929080061 559151217 482668094 622451411 977824383 286375646 597416196 54358883 710751953 197669885 729873041 610559636 212669794 718964557 153455104 739807166 524610547 381155013 291958372 999483341 924512470 46228410 809427883 881520397 429188393 348208799 741991250 165286609 967653726 250780080 444578416 371814958 153611389 98624040 317082745 740631229 52593315 444664682 100 582783649 106120431 525573407 524012581 802684033 155676503 494300584 63168163 157847651 661274840 361188589 936851390 49940838 412832067 706470233 464244497 897420884 651129120 802932119 918905932 505917630 112601191 53374369 720790852 931239115 458953523 419365842 880025690 121467324 705031150 786957210 695063992 670294939 630690176 188273423 927176804 610630387 597507763 275320371 857778073 835276393 614882840 855449017 530154600 717107939 13027909 871593525 917358323 832144716 647015158 727632844 728271832 280587447 240144062 157267103 423465608 668486123 922926479 271468684 404705116 426602446 152464427 355487710 873880345 618923534 6113322 812469006 564390793 306480460 309167888 634580130 7396248 344940885 661084838 626411870 372582926 865107026 475909853 448305073 339138155 330283670 365245239 226209533 38925488 17334044 47152098 408801777 18049369 273388083 724240637 770575256 283633235 775483005 919290730 180073158 543802350 609566483 493607133 570268478 591092220 100 447070094 971381603 214639978 452405055 238233441 202241449 627992690 845173207 891655557 923393244 592701111 595088469 490827226 361655167 66166553 370578571 457210477 408124915 954538072 78852263 400906172 627901238 987023047 50149572 140859197 309185346 69522522 807389672 702827656 501439356 781713852 778871710 834049055 610818828 907996465 147722811 814118364 649722705 36631964 180196654 592239960 195504186 661013031 535135545 604030502 65475275 925338294 266602012 751916950 392524017 283446256 33321469 577132046 893505938 482241594 505003179 876818412 802835664 739738487 404277956 349331883 696926533 545350515 503091168 545661685 212833543 963706866 787794597 274752130 252894138 459167635 645827876 742316072 412247187 449024700 492623926 216120350 870725207 587654207 359492519 487972052 257322632 431459810 336000405 592199083 408179295 699970065 383489285 625537245 904673008 209826478 265669833 162382779 670427312 797361957 779163353 105428689 30620604 553228083 131829786 100 953560777 711666115 861697129 519826036 20051227 748635273 286185599 780929031 318736911 207030327 992790888 721207023 987173421 622343442 654869469 646583781 167157616 867177980 551280116 951627669 615466516 957337026 835648163 54265555 297745780 473661054 721547604 489382152 727480473 918686583 742845249 849956540 439224314 414828899 151764721 801815429 30130697 417338054 255695145 377402138 709532832 200409500 682648320 619517088 428598798 572342705 561085484 832519610 951984049 268364838 17542495 776086946 550550983 574561591 646263881 180091745 981254442 125386773 64000909 114867596 867517115 161994159 880274505 494987356 544425991 506392374 23162968 174327670 623128489 143694116 84385325 402760835 167276799 138295677 640629424 395132796 669043217 787635399 957998383 620260833 956602740 304037695 743527718 277743075 188150307 766810930 827501215 174618700 374425366 344965791 467989331 837924196 832278790 505514663 319280585 305680378 917611802 694123803 826716446 559954513 100 779219688 313977864 483555301 787382701 973757058 813667151 553735144 862975514 185239574 692128134 999858782 660278895 7593419 454970378 801591963 234465551 197222413 846848411 210480705 832792267 748374642 168848828 486277521 191566558 449723741 966728443 223602294 560962761 366300166 33592254 565976762 850281505 687666533 542655896 251196281 400554502 141257137 572207509 181356843 444909563 288137208 31809191 933503362 220192773 303218103 539158799 612861069 323723423 470599179 258153099 918895582 763150691 124070007 444445635 452419328 250558209 850547078 848448150 722835323 212709771 847059824 894094163 233337047 435829439 569720688 839189467 914859788 15155857 571405293 889396075 431892944 180465164 11096881 956061366 474272038 66071281 145730153 472120190 421408705 388860849 902511367 529359632 245163563 435947763 339842405 204402620 529689894 441343118 781596413 453789232 807334362 506861731 903078870 685661028 786485673 222592178 527620483 892955728 550373659 990872300 100 236604030 108495233 301878748 40088210 519127289 142710897 266379121 223702606 917148917 372806677 348422880 634374846 779888763 279036948 340533042 342569908 470905398 320498565 107832175 517412442 617494283 658428693 345260079 121883374 678856686 889709759 230146424 536281375 198880436 275488457 659673740 129268845 223650136 72142642 707120951 179658297 275253369 458140928 386874471 40624217 44452249 418672546 663172650 173710915 881930927 980169619 155241767 410953502 36080093 827719089 712817718 411705232 648440342 468080111 428057315 32188640 663911730 716242122 181335845 402345192 643118121 487357844 657048756 371884139 724155176 495436764 903161145 411255866 28583533 644870775 479318670 905183674 921590889 240455041 90800939 811920733 153801829 541449443 994831251 386668062 474778068 480291396 813431794 280090233 704806682 313209500 240394565 322408484 615346992 96936115 367841967 631707148 188557624 103214434 265585800 294821133 432710244 585751000 806430349 291512272 100 211806147 68638328 279286548 451171507 415139650 985728602 854885522 912213201 756152301 378676508 696244521 452181315 814828688 50229778 865278692 47369692 904781945 599012778 863967354 605457756 270794123 512101652 358977889 519034605 518138447 783604816 20746140 684325401 10362533 84997495 590654790 948674549 392596788 825595551 687490385 751036705 932845839 409878202 277255242 763745270 276235763 628490591 454188796 934949756 609064971 941971039 927489390 682046567 770319348 626951862 632290331 278432183 135166712 975626544 483583652 820089506 480325912 247366130 427564535 717438805 423977678 786495536 781123824 559158207 593513176 221899547 651670225 472096315 349213176 705587647 642827884 32145283 66678857 157511152 773526849 717680168 532118065 674912239 954399986 887416945 410089530 881103588 573069678 110006799 287058519 334441073 727898104 623378275 744084703 739538955 275907858 256958834 256031234 214279202 378175808 538994985 991707304 957468538 393911817 341499131 100 282963697 740425085 815508114 675458423 166188641 597819324 627022906 479167470 410278599 59292029 661298814 182877564 248901505 543154809 558927199 916812889 896637918 197740932 631251085 128001717 92627526 577272049 779222991 240640440 561925721 452192493 45869213 768553596 43610230 293207762 982851602 74932211 811957410 404394886 823046847 318583057 804189324 744042120 73313475 170533081 966377211 250841478 566471432 821375015 119431009 127931622 797695227 827548548 131629609 630239110 78000916 37453417 904711151 724272748 344408617 344936570 839640215 551998896 641785761 776476670 369045852 540039258 38020447 928327760 711178701 786971770 567198128 895194759 256497123 5651488 376869489 836325388 538788171 417609318 928749332 960409950 311008250 465021191 178458591 746488039 944966805 568431636 544035064 386342814 591051364 104710688 975699401 450295731 695636952 175286730 293211147 982425567 120562681 708188005 700712624 832189562 906739605 670340131 471218921 490060512 100 445922156 159579074 890113555 902711772 446680518 997316434 597270523 524707748 120238891 877206112 189779167 876148205 636504947 500871097 140553929 352439685 117676828 452202059 957669355 316608078 20108851 665025615 839288734 62020450 703187473 928450922 434898350 109267590 35091883 547860533 632827441 89687705 55886863 823976820 509484603 392030385 475340988 286316414 474090546 488979588 654362897 846923365 102958962 895799190 515491261 740368073 433896694 774228074 71299678 772603993 669817875 288372138 578284757 829880648 106874452 236014995 852728503 766869108 195816165 675901221 833388171 346066449 931368896 784275187 382056181 299456730 573522392 378376320 917321031 316429052 764343378 993093746 168332866 67606084 610053523 799484391 461940005 231076789 439699354 550287986 475055108 764123898 132654754 137672670 455043695 414379037 432374125 305270493 535001581 553602107 780838112 700893188 703131063 965614774 855880364 287735759 744295004 322344899 120398569 776689164 100 764214934 526369696 144766993 827868643 458084874 753237184 540550344 823596479 785899935 757135874 477871971 71516717 720416666 791975344 60390333 620806175 916444655 642976966 199939144 260489489 322431207 840087969 12981852 362443924 763462394 410660990 460033764 497060478 856028336 520413944 549013664 201952246 961132039 205671142 597556014 499378977 903744427 755919637 190256044 318280989 208090486 991048482 51903292 384450325 145117581 929255834 709087189 611629401 870714888 287677950 302537722 463024478 414051068 184760399 521320281 196124135 838240964 178115270 523441564 662047923 758305880 941602485 245091490 232683177 834228391 728528964 691614205 464413061 142410890 188460950 155001212 934634469 244421452 14835410 820645827 59650885 824540987 169034522 165917794 677831959 381884582 367086205 249185388 419813995 135738796 204144083 978071152 722187502 889775955 673682060 372395322 108841060 571832754 882138689 750659682 431944290 59708244 968929126 268401801 360684277 100 336455435 393263691 357767702 202445163 699283079 291011076 363933955 997702082 788870434 142345482 613481407 226185554 812847689 815166952 667519497 112664648 980193749 822333930 62915457 344017069 586357010 350647800 666297674 733019058 87051816 736562914 531257944 953094012 8607174 356292261 589234029 754208346 763205136 249882629 15166741 144026255 681870202 109268800 291715395 70409506 279070184 288304748 375036831 568655065 850246302 912582819 340897315 583927154 291878876 206793689 509295105 667250311 24829859 715548054 561198173 670301316 197819817 810953846 447010576 480149035 593445780 777785423 848553355 981191411 500530796 319147780 382496027 750166841 486689858 841081382 923559647 463532515 73026180 597937374 825757520 504624933 380638871 135367673 638608650 280486823 217876227 110603439 648392829 490812892 128730541 952354120 49448766 261964083 290659849 70597201 345388773 810742008 358388812 55859028 688426420 179149945 640861981 832517001 675894099 102178402 100 900004275 602756619 231115424 110382370 597321659 770166362 260092927 963746145 256915302 51639124 432634261 228347780 125877164 825557811 253496981 397584957 491818330 854770217 802426105 402412306 372006411 135217236 341618166 621218934 844839649 348478032 693524576 464737507 398471344 568163402 68542394 735250640 617404129 438423407 7271819 207540473 985480431 941567162 277752760 804200648 199726485 392666186 313161787 15186419 49655888 387747459 304425074 444252881 918965616 878594105 258439007 828585466 550295499 971544863 817241488 722089916 37793179 949593463 508180078 323432161 665724927 348456112 624965422 304201214 330719479 118080773 478363864 938199579 638268238 994107771 727131277 236618146 68284581 385662395 394482008 904642287 364753989 723038298 710120283 400723320 259683534 818864579 386648595 884634738 626864047 893201027 908453772 741769393 292917856 51574065 747418493 139277392 474650832 399068929 978335928 876285434 668186925 872978490 646117439 857690868 100 919609518 698586451 87140703 242658104 931705203 316163913 497942881 751361171 227529196 861303810 461523242 479939211 20191494 806647480 169491207 880815419 411194906 96430344 32544026 391889448 845318471 293562446 269435455 815424894 475608194 236417644 566210420 553160276 843143949 572755006 274843098 176690700 275201850 959718686 663668702 809501444 358881079 732688417 797198245 582629172 446536855 902329368 399309728 855439742 745819294 928325844 949679190 828635074 690208010 600414667 494327578 52816240 232663222 842670923 555347131 401980252 888806289 788176657 949858567 616141399 296097027 928915681 929045178 757925334 62591726 425730397 700641478 958032004 528440979 808860550 356022092 892563047 796574312 336451842 240489008 986011182 489924907 300083699 62324142 953193387 183156671 406527150 33931793 920119372 572527835 376998261 836239186 407649946 263761394 963824670 421236428 688851658 851860050 726117929 629217957 867699285 116557688 977583541 725605903 29023171 100 707088083 273449802 168239395 616437984 930085162 858050403 261861890 981357159 465974991 320550003 107947590 474458893 771949198 192386569 374989962 478122605 214092003 920785184 633690696 851007615 99468285 208009651 826264077 300074103 748538385 160153470 69157143 613873877 947774369 134036309 217728904 981796850 514638258 650840426 969573851 462966616 985853919 852172538 762032662 910818872 555743340 918912446 416561959 226544367 790962808 557627763 711739741 846504057 780011308 179777613 768247346 318400518 887473182 928592998 41614167 445141966 77157155 619375572 630025603 852574412 451239844 163590130 52540758 552868679 998956473 129417942 510710628 632985060 479776885 218175301 532858859 329025596 36163761 826924669 934445317 305959466 30237459 352542109 855263005 114244431 914802810 10745894 74526192 238711563 960563512 622044079 271886201 777944152 741467743 865810891 398561082 533100971 623466041 130641376 23715334 170376790 236640220 824680964 243959700 230000499 100 629788129 811815467 874056400 164484218 881430099 713859455 704348089 818101227 627656219 857284209 817617225 71920836 551133702 503497271 210607707 137787109 582244489 703818430 808707831 691461047 2710852 112307626 325511544 561778312 761521758 698393477 526381776 811551484 339371583 220726482 116657786 934065986 424606952 698923752 626601878 703577503 545441508 376105542 294444556 958352557 139367802 497000442 144560517 206512709 496897066 86864988 633908370 869947484 207553363 711078130 992580164 268106928 895508699 56306501 340552533 96730070 192247960 948423920 655428884 988275315 780619868 344324316 286862133 959878852 485338512 142478807 885098089 991984534 175250948 452150087 809066014 462316759 41920120 437457960 328823494 962762473 246568759 256873588 620239293 548343047 249361539 829545359 678733125 478336952 140578197 377800432 800923042 834893130 501887173 925722277 824233781 140808616 91478980 561972389 870955892 642744692 506216907 219736146 744665321 715354483 100 762368333 702718644 953077083 823729057 342563352 911996230 517884919 304008535 401593917 452163323 60416599 992003492 267288062 128178615 172563952 888021726 542944751 538934485 921222672 683133517 845456393 618026361 92962804 165468185 680275707 424522383 728030328 308719593 815058057 371672854 247575738 921345487 256667603 704490109 18979928 432246158 988963391 200884862 727383416 302937504 550535110 200928790 542033574 535242144 690226056 689394192 817442098 448749249 915659057 472876614 921672734 998951620 400725274 526962611 140645957 209673278 301116403 224002679 887301003 768652578 245895466 102978708 661336207 4482444 239963227 834443234 716592309 206658418 407382595 697222458 441202845 59589558 390880509 404413585 805382967 123148042 607965337 405229798 663842002 446585474 636865867 822411573 252995675 70081216 559940531 246959247 14969295 442557152 33973409 696917142 520643527 886783489 452834975 362025351 824655682 909305388 927433034 153889485 59492412 120169263 100 28206610 531417252 836422341 797899320 948538316 379328755 834682849 295833855 195735093 986776467 914109300 220288128 428900278 51129602 191606729 882222544 39484105 975809753 755387113 78968296 514454669 606601282 122977457 448466867 327201593 877164034 509532379 730873642 787953252 455565333 107527179 85507788 2114730 576959775 630147567 165486435 219655064 250567314 824188769 299993498 649041246 709332903 810360904 688957435 585254900 471840686 228553220 772648232 210288246 839055868 516094523 689475040 335899404 112304297 485199098 139124237 182781260 665507371 826712329 735337211 222997675 335981556 734870617 75109064 872692626 556153505 712599916 864830804 693591635 286021880 872542247 255012705 740835447 500582592 318981929 869166496 734247979 473617031 680432019 996647473 621763738 125805960 939032990 738839980 767114623 460347249 154576978 74947272 594518248 762140407 45650718 312619490 454417640 570543527 535924988 715078067 535494685 298239438 690644497 358334360 100 480970293 676826447 194528707 625427255 812558901 956031997 403209054 979405050 463217802 974067664 323981457 764877736 238734597 93332854 924088315 369481295 343457743 800337776 453540244 678312053 694171606 996476062 312399833 463470442 148620225 721774141 558264341 29482775 785027137 346816821 358903934 61760224 146192599 68134733 693642813 705304058 657504784 445977700 133573986 517078576 311269636 666427190 573570031 823206114 353350128 630935462 192686220 201497959 120139264 165470865 983778179 888183619 724914182 129368881 382318033 854153313 103031096 739794672 238566077 410484275 562370288 216420520 369278357 931721305 896895391 815554581 357760325 309259298 460770664 804981503 257905349 91702757 728648289 69759095 278416511 651734662 380596294 74278687 196762438 931256221 104236590 982194401 454442909 823688897 788924716 871361984 261751448 31795166 591849064 908755186 258314932 549187001 186386664 475466899 739423077 167531688 228629331 57188565 830791387 769905820 100 648487537 329363470 739019499 415930524 707287759 278073829 375199161 354177147 646632590 521256777 362569846 44843374 766169785 440326552 853348023 986573991 80076683 847966878 522709831 834228204 311173750 172293703 393448493 78266350 446900772 59672406 7091523 283405396 478665358 731573697 333597115 195440461 550718988 916542021 273453010 887023556 322886972 720477738 15213503 664482138 370043525 671581972 498311948 586385075 603680645 564900771 146865666 545611934 922986211 201377414 157247553 109453654 116334607 278280255 396438713 216348611 250317888 912162185 806626877 102775985 502238012 893719501 880084067 482795014 608340542 984296576 319424856 571970476 784246244 23221236 1111955 84560053 792344568 149704990 567838984 117302003 620915324 101744666 63010542 189878444 105950790 663608196 141974317 199293143 444701998 51768331 467530094 896624073 848583318 283567250 664170888 761955698 778615831 582049372 365016915 728625400 834053574 416546137 698625189 573237139 100 352019456 10687008 788415123 339969727 191990234 762008970 818155305 229200912 838049762 276828131 201024403 753615270 813415103 420220371 596465463 792759450 272543900 168019198 205374127 441274101 58433797 701742189 166766125 727748132 405936094 182066455 550747228 887437409 281481093 51780263 768663249 382705625 393993543 763900856 958667269 191996610 583442954 752444530 921581454 49595477 753449522 880118288 457656666 31909178 871603229 716554525 868848027 56335362 448735708 900505650 679577711 455436672 234104031 236732973 204617482 241713492 59389015 801892501 623924207 227856801 362210854 782660365 304857502 903948563 434629553 515931800 273686749 907414721 112506933 965097645 10025280 712964908 190152937 303564851 730642696 714381990 748980417 916783531 918367378 426961462 87605191 489459276 262982436 216776541 153198639 691374744 298415014 655130641 530493119 75857755 345758176 73490692 228414728 35998109 221647714 228660634 873647362 86236005 939149557 993037740 100 15373185 569972878 530439823 430649666 720261723 802801412 666193110 941861652 97356122 937314869 903624869 86585215 114108152 323366088 582442931 608589650 889658838 968960300 774994798 436995641 6789700 106937861 388355564 388174363 56359048 593364566 797103160 824724293 916624989 717448849 464466918 735177246 285544656 229017719 13832791 617703687 764203752 536413362 859468981 773518847 994878371 610563856 42500457 461650301 171023903 268001014 720119255 457778596 439116631 539451599 405648132 889263960 586200158 996429077 387455720 212071228 497891211 613926426 563433783 732198105 801321864 861074156 899456633 659299438 210548318 911224736 85412152 587346996 311246899 970818045 269755383 128737545 499394857 185200679 211727686 632378647 932074054 629193116 438827104 340305443 364140520 7165223 244260420 6383751 260661956 359152368 220354284 227183217 156406127 221494041 34982158 453357846 543577273 230351826 148620273 40307760 488663870 630778329 680500066 426914504 100 136736306 956857656 529929362 801358080 332662263 265152347 503481522 468171850 395604105 422620486 964216228 976601739 250457161 25810620 999834017 637208384 175020124 669656028 269072737 326437564 224627774 482989459 287477061 373546005 92835177 524971184 322647342 394855287 143224093 717412390 107191571 2625112 15153879 455612574 577338907 985634044 242555804 465250759 537908817 880927189 650796765 714651235 42557156 176735289 636160784 114188506 712108130 808748766 677881849 890753663 152750269 87463541 201427299 63927379 843605392 22640164 387770906 27069690 731758130 654935655 861972753 351918509 759531677 95976605 97447744 84753283 959419439 532568464 66151478 291459959 445676473 413053209 394910760 708502653 271248271 872247524 300493533 643584019 10327148 632598876 693294275 434367959 492304997 735725415 74394228 811334069 85016348 667430802 810630304 731396026 441677222 645256413 111855000 537863728 957698120 778860319 105604116 363534021 614042618 949476247 100 744949439 819856290 88510850 628281069 384621562 675470737 341984344 359652708 734081468 923474514 447372432 286121129 428694788 578029458 938772544 718864094 565358019 796768284 324250250 729375045 542734836 525876171 293124401 611729143 475077896 140467236 59739752 415402949 411121614 263222935 131945309 482114028 254070297 733019382 68009697 816824076 690050178 700814844 255531323 505659577 598102601 849449861 433868320 257656992 550971407 993692261 287062494 588910905 655937287 264909937 89096517 10410094 143280088 890753927 678325431 46346448 227959028 978031141 613609825 294713829 60581026 675935624 251463707 419096900 22657637 274280052 798737495 529954430 615717165 962837148 729438922 68133738 938801995 825584425 730389904 689742852 870249962 807432427 848457210 972856283 232870558 800052764 282754329 65653882 203069913 205526552 914140103 448444801 348203563 285591745 53503339 323730133 555652510 572773852 24914392 854037887 45616350 957036520 662430183 444979136 100 846366375 672811839 770689381 592538005 287563999 113176611 223882245 878516584 430239939 300354550 327483547 270695487 808278397 422887435 476429534 917003510 730610411 699358936 295470542 828793498 644980953 104174314 425470822 35612634 975796082 657105064 487516639 487494631 191776602 596075935 676028873 714977784 990416234 459492409 608902384 746055231 311844273 156134931 762370400 372194118 237180147 696259903 398013189 208209206 321694772 673997998 396547644 871630867 236219596 578703053 163959485 113869321 628702320 781052996 13421485 904888235 296754459 21404384 450242245 715759147 413747127 512990781 971547122 668102070 133087691 473381878 1168303 410245967 937577253 774022971 625040457 704973173 55479548 392153318 735968673 235623619 411921201 112990319 809369441 675040673 56328191 5614702 687740272 401826879 984852028 391836197 358062335 845197462 399704936 240867980 343436254 91991067 730690695 71238305 161218596 243184587 390425880 129637179 823877026 625279516 100 327859512 835339104 158068251 970998503 690201818 170451077 855792816 522486989 886718265 719857846 794879855 587181611 944481938 997227776 691206731 993197520 275692503 818459337 697780732 644436775 204691813 570544014 871386446 45857804 436981011 530333007 848982792 493223932 891332573 983306610 495477609 120635097 871591774 1913055 6148673 50584044 183658590 582325784 507596570 683688483 717678222 406417335 901497542 201542043 701194687 383175709 498115609 320540267 582909428 676698361 204719221 573029153 461996378 27541936 234287302 26819129 838121631 727981340 365442669 908592669 76927462 94347368 644823192 678078613 761641341 534451558 167863187 263643501 186779418 703062731 954472563 246656669 642926808 66508387 889196118 194519748 454214305 361040452 139028007 18872085 462535838 334460411 682421391 249647602 777517149 149622054 428391369 598985023 531637117 686968628 968490913 356000856 290820452 32934817 318230065 176092001 413567090 185765542 697649844 902359261 100 551896943 420241052 801630814 934900166 415355152 243339166 161720161 2692052 631024961 344668253 651201258 611733765 82223065 143399714 123085534 953491829 338088501 124180444 552938926 419737167 16345532 581614516 29975339 450797796 586119888 633599220 816127248 162759819 80209011 755667683 372323304 692590864 515725997 471139395 978687576 725183330 165403762 84697018 889082361 680029873 468701491 675780966 186917750 127041418 391891447 369117861 966622921 379428704 432606550 533712849 640242282 313617429 476335487 486633448 495954265 450525721 788609276 790121267 515324545 811290664 998945552 412734207 771495144 795175968 522685854 795343413 571414758 910811963 97766028 278103041 119145224 342403775 553183067 210427377 296612460 409342997 510293961 320706616 458888822 455585219 639105086 299254089 57500887 613033050 31810524 322422118 106578244 327183386 702271856 243387312 259727399 438447356 127233618 704648812 351827657 185338802 802135717 448508010 784590678 872317712 100 691861397 578998013 28169960 70836205 907440531 257985414 174119738 622071163 130661725 159290879 439798126 665228686 695486032 362131787 915520611 175006066 750124009 196778340 189014209 149358507 129113168 125040296 350332597 726115496 47665943 998982154 796866641 51094996 4285068 506783452 545318948 892328506 794674490 118325130 115225414 697226325 405235661 573812885 935330355 575483221 914243395 386282896 11018322 191266481 760679865 336857888 20233027 106633740 388734939 595955682 317882200 570417372 520037063 798744887 298434703 726530026 203993306 771645365 355076851 971332847 411974488 991266337 19005442 484669711 750442641 54929216 253588053 860561303 638792494 27384413 293027840 598177747 199614396 268969151 20860130 326991587 915599277 623379688 845571686 518693682 724436986 548865487 600179946 82461003 950971862 669688832 959250070 613447408 170232005 383136803 610430232 941672096 435325779 456375783 278121318 814769571 376772474 717925797 306765119 987142130 100 308830929 618375474 749201657 503910128 991850852 576217623 6444085 112927995 792232402 432123095 876248782 462046685 909700894 177955971 67663088 242770546 904967619 359746017 716992551 176907418 953978750 81849109 454062792 505377724 675010413 339887984 219796868 374039969 605807409 791861240 905945924 879051410 504738002 766717759 241624043 741169275 68790448 571042402 563984460 339966618 151378810 506206457 84403984 474232656 503930669 89825389 196508210 577927420 213957736 81427027 47977198 281529005 861996056 450117455 330150380 542321748 135587727 981645190 258307488 587493183 717739080 151275113 948247924 124673636 264523083 421821133 10696850 99511311 625302582 18214106 605240881 93551186 809967041 849508700 383569791 423303200 460341496 673283837 47259193 484499444 571008531 51045098 285868066 73641387 144301049 875891837 458786577 808896309 670899463 209954358 370580006 277749928 88255723 170122215 66826484 368358553 157829792 874335692 857471341 420994131 100 905314234 372410055 509387231 610718672 889868683 966264095 866505505 821078460 119473106 194247776 37969240 78970970 528639828 696338104 768645223 900453433 511772315 632925857 781342881 682526639 414873107 904585461 478194362 346855481 520028536 586434065 40978142 878053119 164635192 870053630 770961627 795207716 618101015 630304369 663170112 209525823 963517976 5528186 135211131 157113178 475197817 732143482 693283719 357688929 763573076 369873741 995379224 719935462 92844119 75344831 730997701 950412411 387818718 424502625 126225450 644605131 653745861 563154764 610264548 323144128 588667302 54920864 270851928 117788957 736464741 879305766 332324097 341139958 108687340 200883453 825816832 469523365 44874489 999279525 680506250 334522095 726624266 190057823 200657070 992370530 13546362 594708267 424600045 936866589 784430444 195071685 449191842 336668359 572688826 39559781 207962957 781906383 234423052 20137223 687538745 154249937 617347882 573472936 279022061 757392918 100 20132237 489229216 383954098 21680212 944085046 623380968 146090702 755974470 692528190 161369935 656946497 257689289 849152193 628685371 285368850 411781074 244760751 387487771 687204610 657959350 126842575 806091606 169433760 302491070 313485796 54679211 743058413 419347275 674262903 437033119 587542872 71402617 33986327 142163125 594961216 456644638 360683079 40105783 244398336 337025865 985908522 546412955 125169272 165614325 913939718 585358448 94205233 213498280 691401294 945464679 225758587 953854631 107901583 487797174 279601893 108991414 488323882 253274415 212274526 139040145 858800296 648794437 20620131 827914148 547676311 269161842 711819238 653051592 390478704 993294073 366019175 373292945 410769535 824772444 97688192 62487622 32218267 352822283 585215810 607183452 100927863 988970037 481126096 803823592 732558377 315053188 382258351 446207352 628983627 36802599 117727655 112168974 321571259 712143593 75604482 170140407 118155600 252033101 29403291 893324953 100 112171569 447318604 806821457 584265134 687229089 124429860 203078647 273853261 60086890 706442334 894364756 321883165 859235199 693008828 870978590 656876902 478235715 131639176 227944792 716025781 969101277 710992947 792364191 598671743 102308399 43894233 992530320 153586327 64848894 375359310 290871690 746118768 597753259 946650825 49918797 352638197 575258066 818524814 242809191 373795161 677266885 143754688 590658747 103127195 214678148 880520862 439509161 2549277 935621761 875341903 467488769 860196134 707680796 650544493 873733280 962085599 791788374 185318900 424246502 561160350 528046353 986683519 743347275 29839748 520235603 97990908 628935846 254037756 224903595 459355322 229232535 669260300 197307155 332799501 537171846 707568351 543515662 14508502 165206661 37216189 913423750 690530819 788118305 51652854 915305823 969797721 181784864 276612251 675919763 411625611 987028557 269701477 425669974 951277459 570046281 754523320 153954649 583780035 72209038 28359813 100 686260086 485920987 624235212 293200729 789845940 346565007 943256532 382560687 346152908 564126392 113378793 322099384 890488676 211069188 207301944 998108282 149905143 551196227 172888212 69926649 605970168 578787501 287482761 503690385 88452047 101988906 615740078 842103128 896925189 446912704 948161018 132507411 302564652 853235497 794032547 843862698 279554328 156787900 42395701 60321044 785035532 43982843 801714242 307520670 381769395 806234778 750340475 131102331 360905622 342489941 497520707 151299004 996268727 982098739 598586402 617104005 345918074 312548292 684226279 128444739 995808362 562762787 847790522 742775363 459716607 10438927 803832375 404502179 634569083 38207674 437954090 532751866 280467241 184911615 423688640 334786776 496053863 805758426 678732217 290683909 19341384 77025033 419396952 746806916 227304113 501810897 938537574 88437612 800355161 772306589 779571345 250277592 130704070 589771159 217953877 208977580 859601681 231967767 949082004 686555075 100 369881790 678744314 813306226 157117048 330081523 324227112 488298248 345049507 477056117 968966976 325013309 107519679 734693958 700750412 381675212 667290370 897699384 299122068 481456499 130079326 75080669 778178059 147396294 564664618 427912655 566541896 751574634 718137705 208778875 296336542 206414032 571970507 821724384 169994876 833206621 493543693 149581716 993350433 719256701 87399164 127182926 109517315 436654783 298397481 756131132 394596992 817560257 681070378 848415377 608231863 191277741 848386692 336779463 827586010 213484227 693652690 563777635 951600531 415523073 740459154 349142435 297977306 488560640 178366593 295002703 804956157 71104719 221899668 745072671 97301125 36692381 783000219 858041932 870044523 820872563 44678665 40172878 302092660 733977541 877520949 767542594 151175154 276617995 36995775 987205707 595615962 891864279 65522799 798037333 958115724 760116404 832170735 509816361 437081814 804743369 423540800 385995327 977676594 718691036 609974924 100 298963306 420336716 658927899 229193757 563004953 385215497 399396906 856040742 542485926 932432159 467591213 525512016 170098577 58461112 943703380 816391432 325969787 617904758 171721340 471502342 966438576 52410372 775658508 967803945 906036120 895973941 837219697 947826232 144958148 231163097 113946567 47405447 647594899 100351253 807834108 72799417 264110707 447294977 986962155 279654047 528592039 151044983 250965668 438479886 794116707 147550301 594059213 792469023 69277647 409523706 788410689 380205850 838119919 86380667 931323394 415715438 950803562 148897662 385130107 172701973 208831474 504429300 7159884 889547228 405553027 467308480 867789814 190097842 938228535 881438391 535890990 824814608 23349416 881698588 262475740 476112076 7602646 579069879 254425938 987360830 982560992 662290326 685623865 664294419 440627525 742216651 987371561 204571661 631146237 865607388 873876796 655713346 363669762 694409109 955397263 327037909 891512308 254937429 34087364 909698151 100 194968768 228621684 746089312 65168269 28756869 887551421 273047054 555634418 604861918 514820379 977160855 408028833 844783297 56248662 945671682 616351492 836961653 341513539 627147724 815261785 402677796 461965619 840614714 28889394 265805669 539153782 822969547 340879615 864250754 348655734 567336413 565649995 149229758 784950955 868846914 259918917 379828844 204417902 951472741 868946455 785860190 829939621 301901275 607131042 31366796 241285332 666199281 816023031 676366186 555753919 821921227 336226859 484769002 885225498 900646248 699625464 754249001 262564374 957960215 817951048 141015998 791495367 922079611 661647393 535118211 937962286 34557652 778886376 831594285 404918120 441451947 540109757 824419498 826252206 592599609 216073992 462373367 526505698 485006922 814932872 291206509 322189824 17034914 944248720 303223365 589634351 398632471 402661271 699117872 494080399 875323615 525161925 158734786 859510508 862361402 351484191 519522267 171797886 48002411 465379583 100 965243514 777492467 845980425 282762092 998820132 927503366 981700846 331289007 534704116 365651500 871920742 498137192 441174031 200122070 819321450 251817934 527144549 642263209 316327137 654431307 995836417 180050128 435336503 435492661 71718655 21107883 229600799 862819940 545465156 189000851 559706488 617403325 512791324 673538986 53251471 187938769 166039091 524829266 164940519 785628700 425724092 557736542 859793938 213459512 677458506 138495312 964342468 593422650 635339772 592407258 246601607 568069568 410831908 465261209 981192226 671875746 796983765 441156708 369878837 455235047 114112895 795602595 488104387 81384605 753936874 42368411 633514006 991260567 271052287 295404950 963242502 328073091 689996207 453785632 770200982 518142766 150228742 403127812 851291269 215949698 783347566 846977393 874795010 654130725 173598539 634344599 54176658 565539895 39047326 105076949 571772295 829691385 464350605 95548186 819931954 231199964 276102530 319314028 113769859 942467322 100 439436903 533494636 986173343 167434130 76341379 673777799 536116841 325373927 349736230 763495046 563981955 462829977 927474249 8321671 10715244 241667212 180474933 291603654 508278095 867601946 236423669 604026057 398544917 351951821 382357010 974142952 898272506 6598093 597006158 133635131 515545654 253016454 674687213 879918692 601966615 349013587 532609529 213443109 239889663 937516173 232134929 633903750 946094890 777399153 39971835 483359396 575930405 274594710 425204592 475004424 404555059 825123292 911928468 448996428 726601282 896742556 788676288 794736287 323031584 755569209 386014467 492207215 168118040 360785330 423003131 406612732 104098619 446953832 939760504 216571249 632798687 933008244 763034764 400293126 450240568 347234639 855645121 421895035 114764256 341613138 481837781 330879872 954567973 863429831 231225412 885018626 813398083 393617385 806306462 523610149 95340643 177982954 576912358 517645292 536328862 504427920 148325378 820884231 670786249 753010226 100 433039972 640624026 177836444 761398857 97036427 52744235 695154981 741562570 783909078 566967710 64711430 369944061 286218978 185711690 290630290 303532094 694188835 840409863 993001798 368849701 242939510 619966782 943603466 835510949 787594910 424771045 388240928 241672587 38743278 93736828 90630220 74353710 99136695 389227401 513538418 915126306 959776624 164693861 921798439 923276264 388540005 264108714 774924840 414380812 190563689 796886455 539018212 152562740 997597181 382998975 925287650 338316611 72989884 404995053 128761701 504774845 315914315 512563361 740318981 579323037 658030196 328184205 731792417 131893195 320492759 552302519 674328306 322017079 702159647 647771011 561277949 975117619 170467652 82899483 439123964 201409967 798180087 762473422 789024431 621525372 108823439 578323381 631121885 391426073 474215235 277364598 707973958 620858443 366181269 356634460 376717748 871723676 157024922 142084429 950896986 521117835 10582568 291601926 922031587 187495784 100 321675142 535759945 35404278 828815412 130982193 706021537 746281906 249001933 607707538 616344799 416127041 264586141 676802647 902320838 315848624 630558054 303683559 655503338 854591990 290583734 622857800 783952254 86119555 941641023 347822900 419934962 486532031 955447353 748627302 414836297 454620351 569591684 424448419 513418412 167839675 652279683 872646229 540011008 602221296 872648964 725052123 975628907 631547575 847037255 848474115 110244390 483493307 948014207 539799803 619597068 861022416 948485841 197851882 360386121 82086245 672708837 409581239 98761654 203672717 387305676 321802177 950071663 672088901 707812417 934017286 609662750 135518288 502634929 921045623 871348994 514872468 391639752 3993684 354481077 514720921 178736621 833005538 244259154 75891019 171165897 383067593 714577244 25314774 364692433 766681439 137970663 862327330 882574052 350317439 868594921 806140671 135992103 103979085 820039860 532903012 517912318 876883979 518443347 666438490 612543853 100 803234617 210035089 572673582 797312606 474334537 770086760 602718955 779640085 546150932 75518070 804880065 378711265 278926263 902375276 694242363 819932545 564349841 429777074 825736527 611800076 489454724 725359091 888148312 785824583 553656228 626177761 695884558 761997161 350890448 335081986 362335493 647599822 256038161 708091653 670897362 237650659 447036395 565701885 841285974 243400302 514679279 462496428 883570273 831328563 420063812 393264719 896611978 283277265 160660761 139933018 270672399 608308616 582488295 254340964 823524349 581650852 252030654 72073212 143424548 420380769 875499574 54434497 779955516 237451483 189605901 802977043 426578674 249592780 827912050 307815064 739699960 390291854 395928638 632385480 178097594 487214625 520992268 515562299 654877395 852618380 756975090 666866394 172364988 215791456 56333694 584817301 230105676 379433971 183553342 352852727 883214098 332665343 763308512 253300249 311508400 292443 521333611 571817309 920486116 667020902 100 827363498 190980292 644721400 525489400 614149551 573843646 243358853 869717602 698018285 718946457 993939633 488415498 55176980 678652922 153260226 174802171 419888193 422991188 630474985 109617030 481986481 356317971 456131239 355749858 410784195 478528190 454057885 646242351 117226242 263528289 964388215 493526631 292590809 767703165 864401923 118172149 307588367 136670092 191483741 872576744 82355536 326760473 439064929 812295643 912513799 244499084 407956338 173336466 725381621 875419878 303051061 828891376 452152147 367469204 798269750 801881975 106183891 506843437 995421326 65966886 11483841 974702569 317357696 135625967 78773642 553795413 563249323 64144791 761519548 96137790 534034634 365293280 744808782 262169944 80965151 341924682 16617188 947515616 245631930 492442660 668395255 95419528 753145995 39783915 716052768 153023841 824656343 417632459 792046794 42104340 534025589 537319266 544269450 82050291 650780940 280439097 254783236 797732008 728868597 347485435 100 729513750 789172197 151697350 315071867 647369742 941955338 509070112 819942042 509817109 566504934 684041974 139509844 847395369 216456692 114693317 610517428 87293931 38228046 210504645 739861455 268258727 75358503 824287077 472088920 822870139 823526577 331823123 596031067 263419027 974983114 218065286 631750439 264725404 772667927 853367724 464651826 203863790 142935567 98174340 756631575 584879664 855642368 268349294 597203157 249113933 638225268 362202164 512515948 917496134 822508896 535977012 145167659 349188224 792265310 336937489 486062211 635874880 937507939 613866304 438577074 403752755 781020741 868770371 836780964 310479208 556016460 457569547 851173404 472142784 18763269 825370144 11897432 534437832 311526978 207904521 647024208 915113961 540862675 731644137 571397604 986648479 917333613 927749883 41657662 748068883 575547331 963373681 533458900 163603164 674225421 476768699 522595201 924300083 742394931 888363456 933461874 362412661 205311704 642026719 542812308 100 524468074 539953098 338167081 328414809 18714783 911388984 822924861 359111261 463960619 45659400 877240904 478551337 33503976 493719411 659269965 499367919 593641783 218963569 969767830 592525116 76187317 331869983 20043284 858160121 263526625 965336188 390127013 955648766 572751291 194832391 253941957 566728098 395339770 459746081 221119271 425339587 437929113 306910207 479614331 49221093 762310025 729140935 998966682 994249131 237681012 764079958 763040794 858376785 841641789 483982500 475797409 935307452 646784351 889156832 743629915 307222777 342472271 634165490 481262457 250410821 889329364 310791489 212240862 51146813 193249353 605368066 456577197 988601168 126336325 460919493 322549680 722377177 873702779 245105867 825664134 558164657 73713186 794841768 302258239 605864237 837811863 157059451 225202382 106748737 586805895 862478230 917907045 983955875 905275572 242934648 555286491 573914420 535352175 485814070 261380352 376546845 999577799 221260774 195015525 550640741 100 860780337 670552786 374989871 856122226 205533392 579440070 171280010 888411242 979940838 664289432 439254507 455265688 601767855 706399086 480288124 459758397 846931216 482196437 991077150 688161560 954634424 998429084 450153046 856199612 747760690 383071259 12226644 770162203 274005778 758185112 618335776 414384451 160016688 835105962 322169676 252823739 890390043 730214052 951819705 41834337 678276310 805791531 730490478 452419065 223075167 179892280 94304196 962827745 36098738 692000357 593705466 541150512 712490661 696190202 838581460 360146315 87604699 219132965 987214265 285761147 327408632 894140188 942763205 574504147 904810110 476466881 404482897 255985379 690346413 928535305 846786488 330626413 190176938 981654451 868534525 132333106 741157141 59645145 816249830 909076143 302928717 947036536 401026668 119270286 245523336 281718394 763594883 139045044 760003535 405655312 148102903 708651896 702967612 668098110 366861847 815992930 295445621 773460919 299445410 218488119 100 360393308 184479919 391008371 322026061 70271089 208061003 276174741 995900780 533204024 649058091 785048034 712116703 211867130 154264092 932236067 964483188 155230549 753636824 605671327 624701165 808555912 698663765 393853065 235925221 6182336 236547561 570891278 72637924 720813386 549504260 505788275 63559461 436879944 629856336 969718566 43273592 985247852 577464891 886674606 175308414 864209229 975944104 659869455 862919620 672000809 184398165 816358589 545164321 912202762 396298682 809346016 564877147 676563858 469989750 486078816 739948106 703550898 356081570 206465400 106456166 263659571 52345745 568556422 868618450 184876264 185326646 497270546 572371197 561858061 637473821 414060653 130805967 442414046 119571033 244686884 454963129 438391754 334315232 879580151 247784424 48479530 376157224 59898244 816520518 108531110 740715751 92546300 443095208 978764303 600185137 982597358 630914690 845137272 878448628 974881989 303529442 603630857 205485585 834676108 656614481 100 754804276 419065663 400818999 365296639 384258367 2421788 289909602 122170968 665039219 49192289 536729676 180309181 552173892 101101965 149123181 437751953 505407682 962508884 250773545 273226009 229735192 735034229 469212509 905773202 135198904 234076174 158008940 191550128 493879532 246256978 432612423 168770650 805521669 479777789 421815546 281258848 935489783 338086434 575270797 915996765 385745857 58429672 608075390 632279627 555486150 376300613 533621859 655002429 494461591 894074924 835155774 935978662 821072583 809781772 11029326 783785361 611360756 835223603 533471797 798657084 119909026 558439375 627955727 967110601 719989593 92738308 772558494 252694480 871175220 515703340 384256268 999717563 320557789 15186837 55164947 748408118 614155294 539669018 838921014 420961410 665584533 641973475 337697656 117779233 528357308 899447482 78681077 592428780 267149714 732600332 67184507 277177715 845787202 375333066 85311791 647616753 946333196 427738466 144415018 507937877 100 35043318 721498608 208842574 867006724 585609737 751660398 78317598 225722137 792671037 941198358 516306197 983015355 671525574 393364206 888891270 50062847 501116418 701094155 842120491 590894838 425419542 694119647 933412517 466674094 871658877 284665567 678378934 974943767 175535906 142810586 924016341 9010080 506154520 22193762 912122731 948544075 132142561 436684497 89464572 842817410 777721697 805022733 203943455 490327126 871895525 679684809 408805239 59379787 882686235 563192825 52802655 759892916 13723462 951381931 371322056 718195537 590408548 200465158 931135648 245971510 981744600 473208059 216990465 748981687 225400612 183478770 285421794 532758241 592629403 979522026 890837546 842069952 268749692 559777525 703298087 826290276 685139816 941810795 786221321 215664350 180049075 234988566 462081577 835744350 388990940 502937564 779419518 605517039 72562750 542985063 550976914 319347479 258537689 447300271 144285283 559466093 504540786 550506738 916281855 918973133 100 81248434 88904497 982569283 471569492 492646022 763861854 960339237 455707725 967131196 217384378 655438178 425635435 968634655 296880684 81384413 856114630 64377279 327823459 577708435 362671690 949914575 431460434 974715688 314097511 888992469 593534544 990873528 806322289 822511731 57167065 434965741 958637340 955591539 843181778 480910081 326826069 769065658 307603658 228123077 989662502 918560315 949556136 105806983 626863588 560180465 554837555 771643192 626013322 790041160 375918176 193872230 735683933 408638487 522339440 206428868 676395791 734866458 865420488 316726191 612860698 728248735 423612294 137276655 703797287 47567206 975503492 116681396 854995236 969650594 657528794 902577208 392489042 49586821 629657376 245683747 730557384 239963575 809563890 198025555 727934707 356139703 686812438 169427496 863179970 38069210 36276893 712433823 186716472 368650802 165949257 169994990 181309579 897349097 785193575 651191101 374980769 502073409 865691677 819756403 699734675 100 672714732 552471526 402205373 908377592 869899511 363354133 883942078 202971 364093134 540638695 253903723 409804853 556864366 415557615 96477280 967167304 640179011 960651823 639956451 855129070 580101801 847955356 572991071 562247647 118316413 187026351 589023285 448564642 944192630 698426351 411175293 430879959 64290566 133357713 315022303 547053697 435360335 64236129 349824477 54024163 774833890 965403251 907431368 146139356 220013597 719341229 814106338 601020400 246756550 633393597 624302102 551815716 659141859 512062468 428558403 756351615 223214161 128638800 914937076 787823633 828222453 711151586 626074362 776240420 496141038 477601474 195638648 254045811 958334939 820557197 118584057 467821819 365755128 643027201 231533810 117854398 978849969 938500028 540706056 262502170 256003433 330479243 154544098 703670173 481280880 123851441 49609177 236962618 682331384 87220460 731639715 965703204 295088613 623914820 808789771 646093693 637166113 753602839 488084240 291851141 100 341066162 77978613 646907148 278167056 642750030 238862017 401087435 595390454 800321287 408483410 405702412 156001832 74906833 954646493 593769688 834041426 835097332 824504622 249221984 428795714 552953340 738091703 225302707 76040894 856655519 422357401 719167731 279620448 935613710 512994246 11302975 898963169 672650776 222800533 835218636 2722855 920819900 622016499 75266573 356917182 638200269 35157802 136863272 88070127 772685627 182102727 354645567 951398802 900591461 536498095 495797652 731646486 964851134 241125361 416376009 401425247 664379123 958703401 485904454 87662034 125345216 891844312 464382339 780227110 805423543 38585227 994632868 194541045 194639687 385701974 754412224 379558333 752296409 418234085 1742194 281107857 850103561 380577848 904404118 915338709 778440347 185441894 475275422 823801660 124040900 406374945 856901843 869796699 218535179 70183765 240945257 265654882 324599601 256997918 793177832 164193398 784060770 950681975 717857019 948181092 100 977959175 453949985 693846730 205917923 791598379 30982521 480736145 867793387 693680339 142599356 690432177 339635750 576744275 156569513 804985487 358973096 472029990 705457005 678962407 536856522 351802442 666776341 837357089 862737792 713774565 909336554 744137652 147044784 756752639 979866253 778082296 673910948 131411684 336665732 135212167 365331237 598968782 69104201 607377770 24622900 100575972 95334407 528247796 410533699 420569532 910087390 828758073 864748249 755765177 215227354 107204214 706900415 401786376 551486317 931229548 711760727 575471517 488590007 644689797 240797137 553378327 673654059 197963584 289533986 800961477 916169748 651698559 226324880 647192958 717024061 514271748 100968133 288257626 586057524 583950688 266004857 241612350 978113501 431178124 399878288 520978977 644862413 825400129 25963704 724887847 526924787 821321979 920067527 994120955 712056671 40827887 243251519 403904492 922264077 556566475 340336220 998757954 807488853 511839273 380512087 100 636561977 416180971 982096963 103806583 768900649 435459353 3735860 418174378 223258801 741429775 575355899 750299635 71273148 828102136 514744989 187864754 392248270 821706119 356230540 46883127 469320037 516611760 883204969 635407171 465366354 668456781 457057927 383228409 928826121 430045971 376921900 455226615 869268938 634067095 29670820 641291653 264525961 794306166 338069044 477059779 500888110 763769164 734172409 498370775 839627989 416701783 553512358 956142304 444375003 924776101 347364120 890014835 362906312 288889700 764277378 646543555 9112772 119416488 83082443 536803602 866592745 672910870 786527381 860759595 404890326 398566157 727246343 727867910 995404163 577740867 284690963 226962813 452371107 625695377 775558095 480263186 370553488 105611690 789892052 125830914 688034137 317938211 846519792 477819540 466038116 174103631 618350019 207740080 51412216 162438540 857808714 323692250 653640884 671634464 644989450 30333482 288052509 363740403 218537599 728654981 100 286043204 703364560 721833688 895297854 137310130 700492603 825165637 681794629 167854307 583757751 558811569 163814402 334500622 194883909 431096108 267620537 340602632 540863825 767131884 894021152 960298069 186891559 700795037 697106710 962382821 1061591 783519751 764992054 645557873 973379716 827386955 992343486 72289222 146052360 341098939 651515040 154474057 761277742 415959537 277217300 560973645 435752453 221206877 442009849 126849976 257461082 904708239 244121723 669152358 581319698 286418593 690777546 621484015 862001815 256942248 376852840 503524081 281723962 810258193 351788198 349580995 800008550 350737429 462230848 220764739 194643317 685556915 520185854 72716481 513830604 248502439 10492714 456695560 396978519 796339814 652218154 940394106 983636660 709540433 750076401 804824612 744012821 270434471 828460523 387662060 689679298 696956063 387049151 929475013 796942687 136326803 137084787 615725471 380032450 22071006 14543638 560305137 970960862 28358515 555505520 100 753625487 399452970 930556563 626323574 30372837 244535967 775494918 754074339 33729954 837931232 902412401 516878014 802395123 100590998 88313917 634482976 444179831 220810549 899186926 16360155 646864321 476674045 842136416 249930844 608402427 806663149 236161546 956727727 876399157 276536475 988215541 454262553 473236291 136569161 916548981 934188208 954508766 729507978 591300787 565464758 801446640 664591259 637729158 773297189 769269475 398952285 931626246 962131736 483538786 585835711 248372321 494836986 278554783 94525855 943362050 956671856 752570867 481598041 891181172 292234878 715381735 984443227 542397094 174281406 485316207 863410405 632327825 995885761 647946533 455058392 867831811 923046484 959878421 40382987 758519151 484206606 906855030 967614004 192860688 65088051 929003087 835861134 587124892 538870909 630849787 96440579 618059480 277645032 251544744 686287898 290734203 549686196 498605591 550403700 64661563 327337404 619002887 717762157 465376833 594396489 100 165258343 893073709 804658735 798619455 856103675 636862780 1875880 899358380 657270147 380416019 346053525 988655156 105632479 610550635 685341846 255918453 803960504 777612577 576353313 899717133 377506989 592194054 3055553 3314548 661074860 270407644 996684986 546507148 916064008 56881957 617721099 857268375 785126094 738372815 818127876 626202208 972022364 979849813 745391589 124648284 51610965 366313342 813054299 213087777 985462936 290279862 899220714 672478372 815299891 527522787 72873531 987697048 377703316 703720099 452235857 258435913 735398569 233115375 955167081 451211805 58046341 559400357 546899604 336478789 378100159 860170324 861324997 523723780 962714317 77174173 641100006 361119371 948917786 689122587 384773138 895204115 956245210 428184005 986794559 267381392 702015229 198936569 561243493 652528154 745372397 642300962 465531132 283538478 372971946 895548738 413296809 580682000 963593700 29276515 446905043 84371894 925933232 116932029 849569268 524065324 100 966861935 111486680 983049083 978348110 453088734 727149807 260479718 568703674 838232306 560022616 504779417 681718884 782025228 774946364 857185995 228452525 890283932 299538501 238751144 260051205 705148823 902479687 472404451 105081516 105737357 997912945 258835883 21421255 411194311 959553770 436350601 210941909 658051192 217551713 799073530 868890634 611918931 60474917 705084217 710526009 228488861 829605619 21491787 149052383 622647317 921127024 389312349 688996594 701112496 628159678 731621782 797122163 66201941 392156273 261282752 192654859 340753580 618504631 649361928 487919399 605225189 259576258 623630933 893336991 474192628 908084390 572943102 408696178 636202453 255312437 714568417 635234449 289065863 102267404 6994541 566439605 275574218 309713169 552861052 617415662 382922093 5421703 224615251 796247279 123556624 668267707 542011146 197987744 623102968 823967357 441452964 378539763 13356164 849213904 397847503 253203755 407155005 236107207 897435276 588889112 100 61929305 423959796 139225076 434345226 413025418 993794131 173729975 267816739 739894967 560330917 567380452 985160328 681438047 791017398 257837193 826329258 193460140 384495919 42072031 310857768 121774821 706463928 833872824 718948458 64981896 970677024 284957613 770196177 129193259 350501896 904300173 763356219 69857710 83840240 874915919 802871179 925524946 493137517 513747175 240478585 241910285 498723078 659090717 357466249 956673903 426380585 755600864 601846083 669786259 3774345 996668745 648467562 426841423 182957960 123944777 741911783 430713575 157658006 584696484 634554834 430708966 524736665 550661479 51378358 647458114 685126703 969216651 35769838 753241261 948412026 904326646 266057389 129231176 534576124 401581421 345127904 921267643 85889502 223093161 987669536 366267034 836136977 236052722 185925607 476160561 505775606 994268958 601284848 762663378 630116114 888569899 640375668 987915166 658559398 554204410 37959856 864492315 977926781 546993915 599991024 100 751099200 246294412 401857580 229291339 70484288 380452111 524012575 780108388 897498498 831318113 90977419 988569660 997903240 946674739 199149414 426516106 419346556 602232805 593229549 919826198 682529348 637015124 351181608 467896606 8964888 479926453 814110659 433184618 558541027 814765190 394444915 27629881 119179116 781761017 954051361 610765934 246296083 361154865 810459596 327684003 38395139 273731734 644823145 505991349 140162431 119881061 639142685 175162782 885114304 213171009 539058476 41287054 773566977 50894141 724050702 649311363 818610775 854866067 307778969 118984823 240338525 56413219 208058695 672844682 595798639 42300823 903881702 814589890 736891902 536694378 118777126 828218600 585800447 3024748 247483396 383213458 764445087 78968209 96843697 510774226 303160783 28909338 213202563 245954913 42157925 799627378 754328068 164288949 606971476 575906504 56354857 360278550 316239768 149453652 299143742 260295134 476197061 584534320 646358820 793601730