6009
139789866 67178750 702387254 265309656 655431101 963729195 672191425 547971240 816493800 807577310 172566386 75519794 471382029 507749335 494722263 614697859 507571919 641846850 494904507 909608166 903731239 374466437 966510630 488460817 427471645 148889848 528899160 88829086 30202141 875310833 309351447 169992006 795005934 11738700 287818014 450437034 827984246 960009438 850924625 644478046 767586748 23491011 719997839 91485128 383756697 67236453 706182986 891328615 709083303 53603844 653453132 465330893 428070281 472480114 806308061 855541925 473886313 187723572 796887362 504088453 63034404 106238808 674080459 710556690 970493859 961898472 13510075 798478105 774424261 864434700 295472502 394527360 740442062 867986692 486012488 124198758 935223145 192195473 868043725 496822799 245799317 374013208 962153691 673869597 846493321 620978103 381927873 172895986 808701675 31331586 676984438 724252430 137570394 203581248 434809119 108064252 17996071 448319194 759058708 792420332 165270245 907047561 186947691 905712306 775034253 672960178 29911063 562773749 717672003 750471139 59596547 963471319 124484347 874266589 489857267 823494019 495244691 724301491 996390004 156462717 755633076 673374442 880715147 893203469 876955689 168040617 853784073 894951760 616359810 465359132 539888443 781630054 224923045 726836133 539858711 999957297 252312663 422286126 415247397 969984665 172757264 474843943 785972335 149757962 201626883 128345953 973251981 696871573 852647443 969641984 853334290 460796870 495532777 586565788 206516691 225004818 754606404 60300763 972472929 223482566 378176246 512361371 5112619 603099290 91713855 397487682 455572938 196542869 819773807 870820334 19043885 992531070 198180628 805016219 142289032 399807510 785878523 968057364 949195435 491042317 790215699 655046076 951839187 138264828 241611863 158355877 363269645 996218266 71172991 188258925 72217183 301865588 700620295 77329802 904964878 644850501 327333835 213054167 841393370 147107641 936390853 860437254 992155062 134571480 517969825 986960445 386895342 303848347 955017808 188607128 794890664 597749859 843653203 599246202 736014686 85265065 757602078 99284330 933999682 681291420 140059606 6216865 983157007 840679900 936063018 740638236 338046752 115913204 953692403 179440121 263020844 742599607 39877375 107692257 729687438 410363551 94652702 116582779 714211897 902186861 157706258 361618912 499936719 1359460 960865113 88467756 939140876 570983542 40268437 725656910 104791313 180328042 584390126 87948320 21007941 372969495 828586555 211571045 488882698 634795309 391011165 751903541 229911267 283404891 859595797 959598705 693768441 806764850 928697835 260496690 708951711 86404093 474631953 61404781 87763552 288013418 149872537 879420780 858996959 190140973 605077689 963788272 370469015 41984166 904252943 243993307 414953660 585355849 455564351 903836357 72667510 699091868 508256249 302578776 982496758 220368397 262177480 528781551 27133247 43391667 641794592 588601309 129795759 116426544 650006089 70075662 404439961 652394977 949496441 115953272 842535950 407090481 932257895 65521316 449074646 836510837 162030974 864028305 274383037 617595325 620381013 347050546 169203544 128637261 649629322 4216653 349005658 911806801 532998203 228655256 955198467 27309146 817256564 937510577 143735690 319779004 7586239 400692002 972173981 809599031 516645273 667226282 69205864 301419519 732747597 370796861 137930355 894778570 87341518 264829744 364890246 707722530 611880289 534093789 836359791 261509610 538310442 37881800 25832763 923824996 266537055 833547581 951134142 83793618 771058158 94869831 256088973 631160748 348078184 228262953 293276130 864723457 895489234 214998345 18659327 480753182 585795206 9106034 228048104 673136723 273935777 445454701 380859252 885816065 979548490 69735394 147325675 370375283 107617193 25674789 146716630 226670599 859222369 97850771 162980568 482796878 45236953 419069541 966473977 393315137 499848845 112266459 110554945 247854431 327264803 129214271 728607612 913060008 138320304 809172067 586196730 412256080 254626768 819572334 150588497 86691609 889307727 150430523 309583243 849441272 176105311 456299872 928628222 887844031 554150643 91608790 223157261 451903947 363194682 189631237 845219083 863043526 301897695 808290379 110897956 629162498 937504650 692021920 394738857 928341305 353710338 980935587 193113737 608337105 653024272 343702233 547545065 394848350 494132755 857128307 96805973 670238065 313428179 25434195 410598447 720095173 969559336 633755707 171999119 185270369 823386944 869734554 48313894 977800990 678024932 11728202 459479839 468045933 556266473 854218696 248903590 909976810 687670634 442017326 370830267 340694905 785719558 918375331 735543254 279852312 628019990 832349227 802606728 941448168 710299773 213205174 514059692 679859108 846960881 686058810 865129476 522864176 408309715 765959721 353181517 86334647 630204274 812661356 406896931 38987098 666880051 655800520 801480260 207067036 97817845 24826878 547761940 736053754 943202208 135821545 15906065 423738549 820687123 671029144 217703068 530986895 884234318 731762759 63362354 583711550 270337921 781008181 959092077 678647635 399484254 312273593 617498633 29688527 124934948 24395564 921191977 644331350 532712435 722672236 851398385 483046632 747499113 251676676 71616737 543217672 240014573 87522802 966956221 60701695 611068297 37175640 444204942 347818966 768938399 507567295 931530515 39276319 141091828 743138943 717923953 540576081 55412536 187938938 422780959 32863835 64850853 343972935 529711537 597563287 919161522 233626273 933126270 519176986 337819301 4743007 62394658 577833873 944782160 881867230 638535567 555850456 919042869 82740508 903669422 540497619 442824155 687716288 579773937 583915982 283371583 150214242 124492062 191300470 338153179 399789372 76680656 403004031 743762307 606392192 853083669 515440180 692534817 786209939 34617166 30354117 643469297 949528175 608187989 588251456 683911756 99239907 996618263 455470976 34496767 752804036 995968595 329837273 293036676 428258883 913753254 576408258 578473124 890761667 767708727 769142654 143067390 844389382 24663036 886829696 303297926 877746705 254786228 995832742 516472995 289403393 26186858 159942291 91447919 486891198 600710098 775359674 438647456 597328360 230830649 473144222 202648748 79315595 802981494 495685423 507574478 569251099 72093680 86047601 312529117 839802406 707706607 455596507 536708139 732369642 194942554 840006064 610116346 449728781 835838805 126589340 591648525 714542014 139047982 683096443 53949563 739758079 458456116 492597019 189602791 541803117 818257592 392251538 621118711 473755438 887936960 128693188 43006536 812546991 67257141 208052005 504865748 774963747 516164863 41573886 359849740 711107416 881579950 969966086 13352549 569935106 949071777 605001073 136993472 940636111 140613868 43459386 532910541 599069983 536056404 722513331 140873099 206830348 967281220 614508162 680585785 707734531 743201349 576108672 520281521 662974841 784160676 25147268 290454939 152841890 919237506 650304679 863949306 653333807 472787116 729818206 75785264 274375244 187335630 212778735 215011354 327949497 256238121 747921895 927019480 644810876 322951577 920408930 851641223 142749149 387433443 532227007 850483679 130634792 108335679 223281552 646125984 745012706 100945171 936580923 897854596 20182676 586885601 614320253 673516482 59672716 196654810 749301746 186564311 383990439 814596832 401575665 711939936 70834952 2013911 491475767 568162180 177481839 264401048 419803402 320230987 651834491 804546761 170714666 634985634 765398791 393996217 281111617 362927848 494941387 70208891 113298795 367640415 657094491 727619047 41156896 569283558 924273856 642974993 755847869 160780647 310088177 9939885 872720582 233439480 11953795 364196348 801601659 41951985 628597395 73921413 362182972 132948237 878468173 532897637 767933870 643866963 779410205 49045487 6794810 126867943 119254377 120093605 494508357 628865220 700229003 388181605 50665129 477019211 31156597 659029349 637799857 193761125 668969233 363036790 427200605 533439379 727233137 228802263 575391364 208346883 302723675 937574335 341295120 33708199 322988323 109228989 677575161 102398527 10790827 536886323 81782821 982561556 509496279 576291178 463943127 62241633 964472782 367124607 391777195 848145730 26153956 29577051 41906855 547639540 245130192 469107459 81078919 972363328 550426073 508986634 33226563 853149748 299077320 227038034 886857946 474581994 188783374 416949459 429496872 52090553 806352133 511279692 34652108 168364763 87570869 351111586 230606395 52043650 718236192 622383590 752705732 596906499 504476992 794612586 144546039 749607184 116236396 78141309 574486863 666662468 439644294 460229777 372328567 738721613 687267810 111702865 65819958 876051184 381168675 495316829 928141736 187520807 6596520 815310195 355885569 94167389 18938132 439008315 998727390 737174323 61391904 603949473 186597174 418385248 251078410 331143212 20508783 367314805 261800872 447511997 886493625 701445165 907741774 111338543 292683129 595009583 223041407 358503086 323577118 604210081 853819914 251718853 644247239 860416433 67029047 132807 807100173 85967178 291657474 658343915 675657853 205565729 114809739 862255026 623950976 365888149 45914589 496976110 733202953 307715460 944488107 472212929 9160624 852229880 583551472 154360104 299755814 806592878 512863189 623332932 263319311 366683102 727568136 907566549 79615886 647113535 760215708 739232411 585597064 51873181 250092677 113771268 109955261 364902415 976026293 733906237 730790563 874457233 83398698 316509868 34689044 27886804 788722796 43849667 732633035 372274267 50726122 32388849 31383497 563589310 508238132 147219159 930272411 88322619 54785707 862404649 735436153 667517766 601637059 321033217 571907298 851729735 434804484 681862559 69148501 263347129 268285147 799939064 137804361 351683844 116448931 25009757 232087000 905171726 68859423 964720034 129962345 119585545 849625234 13862193 535691206 210379717 161081351 318479969 298702336 68383409 180884617 34138488 735901175 635038027 207688056 160324824 339284113 642492540 694703734 408432613 758356020 962988880 208371676 748676732 167189076 177336958 773686488 399276075 82508684 695062263 216512460 64987380 667164159 66137694 78849572 202855364 276517410 239930922 521335332 575219745 308314330 554736300 461874585 896731856 189774326 669562640 57056680 529058438 164571531 604276765 937491051 922927550 419781997 998379078 671604282 586971072 175716036 297807121 838763498 110741071 992869383 55275957 28244802 660033541 121413650 107094373 715405257 250447412 199541646 89256940 678183508 507855975 643993240 140058092 257104183 833767565 809620732 166677214 215342355 974192262 770953978 5349757 749636164 190735974 3728834 273756797 630223397 31961221 571563917 468986894 142702291 564433300 376779203 23463444 76983192 350709204 130557816 792388448 601156615 330099461 881645388 131856475 690471788 378154979 271914566 947575970 64438895 934051649 114253183 279781249 760760263 885207160 137647357 510396426 928459486 141376191 784153222 558682882 25853763 208233490 880186128 21072406 772666789 256965330 44535849 702166333 607674533 27610017 347071132 61347500 357709477 81232871 193203974 48181264 459387849 317634891 848273585 523826744 251686540 962526767 803607992 12446802 700250279 941255349 375359579 481226116 935147891 12029152 39908997 813518005 220262641 772611476 834590410 845445782 29576805 731642611 547612114 489767690 759252627 894683245 403631541 116962103 975916116 596835514 17659719 287820316 914470404 718449655 811647059 18673295 533492774 467771403 883636448 86259404 261543103 111512378 567485519 49207345 123541529 459910867 862725349 196320522 232522343 549832111 41766303 114615499 281474721 441894768 456899540 40727347 189094364 860531080 10205801 17526831 309882945 880381871 305347147 76869701 451347878 116994205 95542995 984840651 584765607 979179443 71100054 846308709 90691820 638585572 895516053 66749701 98496438 610757754 263070222 183535132 160589864 157352876 150666983 294580936 599247643 607566522 187824634 788342006 468097602 50546786 805868837 777980546 930928657 111215983 854850246 234792886 80726539 802909593 219633536 665492146 634605387 143249941 364317206 577813558 781835512 112349611 644563258 732848301 723107364 760149831 768899785 736213579 917502706 919566767 30794514 516750348 527133288 218619147 157608706 847747241 269165932 963477542 478244139 52610940 74693524 185610736 287403825 7936414 988520328 359553712 673428559 623125714 502803652 890262117 53455624 137155515 2611727 698018881 870003816 578235442 310685064 491419952 166965372 228187769 410986718 197759885 597454469 790636357 268895383 755063174 638383598 538061314 718540715 116627736 443188606 645750590 154754823 730592430 653687003 143275151 90146142 179631914 618917216 445466145 69894030 672372839 582621660 925022108 222908072 305141827 355773901 533593135 796561778 522739272 761780903 60064847 573015508 211751723 850701203 841910890 966814896 341601152 232488555 537871962 310745239 675677160 36138903 465500062 258785942 689825906 608775212 201448435 721974171 80208779 646914579 644384552 752581618 229536238 421923011 975489689 534678064 777696911 509082823 183756193 152952534 123380077 243821039 725968041 335131800 94522242 420395282 154463047 436123393 652883836 692335009 746868632 328560996 728473911 64885045 587346937 270816168 673660256 788795371 992790338 753869034 288226301 637174889 358967003 517762539 59097899 334456691 904956954 689311161 696055865 88713147 694780046 819435942 332534185 273264438 7084093 279572778 693659719 161547139 715696171 346543555 853882147 315081154 527620902 434872410 379966198 114967838 705688577 906142805 756279560 698478915 512528190 44505860 188170155 871495193 414784750 99784406 58468235 172258056 641611918 754524100 260971202 336391964 426476393 446021738 609656401 433560485 725594516 155832472 447623975 293807038 502376026 154022474 608888191 29996927 588894883 841370740 997481116 294583459 747513544 606277027 845578725 112558085 503299238 33748880 984053277 770600340 986049637 42521512 942858395 627661554 797045611 56345948 816569869 76038355 502367685 278742622 509598839 227962200 434575093 957222813 521769237 936951118 111245286 983173779 819464396 552656520 824544518 669461863 847239979 424574413 128255241 545335055 537132498 484070830 431600286 373702126 254671169 417649922 416223637 50045915 897827828 65785599 106391862 714397696 141823953 608759547 993140317 503939143 836721746 280231761 313678308 211007335 69699230 277439945 46697465 889163625 830096465 871241983 411141839 529852795 148332747 391913431 75187849 537981596 875984261 506788135 911683722 130655429 776954408 180423710 33217696 674782235 246209309 139609557 241696283 240549613 748369103 87352951 744488756 437607201 367584712 58167063 648614535 437283941 335607007 695311999 178963918 18219823 419070333 442622108 548072617 419919432 834535539 623260466 957901027 710519799 982564952 869584748 693691579 759519359 50008458 726909274 286817946 148734118 866518831 381030580 389283730 467404285 468383530 133772485 905011485 688484593 44455899 406142371 125768534 232579258 101454370 157248803 250799080 373041054 599870910 798871697 792960485 286922800 274648514 603377864 997442598 257213465 325478963 543650529 869249175 228003772 123076154 8583472 376737889 842111336 389614051 618537971 309515621 857997581 604826807 67043457 398998525 649282706 473185828 377283410 881861963 427156549 534532212 132661042 800197602 986919474 784049090 445674439 273842273 58697603 49052302 123801223 168427419 227047616 519968103 37676594 455051388 643044256 46260065 831789276 337671944 435874116 302843598 647187564 146388048 907670405 714231020 545386572 409469462 39933199 922669982 143847776 467089747 309718545 129025169 119803701 149154370 913074259 565478139 422996643 971771861 467046792 399314217 140199280 694094407 919282319 30392225 1662146 414842926 76652289 833451422 752514869 365042756 136295019 252218784 363947155 896481775 966449804 909333727 305951236 6383002 684520060 449799011 325989101 846754956 578824180 445792801 995909326 344414790 11270939 271422320 168703002 330834082 670736536 161418633 877444840 590018854 191810857 879106986 4861779 120979498 565074759 609893000 338538605 553886129 862111783 702485760 450367904 681077938 464335838 608835491 539977292 1372249 58634502 865966392 848127204 489975033 311759192 844036529 834389822 175546482 115458848 3092823 358896915 638711735 17027808 236341754 81246940 208838664 115448739 86108719 182334513 533039849 548518070 520873118 86925978 410629852 223358877 389810233 91707790 687694714 998645723 484201433 689066962 909796576 350167824 389710517 252287960 514443367 86263398 86677781 689989848 54238597 942286956 48886762 692950332 959314763 137744867 774197271 20669778 105709958 712822341 203004291 638749806 261340410 723877408 578192135 524486614 799752636 968002367 468710755 339963701 966648090 952912187 29030662 728961017 155596362 271257530 981248977 670039728 357520927 920443109 212545927 411759524 715246416 113949040 104709855 527077530 251693906 878907125 547747308 209920215 444245818 603267950 848670021 705586227 179661709 279378507 82589192 979414344 247380874 551299946 319378044 66545315 504212132 200925057 795506331 659808493 472182586 629271659 182364572 829703513 549714768 394910498 93979388 117477535 508859537 198689242 644555065 760553443 930112718 44818724 970473657 374358535 648086673 671660029 932461114 827748381 951038536 15050305 807162724 50935761 566350251 979057119 117481075 923078734 32498527 765503757 435403579 504681112 247291768 617768150 186900976 797006535 12678648 280880363 914484069 521538184 332085956 411555485 134607978 262198674 456374208 957597987 489073560 104460880 481774367 421534673 932209260 285329254 289101330 591888335 336265014 855451580 423461805 306262440 631046665 455960331 924282549 66450243 960641443 171574316 684218393 58770 821097202 549413392 133455485 588097622 70951575 465541440 999653107 58075905 727740113 456027314 15673891 69330025 413004546 349964609 490864697 197730157 635293863 779966026 789618492 971558876 487933957 65596648 130337668 118980622 521556979 54620216 37947216 334714773 78710883 574681960 334773542 899808084 124095351 468229026 340422057 47563278 933770466 340075163 105639182 514026930 648618829 973829424 583356954 61623374 176310384 926738003 259353530 811604246 559220380 901488373 635679474 47154337 967085021 766017141 18651310 488641999 673153708 909114877 823356771 604380942 483796837 10646664 356705377 460408539 331392042 697127433 507971816 117678859 37202596 466127349 631705788 538337776 292473124 67579094 599961149 468783508 994317096 711831030 132904105 406053827 613319403 768583578 305724515 432920775 387117070 176892176 921562773 60270777 86007053 597435895 517168070 422320241 460598910 873873446 882728779 791990951 571000879 243216947 909669809 460719826 709344295 393891949 999057601 854333771 461471042 451535101 175633630 308304489 15882482 308537734 714358315 629201884 77121312 20082830 62122658 464238381 49491357 836201782 377025510 135498409 286154028 894193579 557818649 746752938 620583377 293063780 391260240 44100607 536280726 300930049 504820432 98141372 694821997 356394384 952475142 8809390 660445836 128108771 169630230 676328317 436646505 883988544 158046553 366284168 756587725 72685562 830522548 806079082 908887344 60064409 794093842 47557723 806774340 204428843 646827012 427357716 497492622 38087252 471458322 33773347 191533652 828795105 131914718 886355648 37705840 84389860 747681389 698151675 65014982 917311618 374479991 354177838 653816513 532526543 720462005 262920590 605212105 403500905 68999671 366615800 463565313 715609864 266689874 122856004 920038706 913516886 550213719 417531327 951604137 874188392 303821025 143137788 702983496 435735743 882009787 740689335 372641954 482207527 291357361 290173287 399519144 665837352 644351125 53335656 50880246 364813129 168772597 508608702 768314033 90288619 875224501 84395698 805898483 141914375 207251701 725937188 907947612 609981772 995984867 712068100 484170163 299805891 707722239 39670011 588057985 442248377 632875697 960699938 924455903 924233058 103389577 176491398 442586761 747740701 82343405 493467006 112553829 251116002 2075708 733384214 341404620 729816560 670296263 147303102 724247286 877547963 725756642 484711249 340046086 721741508 196779348 824216249 874063750 904501586 716402611 462121735 199266314 349278307 275338024 123722216 126027716 378727600 300213613 568614476 126468300 382557018 62081482 91538481 633673019 916673541 677439046 975077638 499006452 200251660 974897092 75770090 77799622 700653733 560481338 270362060 274911592 609777038 94578308 1491693 366794975 663497270 463613427 566061289 12775576 591467803 689783504 138803292 970195402 842513469 559934119 949180054 77586838 474531952 893234886 711259856 243721844 423190283 538853845 742728296 623441942 366267288 671014737 553757915 66921020 84012426 824119974 194348963 693789463 771214633 195840656 60584438 287228254 511970434 626645726 152520182 103438236 168945581 143839825 926149990 11459049 703773943 727846395 89045886 178305895 473597632 652822093 422027738 896787914 44192290 17272385 372746207 410459577 688287121 779020473 329896949 772299547 455656799 376762263 318605361 79387783 572602918 379189798 366616037 84573352 858351875 519136218 40527939 27297456 662976042 966677928 891272856 366749984 547040674 832835094 397572230 20638305 338173538 819599968 769942570 234882179 689388704 142688776 645341756 230192177 774225601 827755056 2491723 229882399 204517318 173613435 309270181 629636588 552803233 675886217 566726291 263671459 47538786 607254229 143485266 710514827 426448509 34758122 77264811 973489182 720109567 327353392 846643839 910799456 146953359 616586408 145681635 688858415 611791536 643539742 919050591 238533488 471294797 774058665 468415886 528328466 947672099 630202418 157965053 352991683 158604987 724691343 616663142 206143772 184461924 760148407 916658599 463426784 647422880 846439761 289432317 220048798 173793152 136076155 130848254 173262863 605178915 129046240 862121277 69486802 772585981 633688219 308020289 96397129 407746883 776436174 624725594 207935333 259154943 782690647 560927016 417759929 359898341 177590157 623903701 396876616 937738563 540562299 860303399 437677795 239518411 149735716 657726592 413311562 138328222 788574845 439090776 743507136 917621084 153728404 812993937 542723416 787416622 121014225 639120544 47679856 749966750 263846138 255615189 9121693 899053136 816542204 426881621 111467828 994132360 50785321 508344444 784387274 443863971 368647842 74581420 683382381 370899909 732308012 949210295 509228131 373399208 388301070 252735266 143536644 542029474 65729203 686260059 181962447 39259779 325380603 229642303 789226529 441743092 485257491 650864573 340796227 301799694 77746193 452264054 148448405 981047866 960608497 785352030 277428188 181772691 859933450 813326921 552672599 592241461 762537215 61900729 965640668 3354636 167152347 109177311 397900461 85397901 647953722 579862908 124657679 973334324 809505210 766400559 267593767 294762700 269781483 608389993 449078745 200044028 913170398 597527149 33608245 726295247 235395530 311036432 908067937 95328979 124363352 313256887 540086791 739416918 227673968 358243811 595287906 247342666 319937473 993188366 332740566 967891194 573051273 309914596 793741869 235072834 928831507 61335635 529835533 198612989 522241979 978914277 398657016 435412377 428957777 432265260 14223975 664353307 595818044 922291911 612198637 572697747 88065149 152285428 164631017 168255468 510529238 759918922 415598133 830466710 753107287 748338698 650874256 178674912 910769646 444616124 413747745 839601152 358468111 796099630 890730492 880710089 627530258 141903860 168638817 56488035 574169119 182862791 573357693 22503514 105154701 38072681 595201261 45736202 190358108 759832277 213991669 553403697 519751198 629589802 236386759 125374836 230444851 887261014 156566099 141214496 184393489 570313844 833331999 542861599 218929825 576578843 423571688 846460082 718482702 592210504 755464468 145168172 775073295 181338512 167671686 732744347 219411193 762872946 630996900 409769300 522705222 844988569 963172997 894972771 327094722 52076107 20347606 410055924 939337120 29430057 403786772 123730608 599743900 89635122 666592207 818673724 666213964 942680246 517650157 384696665 387407101 273114625 529864837 14996747 454453136 697536522 747741094 673864328 312925819 231254345 936149980 835631040 76242913 751839328 583120162 255853986 803915434 455984119 665909910 743252553 485414175 69696681 719499512 85158074 11848154 238608070 756348149 678062118 181288315 126514658 62758782 568695416 399629282 445139970 583692162 706598769 995192843 183949607 232979449 308118661 415203952 169129428 996266052 343963216 920968755 579386213 452333554 577400540 35370332 118243463 173169444 373300858 40456495 892668955 310975284 52304648 131277025 67323432 582883117 165081691 46354441 498158251 733777106 445983722 943298220 169985620 5098843 791007415 206451578 238078291 99126075 621655529 407207718 947908479 818135097 180692824 379811043 270468650 758093363 267697726 241228464 931262806 640998584 134201310 676448112 951973867 39022309 807725136 871813650 621905426 972806827 918168091 120063676 559100284 216668164 915878247 581602255 221767006 559402013 788053833 459845296 511044440 262225713 867053013 458952918 80360809 900262188 838763960 203345810 510871902 106461686 444574273 294651059 599976621 431291934 971099171 551950487 470314243 631340658 276280488 944736020 456663836 194448578 917316047 15764120 411116742 685710645 449882726 632883747 245112658 237936558 92729043 756157097 500162271 812298407 67626366 433039431 565076947 758906677 636385241 75948848 717884714 80959513 370599907 317861334 364767799 194215429 722328172 835082041 825556086 998608660 632334412 282219922 45573589 549650458 150500393 456690330 87877454 600383118 942090429 332990111 690836028 887335823 941663559 43514650 552150581 9289924 476554080 117227527 620712953 112939320 45692727 338597666 46415185 416292633 508975352 411182983 610508061 231303523 98781375 288580498 82428534 731115786 570800419 128002123 133282595 573817163 584692452 221160048 26716633 379299232 406666511 717552660 266635054 348330069 761067309 818785635 210136345 237621388 788529513 830849297 203077060 834222239 21963314 249492244 103031223 530938665 513191578 713539283 614758540 611972952 2119781 697187073 195605089 425436551 825189195 181404035 999253714 262397999 402564082 25970346 641697230 809230592 596039357 908332284 10077013 357106665 579634270 72729709 447244404 220680134 903579005 650321463 54902373 778058670 899813706 157933595 161513687 265521635 723989230 776272226 877494586 578625362 473459298 925616026 4061912 151164845 107020060 855831977 413562843 362100494 734318674 55260072 23847437 182874382 816108707 33924449 539981046 248259328 106654157 987225450 468939462 862749513 490063264 523841834 640808183 242393322 534291780 802321869 507914956 258281009 431110446 237925894 836906370 904569743 163541919 693484634 55734587 123078331 401832962 321813781 485178824 988667988 377073853 509026260 171542369 45698911 542950709 564039767 293958239 502121217 403781568 762897700 364870730 893844831 139255885 858195264 136238152 673547664 513033484 644153108 931828673 944143929 882079001 621251394 701230023 898137271 167252379 609480962 21215601 421601693 931294742 506394424 410269680 160884946 15420684 434328400 206583857 410887744 998368166 500542095 913008960 402149733 263439794 130396041 148510916 402695678 988591304 284749067 76243341 354141139 781418526 860588365 298285067 516013878 334356111 999515090 414151149 354124841 461512403 287883101 775726533 392807144 794277525 38512564 553692090 662214560 472840964 760275946 925618655 471209129 113334392 691143966 725875214 376774185 821540007 874386129 631986214 662647662 11651547 560745906 16788801 793070073 273850623 167590219 309083950 608206733 19621660 575751450 962331573 481134062 863634551 590574458 726457558 510428427 629087021 132665999 25159338 101927984 892941944 950777992 425653465 6276335 641921957 151528678 235566871 315978315 25914806 867553084 831142329 37566352 280815341 700447481 683152776 554665963 868037699 992236726 15389047 740175711 420504527 977720620 73826124 284139077 420811429 800283681 794567503 49898449 932949679 819726840 4342785 678407974 623021183 429996249 537200660 117459492 581524926 772767530 433437806 459956083 492836965 117096486 350038786 773652306 817543966 33191562 180834620 538098017 877944639 196223667 278273727 150965517 26460638 352099850 435104594 447272066 4899883 82188448 497170514 937849561 754431640 501513298 616257535 377452822 931509546 5974546 494912313 365550823 778742076 780866471 678023257 124095392 897962956 28062043 750264049 715506922 913769956 931098669 106121290 644230946 127322335 384395016 795196462 153782972 589011217 82817407 601055037 593911099 17522207 950741902 531760660 771953846 304771552 534546 1923019 88797449 6509091 496835332 454348272 637767518 130218154 132371528 761862910 28181109 12949922 364643310 596204382 779236229 295741978 702325671 275983526 275580664 86720686 923696340 429363635 528248255 6513746 882935023 122159353 24035952 833676925 506436364 648506149 138448476 506970909 650429168 79762276 365996352 147264499 534110547 3763869 129999004 518998427 618143130 158180112 384464700 982786440 754384494 16217281 131044769 309226516 144717158 406625433 248463554 68413497 835989067 776711808 927443595 571440442 898871160 803995898 257633718 257823876 452502047 248598545 764794784 102931214 328360820 130791135 102712064 862471367 987071356 85227419 233986145 605214485 243407530 470967196 440517276 850308375 487184476 571562045 159534891 631901634 978187477 407998444 552831482 666692895 37226603 480275076 238133336 936097762 136787326 495767053 46437989 589289372 744365597 811232773 544736937 72726417 794540259 499965352 787714135 634127966 585192770 874216631 91858803 681116651 345183826 532376078 531425026 684884654 103938122 543476268 169302639 82125598 951474711 722134120 601334845 988701313 54925548 839468180 777315426 191712873 187751585 823753415 781002244 784633533 487502539 178255532 709876301 134559149 530737235 350106787 768687115 115930004 224323417 860545917 649563006 422023595 245438346 33504383 106908248 349376468 576980650 276210886 284018417 380971712 998345005 885353261 222189376 53270552 577337793 999504802 97499776 617605729 675774568 878502019 402239261 15793458 909273902 112115562 2868958 440011136 314738700 771556072 408457491 539062117 484618340 58020497 961085711 730056686 91524879 920510310 931949505 521021881 49237547 68484273 901993592 47582551 953837534 124182968 953369455 383691678 976204121 50869230 1297406 504495040 781887601 256053018 520288497 543677854 220684931 523157454 983688990 535423631 147229878 244662832 927002099 484364569 155199680 740604161 66937606 99240911 661114470 998887110 620262791 710352016 67371383 374772734 610450918 873725268 498955701 416336724 109933297 327676173 319722306 111230702 832171212 954126258 219800071 204976060 497804111 293001354 728133514 334009452 828424984 727879743 431188636 607943434 212244311 586388315 348547594 279181917 538145577 862178415 130585378 10924719 425046782 197956760 385697453 35497699 71682027 884653153 304350775 34131675 64845678 476589432 145362376 897016889 430715689 217678799 101992949 781036151 510680152 682642814 115045603 191621487 410522556 398750590 799564920 475283218 985138904 628865 754465134 375800833 862807279 885050512 386725551 140370412 935523623 772423003 28384462 859722002 509592508 332735236 893853676 574438185 809324667 891732404 471455073 92556707 109411202 425964373 873592858 472607705 108607186 841154812 516745543 371646093 92421753 168826814 846929311 77560656 169455678 453910796 305877840 884779308 191477659 692603391 25149719 127001282 465026393 53534180 986723283 974618900 238785768 733093310 401573436 48110434 624825713 873028509 993183493 586753266 151509233 719292702 911877322 260116419 412963865 428622864 631762511 505385617 597449677 331208173 435462624 619421706 785118969 741340464 504201013 976596627 433943854 381867083 103597908 751486598 435401263 942837542 578621850 674187030 528447204 980195285 574813815 5789268 705740145 420513659 592542534 857249378 139806360 356936207 117365796 552770224 785559071 601644658 58155840 235525099 932852831 346134816 854946805 570488151 87475279 211664169 547084777 373935484 593531252 503199037 125422081 881448866 298552930 704043930 408152247 827000133 536755567 982966061 832789401 242495711 255996072 277848286 99745088 395802431 634784492 69627235 801089007 272859914 523788245 711761198 360901365 309157427 57896013 68364521 879645577 145371291 280028689 279246705 371823126 726076292 634962093 497245207 607525157 933515023 53805488 15677403 613031507 590561054 851159816 298337259 685573117 107155887 428701896 637834556 355474669 63486388 559978143 9080027 188862653 83766387 720841225 549764017 245440165 778737237 618128537 977602093 776624880 750673578 109365149 964357 476749869 744327242 498209563 936791378 530358616 404531403 804985132 143390122 995092456 508661299 294243733 533181924 468333537 722945628 171016480 823808206 638948367 730994622 832888232 680327372 667277360 406245808 82607740 765233876 37499397 700736277 742835968 814124276 303926206 852201116 815088632 780676074 449044709 165814547 569983803 979403324 570345949 374968935 975309798 417954756 883630233 122069882 951136680 204480122 845015509 974669511 28288327 336480228 558180484 713692910 16807599 77974195 119938718 99415338 843208070 9954466 652667966 438560389 824078741 956594171 143277856 491683724 589786597 592322565 510014622 12286751 571725888 80360570 387255685 399552037 350831678 123402270 521621918 154484709 327882391 219153779 129154219 208687069 555634006 539851054 774896330 424957956 617825248 747351399 376889645 461033317 757305864 882073963 899593705 433900956 691184485 42871560 925584680 133487433 487710476 288115653 145774184 59436364 220992575 533029868 311504752 571824252 508948489 833126670 578825312 836830879 52280448 560495882 898034299 460430805 100346935 672930629 885388760 718172182 272798379 114794756 31721850 30104243 996868718 783831906 464005198 540569555 679219817 242106229 674056987 166930293 530221882 819831170 78883008 751214456 205377390 390387759 175555059 714325878 76030780 754380370 403673109 128311227 167392603 301707407 588742031 267739537 827154387 326647142 838428070 99952766 293958250 870149919 130057008 143343319 506498176 446578557 683912873 185717992 541201138 357969860 205164636 71423019 30317381 284047643 675153826 235694770 526951754 703225236 950020648 602982533 310121957 353693756 731293760 477514559 507917514 172552142 745254095 335071901 351715636 436198516 287541018 645673885 158864786 270114377 789017203 665362961 716692933 472930076 851080952 110410422 683416287 56245588 34349792 713733667 192809582 709503617 949428437 719761335 265245204 899449084 175260220 575367160 105659191 906553979 52881718 613576704 931622472 650652164 801164956 283338107 86850679 88705973 929011991 245715464 358820349 570545546 911078424 928029634 43475621 614675728 38440055 579408259 523437667 72789847 293141925 568763600 634809815 95086713 141041287 900055019 994535796 316301506 475422178 952711338 75371836 380820248 418804394 6994307 31472411 219969349 142848766 118323090 161191674 71860756 216554905 520012022 494922653 980149681 300558007 390914625 447341760 338998062 970322883 970779426 264304260 115981160 392059377 899114074 211067872 533100663 799169092 58120020 849402168 127107622 10831357 924774003 507927869 429635750 931768310 391916631 502121451 74617075 362756072 663313124 998994182 579310977 35841497 346433187 411977009 336399504 737347811 859318768 675397565 707670694 682614545 939701824 823651853 74673921 691332249 34719724 607774584 343017693 92839743 309693103 470125314 956187452 234467106 830569534 238339553 18751767 222486164 740461003 945885193 585242236 403774126 797395726 17069564 439615623 143828912 429046572 776015126 881176723 140881691 303929042 441363768 823496235 96147217 117531972 898170155 787479465 4768047 358461090 130497157 950124142 668154193 453138822 906311593 755137650 136224707 144651145 773889416 358710871 737628500 572290960 796469458 141402625 369686685 813539021 433534599 366031949 95101944 62066076 99725023 235983634 218511469 541088790 59479868 314658685 511137113 810166374 954654502 515905159 21143816 937668010 318545652 541814360 243323184 77373596 296952009 379547890 74541093 923357776 738258760 812169592 495648735 387244569 806088568 717851771 53299941 92139519 83883719 148401884 154205594 183608741 236901869 372717063 577213882 148898088 539892099 88350994 959064462 494546600 456772505 832724629 284730962 775318156 374538988 528054145 852691752 524007348 907602034 927232844 447365123 498377146 739402435 795530209 885621714 398007354 513381979 938921655 490146872 449782050 87323538 644352466 633390790 176741759 869585880 63121024 325639846 409477978 151472017 137220659 756540930 608244521 969945287 41271891 236079029 197000626 569326035 88770780 721007973 329444420 16003623 20889447 827821565 607922409 816419655 713443279 5929762 182317986 504881285 348592986 632100035 444721174 992945451 118007176 621462932 715047682 181128199 947102778 124525659 332600216 84323436 733582940 793361088 54268723 774854830 29440116 103785700 196697216 118210895 824793673 526141636 986730869 845683119 206479552 447169629 662102774 919922830 305615743 844420759 277320466 654208728 329037145 722041640 499670530 447044320 343504571 67234563 628172519 143123700 44276573 960772734 227447136 777859513 606650173 134232210 405230694 636090289 238017909 601927910 606817535 62811581 980585897 446064756 761011052 187065448 745750736 275630177 959504630 51366478 120050935 236825095 558091557 301604431 958866734 910278438 748648750 154887657 977513000 376821268 298011356 21789573 190110353 377974843 799649085 796760526 512207052 57396130 285367166 602741313 659324039 744701052 518069245 492426287 43282159 279080296 679491735 789032895 554710472 491512716 692915724 527277758 728337810 103523633 828882188 539720896 13802070 430047290 547124904 991315070 806868557 845136259 865620994 849495262 75627454 517786430 498772139 587834505 575182559 784139304 43092169 87022950 381356707 561161414 579449236 424638866 840241709 111457322 213671760 247468533 602970037 906587483 627262642 183824199 10111115 308661182 723545094 876429537 738708471 123186349 720260958 398093379 968322607 585881951 247588640 43950060 103668380 746360778 484300917 531367290 383016433 527393085 618390239 764373140 88554498 197839475 41528357 781312559 309296796 255200116 881297443 912266833 14303950 508560084 96091031 876931417 817221265 672152476 753360953 408446087 795338824 326138262 806539466 616177782 912020212 54128105 512644194 868204943 653005235 849461462 252088584 888538019 229370898 870478823 505427510 170441748 68318297 546955866 951754306 230131444 802155981 685568100 994914628 668976283 46644535 943522010 545907699 863865800 468190837 151785003 124828238 116046012 477923264 931367703 732223794 242459827 838012160 97384339 963181121 343533746 946845800 215269704 232071764 28733049 85748526 737499274 199174796 6583174 136971491 3445453 89230970 939127472 689013552 84145597 460620106 735658087 880183959 6527804 452040238 348374795 10829158 576868475 464420807 341268773 508236178 49160952 583728599 198764689 146545290 399426071 542298434 945907441 614695774 774370197 974640489 552960652 364385822 26331637 412060177 501357313 29777089 353807498 293001136 718790641 290469447 753621241 454448727 170653405 612665396 906488964 371544551 476010905 335873790 835965357 817279677 844109967 737642660 253524627 42874655 736704301 652950697 437689440 535128093 120162822 64575989 362284934 673123473 428961810 388616570 937700002 782835474 418393658 291507499 75836609 137184298 581976945 681974201 444149376 605146701 147155948 203154691 976691252 623166852 539028481 665172960 292962880 235654799 402815620 546487506 131045806 139519920 199438202 568735245 527164365 319601024 633311233 889449298 845240848 62273043 278065867 782940849 697624868 696459524 926964700 625977829 686160174 361457996 160468381 130309549 966604697 307624329 333464240 943295948 783307532 872492720 460985259 76270412 108147518 863800878 622757917 91709675 855837150 674712471 660444920 235517866 994313494 293756152 124967163 692070693 208545546 255549381 327527894 906170414 952008904 254492593 384664594 490685429 615950588 545132974 620994978 435071636 852757302 806975569 230883935 488581186 531984640 691869194 564851597 492648509 408186423 40125865 584358184 116539924 714838335 244803103 352057789 561668180 391075606 477024951 106255225 599621152 732574331 433783118 358307917 537099587 688275710 742972510 27785015 156742649 140621835 501296344 591814285 993379137 160788264 822698219 334476674 692772903 367083764 899328270 185421412 775270187 791970486 769779595 891810110 359325173 867099049 243867899 920993352 258174654 573409201 27248576 710312157 158499884 313548045 68620073 695599470 1823754 664108934 575900836 11082755 804730769 929713532 455413391 650626257 90501795 130627961 985102930 783274698 497711725 736947551 821212461 272981911 381434388 443508407 17308372 740759560 310607455 261176270 514269264 421298460 834585471 394034191 131610617 993085354 707582236 52747041 541201175 561922341 569372327 969618362 573005095 226619447 899331893 28418485 877245703 842350040 11562798 714864984 478141089 509274522 304328886 299353549 782256432 685763273 742861955 799564803 279039185 905985761 913257425 793308448 327284220 600359247 187342638 311411188 445960952 894924873 364158229 987162126 309363566 933530555 809296839 882368660 12666353 561145084 763303497 889912055 403495123 774866294 457293390 881636211 136657167 614138627 33506111 918913598 152418251 628884417 570994752 431457435 534870177 336768528 224765882 714670748 937127774 264624872 26081936 383088725 12066096 242756516 222767202 321429661 28803422 32064041 56314673 41469774 445725476 819618169 931381828 849220598 447000814 241191569 583373160 583657980 855330195 469395622 355087929 7748445 98280038 778599032 291722232 485666566 115367560 516488113 200337313 52495333 781112984 78935600 288100410 793179080 321692115 363383963 114608740 350495536 247964355 23439764 391965309 693689830 843057932 175863488 395426779 142575097 417055056 978799938 578749428 124901602 300711911 933837356 985166399 398991948 564952740 276888630 884658513 680320299 645893094 937512178 585331983 279522430 16447777 725948744 72701509 338139892 89332707 39826600 688635427 337297061 63266364 80600736 30986891 758840647 108980575 278930021 753932096 526035631 110246311 332681523 503453584 410958221 119035231 488619982 809950169 683987970 618024963 547125033 216824620 263918057 337153562 654672954 543440486 353601339 380621698 468658346 544257582 322470756 361001297 85409360 659767816 276784012 18526447 543271058 888141011 127507022 822201079 642073106 653542652 932447389 827270980 9512587 195921961 946306210 498132569 5872129 482810531 116157531 405513514 552151502 232591939 742667075 206824456 628548776 948784765 439962505 97207121 493042346 762433260 310724770 578451706 274717427 440025133 596978152 817988485 328166143 724485173 492705915 822755600 230544176 277669655 650026580 240056763 473591615 448849141 590705683 331980096 784176024 559379565 590009961 336327525 791971504 185193387 395668332 273036631 133978152 835630836 222760104 479536849 598064095 533484873 57988554 872781522 973510005 507483058 543286358 154192500 84484582 888508624 976948099 167545110 18694630 479491030 407601872 492286244 780856523 998307554 676782691 565032546 410203470 266792651 753876422 54691325 451986038 149544754 327727956 438480541 985175589 550488059 918017389 435756036 83972931 828522295 161053909 909999287 188521704 556856618 916708138 273006285 445365241 746172589 440551394 464059870 78179970 700669617 808862465 859036492 551493522 485645156 276585389 961696992 604954158 30461811 16388316 56940195 32522916 344116271 347937087 17698504 894604329 265954476 305970891 831093611 94476770 319541151 593609250 135514825 876397768 362833739 408521109 174279360 109006327 701588855 638339229 187186297 402258471 299718046 46222788 953751993 785363201 175324529 767965336 242833710 205786339 784353651 152290257 238309254 980986274 500227343 108524109 728106954 766181818 267011352 411716917 713174939 586552502 5326166 848689763 462950270 220676256 109727224 637229629 329682583 811316078 128085210 369385231 66090900 427803255 268124370 872359244 65682807 443448898 640324579 308516516 649235236 277194582 460806772 740060841 110697207 961034115 848584950 838804160 579732284 115596301 250521076 145423575 554665154 108363593 846629689 17615423 329039849 956356912 507361404 511238783 620189341 487962965 880624013 538796593 915766219 148748382 411155836 833965377 592197280 903996767 142481892 93948867 33707700 455805016 834009708 144404906 269355482 535111009 983209065 701604117 503223661 86246493 847027691 57888814 194610085 546173732 928020589 376166285 355046995 287898344 887405067 975236336 775861308 768029079 366549280 544143878 769293813 777705115 230625606 214007444 534218233 225623849 307956310 567925932 681428864 994482369 712330837 803300697 382109729 695539902 504904814 885333389 781786394 204448856 795738555 828912830 750622587 576275495 205079115 105669582 716690190 92484181 933422269 345067849 713029612 152487900 889211726 334839776 930193014 119837331 548847219 316927599 197977531 856803528 884853530 879406395 703802249 597184367 535223443 85911977 145240620 40128256 823761718 779543365 97093464 472016624 608456194 700232402 48292118 666051660 658418335 617498659 611052193 444356955 962566507 176598156 596844854 704294584 511437931 379554220 676648266 60285149 696481818 874625796 769605028 581335347 606548542 473407276 31036065 141771985 411835605 28793036 34416592 235597322 808336400 131510055 707613945 269308946 684258809 608422414 935360605 342677143 78437424 546412797 787034098 41003930 723010952 236395303 745298513 86965234 615949522 274463130 147250382 312431339 149088925 916855410 746283038 755637467 242779037 777319102 749925803 654614641 806112138 784342394 742728314 466964889 768368801 302858610 736273834 305143961 911281023 671634439 647821103 989718446 70563587 287371552 883238727 646090891 523766855 481053591 733056124 139716376 755516720 880306506 304664067 904605645 649678267 50947104 512759463 744973655 680782557 115201617 252104648 339411046 899544010 994832961 806375935 520429162 297691571 395166120 825573122 61488945 66800558 325910577 903723743 989880497 465798480 786962469 635971387 989565334 120532412 221543862 981798062 876049131 101850367 138978480 633171127 604044985 42441935 145930589 201534992 575740843 113648557 453639639 915151889 13192567 448472599 574044175 386138080 598680521 969210294 64227554 660169466 888527204 242654482 416409560 730924052 708452961 55888380 219411790 550534647 176420791 440955651 384849060 52469922 395322370 523827539 685641048 999367354 418785825 684087989 53418697 994526667 797736545 507058335 762194907 663445463 955530934 188755433 902099895 406727806 10482079 966327448 66897271 899009282 61498281 335823182 482449685 769951241 391711562 701861474 320485887 568132352 142817124 705334946 620602273 538139493 81678836 158759673 390023199 500464660 695364013 443441895 347507679 345616909 950500230 109702585 9062372 758547515 298458018 763678618 17791672 308940096 582522417 84688943 60465729 644020697 273028476 542915413 413971937 664740037 97293238 586974176 232872389 240110361 144825473 705991013 630766206 226504309 864750685 20789404 579485320 412631049 316747650 926992998 758247958 119764231 36695583 619826681 730828097 187669952 383505298 748619769 349126399 966027714 685825063 409592127 462564762 958853538 805023891 876536698 623593575 902317128 316027225 708982315 142427488 460852698 414973327 625710045 687357006 132240364 499015800 119358677 544871412 815763450 46351675 155635721 788044032 935563609 775462401 518872129 123233560 11484050 120008249 324876310 977511763 805833311 734468436 292592876 764686848 392008678 21645926 240796774 294325805 337673150 949779088 289269644 798525847 217268767 914979689 338399204 202025482 266511840 457757881 746896893 82275289 504109555 902532614 722835673 292189515 530511366 94224153 267939426 541995416 214232401 592815735 372023530 20065711 179800522 664616406 637268910 571809199 686262331 878065684 866135003 23935480 680361123 7920998 822461327 750146241 775417038 13376882 952171722 41928878 471134762 551584967 976720518 975244316 306633932 699556190 119950182 837145297 793780342 387889607 379140712 8012742 980705341 751164242 880594804 160505862 268296999 517863714 732315060 954559329 248445749 450966414 978494808 781323223 311403764 653472486 531469464 86820801 666849368 336157537 128749678 137984129 887742503 957986548 965744797 194376434 510059089 85694978 31521731 156355783 326100937 263178794 16884876 306806277 866859387 897479680 319828491 135156385 267859745 52143550 89715713 516305493 355626316 920726873 150145067 667030079 426715710 681614530 606367231 946081429 17772067 587633261 936581910 758030921 545619808 754843058 952407355 55678896 693054387 836445437 64551030 19155323 952140582 81435906 178477952 818999969 978915585 498306442 806672705 246775329 402966343 748904770 615597173 758592658 522147994 765742239 278139088 948863703 299873121 884506319 747461484 170161539 324655931 684043393 928192459 870275738 291402802 733116165 778470985 984457188 422077953 843022015 3612511 374218535 924457920 34606814 45734855 755889856 532913255 852407559 2665184 935879597 453828680 470778708 546988607 975976673 236520946 825127694 777356728 536394066 562150364 524818211 706555604 886806294 61377955 487264415 609598383 352780756 220380579 240585720 189754295 642458532 936124086 45883157 869193418 713098357 80489970 914928272 468988212 613403224 619852182 324169747 549282821 73680862 794948454 96271427 902173886 883985751 773915472 679530613 272896169 188582188 56865175 979451772 927904833 118243129 319232538 390019568 323540236 539613117 630605287 513294531 34588000 419245724 559177687 903781417 132344080 639667657 671226040 453848643 105587232 143594573 778018389 654870052 69791786 425483194 603657830 971965672 161985296 230089654 504012636 434881464 271188193 413394163 266849588 199093025 384153643 586082125 589112592 707693879 125695241 72234230 73504761 12799592 491479953 485198799 769097360 476340384 124866455 292839751 930189026 82970039 436434324 560723766 737840090 358742461 986206959 194014272 183224484 708607 276620277 687237120 435590070 547808469 100631282 702439657 746901493 337301276 288521782 188530437 44995154 266733374 113281018 971016266 132049318 604760971 456215065 901146677 81101354 433597871 193986428 863806732 516567909 482937103 424530497 106924351 841679563 263253808 153454974 24904047 263962414 430075250 564657518 699552483 977883718 517805151 254508492 577301562 855106426 543030273 765831998 752617932 662279998 879113016 723634197 794329315 336390338 32365613 695475992 270008043 318479836 741978771 133814774 835047744 224915873 410861623 794488446 66595435 526631782 947943419 944015833 790594195 378018668 508673350 342663029 208418737 26478500 597171520 785720299 734101278 992718144 404068648 486719209 654998142 135698015 62869757 301843808 472088352 95235370 997319799 594612747 266231557 591814921 580943872 101279300 816730793 991805494 748284098 735842580 370953627 696227516 532374764 14064173 926762536 41048114 356727202 135181272 920042965 806415073 920901570 506660594 799133217 177486570 993379802 306647710 313184584 908765911 608491517 785272936 856517632 458327668 232402034 122749188 50142588 813345905 76544839 719389733 657667751 824828936 307748664 28621377 373572804 840123427 42685550 152851691 733687892 251929103 288032962 506247209 58344175 61450884 12907802 709993743 238937453 858803956 16641452 552122036 620086218 477649321 189911323 476603849 788493340 422313356 451869388 691152279 88175613 528414226 263058363 745843363 205759514 570807026 774464739 431848669 263446805 669666640 584700359 849651048 921595742 872733320 208414608 979939917 786700555 73838762 542450011 25638007 932642717 411607815 430276395 405245286 889257135 472704069 881849134 530266826 895017425 186234873 221419104 983193037 714649098 484477467 581552751 772924963 907800844 208533841 204773631 23764000 878200481 789473989 873415048 799796222 514723661 81829655 632252490 153940567 155668416 27218853 32094926 940827484 438826667 462371320 346072769 180600153 935075388 80438254 710866978 682609164 266673126 932286081 518318552 833838576 269279899 99871302 606763538 29597095 160921495 664053521 53361094 39121975 306043861 926776141 691434548 820767521 8605796 176203390 974708088 16790563 203422242 6803013 957618047 642248908 321690684 156207167 822849060 109282423 89161773 533716037 644407939 355834898 318518469 15242842 42189825 440314720 115114144 648953363 469911814 128551990 165523235 523272907 167673964 471567095 450049048 859108511 144850968 311171195 35311900 119559055 180478109 91250493 978878419 138096155 733499400 153085454 146819674 556348459 114884228 235981446 942580847 759292166 444332695 113615668 774535008 486522520 553930387 742165503 135475882 23842200 870717492 153515468 547115106 38391455 625082562 849680505 750016317 769933529 13368051 637844569 742008935 193846160 729095061 573403705 184458666 315110813 726489158 331278339 871459271 841373386 419776136 666556470 453181903 864108831 780172137 227716910 350631350 334102523 969882412 338623583 210461074 693116255 492139050 757576179 584024061 117221611 459773036 186556730 739671492 473141086 824401298 481680426 666987245 406012710 55084131 851445911 721123522 634089640 35240601 445099145 327979377 455016737 111655614 781161280 319125567 744344102 861394541 522273268 78446624 683793305 860896850 141424049 376909559 205552251 899000227 960933620 175290213 211289614 6701 914961704 684430700 824407998 249158482 351417944 82937059 156758964 55380206 656576933 643364955 90620807 101676077 971344332 545637543 65848042 605021963 864763109 662708495 318932855 239552728 593671470 2726159 100449577 735095518 232152070 158518179 486612096 45602041 186324743 697901710 45608741 101286447 382332409 870016738 202961280 586266704 805470148 212236595 641646910 462047080 855601549 732267716 416239508 679462232 277905258 334603901 137000546 995184718 997312395 455933401 234737445 443500216 458659559 187703373 178595733 690811628 198737903 665207829 736413668 385062645 215625890 782022408 338865443 597958298 504555497 541826722 36741353 162541997 754063316 678388262 624589076 462181217 410655977 893344936 141643448 541077586 80465188 278643994 536262303 77777583 734577394 623516099 373794150 45753304 811219471 552389883 589081284 9957373 70114063 178011303 247536370 285739952 960033711 586401812 736214601 317105559 128228534 772955953 479647555 734808201 451344215 956752983 49505769 714516543 850097918 191149217 255594129 930563105 322309562 644372783 860857039 56886955 267888882 87167541 955156610 931624704 639557423 544237893 794098429 562187837 722249196 41634798 847927788 534799258 628036609 436658740 704421168 608781494 209614692 36585075 196106047 513475258 993338057 245611815 227991801 695952326 289277383 336102281 479031782 611586944 980475063 192405173 520990250 100880296 279572713 476146860 32505000 919130135 872901104 826603428 333834323 447666651 720754577 34278462 982465908 201307537 470937201 539403428 810089031 680551892 575988502 858711429 46543502 569326558 104323243 274535302 117795235 246116978 610637582 596827016 857703921 443628996 789232188 378694171 544509292 68804900 707357382 577014291 840451386 580258485 256134070 174285708 27925136 976888646 208564169 862907395 30712534 679501369 254827174 840801564 212569613 830815675 552029344 259113114 252658584 508868939 386164767 370453818 754985916 996802348 967280834 612689836 292947695 756513021 843900358 837456986 677834273 551257739 266987628 518285658 984032576 523121697 545087718 864474063 352526694 753651886 579897809 383239228 285669607 834724983 76557143 350755571 665540657 628586487 609868684 918199241 137455425 996033450 141169410 744957692 845352149 108450243 210163879 138299843 717479616 54064237 828273181 395313888 457838327 95260808 766115897 441870902 470898857 311203614 158861316 823425550 917371852 738759125 59181129 55557810 573484107 135738272 406313380 91541115 616841110 16182063 862256707 606812886 864731864 3426117 204286929 562600364 111876359 414450807 553416558 681872326 468515043 234206090 77186213 926353370 329466898 695818462 220740623 800365754 7022075 379601939 476307655 776910278 118361063 388005136 832468087 544361521 376259759 238781466 488418987 993100868 107479880 350675694 452430105 824728095 206618162 656717033 239844810 171010872 71167839 793261368 852883198 392199234 27467457 782585762 171068955 209450706 478404223 244325929 862332811 337942650 623927867 191156818 114852927 594805281 579161953 799837366 991683153 955421711 38618831 480102140 801038930 998615063 683294185 105985386 823343157 889912346 762702418 63187967 60923217 686386608 708965686 913806414 931102193 588949494 548908528 102171147 650916552 27312750 199013428 513249362 217771751 822941294 704406179 185141030 270262927 136084483 984978395 114462431 91506193 876113577 594564570 892545122 727244991 130375106 998530507 403104500 20287451 613749276 318808818 81210668 152652236 27774503 847533433 83754428 469240348 248958312 38441927 120156899 128787414 89971706 485922613 346559164 912912999 42845143 384216545 35692277 178929626 221711291 150154708 122952170 97824868 597235629 15497292 677586210 727610735 866544150 80690709 747898185 332809778 399499526 681625204 337978365 279790380 381674989 274249144 601547080 630633300 165207422 574220330 759420713 255179127 60142942 958496229 20608478 955504437 342712773 56300754 134434062 564424064 58971813 109902583 514765283 656207442 125399874 44867844 383818176 844460376 125558553 984232712 29786505 377574430 518374268 367764869 657364810 900049256 642014012 111428241 383198907 807221434 685648570 995135972 62400560 598307864 953632200 83009037 553812300 148861324 991826143 540762713 565801739 50797955 650665295 80567021 707005396 628581521 125434865 943339923 325558248 103509769 927572635 207861104 481084198 298463254 575625972 990965359 51028861 70156335 102393599 434227767 729894120 788042169 281880090 644811032 238866384 88028641 580336420 792678683 236889965 572162562 185957747 802691703 475476869 689139393 735775076 34998616 170237265 713726292 978338539 495795512 669752412 758427525 703656615 3352961 56890778 131798938 994318320 107919638 54471625 96711918 394663756