4000
421018259 634815714 845961551 904091806 654393434 355929902 571862989 38258004 284108799 670580916 279290297 118176142 44562564 439663555 85581493 294907218 992962367 453400682 642981871 589121210 249405083 831564609 683743955 117066896 40228036 163815973 782325040 970639970 675164475 504612776 593704784 695672755 210998733 1974421 829501365 721224867 342660749 408832933 500447812 723064255 274411301 698054675 134561869 254885339 157600074 583057157 896411912 819290383 176916719 592933913 415813750 355659362 955308711 763721573 382249882 25399294 355347740 216039507 330579784 682486218 176500885 633687223 468058437 996837943 49509352 423235045 675841424 514312094 705528700 881011221 125761063 764123104 911332404 319819718 631923313 568718957 803499890 537888602 367144078 929798062 424421644 548198883 898987267 48485842 487449327 710870139 921580466 584272772 747401836 203997703 564670127 442285202 554047063 807549652 428594393 630444598 260359983 286034334 75820900 222517541 858113877 394488439 100274279 657205108 392290290 958232179 720386982 521541764 125248684 326810208 863829797 369696082 785316591 605810359 935591390 552250085 214570362 181217910 68959785 507854345 196398599 255708271 636716423 19340824 8789455 374957843 462029673 580113220 737015635 586407998 650970632 175718444 339965914 857392344 410793040 864605192 156064378 889221046 601004929 449078955 91326269 271047782 96156340 548681057 876435283 347441887 336056856 923269596 218631293 370336434 751228784 292374071 732085354 985235484 293644402 916302456 211089130 958965085 5599761 851393815 753938858 913636469 167148155 24341885 134166194 284751148 677342743 174722858 830716438 578695294 253447777 764776232 369886614 976573944 742359869 928878039 546176739 705175365 590101169 438604084 123161506 61306403 295644895 382550400 984007222 105560102 421869537 115285157 388793988 499252687 486359632 617351809 277687581 1130742 53190451 104006661 860373216 502741377 420893228 480476399 638463959 777984013 474348188 996236455 754137461 290065702 526617254 172161618 299352457 218307924 177124122 95334675 613608279 593913331 469904963 599527228 32209369 501500896 786266654 925182305 208876332 961481039 512922805 264697884 243293724 205289103 208594457 294402597 922862188 563134442 300170578 937974245 646896840 67663339 884733789 499537541 954169441 219727203 715624652 461478148 149269255 729753828 721315491 577467057 473408786 330976180 56087821 158226292 968945971 108904306 788709528 790380241 313741470 71997078 599470695 914330249 451741021 71814337 331850016 731910486 423122791 606414793 741117138 707981374 665991932 24765518 637801774 275912146 519574975 292185796 258285782 661709349 388215109 42806816 626964651 631630497 856922974 549704443 7836256 42738215 219649123 133998622 613003307 714937308 975981482 976149807 526723412 983231686 5572719 154689880 506983764 33987230 840037630 19140028 632497704 786726813 419304196 884143262 84866528 613549679 442818735 335001231 369981743 126538075 983957577 932329452 60835260 877207461 617872884 946807349 265356613 522307194 747079927 581946879 629938577 75500991 448161545 413475644 612159517 848980692 914313875 72731477 29264763 92167353 836282173 159898471 289593879 849478393 223931165 869032217 241584076 967161676 843816722 597219043 357525861 876269483 499432460 845833860 828218675 521226208 4571690 295491098 438820267 952445830 660073647 104176947 797723824 638293492 947852308 957681330 353086038 648712372 754440001 917293744 955379306 729368782 130394651 91675250 847909050 503270648 622516701 730717647 43474109 719647117 204539330 567503792 191946834 343636747 60933775 185635311 374224595 980100980 722047263 606472616 899653772 220526650 381067909 944547536 870796034 645508534 686513512 426857489 640365418 543174197 3826792 499582749 958798378 545052260 112886438 63074408 890300777 721538709 861899644 535592921 258718182 869082275 321330857 756698955 795624887 320041796 592672947 680392360 983193390 924924837 362176920 231095802 82265977 433095979 707867104 288025638 199659791 852971047 994353542 893575380 760840502 561830636 358863042 629576109 625807734 550588718 208228774 594977773 906480973 775072243 893943106 970063448 806337609 471719442 188114072 308797553 191796101 124994222 853044665 255240048 294340139 797782114 44148101 760179783 971700904 548145967 486237249 868153135 693576589 685305220 837527526 105922509 454007105 841137513 518498820 84670722 47065934 608420446 431156476 337442283 828518977 859535470 709278192 760246011 189319537 850318426 526214344 778235197 692795405 50978805 513418678 338522359 174872769 69615947 494037405 257923193 475686484 750342074 559774642 506706019 117314669 698553902 387216511 88799826 60515563 171724106 477181978 800081944 308527262 400855851 932579248 752028766 692806751 462612771 955700463 128049783 975980920 88752540 293081467 762456137 537811758 189986488 743284383 746697802 687572860 215677770 138870011 213305187 612437394 850448894 666809267 48833277 135126079 436433939 851511173 228560740 379611400 16897257 88643385 723613162 564588950 906201314 781082833 18677735 856124868 447895843 678352533 523498634 900505544 722629343 85531316 424838734 290560736 66637748 70553137 528756313 528160646 800168514 136378358 368551537 496184545 488979836 710412443 995450648 839352309 260030160 315064541 904267069 717766816 742589840 529905378 537940655 784935039 144979403 560659986 334126802 697266316 436246460 379600 708807253 870823184 598315995 546769678 237116437 217399313 322621782 702926787 474523998 805731741 838241681 65913776 60162618 177743881 264308827 838585159 912637106 432211682 373924152 908199966 723459843 135164745 593398051 149248066 437771624 93521364 662932794 768636921 638986226 217164624 835498479 180999313 541611161 493814633 675275373 897614143 24475856 56222204 25537708 391131971 457897063 660986677 418357541 997496381 303034927 143415799 351368484 686703230 237918227 544258177 992913095 50602073 759517420 752000660 432091658 602689028 222137762 12032775 922354521 938780069 326611991 165908401 353321718 815505539 449896370 139749234 640309629 851026021 152636898 959486444 11425095 257852064 861789186 78631189 180399077 124220639 805105450 704603068 79422217 239635123 463913407 633917839 291632849 75875806 236424237 531785124 80741174 421376443 804139024 186304138 842140960 894481661 323639952 165368611 489870579 340957717 895503738 982986919 826220910 127310007 191982926 224101435 610609597 103057027 826413410 132902880 535483323 300645497 532130054 123403460 216703115 969169695 719263040 194141994 848290570 455464665 261931833 415271389 101235599 189437147 219344681 197822958 48835147 510134242 663491871 855102835 202871127 490757921 83607105 415821703 633051911 734213391 343946942 225101228 448733303 553638543 716252067 28500817 222663097 648804955 275005613 561964544 602446372 583577526 895986500 471897503 570718519 906953259 538222973 479822771 401703828 627630589 888321423 191813218 506585160 633114241 438174566 534921491 147609453 769501529 755112857 231953041 448538776 334814226 754349826 167725286 648001053 696086077 635744030 631373248 477025351 255576463 825396219 795895896 332058127 871750092 982635782 681627806 899450083 439715589 16795680 822530824 849896456 507080766 198410001 291742984 332911131 605814853 778665738 616919641 162447801 3720977 994974328 823903730 293931297 66970765 710525545 994493182 963776350 558283668 531011363 819864599 888827418 661676442 986129225 40143865 650387526 264079222 335893376 870869976 113421813 928083339 142013733 15866328 557897184 351133755 456101255 869748714 335017800 335670595 584990763 533471613 310960563 3267247 122809257 764796017 327776718 675926376 903158972 292971908 12972153 932943178 89974271 967930132 447963123 593443810 966380011 702451878 890286355 499436518 25211035 42606450 127160113 891946122 899691905 32055768 990547098 895886466 180067042 177514358 149124068 741174092 288704072 429294317 30052410 507590607 234104064 493083361 403339131 722031859 442014601 368480947 542930829 286650748 36796688 384247152 459480021 964630138 982182998 655120522 648031044 811799398 314243734 704357619 649213125 475228309 786197015 11735852 527619617 592294527 889200711 350213537 510581431 302494873 655086238 861914511 33386988 915226783 563370430 231739502 903086305 150741506 163631244 615517880 315946986 935208468 52824035 254175948 423814263 369931606 963803717 437206836 545782463 93001057 126433355 960775328 415667957 621334574 469878542 343448931 783898605 919899058 414261109 91311827 380937487 198189793 601249035 655296288 481186980 688189071 974946386 36243408 325893414 400245116 628302653 459698572 407975552 737542117 895664984 327792961 50127022 57493412 108201616 435949678 370788288 186631874 764288449 760101740 67891623 297744446 582960368 543149102 658555203 59642191 375212910 133160456 564421438 860312486 247718842 93200008 792937040 78510473 209590933 358719226 953336987 141245073 706598729 360644071 67493542 734024096 312166368 774437681 958157530 227237280 66377240 139381337 923490999 878386702 519268517 926185494 454917656 886278105 394958414 514676813 523454974 433720049 552007489 711859964 240385319 173311844 510023590 481816911 855849113 113659185 460647910 11842635 585689452 968501955 531624073 517350732 172864266 427009612 96912084 669033508 803428334 283659587 522937781 51259771 206713411 803747911 373146275 319123552 166154425 609283825 207202067 30515320 139184679 557310148 287941367 556506046 292328471 766771992 856823540 996998470 93725081 952388420 868987020 793640933 621154604 458194371 327820365 660991114 495127204 585404464 192749557 910873619 465093473 703434501 981758535 14832332 276294863 428098387 521221433 108052729 554520476 734649516 887066734 326222706 166197938 50368590 805247349 936939322 636545951 436078198 669578165 202084007 873528234 404493577 227629519 720235532 743515493 624975271 381344538 270860828 672928594 909058872 963700320 164380729 94888515 199890308 666441968 540343901 993167071 933748195 57664633 969432512 72794520 110003790 638935466 292562200 796675683 796761667 792534797 423151881 133245818 978319220 107509812 88772789 209496229 487019358 218836065 432927882 309582512 900049154 949228882 199536215 980640035 159663440 366057222 74625394 774393627 121364543 164889532 829587299 685184955 251320507 70387972 598192350 988556683 813671801 644568767 962673060 255007173 846921918 506606915 612168676 331736101 900013214 294446745 942183042 876288044 512202889 529670479 892509733 6405002 967380600 876514640 504408525 122708832 17912802 692396923 201310302 337082124 338666532 450550346 355399364 617892719 973431358 561044691 76774585 700370794 216994229 516495553 651125279 251400074 622147651 4814834 773462767 744621933 973680689 294010460 25015857 638835967 626036890 223351514 662299342 853002168 790084208 33448391 575173331 481685112 792547135 406539487 622206694 825538559 7755131 995907892 816879693 736491329 827630001 16696012 59748337 449515696 40741114 452369485 673284106 281042344 727236552 452459592 785703007 988972648 447412801 256754480 233589349 294636701 804369730 6213079 65137261 593524416 778993018 872946713 491140244 314481379 42077780 920169714 630588791 664699983 730527662 586500913 246463401 208661792 745846992 501176844 964393115 95629591 957359627 805467853 569056562 652697321 664738477 58754979 666159799 303138913 492784256 424969851 115921192 730059918 817687565 207925065 660351212 339470264 707076025 747860993 304079399 811041890 563298067 143354292 743540963 103527909 595010493 222469320 718440882 344763659 993842074 260539852 292917825 535578088 930868725 874351737 473675354 733537686 495312827 611299396 964216733 820239687 506829255 310268780 806806070 772716122 964135096 311752217 349296213 836670705 264342517 559019275 319682048 663293072 256724567 808810446 60075011 153907111 319128399 98512744 103794002 159241784 332818889 383781161 384705208 820781494 169501974 646660653 739415999 895551935 384580446 116070212 857313198 803972592 16773534 234609344 176738587 526945681 710044431 858813923 686384077 567805090 573188803 957356140 509185528 706563691 239098408 8393816 206114387 671944628 11627171 898747808 114378152 688083062 477587442 419204851 314823253 960073156 224587173 338167305 645576222 589690135 159312201 841963269 802742188 595195418 386213578 227052668 400633676 960980334 254432842 476987597 755114848 541241760 774392420 624824684 323252354 424767185 46952281 676833983 966563741 827768594 734304280 720653471 229654215 748786894 708222101 795422225 779340056 967150183 520714355 796165484 963352506 682461424 575476650 592950875 152464544 988175096 912716424 524152167 977021059 535999829 709339965 327646668 112401954 907239966 358568646 7389083 638332658 207233252 750932767 378877135 938442083 799945399 278064812 694162753 475751818 754369251 689708340 245978547 976943110 386891485 194475700 261358965 657897256 754858785 882936130 603970731 525998013 866395469 909284800 735695416 750340433 246240803 332779127 981617024 424432804 96221119 484058391 503007916 472002399 755687436 243046009 532320412 765845927 564359281 215979634 10786993 88447237 842282509 3001881 371967167 513212966 871775683 386181243 497984913 761175465 338906380 270366677 737277032 710420163 568944327 268697650 218211790 343631811 588036195 782869044 885420799 95049090 210364435 52745782 911630786 825460275 798113368 38666095 826729655 49451500 575299121 457948520 271891120 325399853 988262883 495095556 334912555 389357850 491831819 175309577 70940736 180494173 305552964 514670152 346524800 444640652 135180953 914446915 174286295 848987243 471749791 58518344 525536600 617764148 162810808 503316297 137589655 115594326 913815325 216442068 726794602 349511505 405953440 303540605 333755272 808787321 717014585 685740522 273501230 43082330 753912764 911794180 670371714 835360370 571888057 257482190 145193623 770200706 269305089 182538448 508049638 562569207 313931437 164309297 848991234 170207716 859919832 884890810 233824669 758802989 562635730 945173597 794060124 358877226 365970653 599898871 631414868 174515950 667746727 239198736 469615080 550011573 59468504 763655888 56194768 207795242 549906262 870450851 420975804 161474666 80461669 241618061 299033068 8697445 448966870 114010465 821377564 377179609 83629503 289164865 843008606 83781220 727045880 606964669 75656482 141972220 608964294 569342678 398047100 330780039 339661812 594932641 695807095 465596754 532291996 547027558 658733810 774658723 246629295 622390539 553541642 868847141 768154851 37920154 921343022 220239899 516476125 947965863 486948653 988264498 868679710 755822826 158895896 784951414 679909176 288396971 874965297 942774446 276886952 169102210 826283849 512501527 119811886 412483339 131379259 435891352 310853922 262075730 348418369 801654427 947866931 530039637 483769161 767972790 696903946 167245886 515890783 452734382 325855784 198926195 281168886 289446262 524609980 994685969 670077352 242062182 847686446 959553547 481833527 161486640 599986363 643176869 27285280 842900648 797289399 899122721 341134977 567831822 768453397 824191851 476233342 520149801 983188553 275003453 844649080 903103945 634913343 881835169 329079065 30388279 477796912 783720083 370197000 498500194 144376610 418782708 760921403 236900824 938017961 966726081 599511875 362201045 327142707 537119632 827652049 346209706 570530251 815551892 79125178 519432631 847876082 52703792 666328619 640916818 181454870 912533890 541627396 569280730 553212549 146594371 419482770 993491259 99678642 428601802 958529371 260051904 543316983 568301535 568390239 140956356 695904169 835141962 842668116 635214986 995623304 727121309 993331906 259645749 902127715 688362408 406434452 284146881 847063689 372438753 581971736 681682131 170875418 848923866 33244118 579717632 324983323 695990025 906062218 426283881 254438826 397712909 574319764 568063906 842804669 510558867 430164786 187850026 634609869 693133521 990145395 583510187 755828912 918236278 103871617 662836723 845297822 431489349 332323826 425710284 418002823 478739726 56648095 512968004 769864306 13661340 117257540 221840413 308576532 866380290 111602234 460983507 567530398 805203221 393648806 859682892 821052914 977875422 634044716 494220169 677015561 94548798 229240961 339712950 12966834 454786811 559661503 54895100 577919787 271184939 786178149 678137338 777909553 117849961 199662339 824833060 359186438 330943160 77678615 34365977 864778991 899497287 896616998 531409925 616501479 447922488 36995188 602449451 84287717 769872195 446600784 559167220 232526912 81741852 206301252 780877708 646285023 207776537 513607968 248223203 687388220 244419357 996857367 275516956 328026492 366218370 844668197 122405887 196332201 995991089 727056237 284877948 433121420 625456810 846265769 349059615 936825658 405231127 984287115 756008602 167976044 938474281 82717522 325418408 738962011 896329396 408845042 424233075 45751152 240236285 505197769 925566158 537474190 433077910 952671462 253754843 140576444 823242732 218945610 378683789 106597600 284564119 214395788 311209297 744265362 516677452 158727299 741840499 797074140 364669393 259733480 816183270 725160370 746002989 582729418 656830068 714328681 437738227 158344372 192075097 667620248 979202282 366007475 278267073 511944621 20167108 129740158 956906169 581994315 625475785 163807066 234122404 635143872 782903204 383924188 515528177 384176848 46520422 1086259 258927082 211921935 367682372 562926440 92934351 607157916 906169138 175662749 344088731 372118664 211486158 817800710 759168821 347335983 460526403 195927987 635197739 65152990 306647414 339365524 151506998 14039787 936140024 156134329 682832239 210123752 193455280 488892788 485987173 576853977 413992619 379464049 737927447 794768116 175469751 619530247 209423035 198056601 366865480 177468585 609481339 199098652 624686376 813538812 833858715 944635098 70636283 448368492 778747464 693396101 196670271 414950796 44232028 992465133 131047254 528527440 638628600 56961015 190400506 140358820 196041796 477145715 878737293 401033745 390940145 210107271 496190978 351234597 498090251 853992720 214392111 556023235 74114210 802873804 994337227 775163486 568679780 576413251 555701636 189692410 543667217 536589985 166387492 561296134 909741527 253001775 443173862 717974470 705438259 823671606 162405767 744209557 152050572 430109397 158428822 785704148 289449808 177562124 169070539 873261451 217056407 151566900 287120195 887096772 39850958 929525652 356062109 651605349 252975685 151394748 670214314 480260771 385895600 633615946 948221767 266373729 613787528 749446521 175671834 453326564 705738351 424455068 432359365 622267958 505811216 791656691 372296493 979826457 858181650 252728018 556359701 378734880 382123957 865014306 715913106 293139661 416857493 728393029 990894775 587618508 795522885 313499366 721187185 604959050 163207015 366478531 986984582 921740708 846646777 237946074 332436642 762239229 304189310 820327952 692206418 271219310 67217615 905581878 507430597 139459877 756220087 906505013 898701471 120668278 77094622 333857419 73400805 710264010 63247979 492354658 823734783 553010676 980772433 10585623 717318389 668586235 880689082 49395046 401163348 716883594 209330230 194854216 792266878 701702910 438702596 744161872 22006893 342806139 282137368 814726021 123408273 868688782 867111486 797337844 183343740 420436935 728405043 849289623 227138939 234740949 655601891 480651079 704316133 813044769 497277107 716162336 381307481 700275843 14347775 226053942 432209601 386185815 643999571 907659917 149471018 161135346 829251359 151384939 16452949 624648321 203118799 280466471 134329633 808450545 14521718 873224577 129085555 117114657 450534355 987505463 627005691 644053803 92416987 376809504 778047029 225653804 865133509 558584684 379594407 218448227 148723535 466233564 685839943 761662379 131623773 241283440 607714797 192579034 903042405 991725130 633999293 321730512 269144629 801994915 388004190 60206324 727214231 124650127 281689701 954445889 223238023 745720751 203557200 822452043 839782562 332668941 717479527 220910642 285233912 670601681 129669266 126241127 549862302 446948495 237992986 348694202 932531569 324481269 639691010 839627804 8142692 213464123 512935103 855049743 63434043 143795143 626019194 918552949 519133535 758435080 214856123 813050597 987834306 628995865 476578409 367781535 330017116 574048352 748118487 829928682 718622264 940665860 747021447 368396442 397721664 657468417 810251925 290052983 14256229 357712170 960651812 701100030 972237693 148708808 973978218 332380990 834970520 557525751 56794723 243222914 406474909 710250038 261831920 701524130 71853362 236261432 845582789 543509886 623928127 423787258 188373984 700596124 362256448 556831370 259994735 313740650 34823060 221213840 68628370 919981633 56117027 39407812 205432410 857385467 314534594 140369537 937472592 636001509 270998498 843271204 160703235 584463896 927914905 369930204 382748779 553472621 440552942 93957337 716355287 580170546 789771919 756962591 658765597 384277884 473970282 41050057 537686293 622328764 719691499 945424168 679584947 875201343 767694088 140131378 940797767 733609649 157403067 533665486 958132876 521766572 764375987 684451868 169278617 394679406 584469329 935413898 206785430 128378301 353043898 964943313 469802856 639654084 984220294 306517104 797841398 56560140 591394765 615083610 958534418 390712108 943574139 827481980 679280113 225659487 633298192 278460510 670792173 624251249 260418562 656687483 340393867 81095671 150080689 972518853 260788208 132249152 350131284 248991088 718697235 337531178 89777698 606049421 42891462 965677773 156648746 623572337 993325437 761629800 870622097 106726410 194119011 814544865 375129477 711239517 220207207 92488482 510008719 157499620 553373533 555689826 656404887 272060471 760744527 615971942 264440383 173308920 593105379 701297184 845005514 810811184 547642817 97825225 300146520 627282689 813595313 902879495 715427786 357054186 444486812 63026487 993970423 976530290 98268740 346677601 99743163 72805571 600299891 399243105 840478671 874470317 909823365 118660875 690848653 534100946 792303083 936399692 786081730 429493994 185750524 727951685 355392608 134571516 206153711 745759064 437239802 421897272 814022819 348284894 707319353 739758408 394463539 389581324 427657485 487859750 363463478 500081837 609219617 754591963 866761084 147074614 26390063 123194260 272697923 736974357 676515154 554363611 75805100 58954891 189845338 661733162 47201281 484992855 368415357 936199619 103665996 315107711 146542610 500108958 724336724 562793124 11465588 58123355 31761010 798922392 678914603 503914054 157262573 463222523 717183311 398280137 304600785 692565033 626896436 898518828 863514761 413009700 544241928 682825285 217035605 205915644 672022430 621893463 186610831 953655006 170228476 566315030 197572810 845955343 114555289 426437589 651768624 909046748 464442668 78061514 234089077 109722287 544455133 133541285 693656917 670078009 489365747 214788384 952436992 948546508 358072894 47876368 195271693 723393017 854968295 455056990 434805 674745178 277166964 32337899 105539841 310103602 473166781 687943265 340255078 685700101 381768974 779782565 719400512 210064188 48484981 553349954 493100254 487184366 651059786 24994363 890454097 482019313 516605481 116458906 969557576 263982839 39027242 42846403 745003248 224384623 877036107 404523117 887021661 164376896 331953246 673430734 133175306 236194636 635084770 841421379 386981119 339777072 100265362 123134278 404043218 576562178 757429698 511481506 866266220 379655987 466589998 621686975 808066496 921745731 270146933 363553922 213604276 723137805 261183105 343504167 24010253 641763178 58754954 154071710 775485426 567503209 871200174 626671571 420514419 43978408 705924883 119086713 432342320 179752937 34266354 490052021 263923656 536014827 853836180 634672379 593822073 91097958 547365544 670718591 554891236 124412610 87402643 48309296 828612878 474915097 354151062 627537733 933416558 845663344 74387364 867711404 728248665 931074840 169559155 952814339 805621112 322953840 231971779 705648386 143402417 615825315 238444502 76052830 257098825 831057368 515971495 795313232 592869589 76965015 256653851 366104980 321207594 88561269 739913589 692531391 350760743 451715495 180262565 851699317 701315856 118127065 336443696 183558668 868306792 465308629 62877798 160566910 109427013 228967030 563067320 873016060 785858028 12525002 857032393 668107566 128828206 307561716 410209229 327411919 945842508 567336415 791821786 131925502 412853328 712740499 685640886 441910667 137333637 806957254 682724777 649917178 831461898 45643990 468397114 8955615 746453207 500055849 708024940 411505021 423848581 204059421 611177238 614711112 1869279 385632116 542344995 884720018 163634932 844614126 798913344 907021023 312133315 708092064 843904262 984693710 82959890 641038381 214089691 331487169 688541424 889658732 712444495 41006424 105925219 816465456 629145088 579162591 978662587 589558486 827487108 435054496 791479581 76671054 446916080 692257112 766554125 360912431 831545341 733701733 717061926 190870667 844152675 494645627 950287212 158442951 812264343 989781586 78199529 360797562 236959003 730512648 30598354 331156412 182219185 394358449 156722719 62605193 544659197 312184593 1229296 610379669 172636831 101281484 52170814 864981795 777976253 433952228 982069372 119792095 346037575 278667563 960584700 435019886 889579134 575348082 362386983 273995395 623612468 692362327 182463194 879330265 704852403 190344760 192279220 757767394 388065037 269894353 668988066 286634328 979493770 74211282 764035085 107474494 360582588 548596896 429742793 704062872 195626384 352408934 939635018 630060615 872841175 161627713 666397523 959280003 743228844 568484556 853987246 714733168 276171289 414262154 11611492 29138876 50815249 289357191 789440908 514900193 444828838 794874110 264039153 640494892 710804834 5303552 455246050 751880184 946258337 327134202 984432324 97791695 426713111 250234865 527981810 167650408 25045428 17165630 476979423 136431237 379313930 580229434 752547046 2737014 50343981 427684149 754677768 549021950 549662771 232846145 705931243 560974535 481126921 918025246 834820943 918775631 408395904 437633171 710765806 842093267 355980693 282779140 21991787 317997194 540730574 192368301 477390879 957840629 660442691 363040014 170933626 416271313 966543533 864225355 14988565 767323154 396845000 624614534 694362333 910223186 773486099 774063449 22232683 299071753 267118209 295475938 296208283 424868446 276608866 544222631 660656054 464540046 958949846 888216225 874591994 928737002 345231088 186130415 426188561 543698304 895316965 898717035 183791713 823700268 536267246 325387760 290141714 647543363 730129551 105508217 872013297 791710691 635753907 965893603 518739148 3287575 502695401 560028831 17423319 606529987 360703165 765043644 967626138 794737526 10574670 694655264 156105967 965672499 126150601 781306373 929086994 877980488 929607910 246562308 110481351 622851483 95934344 754862685 842580909 972287054 973607832 760272449 904050171 124409048 312119365 184257424 713645329 17415336 261912943 756287490 109512916 631443539 714900352 725688898 568069676 503582329 261093694 579476017 682461439 242294287 260253481 390454369 274277599 310667099 255900685 452843196 619027603 640065035 349454776 25145201 652170033 389090035 989392136 584805911 345960134 2348133 559555237 189254755 593791949 304620505 158730013 678564186 954855701 183488959 716397763 228943378 561762117 549859515 390546876 948356384 179621163 375672626 847132257 506364583 320208434 183608710 971430607 89467028 546209414 782933102 599845814 651910262 344295376 85489418 317420478 243539680 235734824 320276444 198588994 493679141 688272446 776963780 679871879 272814877 834623710 230320633 534720781 338545804 140611927 162377123 234391073 923181961 752795243 26631595 577201641 862578965 894383872 647058902 53732469 592690624 46619087 482102793 885747761 68047144 983917278 636425184 325640782 458411097 513269418 242327873 718726700 463898266 506312047 910050815 832016477 253534476 991633662 974478438 477309353 416917576 225880642 539543510 410670778 447367070 561678130 9190167 46858347 600592575 339805571 929665323 113539691 59567046 239342127 139875623 849269316 708066648 77599928 684480796 767002401 565598975 970800248 75010496 703857554 288587147 338103040 163959670 567479253 483805524 821283234 65949542 742091261 372312931 169725638 209005718 807295782 814749953 794174955 974489587 916521215 237091737 705986348 198185861 638145269 191755552 7255278 162035810 720041811 51226323 359755488 487222100 990976337 737616984 747941135 37285994 334517816 865503880 500257181 271835336 863335112 892505337 33601594 863658280 522973050 625920448 547580917 502521247 329820524 160776227 288370038 712102096 573277675 891226688 622117271 856202925 910069766 96990872 851523925 939050258 129266158 118844757 541935784 542409636 981229809 770561548 272416531 610909154 239670298 576826332 701462380 290896887 629898748 858756492 228251790 835610234 692728289 537664095 562195060 389286081 93131510 400353968 369568749 571815587 756866605 724333353 754305443 561454977 781214570 71627884 29160330 863896784 311790421 259188591 110454403 196132276 942895402 647411618 468984442 109856310 590614410 553683157 825534319 985332496 624984773 871432653 912629603 204518013 389811182 820611463 697405047 752464428 969525297 573149773 238365315 394146131 691056012 988972446 977601398 5635051 611316960 820755481 795137525 341945489 669747987 697203806 605113668 89276725 987107433 907496438 537302960 328733331 401705326 753617842 108423720 450876698 242382124 770402499 911355536 69648874 638613260 936827179 868518932 933975310 878851947 942362585 710088559 547713479 903896941 207837745 228880397 154396384 151340284 689284164 724247821 356035805 688028033 284435571 720198896 952519221 615782715 83150379 426792291 112894584 2449442 150219478 481242804 106528378 272831912 896851321 280122816 972158419 374565666 911192541 358875109 6825079 370952537 689789284 150650367 459371056 139310064 912174136 241344683 443745087 600343934 722031907 107398801 808670417 61880418 784194755 99128190 100787292 772479341 139801025 336525214 657848015 634239628 746293521 106315546 464249583 351739350 934918520 217691048 426005213 461766408 366373593 298959993 346292953 294997728 826438188 982323061 540694565 540932136 650776893 442199771 460038625 633084214 781767899 405000507 521159982 479181691 297066999 555083006 819144149 804168103 637430745 611189756 674221023 421734312 194979602 805101342 632444385 828852272 832725788 394132875 73021895 777928744 379681600 273035649 251340860 492569382 687784748 620347944 897861288 178310838 810122628 917715616 260078720 111357504 9734490 947721429 560390518 182407666 494623628 192402414 133662989 181885237 777262990 336612840 915885648 683565708 100922947 100155046 954315865 332310973 368195809 659789617 716293557 76400961 894873789 141593360 22487605 134347178 553671443 261853422 791811495 626153778 484112737 638815740 663549117 84961501 404768820 548345669 736672169 492544839 997830496 485367241 834056713 2900938 352988443 344958618 512732493 58650734 726870639 752840171 790379423 686565900 613591992 364570227 97550049 290104428 614152076 911859660 457460403 129468653 171018505 118896138 634942163 553320505 354677746 128461669 342672554 487623275 390143235 319168624 280772633 663994343 995253532 118295098 553417747 662242868 992208059 359729359 960597979 298925154 583110434 771301759 338698318 429044985 692460797 410981779 241493339 355714530 593371425 888333016 177259386 963917028 938494856 116804548 605149267 835367393 728501408 583543462 695629691 650838894 367340811 246675523 36819590 768604037 397751774 347493758 263711709 977241262 13912866 468011281 54109950 714371842 378781428 869555268 21912377 773263914 969625512 457028871 349891508 247221529 211696929 745196098 453220282 705282763 599572586 926754490 148171212 439027134 78143284 236478286 785681964 637157194 531684500 366059310 457232940 70163839 866803513 799651342 11547032 882003969 532842619 809758604 178630833 359053834 720915880 810043261 821298553 777003984 5673085 698118699 840357969 428505484 886189601 842011624 836900558 633302070 950991852 563337557 337160328 769716981 334155404 128356032 882580394 452025395 7614490 873227113 988285030 617326581 213921269 904667725 171047238 447715041 762510390 409242716 824129935 754317102 819349760 599149591 395005915 500066211 163792827 635161098 98844756 663661240 181598061 312862367 93871770 962993122 183851236 222925575 601380123 636003294 157822377 63160391 491322358 401311013 662293881 458419082 122284735 889856071 912422083 41403223 183245555 250619331 994914512 702718479 188960038 791631132 574304898 568202699 281430882 593952972 985430749 860828216 693836 203940996 816141834 927150679 141317752 803748059 632614319 572949840 513283504 531312041 309540280 216976177 413100268 118701307 337877925 323779197 662470657 336523722 311862225 668927535 501212618 371623643 381588618 515722731 326439606 65044845 128335809 437687400 24400815 595126031 134965943 747016248 537348744 927994780 466371140 9463002 37116959 310644421 205744622 483602916 993973134 764815979 403681059 395793380 690257288 241737713 805750859 745734154 763127377 675997338 250813826 434883274 175810866 739990894 665905944 165956398 239841440 281301308 652485179 766798649 228127237 100003747 257180127 22308373 768335269 146118237 772146375 38750166 894400048 830797940 956195785 940458705 26665013 168782527 307083739 324362166 120649948 119002173 803809759 532400570 151705950 64100816 736019779 637512136 454824761 828192526 814946362 422615121 388374132 515607811 322380958 998103512 684005607 32066798 32918377 437481365 412114382 524993678 389991369 48693590 90408558 307270851 875317523 786154965 550125446 838638087 181562635 939976922 354325646 192180695 75474776 353661889 984764356 380499820 465895570 806908696 6589938 148318208 10070670 581966232 252790117 962231824 27828123 558792930 394605100 514707656 483364533 675361364 517633950 502418142 7218487 211577748 570829034 713295507 166898435 910075946 318065816 74488686 175579231 823324265 766861752 596987305 249394874 790535384 81846649 214849554 560413438 395675398 812091265 103472355 596583530 27362853 451181442 495210240 584498240 825851455 383022513 912189817 877805252 847099296 712116879 833302120 226939131 923622442 696703871 90423263 819817874 443252150 865082723 374499414 95990639 546908180 883786334 987608957 701326768 424439046 445154090 346471545 799730843 108824835 427845927 206273974 299687377 238361441 136987917 233414231 406088907 725454492 987531325 646818877 241844986 973849297 959987325 19759222 152704407 724607386 694629179 375059426 601775452 779931867 579887738 518414454 608119380 221545347 78662954 785104745 294934454 573390965 950668349 284738276 269917683 638568586 906988660 194261805 142394566 370377732 908768976 723976752 272261340 195524068 443811758 281173735 399061487 381873603 725842764 303479737 662426162 378561613 788812018 421663553 657128094 848083645 711527040 759217003 160324449 222123222 825124436 35677512 372704445 597224177 265610777 297901387 890431002 811277174 855784246 992059188 401767148 976546504 826781249 384092381 410488553 695564571 971285502 632101163 325551420 954422487 41493372 223700714 115353634 890791532 137214568 685400425 484656339 746267157 294163135 934885802 159370323 827983491 447581580 116962941 650759971 67277966 64813047 484068224 343654680 646451262 65065115 487245537 307389038 283656564 439481916 882300575 601705091 69558311 737542263 738593187 740814015 996632284 281221795 902762944 617909549 437568777 447077763 166310635 902330347 822596635 872259935 945521666 555610857 421657763 980516155 630371684 474738174 346496303 505792253 150656348 823871256 57378030 192576280 463129274 279060940 45269854 186777511 663526145 922719144 212403589 63928747 400446956 805985532 856109035 260221331 423498722 951406765 648104885 963213705 884606739 881718445 69575117 231545754 394337771 730401866 379247011 484012065 217280532 472189043 843712361 561040669 381327484 684566341 910657112 958206756 73029146 806805168 641211078 115186977 863545023 351129956 268301282 285047664 56103361 948556484 221453563 105432268 264205521 633551381 27936023 163639553 113252986 871885396 671417335 542057154 155131560 957042181 433551246 344979556 525408791 765173959 739516186 763881780 627859163 619795593 648043394 618870397 206806193 201070868 265367081 263465866 133063463 573410790 757796288 616733872 86281228 235226467 779669741 792345868 636581096 673692988 309908732 743296834 370738803 238176982 966964466 902779585 89966483 982284936 685567651 179123682 206985876 977190540 306327671 765370976 458001309 621008177 800838388 375205012 790853404 640130896 33114225 429334207 212367895 831147575 567766143 216771402 931506845 761574441 771136768 781708661 957014064 629770695 994925430 793546333 879555034 375403884 12504622 438703962 82572049 4081085 979655180 36103327 667351696 594272498 611655084 490707148 206716259 171340078 54475697 172161548 491015317 394801395 165697195 628196419 489907607 942848456 729606236 892179613 367831824 949969114 29960196 888044245 854248606 364737758 12426599 71660257 785846174 659726788 351945716 583095008 684368942 605711720 726472899 199464271 89309657 401834255 444731370 310407379 509065323 755591984 740982548 730821058 301092829 432048363 802068314 248342016 217298606 546195381 688459959 21330956 439853040 72820672 73004178 541586881 278642642 104486633 763522948 213564592 254454100 818475984 276189868 539804339 866206243 53378740 629093361 690414611 35386298 175477372 975506673 112501186 692524873 550386264 607110828 976213973 74073361 853492995 943934691 280884396 185682475 534839002 194447875 194012695 854421359 365861467 857180456 308624821 213882878 602713305 578654926 787390629 665984945 277915673 306061338 413371084 725741166 986064832 894164465 579989015 133855449 135900604 541846097 624672390 500988902 632037135 497122870 599552048 166457160 114371300 487883819 819042066 903264711 879349075 414594572 372798560 434928780 196697484 54524480 997260700 317055782 277882372 978711467 140916152 845929042 268172932 968402307 387917275 683929095 922537901 753105789 838758497 716601214 700001485 458600897 981232664 668422111 775230920 280571385 848288464 703785710 913724779 721407802 382947467 646336728 842611355 473326365 420530358 629876537 691103780 749035961 292684135 775219347 826811822 117089381 830820564 589656659 20051664 842724722 315925136 155385500 711290922 56060135 527540089 689007578 148144289 582262914 519917056 800958036 812746412 533533411 298100278 449523874 806266306 95995740 777503450 778452118 853653164 147186191 385134797 733342521 432370194 757581439 691762658 942581882 527628263 59996599 436160969 386801838 85756438 323759144 979524068 63977247 349655325 380076552 861633965 427894904 104342504 236349111 306488085 937142966 82619260 757306633 749072104 293935164 330960349 707891683 286753092 932595006 94407660 146951961 538733907 108499454 876409345 370512746 315615429 543030428 803287901 125955446 185684018 888272251 698181412 153703898 40530214 510002481 951847953 956813241 619710518 3996941 105509337 28565500 874197245 846606304 857066210 802401674 833278598 895152557 495242628 748366231 910628517 246969222 927797441 792185934 521608226 692623546 931936826 882846376 471122517 194996279 402394492