5000
485816650 508854658 527186286 767892851 71770912 566690853 909815776 867355143 503279977 453362562 566810889 591444436 421363994 982893022 549449874 29403838 36923015 70937348 794195162 927826445 453154749 469146704 128769477 959223765 657775547 254682812 192741653 150643438 933599874 283458628 287817731 453383133 613058975 530578329 677897318 100617503 805888647 607585902 202529824 558723384 789272178 749901485 557129406 457801511 902433772 966952897 135283023 281355059 865438244 131004678 909206452 45023114 313064352 780886726 44186203 458794005 451083901 546332575 829476702 790530882 710013423 582954013 387202571 738876472 226888840 636587587 325643560 311703166 549426681 902000603 690650993 882440718 976879901 245425969 420582897 747988747 544068319 739424601 898087909 862716948 583950978 893734229 121398186 976105583 310013678 895340118 431925947 120594812 572314817 502416424 742262359 718674930 112064657 477212335 49462324 53245453 832274189 430549441 379643645 5411710 206637731 487429505 785481889 988259809 704838261 391548967 546433341 413806934 729391970 230630671 558415354 970548081 9627799 118751500 431833771 389817837 755481030 100158647 797257192 948276161 559320396 464868266 861546436 22651535 515702233 102037453 719547556 788052915 457367951 571242109 688055275 586854631 893822016 761833714 732179245 811771349 27230256 928818571 293552408 245457035 834596905 281192779 215166993 973498144 290316351 568019361 691650366 391259549 394857785 353457797 881996138 752261114 700201261 662655226 78834733 159722708 63891015 921792348 175916443 779245550 938088575 681332412 871143081 969410514 961424573 598381681 729408266 398356494 395075011 275767709 716568678 854739815 860458233 161392056 686452197 443108556 350183205 48021105 506706548 950913068 243527706 699329133 654799471 984303827 121171275 522278682 899315507 763089434 425209434 382229118 700639524 324902754 858986747 323587495 807496224 801594884 200633308 267316065 138897553 410910559 614582664 465282019 401651063 408653371 553199141 832068377 739631592 394556738 745406323 903967783 373895368 881398614 343018370 86951706 181148956 120606241 508009958 523267424 933702091 628473211 287684886 574818642 736321603 570845917 398889389 957340701 518391511 3217761 78155164 804109514 861652448 862355185 64597512 341780235 416667720 349266070 785241532 728959454 803798503 538771304 704635652 422394466 847041511 405735755 421062490 248507464 294549081 554115064 820844993 306048740 228680290 826950228 811164506 648740240 929542178 77768762 382202011 324964876 465696796 880518070 975943854 9455628 653911221 622616745 104106068 952339367 18259128 707514376 496498062 546053194 327437003 291227670 447111205 800731076 976122568 872642940 393187772 205454451 623788079 280411870 792497202 76959897 390956408 245333410 42924671 619351659 749265071 572860338 129426405 196229412 926176422 263443695 609809724 714177118 166780821 247764438 181053434 735132229 568325135 786621902 545533787 254935735 907718852 662076114 94920190 288354489 294538909 323791622 910974331 615074766 350151368 151974587 979222225 488863396 77661308 686525262 98344564 972161849 363651902 51159512 82400605 6391108 181461284 62013112 978209983 814954296 841083133 807858091 914863395 774108947 885654538 722348603 483617865 180581914 954727533 504563503 945036176 987502042 707408842 509774234 679993553 421136746 848242502 313740301 175607965 324590305 209767427 744937438 683064690 321353638 185482891 617995732 902978351 638752242 476113862 924419694 755586683 421814684 22899360 506316002 990235150 697727521 964984607 667201073 123172211 487366028 957416132 786968194 79971064 274212211 125996026 915668376 725844844 764139205 148884911 180408274 30106801 373124599 908418023 982565103 34755263 574205451 934519423 302092633 559970083 372640150 217413994 776966349 329972028 817466150 87197734 275151791 202036509 289193314 35932960 266608729 602123390 699029453 807759282 71988398 373950238 161642162 931066676 739234320 388896568 682293 925412778 945679680 601407627 194586708 890388917 994567580 671330498 886886212 481226201 175367782 578095836 157713937 701020666 102977220 369176269 589873657 281164891 342395079 212866824 274629186 255276334 62777240 780022494 720148194 701071209 874830230 432541691 549284687 525574403 268767348 428025848 368120741 45586957 234654259 213379106 630164588 857856573 801915057 207710385 548781108 639062137 646130859 254427186 892209674 565332954 730023380 35684915 210777493 485822065 465698427 346112217 68598512 958684924 456582577 601089046 701400691 339544650 417471288 216809271 485181952 662115322 781434397 403030647 602732678 960447941 616328513 365562007 678557781 835363815 333014313 385142414 674476357 405888477 954608934 220515897 339256095 482501273 450757868 319766589 510068685 787677669 304162040 591044763 530473984 216868740 788180972 107544787 336548886 744687640 854950107 249413201 436168502 240693932 717990519 93832412 649402553 553658404 267889453 683752082 319532033 954312863 330223128 551735791 444616503 951646785 168007721 676409624 938457764 103650168 601333697 451846362 657820569 822642191 395348619 638439161 50198107 790844896 513495250 673728388 529632469 344831110 435521360 87867997 213031259 724505283 672056995 995089948 674646375 160071288 223847030 752290511 426053580 524252489 24267380 8653546 392325717 2096802 68596663 787018203 240227341 441425311 233590474 414434618 714425641 620965646 672939535 345764553 323678951 515728746 6103301 829154306 292438095 337864416 698555050 581318567 735505892 458299025 96713961 325897151 480885152 685503831 450849184 889968443 105861501 107622357 750100757 853655231 607510010 626825197 247952696 361664236 31641022 822642345 386737102 992059195 484038656 589684619 514024606 912177998 486042556 636483816 895658548 52441362 782300206 151854628 105354241 767633636 730462632 671522397 479256002 807018483 653393357 620249701 574590670 601176854 689595925 947415355 765621965 643322326 158706549 205937080 584681490 471620292 316395102 294408235 577405513 582814171 919850603 575778404 387561880 404282003 484072601 274379521 583995419 907210734 601513078 235858170 396811831 407131451 923302975 819862077 809598727 394637197 292872268 915724387 927046894 253370096 696428536 574251294 651543207 241384028 891673913 203319911 500848249 152865289 531654828 517102305 987357675 464019395 389498351 405871819 20985928 29678118 784683818 236447735 39265712 581216301 39025151 285285797 835720725 645319801 981262467 574851097 477827626 252539193 715785875 289167972 780329101 131077485 401366762 342866504 157594531 389447691 821224834 57997837 792597164 608776436 896199363 661089629 255113430 418653212 605679690 360700508 299912181 324639011 922637678 963016066 140955128 456549767 226345376 710259612 660908116 480057152 749240453 858384182 189206194 559238951 696477051 959895809 63780104 172609486 168383675 142829378 968069044 285838111 953422832 720174187 470835906 88483552 408232973 441402345 729932214 508604085 444180383 845570165 191205482 198912888 524007583 832082046 173490280 617208190 295682262 894682949 132587311 286965347 164462012 365409510 244595708 170017040 872415020 304828309 39444067 327111105 893732338 319978761 60772152 355227716 877882532 694312788 721200247 77946070 3734714 851987256 655950537 946251575 882304261 614809542 816654782 183565957 490382223 406471913 496668616 572989161 282520397 15174320 737158390 67262682 161896889 836725653 304172321 775632161 510177572 668619460 320664255 984529007 14294601 751853857 685667455 75172658 366605748 322118650 318438341 844067065 286392092 677113839 39636803 997327242 451763361 273737303 309326426 549076224 144694719 402268467 556522218 507344595 597538787 16798164 883787511 960009000 252049825 203170201 276952038 250387182 846046397 724294680 198981804 752558852 569318749 590083657 326379101 896403029 499200253 812981697 712419349 996762754 351109932 220400200 260299868 432458575 372834978 10598927 432557350 117416360 126514610 909031661 933402126 848891936 571240955 429425218 203903885 710365068 114885582 943621939 339611310 29396772 49727512 545695159 440682530 98992911 397985181 706567839 297857556 983384373 241662814 542215688 173343601 598389153 448990776 470214878 393211553 906337186 772708898 307272671 896582241 493499660 7303387 982256179 107190479 374080798 604283593 255250987 30331764 312192577 8521121 144487542 107249751 559312088 544169933 727575710 598196498 789300065 705113327 593440723 415712190 996993778 458341211 690341315 845372187 423963970 978297211 184324653 900418580 884265128 549245607 539833700 532924156 766600392 830270045 551102178 417028493 601590315 709302669 513706686 668883149 90676891 500155816 780834244 577644493 322427528 621253640 627604973 317759787 381937679 794051388 252129063 87511439 596515004 205770205 976469458 115443830 750568175 30198310 989526293 717956695 272624480 941171526 475727115 140481250 201338690 892689016 783056562 920699609 295642457 991548756 445667738 354646999 996155726 990433060 83168643 714123699 298364216 549279547 761419941 848875451 45329724 975066756 566896790 69233750 885390812 168153826 31222463 828549128 381704057 52793011 34234255 670781836 598388686 966424074 142458281 4888445 712967815 131097176 594408235 660747573 721010303 809790327 701175436 689532819 935090796 784452008 403772271 130444050 50257680 47773685 931107084 862198107 121353680 344896461 582919464 763915527 245078467 419662070 938908619 999200246 178729784 326241683 726989758 300871988 427793191 157940573 653194998 766765794 314679426 309232436 765486234 371676608 231775161 905639507 193966207 147959636 373697477 435628656 469871091 922075167 683382608 442070016 145172916 228564833 444532951 240873997 672525471 898829603 312514678 595422616 867410679 312080656 146594263 405031067 907135826 597858786 880663056 231461954 301645302 920331572 201371409 369518226 994196797 362267371 110556742 20191951 110677176 725003886 664093109 191107586 483349311 651519499 384994621 157612416 980317458 473541451 192118706 884927947 38584616 631957830 418250915 905007972 63442528 835637728 432318703 194633087 73950825 960982749 308294529 252117898 307911771 157135917 10068164 708059457 300667086 231722368 609598825 457003046 103530468 354471086 837426906 132057722 409702431 246403460 916441935 228737778 998355847 162919476 168988466 773875068 216974315 986917305 223996073 622420929 542387771 854128467 686919990 693815545 625517277 562022212 180652581 474070679 689061971 984235500 85425093 887953244 166999227 609369796 18083609 631444733 114643852 715307036 928985466 379689980 223030313 88353632 559574982 422919792 856700464 80175744 557907345 589146433 13442346 355045528 123337042 468111760 715996109 983931213 161603966 619015223 487990036 623887911 335941156 561096256 206773677 775376569 120388250 347791719 46184478 69830967 864613933 492991333 224541989 890911083 284176887 536634598 795648854 360771707 71550489 587465838 140235073 588947724 432514716 872400622 926450985 604708228 64768188 870186626 79036294 518498670 386795914 153219085 605261043 63272004 474135012 20037493 921340704 942579602 522050820 773773909 834935068 750912952 669662249 6339872 435495485 634817598 593997400 785691157 771372670 645971443 940714480 219827081 683041589 621087240 362443700 25738596 638783628 769423878 194013623 29611602 441799698 493561646 593244352 713745784 346983694 370565374 535386464 32566507 117111409 315257543 612048730 28553786 251844024 42981097 973481663 354171538 914514652 5919333 418625939 990209868 138976319 106202696 648540249 589814609 638804945 310361666 413035660 397519359 95945672 576852949 634641837 817405808 337704421 713538208 932566613 220245093 899438213 7966403 951677431 197840367 507626429 745376359 310832618 975422496 315075051 757178553 242273056 729997378 597551144 444077196 630037727 397076136 233717943 975094418 985425013 549124322 771612671 155170329 836750272 686340119 642111149 997844905 22108661 668238512 992925872 398984301 326418641 264440037 657796981 56145880 300616255 567996156 802805319 699704484 796790025 421926139 322935436 471364548 909963671 860279043 18373374 32742555 829034564 411406690 412289273 785178463 468041797 665232209 172142406 648841777 74240745 977840339 805524144 200889018 731386611 546694435 813281627 3992244 935417725 541203008 797894837 342857641 32426101 999474158 991163509 853605600 119454420 101040710 549983188 652502570 441749085 339157528 935027145 297801151 601467553 353863463 379104174 378436851 80427200 655646122 94029924 304277963 983277305 192449138 892414036 175987224 560813742 412120424 203239629 15021755 942335427 291220110 119307408 670153026 699348064 920930142 863638714 768856193 904313054 923730018 559400970 48747428 462085997 172007604 65357326 423300052 561985038 416279968 593895509 971735280 994500572 801073651 438127945 932445321 706737131 429571010 374385169 611695910 598908179 94850382 42308990 542074111 146529357 695998318 965960312 832213311 837683433 20009974 234326920 536340178 83535715 704816832 833587722 221343152 410693908 736616195 38068331 165683171 375438627 404350450 667464090 804108025 212659888 452524193 735276468 457488875 466928568 861695136 559459465 956377535 78333132 668960767 167132803 765773419 652766223 779570657 630337559 137343521 95349860 33057817 649385586 131828414 16936887 273137172 909970270 570480054 25876465 348715874 723868474 76399654 354349606 881228957 386397350 728631141 19882658 964671030 380573180 369358484 439481297 115266073 126680461 398075269 669124539 31013251 643700156 510607537 321299008 13013520 157742983 495075247 370381837 775768382 267022062 855969692 788426739 257818244 512298072 704163845 976056435 58856553 569939875 616654987 649661981 575197295 191486886 796639726 458803526 454262311 947855087 53290836 368536378 496837172 48467755 616058322 322402853 526466787 891971947 979978457 52951980 456183831 944760945 840830586 743819148 840075609 244341130 246031574 901238717 975970167 673689368 94323512 761545020 125226730 876994459 850890269 734357437 229307051 649165283 356141790 307149640 892992500 69303246 585207539 517294554 547898607 259549756 455701982 867378801 11678682 543676853 489150378 299568411 949072186 459568606 201916059 17934147 662868618 960018295 943150690 977862131 147055122 547409867 3302481 478313361 219697136 18471269 532164478 16841138 610194163 493701407 760865671 550618710 252446653 276840072 919443871 186106423 295047856 410211902 683816983 575347504 341749506 354451513 97152119 857634471 967107475 886466285 608101982 147887288 392293052 453368812 893215283 765126003 242100996 360885531 876076864 168410321 843491016 129138926 330290350 540949773 972707276 866042150 500245233 410030361 728032947 491054521 973854677 264988724 422460563 248873258 766288221 699583446 904696849 305857734 820746626 317476441 575742991 698065854 214622987 530603464 462033233 146606860 609210877 417043000 9160058 370305652 336114247 303887261 197466922 783662524 436208258 395332265 922314383 653396165 652321413 91640808 263648107 385805032 653901128 765975267 700459030 572354759 814266535 289948595 450499241 848449519 336420632 712695691 478446712 188213461 650404917 174924088 543731649 198158529 192745028 682750574 381433243 845671203 377002862 571174778 168050723 634422380 944044402 916518317 986784874 338771783 839041440 623205458 29204414 104561497 741308149 420513212 121661157 459192262 626056626 773811774 114770623 246711747 416276820 746992884 777977400 407315119 981949044 3841124 58297832 942117990 92740649 967839083 681546530 887692810 476552295 850834748 44595346 981429888 143875 96074285 77700186 835005340 585824464 56106934 429403593 92974448 743275977 295829185 613300794 647257756 65448216 579008995 426922840 595936526 726465401 110710234 865270379 320685009 511479368 486101663 298363692 362276473 345619629 941859072 875611555 114626438 139821963 776233190 211507561 187274355 768558462 557964318 228618264 694581242 413597124 549184972 976605363 757960144 338922882 913964416 917362389 986083147 757320650 589547009 343092235 269377681 337657292 389094133 548507997 686957270 430039598 355896489 264446809 89428264 924567102 186882327 381147359 628234358 707084966 251146688 171881873 246623912 776947092 515970590 479757238 329218699 354729698 354654872 314786143 150900938 696288383 634239565 16258655 576067847 588111800 582522708 106580983 929956930 105827807 607651087 891436150 533725116 327893686 116631035 739265765 979851317 934235128 461757992 998277194 473853260 71278079 500262237 777890907 255589155 343923924 574311935 514383855 802776386 203411201 651420224 450767288 659344937 149049483 209900707 564162578 214173731 817641132 690317265 325670352 633475772 999727820 911643278 496389453 941057916 411629941 888467762 68159779 567780510 311008551 709489191 566624495 123924474 86367385 245875474 951801335 230476409 613174271 267526225 528088233 76792200 663520479 206624773 335156880 137842274 207091772 205947011 457656897 142993081 13005466 136093349 831645533 486814565 618205498 575871741 333299661 559924624 871132161 777168176 415495026 276979285 413499192 394592135 388908001 476778396 965767308 492671708 153151737 554861701 504915198 344151781 264697788 292314223 536457609 145369348 599314164 256330274 383639498 882121300 346345740 420796586 161989047 819521637 386771199 475273155 931567990 477100698 693356725 75736972 804173286 712561014 702811009 187522466 485794805 551145813 820503747 488671415 157272019 755508265 922145061 788308619 360066129 935618407 243120141 828855343 745619854 118624662 774199253 926294503 291999931 247957077 382538113 659376597 503980318 878859798 910215664 851480556 286070870 381246384 5032170 962725712 541053184 179389083 958167058 805313944 334572796 370445675 768830650 861781838 69962004 834990875 522802352 683546952 463245264 774513308 611445165 262831162 913646053 267488246 124855651 658997883 488831264 846605059 650047754 965389453 852011571 214187361 713036395 619674244 867376443 627385752 496323383 39508364 758767801 720025019 851128616 672725371 721334115 947658580 744728416 261084858 827888573 297352340 464689670 891646300 212539774 357699745 135668787 224389182 994029850 20011301 426749800 424578130 858637297 493535469 579095583 555182109 875727237 975618697 318744051 337816904 94641409 304260033 117129666 535474325 224360621 850068302 753354199 859528368 927419797 255532662 829500093 609659137 881722603 356569910 647509670 535027624 776715903 298718441 469854662 8742510 11171580 878574999 738419460 972455753 726192541 601460818 381408261 434222127 354188857 478756939 102429763 234351732 227149891 853901332 136995393 506863370 7028581 15522115 830337182 20252864 326202218 974474794 14574965 631802021 421166198 244095262 955000051 868429160 476375716 53083466 164125842 380431599 545545196 530135452 690821641 453332926 682978302 194897350 340184949 385012234 106058129 800589437 13283649 96216001 872307145 301717750 850057151 66397340 680272053 166678418 14994877 737025469 567480204 928526116 868233331 520248495 972231011 690333394 543806232 531868433 113630687 844842881 300689336 41442473 353923935 272107047 182671126 477845649 591312730 176033420 491864295 701827169 527972740 924382656 783563843 210046453 402161762 95841661 98681094 664412489 169604534 447340389 275822097 963876120 104402897 387456118 371273364 316825716 346884715 592644719 358917909 469872786 899306800 397670011 252792747 835394645 186687464 196661163 269760834 345355204 464347154 579910991 154712043 559567417 517122807 511376906 594667546 876476249 757609739 95045194 761383784 498173612 836248148 601642610 586880078 424815671 372216257 308871410 972209703 838518156 362096226 382954484 602848555 697035571 124077794 849563236 858315888 821101968 699996429 119057380 532206794 273407932 364450042 486632762 291855223 216896619 128084917 77128887 845632108 351406737 59602537 221837151 271261321 271019681 329148622 611811888 343679303 737658889 813805965 232359212 97342501 16052998 935053936 148648508 468844791 563588770 709877214 75940136 493598582 629310742 457824060 151055836 862121262 697933078 204660546 582899455 358168760 491658371 920179978 552506255 421503547 916523496 716985781 922573254 466095725 882049434 186949432 429414715 336248679 270582158 105569047 319520705 235252412 811410108 523502590 830429634 604792277 482254386 431650804 612370378 441397244 663230510 750291052 430301473 501986687 750958523 518633673 206867996 989891361 222788235 836386213 318111131 14545532 940605708 219963553 237752784 688740039 224024659 749025293 528026616 853003710 231534313 832334855 529632883 116985548 309311843 579048444 385697030 101152984 958231514 245505203 124047079 715467121 463671276 470332662 155220561 996265339 944477255 637023982 371981085 993660965 501681621 415987712 78143571 215997444 241132377 980056077 300786306 178551992 780721158 818813782 505162806 844741760 216878068 877671836 414232147 201255895 174249464 507199911 545820061 54442105 149969892 388719149 801660912 73646260 706645106 472189660 37571818 757514971 315514649 193331370 968684647 166979300 429489692 819807714 781143092 111045648 56272823 915745427 761788555 250366442 666827659 965574008 815991098 788987137 421351112 787168417 749282382 123938057 533321212 189315576 216626790 146046722 690108396 375641924 977531790 238851202 406374641 401594656 278042228 43575652 479183589 541225472 293029686 921249685 430024480 304613576 847496289 520051582 635551031 301083863 389435328 224774928 772645314 494770984 160888184 545137591 197297353 729100356 368823483 839443526 682467160 441804969 935379710 470480635 906957449 247231781 748808967 644150925 717735226 274353401 224318146 870093139 979721484 594175377 510684036 676134456 81286450 773875644 537482880 217002958 134710462 271979756 625744405 334498652 19124766 434287819 513153096 928321028 446064473 998801231 372820873 192865349 892091462 122576352 350771030 769271976 462486593 83071758 23267050 225639705 390191193 505308755 244155518 962266730 910464416 22972538 310676761 633684931 166602696 928629526 609922721 719863068 179659399 107458722 3440222 741876003 50144179 908523702 506929479 781473670 957232688 336977868 116067092 340267797 368451501 994747315 368790467 443863793 111730740 334410065 203281444 55612952 146310677 133494692 808247306 157650250 628008385 718765754 55142196 397784951 13127830 941601819 981427842 838551518 577662906 191225548 28041856 991747764 24560750 674467993 885889353 569768227 667436040 70421867 594273033 137267445 557829868 734920712 65354384 127073903 32511602 316222739 227045213 9374735 836031115 881317422 997507724 263930292 755898437 895196004 915320618 684568103 493892562 943540682 5536086 909913811 188908505 564248318 220684712 831931033 462483382 132186275 861256664 270328327 146520529 55819687 5127009 717544060 962019616 986936302 54096028 458564374 651553172 147810023 723627986 981684890 342938783 260384101 95457359 191027297 524190514 448930896 863556134 126431189 800432574 530142425 280179117 127342175 353157244 530322953 349445908 414339035 913593307 352488724 897552263 745966893 688592228 721717475 971345584 731582350 84205487 403407496 217245250 948354482 649069772 15156401 994125322 559732025 769666993 183388074 607774487 151001603 18804594 953392627 395831576 41037616 425190049 263077959 348757278 417311085 606690835 76844613 357207709 132094989 377537431 775746761 94791680 943434080 314108616 272147897 963924576 308547562 898262282 828744354 203731589 671337421 285471658 558008742 810962026 957570326 20497451 657958505 53308923 90144113 826301137 501551519 905224901 127533904 390952785 274502075 802876736 555786232 805098364 688503015 31146957 886315471 410410094 501118768 180618496 755829821 331973246 556036369 196413981 908571523 131238015 648998649 691045539 27367078 864285689 337278520 828896994 364314246 322264616 288088306 719074422 466262140 891514249 860157165 780603579 450455880 913132168 741343201 97926747 594612407 917469487 180889255 461077701 10396555 513045572 97402988 195442535 55640417 188810337 356864488 190748881 15834572 954350539 155805337 425821930 297924411 33273692 831657122 353786823 591954805 535467350 631862952 700239974 610500860 800143068 696340733 867139755 35342441 33217402 140934784 546709666 986414274 545347620 717846016 106204521 279882713 521364093 13436187 868278444 417154364 257183558 730101581 515577300 856468330 688141470 780457778 280528045 608624111 110630892 772876657 516158933 129226406 82370644 498245703 251950762 259755976 686227935 168752110 576020974 928730107 539680937 778307887 903164103 520309144 363709214 178030477 62246755 576625229 397175188 102305250 67569396 111483884 701799000 743041493 942433023 559498185 924495538 763539950 584634738 414321724 400346749 1152447 202653546 435960631 870333555 250227598 922453796 761085415 625995889 3937786 647782611 489292153 814450751 772182569 132078051 135368792 6702817 820305046 581663848 623464771 877267992 9941532 302365343 123066464 681360897 128285506 369612398 149962189 418930222 332422266 735521524 736713211 720863716 144336899 972796091 683287203 593660183 94523607 40364079 400477358 103639208 115981101 714788705 613483124 837004363 984086138 99807940 705323952 748334915 518566033 816787366 681740351 806307209 50640491 251650723 172671467 973922557 98902708 998900503 518630850 358732773 558488557 474328928 156783478 964261134 811389732 378880288 649626371 892025159 397230116 200017965 220737532 474064671 810928936 839353756 610007584 107819456 607804123 961250989 805394318 803992108 418356003 107183345 632085064 853070564 538473902 715899526 974833042 3581189 969256451 994862459 745709906 769877650 830650943 503671971 649156073 381854846 86754623 777347648 129788797 343190595 62524996 412025067 895023166 435636388 126065644 705962413 74256597 51128382 872336000 526354673 869284755 242099873 764106440 789455280 546113110 576343650 623880548 812420738 770910073 58334821 177882775 825621124 318926723 893544583 574329489 140695260 639403000 402387986 813286738 415495954 589451485 546172578 635611553 137760297 974211226 973239592 207105762 992256591 578162023 805774143 326833225 719020459 62340565 284758779 572454798 348403069 129643840 911977781 831616816 758059643 51835128 219049665 542041949 376287552 445495267 21151893 803092875 972019747 175147213 280540460 772762418 300165625 533584307 116499857 389664376 365295323 326663118 475334024 274430978 888380169 834699329 204015181 185122489 264416933 43821651 349436470 534223893 782782647 158364428 179351768 919092401 555110740 737981380 402304352 777401454 296143748 502492881 157280038 407422779 635215914 210942004 135420930 999333548 665726477 105135871 485996331 385540129 5049503 48816122 200480033 380806020 116093879 883173777 376675353 534177884 189857056 729836657 17309576 864628950 815914035 78566452 453787702 663986589 955005765 343052666 429465840 247687529 212037463 595049297 469485514 368191888 309059771 87976839 678720966 971085901 717263896 504204139 751903997 770826955 356408741 175062307 302392766 46902123 839005888 322043274 411097641 273746484 824513985 875299415 806469673 893115686 30502200 588979880 945444967 752587996 383375234 838675027 406375355 282936029 200119797 857057090 338536861 664438083 549385583 554687605 263936106 683155440 150675498 547397917 280215348 425594258 63091865 448727492 982049094 731933254 903130297 391536300 904166862 139334096 64872885 735612418 951508261 101280600 278258257 504472606 804019486 62824683 588868057 409979716 271297023 594662580 298464920 650764291 10452568 332185060 662825388 26958175 694891590 716360586 297469867 392961431 75636748 285968783 152041248 432429820 531069984 371732392 235513462 162414378 170946364 852345810 535211479 832776949 291623922 390471636 347052794 309715426 600952690 957383353 456375196 425412893 626616523 974100005 697229777 178772024 993681039 804746423 695980556 683061477 485284416 436450149 306840407 643036975 916183423 908836707 805386754 268320948 415765489 999748485 869168438 118634627 335249575 906314122 224039353 353815513 914841327 837831902 219135730 337220452 820278705 219939856 856748499 544245656 968472482 733511191 188066213 48348664 532980987 647635680 356581374 853743615 290757152 66052558 93916542 595843773 21028869 536050944 533045990 886361880 920078238 584590803 3237701 308777106 42690015 35703180 353713615 595336308 279550363 192721622 370163367 213968671 589829546 757426624 457555655 33321816 156948631 476146663 309659919 120022917 465372471 6460617 415768890 640574940 714606227 796315153 358450220 56957567 478188194 638605366 556189001 300111142 229952994 539819884 892741302 601880882 12650520 850950963 216805534 559203531 455512751 513183305 786386915 328427807 231111401 317073097 333562108 589960249 679453098 962121855 389871498 602066357 330805000 731143431 639844039 102045241 48243313 353116307 867844654 950376467 368054895 223423930 732988712 58931901 459036287 445586706 853347281 391838736 336745818 579300270 812691975 843716305 632002784 464484704 641519634 338337588 920635203 577772637 401775372 619327403 883627085 511270394 353832632 853228024 586424162 212071413 172789123 583079281 502691857 826295179 483381375 674931544 392443994 263649054 195540195 409789450 711395118 477297677 362453430 254654832 943942444 479904753 174610690 770660965 573437390 248045774 608021968 186889721 600621719 939673591 396123898 284123421 848628521 469957294 773555573 18612947 404029702 777339750 938717132 861019440 87491058 205009646 346619022 355338891 316623540 446606248 395689145 496972644 774388450 68484518 318827256 733144505 998665932 281973120 804946413 225342828 334814596 583053737 300826985 699517143 715511009 540902104 76559663 710207165 144497779 912058968 165162709 32801508 871944775 859371649 68364423 722862266 574873110 857904702 103597935 259991739 959398722 625123974 510468120 311053334 523868523 130250046 580009827 317249580 35498983 623287134 474522347 820020844 458069179 558217936 627254241 300930494 500369144 733007829 690306510 145134714 397057787 50217244 887185252 318989981 408495757 230689932 245660492 591119457 866255435 303781021 351878217 419857991 123401058 418365324 548758393 243659173 349772858 939234446 217827472 535535204 775224243 177420041 590076205 975246231 510583270 309805524 994967401 79274692 957372754 769760116 468817981 985135221 952704887 153001947 735131805 972869551 265100947 526635486 339364379 856606802 553989466 233543699 485090829 846936959 358021707 461533795 377022698 655333406 621832302 785937304 47628636 127191799 514775518 23017133 806424764 406463247 444930577 24209452 383743237 340936086 23121863 511328576 219035053 703588021 154920009 766046325 687221462 637141502 306786309 333860160 992977910 300703552 598345826 279312505 149423372 911915496 445535610 777365757 237577742 612076139 611940774 168285105 459934126 158582342 492447764 922106929 194593914 210735632 130603607 961973632 839878211 449543953 461041381 603041804 924596493 447119471 187337712 499385582 680957597 720145254 863661619 241523350 749058137 452851721 250009320 400188049 790940247 652810328 974737853 918192002 276918577 690174183 621745499 649521021 287695151 337706689 46099385 823128571 620263316 771195726 931218437 837757067 727383011 903998469 842255096 161311106 912422829 87702246 735445586 746505699 258870305 35290938 449971107 480778069 163946996 733092912 861703975 746597514 874123222 35258363 184932256 886583424 130225630 379970225 956232486 394845054 560270725 885642090 623670553 873163290 225153016 553016467 368219506 140864107 639931757 69670742 280342024 522129759 902830438 158572409 782973815 651600237 153876995 481966406 870762491 840440501 632949833 62179313 370080325 721161497 2400213 108851406 106554862 190563643 171620707 741979837 865491574 174057455 435456678 750243158 255604394 142382813 157675084 411205762 78799402 822949639 925221343 636965424 790597892 478770916 795922828 457414961 816896927 351712840 131832119 35202008 670491714 150241578 69301050 107570207 364155147 330890121 634984864 993340291 163584057 336605589 865402580 483932301 26232525 280675605 28944059 794727213 527851341 53822655 241554208 875233489 663005333 686752769 797045043 16546576 998507012 178746251 592315656 921622034 152394681 843370317 667412615 548144007 540677525 611890735 333818182 620135239 583364249 285170425 213838084 754635015 419883364 52317881 184858248 489015539 317616566 642286113 463704355 11003937 627400744 435931537 104156262 329730161 312261114 973940317 647467351 40395544 592859240 463716387 807426468 197787603 840909821 382935734 771833657 273189906 848464074 817410633 211322000 712835209 171665069 46177183 896624200 540818400 593108166 92247614 122731008 585528358 380997159 818601010 84477818 469456124 807278556 924323516 619739915 306122294 577283146 235853238 590579068 275305758 371432759 563978874 800775697 23697484 635544892 345861510 789820358 47864857 544212674 117997055 234499619 383039663 133134253 659107100 115739044 902321528 821068850 641126848 504721200 306997232 51265716 461138433 158751005 719821703 128778392 145970804 835362422 939238136 862948741 350268960 179794151 617498315 974052090 427992195 190419108 872574913 926882760 270896674 737642046 458035570 187926630 222885574 672631355 91434335 799196824 17411477 54685098 21294177 174360423 364502768 424289961 777098776 157444247 910120052 979943067 513058322 810742351 457190976 728364217 448910948 265049469 437086608 813588434 101435794 155301659 537609205 126211620 522165138 853853298 104014592 468434407 434815192 91155870 680030876 5463905 334891469 307503413 70284466 769185558 508415756 447188415 87621134 287508554 126858812 534218284 291529424 743005875 321002074 141932841 84751283 170483115 59943381 314900760 523231292 107101054 506292381 338545475 291663089 90733281 99571237 437843184 1663556 70579366 286994067 850291943 918866252 925056799 686618380 745924441 217404065 81301342 175927212 754592144 305851465 473725874 235996451 640829147 86075902 263360123 420288882 104820280 940878053 528563109 698033487 991164222 458435142 445796953 352848633 663392505 437258638 380336592 785744207 490485480 931324756 200077083 84118954 308969339 829461605 6852859 1451744 780805234 339320933 916895622 682915315 630625342 780931953 505765782 477667388 605027338 644158350 120734674 862188889 52653497 73485779 460325925 891773459 416052066 911980526 195313045 83279005 541177591 574079116 588277214 38790002 183292994 258307373 90224578 169068639 968933240 421299080 586109986 715455437 351970472 517534432 451412973 802775879 500774870 883684744 783798200 445145391 250970000 6244397 467271754 452367318 50500828 627399821 885507531 984600200 673060233 368164160 442730027 464004527 78177105 201509246 984918167 433015932 558222943 727323235 469567279 766204472 710862358 126440962 100646942 145564738 795011372 301528569 629842294 191107302 106788837 485554796 916180277 368801433 459822775 476053568 59520632 560526884 241849368 913154502 376801013 743613777 237729559 28804182 779917142 956706801 844943599 595455612 366117504 558454681 855798105 111197758 211577552 731519174 865624260 659308277 71105241 831663045 938247958 413629760 251522531 615472804 73765333 423373988 704584665 740745396 341172974 338569896 313224095 143742931 485028122 61206930 714857348 21528240 723889415 120314066 77231807 339570716 68086984 376106457 872788963 604310065 288539544 994207828 410405063 322237013 822158389 95706525 136318976 721659312 229405544 321488634 206214206 726999860 303830933 424836785 209158474 116927328 962328671 490026607 108451196 982085534 422875761 457010379 730140491 734917845 719507029 630343691 608619313 171641487 212160046 247138154 774426 452275519 923887631 663292894 689379162 252098817 92375321 137907231 508714583 611073191 375438443 438746725 575993697 546458720 484275402 370502167 800690307 140553485 709776283 926133722 73485038 525722800 647614104 655076321 533113506 672359342 584793286 56268354 880561775 767545018 996386212 193733148 3105087 997795222 869224995 786956366 128641163 844206956 757507650 917222062 131591110 588600574 535832117 860952147 137204561 554474125 347937890 855512839 840282137 993100755 27676172 786749894 124489578 194240542 976493318 316725205 310784351 526529269 914320323 913170391 704039227 200813573 451833557 160128678 304135552 415524013 942308976 551767410 662920746 781963674 756851870 469341825 248441237 808434833 522741375 958650036 362622927 730935395 417384230 701313116 225450315 197136367 968555635 833871072 86553565 487460969 826998406 337152619 596655552 779987567 158877246 841811454 79334943 63234702 576231282 770489863 186925507 218622622 508346426 34625532 672654328 503333908 200550909 983866384 480351806 522292637 895140333 835194052 381947157 439759574 645198819 630511283 388480416 539275179 636786167 116314141 501452122 457329158 100816075 517067583 164929759 423411525 883041809 856284843 905427038 2008713 411136091 30652055 29948497 595881872 936338859 937619017 690394607 984616026 921077319 948733286 79715922 778689741 904510440 700646363 304806751 273357289 68971956 577653645 458975999 490410403 788075927 352576069 414069865 432109365 84315919 258804558 595700398 966122845 593324244 375546348 367659606 404777098 947415373 172126722 502154556 379915098 365126323 901529055 76066428 900981902 915096544 996779441 731555071 426319397 748398738 84055682 640459529 409668371 606980678 885772095 558282396 423796309 256921767 874789938 858947819 91070051 411924203 862542225 971147105 770896887 50562442 249233632 942042269 928445296 546642060 673484654 188562128 488894757 619791508 962278033 976647682 53590253 719916459 288645135 211052171 848657330 860035122 653005104 111520558 851976877 96801493 811090652 228024854 585122576 596035832 63067395 448075798 182413724 75835157 533943913 292195358 531716289 521790093 569175248 235204528 401628459 285708880 481427154 620028486 157108172 761935750 468238634 893685643 372185385 173694938 443136275 637389603 32520613 191040155 632349180 248891376 986094933 983247820 987929708 396577599 211135756 15868309 855654658 3093046 615240147 477964808 283747745 140187736 705291176 765681577 730982128 105654302 699365681 468062983 899703284 825069328 378989260 740225143 613515583 859143495 387192494 772921381 986825077 615340083 157372265 134280105 670897428 266217001 111731275 410266520 1904562 570041392 907998486 183027891 910973482 647534195 847412201 599444307 318682501 982029295 316889042 328510367 742277716 893608731 841221812 52045892 387316494 339417446 390442528 741526888 391230702 224833576 270840956 627015553 728666102 774801473 736391938 509372406 723782226 872566265 670330639 24164396 968699497 758979627 259879375 567521184 543045959 527954027 413549097 593684842 155178064 572548377 352018697 856598828 501191193 436430116 462864181 521851725 968604522 464136317 900504515 873629725 489879149 938624761 63174568 553036090 709362426 790142851 499929 212271560 737237702 541692938 546954838 578883804 891745412 134745011 433357515 451486704 76575981 456909364 448679546 639354380 709239570 449044283 842875527 940807732 315992426 660719343 115693554 400906365 244509721 834587559 110858367 285992707 394334768 231993119 202177794 710393102 492360989 554440510 932623758 80585686 388177827 367767815 523898550 105798399 449058863 867103805 546077809 229724608 766898349 337690114 480481131 153397672 463441147 778435759 986714038 653926796 974518326 285022488 364264555 184838343 566232232 786988962 442957679 350861859 559168990 903191471 760713723 943468157 299193393 212131899 803687300 677306900 153921620 423218155 668584071 181025327 291604958 595546500 119552295 58655267 56645570 457432494 568314275 252214566 455045569 70256710 684000923 848942718 256382199 107984332 584897303 280054083 370036217 177636358 507224525 459136206 140032851 915401077 780145991 909964461 93578629 237695747 699332666 455233668 229822245 671658061 935537337 289838656 915735688 444279774 955584123 292836716 123058043 861446690 603383712 330466970 738604258 304594436 463870567 941338149 484389230 422778331 690760597 704213316 954106206 570990191 663268406 532268010 4239383 592690514 903606893 194373267 261187510 293633539 381224559 373555353 639723132 531937893 617809099 379798535 969373317 100501611 212473803 308329455 480866028 176361899 241504433 570532328 421164747 204307093 679890485 10835942 209027538 155774080 547047960 525118297 16093201 4585169 220292224 63838406 306993433 190239908 947135393 348823916 369703468 949956010 824764379 73040736 33525589 566535884 150006182 610603605 99263579 145451820 990040243 258713007 452146196 557970073 549819458 108219567 821022537 641223150 572859407 622563912 690182690 684270199 951126639 320678379 479659486 790009482 424774290 958159498 484799779 896845073 685971775 204456613 326051553 119923266 552375830 698861417 590864579 408043028 965970718 331566629 127351356 71110391 29623259 36906153 250540308 806650694 133130384 350664252 960702298 2174648 897696253 120716365 298036005 529488900 251492203 395550804 933106954 404327888 869781767 895419766 94769838 863644884 432483201 127352680 290902501 48792473 391469949 487658642 770365132 216871421 520613672 612623091 974430526 71039484 714730231 63839606 244248896 917006867 56503736 60389163 954654106 105901927 219732323 739871815 744695809 118179917 397160245 518224227 858891008 153654886 46882352 304507432 311728219 842420672 588100684 267352949 175958439 336435698 612650586 202272129 909173498 12221147 903495781 269820152 105624665 242548016 247785833 925235488 6186851 643438031 42130391 618487455 409464593 634802330 395373208 448260207 945281351 402561727 555284564 746405989 485554461 284999774 971874740 732649261 778645661 168043752 384558959 285439583 937395736 290421729 639971749 274422473 225768872 912747229 834044629 838235021 94688376 871638155 672549962 833807739 621851160 149198018 100190454 939484395 835254471 566006486 898511799 232171978 637806109 340992351 179368180 540635556 543087606 144094355 109570191 774725542 59169273 100032840 6163795 874474797 230792027 519752491 578143978 608606767 908464479 963953729 670528484 393842256 515211196 385219365 811620838 326582883 614321124 247409508 951305019 248314370 115875087 796644064 355818475 546927180 426267947 433969800 880250577 720018953 901593565 974216000 633903186 652511118 678749677 914664375 371014751 683455835 66838852 669108650 459691324 596226164 247858691 465101763 865464935 691124411 430191486 485195228 168957046 122292113 267565083 96048875 11565192 925125810 324294837 518508178 55155634 739513810 616311030 384984933 308545843 776779447 979326749 778193572 279889189 309838338 400469342 760952424 462920096 67200190 750721067 458630855 751971039 585947594 494407707 263288893 351714768 287389074 512779570 236157393 626641857 642359451 465840133 615432273 634437399 854490419 716650458 582134695 852843217 268637495 455710604 339880980 929283932 304552058 144015723 239648585 277333997 597703500 922122925 713042846 183762180 127491065 739973073 559729174 992149542 521340852 204496622 978624782 657051566 932284135 397721713 817471528 835568614 14009542 749907728 55648326 238272744 908295095 925727961 98246242 747352752 961162017 714396761 302105268 478757200 903132351 427205964 956247244 155459123 82709538 62774230 561111470 121529710 182602957 894056585 395637135 25587769 302558677 257877837 647227469 372666608 293919101 466595853 33397843 622387566 29108638 899882515 44933931 242248527 598220916 738903806 117083204 901380292 574367608 186840642 400797825 172548846 357643934 476503945 890013873 828150073 338950794 155876072 882463933 450822914 282044912 238284394 268281742 123950668 186050403 833761560 187777843 786242455 279588575 280289976 886184867 266317067 83441553 132077951 192417384 623207359 972788100 213423698 587016341 354725224 976938963 190630337 826462851 596751531 515303650 176952091 839362969 45804518 514114966 975711816 833055810 38141727 372581143 372893772 870531794 903639098 642752687 572644130 583633034 875091626 480671649 247544855 788052274 464350198 684154688 115056405 991503661 188599664 195249618 970485653 463969396 374521231 16663745 498893610 5558880 498717159 146803373 451805563 255514490 72160664 516812796 792255920 932083898 787114617 211650885 116531687 994465512 803118132 407805687 587802398 609140724 862347840 379261050 859371967 600203526 752146925 661984323 52150500 240336713 548453559 480016525 437102380 838829575 107085469 581390497 270896652 43407990 429342311 192090423 740005784 252007696 581731426 505239154 704411022 649724253 705902639 748400531 413880976 580906716 253596225 995119924 256687605 711481099 222525725 706946544 275636512 133132907 45359474 259047962 414207994 444679492 726999747 264365610 578457897 108203324 441839036 908793289 853108522 576813729 752332442 760893052 536801422 240066643 908913407 588303932 356704933 734284053 192811676 909989852 169470118 457794276 170557849 812512066 198643677 261031889 987140665 490597706 259222604 592634206 552971067 429460879 11769495 898612518 133009564 109149325 13862147 373230958 271236275 608631987 87255332 268970647 78458164 280591777 921324722 475537964 899394328 244962985 65210675 796362494 830174808 699741999 832958180 884032464 355000618 361082676 735479545 892504802 868412622 284591958 281630174 272132602 57805520 187494130 773294401 311877412 303412807 997085401 910056783 389067890 701331479 108770100 512762264 402649575 457614734 906577279 574898835 177074009 972737302 390101754 767552079 135757963 26348254 612060322 441410607 576569449 215756825 943040421 184726642 448851124 394071709 875719472 609158522 47579497 364068849 855440592 576900119 402722156 290829842 39233284 398424088 452103142 99421199 9572700 102986457 59669280 656466174 239263277 33571179 618343185 9809532 924220676 189777140 973111880 27612558 713831494 918458957 629535567 602581616 990922977 321134985 203483246 484879559 935988521 599367795 672058248 523692919 103699039 740109729 188098347 715414660 252801376 950555143 164009061 711620843 811497114 919097020 144882424 591024562 815302569 774596769 292083247 383114809 316423051 941140086 477531224 219442486 449651413 1179621 914507382 769612063 444305467 967546078 648122682 596710496 569966092 407352750 377027532 960797575 875094852 187047345 271701546 286274595 822495611 680332619 286245356 359413975 899973242 294057166 182213427 481792165 767247278 543719946 762213792 103284296 533070084 309281106 152643452 657416091 84507837 79606960 943302025 739611691 319114538 144788460 598367029 609280496 792699948 416421086 783167690 412708085 729738769 30153300 682655527 119837720 329052614 246903981 668580027 558969979 260287705 926777241 364415052 27418640 54985453 720861667 251560060 241836019 155763204 382423805 589119810 901846514 257556283 224037475 578194481 334518630 417251173 941697091 455220311 515899123 762042728 826190398 887307544 481313478 480762676 663446600 399301192 206526390 51647408 758040090 195912879 539502372 593986134 511514449 907504082 874369966 642837887 495710970 833480062 441444262 311189599 362014343 279643434 374372559 695473087 392086780 821862198 981095225 73917000 268150272 206166945 701100129 451337218 711087740 241910209 852940130 789578059 263488349 758859068 116077529 269469876 609544569 200140182 315610341 192707058 94174004 193293962 613820320 815867371 167100803 527292967 766303100 733488098 133362837 495665625 57061052 999974877 483884069 110618364 210772536 3317642 60634807 560373611 662031607 348443922 977301925 731444594 906621294 567641770 982632462 793851071 911994442 587360639 791665049 196287754 591667967 113608874 476651735 550016442 741355041 116903008 785858527 871788938 496429314 270761624 409893441 55573926 126304576 736902232 890529327 333016836 828195575 739165117 38469331 48978632 982934313 526078550 606581443 242814052 709837794 93229659 371063064 861323176 171657565 771475648 516393638 745244173 595431649 257120522 178970116 774856328 773521268 910382527 744952793 816716602 458583255 428516071 515985240 241870078 614212712 479100765 315821545 796417980 103877312 176338510 281703634 912400905 917155893 912443478 625439702 729259097 347499903 402644431 375433005 409326334 574341160 728172817 386163941 377198341 732281847 108329957 24541545 320874901 943455497 122158126 468413243 644411536 204521878 286176789 184321369 5104959 527615939 638367497 432404224 74679019 11161773 557795580 509105132 251238583 569787894 924152657 489234221 318097180 62016890 78035977 84984049 822688511 748953274 163541214 854402046 299444523 312462331 840474436 546837349 547421335 324939230 200443816 146534183 180553717 555944927 60075177 328845410 737553420 951252661 992507287 275924934 100280153 319649314 195485306 542811828 298699274 712886971 83074937 174521383 135071965 792546599 850650925 71176329 64429435 265645120 308594400 118502644 339417582 672223285 811652950 181822514 240136903 696313479 250653598 948982287 523863585 901502451 500893733 392587672 664775201 684788039 101480200 274440425 864605083 161355037 754844358 403088181 396244589 717648010 489065371 45423416 354574577 835630491 63138235 574477477 819361136 105246758 57769488 445198606 175766015 747847840 119397082 162193556 199748250 293040518 920567456 186081875 265049180 898751571 897256319 114340126