10000 7930
434518273 555987716 179504055 464180215 344958776 592444912 690914943 621784313 671337299 125823051 219639367 891841294 312429482 32290866 835015954 708838773 421226513 668304560 373387437 138232335 789305809 677169421 468667951 192487913 800514910 801026682 981728206 909621470 891837126 977912302 2402884 964271960 758928801 631087408 855825551 907532215 288620358 993996932 446430570 484093606 552071616 461303239 892025227 593638965 634727911 653299775 612245862 309639948 188461685 630890981 615329801 842361360 398803338 83102863 833588652 144627053 200721024 83423272 417520089 529720252 95342257 362248042 308951424 590381332 731824128 489496557 472469149 103322969 379710402 578307442 433082266 746150551 45453650 824331169 808228806 637202557 88573522 892885458 992905370 397332164 558167133 680171925 868469581 677533882 25941336 577061787 629905323 463561091 111793657 475840417 918661821 533009506 370323329 505196099 285040262 965796874 137844290 226233843 113462600 181141474 840928708 341164897 166626808 976050278 391800739 536056123 962007398 717161693 348812755 646124611 225097902 132155746 582601180 791622286 490948613 441061790 316211245 585001301 875167053 494047533 462961945 175789784 735577531 310331846 398846420 121508773 373853313 527164686 457278889 803302938 362566512 748213156 231604205 487118809 192234854 112480926 728682654 154664075 88761660 637513943 657655043 539292384 75006343 953617930 908021315 432974198 218440439 509742653 552741707 164131314 500344468 124284670 509969977 539024151 128143108 144860730 163012254 628648066 251946736 623048945 493198178 273982839 402599441 75930315 516881960 924282836 971766237 914709338 5968831 60945209 684642479 132296702 751001349 829974610 533544609 797958917 161580411 567647558 318489576 75728076 918436416 855023068 348853590 236373029 720158979 850910432 349006136 415207309 419280922 849088033 986011353 41948366 642507639 327956801 746498180 487290798 934418499 906784188 839758272 166991598 288118287 137019542 479534214 207137470 834912635 89271874 149632126 231286955 76732157 157686432 86400796 768192292 174034097 489680736 602976868 697337378 921147268 277493753 113311336 718249445 59457592 765803079 441152693 285308157 855646085 910390927 37219022 627533381 267980328 145574669 516813273 618302834 727612482 85017983 865931795 985586751 884744149 730451150 731901233 121213591 374005017 981485206 743947149 218181656 822349046 447618919 374396218 560611913 326746527 387743716 457352146 134159250 126888364 655658343 458087192 150539940 859387499 482146258 816090089 964300450 93021368 511076025 12768048 95635400 431018964 835670112 343252454 217614797 587162377 790823402 641572071 626950049 677844016 921630036 723128085 576743217 933962737 486409293 785074953 646680046 146658835 844160686 59217203 301349805 6596494 367724289 770494366 214557607 1855483 589372213 216434048 956228778 312362043 419618980 652389988 485683281 241217733 872882172 279235667 488341391 2658309 592804704 438122455 774162698 78705065 581092686 367326960 501379276 824933133 20719670 109684236 113449430 60044413 686711646 366464594 684494858 152421039 503415874 42588739 587413935 595371195 130198491 766794946 860459828 364510714 900900454 395302315 341198868 724481351 446789347 634507101 151450265 542778683 936165626 949311123 479286717 469226899 656536820 35821923 410929662 577683165 521833229 641324968 364091275 735389 516744021 657577323 395668100 946227413 730854786 240470012 727287979 127750950 822865361 226634732 597789207 983595031 32130207 69239051 320815370 89699447 308292052 615144850 977877984 812620958 145044845 969444615 774550693 873451809 868305162 159490417 408662180 561972502 947191676 600539531 507152300 113333833 314551252 557365248 226380274 543276963 514623710 616435202 839151878 753880754 741701443 952121353 988253141 927562704 608822954 105227361 333248409 835786858 447935464 51541304 710987228 240012052 770796122 582876040 498863660 865371401 610609298 933465365 621996925 404423530 348894454 449561114 938428412 752397344 63492266 869935426 386167214 505391357 89073264 906137005 149287103 547636084 986636484 698477273 371180750 468140496 206847589 420470453 704688561 298139024 321057118 423299961 159724021 925943508 516141794 578592138 156834681 581473648 694016929 658850300 792411067 211957576 343666663 578335247 107800536 427400696 309212863 903025785 369072682 527529112 863850546 675184391 781559796 385126326 381154344 185414622 301376474 519327204 888273775 398541439 616071964 828360264 5401486 869368933 996406939 616828031 701719932 961642266 228316565 479274368 521347153 940433923 405821584 986527209 343399271 44225966 889636299 408569688 645215361 226616655 162387220 367809934 750603731 971910322 623591981 856467842 349408445 207345031 858695437 485271967 786708266 758733342 438796952 20285368 70671581 891803548 581925690 802201984 151821455 343829944 130025314 66903582 324889816 987956129 803331419 180190113 509921960 644517378 769865642 442262354 526269924 460576573 364627568 401267530 616603250 958944896 241630261 284347222 456855708 945041653 95248862 694377121 514106898 108064858 380217206 901143166 102276686 931035365 53054680 497710156 595790038 326791945 501694479 985812919 315029199 82137082 541594557 643234276 279721054 196675380 483757620 108366997 199619867 194033791 779380717 549426610 347101806 439116633 729265286 602900929 183456891 444293115 524189026 975626835 203278098 393978306 260384253 50996152 342594778 309116525 795859340 429089726 696320669 947244903 48702545 562715075 774196720 885464364 426809112 137158051 829380495 644414875 50883552 635616757 433022547 269332866 2792416 395498767 3588273 894793800 515682109 974945262 567866728 509176184 570522364 778673284 30143611 508904369 806254543 970198957 496661001 900128232 639964766 792635168 889901866 856031742 192211867 80310245 296381452 332854129 619358113 888082562 493776780 623639581 523104745 850591720 404209925 214254604 580302230 860651561 223894837 982952511 711917546 962443847 958792022 628567656 801478412 267219080 155078740 969750724 749007803 770029775 925522891 955988842 113692758 214407048 185171709 268903275 916327753 393181535 660824265 843702513 571686054 969400818 95584626 26134067 272763097 508801349 369613828 214667060 211472114 412548478 647274253 810488795 475672988 935940232 581706413 236490007 68020942 713813042 689163057 406502595 405009224 500424393 430929249 510996922 884306777 270564169 722572011 96349351 1099219 211623583 796611853 264312272 679607885 265921984 746997126 634101898 664904201 763261467 453096338 893146558 389104207 782804310 585820617 103709780 406484092 251928164 533807565 271613103 202739673 533556714 673782716 805284781 206329060 856599884 775612305 988937065 822433243 931118604 743590080 407090475 502330086 576892305 295165930 108719145 391868799 103033941 89490641 354727123 772248936 486397300 569665477 308777639 867518654 716579089 720197120 759778799 874424360 958613521 61356630 368917669 775320356 408630531 369512455 864958299 403795538 811364058 470648509 966199724 986329735 272886113 782045396 633341314 579716752 499877134 458382862 790544049 540183436 703456771 494097941 213991059 94716471 309569386 706158355 398963741 536297235 227688874 876575783 344969824 895595682 284446788 665944540 92834323 965703610 872800165 770149115 127188776 901027122 353468818 693903789 24241918 144718880 728198294 92302637 193070091 460031679 932153919 419578776 474786207 302723394 61842939 149972582 831078289 962604740 279392839 231640966 356961047 498017023 544282859 819377162 5472104 839697861 388292169 517018773 7123257 506189681 270516174 142910263 217097331 794904719 812506808 78902738 274313316 396405637 931672781 610450122 934466303 965951280 981538022 656662645 932139376 487967911 928354102 300567936 854438219 179709652 714923123 9496384 528007704 859781897 362093552 312231624 279563498 910237829 18344826 533908872 70875682 92029741 547290497 815042366 604042127 244336976 169402574 977130224 658327861 211241785 258503343 776588057 364333690 812692190 864028655 162983342 698564287 549198616 196610247 55695722 474996553 943794633 557512062 162401760 566418176 791091793 250699800 613633231 716082697 263357635 129693701 468388374 201734330 592223121 178626684 462221633 977929014 439643585 469841976 99658157 558504303 397516828 636582535 520904552 724643349 158947869 883522745 455737991 75442317 216971621 666991216 742247552 299119104 509486980 762631002 901031314 357889241 700533676 459223215 566558139 982549004 445019439 550903804 71121738 746343334 452378147 109656389 649731754 342085040 169768518 991984456 303408966 702403529 226017141 155896102 461244525 951050047 903807097 927398328 552728977 416986394 408445691 769120883 416034706 201409101 735433197 971572358 92660722 507471807 211569928 365908612 272013464 458246118 151086109 508168630 374860560 152393497 153212474 274441007 792312289 702781384 713483139 923288614 383296487 42936814 96559460 676898254 50427233 196389521 222237941 501665996 784641484 236674796 425237319 795168970 961004263 963878140 105275156 23485632 432152701 927543542 425249758 417784644 726302123 597216147 594731498 621185922 867412102 329017363 796562088 637491855 400009685 812926539 719791171 56219893 720758521 232925470 799416259 317618565 736348309 993147236 280874738 211848155 30950980 187534690 462140746 574585784 864579203 975434688 256235013 526594998 486003088 963092427 359536451 319169815 739808036 225398631 548031219 162582742 406093772 611788657 601631533 20437920 214889275 803815435 338139278 672877915 161745787 462588677 818577117 973542912 516540869 573058400 182351859 801664264 467008652 866442555 773709004 956207197 642065644 958359356 260894849 125760453 154811875 192009920 429385067 97051076 393303287 103896153 369868339 551021648 796113448 670013246 359373661 434742330 260652139 672633641 976810494 598097727 457751194 911105212 838981040 981761112 619225556 863633774 505814718 93526840 511438356 302310090 38639875 62257563 336675943 590914071 566910270 272142777 87441882 834633510 311413311 406785882 878691632 793239269 813294224 106087275 860912641 705496639 274021490 528299955 825174827 717301416 192926880 344996667 391450079 249083942 337970358 735837171 954727550 127521253 565035965 706517277 585132715 29016382 307321958 705447015 32795443 34741495 686420234 285091388 766638374 549309422 65460901 875540073 108238630 876414014 536846284 985259372 958918491 738302569 704349824 558581604 574491763 209660836 414772485 201861639 894481009 231382611 754063464 603765956 956604117 171430880 251974758 212778283 39082658 367690246 26543982 480316698 516198784 284687811 408960429 227104671 452252787 268397868 280395226 935624133 826109256 222601058 622878501 859486717 824964279 478948247 852703591 355946862 243064432 184223506 582583295 424388029 47839253 821956105 94840989 253784846 253625519 371525616 156526713 785728074 961972869 794836117 459624423 266411418 597855269 478606747 209294061 488673839 321572359 835963006 71248114 633968038 518513923 944151435 642473085 512201931 572539918 476003602 787211466 909839073 894469283 273782220 81489685 504022425 308592214 998278494 961690632 183216663 89485899 992589040 626795458 752803530 184768107 530156710 651559408 421185189 534908517 117469973 98700367 724872095 92096647 321137452 593072875 147618707 281747921 849783527 675913551 105167268 842338532 722310681 817596920 777956549 291541478 733666527 523722917 278129311 934512928 113329905 536304827 708559855 383790261 860574292 250765522 41780087 531583987 225319308 337521271 314693725 257212787 868721064 812913542 966060518 131627429 77053434 757117478 603080058 775152755 608648749 644225976 724716637 346134749 257921922 48988623 833938547 337982845 796592316 908428868 266709008 204598773 214358482 568567537 406617989 214168893 215588955 354136242 986391062 433694230 302102731 26576144 313836077 257978059 664490036 854785775 217843804 993220347 22458321 582999372 157973970 778860534 182218837 949640846 533003325 954178002 133754737 504861066 341595917 986977918 450579789 325819526 666735727 56713210 420060948 868496448 994425306 257817976 882187377 63465745 592033336 921914842 718832106 153714854 430463004 982931864 695463678 970692232 785205089 639571670 824972962 281761822 58914470 155113107 63448685 291898171 538305987 544633495 129438991 240828860 296635986 834844132 123890721 893710198 567852963 654709762 809829376 679164898 469372112 524015936 33249839 223981480 54322571 887349181 178470033 728611961 864680718 43464848 916988401 315964786 104248288 250780014 213569949 444019812 788564696 843295806 19572195 527685279 450262612 264866542 807498645 789230065 916300306 185196729 607964988 623540459 513040156 312841418 724853047 256908799 69388907 274045240 714988404 872025976 392284584 716952835 701772838 559125612 400277267 630645658 421945745 444067264 505572625 384499369 222534488 535665610 461517822 669329758 704733199 132135611 638049519 929915356 708834205 636451744 670719294 272239010 992261957 82340536 472118071 573552847 708052842 900632017 446436612 359871588 948453918 779796414 563951952 111422485 641746499 73708903 938057360 308455938 220904764 592561392 382165109 598290949 221573816 936670129 126472794 673309442 166057439 753081632 290991227 406917322 438242881 740068727 748618406 968778760 521057512 382471591 197167828 238587980 746858305 641558165 571642313 246117063 627592766 8562058 287789145 934107331 28657297 247740554 964272972 246485223 51359229 449604828 64277991 140353909 455027295 152398594 13339609 731421310 910631 181385862 969618621 27684840 140090216 890717722 78179263 184650664 637430614 207704321 406203487 859656610 307972237 855421476 926895755 912989339 846023945 759768914 512851840 348800081 471522946 99442866 612160267 557084868 314856235 174239489 224298639 124572016 413878350 411825887 246892819 989324931 451050748 56244611 524205933 420548476 671015741 975413867 832011236 2058444 9904051 970256278 118883650 922704051 438915621 701676195 798348621 673955944 350475933 882172465 597019189 625085887 401280234 754682867 47062901 1044007 516987388 897492254 41161530 930619440 694809682 350131312 851418806 343327891 279386324 585183517 375353387 488737781 542486718 478615735 544293283 1218087 539124975 350872319 3593156 86679268 304824365 716553325 560767860 621261522 341373270 477079912 608156323 231770876 590785723 765775845 489712680 472462258 72269474 803682806 721205143 523470500 194524987 502788098 921942836 243485944 877612252 866747873 390834509 111846984 264455678 338547621 243455977 596853176 612599527 796493286 140978284 515570519 170839732 88592488 746824338 659484589 275468174 119914832 8369383 397367416 200763192 899784872 312376699 193421810 360943177 533417782 959330029 297820388 32503416 142151851 929950058 695256968 611269247 913223795 511257290 278115378 373516418 60316540 555390180 967204297 304691375 671579632 735564533 221490239 110737470 202079828 251423538 475959380 159308096 479907531 737810262 393576293 968156880 284403972 466561111 317299406 909543638 70120660 32326451 211566980 642599870 337114533 431874592 209287778 764947817 247917703 789512663 977609254 500765216 179066421 812078056 393473502 739166368 875927126 640205516 662066860 519182316 946853769 697789069 102336323 499206148 491075744 482274823 968140966 971283241 718270031 82669825 847496606 348678780 358146322 506020000 620121790 973121171 394382720 422904723 920098027 527505609 748028410 959168008 365330699 77643795 324827295 294351664 763636822 322317630 540364465 402279262 10335004 973274429 807984224 44811932 86466992 446097953 284744888 909257615 221531451 333775714 926602177 331390919 845790356 249680708 910229464 995997446 906180828 430712678 881988669 516891012 178182445 824167667 764473866 969548193 324184740 994740738 199605674 465311764 175868195 643851008 603293544 140872902 703046751 216911053 540880993 466735870 552948617 176437393 486126139 654964896 385317950 441639721 701124670 553354427 718680589 224472590 909975343 484925522 706047019 45284337 794963940 285272215 175385356 139400760 535524973 552077843 431408994 467337562 975587152 692503611 921151426 953965969 927452176 751566779 637846053 984218330 236612715 783771426 652968593 441572240 774968514 252244179 144143351 83268569 86193087 889757859 682487276 552835392 199021848 780841808 305231020 502298741 94123446 103578023 605130422 368060046 716489833 30911502 838845393 827095115 758763640 728339554 490712275 987755343 695979898 40329908 491600582 788487833 529651226 603614062 718033916 300499405 417748824 213464089 514886158 343157729 973492807 804740415 430273773 923572041 516474808 379531157 445578210 560874128 196080023 779568100 578335628 594036536 732211612 768241072 59643192 723992062 276115939 258793104 234328880 235523809 793093642 167465362 784666538 539518746 651975767 354688549 9092479 474918721 898377756 997588239 266506620 883024993 540446573 125486146 270466391 476338359 632608894 446632577 92826280 541321543 109911053 485858318 232775972 556608602 852220301 153288523 523947943 638467319 510463720 564485458 444033005 383990913 780816814 475724819 827108626 254422996 232806454 510639969 407480585 64343439 931876755 291975467 20176217 961405181 48760267 230709089 802237601 190879973 575258162 792071615 576542722 670393784 145385377 428172780 358474510 452715597 861941857 856001524 166188987 867883470 246367512 732374943 846534193 952834554 831486844 785899110 188717615 781157630 15483871 287825499 45040418 971211922 438854515 945374273 353279579 768966805 272848969 576112781 122706404 309168071 597618706 41997381 469769535 628534004 578258263 317467561 535912737 375857193 446516826 819293110 986511261 715160760 150774751 861785204 442882413 533135513 374080185 784179886 829280194 790970035 954825806 559107060 649463503 299961756 875993599 476089625 441079403 253463476 532370949 744166569 272334791 321414214 182924455 958817521 645791268 389391149 531708710 957710978 826614472 837913035 680434382 369707574 172354538 137279258 282700925 278667495 828880905 340644573 88890460 24991888 645479778 112079961 325380725 261343252 592756148 888936782 687604557 753476800 970641473 378085178 750429317 585204 522597276 101435274 899617058 170916426 308978505 817968680 43502328 921634252 436179517 729273721 455642644 738497001 857532348 37853674 280866532 603825686 849430511 330812061 450287982 55941148 882335725 575735958 94416512 589584987 296848769 796866911 508784637 402693665 459170126 683394246 734469640 792877305 103097726 787064303 907133889 436016292 853480235 525002570 25788522 263991124 33791733 727390712 964583549 285118286 398351178 364261031 449114849 173564246 124550706 93117948 108438728 82411800 809907292 150906544 133630630 228171248 948446494 175961420 185728182 413228852 7999755 642451316 317089395 552476916 456676459 688208467 497182056 862128952 326524156 106310690 990211013 797303723 346898179 587181062 31652785 386911764 13296297 484867841 814704892 366471547 521626741 849430503 994668637 682454681 437376514 368881595 142292184 328063287 591602643 665154774 418620628 216478384 207425131 45938225 622345721 470197652 635792667 106979921 344370475 87408833 111034749 501455577 926437771 39718513 595429586 141661748 169696625 780468436 297688600 585333027 963719052 364028450 564587388 194497526 565127836 307635109 512464260 704580980 834459969 249979420 970838603 975059922 664235145 829162503 790130493 936970046 907746683 19279449 304580197 127921997 771262808 979738462 729014320 886463671 170736077 821406148 977367168 132202124 62894506 871465229 579419181 68335267 556263568 469493472 535854828 905962872 417251895 947525790 910850015 479749945 615739503 806176373 54528665 847860421 992387769 782247323 475398626 888353673 77141390 544550964 840175673 521497909 121987744 822585681 792210207 516176721 976553093 590783760 537736701 995698389 487525214 407974192 622113743 917563098 433038053 401147413 372381108 727895613 743848235 227423446 54284993 337240378 497594718 14632710 510017001 679176127 881163573 399646791 927250382 195300496 145114395 451018522 886852185 726830000 294682810 661859423 418340473 488022726 501852605 189927222 851948011 821493361 434188922 857452152 895222698 264924703 856209161 175016909 930103157 346387388 322792727 288573885 131046043 832981326 603131781 310160805 999421750 891956221 636731207 560788449 924719042 79681554 329898223 988101886 512646290 311518234 416209740 631528565 335764072 607049505 546934441 277173106 984366103 588040504 267293277 820237564 272744394 230351790 509962562 959839917 915575305 808281500 884352427 653953611 753581038 359383119 539417799 412016497 575792460 721704297 927298426 24038288 852586200 308492788 139410836 862568510 844652399 493318727 928364746 221816212 936850077 108945892 1113327 594602067 215045382 920389655 157379454 132351631 537652696 865828425 548274263 901884751 897329218 325980935 890091110 396237016 590066031 459943787 289277835 100115865 357478932 865723781 622951950 816225722 102427888 588325083 708562724 418246813 749029791 891529484 916765511 602281926 75450478 623633910 364000082 726524535 793366469 280028925 605060279 550532149 848893106 158752696 376977634 307234965 738972717 206965592 795880437 97905674 891688556 815250064 678149681 791341765 69017883 443985079 861326603 909784167 70698128 181694190 28391637 660328423 292690071 354577167 587407452 513918225 936164467 158083102 521100832 600963210 900324336 281366113 800265992 765156275 478045163 475972862 255160825 464023462 523095391 354734645 512582718 220034104 680152079 27411772 672067218 691279885 462420919 751706191 15061060 70622708 304250157 795457580 107421724 887827838 509701987 643298654 748138561 105457760 283487989 957388972 694120888 104479882 384316849 318570981 671869416 931536114 732074217 545276873 99527295 410118986 248566572 613750718 592985879 842369856 290416002 272263943 74311504 186521607 560892122 456771500 994767137 853626139 212882904 124280789 6420949 904919333 228615189 783908146 167685645 522188752 538547882 721365977 321983499 386155577 264176624 509584120 935634519 417068807 219169131 26288014 72890595 312580375 292171282 423041757 471648608 865597475 175036460 330416954 388195899 821893338 344386478 463811907 952778135 990587152 677690811 525358641 384408891 422878339 501595435 451111049 507469987 281624583 520900891 75814155 528963452 216843797 688042781 621691764 453427270 486471980 737695091 995864044 400295519 853571018 741242537 85404628 333883628 337681638 587077950 590363134 792385944 283518314 610255485 426290262 828993605 132951873 694476206 852116884 489337257 65839193 23830234 250538390 548200931 154848056 766502006 959780369 228919495 80818278 634466709 985126484 188290950 548026354 461051895 555929446 681331278 635607082 539626960 283188463 75231723 883663692 931036495 877530317 328963438 461451740 603506893 317723632 790813695 20063915 76463549 424864105 190505644 922785111 55494425 958056645 144394497 493582117 92562565 224658423 450186112 780065537 27583021 782565244 781552334 987900953 995117626 194617573 600005294 454868195 372972238 250350763 247083350 465290711 245265008 422022792 890420175 259125724 842304414 484094680 976800928 275543354 203349464 564242912 389249477 910569395 154464591 985699685 196981682 852230481 825899604 653421158 550156270 774269493 66583620 992151250 502828062 316171731 238100436 639038273 146006217 884087822 964065120 399605400 221134485 699782983 11376497 315323544 917894450 330961607 494889719 536966821 606658703 86784637 167552661 236698871 3891116 946729738 434306082 535686788 853067111 932139236 310487301 205396199 634909613 754278678 794871158 616674134 956049884 553473729 570165142 51283638 413156629 833757475 254005443 316526607 972681397 134090633 749555067 183231259 218699031 148515814 178218855 686211161 219441610 299113975 916242599 474972644 613340363 150535828 861410067 329489024 304551226 17796375 174345178 514648977 131842869 158278723 69891014 361019202 311559669 735214559 813581227 97929722 89418130 786709024 126661746 229331911 700705682 78349938 318268509 900216261 546634229 756215258 694085975 561383235 761373409 460064441 459397691 8293837 898663163 43831996 100619034 345148039 95784097 40991300 247274026 417308223 30264094 855149161 505307001 88239678 430018197 285335449 994965846 858149916 496475745 516659011 920997519 166235531 759619370 525954965 927597423 469226192 977461274 762033092 61094754 507866754 159567584 245464214 732704989 392582347 522604891 347849456 854251101 751001911 65101808 923465834 557075046 491283345 999655845 528984846 129412412 328544432 310483407 889371797 594633028 793657995 593380412 579318519 938967288 388067457 535645799 74081302 939783303 672724485 56410623 213708469 897938081 678085886 653714053 485285195 783940017 972876146 168744782 681592859 483244338 697551841 22599024 557316407 761757547 688178555 814244409 404331883 284862215 448024519 127863579 325183055 672596601 408537582 349704776 266159677 722987724 267891557 38193336 795068025 493514679 501709997 299018136 532558599 932899043 990458386 89626807 340054400 421338733 701454146 876370018 815508316 620885950 859179408 608321687 55899147 736400688 265441775 409367594 757485060 952766143 4000906 436732516 132388386 712299205 961679125 949357097 660714436 926870918 764080885 643899527 466853860 84311484 242724451 987521350 454262543 151295200 907564531 368448543 777359846 52443194 28535184 612392029 953275206 812481577 418296673 49713375 910067765 828914254 579009280 553468887 126530596 734689086 655066833 268205620 368457028 875998478 176016244 321732425 255087309 557576406 9348493 146315970 909083982 11155835 641598737 318422299 679565384 793416718 848481854 836404333 271821414 705074593 864485328 50880962 993427422 752767641 819228935 797262900 925754807 887110882 859489522 767781890 831951174 929718813 126178248 601091911 855548532 291163022 595994665 110718744 448352622 831445866 188283425 447738353 993045558 734537717 44450900 966745391 124065196 391012695 905979597 496340303 246323713 752746993 806336251 69018706 554158400 238142881 591980971 486888095 495594985 817361088 533744189 227996485 734457908 667225853 483731625 761639824 273097441 972421260 458580619 558919315 86628248 351267181 55545930 24948339 822600684 154168471 9441338 42283846 202759598 593150438 929039494 882677817 96077083 999478747 220476666 5986485 498312162 772171098 547028603 403937862 783870429 57409121 209713169 318317526 700013420 407765941 948730154 882289583 344941029 511205635 710210264 631989343 551804392 373279518 513479404 630483791 969929278 694634202 149541206 718135419 848778769 298393945 134866865 869550136 400688493 253588143 336224392 679477936 595276341 222616493 826637205 35489376 582141394 552712968 258470224 139067557 247452495 352457183 403185065 88777941 595972357 964072978 590583004 610607791 227779699 497264665 77295590 547262124 983092965 430673729 840841061 911581737 220819041 13455398 91085014 436767502 953903709 167209417 636431569 416023483 193121806 178436829 514074330 461661690 393549345 202865031 597152034 164806341 359803040 886004651 771660505 528149155 506114966 719575992 124622927 82434088 149425929 211520147 131849642 906036298 929076825 754930030 294559907 374508403 642825859 976651324 859341214 871623565 190783390 843893877 2399943 960015033 877668109 393649386 720503455 833590520 786077380 999787414 433754837 686712694 791748817 728817068 907529852 750628108 502770822 532017176 863351365 459419563 801787899 181321067 795760774 827221917 858005532 231124940 864640545 329782622 522527712 623474040 259384988 6854302 806927756 682005429 629845358 410111220 560158496 810632719 583736920 23570604 283573531 416555155 591733384 621256958 949404280 104038998 433906502 873301768 640705647 344579411 782401844 207610767 306434292 335413282 502543225 162883055 27378674 696412492 640078410 705712039 410359592 922208993 522230576 170044998 540168223 104219594 856153157 988232535 48904641 935376232 749848661 226919360 681253882 21668423 901314107 468425650 590250421 208485951 860201909 823388924 473054674 400670896 41991169 409262854 459322440 807661151 635107741 440538261 685490544 97812535 804095629 471005523 954052300 344974204 55571193 502979605 355402866 803207381 344987639 447620480 228331527 560386094 651165107 417323902 122347490 499717837 345046540 904973136 9789843 303559518 985254284 462441494 884686720 594372273 170769898 702918005 257935316 285570749 316972479 756133456 350628173 739392717 430289022 181221308 766963189 179059662 653058281 620873118 938302151 106268077 921288508 959409329 431477404 793538047 488720648 652124001 605992968 966961422 344093385 362999931 404339490 511937115 74757402 310737259 252083832 467615779 300211977 878990474 132413174 167678868 918048917 704955380 505774823 2945960 203734760 857894127 915255259 980453916 737485542 324455764 249331137 616261671 315256848 787022617 514440067 147008471 574656334 304752091 551573335 795027594 715228436 900113880 605858343 594366348 609933304 626966024 902532834 872121709 311423422 573985440 632355057 978026051 449609838 489052373 744630589 581821070 23524860 739182257 924129596 345591041 648978042 713224217 26308080 593275840 53542685 451125487 815391566 267110299 360482936 255377632 373115936 928094898 953939040 476234308 856619536 500586579 7390244 486261659 684589949 30136699 913439512 137846050 953281478 647791017 920289145 850220995 436414151 928201804 793840888 619797245 511158944 278446733 403085487 986648866 424778148 973795290 727724395 229417746 447458985 661708797 636858463 462547803 399619642 785032776 947129300 178027446 511683460 493573087 268529198 383035857 776319690 501153426 664084417 759975227 662211234 167208624 443033165 846059474 439732143 813525392 197586900 434103028 47270265 833499762 886159319 288250230 852772906 889605224 394161485 527305880 236120725 711154333 646096897 226318434 791546937 105109268 143654554 137802441 243242865 430716789 496434498 469994666 105719327 359474808 426050944 17071412 404608763 635823182 631356859 560947503 662140596 630400537 966014003 736890136 174289172 967880724 84389543 697399862 548494361 355820712 316816849 811933958 64056049 65443759 169300407 166436632 326786996 56226076 122780708 463375129 834959887 732495185 954831610 308969232 834082857 400980436 443295480 745641774 926556815 340720422 499052428 587483483 132381210 374862886 947839334 54428088 783033724 831206999 51142431 130874590 970070055 300488074 618401130 198692368 924209128 916615501 975001555 848309536 721837158 216416867 532895141 173551993 852640267 522631909 973364480 703972260 513012452 124404961 262082797 610428657 974890565 548688391 900596733 861541214 116037101 723951844 729948411 875852365 434384093 896614419 663506425 352455536 424867303 909900266 708201250 547490042 174193641 276079548 617349262 747980174 356839226 962939562 483807588 675756996 990075365 759051950 730202612 620174225 96673282 179546450 140339923 516865648 348700297 626732611 34231774 767380286 219002125 168995518 653442803 688588897 106439820 568161212 639783214 143485730 644333432 778191596 454844865 311770837 680370922 484900848 319172846 59981327 914084066 840280302 830837533 166304127 849237969 914903860 932702117 373308214 428254916 30124188 24469175 732217706 584767265 274537342 374569248 632766777 939432988 22918666 118693859 776342316 364002311 974815215 664858115 502932427 321366088 931571358 18080225 783026466 745765614 813438279 797504784 650312507 521560139 320504535 930342067 691214867 618138817 327414705 654272474 808494594 266624764 944748725 180578605 565338231 943267454 929714987 268992544 480304144 737253750 337191649 337847445 607645313 305253908 270234192 332266181 145611271 207869 87238698 153737449 313382618 675858604 778581830 371553706 788900371 73292120 145971905 601962543 257207752 655102423 811471577 267607062 115537081 383552568 844314178 837274733 695936949 598775937 14984643 583584400 489913904 857253198 123127643 569207289 346277326 702745793 712265742 882748419 90082393 708370769 257896764 975503396 532075872 905465427 102922153 75845410 455758630 794151618 928332852 923052066 790636087 133765155 549066210 349330444 382678868 594623694 632042990 988014880 129701471 21460888 26671468 501264188 827381497 273765669 733635628 498035830 892365487 825114753 578429807 26214958 839788342 886386686 578492528 414030429 246718921 534547139 689433154 610219852 920861031 107669440 941994237 548102462 188494981 538520818 823013893 838642559 643537772 88236731 629431942 502633740 825388156 59328889 234372773 870450546 491048554 580296471 751768791 188252124 376076998 751021481 297400794 484680590 55955914 112706803 565928272 427177108 355266594 540323559 382595239 773726721 469004301 365179404 744255807 51102856 833002114 92068741 177207080 348421734 463218017 864911384 581561190 270840899 390984071 169240739 763992981 347043954 886610738 137754556 535189592 254213746 820327983 242423477 622359191 984870572 531140436 983143515 852904190 345875838 734229556 630676737 638997421 339054492 758125412 878996570 503318518 55582634 177016663 343585116 832536506 226345909 516824780 826279914 926919550 253871626 971806550 202710315 675129847 431731812 312100105 402614933 575683772 775419382 371286471 310706608 269004028 876291601 454179775 552009804 413777128 585482262 610589269 752083574 853617653 837120453 349633722 281447558 448911988 841422957 833133084 133201243 190897167 869125736 125470626 657683037 544004766 146985888 831114221 920726550 373333465 668363629 631911159 804104875 9823641 569027593 909095019 720006674 603386919 347069522 258615263 736433905 78228741 708745507 224445525 284526265 628792497 587720004 669168774 212321478 710357041 252777320 846379758 105071015 535474761 607607410 249726785 341861221 970367490 480393093 113271817 180139972 293758727 965447739 713473027 130997179 605635507 938460520 543864650 711959712 114470208 515741544 979377185 863075037 147839955 125054410 330244720 332111528 381685589 229863287 234607271 547763464 290628878 826180654 698735019 783134467 768483316 472765735 587373755 297541353 862646862 396044045 715197595 995202320 462644042 993207507 599931870 667556348 442086933 88946155 950591661 819592720 493677434 478222875 58136204 102183380 34313456 509680697 424320119 605637025 75818371 180407406 881717609 662123633 937937318 310576757 124786699 441954969 523254511 829224678 335657783 651592411 875032339 954387726 39292530 695156049 965299469 510764340 858274714 587497943 88080381 30725230 851874618 753685479 687077504 389299831 251389871 476851462 595527439 310285115 236264233 966044140 239624634 212278658 722538485 868807283 229398418 233413397 422893779 880896188 995723757 906135070 973988284 908596829 660560619 109041263 636429395 847905837 220685626 205727991 132519125 54764299 64451337 617999319 326939762 550678890 341041757 853027820 493401512 846096662 280463951 387395874 531594596 165450807 239624667 211402551 176495523 76373738 398182273 280401841 962415617 93224027 228889704 935108730 865423976 149307118 473973923 133354770 871426940 117225862 741238040 717795617 47941056 366030913 971857253 289577400 55113403 266162405 723740688 682609574 820998657 790238104 266758497 29269084 169431248 513608039 632173580 29511589 970943044 866282232 847481828 958134892 64485004 11480704 868982071 290761115 344856944 491807368 827244540 115275068 17442659 210828066 600380498 407380281 553834028 101778448 9922383 953953374 548436760 639319412 235634098 747832089 5126518 720018164 549814411 336366728 344120804 227684993 786090954 888018062 825600309 977484643 79681354 96215386 419122396 53991985 418833177 395777073 214374003 659141781 589793488 196928249 710392513 571452195 86826012 10290395 503894042 791349695 469339733 197033129 304910153 725296644 281883451 423560988 351807055 571789343 490317053 148443936 274450664 682885173 538857683 376377082 759017900 477544307 396920479 699180583 124536878 181643901 652917022 521239768 710646272 483618619 253977370 518272470 839823582 576016806 275384065 723711011 734216865 749084638 226514335 264401485 427201422 743147281 769429127 621025340 264856065 612212682 742383925 16746045 368134738 797692470 999801588 862166909 252623239 737433229 106873290 986647881 422436127 69364077 720154092 643451028 955566362 186292843 667048445 638525180 540640445 373126119 762495220 857507280 603053560 358755539 682513535 75996573 555946617 930060936 277689395 604226471 755960801 869764546 455594384 508439035 383651729 726180593 2150959 213846604 351682217 624110281 908089168 229743660 47731739 337074182 140929869 37197494 691490105 337886196 637363373 906901084 615052789 374979092 548028732 523097172 607038418 182447508 678700004 447171723 523200153 405237054 628411123 728955301 12357017 829417589 475719257 397237951 422464267 227736931 775831369 474790419 226119180 901648972 769192505 599054486 503130722 75907226 666812290 514507185 47177057 692583984 816054241 587403287 548650236 704717219 586385987 450138452 205469517 680704490 845974828 465253358 276696649 899801105 834751490 626906791 908712843 893206060 798386297 16058395 938017216 969822518 184332578 958110284 194491446 22879880 871516594 183232943 468745509 68461159 125890341 763406007 106219400 601696355 502254002 717756514 641948040 951251757 816841444 617304714 574560015 388089298 43976917 607873006 964063166 160208832 544510808 980909470 220553405 694832061 382732964 98215844 363221858 689910336 557802629 47999734 832997664 161239215 954486233 887205930 131014919 820960200 442098606 974616690 364061143 389008471 302280276 22022874 690696973 97529845 468776486 965266120 676857327 854820771 986139094 541687093 455909629 630941116 968090720 790098195 165960042 522180714 807857034 787008386 51411112 535623905 209120783 865449239 315188220 567925476 159827843 317214612 490015296 212829521 313442320 634580049 606140733 628734181 262867834 797459149 107465776 576293768 188090940 318702173 499546695 884174982 73941721 933655913 370071939 818526848 505065991 926133129 656868428 356759383 723012013 564275082 698320126 151922342 979076325 303051782 122603358 967115782 647498954 543844449 175650737 833103299 849803640 873264642 474731292 623137315 601712829 15635317 960600986 822291992 366134192 414709103 580130866 24616833 241246932 666944939 492356838 371099693 216646160 452946594 319283697 26704503 973524804 934508232 253660003 876155141 24196006 625742641 641087649 442499087 712248025 151296058 18786237 895753424 535867923 696969039 279892857 401788466 430934783 595638711 682142556 252886950 869730996 385628325 334804339 625635161 927481924 272593364 439696344 603289560 769026202 162638562 62201590 231032196 795637353 282007995 856182198 140550605 294808591 581488637 180294757 939537921 813732660 382997514 55245683 347602969 17256759 663587849 952883489 152979294 549807033 232406088 789249537 771618537 152277637 153571237 596426254 405413073 392775528 325446084 168519675 61586413 532711351 506799766 208606589 590223289 7271533 422023658 909649581 870949995 111926414 538883377 491663628 121098507 984117177 798552609 41750274 611146586 621502924 463252366 44010572 176462685 550832661 454020603 284626423 58287062 267187249 209358564 447567062 743706935 710420092 857172461 568970420 559374766 594936768 577826427 290405022 744844712 760475609 69633175 37820285 121180652 903849768 782756268 930273695 472050031 18016993 20513704 224781313 754171665 344476946 59822624 332989870 637849262 477858731 818058611 876459865 447774296 881428082 688227159 993067231 871081234 127586936 460012269 2479885 341032635 878243103 294081119 803748070 968835468 574575637 341252068 119140553 878814146 378929985 526624402 91249177 152398571 689906390 112979362 580788915 901852089 829486215 425975377 674687161 9786299 207015021 66650914 785711191 548916212 875469481 196140518 255217256 21326496 114901376 650717571 663027405 146383056 706829648 264404891 48087663 213928783 382360710 521058469 549764306 343417053 862220299 234767052 321815785 489823327 672231428 882928983 506390376 422783887 641874492 409856604 44242721 790118486 333540391 326754671 319528516 244640820 17537679 700683866 467437834 808766568 221077109 445240065 604822920 881026117 206745957 756418821 930725785 149836657 133513202 656105988 483274562 426535710 203911458 604987987 272758328 704950531 945254244 950831648 901647476 829453534 168399213 235753223 414028693 925950820 322448333 424174495 154923137 83848580 90706727 666414022 219691686 476343559 496832782 382836920 575484542 37209675 195953559 10112798 122493400 620577276 229214788 592110614 402721325 418164691 439848952 340374726 420846525 179661943 214726441 251592000 535590515 611039795 319813531 53473788 78780518 798073236 649501595 518240015 588452581 787688160 848274897 491649831 100385952 653391394 557603687 539607167 981777391 758380522 61101927 300824236 385914217 331690776 740351712 249627645 913735148 353341115 567265638 225751852 96907254 447373832 424538101 832684837 208140988 561162568 732001672 139579770 140004588 347452009 316845317 74678066 592431037 303200083 980580812 423903435 539435556 493910217 189561404 193201494 561967688 570622185 787143320 593804030 199809141 380156546 222856443 510161262 124843311 815947143 795339816 593778011 608573126 79661679 860661619 779567286 926963510 800396452 79706187 112778717 111098700 21507671 648110356 677861191 383688629 582203696 270843296 321087109 389360208 278462690 418624094 375973782 904107476 458085554 167802732 246776982 1019008 76464014 432410388 169503015 31817915 605519935 573649535 110758968 591510230 605390223 543204817 238029224 123416073 919371610 586765011 687355372 200714206 551620048 220498250 702138161 688976839 255751393 964062507 368542003 839405760 417611075 704444266 882488028 865311384 836041647 878163959 678961007 456648357 892049213 533409157 883928448 679046358 24762970 891534893 74522339 95737134 815992028 385556486 813865711 36483716 352767183 248437266 302433242 899399837 757818447 933970772 443254474 483990915 923233388 438653462 599981600 880620455 927856240 202201571 924643073 287676506 510787878 462190463 639308993 201975459 457090177 42217950 689928004 370014173 393118478 706038139 512231584 291023723 695591662 43858581 803397310 965633401 45219256 939102124 516774015 618365522 17659813 980857208 838577916 856868063 542243073 24829337 972952461 680349327 54631891 589522400 205491448 203604645 893946995 853906192 974171436 220100841 898227196 331125747 711533105 411068033 920033078 777502806 38059522 41874900 699076042 721327626 129567038 20746352 528637985 128781713 263040080 815392383 301375903 90159366 818729039 324029534 437267337 155233420 393786013 658761742 507616471 53091371 882959083 141217506 538787752 952077828 796452483 488364445 862148978 636245767 199895128 40887699 714378784 593242784 660597569 945566229 239166233 578030271 272986343 431677450 882510743 27405969 310877528 266388463 164721680 317546827 291411447 260015529 581305983 295394086 469366801 517900690 290192443 143573729 157066769 66630916 806603118 186219422 20885738 102967002 686267409 921784235 773735396 525194979 142388750 794246234 572634982 436013362 818793947 416305330 297652944 315606419 463483921 431708136 866161027 510797511 191790348 241886315 885451443 572035142 705050922 188755655 723151109 487782001 922893880 850411326 766630288 487902980 392662534 472939281 419082337 646079683 946405423 823676361 454182086 764515694 494736898 576884816 236707907 770481174 473717367 157787549 344144052 578843227 559668286 54109679 436359718 708280355 877262481 128686351 466520530 391718142 648264746 686304654 309017983 100808351 253258050 127968808 779637649 978521129 956134152 671953260 580926109 506478003 910183240 413345096 296937181 576573682 668235017 419449634 352606491 89055287 483364895 80795859 615773733 204666451 377502477 809685655 940648659 72270565 167509438 303247299 894082217 227369066 228445128 594176378 43209471 675702358 430571710 359977168 433563540 683513812 874926375 489828135 503106356 945327165 834441521 503156233 833272922 505323135 564251496 29671351 305396156 731298876 14045900 192449843 128970356 566037710 924841557 704987764 769440813 638580354 147400877 71202337 721847607 683344473 364849920 942683213 134790595 455522663 311529811 65709277 410635306 878938315 803672916 431237937 38445144 51972670 292331479 916360857 347624875 16071028 145372607 468319545 767732207 320742191 797078 228464740 365889794 207179635 662882339 204487629 95261831 205513683 667568811 925003347 583528974 853536308 542530285 435916433 965656906 560064319 52818235 604701976 791542799 103152402 861116387 397084962 310812694 944438068 273599971 69258855 828852572 665135735 416752402 104886722 940403351 971399619 555779097 569806630 978465281 111881392 169048509 231721083 527183956 748413069 495437458 699019408 937947315 180694735 168876288 198095040 388629173 34942676 683620974 201003334 506325596 504679696 183767567 590332072 835553682 21675534 685584285 597832671 827541903 572262404 476187593 87365592 931442103 199255761 371130188 790182412 602680884 203253133 542796553 569751678 527391193 968986023 379022711 338626781 180464695 166077038 727476388 677858405 571882622 58995858 499332919 302225154 443974542 942236527 838809546 216469322 180210160 570944580 542098362 382257937 134210484 748800265 111504659 458224557 89609133 912664833 960835909 230901197 186509147 777204095 488039325 260067974 913481648 710575930 854334278 50387913 416771742 294816081 241138693 782432695 92752535 616435814 601704858 30778031 421780993 200022025 756907284 58159256 944049411 929362654 469340723 768203421 455036721 194212771 852747039 394578872 140525820 292849201 941256368 558492621 785670999 140460940 759636017 865025854 270344411 765837869 23653335 47934443 850836751 974446435 893974575 879388996 388911347 8018710 356972041 872937450 147373047 862956389 65218015 281515975 415145630 435722501 175572486 967809311 482370775 330473906 841195054 813958364 574447438 755195102 207383525 445132455 451020219 244308444 431956641 360061692 732797341 305492986 764317873 943906768 271276951 405253465 64434877 886557444 216786879 728425532 189125290 618559548 813041522 675695623 557037988 992718363 303910832 205698782 832764597 691820871 146110049 673466367 791724857 97219975 326922512 231664355 318968341 434109191 831990299 232045631 480880639 540279662 233670141 407296099 936024973 215632261 833990325 158392811 20037100 871136055 14910763 391386037 526817557 673126893 803020191 776307076 426914098 730709207 753796865 738749602 144150130 946820038 221005992 549050957 316843936 914879829 956453014 76324385 62199695 320048351 944133085 636562119 656693789 967075767 901870713 858023434 815586561 338293290 650171637 481155226 88988338 156233955 159447421 831289884 274961360 776594247 666488854 435802097 841123666 433172378 185098794 128545760 776136108 934396959 577233845 195243327 601882391 572145475 922092222 241723880 194329238 121138183 477847726 728584387 689357080 474656947 982419059 994930392 146504574 586759204 151167019 919819239 911130659 675775674 593537262 171059381 697585145 83455747 330716703 778627805 41004132 936865389 180227557 725895896 837227432 496417628 321523825 189130918 366133561 460564517 968385322 290263610 862108395 732125383 11902296 338940292 448621727 92766038 97843476 203726121 76119388 308141368 286077746 365278598 970428736 745629977 344397138 323095025 572374428 895015627 705839261 957295597 695888208 579873522 298023439 104346335 279984945 505320620 456227794 585090637 423005762 955971769 372298056 563147391 595525645 606463211 198666261 9910110 272400986 943508821 258508521 296172199 571985564 607688519 229031731 756761732 259128900 529956431 455489797 27218471 432735659 436154457 387325572 541752896 83209004 571813048 320418082 659555810 868498409 903122616 379828965 835584842 887283933 312296829 67830779 539575555 924225842 993029367 473840561 371664358 769000842 869561993 703842737 423915454 9730508 768387544 922939361 996361332 964456598 983487367 667151714 918823803 99674932 61313735 608756238 188513760 800036203 913634519 477573246 62185244 816602606 257651933 533749102 153246033 880566170 959009474 182929793 809741150 542445162 230159901 16404111 197287875 802432367 974339805 959826128 15669034 774352269 540501578 426749281 246213778 181749479 591279190 162394841 706658809 294855109 323017157 124622577 82218193 745347669 661471712 519625418 308854500 339947572 780469497 240046232 620050738 187113 58051502 398098401 504979621 558421568 875715263 762010901 829221935 297168060 479079397 651955687 736361091 98693511 705212578 637621475 674021528 76951015 926356699 670599172 122967518 735090982 692677710 75734715 273742153 924621369 140546627 389920854 411472315 363546541 118385627 976260616 496767499 327059554 430742567 685473717 820290447 545422521 467143728 891933924 809090586 276600398 162047690 579531119 47881053 763354255 725560135 116030833 507652470 393378574 421079739 556087231 712963415 88728768 948544221 45250776 738319226 269665485 659302395 950987024 495013852 639821794 121448896 126824520 79230847 733111514 47035189 131194495 318841909 836084086 352091976 350902227 425324311 373715435 769348369 257537150 531958284 825205520 137037040 842891441 119121981 164843492 647320854 169454535 14952073 636249027 735906447 437777938 372704127 655288323 999560458 772976085 577127276 9066916 865159105 522114902 799934615 583006457 361500121 327122186 726695182 317443819 938510428 1293258 288460618 500989645 257991699 884569379 194320492 929469886 897758130 709841702 135684753 255379845 405117769 427746103 458284953 830287076 494586171 804763020 896254786 926994336 293155952 526761988 845287210 524556957 555669853 680108841 878017209 469768220 338891202 929066405 231775855 489042642 252902522 93026498 192656852 307404835 36137049 385832625 248044155 265350467 630533696 643213661 571479836 516868896 80068314 989621118 429977787 378011647 919661970 556860307 200881966 295152168 147957310 111896658 135332853 959986221 835293713 283991661 495395592 815532087 234597741 620806619 839239243 218059109 646552897 759404494 968289843 432067610 346454500 153903954 379072514 809264702 19418067 517039490 143532124 910189914 37778430 43547494 285866909 450635254 532990525 202466277 109498018 674356177 320590100 953983346 477636388 469282233 138351932 1535734 426293396 357450062 652814685 541581033 813801385 814671732 167446040 241709119 797473588 833048549 686463662 395765768 921450746 887600100 142601332 785574543 258155057 285825760 280903295 931435981 40724556 59407435 59515285 850596378 839888210 545363877 709047353 24033666 941357645 757279742 273607634 703470919 951937291 258433912 74640509 388424828 824743136 706372268 781411825 266774307 426507665 318890294 959299159 94968290 433585624 475242724 756543692 43814139 782893122 458826082 220228593 31797032 487246347 747388421 986578005 434473707 135011319 804621434 352686894 267151568 311912892 151079272 70196015 545841356 207283813 671476090 756210866 790585024 442497747 163761734 920546019 172867693 11746809 877946963 531159089 264693470 687555091 405023808 743780755 378011366 242562299 233590752 288124184 243765226 763815078 497703787 457220221 390379532 943633267 249335619 973845866 314108258 552143712 936575840 78923583 50840874 707405105 749573155 300875241 247606471 228245296 806540155 859920971 485322374 178865810 253546893 48966307 48757836 604644909 898885784 143858392 562131638 57622116 150154613 11136964 661747489 478323218 136051677 274547425 479921836 747464997 204504191 93687159 350426691 704006449 861197560 330450324 598563117 357019728 923552815 78097223 890144826 381981710 529049817 649316156 402052749 198771056 133320709 666540741 221310931 635874662 229848237 170951817 300663842 316602251 614019348 668028927 219265908 272566709 448172553 980177101 323070981 712965123 246274415 23332213 118213581 548515052 566320925 114419237 913284629 649111976 318144741 261260405 742871760 10275677 789943258 206167368 160998897 181715275 33131712 762064810 577783365 55605290 989889193 60008471 414283313 921880978 259624610 189603027 573848862 954184169 841906789 478418020 68002578 339740366 15119673 910193344 52007184 63077925 20063351 610161074 501217244 778039081 989776340 393087961 395845072 597645065 354288059 992142419 468590670 855544460 7011576 928357120 121046824 909149318 215626429 434319643 305156142 805543430 79943338 965066274 27625967 532531427 362791985 929533180 477713466 8876604 761548149 280150901 180471908 616425575 594768667 361393754 238667616 291368691 86219602 897285272 653659556 45260191 139340982 349071348 124796187 324189450 198508690 299285009 199181076 466139335 524434312 481195920 205380979 662200319 649042413 665236170 109278275 261062271 305249162 464648509 867358624 148569574 810922868 433010110 977408135 686802291 274859158 705964424 927673302 891899821 780483410 40637845 987875252 433607837 432386426 984649481 325269262 534059098 82746366 489994105 730423044 501928236 457001539 449430664 619517697 87281439 554212640 316164644 649501407 574920919 227275663 664501573 53894442 600111355 215259202 571113306 303717021 985739395 250754377 799109994 661530941 984110045 510301220 251111519 161636128 643639948 740911257 123959102 877880484 730274897 728694583 731872591 400361408 562034379 693246149 615839469 336169475 757642459 189085279 797368172 494791498 88679768 876398651 556762934 577046015 366736834 474467241 591745391 437504714 79673287 151423973 594261392 73469176 635094701 512108803 354807554 254623797 460099346 114833110 634609622 669465991 348672244 746784416 193183472 692583970 858171592 453539168 184819831 266923494 731989291 910430895 284055362 731798365 173227726 947656076 245631372 442702587 318434784 742962179 381234705 407589778 160081877 113277439 865454122 18109165 649777663 366574426 545568295 667132942 104327064 733625115 253195676 10451423 906398372 88468883 581774633 28061550 75648410 41485178 48064996 789397653 864897331 22356213 485011115 724294247 330125097 357299425 948033394 338496858 738543443 722624041 329274925 49485433 331097667 535498311 869506982 678278479 898079529 700652885 637072439 158451194 721033075 73864678 695348455 317783789 630349993 255603448 286632311 262705330 998508029 868972753 942079683 572062918 684964661 251535425 683225834 391856858 965811550 808241328 405940855 286857776 335630380 588289278 944161615 307371811 585277777 742934227 824732845 686858219 393969276 866318112 231351492 942194259 334848603 880403266 907741533 402970418 461005633 215691037 114308124 422057408 234112051 158606901 605288917 704648274 21135964 475817744 208984033 36209673 154657613 184343285 937400275 286070846 8577816 941578839 175753773 883048934 769274610 580791020 500177271 447268569 549924739 281950469 974178543 182984309 529228546 537773877 521373793 608474941 577235404 34764198 510142479 189079650 688196756 725300800 791230700 704498585 374048475 25011492 641278658 826156795 291939310 224693134 735304684 888545816 204464026 720632400 474005418 912975467 981453603 996406370 146118054 655671420 649492116 122595297 748964753 311783185 664039491 231525652 862112408 342256922 466125333 380019136 633897059 514843983 594412098 562723078 542650521 265813231 695793591 524127324 433450783 729728095 707001212 487042342 157397772 658923714 81191894 956359903 374407884 331961083 504805153 696792482 796928014 113921121 176438824 823275223 810711178 837106423 980374362 114239370 274237135 178109322 380435197 986334322 953312528 737704451 230286850 742116593 605466300 67791848 630024558 961289986 240274919 783854947 318720389 122356237 184239586 407058689 765648207 970015806 662238758 447006070 910957337 443782121 448064211 829380773 229021932 541551890 504100985 375113678 980749034 476075943 653280254 169040562 614869494 130495325 100574330 625426195 408124507 383565955 21980336 793520570 712548256 251983773 892070412 828020076 393101770 625836418 587106801 526048746 944083742 408416773 534144962 1689812 333935638 924099912 289435147 767312068 30001946 143068241 801328152 860959854 950191631 343434819 976914362 698767189 554793469 105990311 705782795 966112406 67266168 514484304 992361937 355175715 806240325 671016904 37719133 990834398 103086898 877435784 146334042 144545852 467987906 320608931 873057362 450180680 372218522 994169259 850407056 544472998 157903929 874187619 97992860 334959909 958228369 866138851 652832897 583577880 214270303 179431613 484068764 869730750 53164391 417541070 465874131 431423005 860607911 127347272 942234761 219742018 734620430 740494121 461002769 135112123 294501553 880107056 110810852 911070135 545640674 833215062 306780312 397956087 356401468 159974427 141644048 421315401 372582121 489033698 143379738 186813003 638043016 957431283 72552046 917646303 990925544 38628076 94823768 183449867 845619816 262015078 243597341 406014381 203382610 276940325 446825945 108115561 311537799 847839368 947514683 475990903 528534222 222237993 309275121 175711381 75958467 499544887 412540883 508227628 983136766 996590895 952362549 741523719 856868385 104551855 777708603 390997215 180191672 461424979 755057499 567551929 829389013 546248316 236384664 948720934 871927600 209808212 119646536 416237109 118306426 255104677 649332151 167832351 273919982 594802910 406700972 824503558 152025334 322710708 764608246 649755074 944238658 981222190 140630948 406568196 636493924 850181297 698906413 869814045 444496206 350325381 494682232 143941963 755634030 430002058 886002001 841482451 154924007 267368730 315503103 379250939 807432349 773773017 425737751 321607564 504199544 952163957 854366085 902828087 702258615 265533455 403183035 440458802 616350177 679391064 84251032 403155740 718270188 706778377 240931042 218083753 364179010 657534692 17325443 810797934 796793333 178767095 405147001 271472542 880737233 470769824 479398534 118467113 755847730 253650489 699396624 237642361 473156005 379569706 953135639 183868873 73293231 629212262 557496241 833309361 51452213 691416845 757378033 515395056 313007263 567095925 584607636 430685677 344878712 107084620 164048413 58548735 183591530 258281168 995537844 900783361 647046459 641261715 179366688 339391366 388210379 87854819 523818068 555597070 129973896 190613305 929514959 615091546 856178724 598060895 612675226 860082719 694379936 989488696 297211196 857075575 480574276 627025837 642324621 88221731 478875474 683048785 986241859 455132446 974135348 491882532 608697782 780568037 489346228 453678519 711561926 266395152 314034044 129725206 483568417 5099917 726502898 873062562 635684036 520079692 613710588 245667384 783907871 293280673 454452768 645347437 462867410 323387066 615789170 391368576 909373932 412740440 374704129 988895168 6572343 115049773 167577286 397047866 874043996 193957141 208963004 890477282 15749316 133254276 382831525 698142448 764863774 696497062 914781578 289973757 400438549 243769752 635393364 819387236 194703407 394719332 457744373 262998889 418374030 535444126 906135557 393664376 768429220 444450131 62966056 583768187 375744537 443641519 955746006 183388816 500392025 514383537 812702546 933155363 990770807 895324069 990081860 775139928 182581445 959564737 359526733 358750727 476889811 357408377 808579187 343708478 289099904 474791869 604898514 513058078 87029659 836471536 325339348 332023568 970476717 925056683 909277954 796779328 191312052 492182341 673154228 369427484 7132657 287484067 141016881 197263346 681286442 820503571 692139040 324237319 504755685 367329346 522917419 230976964 245963376 977972330 116772983 961255553 72113955 866596194 860362588 507755760 637793188 648551463 990224142 276950896 119237798 987973391 307542075 261583644 286305764 382803752 445623258 256397234 223633832 723877871 917759568 758163773 462129740 878358675 331220188 571638426 498171809 734426790 223156812 988214898 859185035 905793997 403709649 929923340 833365349 269180957 290085003 751537240 318322659 245084673 487615234 542464202 598045333 735810785 156176800 28704586 73943229 797084049 623432318 125446042 964073344 814417094 496693217 653926946 799191460 7150787 408807910 433348497 46277095 505607270 223893721 5846710 279980026 926406768 886578691 146152347 814132123 647648426 156700844 905466279 379833093 601698678 890197672 898309371 356525940 471321018 178938459 961158417 971040886 854567551 742766641 873853931 697608425 200984100 164498328 32819466 336885984 108685194 166425756 360194170 200272231 977213424 219555457 741605097 128289458 773030094 61560813 129157255 803287406 583579118 358903115 361320166 238307091 880109939 703698900 346484609 270314747 905892029 365721846 199017581 569394795 274645224 945049182 680116609 68442314 375342038 361061804 753879491 21838363 964463052 692879154 567780607 253387414 117217921 567160132 683184289 265723592 613873960 176315411 129583732 532314961 996286213 958276929 356657557 716640212 160242158 984520182 512842380 704512124 240514150 280602291 149390440 856886198 704896088 769186175 14847219 16294408 516256872 409410350 676716576 301053853 572403340 681021959 774113936 416200990 59976784 252490152 311292878 703141988 844184688 781007826 404583903 797977333 192619457 238716795 340219089 26001720 182484438 732942488 975386923 471704531 776468833 156559670 205589058 347710064 877685336 83097560 340135054 508482198 815254655 837086227 615681852 421970145 37831850 746801080 632019632 356375106 894328077 930497837 532050053 138106813 555047141 984898819 299319707 325258179 835365725 955882734 561338877 236691288 969454147 166462110 393542807 197234588 69298110 852077058 478460341 458670427 173116697 355291675 628003398 339231526 229475408 241268521 767067277 874045023 432279682 482897273 842610698 384993714 915544331 137527100 791693996 86413732 679681129 33933496 485787818 578179127 836714039 276188375 740399920 227870997 992881763 929904901 229422885 914007692 938748268 697716494 398304747 541493791 473822302 45059774 492088148 580939842 249565259 506360950 59697838 77301005 404569899 308184918 134768227 827805690 4192928 195316653 548172080 749115246 461627348 857233506 645720137 997342796 542154577 741686682 31375582 390051271 796500759 24403000 25875336 334693885 715229329 265820418 782625830 935854547 443376619 422369447 71517691 93850795 860586443 700667213 510263655 851099894 642959812 203152928 235361229 490197287 610134146 256984072 504945513 955592733 141289073 795612605 73474062 953570982 909266974 128884398 794859334 114417403 14648972 839379785 458086344 935034476 986242090 60345326 236990293 353643233 491941395 876501323 661325671 73567096 862785215 681074734 994275306 870581358 662562896 941972367 518617703 825116398 495200280 894124096 502034343 724336090 373169487 178089065 303125685 639687002 535055552 857132311 558774395 956990242 419907588 951141867 201366255 4701156 702248887 624665447 92547111 166098196 830668820 273064566 761370561 232882129 846478830 907079617 998448001 508641456 802890956 230120472 853604085 599048905 30488020 727472413 71378163 828906654 916660117 991805272 763098378 153826259 216496278 90585726 822269015 552395900 517064754 447370773 548152359 56104121 741166120 317333637 704319597 472820821 798616901 299589411 648853556 798804818 525440968 360995775 276291939 764334209 194359127 345867774 603817766 534703475 377158631 525525234 620202854 720389512 839996689 832749754 422186515 194547934 371164470 752319094 479834500 159953608 948709351 644926827 336112025 201588915 992594115 790582840 284765706 975903084 167538162 401635369 465175345 418545710 411493047 466881041 578275876 745222347 117260063 24623591 247548174 676189610 769546694 462212202 403265785 35274570 979612055 354277861 520283724 250662539 118896998 916789780 217573051 546951926 842224119 590665101 301345571 800628464 213500067 333932984 736203683 598031369 244947387 936500577 346198791 175146103 933787804 583935851 82952931 153291631 732989934 419674532 346636791 289925849 85377982 886613009 617448650 901632601 958769776 333953931 491050326 826341098 83357404 538226567 57154120 885884537 91479467 350537256 10069217 23615080 247905548 507246379 19601595 652526641 136812121 58511745 587049532 817390882 114523673 632347872 274754277 394743432 178457051 569136840 224044233 995072724 28566872 240589895 424604753 238801813 199541426 78866768 513195858 186143715 774541767 897332618 497569466 813611317 753759830 241899936 646066630 312226508 581858349 358535294 772247030 966585994 912414576 385217765 387764055 394180037 502698597 620188875 842161007 150603457 720861927 782810260 42581064 202559734 302101323 467300667 994780265 86223804 159474371 567259132 475697747 374443830 554205588 942149313 543273933 821649763 3048801 111064432 905020554 123659103 872111522 965507105 400367376 935038885 715790162 144575733 306353991 530631555 583073190 435703077 770235642 241790067 829667847 265527985 401019817 57595977 447527172 835750964 887618631 804454930 181449371 981540650 475980111 374001773 132207839 137667571 759421441 341242348 66603506 509221652 776630689 495871290 168280501 777563121 807859266 526682267 182264253 336447662 963455169 192985988 903722714 179724162 728867478 452039848 398644203 31025614 482394659 458103304 75439781 662067455 336827227 395455427 849691682 895955066 284613119 239729501 42869483 837252472 293206341 579446993 13783834 375106636 422781273 484112260 680127869 637879942 64332223 159269654 86970994 695789326 628334909 579845329 652480243 703880949 552926209 746949174 559776292 354757221 141255036 18307234 743649656 334103246 597824414 484443614 975492159 226094052 488445424 959799445 742715250 630023207 886193580 140218279 106886026 803107736 763965583 743513404 252143013 215396247 744895669 310609117 895798277 379801496 864404219 693947557 636653776 445153400 388288273 355803602 136251767 356706725 135259786 77810570 840330252 512060929 216220605 683474008 25604777 738748905 921595010 627888070 626066198 915305173 115832947 169944892 188669503 27736829 473582129 150270403 73555181 876368782 222215244 929872297 806468373 509550656 325824916 464854764 371308152 258297878 347771713 646513711 202396755 878073981 779632039 929027115 653646574 643439855 919604011 945077944 871795425 661558012 367464087 384757619 915367954 328893846 10880233 215918093 152540964 434074259 611434698 663212084 787154468 889680629 367418758 251243156 161052239 552254557 738667882 94892987 156069927 98181847 637168464 729278342 391579798 959276855 2766225 133874156 281151015 564077353 816470336 812282107 292034693 77990941 756933831 363338331 669245492 563019050 399099879 193816275 846956554 329106859 192835977 747226390 108430408 243438106 299995386 40961892 544994920 129677233 805568667 931841999 603798917 158714148 160934808 686655619 345549744 89877197 386584220 668567943 405733837 853177622 581182696 992426436 850132132 58657892 632190607 447380893 785222582 585721420 890388194 750054436 619791318 419133147 89893187 63518270 966719589 105127748 509739759 346502838 718838845 662755840 511811868 135196616 509828122 666762390 274669538 660109669 303005664 98087997 748644111 717864072 569804877 419863385 650283804 828307842 522202713 199947777 900014347 773105437 863635605 877226608 455036675 471463026 216311082 632414103 237322398 617930888 581612899 753704358 579929119 456826944 73947778 607319755 677568393 187088094 275546316 745062294 44036596 961339104 76988515 230105817 949599607 54272007 658723447 845702095 448432622 233214940 706398765 77471484 665389946 823111478 729610202 117367354 313892690 197900802 552491211 447599901 492953804 168001862 293722801 164222384 265517680 78991803 371422518 783857320 853237450 157712713 281880312 480335611 95364832 340565696 473467174 994944315 671376630 393536142 975563329 960490046 474456449 512285273 231910298 833960371 750140577 870703165 712709868 187854971 115789398 583393852 207304457 885021218 217025522 736288210 896472976 747004970 697714531 493641691 838692629 407210543 181560340 82487114 615419674 877778300 357264999 276324532 855753106 599855809 932294158 355128893 332320179 844611127 78457264 692356364 313695067 696859979 532803621 742090978 199866594 616462120 441057948 893116717 228372750 378516529 369829517 621209302 656671871 664233513 78938243 595137467 699525177 726109839 76322819 759838299 167671362 229881819 95132418 559735388 663941297 975892516 462862352 813943991 127095197 149700400 154670182 35175833 224192434 553573892 101695386 18280931 55449070 29873501 946386827 601285027 158095376 618191106 50653732 356099431 794084452 538152440 223973680 828811977 79185681 353906408 75603178 740777848 389612376 408237787 849239901 450670389 902872827 612701397 403094676 147992308 369403220 464495208 170966213 964514968 892706403 579815051 36660667 780604362 810415121 898013693 316672627 432866683 77590153 792458933 358772951 369262637 327729326 731111785 433436529 328106740 390515858 330616671 740996629 603901322 293329044 279522857 771906934 670945944 985421322 997006395 343007019 819812169 855639268 729340923 594186795 169437116 850447828 729965185 55798482 327238379 445054126 2962443 792997313 745892325 612739354 747974932 340914090 548754014 153016934 167085586 99303694 811263762 631559559 211552598 617101545 257624431 628734202 148697435 425795821 59524710 656056860 144119758 253720972 946671216 690903043 797064353 948987633 737823526 525791553 572604511 295145141 768175878 97998503 768353923 340308975 277686276 166953637 165957587 512217262 398528283 265472310 472303663 783677364 59300800 247677966 908916177 993398390 263187359 908190854 814279576 626531333 244444743 520169397 208007093 220045509 345826826 526462807 631952762 588993326 820994617 620526770 388859099 970098650 666567938 317574383 252636183 441459648 228834232 127517402 423905192 193602430 933540683 935589376 41321243 564417866 557964652 48088550 973406365 637722619 607910658 343708951 911819044 937208677 784383456 65786351 479332219 762753886 354640379 605954024 638705490 495364149 890532444 263371293 45049012 545505073 757495462 30335409 349643477 337768242 4111395 575891882 40849951 707657053 47197861 648179314 659064453 632989847 521598883 540352349 332335300 109259434 365856564 858554666 211462083 226735913 428312722 481616440 249710206 660022462 730797733 823508015 273785391 567304540 558864761 701435146 799226028 99207761 453012500 339895094 371508366 749977253 71801356 773737637 651221123 844731031 33537593 76486227 846461236 595513333 838964167 647582920 484182480 128535533 530893252 454169519 729387444 521154544 854859399 768231779 430099867 538804582 947774790 521032756 545071286 9077685 855717521 981174973 38993931 887514760 228376495 193908750 541178503 924906540 41699623 942367490 506048144 607889672 567988068 361924046 517403191 642561287 114487452 751993445 798834810 534182997 622195758 993587668 742956170 119917807 410771605 854064790 815484570 563412125 281736969 341774432 925871705 165044966 441228120 366471419 259809108 207951229 821671640 749580299 552939543 264996700 286783552 289091176 155872474 151772595 952735789 810639337 712378129 95213787 937246356 605341941 732150499 330228198 591257963 732277101 507916112 242554987 999918752 64229948 261632172 375797313 371848885 751988698 854377429 294658734 477083895 111338077 156661606 856713458 492062810 347520910 582530999 335287011 699447883 562692684 97926270 579304554 783385528 750870621 267575310 548303662 284647754 281456037 713614375 488500692 181678266 946327389 894311400 75817792 654329196 78685938 282071765 76052276 891288775 278785546 341678658 251182846 42816881 740290469 958705455 299699819 245099794 304876878 879540587 618930080 584655409 836968308 950679310 983090040 833570777 195582839 616799122 13058831 276350512 511714876 977461221 891699745 652881024 447443551 149947301 239217157 208907101 947350497 343588467 439639358 498297798 298280743 303141378 520255692 155209101 355719119 744219313 201434186 46229871 928501439 178313798 739540142 461035335 671385963 275857147 709476678 877738553 736514968 544678255 980202330 976032282 26434699 763237121 483920471 84640499 301935214 27421048 337689369 467610797 883296004 142514840 647967465 480123645 168772900 329741069 112059390 402254447 105051373 436071208 556992679 46380420 773650736 960987612 64777974 983657423 540317710 491715425 596533754 235715492 16374574 156949854 36691605 888467374 461398599 987057114 382744868 281297624 594010613 351363601 737970628 23434710 68127540 990466561 687986608 436961985 784974410 505687545 728542750 238874532 208549195 841170501 446494284 109882239 173171292 366182009 865090284 350638315 667742485 402367456 807248885 382742396 582986658 604660087 697780429 236835667 695632073 509908047 333303606 242098330 242911273 630607229 869261228 436402694 836619987 683612961 751687859 537609319 747280334 186875582 23676841 66904531 462119050 138489025 567042250 294034443 456457900 477397678 189996423 768964976 685246610 444882657 764609729 153833485 684144926 6325311 195540770 317882574 217100845 369179584 454810547 168572356 724441083 998344578 608043225 855023801 500897493 302754308 38259320 460321333 215907202 466739222 396162557 16590857 83704298 546730231 894400645 679930600 257592506 3244923 206461109 463353562 533245845 858815556 250929205 450391818 16607984 757828133 401892491 624947969 770689048 952490071 428665375 17178639 586300815 126235467 393490250 697611545 135364919 246607780 266725660 983229164 806652255 152510223 642556139 494113854 574703572 496208662 920692592 721239202 712628503 599224310 313382663 678942477 849119090 591666627 728764579 524200508 361262496 65011677 998218773 690660918 36406075 411502353 254629819 329372900 784841531 5559683 901514413 296506507 430309188 652761303 322424092 675696613 858549096 38272656 702932654 170509858 366750262 830407387 832960432 172728008 923568401 715427282 479922417 564662128 363570625 290155890 455658102 989439740 681511294 544678099 645287832 851849228 540166199 673208605 779819348 81596510 116973970 385549065 358167852 319573892 110864700 479195609 516085981 255045836 231818599 220644113 881168256 203572394 990805432 611435070 901544988 872832656 725630505 110930951 609105330 188870488 347275988 578346015 326121463 638600418 415194848 234758953 113779449 169163003 789772457 366106488 543730088 249926452 622089233 322488099 900890365 474076656 810567494 304437703 388079008 958174553 988509366 360769452 36610267 262320293 989786525 868944893 401016539 625766703 921807032 33566086 56989367 180711382 186618296 462467383 470890704 746698687 149267237 968239250 190266575 315787742 347931326 453697537 614217388 473844582 179467432 285913032 650375737 289463576 900344238 332170738 769883408 730338310 206308161 763750198 399121486 851133770 776881698 671014653 992966464 438543762 26191807 2109319 918526940 834033744 5934070 418390829 729072567 534984587 977543176 434563738 166316458 841474832 53036890 831245615 298485761 321188610 985404654 946355760 503327448 979187556 346499538 341503545 940278539 244217065 383351404 837205008 942978933 691687659 94795818 825178533 809390121 381704574 505820221 291116727 484638003 520822646 409632442 741567421 303911771 258709309 61645933 534517933 668565685 527945979 496484216 654140203 552442272 205661605 804079213 540637418 374794375 143666731 549427316 271305262 253553790 162195785 976511783 949141442 80181979 899397222 511639884 542589109 148628848 100791361 959888548 568824994 302995621 73595732 68186096 895465821 590049288 234485479 426587569 592947417 260189008 99471977 333093051 70489273 205362684 593932281 121493258 779558445 830071274 593548275 711927063 709460936 191721809 877021337 639771036 597662180 625250184 225727618 536060296 450192221 517208036 444007478 966845254 641695321 999823366 60657510 52523672 350267320 582316241 609671161 398800617 454510198 223334247 888507184 550871783 656655140 525038434 499415165 97060115 571573892 593170574 888363638 706121309 161512016 594486431 360135258 877928412 267663260 7200756 437408318 892342149 38413946 496287011 883481426 51982286 334087876 433253508 862274292 651994836 119398468 32097853 365990111 2413243 62366353 463658344 32045637 102716709 211328350 29351090 684307012 749201902 258356293 308098107 583447157 356430468 237146667 171806300 437933716 420327705 849065103 991878066 462786794 24702492 347938372 797159983 279020949 39858927 170800305 11961973 351789855 325008744 215843497 92075355 898715572 264271691 408753636 350645010 924889076 970565364 510700265 753192510 845885986 477603139 469799485 837709071 114640809 695059688 396304277 964634238 134586892 259516604 708562879 723025348 667595218 299120905 461981489 237264682 814883062 742178084 511054831 606477650 472954378 748579643 518729057 575921719 103299942 109518817 334927881 595247063 178995178 875805736 482981066 330530172 843719903 697552920 772620681 964493936 831890377 21274171 14170651 812540078 576604166 289329050 379237533 863215843 652253374 684992594 995947333 565481123 614060268 87722628 973800298 594633111 983106299 410856981 99238751 813655692 158745660 180705233 918913725 887987569 579885360 27747386 389559497 625340171 18286970 683874454 834549560 87224057 541262570 878164261 749445800 346530522 828243993 696487527 526978498 106964990 642709436 624094962 571227185 738732750 380806924 165961075 943572951 175572788 14410002 167314398 459652561 833523177 963612996 14777456 326938601 69008505 717974427 964935849 85920016 816953305 595668423 338222330 649213328 482902922 339146273 488300196 691985133 167850959 782258705 374249562 420262642 790555447 803564404 390546240 340471383 58946722 87370543 790376668 859063814 947938869 338704526 269556022 322413661 234244875 69982766 613334866 481257990 28652981 756223043 151536255 383386019 389431590 981043595 833658978 839619419 681525009 379750766 60243407 170364231 463974599 267369946 534411952 303124211 826592975 476896379 132171664 839652721 335953048 700032411 680040833 153639227 754240280 678355516 779823665 777042517 818399280 385784085 156658731 926794718 443297275 248035289 356324174 170697725 205959329 585267526 174763236 771560726 984075259 5549966 650379572 658263163 913745355 388333402 984052682 413437218 186652538 965902919 118753138 805896212 86567636 515241257 568807662 466326356 362662334 906797676 123484503 754307562 521459007 40546285 274871128 178329565 950419582 952455669 288990161 498343126 706254838 84603688 546916086 846850699 816471724 747783570 278960841 866700232 375743953 740531219 443251471 684617540 654060140 337093249 406845104 279097450 541133240 44287289 416145840 701847005 805512699 228403352 89557383 281319240 759145621 290415853 715259721 155728688 752952998 844685259 648460917 638014268 964989272 755428576 922345723 939022595 109841492 417712587 19043832 477588797 90193547 757842041 7850278 154398710 907943553 673074385 316676307 358737392 244883790 366488005 647727918 598201519 144433490 102303841 530050119 677703234 99909887 899263031 502485302 511710468 170558931 996212800 740937734 77237733 277203368 670846559 97111121 77679058 469657278 360635300 745308355 952840444 675352791 17765022 837269402 290716390 624694368 693943412 462465677 71211114 59738865 818025194 109421124 663754658 690098183 367526672 824459595 689952470 537057328 828718906 411242904 345497343 826041204 797906836 218094399 574603476 809617799 388140026 113533545 823139705 525055418 602841347 837623042 222557592 219871056 24821208 549608792 803252874 626499189 927269906 677163415 555868985 36949494 586141615 746227980 401416716 365517715 959011577 884523768 539275612 450106630 718867864 345992900 652897904 518781643 544862700 336993107 263352538 178360492 351120813 423855454 526351492 153860837 693366101 697447112 494531398 290578216 794544888 854223494 938310577 86502640 190229166 457290961 575944059 308242764 466570955 631537966 615181439 128214298 523531741 15046308 741069938 376315646 787523067 583214128 386181479 437925019 167598063 234698589 786017865 967483439 379776049 24884594 684418996 239490687 68170855 742501252 984146494 705001636 290502696 415356632 657864089 333906674 542529777 227241229 221078204 216289114 847976017 367806366 419185937 771371441 247374799 456335388 125873532 721431725 889943998 759704453 838126784 195336377 984207216 699270144 245931858 422486639 996463178 134179408 615457538 410708081 845013189 231574238 837070179 391239262 821593588 416614822 198683523 669873979 642347816 341545964 249240774 189502829 93278495 770547194 948999292 569406825 315691955 237811083 979834697 840388234 263657805 648373310 757856503 573645450 804792067 870956980 567932654 7879025 938433992 520366998 697921068 344073314 332086179 544097358 131299991 771998002 564321897 343971594 520309931 753712397 555142816 750242906 372103303 548790911 748366375 984210576 453404728 285455467 886767499 764191776 281997366 484720609 424270975 294462995 468920555 294069309 207609789 788243833 851994308 240461756 120012189 987972622 946946139 464827648 111889326 27001964 227018524 267915873 493066598 523979516 225652273 697031941 576167676 819594045 223196569 618408293 883295168 852461529 194551831 152932482 459580701 350549564 916706280 522639618 880926383 965510176 592458577 35956270 146710547 564252898 431558215 386194070 412173199 418984982 399368154 820841913 465393146 552303353 7262405 19328700 707347147 279825019 293925572 116250007 538588741 633793651 167608029 141441072 770379045 220073313 697905380 116189500 43487734 492929869 287447203 991479278 830230245 248935146 504187837 932475197 182913129 772693540 768410588 704832649 546442043 112579105 379686473 311857704 612119310 851138169 436706158 130837247 118911207 660516527 143856846 437442640 636282182 144672707 156550407 31549529 774443565 369698628 13361583 355912912 147201800 758901911 495882083 97087989 432803969 802223067 636576545 36222605 251280424 420538613 157141130 217693065 361499950 744803556 13925762 35493620 525398363 317193600 664370532 908893911 854914055 647158146 620183543 328431337 477276027 965255586 503955940 406363343 883458700 312476031 762974761 513317754 867684124 766088775 350034446 974362450 446669332 282693245 800369699 199447209 991871579 971237075 309070582 770940086 31464996 178141659 403091325 894156586 288329474 42124333 586278061 940464312 854977697 863333339 828343835 933207054 143145662 838484884 856646603 455385148 456055117 423050694 275007906 186049876 951082234 482507512 418600805 293667911 788972780 104357760 173937116 466461226 603999930 942624068 677629567 982187606 408505529 722061581 771913938 418953262 753783811 692583453 544211154 52674810 50694499 619231424 619891348 867076951 270813285 837349999 192675340 156225178 767257282 925220205 539440738 687154552 975081680 755969754 197877183 486364986 421311387 475353755 950110775 486382402 177645692 644667189 174416420 722112606 170285197 931524586 853063802 304557357 253741168 470099751 291615386 604246846 855069604 115143743 267434167 68827373 533725654 369431712 529553290 369525090 428234771 428568390 269116826 80646206 360366378 359526559 678527243 269832906 172625672 486466526 285903594 150055557 875922972 978177600 429999423 386830065 822803163 936458243 867870400 799144346 908428762 821315242 97573280 543215097 427285656 26658498 850064427 115140062 631718248 355772125 883426398 393462174 744080300 51398899 253869638 687059907 462203430 777261893 920513155 415094032 733833211 970317971 826915537 476090565 179258255 375165866 162610229 698506532 745332268 333112154 994402520 79382561 479287983 430928964 411041022 557933291 699298698 41269171 839736446 726710882 659326891 768804167 628668210 67851674 316841630 162774853 916188076 85461151 138624114 453384549 97932297 846763121 132691830 434517150 78717412 524050668 260625563 618165342 906145459 830794676 152789004 553773857 38442849 609074594 354506259 398799136 896128028 64107664 724290785 110620491 956227950 491235972 88263376 757233761 910594262 297631364 870004362 37455954 366288623 514308822 354770158 525241935 25572477 443417625 513854575 525486531 501524377 424387125 681953933 361224776 194561360 734507572 188305302 977746497 790229457 479168522 912893643 640810200 694945745 141079820 470758873 678570716 835900240 665937692 615747697 318849482 719279182 285920372 479305389 869713442 352963679 906685768 703607570 325870242 536485583 596912343 668885566 354401845 904570221 439340176 764221062 681962529 358864377 564977912 217571486 322166348 284038417 902114766 185689986 447648588 791323598 721557836 900114167 890503690 838105908 853899621 256717329 528300327 810409360 305132753 146505362 531033422 971051853 804291289 786642079 742802788 131330819 63442300 303640469 75081579 127893084 55003364 415886420 254576521 736012070 114457169 501504623 785656725 694990499 948939459 670556119 335161603 568680310 726749127 413089264 126134236 171559771 899051693 829690026 284222164 19406564 81286596 306231200 125612103 13080840 452077803 326679426 337062382 176811761 159077492 549965913 469802454 435019366 947310097 781985759 460060203 126134241 996404542 494693856 409185650 881524997 279889352 864380787 573296289 456954591 213936951 889605032 727366698 992170003 925692075 84528136 334021543 138982775 468994590 616092604 152928897 694887915 993697738 289445648 181899027 316679861 778090302 524270191 855686807 235191148 302975818 984335493 939306116 283254701 450226738 828181497 336407553 171162951 190682686 922203879 453871592 513547272 788883006 916665028 932989699 444307035 126582553 581759247 105796758 689709061 537940851 856675301 678592821 948934994 246100576 260240576 672175022 777348792 743640149 786866526 585917195 439966267 48595295 508938023 868876094 333109374 284442516 153703407 330548989 767946022 747004484 81332075 183721187 724448168 956403473 931982376 483535606 679247862 84355555 546210082 790888417 33452139 79416492 837905740 677911628 775537581 292778840 668966598 654462004 957029318 38997929 605454992 796966469 458710899 687483954 623703557 650558975 203298576 588883517 61204200 649769201 770717077 286863463 359659378 83626188 184438577 412892085 36188140 725723657 336827402 12452088 538675923 596753734 473184199 465680696 62436465 653207622 888387050 360288815 935336330 335394905 69617207 676209187 614140618 107035800 951320790 657655924 55296702 476354141 201520132 758040566 609667921 862580 526778105 685617790 252785840 525747257 393350803 873534125 881875830 968981653 236009736 115501955 217808565 552997286 782499210 130670723 365887619 351631914 770198934 487462774 42726543 706495722 613870379 91705187 972557214 249809457 182536126 855957825 319390747 679755914 246546281 290776292 432205401 821176889 672672692 227746006 794875968 565937159 909474857 240883451 856598735 572382568 420908864 405910509 801461050 579392965 376754470 474032656 749804031 242285840 634271066 842097043 722533463 61482354 96789362 784605987 98351152 481794735 216762810 236539798 310852056 765483299 975137751 592570656 608096938 656856397 792864272 340764033 283478528 600535837 76634793 264970644 47539469 555935839 564896463 694889443 634538471 108005971 924540491 849725385 151528492 951446158 169118082 343862491 977340423 51719751 291807685 525846938 400384151 897670089 615560398 498340017 668340621 528773636 849367329 660268982 469062884 406956391 22887844 523612972 311679161 202506017 462369326 293133071 447171095 162680314 869481957 874896774 351718152 254372222 455287579 760001278 629281182 719693289 219888990 449541944 666458340 579132859 500401689 506916349 420697294 746681624 401206369 4110014 786838773 496603950 311606623 946204700 148967654 777481948 385343349 84734088 285979037 36101874 21742194 208789659 285942709 885437951 557062401 363279917 725368493 708343793 574702130 878985439 759516206 244981213 97701597 660556163 778190507 484916486 861950225 90953848 465656839 604638671 403241596 254214237 328981274 66958892 409425992 698693082 961195287 822209245 736360065 837368025 48218881 697886943 797668552 248536131 158562949 421298743 507246658 22995906 169639604 792278502 46509920 737968165 459965253 434345252 844797543 669484846 221817971 491254115 54356962 494413649 880430317 929259922 187329476 731678143 958322308 325545546 212038644 940560262 208510373 448434197 388819526 651433808 828656229 251144935 610952708 745504726 157551885 405549561 583052760 346081384 320867091 723264190 807105003 823837401 61517652 313969188 889085636 660454835 551079739 56406511 694045099 805943342 250870132 183781262 298598718 66800059 186657443 545316440 88709617 600619392 404871323 698066626 913953930 91842335 1308184 795847354 10266729 389306830 478669153 956062895 609034099 158461566 691920568 381677664 621150269 279940944 663084982 354305111 447658126 8825651 402998862 350346619 586230678 985860381 43179248 736585917 444834875 481136372 753553129 850196543 982862923 311753101 308378441 201970814 140328978 532772850 724771541 898795862 536426308 466648244 597210006 567610417 953845968 31243122 326482058 402709660 819499046 865612399 545346054 317508967 669432281 203269361 927630485 192883527 391145553 344966633 335011822 182372867 206114617 957235717 435006664 821660936 564008235 173652231 600719223 134615483 928028888 795335483 415712143 364279135 574719987 218153477 233492644 843380132 220100084 292149897 703263212 67256973 16363566 676107245 669800406 715549379 706908970 235666547 736820381 535101792 632418818 725818700 514222220 403015635 313186971 42846459 286908171 172421939 200625843 346522893 516801201 87059607 146626725 852729677 975193228 693535994 690225249 777344879 483718589 926597395 432515746 762228585 74952560 285235807 505913055 642904737 82771798 993392620 673645796 44936263 41852923 629525476 973365737 734134366 474380506 676011607 847888239 395014105 275352815 512962797 359558995 146821852 523428149 921666239 410928265 741055187 806440506 54406063 997927745 909355875 506788262 139487505 123411678 12706813 75117507 591025709 966745842 868581844 448580957 69742783 471161845 49119344 666706079 23854023 375940927 428468036 468896968 162762056 353734170 630850584 156197492 291560074 810717618 380652125 774998261 187079035 830530064 871816809 232125113 306284640 390405062 133110161 231575538 337905009 87078500 796351292 270066542 436156609 250347639 288927418 263304455 448993539 247290169 864018712 764323437 933269256 406238287 354450621 544592518 951431840 419365133 973046198 404511965 284278142 657150504 711925463 551138135 793083132 934772163 438776256 941863034 495609099 840401678 904948685 210907701 994545950 218038641 529968689 857680202 840377339 694628736 377333525 9480531 127388658 862718520 376775135 609583881 302765481 555495256 938879562 582448097 386522006 242764412 652253609 229395640 209933955 202877640 285249320 537866368 399151014 608741398 297320733 608982010 887620581 182210891 105284074 116474460 917960446 559099185 758497091 822172809 249328608 193571768 220526676 755428509 510306506 444746199 795333129 70881736 533321695 157838931 770178342 115323026 957363689 434863850 764219185 701789516 425625077 181621936 92165616 136628623 141987063 617392385 27726315 755265742 178656275 359100040 156209875 954534683 47766899 53378749 492558646 755939529 534611871 847684331 995200222 359997192 946073048 843124098 957913582 635863032 3654777 471367477 271271311 246669045 291930230 878380671 396770609 472886913 888242031 744126842 346480003 698021794 777053280 588578555 159046095 950797495 848412836 349831865 324020854 252616948 354704811 475742420 514086274 340647866 928858695 876418811 506909613 117107788 36261788 207858971 5782338 262381936 49015058 577218108 61454796 520989536 702963391 181635548 819133322 465991329 910860915 320379117 949300537 977390338 56994964 307388665 55317330 669167734 558028091 950348886 738940996 312760462 900836752 248788118 493950995 609088163 806854682 806391914 207570717 681782822 720002239 197961272 854365531 482243981 664248753 815069522 419781310 139658542 87243161 891251280 706116312 939736751 443213386 383435929 469158376 706461778 723281336 26404829 322789485 668756987 311588864 646547022 324919365 38697037 472334071 603557103 76469153 438645 264081574 393532241 160312538 249338167 797026830 687525238 325185860 61407764 20970702 685427996 476392912 347073770 829377427 106787338 407683178 651344736 880258220 733885350 845903764 976503910 1021892 875249215 576655444 228137219 775568623 845907638 762916337 321942330 836828778 809431499 257630148 76158491 382513642 141661071 140180540 608333780 193923837 634895636 202113601 541358051 693051515 713365676 45879259 103043734 213899229 127019821 274083155 263226063 548055203 365792158 493449904 594495668 734146268 686233162 802220583 347933246 743169570 487613801 863436412 90271337 245645453 798876853 706109121 467781710 881167352 598998562 448066038 316290162 504957154 280324617 530827702 366414530 617025518 891115600 284324228 70073674 885384205 36102532 56547441 555509755 344531280 488766006 207941872 523283527 731051942 133680907 434953340 616198497 48353843 677990414 298385453 765784262 269545082 624209723 483291389 684446796 338464934 289378528 968698490 147683081 202347100 486076767 76098987 838251081 745742577 571078533 700873292 469222454 171237312 434594091 883463375 774761022 691463245 640109782 978539530 918950386 945439148 725938889 942368817 613896451 652324083 913578029 475249231 25742718 155449167 658257779 475669323 37179033 368276198 344186456 908119242 267015061 38401052 886777912 440709317 140530793 887354025 725698153 465727319 878096666 65921739 219348114 151519693 156817306 297817862 548933113 345513850 377709386 616104376 507304314 296467596 820478560 935386651 793301357 637579635 660533293 482881227 136191771 114722105 37333152 401965820 335338800 798574878 93209182 21410788 415407288 823254231 280589413 409353176 790334775 996652665 839220534 869185511 977955287 579130751 970701204 520555846 21511602 8353117 410706705 312606954 998486332 60628076 352475729 28680170 463094363 934186460 774820147 249383267 737096438 134631261 833609178 115594495 265176308 378996455 20583883 469090148 626051706 711239534 690427769 946721061 537585294 560278690 138974033 704360752 280513588 200095011 112556913 543011501 346470926 681637645 185693825 770928107 490935252 972667352 355363505 353422100 157397184 895889690 357678024 85490655 882791300 794846411 262359984 936932918 394090410 45486255 172808131 854337203 796629542 984812003 621117513 574491496 3918252 857512909 448879506 694333871 976996927 263354959 918130312 235607899 958443175 996410993 928975962 420381290 627922830 349243309 328109983 197452026 780874934 83902991 4237339 43273784 455715519 479611737 892851645 812404084 269647498 155761525 75708494 933750971 103651021 39436567 425053791 255944964 762699168 639127645 487570487 612411717 500614819 72875502 562619291 930756417 367075061 215476223 318600361 116821561 108198257 924163910 674176296 275024867 202336288 644325743 288785538 298386850 947157517 205883281 572084341 40635396 846910270 145869472 447594657 198637178 632630256 335618433 369981461 641281901 811037246 41362381 34381212 734807062 785433900 215017895 837185750 568491826 823379437 118439215 828933348 214335172 914308251 569359338 523494495 854992686 670863393 187478288 337107091 804060632 497753872 510030424 323138587 850506827 611870123 774220488 410810017 69579352 367380403 894583953 32311117 96580840 486002113 854014488 210805052 337800276 249223403 436352145 114672598 534232381 328960737 430973258 372829658 586130650 795616913 594529987 18108122 434214923 213947204 74474988 595871007 76005995 564495267 134999895 255602904 578351463 944060508 871063445 40185596 956396781 406476827 274570917 194992533 289816397 747531720 431087642 982458040 840459378 936265535 877888531 390742167 843341018 456549457 3082552 176652975 478242821 701715174 166129001 340808915 489670134 777409348 547723275 786494424 318611843 426405632 852940543 705161309 802471917 599552575 469587017 709066574 853261328 754427191 328271042 39738724 841904177 520392545 849424549 755366179 573625166 509445400 938426744 424357049 827179282 574396058 15873628 85631541 275665514 891742089 166811816 31786183 22997072 305392052 131568985 31749775 782567713 404242396 620986292 198722861 460734653 47411856 917699028 67451637 303073303 468796534 51410099 745160553 900220070 303242229 23016234 138792097 334379641 665650069 237885758 908795903 477171392 943171934 596069486 952726297 643023336 118537345 990685815 833435997 746667545 20540315 58505017 870424316 973169076 113174290 276665843 498566884 745583676 885750765 967276521 402147369 304596689 831633085 221368541 838267367 651353397 508709121 493694905 414125855 726893188 809386360 71816071 455763989 53592088 572655225 138430621 287091777 524851189 283605888 788067189 645263542 774433118 722695183 100749769 608612886 606540082 866356087 19598437 852750531 542823369 265949628 880707262 983555923 842714662 840208922 520776387 452942979 506458695 586956269 926603755 292660666 56820638 225111948 104790328 937686018 94057555 201929844 363563527 114936418 246786987 827568982 153147395 565742134 679405702 971683608 442370171 122514174 718590104 215507718 674899490 882855060 149705264 486455026 24560251 940284429 608071365 184334353 691235140 690311895 979402461 386991298 910791905 928758804 532359313 458343747 324180315 819774615 88617351 867599338 647873303 391432448 110340485 206569704 499302374 780129450 336156735 603354660 331641392 882892362 989939687 101904997 856007352 132708309 88962120 717782987 854154021 899080759 884567238 465928260 928781616 909921713 116272492 944007899 534121406 211101963 637038419 541427926 687628184 727545823 744784525 681498778 330655898 691515103 284277584 390178258 450644653 395873121 644425467 822883228 962211833 509062631 574275398 898719808 606544305 129610234 810601776 901294192 79862487 809903402 348067179 889572084 80236790 529342279 499545089 896419221 154523218 564308490 398336440 363338093 467521122 348656485 236559434 331445120 85187526 307643811 869825576 643910630 628866819 863128473 349245791 551202966 782924646 261337525 264939139 332664915 713528470 512776076 562166150 867147010 887590382 341111173 915385787 784038978 464318949 540474725 177367017 467060180 772315590 33808976 901633398 261152897 822882601 700027333 990453906 899257155 631858116 171871802 873897816 225467902 871549381 89188880 586758054 451656104 920919750 432948457 314300793 442500331 50303198 622082653 979753607 949194350 712857608 795517677 487954470 118214930 170292803 812509854 895824575 53710537 526414408 61583443 901948699 588725009 788377672 110468732 388433817 839221319 743783906 460105972 655020011 613087857 835756241 386534358 944910176 932952545 229422793 555957895 651287233 12075192