4000
195110289 229206436 463933160 727952603 558214142 442810979 58519944 674280467 115085369 860197632 876912947 562345537 810556417 530944579 698945990 193950256 513755811 195725115 653013383 418597647 227727729 618845588 173860735 793454707 293671864 953757004 103900241 473451693 598260701 547777984 291830713 180075445 115573969 531858515 204925919 566045633 785738597 200957190 905004761 590149818 12722843 608152492 672093860 979876381 766093227 574907022 333414201 236819 459610674 364146154 43913081 696332505 860877979 393584530 831407673 175769719 5652368 952956729 504108325 919178430 942351551 936404743 691933090 69871850 947889743 304931348 894206913 26997189 589096973 218573036 115985417 877146231 659533233 318971850 179997808 898862180 307849798 426398971 104735999 567459563 800249766 639334940 700609953 798391962 24838940 888973445 364765161 488600391 768751180 828718127 350177538 826418889 413914869 277576854 639402770 803819188 386909040 308194168 513720419 287921830 939967389 738351246 756778011 731807735 996203037 594242187 759888654 511692467 468127608 149504718 140590073 518356675 78416264 745045582 994005368 467524761 770372487 712136605 256315631 364798244 263202824 956348842 350964421 140732003 748325048 465765818 235516625 89726929 651009395 270710849 927816497 94664909 650176471 545152269 294351078 273538505 351763642 333024764 701911998 934488527 965509054 532159145 918699654 269160741 838315054 308688919 275789813 45920622 260640609 695561882 91583826 582738124 775725135 883272395 637891765 567106019 612141882 220942705 129697102 801980455 754494403 955428865 475845882 529571207 139539132 252919264 211170915 522402477 692559532 496494177 471409217 439319342 384651419 122417493 975053142 725058445 887639534 951557182 127197625 420643946 739710493 312503206 380562998 261060845 664385416 325062961 556664558 848507287 819426043 990971119 873017700 153871870 429347689 215937994 492626380 295235527 231627115 63575025 987739769 729843267 460804725 219043569 152176721 695418598 34774048 611189115 436067304 862998031 362291075 766940151 918619887 285883475 987056779 385293492 82373803 241622467 46352836 461783453 377322525 275616771 357498158 697575312 204646663 199287513 654533549 976147177 364111849 128009348 486560128 601958732 378938292 734110471 75270245 472472576 658907782 859718691 330756097 913132664 743637338 92657862 510638767 794498676 630476126 426213302 46903324 672392147 893254908 945652408 859369142 680361477 750645080 187602726 953807359 278891651 130061462 160464079 55421280 220502314 989587281 153577276 153703453 597220441 400221232 701639625 33304433 933770714 48395717 233947373 869768901 844748648 130736044 819828402 139612385 807664080 12035999 9281137 943104042 180477906 651315172 756214655 158573382 173352352 32161312 529128360 419736817 470079716 821637071 914914538 191394520 713470159 775304779 379274128 710119373 256382582 334006912 643880595 741429077 344911276 33870592 100040560 890942000 296415883 142049045 996777736 603001533 793926488 344634567 730751218 145554498 409096278 731719708 977502505 117332890 941287169 452939410 970815409 419979169 862089901 32953741 916343753 405500564 202523466 406679294 433187004 956655456 453568514 54833509 372669632 907245828 866648169 370174708 434726504 485127042 489063723 710704591 349392062 697534153 296320229 252341667 294011112 789748658 308842203 183117854 7300693 926891765 411366813 66703957 513080415 861701252 767698332 4548355 45682259 216281793 216424537 897514428 228748333 215062030 939574449 175325987 409999974 433559013 517438259 152012510 993743369 338894872 445935925 532424387 995852504 261845949 369081251 93364968 168347420 707959731 769727339 370269545 859044879 955533035 388400701 63453573 246289506 719178226 707400387 231856340 724867339 504931248 485106888 793117368 629340730 228638356 67574630 227168699 482996270 352479671 635034161 78510712 211350014 453110617 134864 327054481 38306652 254636544 215761196 524248692 16964456 298695754 952330332 691760503 71458676 874834671 813717309 892950877 988022401 778344053 4581410 112857927 491332826 793761916 983372949 500450143 737319607 122879786 184603681 511920298 346761178 221001117 166502843 945588696 569644728 92108403 856340203 739771290 87842297 203708954 509562173 37598422 527139331 516991538 789490743 650429362 79301155 61955150 767954392 711035779 228753290 859294184 402551136 232931767 499388016 261222029 436549634 648190328 474327354 922227523 203807429 917722256 684692298 997811737 821672395 109411647 706777036 211567616 195244638 426870486 821785985 331014837 660572962 191489156 692258577 313031052 494697673 324187463 158795588 599026631 321449504 617288770 634932621 607757522 752439335 946160140 569301764 884067750 358881628 773194350 810836649 829527087 65064544 490151885 871718124 273624446 71262208 34348623 296332503 736234742 529386618 980588621 524251033 842746850 402401978 133047268 511706892 209805696 351864660 291648620 922592919 902671681 180935643 832829564 454261266 580219827 630593775 465759426 933289780 602345285 666665843 307047961 201863107 302489632 382003130 671211708 733681134 392854915 981619192 149828550 883845995 7248886 498494378 652144580 713178019 727926046 681075413 161518760 175103119 137952365 800657407 599965268 718805558 423513714 351084756 384959301 584654804 41907653 320232395 846793874 819695429 126775347 169684136 206274746 359566496 589778494 943579228 220870103 313554823 581578700 468698241 569500314 739631639 492514705 370367217 955454063 493922731 876139730 64965033 172201869 7108884 316096662 607654163 5407065 839994755 360458974 758656394 928362523 864700486 535676558 194129307 556038989 611611849 817427510 35623604 892034472 251682306 673655460 23557995 550968479 905036217 595907530 316284250 78319586 176282125 95611191 828973880 470588473 277421070 294730231 201880607 319913335 951718055 874988169 18551290 639080484 946526159 81655156 277680295 515684203 127014496 639921744 23101835 626308516 607265622 369461124 775496810 935646543 245807467 523041826 512078910 630039889 907815688 568590991 472304069 311587841 209639104 616948151 939625522 511046392 388010041 506216190 311751823 88417813 220398753 404707704 625455316 720372738 982526152 356050445 613503556 63354155 656352751 756676670 202660068 192105941 306748953 738194537 985065609 984469001 996793001 715106900 804665095 197917474 28104031 67562300 940569308 443005883 974780902 244834495 383566771 484840126 879002853 436161235 216544705 808648526 731129604 57551125 506347455 55577592 903402105 479358391 774906380 562027980 317351823 534511590 84759917 822332357 489648866 224980857 336413916 211880814 734682016 413948278 850672632 336573604 296484700 430204683 617844389 611745413 271167553 922682741 761243259 474315835 532285317 512985926 6517461 279632103 789814402 3818357 669485165 737058371 380756111 151099612 825593483 112134165 965818138 864915212 683775961 227455924 749326282 658240556 228115348 738196040 186158757 840587808 373453175 282659234 994605362 11333342 91424946 169192448 75197080 733309202 117061131 769450090 297702761 611432332 437997034 866024059 428955582 383635398 260900800 28489819 258253868 831225869 359263638 846594234 397885409 797383392 208163139 831199172 980978957 576563062 543664344 828612466 507996155 490052730 547069177 907206362 84300789 6887549 258345388 59204433 369274053 128308220 455053257 770731942 567990397 722297057 557134820 749526850 51643668 550502650 550937504 791745390 689440204 158620448 570695489 685125038 905754353 394307742 522290437 30046024 586476757 757816559 211771753 588937185 122665575 688035925 927708921 89737515 152341859 188735083 531627276 951764087 770530856 202193725 232146558 288709590 21196164 815253864 417383548 107934364 150163916 331960059 201492280 764658023 909588402 652839720 628735798 78227605 682494322 842594770 950251149 311891488 391946539 547427788 853808007 458862389 257700433 106691573 585511176 218334730 640977468 226116001 315237213 122308442 502460195 344224944 751286674 902999786 45968983 383163504 803510638 206447907 923318161 220247704 576806512 232118057 825710880 497056147 739284015 190658272 15850971 487199761 400039184 87658775 384647641 219236437 770375290 219785997 669729235 951911757 785057588 431483090 881183135 896135284 724737155 367419652 855145944 900437587 53405554 898431939 354283715 795239366 530222405 934077312 346240411 78321712 672819432 367308002 608903698 748799431 535216041 344107289 954692619 975008130 816010330 586241600 759103014 256296312 881570284 976630622 250651320 934932286 1413505 837898353 505279057 304835205 156856092 221675822 561662277 482552786 545794646 273459306 322921619 592760807 705299375 861303786 248295892 560421512 216514105 160495039 411760648 276932346 567325165 970693960 550656392 992885050 875839441 154793308 779903665 43827275 882852753 105118060 337986011 783866811 677929109 784743035 680286505 327261882 803998399 117071104 61416962 437820484 532823615 565584781 525834536 448185264 877793369 321645284 27848607 144085913 967798556 811564521 120683141 143038510 737664424 727951759 937792440 722213589 29098340 837186788 165926600 776012412 946159692 673554629 62483371 582447582 258731242 735932010 649831765 804348563 882764643 293205136 448539525 83029481 197006671 101578424 208074222 175784359 716497968 21159017 573046890 638912198 715033877 618570511 914907516 130057641 88252271 315113577 543708200 897452848 26233108 579687669 549933750 831977343 811714548 845022335 690341526 237441161 694404445 499429792 799763590 432496882 392414861 495773322 498979883 5647281 530480685 205278860 886773347 867564930 612844929 334706653 406720018 383159537 375426031 924159645 323408501 330553280 400452507 573893660 102096826 593149059 408055087 105679687 885633328 126024953 332832831 463227467 869340461 292080914 926441753 358247490 958318957 894905669 715048635 707585959 807136647 38197801 866866353 90231977 588504298 844901727 920200922 804503883 781670251 106513493 250117084 818878462 764110565 121447330 703464872 390776181 290694646 897892346 238908793 904817188 778907806 432958459 897880453 835442605 754947819 995279068 96906503 153198104 78908735 639343716 90462868 723536813 473458201 707313622 457912224 870866867 528182182 369124670 166110974 947142448 873975868 125545877 3428764 48744892 375186387 59936101 360264838 863497265 52781931 201446223 299378799 722294576 27961537 373962940 1721693 617589114 18113769 391805701 174613459 839783873 981420764 137702824 651313629 599479682 120479413 609576025 603285663 789725435 575787363 127488558 137247215 788551 631340995 315993765 298208552 499111881 29957159 759308969 410402024 283159920 325138550 700582062 170170562 923013809 975914344 135494441 973519162 487366530 207509198 937581934 469342278 699066105 697974315 520288617 996912818 502602717 848127024 947861144 392419521 995207949 511334093 675260710 640485975 98488474 301303816 995538994 177705418 267987039 715931210 609576629 691869372 222695447 859079455 36468831 243355895 641394414 713852185 272938450 475654085 827393983 432360850 782660913 617097859 452281314 263068353 2848537 781714426 579558500 873004709 444056115 925691333 885614973 677987182 873787413 273774624 578642397 299232899 384728582 882469190 632722475 866457922 623592550 751389988 814801754 268732040 798906905 507184097 469826764 869561358 975392499 580741302 631339426 244688708 867848234 969354907 49610973 436803334 373034974 491856799 529240797 349320933 444529222 222581691 861442570 919791721 545366717 668344246 405843372 689568781 246546095 106271496 774410511 518618907 559320445 672253140 571361603 454182522 382722856 98061038 597426709 905431648 444158451 117299175 991499006 53654567 214445987 694518037 875087477 665055462 936568191 510778219 368473660 455557490 581594432 842952500 827598939 318552083 433187125 884728819 747252975 192334413 807971384 549600948 430388863 223192711 605882243 56178805 190002835 250565128 672836065 52911725 928903950 801997983 717826027 134221737 790462960 768832133 442836538 864233304 955087984 401557302 237837349 774301108 757421266 321265333 668644654 989752014 941907630 891655247 109237858 130403624 313107546 977127028 312666993 466041044 410286130 336951074 231844106 365448248 21869406 983384017 982519869 848152842 512418128 188528710 996427453 231022298 272968970 524536621 740580133 281340293 771875279 848863074 144920082 793601274 134187536 362515289 364647508 772304931 309168494 834885109 200193131 106483411 589507120 980528780 71043536 991641031 962946268 213247284 942257011 361842157 157249966 902487004 695087319 526253893 589482146 354909767 166140334 174277678 385037178 954255872 526644285 459335051 89372327 388405550 505660373 375623615 795740984 364274649 318456772 831029475 278751785 226362057 691671970 624990071 490762114 913907382 808381865 515628356 803927921 204474580 34931556 599024212 278122902 212725425 967230820 464233299 983587404 965094493 729489773 976068655 872758971 811934765 989414606 119078962 476670789 895270851 234585855 993915925 538612870 382320145 557037050 278746711 614396719 67993145 478590060 275384696 375327563 245835768 79763114 848231370 375085513 671049449 627761773 480608084 948206757 661469354 560012296 299399893 557923222 560717240 392009389 433039902 553031804 605498257 808178636 266424822 172300710 544189974 90708719 708089159 324691786 111649318 265624211 83748867 205581053 510333697 154019711 83195143 284193365 79361673 76446985 109390431 313877712 177321765 675404977 300857981 258616043 928791817 751210307 617821604 288133536 758537130 299670129 436427454 437821418 786837893 731131095 596525777 862463560 400231310 518864668 853866122 549981393 856132451 194973102 63179723 480573737 707678139 559420434 923155286 111319787 796029026 152466225 893500021 977349475 286732612 806208572 475431382 779571972 348522737 848141292 986316111 488285664 93048298 453338838 40383390 206420967 775304728 812933617 268045947 807235060 122950884 902999058 271373220 317409337 578314285 106709056 799295115 808397470 971544536 138711215 970080723 749848837 84469396 942860714 478250634 451575122 468845418 13622822 95890857 563598553 717437236 351395 478466109 736877722 958903521 269044242 462334210 899650684 668456005 499926203 423431900 182073796 234434136 739636939 436328006 535676569 845366496 562994767 50344617 185881560 161330164 718929811 326652045 198099988 280118827 396838839 418634853 131717530 788573853 289084882 190767199 303762874 201053307 83697507 179543855 200473985 892673471 586195987 595054331 825006305 508555662 912058135 203105793 440955207 819708128 742242198 285804323 675932015 983113131 410473996 425565510 901457524 714875244 755084502 862298375 888987077 342902002 396380770 69343810 267982901 3982098 413516978 527945952 419415652 385300287 989247102 357407125 391620238 446090997 579536509 128496542 181893285 570690021 902542179 336071092 491423138 241604901 305377259 457455399 982205605 884110058 625789987 725577049 933761287 673415191 836160536 206134013 578602593 334495682 357055055 348977345 779026099 120185808 763194987 651501741 707054289 132373428 479625538 321193145 263154541 890208882 97486067 898841915 973028795 146205196 893262110 202892695 191522615 882326895 409738563 536584572 357592651 926447907 556607145 942658973 693386930 126489408 407574673 791240391 775230127 615444848 466782360 835807944 17358227 467427531 239074608 264923985 301833806 201848605 523498492 672523773 629646214 418564079 964392583 822741395 483668614 145908819 892919816 180473949 334546880 722517847 867036777 515129891 259788483 864125701 882754596 111622040 865668488 305695514 650065360 706066617 774159055 114712349 308194489 833898823 229294545 943720633 324962202 668867776 3148500 904313824 791459141 482552487 568236515 653548062 628194538 252768646 876927098 115891845 717880172 765021377 959151994 515783085 574356273 458234393 354140614 523846885 208387369 827670778 567726109 637141892 888537948 58095564 787416795 210917887 931146867 661967841 884354464 718874784 723023915 73357282 870353143 343444236 839251376 951351776 73766733 997448748 560635091 689206901 981636806 396859285 669983877 503929826 679623345 48542776 365658245 925458969 427144248 44771747 855107482 990663996 120850822 64069646 296790930 473133848 600844932 665481092 828803824 984618392 32538570 697070728 753952567 706537429 426695991 370291117 870245276 838544693 21653999 643607768 913988680 205903929 617537780 580749449 885179727 232643234 578392354 871470140 444737363 335255587 272828661 570140476 888451751 947184904 120326429 539181383 1462635 693774416 228289713 410113789 961537508 127744506 422413131 763399668 304580689 186081948 616208322 248020248 862877981 473384180 171312681 854508932 604618352 407748936 180891783 982277590 826784832 55562439 253162847 454363792 630654282 545343047 851219159 349625600 113268955 280197087 238566083 964457058 790888716 472872093 55737682 496779423 534994606 681867282 180326025 939166214 73438603 508935147 109701411 989634120 34524134 565898084 866738154 803627710 741924130 646943019 918824316 131941925 184403717 984603628 525693831 433857683 684353541 966439867 497387002 353182943 495453014 107509615 801113884 755889886 635004012 776017600 67188035 608586200 274008818 555716448 565453969 329090845 230854903 389137344 391970451 620199685 268158506 995036106 213591478 837690857 228292471 175644094 218896810 615666647 573548268 149150036 792561626 739324479 228883983 322406167 395865226 808132620 524883165 840956687 68073278 507462757 748689885 885311734 490673528 173455494 776368400 667531160 933765342 636684483 163341523 874136879 935909630 513393338 781236710 623975920 401055312 663741289 17682978 258121536 262857511 423448737 900602774 293036452 18438669 226378744 69773182 620750721 909833205 110391894 790205146 333043463 916768899 724214718 922005734 783301179 506531451 314927450 538753736 871519470 978334426 53807817 350383857 570790990 479875456 414087266 641485821 281744399 206602048 708516861 278010087 412900899 910439236 163250456 444707686 340844613 336266379 607196697 202844575 728011355 529811242 517806651 898871440 615948707 686454215 35594271 973470656 374815045 253962885 129574086 110642296 911376654 492066815 742423330 785146467 484627204 68644717 17490195 318769420 393962315 552021535 582534643 152454082 549408718 485537261 613568878 682139664 436410762 345576697 241468023 264916343 60924639 359880553 364397660 93943898 730907232 520219388 211389013 693531947 415674179 662193058 385215028 490271648 850583491 77693342 556550448 521795068 798887022 505279073 243542043 813120697 277932309 896306982 792503348 337539051 613392516 896443752 427087437 644724333 448605279 917312325 663485266 656864538 54675469 570979476 696692889 83629083 680759191 823654347 629720665 455177914 578094333 307079048 193535123 686365332 871806818 596647901 415360298 797149398 231286372 669756693 641339372 391326789 307537057 865751309 146229508 89778686 111183163 636208167 870869919 297825427 836342246 919912404 144328015 579651312 867997369 381956563 568666229 105858387 589254619 705557640 386927567 575117303 75285248 360626061 826089922 694896266 897186296 223682470 270404496 261816775 638439471 55328258 578251784 318902154 156578049 695275368 345383494 705791902 605524390 456971810 589958418 684077912 90393832 619471062 748251656 768134423 943680575 359595098 39476235 882194525 267966536 757368631 904545430 938891996 353967626 494449653 554513414 49084013 320796547 187384947 344318937 111042035 622075414 926764065 144143089 178342364 229840718 925325457 587560948 562376946 903589307 481868886 759247378 585256152 880976736 897421852 496455347 769791267 918887262 873395825 459674035 904766713 477182679 855145909 35912111 177506414 722137288 704951570 413555778 680623125 757618982 672758415 573521781 723420697 64424358 804129020 628947585 345908197 127670744 773246590 845692232 606362933 230240528 389963966 201359629 275714558 612830047 286313354 121513647 759317273 393626148 907903450 75664783 385836883 392477144 458529305 404279987 228158308 619395592 545057469 681974554 32540716 694784814 52574855 948455139 519251191 396068223 563218018 595833549 705251793 465083395 108951610 817874343 230870551 565794900 622616365 202201390 293204528 965867653 26788550 636161012 919060738 822168563 362924104 137889694 176902705 226124642 602067678 586564110 852170820 696001810 595931033 761477586 777858882 326489503 330614437 200081813 176736649 334724103 80060278 558683496 977532153 452247665 504691818 448491449 99328169 63849431 203200116 553972159 552187289 110726644 917996501 840463980 285686601 916098009 845224320 586963325 50116366 683992666 157637760 603514896 533682004 343524466 596796359 832362720 758749342 737614534 22510945 170965268 398885867 16202947 156560181 744448056 706203148 971190502 823720934 980049641 23848150 284419641 757227897 632563472 689660290 66611697 645523808 848224178 312413422 831584923 698341997 523090202 26862652 172302765 889726730 732822901 810796029 848393477 657181609 350185726 442685097 586372973 736733364 492752832 754376948 230061262 657084038 760328887 278607319 23082794 857051452 744475621 135259902 275823314 33333750 215744518 4078069 979593954 160099076 28254601 874770937 782877208 712423907 811715410 801078594 504559926 709620514 977728860 161295251 69211508 102388698 822901021 897303103 479220875 776745155 607036269 611568517 305417838 877298547 926825645 864356410 795884496 984239742 930803170 644477670 88761913 653716727 114346357 848359143 521027877 419313416 203770751 364051641 349045945 140660982 185045402 975479657 264283096 21264888 322539744 754810382 120328296 574085761 253947609 595340188 579658359 733851952 194415986 453897129 443150624 226051506 426288660 490390340 895896112 439971291 538266663 82354484 790237622 365350299 15410057 991284462 300722675 391791531 749695013 503008256 257818538 877402302 438938143 444462286 644130236 959092817 485765418 263309763 495695062 893201660 488009890 711038849 961287475 950109060 113455254 596735378 5442771 853183801 598645810 177382881 980065318 309748872 345176066 243563798 728439715 706332128 852800212 178619252 609337524 862099311 679294898 897219103 757897631 276628375 839220202 245920020 580757122 275082 17730583 593483254 875188761 868341853 448141042 107495246 846732933 185713045 580917828 496974247 415632833 127225507 225431063 523286938 327971439 763481011 885696012 573479442 829899373 790628826 29637 806459655 692403162 60676133 436415480 196607418 468548788 979308635 809843777 507573254 587125529 771216570 13369190 202727686 694328048 396621822 235294953 851468220 672163843 819163244 676970351 432996277 687467860 912272368 534445222 873342700 387628353 366517152 658350871 695582947 182236085 989518567 926932491 635921711 574380392 910104795 569090350 378303716 131777416 437757306 618982717 969523327 199460357 169183166 425525178 209718958 894474021 724190591 794435283 59424235 72215263 846122702 568950415 509111591 442222046 826925965 553128927 96873445 63583233 832639289 736607351 923413104 812735475 418825406 453622831 493449925 810977017 91183673 331909383 85517030 696396061 220799317 504626298 887609662 149056994 480822908 746441043 468738822 933355087 590402797 553336480 853214300 976746104 865960503 641457289 869885255 894959213 781762092 283027233 159130815 295197702 597233618 128251327 699638498 534607500 606856064 609627293 639957883 732657413 699623248 261523808 38443904 489969174 666355801 340841971 408776667 419724320 380842721 461593236 792996447 610628224 812743771 319782617 788775299 417651670 903939279 739717095 619239980 584427366 586012007 114629339 613132695 526618875 736172536 489546897 661354115 289602050 699884008 551764407 418868831 162073045 606766280 975152252 602466317 806824470 85006973 112600313 285796415 325780882 578925529 587546686 959748251 396021154 627609102 367410320 582096183 995739851 563693765 581793678 204264794 259436542 486413196 186052416 648317492 20174461 397080416 544820559 562160761 831953011 185240596 352837116 5115436 451360522 748106208 944034114 10898964 104001887 133858995 203083348 147208418 806497193 352256287 689328007 297617505 734326327 196009584 4408455 233885273 531066472 264477241 910992358 26540937 763487341 555001466 512204589 39483894 776599580 264070142 137998063 76466483 733047085 13875581 629749631 563009545 847468475 474051213 698997483 559819742 797257090 674609885 962323430 584312836 173912249 862340663 57649442 934320233 799650805 420509387 284897716 969076982 64941607 186153720 399127108 825244311 788223857 881318523 142002426 281168330 354710349 700744006 960840256 489637730 920874636 305950491 556151917 384684929 763337352 833162081 235772440 322608068 84854827 159001915 960085111 450078471 170776979 182695271 480827281 622223537 195684506 960602054 592195343 469146420 127252296 28691281 580734871 766603865 317517359 692844155 225301199 112719409 643255612 545998126 796894681 599361221 795358491 196551922 371758994 581277642 394914135 373184268 325631049 972390555 280386174 43313620 135941453 608222381 872249342 842445319 329765905 189714863 958128427 31435408 802221105 628008958 367164667 94968918 406155944 837930629 585443294 916758649 873080197 171173059 252603276 190470850 537253530 804497545 410636717 230269096 198200050 585619521 775575312 498984324 601250755 542495437 974441701 159449333 302175297 613780391 422789024 756183920 190533488 58607537 122343836 715313474 299269484 270645963 581857878 737058214 100845978 679400265 398682416 862416136 95632343 725432642 341623440 775511966 960438914 75783530 864707695 749982236 358178534 371418675 495270999 139696999 878398956 708007189 675228702 278559003 827738239 775221265 657990747 551084473 24748160 78561979 603434579 573065408 101991628 614616868 72382056 140883921 425171880 409225522 526740353 913343442 27062301 698057570 122302155 719133978 592856583 100287436 195748308 58610084 660023550 867103269 491753983 932299383 979665201 5764209 16837635 124659205 670902384 160061140 219243854 455555414 723685626 427575301 156311875 996489744 521905922 590114129 123424337 365595302 537016694 921039818 244389733 940552871 579951726 600367238 422592052 563306792 146227435 662883395 72722442 216813133 28430482 593936333 533468189 288072903 795186373 57656426 921692949 569457085 430225667 85448368 752722688 851844953 66857089 899219117 707367224 118986498 490487860 991854573 98920469 514325054 346991119 524430559 154896308 311784378 510525297 426287870 60422625 157476668 267641878 132882145 740392818 124711570 495717690 852126945 952059710 566956224 711752653 688037987 765913059 532087353 106001877 445950165 398718624 121090055 290821682 272488759 591085885 108267607 773333350 460886582 409282420 788368846 861754433 838331371 238942794 759838591 744624384 758920662 740031972 582727797 371425242 464213567 960781123 405962368 227646870 764320886 71052052 341517931 261653793 291500598 94658648 953949715 654965214 550696894 649430783 958830116 215860271 796144349 62538337 611233178 822570188 237778604 639102625 86545685 155192669 315555977 173797744 126355373 684157964 471685191 732389128 490332352 643576719 752856087 46232587 979154340 304673529 694106957 859992950 660199635 610254041 953921567 665815317 737528907 958481824 518312233 908882717 419968569 122485536 668725743 110719718 791533656 198255094 195924113 230163403 292738841 689514926 67483937 727031712 143104034 88869806 774704561 248829977 252960299 922943281 290691328 569742587 509281153 463668663 10000016 730689857 448062277 438129707 329115714 933708213 281082842 909260932 261119324 607039302 105683199 987536783 305969165 219634199 947516784 129704492 890324474 163185122 428130472 107789497 661488876 249875217 996717765 914265972 844129205 482359815 947370100 843932972 323607993 165914774 265553483 869951922 470630429 20689666 845324722 355900765 232782599 379367150 363748666 359855124 60362474 626053092 287630985 491431128 742840147 116442059 662508028 758562917 317561343 987437133 775343163 183353986 82549938 692104100 840087065 895471553 445442852 985378579 759714897 229487540 979588604 572748936 32380273 151378698 284502280 41815751 334508501 956736502 436050304 994918514 548513064 91258660 291321328 107416310 923779316 293386870 352791122 840383010 513655131 314292922 676291732 968027430 396039420 344648891 850646594 931141027 530097894 65746567 280284687 908930520 67056401 25452057 828626651 60007587 909990964 276385409 500114302 491206015 302304817 210778382 243814324 162127996 10079966 538025883 741238202 523938890 930181317 922363193 982618898 832270221 819481658 118984995 232846732 407096233 132150276 841083847 540424126 647816777 433908949 621207765 398827347 385241910 611963787 152589797 494952445 298903733 775803395 688600839 210534643 439992971 98867057 921222040 647536392 473129440 540986442 370750413 675348843 961553161 401479515 929631329 971992428 469460743 359852993 402888607 829032336 481966256 273374412 409485198 663416880 77295823 745856768 92792377 547301842 223432096 622299820 411116987 373589537 330057871 532630479 293530898 66385158 646133734 17695398 462552221 66074631 340373547 744708221 861371829 723599198 406627576 981179102 646617260 343211469 647273114 883992732 11154412 430444455 563997515 432370896 527125799 694878367 920773940 57144288 472771760 755616210 719237941 877468542 564956016 886872142 492411573 990705711 719411362 866656235 633172024 972997509 850404651 324669005 788697302 913436899 43622496 826232202 800438878 463220691 228814784 354305965 613818500 69428527 752396420 548235860 34318813 331077974 788981804 699400302 435306951 354093541 974181222 234137574 315504235 711045148 466076018 79249845 923441343 378737199 287193735 384393542 462707926 918023612 303023249 490852004 192362060 687365871 5398425 517691673 689260701 665199254 833822350 931412845 868887941 268250885 976478170 843930135 660627990 572315890 161023655 823632058 106126821 639259349 977710049 1618603 725869788 28461864 940415915 844488999 708539311 479135547 219529973 529042493 64029645 444679698 830364869 566140037 181956367 689438423 69431553 135640471 181781545 570857538 659001730 941503108 292435505 41214294 566899582 401797040 730731248 945640861 977422806 139408267 780204992 361042072 609848298 651336385 105796666 804120894 173676532 358120349 780527030 32870289 556291256 966618840 26043098 172030779 668518993 270549122 141338028 885841390 517322264 582983272 642823415 107969223 488813133 768712071 739154971 764799067 987908701 636759713 545291711 994478641 461085452 933454085 260489310 148167851 445439320 189967371 11150599 774946026 90441772 909977709 136944493 862870486 138773953 9727593 389349756 463853445 176466488 750380131 876060453 578639466 300997623 832700843 702204554 448282361 764476361 153101834 294396778 914429516 499162711 623352308 903369429 175751373 525847060 782595508 871999534 750022634 1679706 689255960 479080171 392478035 595924941 861273124 797032029 274263499 961889220 447532102 126607562 746118413 560231677 612711671 892178807 529084321 5482961 654836474 865896199 972586638 230898257 912024462 489473039 26844318 107984443 520108593 183380428 522488180 862718697 717142410 812190477 839041679 914624189 57549602 661167361 452649600 160735678 253377120 363847064 157897042 55936019 331726666 127321350 579873543 162185675 520818554 588800643 125801087 735106575 309316105 21179012 363524582 78401308 215829532 44999198 238214283 341998635 706106653 111466912 17857142 637320026 707149672 242545200 627281929 884597816 799604928 571305983 678722260 365263971 130471837 892749208 170945574 306236945 934661065 845765790 293543885 831868846 253254091 699580558 859197533 662189320 329543942 262622793 760986451 221947000 437324054 593345832 74713888 779899720 722039398 327669240 183515123 838235682 655098119 110076201 875629407 352271216 868239567 65069105 296533198 648906978 438595118 126541128 596130710 930090882 677342486 680021735 385204101 818269195 506923013 764870317 946503345 990811178 261868222 473026211 329963625 940875425 476837102 910857368 450246913 809377782 28019103 518691473 145621359 37433701 978037164 720143631 734019030 162188162 96165145 729016097 497570311 462070947 821614578 362217777 699733250 839926531 751174543 457019006 308265767 627343193 907274796 865013793 972874193 449727248 280550792 190750768 157833973 849985297 599533127 426929096 535519615 632819315 413832699 182995061 867873203 355634905 60023739 4896503 118594115 786087392 235766220 556092324 324198727 975914888 380479009 107942326 421349646 656489629 752881372 548915843 861131918 328195636 904929060 138795934 392968320 595092881 442115867 222490404 877485641 226341476 450219478 749998814 42263158 974796389 202234016 234947911 407757960 551992288 307944595 437752052 838826461 102374851 832919698 364584083 426181156 755360676 970568746 242131714 561587565 103722111 754625847 453742480 413597601 23167338 253449016 484635918 106832710 826314910 740112350 530289084 51185433 73273511 589335804 579328743 570814472 557630360 555490465 610372668 819137613 893857939 394623852 490468986 268863707 741066098 954235827 419597741 528408070 70832250 175078161 663122600 604459898 651953950 86878414 344499277 299097889 454237426 588678238 960323006 788393844 515542478 100922347 637502651 311643029 773055898 352735981 572534525 810212561 131353223 607097683 793199679 618015791 945496747 931323952 570160276 214651572 364513967 797294482 968101331 225813544 705264937 799116330 360476124 666658825 110265199 812808275 915264330 197293198 433935911 604550522 310559101 383068539 2272047 826008533 342090131 997480674 687344924 91070397 310567718 756739494 297750243 334980330 758341797 113621367 693309602 782634160 850981561 77950389 492415681 376145273 618751350 772840727 749260065 408817412 468791730 598416698 904407664 567108303 449576213 345592904 9507557 325230304 909922040 256614427 493615536 991658040 935758514 755376278 165182968 697814683 966509143 875493546 919290970 294229665 885507408 651546283 314973868 430782029 495073859 498673968 10517111 113772904 306040447 544235343 192224305 979102440 965331972 537647949 696208645 318682333 476293316 701425062 531385840 924281514 540484415 764448850 52037926 568662118 130175767 633245734 188909655 546362982 851512813 112481071 605228814 764485693 282899156 346800499 620079048 253432044 858031582 128813715 546564603 285025517 465503938 270119098 144720331 513985154 968897950 396716798 474168713 701399534 118850481 133945862 294195279 667048771 662464116 479705667 542199696 119571737 67198504 210509628 675557380 673604854 934455235 718290902 345873433 669127363 488931870 945880892 687442615 363287192 352000173 587522068 823698998 38305405 407725376 314328458 451140910 823634281 971131572 91469559 712868549 177621210 950592161 371039220 305346236 375298344 355243347 165280621 531601541 394845188 460969544 748533427 275361617 705465288 704976544 990312955 809579595 26768642 646862505 903570431 223291831 956381269 345432379 469971064 354302199 592100002 62089969 431931565 267170782 146362327 912454381 694511269 33733462 244544501 237708244 61264796 85974398 489613932 191353160 272685680 818410847 667414736 67202499 743472462 141221732 188156350 734749304 323157083 416852564 723521583 769202566 258440086 856775765 543448420 583178917 418036983 33802619 17658149 935451869 564548799 181723409 514744779 471089307 244081716 37587281 615495704 420616933 61360332 308530554 545268263 875742253 135111829 219974294 260606413 350860746 73664845 717504571 170184898 126269479 431795218 319165658 989655663 681319256 331777011 864758986 201500250 900989844 196206364 401663877 776693013 415201134 687786869 598447341 56673599 819194362 336770401 412360532 560950331 301175481 460814649 784369915 441548334 180057627 336962329 589122582 63208388 494473437 501313210 798355234 608605967 115174989 2546581 796929714 378367408 168545619 757746142 967873675 151864186 720908811 968603965 5943908 363481927 44170753 900331166 839659907 421720426 778729495 96228013 131678489 654251023 339410456 280189969 12936853 636257662 687840600 238560415 846473601 702348134 650300390 890495292 514939953 464717375 444693985 288822538 396220420 925037218 969530441 754320620 650420037 846197337 819378079 841760303 205063684 591042978 235655811 972173794 370609573 754574130 99510499 926081934 233952298 15352854 240413085 817347430 23334812 681308776 799235686 310483773 296666347 525557928 328364359 222064398 766240141 347961724 949017870 239416905 550767606 301166923 645097989 822946134 299493368 698716857 820516765 868466843 710719725 7268877 722768670 859298497 517126471 754184413 337129564 481008505 289512255 948591580 781814240 477732577 833027338 120205133 58259039 138803861 50725516 961202677 165937084 605446383 526020777 873285263 318770843 59610471 645389068 3248693 943710648 857539651 217123622 977198293 579328360 926835337 73833238 545804580 991002281 976437327 133293269 616142072 796331429 170276384 272621308 399745232 272493077 547693547 901500650 846563736 424499138 632489925 213172725 219621957 995551241 118699051 906191854 864897873 619229179 972583977 997221931 164234353 237196509 329271069 759804501 306762149 370129086 760870881 440725376 42171684 409990952 622853304 294039689 788246857 609504904 961098081 952768186 265288833 10249605 90951738 761628546 290966713 638245363 72989373 922730970 155441900 422741645 319478001 420573163 571331123 622296208 532537670 872094645 692446373 992369133 929977732 771043819 944053694 636867413 499858662 995052089 551901730 275947664 570558692 171092186 107940304 482040195 217897611 466568300 846311856 338966630 752101984 38853360 42393480 129524694 847925987 810429447 151973851 608049865 281534197 425923476 707359097 88209356 596713320 913409211 804076829 188838712 637748428 693868392 184912754 125546213 258523190 554255462 198275633 435030612 101582798 389033016 176311156 252489076 305822874 392737932 243137951 151791518 769606121 884472085 612029875 481170744 508305533 122803455 828365610 678247597 755862370 452879916 22516464 775706928 90422332 862912625 713162961 772993848 449718986 725495225 510324679 643440495 741202749 88828642 846322143 702797958 54649180 64336041 298370372 714361557 598915794 410756798 178400028 958084535 876304488 149581214 466063516 392089373 133771200 760762956 386793814 483161897 773126932 263230109 725033580 819553864 926357800 656504902 495299773 105305554 542983685 981159238 725686482 899264468 38567578 152657440 427495931 362497613 720653724 130978135 324888096 112073075 627356898 17957355 28615465 685073418 953817929 323849482 88341139 216178168 642583717 31864196 437829809 243236620 589876429 338403899 318481081 23968089 878059219 97801457 622581088 520142358 641818412 7363514 320719626 210319173 715434313 282447797 336608726 730445317 389938047 932638673 706654462 548893599 640955532 182632593 281768552 958819752 431924566 199099765 514829879 356717763 756829831 635954574 61304521 312450324 740301642 548524611 966613755 93822239 220651029 955962812 621971816 436878326 504105058 243490286 569776905 870993514 146273429 3227543 949299480 885362975 384882108 416977383 166609193 594578309 318055622 367178918 518306625 900156077 249986249 292465168 619498290 815611933 45179282 667035892 749143936 633951200 677055606 508721446 720193589 429310397 24598919 854429340 916631301 361397193 782916763 678702876 708468016 6847239 389394395 708626970 751095704 708540303 225555155 875962494 696706692