5056 32218591 508968504 80155370 797085930 388502247 941362648 132266038 389776776 447010553 610010096 803232528 986064152 901715224 924876547 703395388 743622088 553884101 881307153 176402117 354601195 843220224 846247799 57160135 197824345 165437614 628258701 975261548 994136828 793621056 857670831 230765309 324449985 548679650 722306982 956877249 995291729 783987646 829316390 8460045 532755558 807300182 880312357 61705434 630943940 607768781 709215222 559521841 707806597 573751901 943747157 140759130 778157361 125385337 948736447 317835721 575440955 831318989 928807494 878415136 896931984 655047839 896937173 90975474 552651842 818210070 988223121 684134572 722638676 164050994 581984257 52032138 499927893 934264486 985343280 732067083 949005344 144023106 501319148 590028800 865102450 618183151 861460036 498239046 522443108 189883232 863315202 132398070 155963519 776445245 828297839 621982334 894117177 972260331 996479765 523152719 901463786 259175069 409813691 452782319 785301039 736154906 859837033 675584782 995319289 567931029 790681988 641216528 690036142 497493249 834738041 459564140 529370106 795367303 832245949 285325421 768008620 572502492 633481309 862683526 993544250 871168912 882652486 904501831 936001777 183537258 988879000 605655775 789541274 947689266 993778418 122741758 548180507 756855120 902069468 797274025 921811672 34257614 330159483 143802578 208856085 677030083 697349353 225128334 635720435 804172808 853141158 958853214 973629893 322032978 977529239 565281341 779695193 183888050 635291877 744933300 955081620 941630349 981287722 94351957 334654668 468325439 924054483 4240851 782698417 937647559 960723475 663988237 734597433 513847091 578517294 375953483 453159325 487937580 765891241 81775059 969908062 347235397 706775069 969375524 995061512 514981832 808681374 184943880 531232757 919237724 944723226 721645695 741170914 981147672 987461988 256563516 577426309 684575238 891162368 855475847 890785028 129181730 151150846 418505836 587296545 637859557 862143089 274589834 962294961 417381570 844723065 50795659 159724653 532377725 573837701 985644943 985999940 668474114 840559047 44177366 714558186 19492953 835694094 91326570 414874434 830917314 888069676 956201358 971373282 779985817 851435432 268772062 569430397 495246787 597113553 884076564 923957654 102938381 775743028 884863693 976515067 349311007 713421425 770390812 827557677 560961348 748266612 674550490 770719903 567628964 849239816 71960458 719083997 449199264 619732994 834382671 932406386 734537477 761852532 921538787 972879321 301433879 472223490 923761609 986840584 713408476 849841276 125881811 441788212 584587937 710023957 602171489 737217068 759711127 814782732 31571907 388592256 578834356 780120865 565934426 706411105 605091439 742295390 989891561 991275341 880313938 976190616 154582862 609953876 718576958 962495515 661505519 829361810 543764238 932240329 7060691 31589898 386724746 675480002 660530224 867806304 368196806 512626498 450442794 726701942 410096152 857517220 28679278 726949020 158292421 304675359 875611321 945636818 857675495 904515221 55779621 218118478 511051370 880263050 320745231 342245243 820850921 879316073 52972973 140489514 111886766 658251281 1 20939319 876777762 881358296 598890399 860863817 79278444 617369210 411680736 875305299 980019819 990277741 992757355 996061610 145279497 896983226 664219702 933379695 562448646 676964569 509220230 600631208 880335350 961832915 896084828 933561555 828207568 837167222 30620489 49620554 81539864 326523250 84406293 625112852 307740099 936010346 549441213 785416807 782221248 918238583 73999463 306187632 437268399 736571422 724854571 795271358 160102736 235317758 173482190 527523559 346561335 358560537 135785338 636883545 423596386 837998877 314153020 427445198 418342689 777549835 73718827 691661949 202769540 243442805 938526900 994765059 106626183 941287239 791092510 893686834 577475408 774173569 152144485 593910784 902055582 993472364 725005482 806818564 478514144 787665423 981612111 997562714 857124502 905933827 615881181 793197628 634118333 765074648 364721807 566046875 848514366 901931162 392340348 788137587 679315882 687658780 246672825 340354719 420499151 421580304 65551568 608431090 821423489 908890225 623680121 984182375 945550521 971120303 314929842 986556734 837933376 940292759 811081668 884585528 75468201 957019026 93964950 266894928 150231277 451118808 565800381 989490407 356743482 892393884 955773129 992523490 208663426 839334939 346449055 626144636 334001996 862981717 993120423 999547166 958675421 967919495 273028639 887920004 133562137 404899343 53360099 871505491 983861715 987477559 698597614 851440904 839164285 969558058 107133128 912332910 189152761 604401440 778860325 969381228 168305220 856636989 506528872 909579477 61103249 631195407 82146410 421383465 159082086 585101772 246251707 987247524 716703983 927927640 315761807 591690893 713136395 938109604 697734647 959995018 228259455 665013125 110508717 681387843 553516401 939936798 417442557 881790210 89701294 202528046 251974725 504065030 10771732 59166616 854833881 917956196 944930923 984926830 342819901 653485596 592511590 974622473 684471104 931635070 131070129 969135287 868863219 933732141 331049028 904412479 726397122 897941252 526411537 836882022 74306792 677188604 455549863 664832246 61794121 689103547 817295874 936317041 732587922 844928020 994539571 999356354 448920618 988371830 568805156 938807908 809928407 853872428 271758481 769650798 712941538 765093093 848822494 859892011 824571708 903595491 784623204 814614409 559138321 897598431 574722278 902433340 712611805 880300314 64871967 622255866 914624711 936489582 98985337 402012424 691325282 749323628 326774153 973735536 533643081 589782210 667274442 872708369 702345075 837533757 738089392 908398174 796827906 912537453 731371351 909054316 339143431 537706968 945340215 990349709 574158691 754937754 225940770 835424362 790307476 912264963 189650115 294916797 592037230 872547046 510212416 725281071 725366373 945589967 504035673 796797585 792045208 834257165 20146907 116058095 624427848 837582114 483371960 588270985 849210890 989367630 907170941 947805584 89053939 237452002 789878878 924678459 420243396 669082656 77806506 737088381 490629991 514363710 200147023 762657627 942249028 985877588 524770997 687245743 176152094 467826688 144917360 382077805 515592432 624780298 261812980 598922517 679876517 699416915 381683454 566350292 476769983 864383744 274956090 716329747 30475990 434677408 832345340 879258838 194906449 350093645 725526604 770304796 135571813 282544799 880699340 929932617 755220633 836244885 269923275 876269358 759930739 991933161 15259891 944647429 934139977 942767053 387026566 717197668 378276767 551992561 602862877 756926116 971618604 987375031 535086297 973878881 122381819 660530979 552302234 588074712 280883573 389601794 943550849 954568137 172972541 759941372 836392205 961699514 248900734 964381422 537596172 905627032 126700941 910917687 442821879 633325916 668302632 725647885 22453516 643765362 390069481 911377632 799533069 963938161 90740927 577686430 573469493 681957848 940439286 979453432 357929550 386776030 571893239 702586709 619970074 826406628 232502178 650510089 505134490 610275383 922209477 989665377 755180904 958670208 254927157 764400823 71910404 232637163 801782105 986501486 269920778 974782440 971601676 975492538 429635065 461625717 435788126 931917391 920315642 955854729 886526418 923102701 420125079 617078017 37939501 663005534 508015739 943263673 5042365 612442578 802880665 935444222 826405076 996652044 430317624 991997047 52894784 880552023 60928136 450806693 891511381 898105942 509083181 608209970 689226081 714319076 232305391 710604571 528927140 939565811 793221409 981474252 17154447 305151045 493084051 631815845 228898489 833056865 684863692 712025067 588526376 987773554 279907939 536161149 675409451 913867272 517787278 530539465 643092789 877227592 691810528 788500245 410478499 883322418 813975152 876609729 656133185 766860917 460781366 665114157 137203707 760882226 953115089 987889717 977461935 995862232 754567987 778823937 857978710 882974170 346396736 573804754 225962060 548016750 462155524 642074596 431060244 963310757 42228874 661264490 77356539 758430356 916464360 939454924 95977494 763651406 167139002 952822426 885852887 945939050 223864756 787833721 333140663 980218166 920304790 962160471 32372009 927448120 420579928 715340493 759263798 968396311 157114480 160308447 313333399 815874241 266810240 385046378 936643008 941997539 684450668 791432709 979447126 984621023 334042069 990237148 804504884 811336646 542195631 948570867 940852863 952434267 545626598 927172538 626275517 710481149 987260224 994450282 574467391 692571393 674070118 732873797 646082766 751556570 293799499 375231600 20421292 86900148 167593348 594711831 401165205 741530914 644642639 834674367 64653705 179258213 137118106 765446195 301650798 677402540 540352067 818851146 23826450 297330358 855757624 888022123 645175069 994414527 337340989 779530742 737808408 861660665 841546710 981790736 994363258 994582895 307815222 422373955 411546929 748140931 150510643 849320508 687729531 699205270 193543023 535880642 806269600 915113610 719667184 881282569 461824531 927063072 707809482 973624028 907552391 930605276 440737661 988690106 657284960 686352546 919198750 966293087 227780714 622120101 83839722 247404078 858042086 904592094 713140348 885912631 745233137 798081052 487229238 692523866 944575197 969029745 69800461 820513958 840844630 916067872 230679770 912295274 942365170 948783249 411744599 715020049 667624163 970277217 246993772 417083634 86101810 447345454 713931170 742798465 140915741 630540355 793551347 980995589 903533367 950738747 592281005 770418980 555045908 645491857 545423006 776394128 310695993 716064736 248334963 731720065 598715951 637451161 177869987 216397788 752622196 910067441 585958202 703769078 228459263 724812931 418893785 656080006 863258536 987392697 915095444 964986430 117438040 181112403 702403275 805506985 387641881 506820587 290502955 298115078 236636763 814734416 989752302 994134269 837233941 845710585 694648760 904226209 158152446 888837550 789340698 844794428 374571198 866379817 588791236 727680606 448933210 688769783 943511200 993483201 236283688 745843562 162622317 867389492 865104915 898073712 655322074 717863087 756079937 892094688 166597519 865291263 904425355 908429109 228741698 299258142 921350962 976731824 659587391 775960317 722773341 881595580 993192669 993780838 343808171 663607275 435375568 641285017 820099744 960844764 289543148 807579954 997761544 999751666 525224929 689263026 199861682 741782319 203547052 729783148 277145900 805506090 139504389 190650139 81010947 502559778 104894802 618242751 517234414 976044834 63505766 506035419 57398605 197150413 229465538 446437926 975430209 995787948 722824137 966691431 27445822 289167760 191462476 262927452 744167551 939266688 51450958 440409678 558167039 766654787 719300623 780580997 722190070 838593371 283878030 937240136 563795223 788683081 587130015 894473650 83376151 143887187 78770192 160216340 681061409 900979063 371400327 636806109 89482957 259542041 420291168 555870315 465298525 724537027 933795846 979279119 311601079 322546507 566799396 709962554 378584590 584728104 88148058 379892768 493152182 668466760 205308791 594038418 222408870 410083871 159018462 278572424 782680334 952079689 439761007 691688249 98195194 171436197 41362306 525720541 638426774 882040925 12986557 584434549 938610128 984596895 262286853 481600428 204180130 772848169 393113455 853915104 119974592 237459342 190098810 260737968 835357856 936455026 118097918 782915242 60262372 870635833 471634716 843079904 718551166 768511220 221990178 261415809 128102355 998310730 273874639 319523977 912985557 977146241 755095850 932619588 176194006 891810254 585144329 608671172 272693903 706133650 205917067 409856257 666753765 721219277 378776763 501420498 762910829 775285568 667724752 811058936 810848182 934874756 904323299 941205957 55120945 520783993 20025307 359230712 553022244 743263020 809075506 984198120 361011795 609683859 309483467 802482804 617109884 792482332 189143301 578801760 379175435 842900627 918431648 918835797 469255645 671709112 668259867 930938324 202079122 694937636 613068198 728060105 897534705 898113101 817056814 958804233 646466932 963896758 24349869 183729905 699167663 985407266 919026337 977299470 186806125 203937010 564970971 827646130 120511999 244047693 464240807 749604934 69046294 344832261 895983331 963358526 945361561 990298460 719093585 919629932 788136988 800492646 658689901 869099868 641799294 772763906 124166655 571391044 407594665 718448099 761965373 831931514 613847622 896601316 243072434 964860524 616180050 858342234 895173542 966450791 595399516 975749344 664918421 993764302 977391415 986469241 376432099 598072910 710457826 986004203 352741286 400856652 39332461 218016490 578419142 690737347 331325144 531795195 185872454 349925746 378742573 773361532 217457540 265064545 173454734 960919314 794880945 944078315 790332074 809154444 931973246 975845855 39383285 745785794 1 315266598 600471848 972426697 824244740 835393968 503403531 725886139 670564203 716710415 804786967 969388441 179308446 579009583 306143475 492694533 961082997 991095565 106317205 853906794 930389936 983381514 285997917 722383391 1 592674083 78918299 271218783 683219903 904186229 59552937 241126556 204707265 617471947 563111006 865737978 953150452 998546468 66672200 91226489 574028528 708893614 610214004 882684210 782377504 854750007 420094981 614517414 415032866 640862735 406037585 819220211 98043357 104285456 294194171 311246165 623044220 733482031 788855449 975873013 645344370 702977479 347358341 370299853 718129701 746390955 80269973 706116005 574322016 844797034 480417545 612394963 508507088 827911077 480063993 689203075 149051307 742413270 363851737 671399798 78529972 671427715 379038175 909989280 470604943 851125649 575779023 626615031 62152711 892159152 992836126 994775102 876843189 905442726 715667029 993817746 250233897 738124431 151541968 193014174 318866754 479539968 637068512 890477154 936258593 937109086 237922049 592420218 954949159 974392028 518341528 710169529 758269854 876946980 365426259 581633538 647314176 848366766 904009749 987654372 268082534 909471520 188019796 699688622 168894344 546820462 254506188 845041672 767301210 898363374 566977554 914559377 373465427 407031233 183895078 854788768 987441369 999530881 712934664 736599474 332677634 787797675 907962055 918582738 246842257 852219784 183548330 520940268 560563232 719869572 592812108 616563150 63530135 522079932 628356481 942109612 32968786 490741342 107896954 182005335 928999101 999475247 888262297 937430541 575924247 594387510 488380272 785009860 513786327 913582710 124154393 757936918 298824953 318264793 867890789 910127186 247766692 901751963 82136001 203779011 860317714 928001003 375905413 588240207 841860873 871382943 157721731 317830667 464195618 577925401 87574524 824352261 952856842 965141907 82051572 480400565 211699525 935011697 6954482 969396367 803953632 877021798 510899954 551357207 842562326 854611023 603403554 826309601 381185812 467714772 868463492 949589842 714760318 931368394 537734289 649977229 257983501 635816803 257903271 266536166 511557990 843676619 733600615 810898682 455182600 458085530 972257662 974684578 760008747 903239667 613869763 957760015 459393447 506503647 684457416 780307408 738132984 961092696 107482725 196276553 797896187 806249745 654465319 825112337 394647519 487140170 469015961 816639633 620964180 901472253 152818706 689434686 624208606 884313063 590493603 929143265 272604054 632874481 736868615 956550367 61014547 310578036 660212691 998073193 552564937 908855580 772211267 938322720 1 261547652 880850893 987550140 765147617 796524064 776813722 830331551 344087209 785733700 234619096 653479528 662778585 699572733 557904893 743297211 98926217 158469231 571531531 719408430 533851773 971075685 512115939 755120273 127652061 885607581 643085934 756024569 239120553 673737648 624234307 987380079 642194057 702737879 951046893 953603652 119405760 317083522 609693477 718349747 171167568 246152147 539179907 990376154 327148078 806681420 708981488 857627520 264818130 664876281 56048335 527159281 831141709 858503789 324462966 668061272 325996060 902229489 696820823 834412854 501347754 823574269 142376650 881226269 486371216 493039691 334546173 484300542 705134224 858629496 821774570 950897312 199564056 551075431 47231210 393928199 991635983 993333099 141410813 944662762 284206798 792259951 771731924 777681328 280679446 456562729 14540392 152798222 199189713 819374283 17738231 506006572 142826544 229058115 216690856 841155169 763284124 985849447 271236573 749572888 858539275 914463939 590897906 832034748 571898627 616279629 480830523 504251197 527342272 587699792 817601453 864444740 588749440 889729109 622467236 661836659 621839838 693599114 722574728 825550169 973758088 992014190 714504221 987535458 739056286 866350494 193206205 258817471 680105614 785470396 665329438 773604626 883628623 974472206 220925596 856951418 38259257 964458366 456291742 910229919 918994844 959995200 803603347 969077277 399769278 777010604 257241495 451723528 587093893 643115025 218237411 477323969 431498505 614199845 447420407 631882209 883538136 914378489 70818292 821990185 365613861 944199865 978954978 993088077 857892940 920615504 723619801 794657178 286577241 672615010 275799892 779266467 484148657 977341969 315804825 910859573 94869801 701806687 392002774 855715655 94734217 707111848 283856466 785588288 841780599 915584862 282837040 341787636 206431168 399113499 319246587 785646458 240514718 617558592 345252421 421961469 308737353 924831619 313270371 711617207 104413369 882824910 841092828 885948047 642966605 667477617 263667323 849478477 199972671 945743654 826216366 903836504 774919461 937346089 68292735 458188461 230866391 727142175 871170678 928993867 280992974 821886727 931283946 939204765 406213355 483306122 249241616 264798898 997072514 999710057 469811629 664490905 307711393 736301242 799797323 967159170 113472645 696315673 404258217 693746935 749631769 934432357 679300447 938523801 541353409 897997957 642305289 727526097 672520268 972861593 605795788 813133251 28743655 126911410 863358329 873508595 552788576 942143251 410280812 556547490 990915784 991284305 455846277 893967286 956994807 981945645 562044899 745759271 889710913 953319833 24172057 820346373 619117607 802489149 15596565 210213037 570711476 685736691 662670865 681092280 918087421 986470054 89214493 983934242 532429283 847861702 171722581 217617040 741198589 815936341 408449447 741159063 195203928 623577278 209088612 537277132 966641550 986837085 129398028 717379326 943627540 989017771 24871513 638636736 788011065 931298296 539170637 673134485 629385444 695812197 594334416 850440088 709900128 860314130 569209106 648591468 674155835 773218888 639785497 650820950 275239264 362904056 359393601 615759519 267807395 741186711 914923153 956759682 119919778 436424761 995454813 996587902 94982904 564184150 550151843 881893407 47011192 714077297 955417059 964931333 674844895 713671195 248591121 495030733 206695981 231706835 734724602 750670810 376529350 661493367 488424664 561629538 422885698 974227006 350272539 434214398 778368234 998511328 396427716 537695771 575876338 731700166 543037058 964680954 312796890 940115750 338431906 676586883 370289873 744807352 966766492 997598091 915950238 989570120 203516126 707579275 986226070 992283647 355481427 960541884 787276996 859120131 580798076 872134087 831095183 979249449 867011263 921583412 680246129 842274932 226008586 440659754 214073848 429498038 706378427 764442099 239284488 698645652 643501537 691315151 263417705 771461814 798844483 969254791 689476253 902072294 320349227 980444720 133361403 355590965 68020099 329855544 997353309 997716204 914253967 916513962 987759806 988484317 362878583 444772076 652252306 912336015 155768735 586713145 273537805 540006006 886324357 974808523 348366586 390370117 96318068 167344804 479609022 671117630 704944146 913078112 357538310 809093448 554565273 857969796 476862041 684565071 171594209 564803676 753404163 904762697 604762370 675770579 738599564 857578431 7920226 481567455 533527089 555178492 565225185 715585098 834772203 904902907 601291514 780388373 546042425 862804136 48540598 429269216 677988660 752339975 942081175 971685045 700725311 946007112 915024275 921226624 390285571 523195018 468794959 517548119 295625305 573647368 588498673 904091682 938076859 998048515 20824036 469348023 357655490 545782230 859022332 954130220 210421887 604976587 555492148 725261977 550872516 690990087 439201668 511367102 853489195 978521039 347248546 676266306 460152644 541715789 679942100 978377595 883622869 884538454 255085926 746652538 620337567 873916542 300076689 457602813 676074578 866164611 443038908 667137793 335078059 862652194 914412717 968026966 37688492 620061010 366677577 736534087 69483714 988995879 672889485 753299646 276458909 771993953 565463318 636829827 84561432 819300735 370138572 989825074 887712287 976134201 585525107 931591900 469467780 521053946 9512707 421403220 394027156 533841718 989040367 997497757 36780128 483037308 205277404 521404951 168121507 622634401 363358913 790066648 447202271 549682694 933971169 951903014 308416699 381019166 717170324 886805674 620327241 760383942 510932812 577772404 336223029 883642990 627505114 662635891 191155233 827290808 14842716 688859609 597101509 958243766 941159029 990807098 173126236 198010607 391429755 753444625 427080895 443670168 13971965 508226413 621374084 823262139 980291717 998261521 896728162 903986932 951890700 960896053 216682278 587850145 786429109 973088020 680040951 698576888 832855341 948209672 988718318 991344256 323664718 695817889 417806487 813315212 8470683 298060763 344532905 953287464 304270038 413705347 915624500 994960235 500137619 517372458 531509407 870996774 627585875 999295858 462153968 665893959 819583810 909917768 671106526 929396934 474417028 654622772 322486932 761367899 310094270 530905116 781304087 794587240 926783030 988966576 556305005 631566696 819438846 890725980 131204523 381639012 362631621 915457033 416211700 445647106 594449238 747573898 667815305 740557482 677703515 859476290 748729786 872382167 539168328 858327297 492031319 709534449 471994102 735614943 287299684 621698521 236369821 688167398 799039847 888953370 747602411 853287792 439326617 838274854 582645793 620910458 620138934 875586187 898206760 968021145 550458819 847514346 486642541 608342669 505513326 807231128 323739017 618919920 770357342 772084536 595104558 762517537 703198639 943754611 593464789 755881426 50636869 647959003 587893084 889413986 353484677 596692161 423397605 737066513 429926403 504300640 115550045 414836255 297448444 740871859 32856972 373407079 17575451 385860512 190853243 963083375 677480184 736504532 96032373 181682293 572025486 718383407 596601489 670965307 26872488 274723870 761147404 851566316 738631479 742036867 772442741 786581247 1 48618572 749652601 951445936 963305714 990522274 993414733 994693628 210970747 934414984 807876365 876658719 326617352 723950525 481399856 748102058 894238736 900302337 580718621 932734892 908169115 974275063 125344870 137893200 450174505 484656327 792460326 978487880 819094727 934860300 768955222 862721474 207048085 913062696 548154036 976162863 496113087 599756229 246583831 637894778 12438008 333460089 965850931 981263292 793000586 853859491 334003995 877740137 712623415 910004163 927765944 930220342 310364746 723302442 515441318 773705254 560672134 664268271 930660981 976569069 604476251 811113132 108580044 925748752 131779728 508870045 149442937 450648248 899589040 906942318 800028326 886054331 352685507 365772042 183870733 920007162 127689760 273874016 615369699 741102052 788238246 883652697 77620981 779448997 981834770 997778003 463485338 817603548 192950397 417360270 86203978 607401140 770461151 820919590 415696726 479409997 157260661 942574706 659624330 803080446 32384050 579187780 873163867 894854249 39394601 938047848 903889704 905029807 567043274 762610718 16704136 507912539 700370494 926058822 543562229 773629364 890554852 899368996 328821581 667553944 157407032 996095756 683456578 857696746 220314856 928745941 342137639 437822738 466248195 494684661 111478354 328822305 9553130 882608049 135710312 667432611 853153281 975959419 16264369 974277414 636503610 860043291 888050548 908638699 901182846 970007867 707229222 931692763 889211241 978887739 101601898 298755862 388971054 521095279 947986325 950150224 544679508 795697605 959093101 969255642 872035405 975147525 664406737 848535555 643846985 649101694 985857993 991422767 882764910 960903244 480474935 813180676 554371261 879468930 426463211 778136250 299246627 596210659 811942219 950197541 902318747 918659594 454555361 926836741 458920434 741434420 450353823 936315752 779448682 977228618 293779780 973263852 360310969 390759303 909564920 921907023 822546005 957518252 74443874 577344533 409252723 787687707 409619234 516680685 179894860 322840470 97997289 855032519 624705501 967879559 768792712 866975345 406168237 619329380 214302453 384620003 566359754 792051633 677523885 987256501 380662395 781712655 705544611 887453469 999811931 999843232 797222143 888748457 669958088 822069250 395207153 759598035 241993350 357088261 406078076 752370724 826264234 908892059 324626825 834617181 696593964 746282455 318184052 838566478 503327717 960001618 870551801 902020472 727710009 904472174 193607219 445116024 868097799 996309732 342821076 914508343 326360283 787704469 701217317 715315531 213961077 604260205 152885939 491181679 417346926 845648835 808755544 966016688 569437679 825865476 594482015 995144415 470952496 702967335 467178895 843628200 476596230 503429201 481901040 559215494 1 446445310 761515748 805897494 229019019 960511666 412357149 497686290 875536295 877216437 465133426 978601900 496973066 859279321 406491288 935421099 608297667 792396319 275779414 349860689 40458748 78375300 687757634 759049378 41511147 116676795 353642252 846890874 231086283 990776265 467153366 881030037 280524329 321678176 386185474 581909266 900016894 949752985 120794133 962537749 30065435 592073353 592534679 756592901 369058560 797494272 180186871 697793058 412663280 536498633 839996920 900048620 73083081 193828337 863082386 863931529 340926588 851528169 546533824 925427578 535918752 754133143 925714334 986047981 344301758 638687781 779524499 815022356 743144037 905895050 396738634 793561686 479044939 961526783 246438933 465205030 864314803 912719765 386234966 609413377 13110430 390202729 548973001 673568825 351709655 353405749 759668943 942071596 941851507 986405334 134689129 587645160 820357338 924469727 591542894 871299013 548972514 670541618 625519891 822727931 492830818 626246489 874823329 984374270 943855071 962254642 859860136 903791950 833366991 902577485 188891905 394027228 290886407 742869297 955653674 980458450 98076917 227155638 768575103 832136980 629240016 683976538 367876130 592841436 33853736 469007311 173219390 998063480 533432071 903837916 99238258 423054686 190600972 499099099 49583064 617479585 848031084 955929778 279101212 971659904 246197384 402050673 600915832 790730713 87275080 983613181 63059351 834163079 534790720 609801240 201297681 508184312 357098387 701042219 517672423 693160476 740871059 927643644 14183579 906187270 642274679 695276866 279047742 664908762 851853324 902539616 999780798 999866919 720733370 912561551 689754464 867166809 532791819 995603596 732437060 917013631 189144387 350560133 988336499 996529672 947396591 967319738 300516541 887655791 352828751 472083915 368673509 436530410 295682395 419126626 820904820 979901103 704261619 753462490 844240842 939380614 367422964 686517676 601405712 635441543 60466934 333576288 589645412 666588522 806031794 971011988 555831802 907999995 557565879 569086563 911405839 955384595 372392676 826473654 887198139 952428425 598231533 721200091 909922873 990657861 737560282 913643610 748439354 867067188 649613997 818750211 286630889 964704626 746691896 948324530 100717184 340219229 415752218 700934941 471868577 773500890 447311903 801431278 177665747 945064133 923178022 941129485 696942612 719765213 207623229 258794444 910390886 926860441 307414616 920447756 196100675 990324595 619346193 694134891 408207885 577562993 181985990 210107713 392866413 499000137 957989120 970719539 242028530 477520514 472033893 714316170 205116415 521812417 310072723 915911220 735112680 789050305 488480048 601467476 465851716 991313165 881088339 886164603 272171192 734451139 980710323 994446036 644418452 795532975 102429404 219655166 87256124 594817078 850572470 859363121 374640332 500871681 299745740 630097507 570483746 890059129 374559439 378528543 573119990 575139158 283789459 286940009 683437633 942647376 498121590 516196657 885752198 938873194 35515320 858282478 331409921 617298224 864460948 931569036 178356518 752426269 275416554 694773619 824777610 840520405 606083034 710288782 305785529 883741410 588011348 846293264 531227025 622574770 946377247 962174267 243016983 606560872 627501214 682409423 619942086 795617280 364470529 537209700 640649336 759868493 160255603 192262462 424074069 727559302 728830725 979105687 554060209 857586998 291407495 355148260 296808602 610303065 238145143 415783482 678211651 751213134 369671518 869814694 168758053 663748639 266020661 896671586 867119424 934049645 737476736 812301350 203667115 287888129 779784250 792093664 83866487 647347689 1 816438933 157664459 778824986 994224296 994301974 18887986 660668752 868712722 887851631 775626372 815961174 331945018 743641802 707037906 877752601 400646570 683023263 989640884 990645807 175069555 541407430 108923218 317540340 717662471 952400065 419711633 754920701 227775650 887069193 156047269 544594345 574806498 840636366 581902573 942408252 811729581 901471917 669456286 822185320 53380042 244941084 278978998 911441236 750965497 879137421 833748857 898228392 297920355 857487427 403936237 917186074 225048577 734447913 927413551 986953351 490443800 650114568 907896631 958805437 782233662 914615935 402383064 542427727 374787520 560443535 921362004 944848569 748481514 751530405 163203814 318961176 490410191 842306780 552011916 693706704 375569799 952750356 203015639 810739983 772853315 968078727 458349291 605814543 605886080 851280555 51634214 516841775 34181601 937987494 702040239 727936742 797012795 878271553 872211739 952519966 845533644 864435580 841289121 892197671 14168327 146695919 20062920 459604383 237002635 901165189 842744009 899732867 437982193 656715884 376614970 542486863 515058422 701629049 546971707 679881825 887656085 908462753 398824472 842393531 72642742 536758503 491697184 534941415 504020194 506524921 461307514 568456163 349437505 822518129 633925488 973978355 349583738 581842815 921092610 958089300 713205101 736072202 355805941 841777506 164724352 853754546 357788801 654704279 585887536 964164481 464564490 781984419 910424521 952108813 242811598 309386746 164237227 467892169 318821656 768562890 340016614 362806938 570969051 875477593 313315759 417305731 529168123 637030681 594343855 641954793 304694118 714308771 879728803 919077394 296526464 483408500 386178442 935086472 768571918 921748210 310450141 748213231 85227029 292103985 55450213 162805812 769782912 888686450 333328054 539088955 771200287 889099716 347801923 851117267 315283686 667632262 699104077 887211983 582966384 725364376 1 191288076 870237766 919638013 961138331 976727132 618457961 706537513 423155606 751786797 560074125 839408892 492903094 596640359 499268608 638786737 486813791 699017572 793871115 863806743 848779636 974752250 105913400 223034214 87270288 127532057 710988559 929326405 917708989 948599060 449233968 468361792 87353645 428262221 450953364 596513118 453311703 926711285 228229868 247032194 739795746 779730565 787882811 943422057 295678948 405081570 703262286 865442480 867024970 881712899 18424731 731454379 985409301 989433084 862157559 908688883 782958253 891706245 826204157 916468858 44502915 927448533 38144487 45427486 643340841 893458935 119380610 228864596 658313044 937609114 180567798 921091477 88888684 895423956 899719268 997349099 234662337 487398351 279274687 824389317 157286292 222189599 108149742 440716034 910376078 987012219 559299902 974863147 356014186 924573651 184158248 247405214 922855020 929777961 291069153 755586314 662381385 980905656 664919149 725801632 203710135 862991933 402386180 951835355 514801371 879983370 83171938 521931352 64968745 480666889 838531600 942717221 110396016 898464460 852339596 917737774 279029331 883033419 248243450 993132328 870596499 885956307 880369311 978364092 18860670 343792931 472761039 763933131 883815942 927268444 204620624 977914129 725727906 738243692 780925101 907330620 60752190 576053643 261341530 898771897 875545407 974495896 948434921 967123056 467295708 923256214 736698288 775938587 616931027 840288372 396550066 825731882 1 329627974 799102868 870669781 524200513 995046629 758315801 958044244 312847745 893076393 143768367 206458444 389209721 464985431 849183238 952073885 229200830 578684116 861244640 960018948 834573867 927562688 186133563 986476904 95894672 154120424 877639936 884841985 761556059 835078195 656318253 873926230 216748957 420148813 991342781 995515101 629249089 922153010 648994006 940338786 184857981 970854368 42765048 155362246 191867624 734079529 449916389 684021758 73968359 362538057 758982468 994973873 525180967 899569642 466623752 689468471 217338052 423935049 311279709 749453044 168762004 371882818 481700763 558112139 962334875 989427715 827415430 851000364 907584238 929116479 932908653 951443320 665548923 753694069 619031803 817829048 482865953 756811898 293219509 992036549 6837628 310722793 440297798 662613963 1 967952827 195098202 414290624 441969616 676517398 37107613 898837453 906197432 975329222 891681923 955966186 595635925 755049935 214115313 758144887 682599195 708870722 237800467 902451156 600048450 815345573 475952591 951402583 678983778 965995300 323625305 604661729 161157814 969527016 118160173 855434261 48017958 140434413 989452797 998340646 156559382 173708512 865701257 903583833 686020771 716583720 659515709 787570440 601081604 785046436 298117386 576206932 260679788 690411055 490499576 552914785 187172285 623041392 63034326 681465502 1 73491532 864185952 927602493 361630478 990785331 885803303 963078740 340083700 393986997 493274276 552063677 580893908 785080270 636439218 840655442 630959965 840704429 122407655 906988124 115548768 357294990 777838098 864727116 368201880 499499133 89639899 687010632 454588062 932892088 48825861 697429714 1781310 168354763 771039073 968518550 614545057 854778788 195962159 254093269 836784860 856217245 720483872 733342483 406781218 501534601 753021516 753534392 634884833 936911917 800772021 827254136 825172841 993686535 315027371 801991711 585788067 829177196 136221867 713682829 596978664 946305808 539824365 617079220 903353574 970331487 525220771 941199855 364474590 962641025 496986405 776885499 912494152 915287720 269092261 420983196 293208410 810472674 935769989 965429445 920041574 969347440 536612951 996852488 269563208 334599489 671547657 860842664 230699543 412482501 296931956 906711542 879713941 988784427 831199639 977609360 291042736 617507068 806863116 838074626 388378353 649515915 891156881 970463641 292832740 302743237 852240871 987796438 624360206 729188364 476388091 552475623 574959923 956309695 588151090 634830616 249266775 998584474 433030925 626975947 87653121 465471648 98725437 503153556 808097918 881243250 163446596 945371137 971141364 976119368 997293998 998999057 2505489 970503717 852445522 989381836 826406934 949855746 187967590 324578881 768597206 941490188 23573669 454245002 174135607 541343402 90655970 958368852 12317915 966058440 759091785 888623544 625310689 947356811 451476010 683135880 833908118 859326519 991764858 997448119 491306739 999028235 309410443 973496252 404238932 786529730 790579511 808929347 373195551 496876676 934245828 961831607 680494496 806822294 618023532 802243739 664672173 989557665 259672600 798264738 265096275 983286279 39596014 944711604 506835145 701414344 677641223 813817350 712945228 869437957 687682198 875932561 777675430 902808014 27933378 139925346 95883875 116777659 123049056 798874065 63562887 449566114 720155439 879149685 265537699 869936774 335935716 860880636 42338685 738112384 710371312 806284179 736816227 796005246 166650542 920139503 965599797 977014813 829746701 932372792 845765536 932722221 689744948 724189772 597119229 793214277 404344095 897254215 86320980 179140478 827951058 868002702 314743630 325777492 162164983 802022576 907662739 933361132 107856006 804385455 210619195 892129131 83414867 348332037 960596693 999450153 996294918 997616388 403333860 511162606 453082763 943010390 656943722 932879597 857559618 957045817 4959072 530207744 662719561 879917852 586707702 891326909 401914817 467973979 462438324 727421189 978231263 987532090 225908879 329262636 583458945 747812581 36073241 587342297 100989309 129847951 621582316 964084129 995773960 998955523 634718714 716551706 947288965 992925118 539877457 954882684 76496888 887249040 70458705 891822371 873231719 947145899 795345579 909910106 188162616 478692038 707827036 800574790 770533703 816222185 642366694 995433481 652394081 816476614 439680151 832109192 614656320 626566773 685883562 793572255 780095683 880211112 807532357 993166066 694655982 916868337 424963316 936398925 997099156 999332955 944962249 952232915 932187281 949997487 607744856 627783032 10925537 592680917 424621654 780984160 744625103 751826510 283363567 646355469 485018875 590434563 561777078 977857307 681960167 888235759 297093396 506257757 303592486 637193730 506769953 697239919 616670091 904176357 913640025 968618916 723752745 940344567 429914772 927584969 666703116 744951261 34729409 643548834 14808593 558520450 83751699 127938882 871958235 990140085 519745494 927635505 522797659 764492982 724628152 800833281 960769932 971818589 696772306 914353164 698055647 755638741 896681619 902117148 22636275 345918678 599458530 744430668 637577090 676891796 36942629 980404132 744607226 964404808 724860603 963651847 770794962 892846435 558097211 614907551 377392754 764809420 835035281 922444244 122840518 209968455 663055847 821610302 951199488 979871285 1 755897693 180252883 226228583 986848474 987250698 182802371 449966504 338715590 502883956 63806925 913914411 359663340 844805244 162743030 644857366 148596007 206925759 217552543 304231688 485750145 570866703 129712139 604604167 363092757 420909121 602550520 687801896 278448366 708379324 634553120 674716287 339638362 670666347 24512808 280778170 786107026 888819273 824058201 869671355 502371000 685977601 407363650 941906440 193277799 516357767 207791722 881002556 129491610 408317633 889016462 950854424 990741109 998121717 361286369 771287517 262241874 378696203 716359158 843719950 616346385 930568631 982343129 989675487 928688528 952496965 150262074 710794119 686095615 804683567 518995323 847260479 350734281 709426565 183206298 890503012 778611987 995609719 113988304 466651361 500073223 655710805 436128518 591607225 658053658 816643130 217151676 351450479 26779297 550507595 676982932 944138347 631803893 980353724 83055874 824253239 314175863 629849179 802546288 862974396 323189960 561052726 660507246 867024849 461235793 716028286 195528311 520319792 966440068 998708479 114951873 485169996 548384164 871658245 694241053 971458553 883670939 951981752 674410136 929698021 935412996 998655418 821717759 914251431 832811494 971645082 428625130 914445882 286948908 960714471 54592342 530358971 247698016 700409519 526270515 576086718 898752748 921094293 315215323 594047229 755698386 886670642 83370368 489365603 6785778 270038631 956256672 993713884 148199011 365311475 897221311 967687443 245530406 883404404 396883786 448482902 929481456 997224512 539224390 677794483 339341538 430247123 888536644 995150073 892441466 983267605 750301687 976576777 352627923 963761031 830755818 861892562 803318846 841256682 271956398 530086191 898483482 986041931 116010610 586469622 733432149 980926017 440027187 863079765 797296133 940907955 553971004 863626956 165171647 461137480 937669422 966352458 149262051 943505143 201509123 544274327 804370496 919580152 12515264 907022999 427717819 714675878 150154403 707910796 591234164 881678808 136773272 579426930 425857298 520442676 403796019 762326716 136156640 848567962 879497013 912970945 938099848 944211132 814695278 853127714 6147392 790147890 562870454 800364637 497411989 971503954 69652831 664111895 609831655 714181145 147002778 554115057 164545674 408706463 794103712 849943898 1 525421029 646374738 986074471 406264474 838840005 336409352 873284398 572341737 981922813 552171175 743939244 472893979 731155960 997527405 998931214 65503120 890226620 658358124 745826264 574119018 768225845 239229041 752258551 116239845 296132047 258431196 296762548 658813385 705652305 294853735 888287247 61608395 380129789 456945473 779542595 104222857 399588603 326655092 585474535 173058558 963190815 608123666 715949444 137681231 682395528 649939791 817556212 913364441 931651672 62086978 393773986 535746782 658556986 111633698 781417449 122393124 922950750 266352174 984633160 758824883 937813750 569833490 857657195 701531778 722287832 659014903 811063133 577550727 866442059 363004935 520280410 847306188 849651927 188439398 515762642 814696499 942398670 957945998 963412428 350078146 424756649 3041791 92368787 236599536 848455397 728238711 757710033 663725856 912986370 799689449 979453933 949948776 992520845 480075720 645150474 635190407 725787313 524196524 629230495 387668547 606847480 948904699 971622541 477805604 607170694 956140867 986277175 521911670 822081973 557681754 677822584 311182118 537151604 193239328 476927913 913125453 936907796 994493562 998408473 574672513 948641980 666167387 830430037 633149362 958294457 521681243 690226810 109416467 324126132 733172114 978957667 954574152 998345195 167034214 799999112 640487060 704731470 757291118 902918953 145082104 313224321 953083010 986363130 947697666 948662127 474890812 822113145 962881383 979109545 418899329 419137038 301340578 773898068 357124865 436987109 281262104 932502560 951352339 960091196 538890817 909219751 596139395 797529774 730706319 756184192 972009677 989787079 41237615 50393818 222580745 573134305 359424123 451856370 149070564 775733668 425633259 677047896 248605253 293328288 411771202 742808687 23310672 993516684 394807639 644279085 556343776 890095085 637102629 793786894 725581855 890196060 551280653 957020867 506220392 938523541 24451646 926197872 359375622 889654831 77486968 356148842 515631854 797964933 308918053 970319401 972614189 998011230 269281014 971319304 925432060 980843452 523073574 881540938 965888860 981859777 582652040 878076450 952520824 988151374 620002743 730558728 168768605 787838500 288989002 877295635 849582947 935097506 687878116 846208848 557962978 686287004 789512644 867975524 643161851 953957616 662753268 818135774 746373920 819070667 942963324 996063177 571645780 961930347 324532560 599042309 76985261 925191687 32005530 105965049 601578818 622275736 673063306 715749962 822006783 916998877 909555890 919295606 490885489 901365704 512407501 990020146 438430768 927305521 546241811 691011629 271911341 788959922 532030861 848455294 248097607 930950836 422673993 985338716 951256859 985768563 62615845 304150367 515019632 678541316 788282252 981756258 454628771 676518741 566660704 907680846 793476613 975168317 443612531 936411517 887660240 922340429 386655380 680184430 301205488 576974303 7360682 459827171 377227038 438499734 265292184 482762564 244399084 637593383 737129352 888550016 245330040 762628976 891569178 922618587 562586156 903551304 895168713 982884928 778489929 998814243 153165762 416531710 831190187 865818297 843374608 972405615 482698005 956161170 528027772 570531937 130571707 256093612 848030423 871405622 746095991 957768136 852574771 890979604 918072357 983828679 417969356 856338096 897668738 926052841 40206820 777875909 880296757 969483272 765108855 977415007 532102618 580181161 563923257 900637674 793727281 913212368 551299436 645533796 581096618 904384603 86862602 842413995 461690547 758092306 703378275 795776038 997922752 999612155 26185092 293766525 628206159 901283131 809248777 931163932 809352018 913312634 417928362 966515198 946545782 972649161 322519627 519316131 935298775 958989004 911797690 980937428 537907845 969760065 707223932 909819124 797003737 937944520 773101011 800231995 565669175 940478189 766613151 839768132 40632514 417434277 926182902 942239541 347087654 652312955 644800548 725407774 826021413 996072737 666777421 970149326 443587208 723409829 731355402 747145033 109726133 648150375 268816849 433185939 65235347 600978417 628563538 895351851 323520045 722851846 296495275 439978590 316482389 621090144 844935154 861850187 308160324 882875241 460707557 871413881 86370818 292898472 707456375 798868547 422549961 971391605 811210841 991418398 762244140 982214013 793176273 851416441 357527762 967088219 898268171 921201644 817102886 982165743 22829257 480140552 146386218 565205962 810489143 970474859 966720494 991288722 448553060 863350322 777493849 934839084 823261586 895558157 13931749 553921029 925858512 953801020 688383130 760455783 261734735 739958251 109931666 688445024 943204307 950464870 134763596 826313386 120129650 475903612 141932460 487766781 289161783 446818374 467441334 926225606 496438655 534859641 616015420 857432495 478934440 848452475 325411301 520116399 691664534 747199234 370707832 943304495 765890502 869106775 963061958 967789998 365525144 590668587 70341016 991160844 145753064 989621767 432267625 940969156 427194381 493373903 23120621 997435160 512266922 967518306 878505496 973814079 344916533 937001477 550098984 933830953 783105971 866977114 724457241 745180301 961400512 992001235 632259995 888787528 217166075 264364036 739394595 919779160 498204615 763053797 230765456 442577366 874000444 943228794 840820785 846176571 807264949 809983142 13337184 842142707 459478805 735580310 1 410822202 858604800 893849713 486371996 825588062 440112893 597466944 747718633 979450005 790241261 845936258 663368662 839095503 771779058 790193002 669713387 933491050 403643578 540043830 385187099 746250946 612733751 945718453 101628191 454577886 224065599 362984911 1 39908799 383017771 619201206 186756367 674634325 439414087 893076134 201171794 314377083 255722972 909307340 999009782 999728844 374588995 621749448 453303086 797920313 142136694 303001696 960748355 961232460 481342616 925316038 268348495 493663396 590790253 993573731 253050682 253825209 144192067 530701327 55141583 762856145 926459788 954043693 217514302 646966483 1 297772050 950675271 993733474 342606413 563543068 114620236 438531953 360786730 613149745 866836832 892776689 661422237 982241606 739015832 962562497 909241533 944827215 105614198 484395678 833659729 982552573 722686767 948282306 472072357 653015226 272873614 580963012 288160305 795710617 754377250 818792992 138610988 914940963 107834412 268914103 789943830 984131186 240753651 990280342 548488638 763421527 659474765 905507952 675149031 925184061 728151502 834343552 291867437 746968809 161067181 831423428 70686364 102808799 673215908 772516102 434613425 719203775 55095093 539044518 832539493 880878152 286781212 401250400 237542178 673764928 126772381 886194416 966256831 977054783 123923408 986017221 428101901 824237107 883179400 923723726 170297556 973277408 508400236 887054639 958571227 964222305 340203934 460538159 783074037 862380948 231311382 637845970 880551345 983887667 555187434 565483720 565442038 953003495 854358292 919464118 28765941 630351123 905254818 986764421 113725114 649015218 379373121 861024003 732228444 896117985 548936662 646264351 398563051 673890469 144181407 503897239 100418102 512764752 349415790 671831330 415756230 501994227 797251852 989844945 878430142 904518048 252861755 336799660 418644401 549266162 286284876 461477494 681815144 959130525 307377440 787855551 141867830 785848202 304655837 436118388 160476526 644317622 72375058 208628722 403382723 836242018 601038605 909257126 873898445 905479353 673203853 676969880 52846336 560825738 484329687 752570907 885601778 967437955 479668079 988445404 394855802 716996515 248215747 371099350 500328362 631187428 276626787 293474381 115567611 349112219 530700316 798416592 156897006 546945522 572061253 786692981 415331460 548960903 735176129 770569770 35220785 799092607 717898405 942106297 1 935483029 756892893 758950249 594193334 856826200 450723565 854617088 618161036 963984679 936094212 964562139 230028148 239426585 58643285 933707888 742377032 794188371 255645133 494885573 159768086 411800570 893980518 985281929 945147256 980323955 74682370 974767283 384023191 680072753 65767548 512687920 695909876 986556942 4002332 546531713 674801194 994323448 442541158 857111624 882151773 927170434 310395132 867445319 626757149 988171892 475077180 710002437 374465556 813590027 922769589 928602536 719138604 954188261 853794703 990735305 172995542 214824155 302305757 906719693 972269867 986706912 305176617 672269574 383072667 611731539 386541476 437840171 293322778 522942154 688604467 693732357 423001193 429962399 480545657 873732059 503532228 598827174 635913417 998890864 339885694 454548162 913041255 951824602 405370174 528474388 206984901 354314088 202426491 625683949 185125551 342212142 161607746 289506185 332410470 718763231 188289243 464689977 975418559 990193894 312977050 361246260 555005787 667017924 119332375 867691514 622498121 894362253 791227014 956517926 946766356 957852914 315330793 902365345 142958212 880337496 572685578 979981124 421100419 472587725 841121581 929211940 422224749 658484090 893760772 909212105 201519993 256516995 605802220 636389707 365533889 965865497 454321968 988149395 300851272 897635656 676299 416636583 375824009 962119872 331225453 884230143 276058579 994337045 94726477 924106068 1 981861338 526568774 711402376 368214383 728385277 262865627 271107956 492760701 605560260 394507587 892094807 908462618 926676042 708390506 890258755 426064491 954606512 63186203 356557624 754720773 980746951 313764805 733840276 284044144 919889818 847090833 895779616 532885766 918019133 557440745 886999980 680252546 738845875 18778668 53306774 794923603 999321393 872596132 911594180 471931962 870680281 569839762 960305953 1 502171505 680609035 719974993 354908531 728164311 861878939 891759481 670810648 748885989 786186233 926391948 287100546 380534304 232183840 917328195 323787531 545819075 336333283 529189919 284466860 972455244 654286658 664721570 910274213 989066398 718548864 731387389 114055123 268574521 833057790 849387926 877877289 976861509 781180171 985729261 563007793 844641297 182344815 712526950 847701738 993928513 948531016 992971541 431842513 645125037 381680836 705075232 91330972 194843971 299644988 391115480 857803283 983703718 392118773 683085769 319492855 991743093 793186429 835732917 803999930 818528450 239398416 621635165 129032695 249538567 895574062 902726343 915511361 922590796 318350163 447729189 230140678 714105882 206258885 362879517 164488350 892001372 107372023 497558914 128000801 708550853 143887902 901414395 573337616 967336406 473822172 716087762 766975841 919045818 683993254 814917795 865103185 972927819 894051884 929620677 895091897 952619612 606021914 912650723 951150252 966980594 363051970 873216295 711510154 778106139 695427574 833274685 814475012 916942262 954347344 959414344 349730657 411936110 899374481 948659629 900385712 956513746 451323595 949293243 769195215 951508035 635263608 917997567 275211785 503800231 131390537 950339006 292453879 597517405 799915722 921806996 702842055 896136574 864307350 940510287 378868248 384964364 839001909 882206848 416911823 991011953 907319183 972888544 638881754 859225728 185805411 191620128 80068895 280430163 245520710 298925101 30616768 125861060 144550600 703015929 428106464 943949361 750020543 872149786 650266819 787691276 639558677 640120970 665377973 791339498 453663541 786019250 756269702 983756090 509461614 605408996 572973491 803270761 797681678 924452275 404482636 719485745 594502484 966106522 468005385 583029051 494925150 950818472 115029880 589036219 862758521 928236782 1 875906907 289526897 374968674 84066661 962453585 277191201 919096621 418764321 854128821 682504237 964712961 419112566 946612378 433084137 835421156 579755743 920077419 630843726 671794607 931045528 945642501 47917961 522496645 595728161 998173370 153556158 796243829 919732841 961279196 559189912 649104401 223448288 308641585 122920618 158892278 804623639 954055117 332744136 499408422 46996856 776732808 681405819 736348744 777527223 962188888 419672090 973371911 378498305 988260470 849805779 872022591 931099486 941211983 284262049 963103155 793754270 865258786 937099783 939796169 156633059 717939545 912655852 960127519 818681994 838519738 772063127 859900464 101556319 583773272 798583823 862655096 871790223 920069906 751825948 925330486 869416844 928043750 254297069 790683622 729230430 923287120 48692327 174421714 309660252 589129287 157875880 522342236 809288568 946576407 957164552 989296091 662842325 733943590 722525220 948021019 155824418 404882590 337030706 965384454 981634696 996654100 965692518 973498708 101356068 746329050 415933804 496909941 271596506 843513219 674238351 972773183 933001871 990070243 904051030 953178410 760526242 961509801 6293265 718593078 374638451 728401235 329834220 711710349 625187564 748726486 548650920 730709261 196144601 941634572 226627044 718215370 713056201 990905601 2994712 676538294 73201218 489941004 81788946 257688602 649627610 667936509 919086274 919164935 551015780 769725108 317854462 532824166 822024829 931125661 768787756 885656614 36641178 623742163 655501675 713213051 284021916 994785376 307045649 806246471 78634894 100742759 411470745 869370244 806024221 907803022 714568394 928781039 840538762 915333284 592393981 806605074 341906235 999113535 735608267 946348139 338253204 924331249 876237826 897321360 54839393 643934253 857486411 867181377 842102289 902188598 514749185 583039852 778084726 868716350 174675852 396135090 81132495 202447896 966481536 992361784 758003592 996478551 602487725 854457287 94017884 486484731 514773588 717650365 34709077 546967384 516620568 623178373 849711390 938755997 990149320 990258070 950268953 979065175 87377971 705144355 14943438 307054307 916625973 955217968 920198219 991758080 673696600 730792688 660682747 929332566 976205492 991047506 758260064 854865115 345667063 388706103 812828617 946619291 600364691 812109915 874710836 988525514 907254818 937187056 226074784 436836112 116804604 797087242 952475362 958427260 395327602 781231910 462948999 515738669 649108756 875201639 472576895 910027724 314319509 833560124 139083907 471388557 878794571 935128299 168836008 499362093 35025722 880046861 350349897 557470147 653308927 929864580 228530464 274545778 938524181 939257122 91621235 917188280 643728806 960046833 488861686 777250330 657568984 928584757 715447222 774506259 389386875 622856057 531973343 872861593 807543181 828667895 116658863 748168086 283720393 917337914 865850858 981605057 746017022 988156405 761121738 929031674 807049755 906840422 520333189 664113232 43456210 979753314 21787293 122610740 390441177 985090933 853446481 881961052 47365936 149594352 790135359 798680911 746900990 824896301 135885759 617260648 531501565 535913805 496575459 775630929 935012176 970096204 410220353 989328701 997532186 998580608 84794943 105510974 423575802 841516157 115858012 349534133 430738279 921013028 851723450 947180602 477087236 729932367 2029623 637960527 229594148 348271944 676712682 998642929 365914671 501832993 540516835 622317373 350335360 661101617 640446752 798865335 736629165 937286889 416103680 680492697 59077271 957931239 514240838 521456341 126566487 283110981 375245473 853575633 977616247 987277054 983660686 995903912 362393976 803042472 546854477 666515726 494970454 707223930 692319071 860281278 858510491 873616046 54814204 869516268 239269416 559772802 764491502 837850916 377211575 806548457 791984463 940472647 432291620 856664944 546992656 868940522 620043910 988663919 600161093 737972148 85855014 910502634 816648782 979339259 963372368 964070814 727059128 818753234 848351205 957487128 302284355 748331078 866907187 869154421 826641080 898003420 100035597 875061088 165885620 192077163 589092877 693481467 634680752 758571106 552864033 794907282 322690964 899804821 810514264 860824360 2411900 50419570 446946882 714728750 558802751 919681603 582131134 878633490 781537494 814903246 390455077 765548758 640118983 788455787 638256731 857416265 315304448 789165547 42812533 665435602 943304317 969250241 904419863 938052139 305443345 467212821 482915825 857825839 268516927 714877953 862042299 920140396 241709300 913356969 404903750 415104727 640681827 692520387 961586007 974205166 531688088 642122554 184542917 337057393 126610266 552494480 821697227 928769427 568758651 904407937 998547587 999159097 214715350 594392743 531136048 606299258 486074800 730089836 389410824 523603989 294169268 359500876 570104765 717870970 397986334 891968587 412374552 853258713 272660031 934362807 242753546 552633604 125384007 158227999 547807775 841904397 490690656 759349558 942644738 991517256 73149801 903061449 841408546 944510502 104372257 976604135 635135506 703961373 860389303 922982714 326929796 937843938 872804171 876829475 739824844 998218523 295149167 476661814 71902567 91503708 740590575 825364260 805198574 897983804 774206165 818917534 628221174 681002829 139464222 434253088 566133193 584734304 662810342 975827075 725611986 869547610 363638866 805139837 410848889 636176068 408432782 843686135 643245968 735261568 220301023 821965266 879486738 922420010 677966524 948811831 63108108 348772595 401043694 966333672 506381511 874623612 937610418 996382175 426668210 462169732 426134119 708188679 531947451 908731884 707210167 911892729 183940926 623858730 684487307 894816376 902651187 964061994 842555615 879169535 345303714 708069991 726288252 776520216 880115656 886808358 840582950 860413447 39331684 286026854 237769666 585801867 515510485 767252289 857880788 878690416 136807866 884155037 217669034 273980754 1708636 676294765 519168912 820080027 948719893 970464075 439359909 637491763 410497728 736766801 475400733 898155346 817755216 821062093 386782274 587071236 416804842 988413908 427165676 656635027 311779220 722508588 515567318 880298405 83434161 811860469 235415736 974459888 351992346 456577397 209247355 387341765 16696923 293735839 125920550 587800534 715162778 794685651 410798153 411877238 623697838 994411705 72227498 879793189 421248918 593372861 120865834 220152668 123619831 312847671 334922341 530458457 496226103 947013191 287872927 718421061 586807262 843798355 113819064 138522647 301170633 958504553 691491061 926927396 740520233 748496256 279309107 329211160 913916779 932055839 86344096 541374994 778017950 793757056 746133734 933026367 871262689 877011588 840327641 884650910 390670509 659072812 737739309 946067389 89590227 335770889 213541002 648937445 809940736 845753275 669476388 979256383 865171461 967709829 499167707 992331755 975495120 999154223 508019979 565742686 839039183 865923443 388659624 714727328 632850603 916029997 967569362 969174202 757858876 780715571 738345863 951321456 350974072 953047358 23791970 440097959 93592344 625544456 857617751 938899974 791081318 867645071 109688453 200436151 14028045 136004151 231486751 911490303 747887859 845792138 507004153 836517175 389119049 817888492 207057264 475125252 597449195 739384303 652212593 702854735 543571446 885209900 231000161 304040890 361374797 775827523 656037490 940301271 5465809 607753544 667612948 973708754 574055263 991932327 734684458 947845547 120628892 966984729 453327602 860251444 840630557 925550802 204985759 482155553 702483899 867991481 797898582 801838960 622250646 631141171 657616652 784305007 168778593 462914600 554276273 691247645 913013729 957661453 244619060 429889354 279984822 567173347 727471146 793842993 102785906 198135028 169837720 718629022 969101853 970946068 416983745 740126767 700306675 714314815 1 499815239 129940232 880586410 113108415 579311905 529330598 555814881 344520990 960194546 905112794 975983794 724979766 727662708 940524329 988312336 228299671 878063490 447008400 532959686 686308551 756458664 228579460 592561485 411460400 944722697 308164196 533917342 297747251 350085431 771895784 917302426 964380626 977365688 965830252 981929716 977761297 990574048 21432146 704277039 484675491 671573259 609339123 892488263 749064847 851544165 977449343 989307520 414261266 668121652 244608914 858039356 582412637 809112408 107249168 953559412 763582839 936206781 246045839 463192064 173428416 701890499 830126085 897718183 990016429 992690788 636644433 849541317 298188552 583422852 224270022 572713220 324625780 475168585 621452027 775773770 550467505 875935438 432134838 633245254 933881480 999848573 512228410 593367539 421006359 924539664 554236957 741243126 416888246 842511743 504501770 522330857 134510625 694623691 731858230 982842178 254160368 332445527 826428089 987953745 188308171 405787066 432554694 795920094 534753965 654752344 746882316 987953502 263651235 935076158 169825282 898083111 351814347 821663275 381228012 775796415 771312184 852103999 577810457 849033498 277150349 411097685 215439970 960158576 71757581 394807139 592579945 900727863 55592554 702931321 162062551 713319459 891428066 989846217 959739714 993197583 372068992 759453118 338295281 382404496 32149503 224960072 67774263 354928582 825451749 898452772 851034975 867953403 947747770 983644401 786051218 841740482 810842948 841936776 719077241 813638479 360292281 535511570 16189926 74652387 41847354 62021446 668302035 788317171 289278790 763317297 232219241 322467132 305382995 580222512 41970101 234440762 1 502221896 719942308 951382156 575404325 712287877 110794720 671884524 186375902 552148314 382846969 458736485 709617657 722389920 848596290 886108633 580640142 976911966 252001658 598867328 15104515 471814613 228887166 364346673 992903663 996996845 489591155 615086502 78460871 532322609 877281005 939722054 653965599 682992654 549844016 759354515 785429665 984166684 117302871 216099142 402323046 797321775 427649943 653710946 638370824 760323395 21180663 368395522 208136822 291513835 950276959 970401294 929725089 997719163 502549557 529243096 718934448 785727045 408629777 713634422 652266931 984016156 131818162 867193971 593378422 916033937 774088399 982225312 329063224 498730172 635235659 825003741 473187386 890078888 40318907 247207259 929983498 980526601 27758733 768726751 294865351 706327657 754246073 934323058 311988602 968685432 784265252 956209948 561499828 872035105 850722287 963690742 179439558 824801156 532362047 548756225 237655874 437685869 96426199 373371860 602390589 693509454 222384834 586426213 151163881 238329528 853967007 958509591 838899701 963509710 777650388 834504255 952757731 966733998 898241228 947171456 118445376 364947106 326507758 423233465 252291848 760255783 597684276 754397716 439524606 851989824 573904317 601919235 375230143 396760520 828361207 833143727 94381769 546509075 191517967 841107036 882397548 886197265 787721041 932929026 432177908 649822174 984975448 999598425 910805758 928055378 28804329 353592504 509495839 909949516 830883408 904922712 893339534 934587736 64743756 820174801 69416083 877524296 501922066 677003411 455499889 862548279 362257374 886070880 856197510 885801999 957731983 972584779 479913717 935301056 30851941 565445496 566714841 890316958 257748939 682288710 73064885 268480986 134971506 448070998 564550047 915385452 133938122 332967167 492804371 623399042 306230258 765285407 390913988 898892721 71253250 965032571 497407657 648414214 37456040 39071018 404951995 975814120 714767281 819188360 349143038 752951481 258021257 685091425 70017033 607863652 882539904 933629352 781935276 893461666 512249232 651397600 196136581 404152335 751392101 821277776 470788669 515209986 16179517 653476276 194453225 304304115 391778548 862780731 1 611005644 228578814 822060235 670378192 879183424 274501875 443979663 140782647 978117653 159046034 331339979 222954193 224890503 236136922 965397988 148428845 933279320 327026673 469618474 762525620 790016384 179812265 392012580 917424349 958094949 427874059 790255367 39657472 715435509 966329147 976738264 241594041 953177096 959785231 971966003 233324703 782723923 704145844 892728425 167608505 862297802 32436957 950422606 593626630 944531201 78971979 780929567 430065180 729096637 950609129 968484739 545846691 903986422 288321370 949929753 914213149 977879147 490451766 674552723 359342166 682904437 409111508 985322391 626018675 984810676 46646144 662747432 453084033 953254771 934815945 963957549 468058990 484967324 131766102 667652076 935711230 972081345 80949212 901074824 892847331 914022745 92203225 941183518 176518833 883651959 624037582 928914188 115618043 780143847 490337217 687773308 410117872 450472415 612192664 873833578 1 274174124 961583862 991506436 13375031 783210104 521990785 941191140 495400345 708396031 799485775 957804526 703301983 709204637 324187932 367215357 778716948 935159058 440691266 741613927 198897935 838452923 24347065 522185066 816634095 826855783 988155262 994347890 888835979 922787961 607887229 928800756 485728239 697779734 530429989 785940417 667688899 913378450 286021169 630965130 729824536 807496371 892183623 921866084 598919746 928679389 58360207 383267343 78249038 352144950 337936607 386047278 751213610 952189717 959064599 959124947 442622086 529522072 973552227 996970327 402933222 767380395 337319248 821687570 368415259 510571503 848231895 990106549 666421166 975607612 800664047 881628575 689382441 914026503 132835368 396695005 752341882 855151203 153179745 731614121 969249484 995165234 161521485 728711231 150561461 530166130 370438961 779332479 294465563 669563771 337799887 451781807 532435846 768574708 454773399 818033554 563504859 966341064 376533684 903267425 585964844 896869992 559408749 617125587 460334423 963818689 347255226 637138008 647328077 860261354 107832941 671636690 995436185 999889494 352241603 910129627 808036095 868989694 896213 21361121 343594819 593454189 664860768 908248732 168247636 980527874 989904284 998131984 941543022 998470284 41783724 762181506 559959230 904835594 777142996 872718767 382236575 445943054 696907509 755560656 184929538 820001291 867027746 963839728 321065605 882662461 832079454 906564916 885132742 896428551 256149987 995794463 496397077 712358320 474766345 973615971 667313735 767162837 780802111 932242296 410118643 461690496 410183345 934414246 900283326 986647896 955897474 974365440 274881308 728457136 971826393 975738783 634670096 846167110 483778337 784434179 582252672 985912057 159505096 788602931 389658139 966054997 495164756 572110751 78220771 772220559 170444186 591882505 707091356 778004975 864116168 977762132 441313414 681870090 874007967 912765782 155459736 849904251 564920498 995463403 721076183 747856322 344054299 513259756 901146625 979484718 915576011 982326318 768879477 880812279 159628964 987542745 927087539 946762250 534109546 906554716 699902419 812699777 349498412 390484987 759318491 945379560 774055117 990406232 775854836 827503798 242003683 599375878 30610695 794017189 702534507 836167028 896741338 985590422 662891362 899438576 149338288 209165489 613085420 997769491 461561999 564591215 910696070 967898168 533615318 817909299 423577334 919759894 307221696 593023702 633134363 961312714 613661631 801194098 797323470 980717561 34715462 187437482 85256260 86691956 134290148 313514225 144186076 992637093 332200976 460009636 333489932 497404379 940727758 995557347 238167205 517265981 952204344 975414557 55280408 859161123 141507902 274567073 882972862 930946484 637672834 659662466 36866505 220134289 405908538 518963759 870704274 899869617 870116795 994347648 339519005 394211369 881273613 940276450 731187210 973793194 495907590 712740156 30882424 88347154 704684194 873671682 717160752 873627350 969837938 974109121 883408401 981670832 93359387 588657306 882727912 922705131 609710328 883867542 619993029 816012186 631931342 966046150 424358236 824728116 576724236 912623242 369489977 573837256 649268948 693998017 905843859 948588230 772741610 967255568 763862786 887304486 85696464 392382542 957002848 985473821 587224039 614990433 189215715 503664528 979879799 997254780 633125310 914575372 355062167 622316004 215761333 432335492 677579659 706436731 89954889 211573229 358772222 649818332 1 36469788 846023964 996171304 83285357 356407087 311702841 848777707 157430337 405601531 452389524 912126018 863462242 939124569 177218506 382035236 392132027 949560443 839556785 968219146 426166468 983972194 49198951 84067553 1 307949669 239819487 259521707 365664431 565580050 777982038 888925968 960865420 977621028 507798481 766024344 947839681 972343311 200950562 699951249 138094580 806511374 364408124 524798255 136429242 737012337 305870783 352702956 369764510 836320894 787584239 838922208 339200930 838896294 446695484 623256135 941020532 947639918 579583904 733036126 700686180 779593649 93696927 421023037 327924085 361494566 927676439 943061670 517266545 791392970 910186504 973119510 311644330 502214488 417456357 730599238 492538291 718965205 788350133 866893313 108189150 924869838 122158873 795727361 779607385 978656486 630679291 640577861 757154109 789242809 333537306 717168640 259554274 805422620 989232207 996899046 472153631 498264488 957156567 963529281 236478979 986830396 65897256 77319902 439179755 657091778 588808444 644027533 981797846 990972497 118850316 308747692 640557772 849140892 307794086 885719185 427234240 984735171 594867014 903106971 241593935 321884654 930708297 982675127 671483105 843092269 973815555 986413681 616167932 859860789 847716923 983368838 370773505 436136904 853451993 860834446 419895767 924959104 962412488 972626562 25508528 389763578 642580517 934048402 739820860 916676277 747062060 980939965 400973144 758742675 321607997 461299689 246563130 413493210 457435471 599104833 503421824 569027276 487104084 936284081 564051609 960315095 545621655 656172002 291023487 891401923 697037111 760876885 791481460 875715644 589679264 666970722 805483621 912608300 147542173 965503707 294666501 798882530 395971920 406072893 206640211 972333960 490323010 849199464 530738315 555991120 939539145 941156867 677824756 910427649 237768282 879653113 805534313 959341335 647959035 926448175 484017525 744337909 39830850 623776703 349303091 368966391 97628679 159510368 461582907 659390252 196312150 248696449 424014555 611294632 518885553 652440683 989837240 993540353 655009877 662074513 904244876 966427797 521192906 869795203 281985260 561933715 709642572 975619941 573708909 934106325 316681776 801280831 690180873 929289586 848300155 854530526 999262923 999271809 907104829 997786595 301947737 307707584 949214051 960494916 578728435 833445849 647217200 769260207 982943674 987268888 486731117 546618468 659288811 691879227 832944050 971604416 985110927 991255237 477269419 853723328 58875337 987791426 233835955 583881373 199594295 470142090 196904821 612597376 605702056 758354338 740428990 896425487 939988829 941715715 558386534 921772399 565701290 796295147 43049140 286837121 360891687 817965108 163490172 586867521 893630575 993068790 656940794 731913513 961548232 994925829 558966996 939914287 388987774 602391454 949583267 963830973 417508430 525966541 515785796 937421422 402005752 754360273 878366264 962654065 343690943 958233736 76750429 281550058 59050608 92324707 442704584 816506792 24907171 443386053 668887541 937532208 701807343 731980813 829680349 845544429 613554388 663863235 886622026 958926174 553448050 606975315 888578138 999492526 358328794 851649626 402560988 564649343 922077258 943460292 939072365 966926738 849812642 953947893 73144787 773387936 481380705 935418757 966177254 987504768 118895423 918925722 943655905 983321062 265177049 813827796 780986811 806446549 509351285 900424091 194487915 645284091 492216512 783044782 891686146 916231783 693521665 961026454 791866659 905871816 856223019 937607193 217360329 424563476 257279496 316606661 207011991 691189983 982965190 993063596 376078102 477020368 261708413 790431175 768892641 970374259 630782798 965770689 506853985 736489708 128964978 969765971 932477873 957805378 74684126 309212130 370229910 720843914 175274655 752477109 855346434 926314379 84181814 154143279 546863376 710140293 277131165 574599271 637712720 889613836 556800042 862224438 936883363 997146642 754421942 808414067 937677567 998509343 441034276 884844131 494954245 561840991 29069971 950045472 787788151 913621422 763101891 801970639 759335350 762854513 264102857 844454311 201048714 968973797 793933092 979803174 633167214 922001847 157755933 664424276 253747650 979050052 325152889 833686170 397948890 604864688 57051435 558035748 1 46444906 953368652 983830737 821051791 870256776 81845187 944615293 314854895 776522439 715095579 727753680 999617947 999778332 153186627 557432535 535735046 953968782 1031766 306600714 890842743 901901108 776344220 938054565 74969703 532581823 91281082 554047139 608690355 864921435 445267958 609269248 165435805 389671301 843051508 964588549 8920345 770713493 236134633 240053187 41046682 976529603 182694417 416800942 220200607 534156950 186414765 769871206 481708322 654368672 318454879 467141743 138558549 213384108 322833877 538510109 816597352 847613813 1 312806920 95815370 745589234 141274827 562375066 224354983 244889075 512559885 794549929 576940922 764343464 195194826 601493821 889396309 970617194 349169068 947168017 590636 151517165 319149969 668016619 884431975 925046729 209878020 494357213 431723848 450558030 919557378 922043850 515261236 640385218 642249981 736236127 961930181 981961338 210279920 338749091 756229273 983095805 262065348 834831290 52576460 732069347 803225455 822150525 758148493 848192415 314946975 676350387 798215472 912298945 24675297 505886137 333943320 942553355 188651911 296455005 609226119 880388658 656344375 923808325 125097181 532597535 691310601 954284358 327643227 807971578 922615699 976259860 469288281 522864660 850515257 936199980 454581545 590349948 351532424 486418462 936046179 962949030 317341802 708911027 79323196 993190990 913304132 979287438 338452318 501201392 692544422 705222005 265047660 786518727 190319370 763671360 43302677 695184809 670759508 724328815 646379793 672884244 853357153 901070939 197922088 587679015 768361804 966165819 117464308 372275338 97970391 735976457 466188245 676474804 619533359 794506488 600523002 712849296 484321115 566732127 568277339 705866505 600831850 932405972 541916432 863782968 77743229 257401100 330516752 698662862 893312309 901542123 378678959 903322225 535000814 727381519 267793236 414299270 663380336 791474849 947166936 995205343 685461812 724659887 239642602 760585978 680202058 939087718 231749133 579742883 798642854 958708674 49270546 942843177 252801097 429932907 628064579 659868555 506463331 858695947 660085116 924903760 197096618 422187167 50260186 767705639 761788952 875586992 372575333 473531143 180584039 319453111 62777044 790029893 461326865 807452931 918695426 966657406 122913534 200368033 250899744 357448560 344740191 950371426 794890924 844365670 317367702 712660743 769677749 993857799 342546036 493169454 881652751 904618321 699311951 957276719 354880524 464025280 776107523 824394704 920887805 944451632 491566985 876824956 393741524 654466202 79474495 416309135 982126903 993049181 244950053 957436406 327330326 880546528 716638161 742268031 283435525 384247821 257466893 532151801 185403749 525103339 977107978 996570880 967348974 991513869 572169894 607932706 82118535 259071546 432332336 781512929 600501772 912067062 581863309 933539709 844514871 875164642 865910129 963328070 997235704 997562096 513590463 775247226 560441208 835903233 495543878 704195956 470728481 680425958 668797069 875572023 998388711 999177194 490676745 964896163 292372068 550537180 939108166 980993750 530096534 777918758 634919547 742199002 822512915 927041521 117211526 376872183 775578080 815599251 791101638 802933258 754082508 890184230 831209640 850916003 838398973 945395289 150472677 492469724 81828896 524742049 731362721 852783456 330003007 453496256 859722945 876612894 597244654 853794925 939488753 942666060 665714190 729521550 1 482974713 84001702 131203883 464716312 506304380 369681824 709416456 949832529 978657538 466030984 918705537 299388697 334635588 755046892 877520908 76161668 559533147 806014592 992379373 349694550 577851610 52177929 358679519 521126374 973121374 22093566 878955592 546326930 904614290 288769361 606215911 763407689 777046168 777722643 819998133 624211653 987465351 9227172 483278384 1 399464565 165330600 413091525 475450124 965242196 229519626 770080942 892810862 914503437 499503791 793912501 908118479 958795238 476008393 564390964 109762786 308618708 625962622 940664426 388203555 803090221 1 60994614 344087399 420634822 264615787 335171594 810143192 838003146 715046302 891592697 678724329 865619720 681235496 813504908 485446061 692281592 437684987 574585629 916691148 944455727 833239016 909396117 409396526 783771691 765915427 973243002 251870143 590987151 45176626 161324530 946946152 957612525 963701412 971973026 261934929 696859932 157181624 943135907 899811307 976698957 243228556 964313220 561684791 950654329 796034653 863086314 900046692 964140244 333194688 377507999 49435155 977785350 983237489 990991552 450365475 470028000 800329633 970025044 105982302 551179755 144059528 179210999 623988363 798164121 858527341 972902639 157186806 321607370 381117391 399661962 221017133 584498144 514779676 936865343 10253850 590833433 322424804 982125975 515004212 517684183 642767504 662141613 393815161 465429814 164375888 900109105 237995014 907034392 286250674 647163613 53724234 371391800 824810302 937732012 3693540 207099967 478170314 600215460 733747289 907014832 279619286 447102101 137176321 383711811 93505162 352408738 525252276 835154390 473776491 795604930 727196009 964235308 517629936 530050300 963786477 966080861 988474647 988909767 955265301 999388505 66272228 400567178 922442471 996041940 427761314 478841692 270284187 484789628 523860825 777470751 557345364 866503868 800828876 933064095 622947616 785423454 259646512 875336351 841389180 928542257 849153264 912566139 785073970 915753692 140711051 545794057 454865708 462111275 340946718 974090709 360141196 998009236 921188319 949902299 309857625 862013426 134786151 386807884 719154286 770976716 485097264 705774188 468370312 724054702 407986217 828155268 57109418 343647925 625639160 780777401 116835652 582421949 214529703 526475045 73386237 478756935 130955714 849291299 763329037 768817693 193717433 529845620 628990549 914183512 521276759 940283411 119846476 371190131 728748209 929864890 130878955 276355672 63316118 685302970 381325544 592993077 84333641 297142716 617882140 994082195 83303838 538491495 437326523 919157943 667446305 983269625 666775298 902000928 685068899 902921752 84449371 541564536 373634725 891386460 478701729 576768370 504914933 678438075 877254615 960171480 3095704 766500344 278277278 280041259 551089610 937641229 686682691 690725409 643007140 777323237 940106922 975252300 884423885 992558879 876517401 894775592 535413746 892003531 592648552 657705706 179126662 827070583 164297185 666025503 416477838 621652387 950959229 968304096 7362400 911874002 143942340 746654441 435753428 485929091 565904805 909612334 226020389 281205922 951918968 969951641 292501257 512189530 953118861 990709397 399558226 846914367 40378462 459278906 442999041 564266161 933602714 986081126 910948419 985580567 125382322 902046557 160843382 706420841 498775016 650134954 225427733 892874307 203904100 723157110 990711606 996558987 968596719 985973071 643080830 722092549 967907323 974087182 903002783 975045802 576291361 835881824 774319348 882878953 227529354 563774245 544686791 984295659 968865285 987218877 740480830 776839229 473734340 789909342 196161670 270927208 278098574 314368817 857995819 891671784 994215853 998941127 820143777 860014719 704105804 855869246 562913570 869325692 112268793 581490275 181282864 866382170 414669745 505003589 933589532 975408140 169648200 827342511 806724302 942467791 235322559 838515432 719890706 745514543 305213467 941162044 5281821 276354696 542585084 828879333 858892026 896455214 430771080 529320561 957830474 965106269 280759475 407419917 812078303 960348393 492010543 607713019 777172977 953338200 505863961 754535126 179566966 707805673 547423903 901005861 459323604 687791053 949493836 983017017 296544184 874431379 488413052 925590778 580409442 973689403 452196471 881594277 154149446 377996822 658471026 862052910 530137302 754665315 990947521 996532484 220987970 315898336 911223475 917770084 326164642 860082485 6890488 920345966 28563843 125797047 211969972 547670327 255069295 573837469 759445826 893176176 207093232 388595141 394010874 773993132 801169777 816825301 375924711 944879270 295597554 467770496 652531063 704745003 602599182 740119320 218340144 504683809 466900517 720142666 678618469 735901266 529223207 694690829 210430254 376793275 215135331 587377784 779503027 788425904 232937831 773643356 721887349 899504580 90137644 437192131 494949617 963483542 60228444 420279309 592508540 712689027 1 150941588 106878319 938553761 899279074 905336245 429948424 728577592 302571155 618447002 585897658 635882854 824243811 892697752 912117738 939658472 818173651 842320376 1 417085496 876554580 879359237 652047032 779127762 902221373 939118654 1 3673766 274368307 858963616 320679191 594920955 878243981 962979079 540781283 705479730 916897191 919067516 136236147 537361789 527890406 755897428 165884590 492547064 183932768 601695390 580361295 752623199 847824891 900961302 120644305 549046961 943151580 973841034 376316642 849919535 104426470 451510631 446963599 475560278 487519545 658033728 746652827 851840134 785479406 786295401 972191684 975738944 852535236 861876562 904770865 904909961 569790592 945649729 953539306 955433409 552525625 756436602 460313807 665413158 76769192 456853528 759465577 981223710 934849134 959840043 508439065 919981230 776650944 970865115 408061799 702202943 185882858 273806037 984983261 994801631 108019662 982479698 184929050 446916026 237974908 997494287 869473288 916950788 129752204 705610750 695650590 874977331 155373930 667669538 621358237 860692799 170085313 291426640 920052522 984342585 65652 177931628 631190206 671471568 347613282 703078849 191169445 995031246 925348105 941589887 948940427 974069193 467136096 797916963 122723517 316280552 859113541 949096449 736858906 873765232 84227914 872034286 874768582 969689325 14039664 613451114 247289022 279609959 13142460 891714432 24866775 133740123 570344789 852158564 1 288955483 946760829 958638992 155175149 247568814 658211737 665242841 704334939 969721915 304883177 497253150 191455330 467053012 322159159 577757169 444055535 680187561 556020893 746752745 400399735 721127396 190487622 857812935 922228203 986350208 844757925 963718335 566786166 623118059 31381029 45747408 963529533 992625704 22684267 721141383 101021735 629235549 560462902 641731810 533149590 962602744 172009032 838301043 5244488 342096193 986599512 992543775 77551126 246504897 431658722 687531961 789123840 919619252 29898012 230967897 547305692 659289877 692137043 728208718 132884384 670739953 897300507 899617374 643930554 758494489 444866888 826903259 300415746 968108869 461571642 744565353 337631557 421551998 355238651 641873077 371768969 537485089 679859142 883133761 158787841 393155415 571944835 978657880 156527518 304701772 535934739 764396710 849778481 887280983 868709020 961800636 69027296 412519583 867492952 990996101 391469944 992768387 826390708 977102617 737824994 961060218 320770287 494284544 818171443 942731912 1 313817981 348701934 911372818 143887027 846625986 371519196 758246558 705610750 820090799 598586457 947375342 992158661 999304324 633604994 951097279 671787373 950949510 418961783 543211275 187488465 811013574 433635318 541856761 219001910 906139207 709843684 827257532 439160290 794467788 897943404 966506142 355720282 886890486 960161547 980120420 343199566 617628104 378387190 893608412 442179617 880137818 807683727 868932105 400919486 973353052 734047738 814708166 266274265 430605546 1 801884576 939503561 976838023 713624290 765099102 560378841 624756447 913293809 957954326 847372441 967513537 256669740 742313279 103787634 425323664 608132420 938316553 122318076 329738906 74797848 974016301 222350396 804592619 433763097 621692514 34255084 206407461 745051559 981368126 596553644 916284954 809575269 879955519 819227521 836475804 116178196 325354207 528307688 847002384 798904817 861810749 97106902 905668504 529372921 614996634 324528237 508218939 242166185 871839577 34481704 401864038 541538905 999132919 851365609 973225046 722555554 796458916 249096577 728375407 873908479 974302893 66261576 356081945 50900690 61944758 683243809 992795693 493786431 936254898 452088187 918292728 115800698 550775955 167967693 378844662 831142555 940489817 751510103 921904666 344053334 584370479 14029916 469753523 960954759 977689247 919777088 956866734 883571437 939121119 345702804 555144719 65491665 748119434 445074741 471805562 245924114 440589892 1 188311731 469326014 702510471 319967449 692650366 796864600 923697178 608931482 784163481 983501080 995420376 81978727 187937619 83473439 443568087 611842172 636484763 959284671 992358354 810185446 831216081 923626873 941877768 674954758 945342385 964756575 968614510 728448200 824847477 739734905 910619699 554966165 727117959 500533002 701087522 71720632 777899431 804531073 894450423 395168191 436915024 769154361 942660576 974214114 985339191 239195868 909943649 71052137 565378833 818902420 887082982 255676821 299620616 166108970 744301019 576499373 627435207 242043876 841395889 146129770 746521319 34986068 780024297 956798712 989363750 589577243 765985175 824197381 833410830 870764670 943256962 882241562 983603189 944500552 986305747 502125193 766234027 363100333 506777773 877479889 995168640 504022145 990742088 986515160 993977812 527624194 591605917 812981998 845136161 431558393 950848832 378183689 764340087 205294000 613793572 647439850 887641382 300197858 309817623 32873458 352138294 610242658 730593035 562109717 884530814 876291526 896027878 343903325 635960413 556039891 672260331 63579436 150616647 415156356 477217157 463917569 637259809 270444371 275205568 761737858 906169444 302596454 721276393 225416375 317032326 159390766 332682822 893748471 950399693 27453875 98637748 816390 135314110 944440660 985783878 902654549 923164621 213809083 441378076 726589001 832726072 25824221 720897849 83760874 476212199 71251287 569440903 420738576 616261908 975260224 990968478 598842165 637188540 619428878 967105843 879296328 926807811 708338853 773231370 791674869 893760642 386504438 969236076 843615910 908828189 370673487 481625509 377228421 884439381 235967441 714128831 788355227 845291134 306795396 323882515 904984284 955617435 495798132 864438312 667401489 916522254 631858927 756965326 299571258 824829687 364992218 388410130 665349868 959393453 416771601 421541640 541629598 858405813 412799688 982247154 977201602 998184976 571123193 590841339 133454249 669768631 247112046 509811664 861211296 953528585 962392857 987797863 424860906 919610333 310745406 913014601 960452460 979475166 678804153 760480641 662797784 734335947 669541079 767920623 144634948 512608478 68137423 461463110 969814017 985312810 207491639 310629792 254663213 619441635 111531119 924672615 267640543 316340419 997460178 999611254 778395513 819945565 62843168 449180891 688697464 997766062 892446325 896545094 659469013 839390235 681999954 893613615 680660827 821435024 87309153 481318506 18490186 153182023 353934740 879775558 776014155 855985818 660012969 946182494 802527332 920377473 308722620 742402239 790582453 915565688 848247775 855301099 373798053 481904033 377143003 629676356 368945139 860338457 365540910 804885763 735464002 924171198 71972607 746416181 696539708 909461224 767852558 914164893 967195640 971258442 776494142 865034800 540308942 832144018 163743528 216588319 847447158 965670344 548595679 795262139 330021628 884013397 696723109 761132554 737787286 974889447 644751991 960409046 655178521 801362327 636241775 967022805 991371164 998307736 915459796 996883682 555535226 582667694 52291613 122690892 973447194 977100798 397330550 698710088 130464101 637550549 254319804 828157236 763998976 811112847 427809527 729243115 708031641 774653524 519757518 815541232 765791868 885395600 1 661331254 282174785 390030564 838188936 842531871 368065438 514632796 964588311 976665506 499291386 968508137 814196570 865550909 178133501 185265191 701160950 984327951 110642653 485555761 659640142 686367730 1321564 850839940 116676730 823893433 891547747 912637495 647935319 806388098 353472272 799441994 612363696 940232911 31525821 673825114 732898470 884205020 289901414 816022073 859482857 931618270 885478628 911004405 153022019 154639224 451507539 566970199 667042334 758937224 419153969 771941954 809363311 907972217 1 634738197 190680485 621627709 952335986 990107587 274407627 538591639 372893524 854406124 202907084 942891041 613490007 787634791 147037136 976739750 473250584 704795993 335379652 769067213 402548144 690009732 777597263 922509664 674091401 915580403 269802568 992398726 240388233 587812801 50184470 130542237 66991900 490884983 990288201 994845089 1875329 418957688 895423004 923155964 889742631 962506049 583150723 996876104 493123011 726661590 255209451 677343488 966718695 984421088 335388036 365914592 967951205 998898922 559300153 907334365 493364353 913213419 114733044 143715551 809915523 873954776 724122943 726201405 754050302 934314586 470561198 676155229 1 458780850 573244205 590390609 322540507 452754899 491116779 560863391 338717716 350577565 818459365 990946689 225642713 256946432 637284877 839317258 807825431 985672504 862297215 934666977 734501201 771106615 269101513 571281567 284287190 480825241 448065139 863844368 355734825 716926441 708237758 826223168 7450740 366562293 1 173131004 467060102 815707422 177106530 269578498 257307320 497104911 938741995 960317506 664624083 757555646 977294587 981066370 460011632 701314727 913792480 948821803 962988177 991603788 93736759 812308513 684824513 995503614 45400333 257158805 916082274 995873057 894547128 947916007 689047475 819176449 233638498 466187937 238955488 999589021 652223041 763826921 170599200 358803649 822681094 901388185 569877167 932517476 501055930 592051852 16636809 341072841 609822844 682196824 653658661 665034663 625441444 903031410 920870536 936954121 399260343 950520662 515166820 997236037 513551885 809290197 581181860 708410471 923093294 991155749 196735549 643191435 487836411 620314995 605681599 923985035 877413294 980662974 691007917 855014904 477266751 674114453 240995553 331838597 963766884 992801181 284198255 392514123 61542427 712820811 61922383 569832314 548339672 703914846 287435061 439654970 882612165 930663957 964986393 990920494 495096609 898051942 3571108 844421866 976105857 978166165 962715654 973394522 138337600 336028613 48695610 996625269 753286169 788829000 398984387 994030385 139792982 940520677 68377569 683541699 50463245 159795370 660000699 872086125 389051837 741207734 926663949 974249943 96851010 649048855 974764807 977626536 895337230 966363604 201505788 818543377 911598123 915241518 191948381 559244297 285731758 532113037 313735446 646334421 771528892 861442306 13392451 526675787 893696818 994020093 630868443 823239932 142111148 595995442 685512146 850449450 753131642 848155642 992782325 999231201 609228653 763080474 537776710 905787828 853041033 986339394 777558064 927900906 447662610 771616920 19622559 811522553 74476450 500109010 654316033 772096486 225543236 439313129 656050958 742836864 396822419 598233578 629316825 803489189 484668283 852083886 29108275 53897244 494919866 877569780 96614633 174806876 920197692 942325025 152346820 219976612 1 754188493 99329639 564956230 583600616 932388780 520591112 619419941 928912758 950723944 755515748 773619621 503749666 788441338 892790471 957355955 466927443 596345337 828385447 958405849 663827203 851551282 999078535 999284604 415192509 593274843 961910510 980678464 70220586 385926922 352702272 480188402 149909758 729243433 983837359 994537956 742385852 793346087 272901386 615695946 321908451 536984025 882119726 903892869 885627172 925239323 1 222879828 226764500 599911739 548710804 564390325 138275518 152477579 765847248 875625252 411581899 797173174 561182723 636065592 526582468 737751893 756411336 945231871 1 757130823 339010624 676398611 404047582 956746426 584782368 680328431 288062912 953151896 386688331 633957581 951868734 981692519 883565305 980194206 782021944 987752461 618740634 873469121 156548036 438547921 819536829 870994946 250538562 555396920 911934322 962044923 330261605 446258202 998469176 999537401 893587389 993212931 559406381 944766536 498836388 502922728 512843931 812374599 952577488 969732599 400324881 775725944 145452113 169374990 68014765 789585170 628383192 729920671 926979680 957020596 347858266 782296925 810164853 946135981 812494264 847430346 631156123 923323602 610538318 670125250 407992985 926589942 303393599 859135271 218317517 891928109 309003267 807341582 790823488 815008258 763294822 882335316 885327403 915517216 623328339 704898571 589883003 720723692 291440734 483910410 945591154 971199058 178556706 409328981 660915326 837717463 301319953 527025421 537773407 685722312 205754882 326528839 42631595 818643014 535216850 818491816 448280250 476589021 204052053 372549182 96882641 948575646 709255652 905837713 741019659 795330743 363159962 816293098 383063184 804589922 485517465 658112248 447869603 478774057 765737906 770227892 872786886 931276070 680469862 716465319 736823915 809360794 477035139 916420147 800685870 958059290 529059246 711204443 258274738 960461006 143951606 926400717 352881076 384465236 244246185 249807300 324435822 675131641 554001083 850059276 761646901 935005355 165423555 435251568 651182675 812967018 230615961 824764893 936463352 978700004 194935186 684116988 75830934 125366348 998220167 998385080 573086169 701524797 884483868 987539415 276259759 603953539 110719048 509012456 385172541 753617718 862529660 950747018 166192645 179464434 199578787 611773953 492402501 528421264 403301541 858504228 688592789 694768175 256614268 424310213 966960511 992669141 746523484 932958273 1 574892307 243960918 395273748 271663162 506396601 52519106 252049900 939252710 940946382 151652585 986363211 396877788 465133784 16846802 614844843 713687610 990652643 968076271 993930326 652832205 895172827 389676526 552724227 750125640 843015789 815076354 933045096 110296684 840670085 543730302 942715199 559267577 573426310 159666363 779873376 761592170 908643349 237712973 485846456 62563129 151774036 761759507 782747020 717051030 887936053 66525060 384284441 789139698 941913915 648484888 749401734 98254376 820292418 461815593 854700096 22198618 885843955 982850994 995521951 634051075 973510149 152932331 852086205 995667598 999231474 216450101 900724390 420269830 686065062 837730497 907807453 92168616 209749215 276429951 775406076 819908862 867004943 967172433 982778059 836039798 854637592 856953200 871010553 773722281 815639643 498393323 930714785 629827435 849704620 739406665 997695412 744323100 862081680 934214893 959938503 503316055 992476454 949675831 952153746 635275619 665963190 511799692 998219612 622633418 979513226 4336971 834552280 244251184 583789060 479050159 725478065 759918939 941027851 671090322 843651308 932346668 992188212 944909730 977985469 213986372 431932912 688756716 872576894 964996813 975536902 551363244 769928516 248841515 737555819 637634214 967835548 923720235 976347132 96313952 963483711 867403359 896732810 807283634 908080764 792632368 797519608 687506814 982860700 473755930 833246696 164075417 624793139 675220985 966090379 204330316 285314064 183244141 234350932 626187655 858317209 465318176 502348634 848389776 897188064 858851102 913092534 786719661 961660976 746015655 996855318 472037100 535875136 233898667 870208480 725641676 816012480 158289327 947059109 786047023 837658080 20379836 132351445 616457866 620840143 1 557313883 81712196 848858701 11016133 626141382 771660927 884290932 819461791 841931234 440044145 682622801 414940741 674591427 674088420 678732214 352903937 909638251 175179492 762618113 507441499 527003271 547788130 804154697 785676443 985442366 1052838 592174839 490834311 599665321 105356959 796516966 412335457 701914880 459823261 820938175 129421942 589933157 659115486 704340798 929776141 965584633 993535376 999964742 213432949 292240092 720312587 988461578 386268346 714967183 28467237 949174039 45629842 806284366 736864297 751505499 470245140 711186009 169704128 715487905 360014778 455710817 746880644 850741791 266265786 816681085 723375561 998209985 177999681 903450789 562238675 860338341 311554430 895456943 3416573 346596080 566503501 741682964 306559024 766134582 128550476 767646059 856414011 961638622 639440937 930346678 995376511 995957739 489804998 763498134 338840649 824270275 73332081 424495378 721171822 789049228 159326890 476299269 544946376 864405420 681330088 986334988 345395802 510108131 495948293 519751813 767251078 859381251 120658056 322925127 223915721 779899372 237892295 511408980 821530882 946492332 446068742 886133649 625988226 639439841 777212303 838179751 900165726 922623807 483657663 644980529 984532280 995162978 755133379 858355189 67995359 853436224 205334898 848871688 196705986 847633924 923265615 945074175 333671495 989957917 862886560 911882439 350494552 415819832 447305123 707789161 997230435 999337438 349538871 721279390 714245479 765155702 602372162 642552706 215641674 703789018 872433771 946540520 573484463 938044288 813918844 997113296 704333439 872018019 777227308 895696310 905758008 935238230 913843177 947550108 609524628 659861006 437371805 882125790 140967295 963707952 982078929 983072078 240716842 428058399 310820271 562440985 740935682 983829600 980193176 986398735 946836829 963471413 78124681 568680150 203477924 587119404 260022248 342143863 235343461 666285806 491461937 973327299 258146118 346325851 835117274 932520853 914380351 982934107 211178334 624957981 274511263 420533097 942743821 945911132 974093132 984004280 250082605 342824535 309387825 880602027 613442902 784151971 846102338 939668082 483558795 538189827 994052977 997263073 866440189 941024382 857184803 872978829 554755451 919205078 165502593 626150600 947525456 962297838 78819189 478797982 1955300 336031867 958734690 963407985 833288926 873720286 939019527 973408097 586349568 949059115 874950156 963086267 519295288 608405948 526829364 817593721 156046045 308765101 933838525 994659465 920164203 927391795 841827203 927392175 93114097 529780981 767832775 927717814 712568139 964723304 374289638 527124306 652478610 793457613 714832602 899068430 302829903 499439138 333423442 730705384 246858746 567350149 148673955 806753114 179159425 868219324 797973999 983073575 486386981 929130317 503309598 686325775 139911334 543523902 157871105 634562103 89416585 166897298 8128537 81640079 101337388 403002370 136914743 558011517 260012643 748529927 917189554 929773742 512621776 854073677 79816025 678502875 800287124 833264516 228720136 952990751 186929644 561796587 704329889 882676923 1 234144023 546745224 552364739 52684043 398631077 121837347 581778811 117567916 733697700 861546028 925634071 797270465 802363387 436916232 494856955 20284101 338897419 930040086 976252521 163127303 502515643 1 559312611 547093027 600125513 180878707 452801145 741208119 809298321 704909121 752081463 911573450 999633386 163388726 701542027 611658213 860386804 610589796 703966406 551021870 807809351 760454910 985090822 763978577 970097489 626537396 652443361 910475216 922825897 789558465 916999171 772461452 784633818 665897906 773056522 810371477 916055072 270349449 791515134 798316718 833957429 792471834 991187916 96585092 793601133 896841017 907707531 810503786 946167497 82754479 261301736 680007301 869811065 915540615 934371473 273279865 351218960 845515554 847393305 787524335 868694832