14342
532368802 898543584 509972356 291113887 576312715 729514807 764182298 305151551 491151815 8882478 549892806 426240595 613195545 203486056 196160362 272767761 323134554 83772656 803697310 68532734 778408740 245298850 716636551 67698406 788243573 976074840 262239641 825185837 448953327 448498172 34137606 165572065 423851715 472500100 62120935 975442453 164108145 589552039 904533987 465965590 758277362 992623608 17487885 861090397 246967018 481743647 652109133 389130884 828024045 699053527 902557324 603928901 18285157 814412528 563553890 247329154 125712458 872839799 150670908 235692715 120577709 910932745 635708946 629094791 134141350 448801872 50477634 914515845 727328530 733668180 57467027 66621989 669750808 185514254 939278375 92321300 953857738 314539483 153313639 909421114 792509071 799339375 632141765 805025840 922299974 558682166 972642472 556489134 621575647 461423315 371167660 567828857 82255525 636606848 480726754 534036236 5819411 608533265 301441035 198513744 23869742 746778646 7232026 728033453 843890806 83733426 144358700 727616631 73792971 578855981 731534951 564025576 585021168 270617804 696029254 820229963 907441242 83560141 526924999 598859737 927213111 174892070 653374588 975775177 313749472 115005713 958697863 265163194 569217227 941753645 891994897 967855944 713691624 111917845 393486493 18300510 72450399 636568494 836111076 533335205 961009629 464308710 828382613 283054962 421430001 365920773 430228575 274203770 42839122 590084903 477466069 773299685 69735923 318548371 165722620 13767375 607504590 985348064 143987756 935611764 744615986 19143758 774060497 971801325 451717034 446460065 139411609 979215358 505318139 377100060 696449317 437777863 246530591 736649646 420337139 178058315 181363128 683758975 545059500 442740170 103183529 186251968 98630622 974955311 566647139 341452500 715845910 18802070 119256153 528882592 287870583 753193562 655564310 123727185 718611193 250273217 568960487 567186690 26772991 149560708 903914138 578560260 849297976 974747864 227569057 84748886 592852235 890858406 194204530 613354042 719861488 936628459 652339675 761861562 102730892 607190006 993102070 823569200 195422679 759431462 62229485 652358656 80875229 498765602 917760345 216043786 800531066 333539579 660347355 55469561 61970701 804964684 41934729 8294437 404105954 110955189 808039121 26906213 241139215 318106388 120227505 467505058 507807205 615664451 896199905 128970118 228230106 457581194 428170845 49674012 647447842 149202917 185488095 499624062 313512036 64881086 682186567 887402008 291603235 417871385 892825199 244861198 596448906 856060718 819519367 494851083 905453991 689065867 543680170 89682399 906026640 576159375 506834496 447213464 916886720 919919009 136971282 559807340 349067645 647547683 34252026 734123936 920402109 666498394 356766978 201218594 387127105 717270166 126931123 318579493 688790074 557899582 497633644 72811415 823239956 749764643 7781146 367158705 908798876 71973240 59408122 39877440 791176566 878764310 146700945 84517631 794095322 542172521 520429420 156350903 417109634 767956602 462853116 779512950 269382075 608989843 385212893 757363787 670554112 801742700 577140816 615022785 849137678 428103025 850285497 37639066 239573238 768534713 796251527 274287957 457770031 99965588 789408756 438974120 231690589 428839084 336327228 267723864 449703555 965656864 53954641 16008956 627050811 140707842 290166919 693007068 565957389 633726132 309173176 510610133 272813691 95080064 75764052 701581065 787720619 776721550 953467578 199571304 618411486 968460563 931083500 800010583 382737808 960799485 227385796 92627131 444486992 190228403 713085679 517734818 112815323 445013710 452843241 254289713 354732055 567027507 646351604 52083674 782921292 925832669 950628562 728869626 865064888 681265620 795936377 420012848 170150419 62836101 671862024 308983214 258381024 190897906 873499296 704440174 448641701 505967284 904366909 598347869 914182223 208089448 255958414 276280929 386890661 683818083 745509078 144439120 370225433 118710266 944094371 784892555 490090136 345112701 748796932 775847898 154900296 659077902 401630882 669114447 582118231 518574457 192242467 996699553 949902443 409889475 677828521 10671953 560828073 531679422 256573581 84995885 449197134 251195127 676611259 879502342 665902887 292520486 594701991 560431371 99738427 59459701 197755555 520394170 356882731 206217040 998651863 402638261 420264124 305400279 376556017 142653204 980632770 705441506 891138027 805848805 868970847 549704054 401369378 568984013 169609594 917629983 527038368 356768873 440089281 646848693 23745331 448781547 708875359 976351998 418445431 596376664 996394493 324747739 279285540 345780210 437223882 880211581 494159456 18697237 504811569 453112658 487413938 463409502 393274217 952566494 87438045 485369539 108428792 296557682 728378459 199955707 636621766 938475002 829438240 845108775 79301939 33305758 424109680 306129139 534582733 807881324 315274259 972297058 193566977 635419006 51040505 991775576 4021012 9138821 917787382 670454645 484505900 980138717 637322254 974158583 60941525 687472828 893782530 154854139 30800850 712267373 796851405 766502915 653055824 120297345 55348782 179521695 799565602 493876729 354850420 201882993 816262863 804384599 882380722 798195313 731244554 125774138 200485421 156611798 507004605 804246711 712380753 761966840 931676013 375463408 899505142 491008486 747435622 164125776 92897678 903624549 213426653 764049675 578145506 320978439 205686203 666808992 134536623 4209311 464869976 317140618 920916644 931374973 610851422 608000088 723248362 670739886 776562671 76166803 235187603 428116335 73986667 686821006 469006989 128441405 79568950 18970919 809617649 580401123 723911359 76312230 117852701 208879876 655779928 600135264 535653861 482976797 50308360 9989952 190360570 432427732 728213470 574469231 17871699 869401354 342784262 269428305 385977453 367916756 971481573 372612464 435350990 467286795 341449680 668450170 155032927 533702050 684122603 421125777 902300368 225731634 415435230 543535985 606827329 547062094 95104245 482174119 90096027 267937848 105670418 619679607 452428671 876546311 168992329 73653941 389662418 378602817 976461030 310484030 67296841 920065068 651322670 848927703 839515425 768170379 115340930 943217619 81707220 449652810 319807071 993340697 332184473 359917283 815808623 405402438 780630376 870091681 60208269 455562540 860391419 591167076 131173435 313683417 797797906 848981115 737210909 116066145 808530733 846978156 285733701 552861209 924065935 967396213 429443648 114321210 984652755 549852697 752128632 937154976 118597728 200151852 785747134 968097507 124168602 695055771 284265289 643064489 492633044 134094517 809163288 386406737 347463425 809730976 544625787 950281789 550128178 87170505 283792053 924816556 52686547 177989568 25932299 52435793 258534384 827957201 930111488 643274075 867661299 14967288 299605911 774860803 537642385 337339891 314703151 111103137 585591019 110685326 567418974 783286532 414948986 961167665 765914693 504226905 364083045 755788784 969282455 66741884 182837357 45827083 855095058 622057276 966227330 111379890 503537887 521175754 962568206 682487163 644551686 865632906 283504489 741200771 601683722 145288772 765424715 859101247 27577673 788949200 98129594 582585812 934757383 269936401 335612337 137452709 61216341 11338046 225456311 83048863 730831663 628766042 696802779 935962756 408309011 239278906 116664083 120656464 648610874 575950340 288550545 443896661 5953521 69541457 138104181 273088010 410592203 751159782 479057133 597024922 154248464 234134291 697949305 671250993 776803432 975153283 598995249 57279648 64826783 769516046 109646082 73692820 250123193 194990766 942720612 170961512 16995692 31253587 293010035 232617446 974139154 734398322 444061739 632935820 58784921 741629977 372898023 732752387 343614536 545962963 949362351 922497819 736379434 173851349 134824495 985980230 31383483 328688460 731968908 60584865 342560571 11842384 466435558 860073528 336318911 127940045 450167440 172237471 780180713 109561650 447622774 560730371 37085555 319627027 907803414 373628935 339309911 212574586 121240066 867275100 114055283 810184960 732283934 60259553 110471306 703825637 857536577 854477816 985489217 723367649 528112848 235685057 991869703 231508432 869315101 40613738 281235170 900956915 475658602 459972874 615925890 995237884 212973099 731102185 525956933 715465073 60525552 138665558 532259505 416093974 877628158 24242035 561456156 143430746 956857860 197982409 38162054 84992897 398977818 176224386 216268061 67932275 862386071 755544888 372111099 598844023 663107913 207527633 403468297 485777294 519116136 706306832 402286580 952012498 720866930 300717908 136841559 734057948 18363215 540376178 187042255 496082349 124505183 702500275 849992491 762559587 156556607 579409468 444056372 542732651 137578320 24876771 137540804 955871850 13002937 644497006 946626146 386762040 669568583 624847395 615117129 287293639 935411 482028920 944703728 81915997 811084202 458953630 19866227 470168607 531423730 47104009 48575292 361129978 722737018 873537288 342971718 272517650 414486271 981272670 368317502 264368654 893263907 28291966 909169769 70142372 707285773 29983860 73039747 365848586 364465313 738116119 297545086 498313380 759716132 758732303 48882407 20823067 519392958 709381823 898557858 749875474 368529047 524838175 239852190 161913683 214451204 596787734 108291973 144524396 10480587 846528427 524094408 624262103 161027651 562318331 956125511 774294648 966714957 509970869 473143300 134965100 54161171 901201510 84578051 662090615 644174392 966903589 532825246 980063304 724361032 251053175 792812711 460165914 919886945 805093056 51999286 512095823 473001757 903535546 658015457 517965521 695273350 793631895 343289520 171364923 354673428 729167165 216330498 176848709 178867909 903307604 121961557 546945964 290790982 444215674 279659140 182424469 548869408 51354516 974391159 674879063 831255228 170971386 182948010 758088407 964340570 612859275 994247107 740853236 410135340 869619351 711692547 80190480 727607394 125568134 240164909 329836044 692060373 480218631 583947563 199386323 804403113 986524098 582238371 744788859 777136622 339648094 453965326 933303132 598143608 421629821 429328219 174306007 393348335 50784073 769868824 389313565 603376318 527978686 335329392 883984810 840814918 133912760 901857036 571606720 299773203 84548731 169309375 166816544 219478867 197373895 548285491 974879732 650895955 119579639 523260853 499605100 201839124 433461649 718365891 215428375 840231555 66749054 303343547 168799645 189719022 741853800 839723890 124357987 21555681 509061065 7431579 141458499 21557236 180690881 329743303 487867455 288713711 38743976 68399941 132513945 221314870 197326680 754742986 926929714 854289632 763142954 371271188 160340306 895012798 150110523 761741677 87823697 731593184 542747607 241460165 624367166 926821492 35402478 156460721 115337113 86086722 603025417 865815098 198121786 26166224 127519483 824232847 611919573 26039700 355535684 188718228 746873149 655081722 957310326 360127530 847441236 626268320 667262065 306883593 329789229 112262090 298287758 888478380 995296841 996841976 48638510 423634904 916503495 567002306 222798397 154139783 762037793 124183084 376928254 749368100 785533886 531522018 906051847 999813424 952146234 466579166 333230959 768338309 642773146 245503606 655981927 700165163 612975822 598547467 766837093 974618176 195386488 358190747 715205482 992546909 82912861 947034765 457465563 632244275 380427763 790578816 776819717 455876700 491006176 708611452 481329274 130193063 16440389 874167810 202736737 132752742 87292402 978009863 364895075 371191465 174940914 326812049 614405358 2438902 774376971 995812549 74411744 241155557 799787804 933458449 268094202 231523380 766041068 687749305 245564175 526481463 941306195 21175110 555255209 3329573 125541783 151788721 695422983 368051501 881635719 807326705 938232383 46708001 628298355 633343380 673216322 448349583 38790999 711231855 779790977 1719639 423141965 428633732 32459811 91180333 311999614 415408296 297877669 645584920 258348990 652502468 557461288 573677327 740726700 223907013 606779719 539859402 298544033 107746433 358546782 49613364 421115484 374800848 708298879 877387226 624370274 979057648 795148394 61284449 8545555 891205377 583295186 179325741 8155440 422488444 182324520 662005143 207646488 253580635 322159991 529656422 408729511 509666396 798316530 621055026 301280756 652188238 571164972 317765508 40529708 16426607 642533736 516707030 664146514 837930533 693672877 18791017 726466960 78625297 191380477 748640574 88401217 493532167 213269249 59022872 652926562 95274558 404162485 61071706 727941248 294201371 135070197 27547872 81062371 349093902 295870504 270901117 162703551 604860798 500808860 106080621 278531909 564405875 534255520 603379727 585273749 220779377 580208995 996804779 570952178 829282622 377120696 836257147 486361786 959760014 936865875 554644515 831318819 239745323 513283661 109642200 8448046 45350192 636944031 59815563 883760895 17937738 831835180 535311484 171097499 948024132 260392625 640137561 46383098 610104575 586139372 736919609 869659408 591951968 792456466 915207140 608505360 625420278 299122053 85110338 225325058 24563339 312140121 629425798 254925058 295557235 300756328 782566499 50772590 783895465 118889104 9362412 380714025 99795534 664751981 69574745 550091950 478286509 530049236 775324890 102123075 129027922 199741934 338706249 449740518 793915427 813644550 541049526 973605278 705984047 419690026 39448359 583589631 626074140 551162452 290344447 529236517 793837117 851993449 825900919 729918266 102666770 529491552 139748137 985769091 132242673 542970816 845450181 374861640 730030023 833483022 106283145 387385483 764861918 990106656 19253630 911669063 126103690 5825082 703845762 195777452 279650332 34388413 292939442 400665964 277101728 504178994 558842868 526077339 384623646 236802624 447465449 857031321 952574812 434260093 459933739 105667592 572183025 41291681 145026358 857021333 784706496 864985239 490088524 110998395 972675872 117842934 399230976 929062176 187356467 482076139 590829814 112283364 655839876 460197653 453324318 542794842 242360232 719407706 545343904 927750904 978149502 564324101 100342127 113922297 284099396 795363063 374259038 192032797 974764579 508498062 489479815 470360820 466980327 633092945 404617502 473112906 269628073 448510935 455666769 464684575 703094727 103529020 550468264 360544966 627858569 477289597 954818428 635492206 74291483 367412577 87679708 252032286 861840690 972239587 227651880 476755047 353549744 816257931 721492475 431339557 412103999 597132812 820072047 400830677 104970894 161724465 181747925 915612635 981208884 443749847 685934270 805041988 193699410 713736790 78044229 162788836 890762146 930867779 676376452 228068387 680032186 392963962 33078003 536693620 778337134 189300455 942427750 336775750 570603599 265682663 709998122 519276916 906547576 96101208 851240662 58711692 865375243 247929742 836881808 602126047 782489037 896352403 397036710 764276935 102737032 917406408 64380637 299548321 599924251 284125664 89365692 878099385 708724705 591793867 75715184 673235167 119582567 365450327 113377241 506256370 113562948 332466625 14100075 756742549 173846703 56739173 718481693 14228942 568105149 223906453 597367799 267509840 85834 442595232 607672788 871789625 680265666 22095028 983931506 105701214 137267979 103942878 63728729 287370222 140582245 533763209 919043338 658975736 624989145 643004310 628688238 536634598 579332958 158152802 636855069 357609807 334260068 91725518 884989321 336740697 774446406 15322947 627694361 219434457 598458672 274459528 46396534 249966271 705086359 571654761 107198290 528820547 245080268 190412524 512640032 236609254 699484575 704730119 819758600 220672820 143810565 105046274 74131056 173104704 323380215 917629789 169272741 698592553 744901894 529432220 142555213 126676611 897490094 190856524 532497091 907213160 190648192 971523392 75464397 107730421 882411676 963934122 224138680 412461116 156747290 636735002 487127385 735259103 671801055 284277231 843773683 115247165 76319402 90908858 44286583 88220391 394851810 549884634 288893791 770381242 618609725 5296142 758390839 752347900 120403536 485595850 764554122 111946578 290444868 276550039 821876559 664492803 215558815 885052988 613813388 643133700 862883743 529983604 819731513 912905258 220975163 930322072 94613491 31027651 436165908 278711739 439325038 480097052 688052957 699570976 216409501 504652130 68388679 90717158 555825486 998040524 72303345 874042054 29617870 157275336 567164467 800754677 796802362 149258636 328978750 522927066 125076510 360353507 350469381 584204518 430083136 124777791 634750568 701504921 300946989 485017210 629286230 56689329 442280076 753296837 36802166 644653976 437337289 284254314 458607664 293161537 631427913 337712089 127783996 181956966 133997428 531893534 353165249 3522829 226111728 6719078 258377496 131602810 733233032 186385532 195957123 358918604 856374777 655458039 839619204 157878963 122388868 286311000 311085845 444583311 809061836 828786620 837771092 515936706 602212928 302235779 877895692 580223748 890253381 969989012 56943501 64676517 391479031 845646450 526071076 279361405 620843265 682675854 875419098 551276261 848627241 84617885 538602075 641485614 80789752 416658732 632097629 63232088 884764592 854687688 10819205 95230212 658839263 685792503 569847666 800123683 929104439 104692130 564483789 489251049 127479374 504625953 628431840 522320706 523918578 816570940 687267444 382355867 983968039 926732767 691685050 821637333 938788715 659561690 90204857 535517167 126022964 442041778 43189645 624831179 135553395 558722070 643309000 307162127 70647942 407444753 391575160 313802906 658565882 386045330 715746917 502510366 431499483 159518056 960358930 265428852 739163939 82891719 30174680 132667840 453323066 521752478 918150239 681046372 51497466 874963093 684156236 779374186 84659174 232546298 778354718 484834743 857530655 547925340 364272816 650302687 92964020 18634543 244092089 554935825 77893626 133592931 614436905 739670753 656474960 751141275 168009984 950272124 180667101 723051421 862741215 74977733 370819514 366011398 160384372 281124991 196662109 115695002 806159851 447248606 507518314 848219286 25074210 308414430 288762924 72888289 406251136 12312133 564550991 618715063 421206839 910204333 71168922 573621025 587437564 873774661 830511013 547851763 482169246 8195516 303067198 966652943 615185218 77160393 902069204 635525580 842229723 83198856 897258945 393881153 61416542 435654028 58457745 537750239 357063491 889745291 813433548 289706206 539738265 203056699 215386782 141178004 956750134 534915174 952766270 504611052 377990733 426583477 81046025 74366680 45291400 3331956 958571442 287889094 271329361 124770940 874110880 38892805 629306719 194026530 916675336 307650346 331705018 98673108 541533866 523973070 732417984 165754256 338452205 474990304 965306623 816926517 13977720 286279220 131464454 555367387 95726641 205365456 363960035 835843361 121795072 43799863 143346870 547153928 491074636 711735025 646634579 720098627 272751269 400458579 86549327 581071642 108422310 187614708 527365332 557085527 700713141 85423833 199268229 967080902 217957543 752790260 112697115 605775501 841836652 126326922 108212943 963750833 84062682 944723489 266555477 346997491 568712826 699715557 498898721 214629153 292609283 146650945 598672700 724144477 699359162 744397475 641596675 799908332 811688898 239166136 368822340 159246332 481439534 628827814 942026205 384964945 530563976 836625482 589022259 590456115 273975212 496432110 560487369 247918235 436462237 609640879 589756710 403977259 95461971 259045482 828046699 286820727 288132946 74782631 593728916 592850444 506252000 247137780 411278356 752936440 274577081 22109805 670762054 1656600 72655630 790918617 45404183 751392190 444676164 222158560 137817559 312325841 603338191 680156775 339447638 379868628 776110037 265703175 54743306 740704798 855800099 734263128 112318406 683264279 820638416 122838450 252501086 358049124 482431368 473217745 31657146 71648716 254605617 369163289 240103812 95957343 787806676 430102971 103639567 53926624 899632306 835275256 163588925 452956087 796387366 764355452 67867182 122873089 41700181 775256339 949986418 28278722 125051370 499352018 36235822 70550025 909237381 851992187 11711907 420992266 451359569 88018173 498162600 727545388 876411870 263947511 612069516 398648054 721826710 606376261 555896806 49232117 662969518 383511584 873729413 70027877 930451955 130073425 5684523 50480787 967508316 166075122 643301195 175983492 669551319 334691347 897780730 780608482 709140645 140046506 705489580 699117745 981869250 805102974 864186043 942903234 92805819 507233983 364435463 443448591 272197041 468461749 554527313 654483383 490961341 955069607 562090365 65163174 773767220 692167149 127319216 753312672 155457364 431785190 459406889 840834230 103984475 762849508 527270138 104643616 542087569 33103381 756200244 442239734 75268843 968537990 291936864 730206694 507825225 918526591 563943495 145948026 108088458 457488594 812304870 647367883 952815651 980052450 541937854 871348445 62309416 55296748 659491326 700575687 715696680 658177107 294354846 567040875 516522511 64924397 55609475 266021652 757913882 533087611 94664565 534923300 89339952 238465783 482891351 407196016 506019695 637754939 656360790 979769732 878242300 963213463 996924749 646825743 638024681 894947290 403622636 932269220 401053800 353010439 696598453 442317899 596009420 59554104 784386776 579397071 235699993 95415408 623944788 270365387 748624029 17350824 704989817 889535592 436506102 553901356 78463741 185118923 737401199 166786528 507978533 140669078 431638949 149018049 373378913 225136029 788015161 639143072 364392004 860516825 196877002 786939428 532146295 660857151 33676345 3093026 30820804 47634251 163396576 367630091 448470212 918718955 295016527 595990138 942502952 807717186 58595609 61851909 748889765 981587060 564324360 311716562 100604273 224842825 509607896 608085608 13099355 910489263 417536491 706712682 780956589 117324053 475354019 635813687 241993131 991992140 141823444 67241979 145483081 736208784 807725515 991559690 463570882 958104230 25391598 200303605 395797580 58550426 509482650 857581155 603700262 323033131 379156295 895852610 586950347 482074552 564157105 648145424 343066778 722707423 376134123 641815334 972921429 949952139 452151569 159755222 651440598 890481374 506900069 401815228 619934022 433414282 129290144 873466285 942602875 339639400 307845268 667296847 98486089 338767758 690543703 966371127 380692422 943735335 45541797 916787041 244614056 944722028 596505519 807555409 280071795 675466113 960386343 726159143 407133694 813078910 978777703 592101495 10589461 883395167 313598183 719775137 485327202 751375902 170923748 175274722 642155811 252867427 72691370 953127288 922768215 631452643 107854268 816424558 20003748 195526898 363556548 496888293 430599040 58158084 357841597 289492373 93330681 945676451 457623704 142636415 491438625 179825785 615438938 46465139 403010506 27113476 222619740 446418878 447181700 737534241 255339775 616233491 515615528 853646645 48383749 875307580 31498304 903979938 536977213 249717391 610106071 611282644 265613654 697647506 893882494 834949087 124117483 274372247 726948414 787509509 730584496 769597567 125264460 578766932 27866986 208981850 222173299 385535932 744229319 317387499 775278317 319370664 894077767 614913682 955905782 376276639 535093030 794508415 42575631 249537538 734800347 758444973 514694391 404482615 353550744 833064931 876383718 583775425 808251673 97278961 732425354 496643268 961936228 798251152 669730627 993815834 727877444 369331190 914532272 796395697 549869500 34536653 429904053 55392035 551969797 974489980 188279963 177909304 617397476 751358600 880129034 461297096 604309996 187919303 204242556 25753980 995890585 238479149 707533713 695122724 409544360 319931657 585268883 138996515 445181441 331435933 18612454 872842266 399155199 9983206 869959126 127323678 473800437 294564777 800383898 214592072 23893985 799725678 36790414 447138112 797929303 555381778 337596178 120130044 183983100 620471792 88801506 133243518 184303555 711391683 111515104 67069447 600242826 550469817 179624815 385219795 873365701 399571234 205327441 725041930 957487626 399546405 788026438 828675611 119526476 777233959 621085984 821591862 967536196 634654282 83226119 769511030 25342170 517050856 379155 77473985 168632516 675749213 68975680 780551221 539733596 331606238 585961295 38946764 181690563 744508079 707539525 792805008 330701593 413978309 33889924 90726563 713895321 240486030 77444328 24692386 333549403 825459323 543443813 205176172 330147494 838654651 126505868 761253296 469538818 683978242 935312675 219815879 773588707 839382805 686709686 952556818 131834935 694095682 327918642 678539664 870929050 248967170 886043606 876239516 307656058 782211671 529629335 160499724 279383830 204761662 953412512 274077042 60405273 619125121 870600704 25423242 86649382 908190958 444630002 800818895 876114288 350432709 322363283 651417772 506844792 620258336 589192386 302296957 551609269 210063178 68700172 445055559 156199384 810992026 57235245 673050631 165569662 383464494 289309205 516814821 682811273 649417515 248263745 800997866 943617660 8240297 848680043 972061099 522771358 655575801 316856422 793906835 669238806 170231228 628014386 155643691 268415785 548422989 138324971 43443315 593295575 545117776 422184902 168639998 446994118 732327214 994687935 707398491 569930217 833053271 325909029 469733747 458161229 232379433 475843379 63531197 262417192 307296778 38760005 751842188 417857962 667224838 35714473 543666901 14153963 100911674 303385560 874912136 827721937 123513087 415233401 298879629 305657464 404097018 315272906 742535765 564091410 336988137 845224614 85745787 167898166 70946998 552754495 130523737 131627366 145945724 276420166 579563273 527068291 66706156 143883352 180893736 591643641 698350449 970827260 905970686 990245566 58946706 727309669 416671353 51240198 53048533 380963820 210154227 244455646 429808805 809063968 864619144 779580800 409737025 263085018 1051547 493464447 75099209 619488068 528199992 552830618 409922998 241249582 25560910 898446742 236853931 162298551 447498161 613843327 353339895 791314504 256626051 966859175 140864217 416372828 476381464 517191204 211724344 70629723 662764511 878421160 821829836 672197920 866441414 987196563 353960813 489665095 643899555 849706846 256691366 64608380 832257628 192944079 903790555 856005848 897319277 614902499 767953101 404011809 676143821 613206464 179980267 64334265 520174117 160440676 434447741 111744959 989780207 620571159 404357606 400008128 105753958 876252740 884416895 305911503 378763197 731505465 68454374 608895867 746220486 216171494 444930706 412300082 745216146 516098290 170471569 165436857 298894506 555695203 162879212 616733000 320928703 517256898 315843402 593443802 95906740 84805702 986232256 326722240 897964073 714570636 853087000 25343400 183218397 7515422 196102731 304163544 65587342 460307855 950984263 264685392 128733601 902561250 315408114 74514396 173449143 817399194 368325471 43798568 683108296 346515782 708059182 143767041 166516984 272719819 664857007 687263080 309010119 917594781 935398354 659822832 829746088 931164239 9507309 875535679 570190903 126457001 146967049 468981687 910212113 408948804 47840200 329814125 530689162 793142937 922328424 36841316 509669448 495106425 902019691 950844236 58735250 468335971 588060114 599554276 508406780 748281819 708278295 531431938 392077287 163116807 108003449 28742331 36003383 104409977 117305612 958394710 612521664 407964902 898289884 541003750 997226624 425471574 573161480 660820759 422036001 20565960 54689394 627584392 164164052 736202410 346092628 393065914 392080198 5020562 67180004 665395747 4448025 743495371 512320276 304921103 705958151 984455954 537185584 249820072 188381991 538188831 931523225 955039139 50014689 723733818 239864290 365278383 370998080 219686513 539796570 35505187 882690884 361615684 89041750 521552063 844742628 367920251 823200616 88577263 511875064 264693960 272735977 936424513 372102900 461043430 635912828 908255918 536412722 145230320 137527020 162677671 376917060 915735611 546077800 731944163 792179297 551795051 185017605 827528151 161519079 24792717 872328873 360493636 765155259 832342971 479820233 537544740 50725445 139013097 516853693 981627908 250856696 431052383 28021522 97258264 384570875 704385496 322647133 334138850 201898239 279523807 409871454 374949574 60453114 68683739 961844706 260040898 378134235 897959366 635460087 534467450 663298521 470614064 428284941 967285484 508883570 171756761 497843753 663651153 102332794 358807861 142600823 893243881 839198631 531759493 602326878 862888360 607581523 337898770 117847916 482963450 471480262 101572845 471246900 119919936 947665238 316407039 683577695 275256 917200648 546634542 144667300 264784468 439398864 573406987 492089614 383579673 870617589 663714506 812601596 191990824 269324368 432086872 441830391 637891983 812175651 830089219 255716015 497248230 37609258 738590182 29692408 617056924 470152077 46582598 668133781 132450298 299083388 228246261 729098279 413068565 776208045 558418562 837217338 798927816 512025662 441289477 136684973 604305762 909737043 659876833 944362317 993293683 542020175 107433845 754352629 454145487 666301765 554012091 585081817 142461900 60353736 191416271 202746685 654453847 787528367 47530902 780915002 565854991 60206593 13351164 493170763 581603162 451744362 112783183 111858152 951752733 649963869 486395766 530861874 193924805 561488330 684179164 17241435 13972541 199235767 628513490 101633678 346183484 772599059 386238045 452719206 317117115 880406792 627587086 209442110 367828531 636167645 541492874 982504173 738835600 652444018 368070716 57098577 878060271 844314285 965715460 891293966 279231931 592257394 276278885 352537153 977510170 763510834 111779407 421264096 79544154 602224547 497516312 602801207 245001275 10260820 447871752 243314901 377638991 957306624 297908016 948605527 87458733 833072755 653376617 216898002 917932427 960742313 266495992 494716743 440580189 307604861 921743692 946668827 749596538 329924058 23828024 838602798 255012497 410639439 752076656 856572922 838197407 884056901 52448355 469663918 639050295 745551190 704731857 55990588 228936902 244778262 557048623 80467613 651940922 502470832 914535192 845472137 743876132 823824531 984782080 368912903 326833604 622175174 800255369 201888816 121151446 377838760 226878335 360686114 498144289 419792411 760233054 502200700 876415384 323007309 92649588 821921791 70201958 915769097 315898424 725219978 802456715 485667617 823258444 267513881 422507990 156329073 50212824 758821469 754516791 65732574 753738432 868754743 419632842 432861940 583496385 58888618 898508300 916954168 906033898 52649650 705345336 422292484 829287025 658143339 874299717 65192617 61594299 714205789 16070765 665874674 611323173 739763135 61655587 158316049 878558682 985678443 401700315 481569809 25381161 817867524 4118262 82093080 492350889 686882726 713356451 773632528 575882352 938854807 770369934 221534747 390810703 350475989 695265174 863239285 63127057 119508575 683393274 48195156 207613745 496247612 754596777 262573629 143554859 540836335 685471435 261603662 873705019 14542988 196803908 351427148 649008958 617075765 786812764 550788094 440960482 49716949 14584932 108778138 518543541 465615833 967857335 737070161 45481803 494425039 980362002 95105955 717935511 778987725 31860088 749054107 803220829 650251155 226865696 148262441 558777139 214348614 20041251 264313328 110883472 188648658 725093806 474862489 964603565 738048946 523073544 646470031 895002616 126465296 79359692 3960429 783898918 176923675 438821471 606581071 496149760 902976791 63976182 505850568 735699675 841065140 837405198 454302120 151348949 894109567 1892635 744728581 911527923 694425935 790534941 832391170 289900826 515749311 954653879 17400810 190599450 152316598 184538556 573107618 755562125 661813358 279283287 307914039 823131044 66764306 914188980 321654347 828253724 471322608 599365714 486728893 687276422 887754182 561119290 131196247 342579632 332200611 985653718 986147240 45341975 291819490 550480454 565422296 437374091 109806950 836939071 417061641 168359673 385044206 862703603 442832849 660839482 736713462 699914073 333368417 138132690 166281617 818895366 99189580 70417691 246626334 405340022 731604664 735691967 357011715 226567481 431130230 395933826 555458370 270372853 874105091 148618504 307698461 347395245 811313363 15495263 583347148 52651075 936316733 62633156 994406212 60425902 404310233 396788695 683834702 670319542 361313426 658463907 612613730 955318164 90115501 595237366 175565830 885335604 68773206 111011506 193032449 241541498 843847250 558709156 426263402 996512794 165548999 390686522 56344500 89190014 658920042 688940087 931684426 162355630 406824914 711359322 774645199 415974673 20019898 905433457 550972351 242800587 530519603 90848471 29362274 717967149 956222522 611779947 826829165 151079612 869351324 856435121 315154578 108302138 108346129 493197797 681458531 743224260 605230062 264577967 470725273 942869535 526426726 21341436 55728997 334365681 866763209 100637834 788902552 521138080 329381288 491427222 195196986 468197927 415438253 594343546 978497197 965583025 19963990 527314192 52080616 731525486 404947321 573929898 690720203 430817911 589239334 91351993 488079096 550796704 585668752 62638788 503106080 60751515 788942052 977993158 84134140 791213026 491547530 862708473 879188008 470837221 31400993 61452539 686150538 144890970 83543933 254517143 675159349 99571089 601515004 457128993 63458157 389338981 30543030 881075349 333627772 995123459 437315771 277106357 227473528 626676630 294298716 416642543 360009106 211594137 822702899 667887301 77806810 674476419 506468461 383209091 291718278 203915439 970349502 466226568 495062245 159486431 221816133 825097911 118664692 178132153 274874747 582531326 226032603 31370272 106651183 130549208 559718463 2795553 326159387 28028290 772534531 301715949 731047470 960866997 214576333 759368612 212930957 22821591 103352543 317860128 128819332 402979942 867929397 225923080 338100858 219373638 930778808 121503080 431257613 182354838 171559769 127461434 203108373 83871700 320846171 130141574 151064766 412813180 424414575 342553532 686516489 462133 763075093 230731361 693984686 609892517 317047860 509416585 540205278 816714671 600965645 813986868 206442280 134788180 937160516 4687086 904899813 171952231 635624396 1041519 324923851 91716277 168149343 790490121 433606499 5376194 749319734 765625102 932038262 21331410 680200593 75896764 784588002 20940228 548055660 614098831 352628329 716926624 647988023 845111818 337467062 304582501 664546700 766900625 101938275 732104460 191323682 794087009 756960999 343347137 139733842 100018095 110367414 312217862 143040207 835519828 979143235 293146878 592075522 721544897 957891042 737308176 750832614 422795498 693508735 407540070 993567979 857145753 728349789 718099017 232065773 499127053 757237783 907309953 24469565 529059081 313658981 387102054 296238009 798085289 29554833 452317546 801847014 182862567 115026484 307796060 633236569 25527492 129768994 124542225 970560100 65284929 465598436 675465956 957747644 474701637 201626226 795747188 742302041 930859436 329134229 634073903 66214501 263550933 34728942 721243051 179732614 404019010 797171028 50460804 424632613 505129482 501309155 717582676 936835752 48367254 159602606 26885711 689540679 81394513 636437202 776970079 835527187 102825948 264333973 664885409 17131847 172127025 278419860 35703401 919106288 569492739 129832888 257946458 684103154 887225012 611798757 142968835 635970624 732149643 157735785 70501291 297186465 913421174 302040787 895632442 974532643 905317004 741230427 307133536 590119005 843596961 440047805 742740139 58543003 970681445 602741628 598162091 939295024 579162465 587644245 52494934 459538593 113921133 57514626 866618382 814014092 309490979 409474213 495476097 318140985 908720706 758170050 543535893 605281085 329142950 135152819 61670757 58773170 105657411 401070958 641384945 536329516 894270725 562991494 385074170 573329973 990693894 151544461 885112457 465825224 546629647 62397035 527909281 109301782 374988592 716228640 801872817 262028519 571825677 477794786 648573941 748195987 413183518 206234400 142937736 467794800 82533705 662505745 31329714 424992877 324657011 901903691 1232236 382820823 1527521 696203455 600542523 938004933 371439498 48664251 856263891 732259262 645597249 465562493 71371955 252555853 71496671 639647527 252832601 634854435 92692521 396013075 739912666 781844526 801474261 360453837 889232044 984247229 176628156 767000932 787798024 77667385 271622669 404926133 217823182 642068580 934259657 849095176 506750489 828286393 20390491 46044136 208137535 64156623 829512317 942637267 917665744 128073495 191072874 873724247 190224337 644748417 877123529 487382089 721101937 102996910 783187238 893598375 223279 605149700 61417480 96913925 39716243 436443656 651855081 59741145 194544060 24867458 773995791 238792652 534127693 602474985 411660484 732910795 858494145 915937663 794482117 600585145 861374309 930730130 510393356 131431368 146774632 968469971 296225178 582434672 542031050 83188548 931033811 319392629 115759875 103501784 678669968 913464731 34103286 588755825 761972240 815412391 188382155 747966601 852860310 362848217 683892480 641394388 340532948 293320975 370640154 291970103 141370920 904122052 132508633 717993242 394767573 74575600 847599702 349144157 933484867 357596459 464425301 285938834 853047893 368072051 79535922 25395814 271161917 458023279 415842499 946055127 172558873 887016833 53396529 580260229 710410970 15562311 148696393 262273815 399548255 819119388 569360040 840023020 709384956 951214189 981568027 37415307 419317950 582923037 160047017 53650447 345871339 614323916 988148277 110011060 558405703 414074703 151995166 224681873 744949857 335546361 28594077 337276983 404892042 437834323 402475233 620714753 24763386 172341334 378322507 914763223 383021860 85389086 615275400 799870689 179022997 214904326 976979669 230293693 573528129 26134492 155726250 301479829 57545924 599665290 226735431 899360811 212721016 789310498 728014139 164775339 272684784 76023762 771559741 98289595 331260394 8790706 154964449 382792304 876713757 835773604 949389173 580316595 657754332 424204940 114185381 849258399 309577225 504505666 961273300 600859913 184432791 735977488 860795868 946290478 833135836 920600406 58813848 80322419 359149011 433857932 143264753 314497156 589407397 621019540 704867554 189166420 837185152 50956292 369386263 47165605 876797842 101506552 711565518 738192655 790907060 998649331 360082937 304988107 39115801 875211775 214282247 111632504 454254091 137104124 852020609 489400461 491163211 52931403 559843557 164788186 134099244 95631399 752116809 531424393 58247050 498588090 288821230 905353584 356030487 707916239 681786265 601977235 635910822 874541076 826746036 694392734 25504312 740182734 25910108 117945165 969943746 296157839 805173168 43936601 294018789 6876748 406348470 500721024 777304616 808618183 962245237 549314474 296149259 660969108 767853997 92875950 538442053 99479507 209779977 396886837 392845071 182360613 268620194 481936336 388644440 449315747 890218749 180907566 469579382 218253743 288572719 23596501 94879384 204924008 386994440 635053158 137662688 649871169 75870513 343387445 24211820 846611229 561242553 55393841 936828308 716234524 107786627 34087340 113729981 992306609 339158055 807814441 545676747 433897333 450972291 21487768 160625852 44712057 649227321 199156834 449370206 658027515 75129396 565314486 565873646 226257531 664251521 100794466 835459420 111349626 433364348 437533053 426976215 91859003 980988069 27479436 723837097 828190796 561175359 719042861 62866352 825785512 937756464 283366887 221502535 203928688 838520376 224251012 945919971 255497050 319092191 508749350 63404868 493710758 67364539 57865354 318852937 782574666 188035359 361817170 180449658 570475636 616997238 467009475 122983381 540872756 150115535 845978361 662048312 933187871 15457050 734079835 386218024 470731328 44635920 517076409 429848426 327490468 131691609 432699247 789577359 918179672 821221734 396267263 717083088 337216246 384085283 132975340 972003203 549713286 556531602 335335323 776645705 471719241 468620535 282781390 118472691 246138640 591580130 630921072 763675059 369920266 284735791 960857015 46808859 737461605 389051592 495363401 926048029 68195366 989189214 632191465 285828671 1538352 85261494 618320303 435947882 909316051 26715230 178771581 284322908 463983375 655444562 613111265 727454321 493332448 797054241 87621695 631512864 765483546 700390217 100491106 824833772 767226391 75098721 49759761 734126216 958722069 464972014 884609637 604864072 910340047 57146826 541497567 61379424 250285311 772224345 176365719 651189567 966370651 372692290 776986572 758219969 235040879 109609714 462455844 752034809 507755462 538998428 860539544 933220304 206053412 396039714 980612917 17267066 297269111 154968849 456743104 374777744 112968529 79484727 957940027 413115424 416283611 124394992 643498716 555256714 383129177 889065905 132411281 436303247 84979596 175427911 69319687 558299438 982583917 138630783 95279727 929511377 501648155 972704735 602943375 486935204 7261752 227638335 42082810 202124510 934976857 811152272 603006120 541490419 586737919 59280803 47510654 233585444 63412364 412674608 242918618 366782973 243343515 858554489 575634202 63165051 551052311 232183238 325877661 942531771 292078119 602290763 610408624 401323621 592924692 961159558 836681766 387503800 605932090 326144328 922415324 142864547 30685855 134051477 85790008 704099091 951489239 161882436 43787944 943024237 979019593 362579431 461373472 533456359 56782682 863780300 566031574 87574849 282645651 191612387 351384650 934745072 417530493 251399227 166457734 276905069 346414828 365830373 265380844 79777130 222884885 814765021 399957869 261050945 967103566 953376460 815634725 777666046 440721252 323945633 476170458 118297009 795439982 667036671 813653929 698682379 314145251 324412425 731609014 808802417 763698781 123120989 706166765 550169227 422575979 506041618 6214800 18406669 123223909 849986049 654288893 517135205 418032798 103704774 356882095 988506366 892983364 755656706 896931156 534203793 526982616 774250078 217626967 284745300 913653356 56840014 265832733 877719543 560149730 661165434 127042854 403463832 56228970 147477304 454902884 510971262 106879275 23629227 644905266 572822447 257660422 171663396 869120423 916144239 178459077 474519121 281563461 330597880 611336143 957749925 158533335 590022259 217586939 966499773 188340675 843790819 757756986 836598764 932951411 129219702 128021100 19480247 425453688 627056547 30091372 525488862 438530364 8913016 270166394 906137394 644623275 921345582 698084998 804359597 255150686 585698315 914009198 595025567 556322262 111925237 517723837 573752587 858137873 223041453 298719750 559033336 432305721 825058240 451914195 819682767 93631236 347631973 495033565 470440249 447438461 757949074 770054486 569272574 517465605 528614657 286675754 353560451 996210480 527008542 2966938 59143435 324723834 670492783 918469844 403175244 648381395 807042659 252217133 673596925 757198332 37235574 693512713 119893247 706124637 842123931 659657781 203217578 978817910 267860544 599400668 74200771 197321062 660321260 971395965 874261033 415030629 185857919 65783667 257953414 446507577 144967215 10488579 773828549 368418583 608731952 138784728 180644626 345314096 193180472 581880412 23539240 486998826 929073059 577288470 156181338 714714326 327622605 998013099 758855017 963852958 7498979 126766652 263325534 895920312 370312792 439469332 964784085 624564939 955825009 373229897 868107764 283275024 32066163 65072985 50939275 437886613 926808194 166408061 589534605 611520749 119960742 278986611 764131448 597999248 142854948 869355462 925982487 966630972 452940043 881240927 614508502 795517885 35890167 910598803 111091624 953618519 795974466 267196093 169390946 183275272 815929900 650726399 417335594 477720450 753713858 455739525 687494667 53809181 866230030 729432969 388731032 757183844 757180 988489219 397772313 35633252 533090623 352308671 639401912 419748590 230754929 90092062 787255249 545182548 363324259 94795786 592871000 58758114 852611219 471343074 943337776 599197203 156553232 315664421 880277429 600866792 93026722 717961988 869481595 898416171 516025712 98136770 703192844 752581439 750526215 922619868 285668261 600494776 135521104 370512302 290645186 495811018 652190938 409522450 951690287 600433947 467673170 392803364 481391064 168697593 414993283 558183697 184808577 609361849 988045372 734991794 474105986 927938104 622431186 601060337 50970243 603860720 79388512 695359591 302622157 929299797 93106742 476900972 658627572 68364091 91509486 401623144 539061881 926994115 789193592 117680066 809392147 292377725 342801511 559332248 161152411 304654582 521506998 880313751 63846999 482155534 925221579 62952098 119434887 592402705 571037215 111015834 472794567 568776863 983006838 804213089 147295799 699315643 12973642 945114519 396145746 822230516 170997161 616148435 440584405 378463173 131453038 156477253 38685368 644901776 307144595 421482549 456116431 225197799 33204973 523194763 536314117 635459732 528500965 316316535 102939192 813120812 683024617 87606476 814200640 504340990 341047415 350033256 51207653 299043296 908925086 252722485 577113401 508763949 308770261 181268669 96186562 699828184 37315641 891715135 915368373 816359675 284020236 819426012 73317245 380285109 540476685 83284826 194673088 45957407 897966879 761731078 57169951 368632951 123669056 889120737 53972705 319610604 838803475 687328611 410389636 494099860 17067265 234180998 335470207 103178868 900893119 196417808 511716811 899903083 736751932 198995716 888943627 431790004 747337209 12087201 724581092 802117948 86977942 549374428 96774715 285970929 244984911 735231072 407705460 832815484 624390214 521210650 194560209 148800054 211525664 819360835 125371053 15770414 351316220 139147131 829100906 825008600 410593293 976500834 979469858 487732345 165403588 887226070 275075494 809002508 979144571 108579608 329333478 42389621 270751115 143608653 444952093 564729969 331831015 68821040 329000388 532091863 746018527 323835297 769236953 506875903 788635844 333544018 941975050 525202860 926662044 857548658 57523183 217457303 580686099 425557119 10916295 372516773 974556000 504899525 138410572 334655675 91220004 624245042 228788493 45435493 716092869 874474689 65484796 529795811 810978209 32034348 530358280 319955035 185204351 25705948 188616761 189000927 203227948 946085078 675945330 217630452 343317695 644902148 520418221 115612957 220208114 716409989 554838166 791043882 3249391 925406556 231398312 811506839 326784170 145843005 697505580 656015859 477481709 36161165 608768404 751433492 784333809 43685771 580307695 508172032 97839477 208578109 878949253 107554299 69812869 611779793 824240887 747047853 89343134 498967079 216038412 710210248 582489882 322461873 515441324 866262242 477841475 285792317 538020321 246859302 25865904 936535028 436549927 83446709 767957022 469912056 160033298 30096636 968465979 22110212 677602503 152449652 66272065 83545434 841270941 1335311 760697279 861979334 154945648 66803897 786616339 544440413 775163196 532015664 258320512 528377791 393614764 26667560 963539047 26564096 933629737 644942902 205370699 452079136 89857438 345918397 405227722 784640789 553626268 897510666 329588706 830017901 850052967 778979719 44786893 552490904 142800741 751276991 656010218 175652000 186111147 233840791 60062099 939345575 428773122 227703894 203470698 938038456 934860559 211036855 46398913 289950124 551322219 828064769 236018148 354700621 38716269 16771236 553788889 335714519 914363358 311963168 157365443 81592816 674348429 502824178 410770473 452376378 997657860 83320438 207246816 126227919 384731747 906172484 86897258 193318440 107730010 875503999 830723721 182372894 475026961 226895753 653430440 766996094 706485758 262012215 90782927 513721422 231661808 945116817 789273301 102844160 570423057 733301985 197794956 35123130 903909826 506088476 439252137 609355014 873169527 604463532 266410139 51785372 625853363 342552129 17441337 517231670 98857828 498639259 941797191 476388872 848718882 831849594 777567582 140341873 581776877 223888720 299329268 65784127 827211125 921208969 549513954 146820903 160189512 508101687 63034709 153372895 757853059 510835450 119254285 142982047 65046130 161113781 9905241 559601371 389335378 969987409 30001880 375901887 33592176 381443221 470490824 297452486 734963758 209926356 64100112 879731940 229789179 891117341 458179203 888973520 727180233 181702726 948931620 480157912 563443330 536630881 516861339 317155652 380614504 781651156 846471965 368116152 27762851 606268552 893115290 470948272 750351503 926697509 99103844 338462877 654354608 474123563 430376165 400243831 772246985 556876199 684526161 761274142 26918962 455411658 264979870 428552984 29833244 43625351 712312402 406170161 798848955 979587413 315995583 3666222 134129163 598480032 633457048 436150751 816946618 204331580 374496701 38951191 256095152 426952848 846613481 599091917 534495077 127625510 458744989 660720587 92950266 994492487 569987602 4544388 654058174 934408266 844777923 168144738 713093886 10174936 797397942 569237108 921388543 272646878 793442689 310787925 732409165 224554745 962814630 736189459 482930240 60803439 307123651 69476741 611948860 518266309 101144903 75781716 791438491 985970491 222205179 921343092 656235568 668142156 273208923 502314769 646089420 147545902 253324401 310602447 555542644 893787393 29565158 625849821 76000313 377452398 175743142 924956163 104094102 457866850 727202521 556297142 335228328 332885809 409853200 68154596 865494315 456194268 533404258 121583400 633712206 429623963 642886699 799483808 912143549 658338951 659961885 19326212 338576159 410801535 181456834 318213492 979862208 639507854 845810715 346410706 89530497 145988304 199083648 12311682 556971034 923912937 897947543 82245857 474116772 109218406 121171807 513024665 51663722 521744038 569277737 604240146 806928931 695295706 376390609 303103173 423801121 769650389 13043814 769990254 282703928 964052504 859279885 89484314 724295692 300367442 334505369 67015778 491206521 780842573 348540788 737101741 428763216 415718821 14882628 462682447 265584136 201538480 468483813 925356961 190833725 942292876 217432079 511251400 313169925 757472450 556390928 118511052 890871967 422124257 149379483 212570632 409290257 344189830 270489564 42688290 788492282 861159709 618915224 490345472 341577559 463207454 292420775 66342861 66392384 751241798 64521467 726015906 147233082 645231024 752869859 303033861 51852915 761048564 323575388 695913684 818307198 596763170 842928472 942171417 678059382 241280417 750826177 521630261 11532767 350648511 447358781 211745892 225765537 630737882 832284376 642497715 704280661 708168935 840902065 451108742 167336078 6847148 263366339 227224878 535561952 878724459 269903766 580094470 864961682 94166025 745896108 413822811 213413616 544936816 882778898 693383335 447425917 192616997 55995744 315593794 693249440 344536299 798626753 540005693 402751801 974025835 184350958 715115326 270273595 560380954 606884977 161446961 167210560 44749769 490074327 79410838 863571251 140490903 584535371 695762213 420017748 252504719 212087533 525274883 137152605 312335707 976177475 987226086 643132452 634887185 495638124 100866549 899474754 334782439 74258905 174379200 268998017 596577978 84911597 180052365 128601704 833252018 518766211 913063229 83015182 957733674 239907847 97340882 211605110 7126110 302408310 630140562 176040302 624356989 755776653 765396738 595913230 797393843 145840146 856475789 205683076 614253503 597695564 333805254 37601208 396272410 596567295 698340994 18938497 264701095 38148853 217628759 314863444 303158872 5429145 53310035 274039218 217675883 313897934 108217831 45903449 138578420 653688295 12819207 704030543 6424425 601111819 123249639 75408737 965231379 345279187 399443487 205767259 674612115 285122417 16429256 41560548 14401664 530581578 925440874 453675869 363366627 452369693 885303065 521890233 878893455 962735891 205801664 459878372 175114423 888472743 900555782 969245790 450513229 541462253 467857026 128366087 813699324 668657566 345770205 269069847 803824788 856550411 459855030 782805429 126006875 171633955 374305536 766503261 658871046 219969384 999042173 520127490 524264334 978219669 950642292 959629736 894767176 671413932 220351911 192743943 835072097 44062906 269343277 749890435 974483643 81774004 133617989 35586711 898359683 566631896 439768468 342890474 261554811 845644840 706033228 453296515 75509821 78193011 515884263 868287074 942433125 427113375 604128545 78734571 234970017 711610658 703882057 805787517 631882009 527252620 810218590 942998275 542676259 396819398 406881445 661475839 694547326 683269831 913950880 614874941 511807217 271873078 318582902 746085137 295865920 193857829 228801276 112795727 677190229 665811475 903642649 310611931 714940232 829457453 375043088 277637843 570224142 685104874 543263876 682963729 64261860 657768351 14327342 867408880 67528449 79259921 474592879 521214167 253670428 476805873 60298679 975083410 572123385 38922201 330386713 209736021 12623414 353799817 78772617 519904070 64211688 607506125 218168231 791834760 203612633 969034932 847085048 289288967 969653333 857637489 196000731 737333191 378281141 12503439 277842217 857654313 478761699 719611556 30988629 573301732 870552476 362338893 359113531 192050641 920163618 160168873 954200592 634435720 704821879 421506695 861938253 464497281 702728116 738853953 960902889 610791755 398155397 31675099 580406209 16413183 771421637 717637892 864851064 27987877 93313240 652545564 134292113 42213388 810791800 194025579 900691879 109144422 232227788 867608089 268150465 29651974 144504108 24005240 315083394 704891228 587055338 892153220 481306958 548106629 470734814 103225122 530800450 516076706 14730703 618289110 59170778 784277635 892547931 879785216 125198911 477084889 809258366 984382683 98698465 760687543 698346382 902473191 982884148 889645906 497574922 233354408 475357606 489078974 175877074 28467640 359733971 882367486 575737861 657878217 713361557 859449070 785492962 198217419 485986408 886211487 402848189 801040373 303527740 910026327 226905727 466558389 984031920 852897087 187980678 442793603 1231960 23677022 655217253 87696196 174641033 729163023 146715904 542954966 786080653 338121821 571698779 699525169 594014899 749894362 40484732 260514975 548990364 291283430 130854622 250360620 890459061 131885478 396088236 3143593 733216726 912330590 506969744 572842953 395283342 5686948 91237762 922703748 902460843 129856381 91266818 618069362 513349789 428076918 411505148 62640868 124021796 813644485 894462140 632619752 41597339 987253070 96652540 380059351 41129273 562918749 309932602 34875964 44758158 69541759 557222739 66373000 986981401 32700373 632317151 605254695 678584798 836517610 568996133 373310434 428714545 390683902 12310160 738412202 185866195 411899821 105975391 864436368 855148215 515466975 297378599 640628596 354768686 182684724 273502830 147042424 381304243 489192647 293400607 354510109 924726957 339774732 227865123 558741432 614221065 259531520 406952777 67374185 72502029 918356748 856875841 486906099 518094017 352916906 124589322 176162223 525999589 77879396 101450743 773583655 754473841 698376993 269468621 63568465 534275399 937486080 241011715 529718957 666776678 738918872 904512875 111136206 702908193 263419376 118617737 181938046 963492635 39496190 240001601 732602135 320317888 634202359 77690846 872953118 114761116 349744800 498094955 590635873 147684271 431408537 778472281 313232437 808111634 38610782 977292030 37694079 16693082 387738258 44478980 819848054 724126198 392144009 930008392 265044672 517680198 987795561 476880542 522281984 227622993 784229816 88853998 867992915 500491528 67648991 957725668 105351005 900777679 403701375 108151946 731552832 657530121 950857957 643849166 795797501 440428985 61286527 836449079 771700685 319651756 175940070 87241412 121020933 124768994 841404458 97871883 753225751 49081186 273755848 104548656 300599918 94245854 733077042 712145249 98818406 629052283 212687972 26918568 887263209 106292089 892212360 327789291 859042476 394318545 177234367 218170974 44957783 484176909 745754274 177502420 221349029 564415571 490194770 749191270 754014301 210317732 845000534 614600521 194597571 131248257 9690280 241719138 327454014 666492878 264059566 140872832 561165133 901679548 529028129 793448717 766605590 231230902 499835685 575292503 969702321 533495158 708877475 11915610 135618449 297579579 78037231 45173450 961408531 519182261 463164638 572812263 86497934 71814560 687440656 146046304 819384579 731457883 61722278 131708039 708838257 145757262 49401557 8758882 181624972 789603789 214905035 988895832 789266063 981195094 419002739 580139054 821306392 819114269 128819938 413164984 249238531 4356992 213503740 59650884 263484589 67168981 125627117 438513612 81867221 991305970 701287558 149715764 214973036 984304992 147450897 804059013 852707761 93924468 773993481 992947060 158778355 58601036 360084920 131294966 1749865 931150347 130529534 22036123 432388680 71866506 974539922 234676579 429270555 145609384 711499658 985788704 314394717 222220193 173683390 459421229 81846610 644896893 432097436 619379539 851636736 273076469 216622616 584487219 679450127 140695162 870032737 217020108 822684322 1158593 145102922 350853903 604414831 802397501 844962988 776543477 108078314 494019808 819116948 528350960 942666147 403051904 722889662 84519927 478179125 872729995 659700149 122317976 656355647 893331331 954465712 795340266 345614928 599791533 408039307 1331072 689452406 597790202 131407542 746331050 926936995 183682821 16133580 12596241 251608275 177938754 112363626 295793172 118665840 990405167 593877066 935323847 200562261 93556609 447881053 606658230 999982495 291733815 258024376 639165911 541225655 431816665 195428636 859550761 140108530 954948370 317438684 842566034 500148314 741702234 794342844 407307481 586433372 28705246 412715788 935030878 926104641 872189603 167266393 190156422 503301012 42006345 625987393 240689270 198331714 466480248 818199780 938872491 713079853 774322305 77041087 689871840 411787921 727260807 388426297 77953640 787743160 155568137 939041932 413391093 547463778 49251223 984084060 729214067 4612412 4358964 39625722 62540856 797625181 886454265 188250741 686775150 52810266 109851154 579875699 483044779 838376765 751043160 666474826 167681024 716408698 887645398 880270249 687213954 837854506 770392157 802058130 436121885 538817178 109238088 451967181 355713400 673602324 847939325 407715555 647977080 661192817 587268935 187110705 646521499 612541645 98290638 141768673 585179291 780707418 17452928 66546676 196943795 555024310 417577374 246349616 49507890 2919035 461059136 899883570 763302010 542536664 198129880 369223504 104653670 125107991 303497518 609106595 199980110 253784409 452022315 489371960 805125482 449499421 36765442 27433708 162308023 606694065 454777693 554369772 508680512 53928249 926943681 296054423 860039034 111083322 252560314 353494120 28869010 456087198 881362415 508873671 359889337 139098779 809427420 885211036 768137408 561197333 88359879 946248048 120014826 602019243 341939278 100167746 685089546 640151249 921932245 820711804 415808341 578983043 719582338 539921703 138615518 277194381 706892896 662329640 11995204 887397651 11353714 488788387 941453728 353278594 908512244 549516510 189779595 612420564 63282271 580706626 770554408 27021971 39200274 354487261 747742043 226197651 657848361 211571765 446696695 28506147 213942542 844661510 359075094 339018560 403784201 145703459 499639605 574743237 121101825 336837191 455758839 12105065 24821340 353395634 373614808 101877422 709348089 331590520 114767447 249128495 302465587 445311454 369080777 207829697 978269229 429092143 294522547 883602866 863933051 985833984 75415677 288893381 763490372 767874573 438696782 658416695 819121646 607310246 866492103 46148008 160935661 956704626 917545865 906245720 317774710 840682653 58418552 233538557 275382555 527325794 99591783 949319062 549444665 129764327 46103956 213532275 184733560 348551130 910919735 210028454 278072482 639772296 202341537 287582352 203862439 79578502 386532805 318804654 178103707 944266472 175405346 335564663 543217213 898698688 176343059 63321525 33427182 755872710 586848159 557579414 766042431 503635824 19719266 709205218 77841270 253645639 60177150 725524085 471132123 545367966 539182360 804401021 951363854 202020388 184998403 859305206 308032939 319494628 37078490 200885572 232477292 766054523 706866068 211431444 235805295 72247544 729173225 318180918 432390990 110690676 657336424 197381194 316454715 484868227 272812596 283697821 695564401 597380180 475597307 222766387 763631360 782954820 134832696 537857281 8634738 35598989 750210960 919096377 402918562 836315737 678105338 220684331 337275942 387395955 586359753 145895782 791550041 713307694 308678698 435347906 415454007 66142446 52522548 130668513 417393951 104021480 237308896 573465787 332857567 142211328 143957426 864328963 197476027 910312946 749143966 958975973 644390670 513942063 645007801 148644545 745369548 153863479 206142337 536097120 135874800 872630033 127122462 593951841 44583625 638154344 926709684 658234138 45853441 298093964 778866269 492537812 326508871 813860006 221756293 966850678 643550069 418346585 82555589 30310133 261742764 857087264 538303744 69887438 510555907 361437309 593081841 100374085 212566894 139444269 173626909 864650131 945874240 634379780 557616877 248199425 74476695 539808436 589442118 204575387 970172234 988872008 388856095 504612616 404276881 836241631 580089443 780472893 577779969 974354090 51860380 886512819 172367819 823455902 438706840 827461501 834311107 346027280 87740656 128901675 786918743 184493500 963335073 686318950 620886385 407393694 680910194 910237467 835073482 67340601 655539388 852346778 321850481 977194215 541201021 372298096 239713886 191943424 472672568 665823317 102671143 602988563 453431342 548568632 438663225 94424196 790008811 934163917 32971574 895425064 991119313 504605584 493111479 585216974 266561952 455822816 939882857 868937108 130136328 501368753 926267684 464969657 844995538 530632749 992493293 122250974 116210189 874973172 499048920 591540099 105603702 498383795 150202459 952404960 520019754 861029029 215555042 28661599 679140659 441455202 129046470 511478170 829526021 379981817 885498982 312678536 88632115 79267559 809986167 538653630 507970499 5641640 915703362 4068857 813269736 684001569 534390986 732673142 366248890 856945122 651311866 667344875 551187616 713275795 565530783 906210031 717949687 17243757 491471904 739145938 425843843 741940691 152617280 943133636 670204939 582664452 315997638 245226029 492734004 683445590 927470168 200281775 28900770 196898940 801146325 143800779 940572972 582798031 413576244 718834410 499892620 739220470 885524589 950076807 399962998 347254048 231193962 878985105 562635216 839560765 530199759 950659882 255264866 357237928 881045725 628715782 999566606 744338333 2102150 764058470 371458002 359660979 803074589 132857700 349332792 15927440 404495046 207973492 454569569 144375576 449725072 179809436 547682717 788496771 143627754 180025444 30645526 249220552 849667586 389827124 999332912 111610569 878571124 840286068 835465398 418843294 840809164 37205282 184395069 101983834 143309504 66627213 403045507 822396705 816652037 902781076 69561471 681500901 100831781 315128978 678042938 319411178 427512918 876796805 84077693 842508297 677246202 606549686 968662065 229781742 766123682 76242803 950993112 767915604 773799730 91079072 757589634 171397347 692602174 996333450 91776616 596309760 19422612 604265890 239608339 358477220 27968477 353214596 625876436 523318618 115956386 111294867 867534904 392635239 596176414 925760037 522881116 352794860 13824425 211838871 640979943 171911843 749801858 278748582 58545339 9942597 187443663 800095664 812694175 747966077 489548373 829636548 90125459 762601472 860517802 567802510 432420074 599505464 42528565 251477854 133436654 489878082 721583348 811158421 913373785 860078933 634182168 738340709 131766991 345139452 198400989 276280104 580046308 410008017 522680268 479131240 488036202 184382315 887627356 931543424 87502310 210966325 8484850 663915020 887673100 552879185 78704920 91130729 64262342 458847903 35891116 572043577 52094214 521593563 187728059 284971942 427858156 29739508 54161555 553150329 340854834 408291683 741025788 955711735 262412357 580540002 910567065 725154705 498391982 80779946 44827868 241157729 629271186 596823399 62218697 471044740 17184110 488984775 94663197 304909902 517702944 222603936 387822472 519401453 59178710 331633603 45884850 33006449 481569189 660455752 84319362 402250464 137989464 699544460 918238736 813910382 713920656 873312797 864918775 166006654 285538097 205807006 549661366 476890740 693679770 134641668 60690488 763261263 212206904 384059633 701875790 91691331 103386990 896810857 305317078 125680457 127977570 726345046 384121768 391673666 614888179 527276861 70153430 100159001 892617400 692845630 152570 209722115 571883850 308024750 536367174 379705084 529414745 641831466 244051953 880370073 217472275 39341925 942237040 426480074 343151804 358760827 352100385 433706404 536995882 208982205 228139784 880001565 259387838 932551628 59539184 740647758 251633888 608416445 131025873 981092530 842693238 490582295 26894426 836013684 689446439 852007902 68812490 978279116 595262952 251084663 174547880 163540552 994456145 752166186 568325054 624882494 205026022 101543738 982045551 827731656 79838898 468041083 133866214 474063483 213590183 10509669 542331023 36888887 161711598 319997325 688950959 759905061 639094712 699089131 500953752 39291749 98929008 340456450 948081314 866945430 75280309 368268474 440355058 818795438 419699684 556275434 117865619 425992702 96330257 405899911 197219430 99675883 8282693 413745968 276418384 756634621 507384454 745917913 780299446 603118465 489210609 595287941 671074786 169797452 927475742 293963993 440425445 647284678 908894285 528028656 968153760 69612773 396249968 426406023 453081716 114855391 372698234 522382311 766335235 336846780 409899740 850352376 368695841 180661286 625318716 94158235 407948156 262334793 276921854 628520323 68992262 59244895 882478407 292503461 308562816 635202779 711880610 945998027 567384242 992524386 497347378 911011116 952890343 87917247 156404387 168531575 126717473 22731237 584772865 392356577 207671474 673520337 469983816 573125040 48373679 60566159 614125985 601984185 545698050 437431785 79470008 710557794 188265985 942981058 253310140 70917820 855338427 417392765 438593447 69148997 984479902 585174551 701042238 114568396 844140563 193453453 874904785 704173680 264644337 438722216 292907355 654358333 329708216 691138824 24130117 473428908 492727815 579427067 739842765 399996997 918675241 560315329 503925602 949555887 27773724 227484572 812293138 657209581 213014540 73096003 956838109 220532421 724586797 898001883 995538237 966038676 235639406 224613346 593216568 571752196 242799619 514250427 532714255 262121214 775245473 560340134 713801815 816414335 995669434 816561586 175549697 968693342 548432859 304210061 492893492 216476759 280552267 160824429 441733471 156441190 580058174 254934810 459459099 925349122 59083652 674456022 956634660 741627303 534977527 733141 22939255 933447744 881153845 298404975 711060852 846205781 543834027 321051929 86327564 355889617 487797796 117954898 340547699 541241032 44762973 150467464 318398123 580966709 846802095 621643768 251827893 574091186 106520325 433207518 742153468 581276672 406877873 601441235 10271988 635572328 273418290 519157222 249355587 178738606 523090661 934155450 890666705 474274539 465841081 813138246 621532786 741058488 712322057 568441746 793146360 772837363 889424657 719505204 243530565 61841614 575861700 591756643 657112838 734538586 299490071 975421570 813127564 796505481 247525541 485926542 87065047 865864516 235711534 289384995 790617351 69972393 352437436 449050198 722104000 764800575 106598502 38118219 702763121 179699341 844799699 534133970 500951102 142236846 11311961 580024294 40018719 225190494 703408416 80732749 458609311 527864088 556764453 953894786 144226641 301079596 773280834 107412235 829626868 74917346 148873783 303205320 140585750 31145253 619724144 200962030 370023251 15604686 860893018 77101812 917498337 461947693 594454118 689397154 816653485 720096190 231792610 203043806 205715553 12610795 496217353 39012342 136376362 712447979 891834222 414874866 69937894 211086252 83635714 211123254 498506906 864823967 720052245 640692642 431189808 42756203 343948917 516432067 692315736 477137278 335255220 430354584 244553386 72524985 742651749 572972273 628302357 700604994 415280851 303393201 3334423 34311 369626749 439541444 29286822 449845385 408931449 756154715 677033831 539219005 65788467 545648436 958074356 523299280 145447689 495880509 672642528 749033482 456576454 721374841 601748566 880616811 862409125 143013466 386083841 8496225 62116067 100647399 156682929 555019675 694181998 631148007 282804310 503689131 915650015 461970897 191465168 817537142 539333860 848672805 57433455 63903876 83582204 104759262 545287666 337063907 764185935 720783679 49001998 883305357 951645160 989468105 670040139 107838146 545462104 766854657 476837746 595988190 909762916 301745766 232181789 94502896 112719711 985546473 331164172 391587552 522075250 693506880 376363085 987990952 613333432 166447796 109877103 16000542 71593869 125770666 703658008 187679621 825379545 202614967 588153068 14348507 430150457 901736769 490741476 200260777 675987384 131453452 370456773 711874352 840819821 216317481 751050568 145486151 787806274 423346557 365222760 583625966 89272838 464985854 117218517 642072692 3370041 598666037 612159436 762449847 459640074 672028653 169054592 972624535 255021975 924441254 832931705 784737983 39682179 218435077 981748188 917897587 375186433 746375033 873180698 792214529 143939275 913770175 872733300 508225862 2560287 667011019 382520765 253420009 770002456 694804364 708340203 217414625 217902022 612627391 37434944 103862078 291680285 358345666 171445468 353888174 416305069 130534529 105987088 499501356 605697363 883076355 604797262 787464377 119534619 559588291 169499818 13086976 347930341 67253600 754840072 411170469 732658209 115269959 311934513 675760858 619198264 952431458 172393062 454736425 8262143 861340696 365796439 842535753 784194125 843500430 172156357 564381362 915244107 82326082 674974700 291142640 59564386 957196350 592016545 523297036 900711359 436544782 996974694 131746289 204222360 686319808 842328213 798058061 926438906 47730517 195382082 77117683 977220812 988216800 321214896 32335355 732889144 494605788 77748220 482732867 98060497 982799024 606450485 448874505 916715396 187960188 891396751 859255779 831818419 46587935 112337809 9370500 162143972 144456202 657322607 965158875 481209528 58084266 57644696 905221225 71934999 564175282 746624841 569715038 364023465 108932793 615841410 722866171 689706690 576574096 34599402 337042849 764769198 579245263 624725162 501209323 39706252 623029988 927707316 245565986 556918940 402874148 882828217 729309190 810366095 274631163 576560910 605960878 809984244 299312347 928876527 214637371 785234278 938461303 244694078 142168135 418012675 912981160 496660077 889940022 145815240 23837803 648453382 76465943 967866289 887560039 593125183 828823079 450537505 949468985 921716879 141517667 223015234 651035595 319025472 387403117 61236556 144070129 611044637 560397299 881595392 129550816 959613295 411421867 662937101 838679065 743853388 87061054 798754165 740956952 5806505 953148614 488215719 699535818 772992642 204231516 840204700 615397069 490256503 639254154 83863531 745076279 519858690 301510028 210595448 424627474 625779731 252502752 179028164 94724673 545158456 105893662 76774221 499622272 490448928 932878904 117615975 86719779 150891112 996199118 129025986 167203582 74954170 767774751 908472075 874396127 745093262 805291971 100196397 166626903 972644805 595699865 358851935 90373963 437219484 451789326 868493131 110665830 32728280 101350100 229560401 133991367 868499816 430042047 434194968 158356442 557443833 280311142 757708917 28703081 21823564 716403352 443290107 756040100 105204595 794569878 282605694 313033666 969356153 950879101 644711305 607887214 973658691 249191269 357508205 774118901 160418775 859336212 829150781 308752656 678360012 999001533 191596079 870274672 988254359 952469009 803512719 261079091 440153388 369789973 242384987 135464991 13378267 948690884 729075254 819065968 671530100 379808909 919896451 757838976 67121047 467484026 154322381 683478732 129982693 421214024 30962628 136302925 625675967 301519782 729035995 159239955 581282717 715497610 607374911 953316758 812223211 629430139 120862823 614897871 897191727 618653296 383088870 418647578 53399068 622933202 655530083 902979065 102195300 756956341 265060131 777499611 790931854 267878442 107233776 332255171 548138569 653045325 91324299 22626038 964176919 9860565 370258330 671610145 370620155 103330557 948341426 150701942 964302575 121760957 470429058 259351324 673365899 814806575 98355947 91933389 876688502 411312819 977651012 983158681 208754743 345648175 365595284 609207315 892781150 297508233 671903587 7532555 484057062 671947970 605993989 573502243 738552137 183248671 161825471 879355767 142879087 275059635 187955226 15021839 216444568 739518130 593328915 105463156 283710820 914038594 296105561 719515400 207873315 563873308 173336539 279368835 745719275 382252805 44783583 58386225 690218668 945958823 701461192 565993686 450791233 918908187 534976526 629404265 40503574 577192469 483154756 539276557 33064931 109971094 93718563 22358284 759002735 506087159 771622387 796675848 170421485 678180138 123342862 701745473 255958581 486109120 8169846 664610086 39250549 199459186 881527907 349835490 22321785 938542620 818410319 389455592 49961882 43227991 683355245 409041753 669571818 679218040 741997669 110246526 427936893 412610042 512262925 341022846 84585720 583962076 443306314 821409727 53876898 418392493 854131345 250296992 968546912 234867496 136023858 23342770 918368339 51685778 892439230 993309734 811789332 779676727 81519889 10190831 626071698 510119758 828037076 125086966 743108921 814211136 473725840 981275223 411225773 869173959 22945213 33583850 241508139 76161115 932567965 334115143 596433268 947737921 537990220 888435442 273637875 62238670 806730951 308308071 3175927 276654264 219081065 101450269 558595715 312639093 780218683 393218371 806941350 697000417 755675906 426646978 207845107 444286521 115879600 613731143 615347054 4159467 627141868 523619194 79791346 23339688 73590587 33881878 955497441 955740393 98572432 435429490 786636295 879840905 706658865 230959339 23622216 320049967 426221406 645191091 874694506 110476752 356883050 4557051 73906637 903283287 920287160 89055620 754665153 618790483 895812201 700774862 122768680 434381765 357391396 958393685 595294489 781127022 834307837 291068390 811644636 495254702 99143936 12289121 970766885 38731708 862211665 764765471 723626996 799012005 779506538 516120660 546444159 92383866 64942275 563106443 169538366 867984634 154291339 954734416 16481100 765419009 970221927 676578612 330804213 138712649 762191451 411745796 19265932 325450199 200628878 420209950 542381508 530885213 940688447 169081287 421287400 116709413 675496352 114108147 112713052 287671504 909261525 464801817 526097374 721351891 9006494 486746071 975987068 934539284 106335224 469698658 75441828 935434660 122534127 141721857 945826426 623748460 118164338 713122132 130400389 998979755 618551811 824914122 177206616 899243564 389634334 906595029 746160132 556306885 498978929 415201362 114905225 417279694 331187728 141998313 149771477 358362849 460240149 813049521 484836780 98787936 116942993 306308118 395199139 737970774 356720387 418163657 510073409 842028011 47530341 125991344 703583016 867751302 527647709 8028472 228999493 296745199 732493031 279585538 299900724 287331953 644878809 921138226 360536353 483099878 616942011 893314355 876171502 519049829 591885083 668320271 119304081 186924841 24693967 5616201 49676580 129081727 311063991 870261711 770418832 250384855 90755284 49125521 18894193 520083767 789411873 491361539 238746452 905127940 504094004 484921007 366907478 188415403 99744315 803914248 567126053 948109157 334902731 948522902 53285427 860452562 471313830 451833868 262605456 323966179 821487080 353948769 80220165 433544611 172246000 130549038 556861273 226643457 353553793 91330896 695028308 970178295 736234166 86837142 330432475 978857955 940896859 376894477 536183130 581444870 86298012 297682662 663069565 710496444 97618760 586933362 989586235 507967402 160611783 808254374 497179737 33931054 989019895 726909257 922376388 842972264 678183561 180873223 246881650 194447318 398924664 282865108 732542539 111666494 671018952 378879061 324326644 437371394 857457049 665334367 120318012 48193982 394903749 422823407 162575298 596796274 251823753 859015275 730129916 571922448 163762758 434105093 795310964 646114792 219468037 369859154 50604985 114441877 426745868 515384268 261827119 127358102 259386027 109135573 290524067 607647632 94487664 63736909 424851482 95714893 214938242 399522234 736289510 809982328 267110135 872178487 773418359 123827616 259071363 263028666 994405708 51955174 770705439 772421410 340953527 712519865 745517155 132705612 295178492 170652246 54591549 130587124 635446184 300799729 157502037 82360880 259824686 832205023 101790422 40117667 95230952 109749952 26457332 725204345 185207815 83925396 430336265 84149600 696544177 884606236 547703465 137208407 457221343 822606029 39793211 937066254 774930721 565270564 34698014 201436155 896191185 627908009 515249099 137525383 489669681 513955035 656006783 117919955 546239276 150904001 65340894 820245035 160756346 90441068 417569572 115221402 643320661 503148554 774612033 651532289 77026942 452136825 266457883 647197358 234285623 93902582 406155479 197583512 776351116 22550634 51366960 829032398 673594644 718861565 956286705 543019981 878787758 186286412 32035999 996580146 297534063 106028397 193781719 97104153 527868101 417189522 963150571 87382552 345677266 647506299 131689716 839357105 254769786 980868025 9899928 31832271 74512366 139330933 770777473 628591779 62931832 571802803 300372890 780574974 938950267 227282507 356648908 571321173 795552068 610403848 528074811 950902267 34062267 46833139 584009074 440223122 541809311 651388469 807327849 957459591 928362160 514110859 127457104 568807572 499133001 650184397 45326215 26941170 474156445 983023939 884608174 373254009 273358148 655834275 366061646 4902508 230530073 458420917 656493424 706960654 8159768 288207718 124454213 638826063 124367613 744866354 286616509 150808314 397591710 147722278 277213608 237062507 520351736 791178140 905218528 233627942 777676250 612219880 778332155 898596980 259915281 414372963 76905114 906562345 989818722 474914186 478969975 279644063 76508977 129612236 637394166 828278498 680677804 299426031 692079868 807871096 143372263 180955501 482244349 477473059 890780615 34254840 781418834 89319758 106086647 586832313 645760761 711719961 393453931 678052398 478405398 173711590 933378629 719538040 795405217 289762738 696893011 97986911 539017700 184444048 925173887 261392654 622260857 885824481 695394357 679912897 328535964 316452283 89488534 795221232 492494137 739946793 911946 87652665 797520585 483014362 327158246 783465974 135863386 680794935 327584523 712473994 974563258 626884731 496884929 728565361 839228905 247596033 670685586 863942571 145836624 590260113 67715470 513511730 647830589 346602227 367961719 372669645 396392057 459990777 916821611 825632046 505937049 41702195 809105637 771971449 575415010 674172401 484783807 1449303 529077176 263276577 73100013 24234179 74915295 675929117 152159983 847277545 22597330 481681563 756146992 547233370 826256330 53838580 212855376 900015371 476492701 446289238 770310936 229955361 536654568 914968748 896818310 430579649 879737194 111071735 412322674 770414821 182971978 806413514 622616775 779792435 671719176 262641947 144291838 396845575 492333215 389835808 145284900 700348011 184113442 663646139 18062496 219632748 990673284 598130769 205844748 829486091 856361954 232920456 624377283 303879333 376798937 723420928 630594423 361631188 349617478 298656326 640549815 178180066 873127116 684640433 327338577 519321797 867883965 816852525 124899245 528544299 251652495 921144294 255499807 10924021 63894146 920050094 399654652 459850120 54788128 139523083 705275229 598509204 123750852 909361040 782845353 797009543 129360987 916640939 84045036 86620676 632750638 300936116 509296121 17555546 289258686 815225635 344541357 883636559 75706233 84322201 656986959 766373880 631848226 166483161 58761727 351808419 614579714 637872900 491447670 538866522 791079049 594301160 473137117 31047419 561385262 99398935 441563529 447709643 20737654 83856667 629713031 787482795 281602298 983331339 608629033 763530164 436658717 764396592 759307162 120603032 336536406 488411216 44791672 987316626 17354585 413695875 581988980 493736547 353316615 400047544 975240092 57994112 335404996 800156169 682118063 90560349 274841692 26975941 265574064 32258376 793608160 944375375 65275842 874399718 598425777 869076910 184821248 29344768 69238738 906799733 684631544 384962576 845253262 360211301 107896786 738046006 266639542 405372877 283798649 35675528 243623355 119374428 576268292 189918868 805698228 485706855 482731510 868231976 223422461 259870265 450767629 876700828 618475901 696578399 105270321 899226760 107209506 131370703 334199399 219545282 313610800 724807634 107620626 37087111 552800141 897696059 505026632 920192852 296999642 920970660 839221885 922589471 129290951 532524465 574309400 272054307 424036480 430361808 158945732 724222628 72380794 28243750 891782035 892273026 554424175 275548086 161921664 348587871 173920653 152133176 42227227 43383873 948758950 518555447 665719975 158780727 98467240 376477684 766572698 825898705 338202499 927653925 141202027 5999626 696944545 171140271 666893136 548744831 105072524 722336228 579910699 278311201 149933813 732238932 303910939 115022401 239173079 485513341 732330428 841684211 504713260 948316942 886683001 885133046 604843125 203778749 820484319 680413818 157580623 403155782 321283561 831882941 131009189 139158051 219654768 213279777 442988390 127533422 851484198 856853950 118984062 457837871 447173890 606271571 589350554 20164308 392070102 42358512 895385799 124171036 174437518 249148643 641093023 924963756 231709653 956269154 248040324 547949835 982981703 381769144 860332813 399154612 645612428 720675946 385817114 968066477 750131039 368842708 501571308 828620853 992187348 482222075 103113941 16686452 276307848 839318294 395451887 45444185 862179313 575530476 467325816 790254205 409028512 447030331 340959105 806269311 139459179 778724348 47733790 688864902 668050131 874028395 7072479 548515740 549707381 457286267 913783697 99997554 765134827 488942347 381575801 551279237 898644873 64852932 1980867 518633667 39901290 606066360 642357993 710478076 995929206 94603718 659751418 776974637 557628424 442269854 788517105 485381292 660466532 910993753 661070402 322818608 68635528 151562429 187100633 477241395 937665992 117309052 16210790 517286133 14217469 375278438 938197999 468816113 67872120 205866055 187592840 159829856 551309167 608699805 598490099 9674539 538686642 708298114 864529871 279169489 897299769 80010121 991280975 74175171 914545509 18869956 905711086 922115660 755884062 423136154 330968255 393777827 472300107 848322231 607787178 646858708 985046014 509884347 959430271 482821146 581765650 35196531 783055364 824675704 258061162 109944566 2367536 929433678 988739640 518652188 351183737 59988997 858203908 125870276 816276787 831383845 185153658 173708697 91777400 402465026 449165704 722951117 176931887 576840555 10987099 562519601 836881685 245553717 705218926 445203261 491143251 510442261 953377703 836525826 707082445 907617458 543233737 969396134 475356121 671142001 299479957 450930503 319156852 802528199 539615558 495225219 751106802 736105920 871868845 218737628 624271904 680258127 688365633 866770636 432484845 333606592 993656268 193535329 458016139 88819097 867368964 544143884 86367587 28556178 493287068 388857650 530747501 419141441 763819921 11637322 753399327 611867949 158395132 414728085 395968205 133266223 565906490 778266639 4490990 318124479 631304364 408707693 497476339 723953574 638336088 833797445 95823212 473929184 103910537 313152120 458223815 491283757 78948025 320502679 592501049 76421176 8445898 9248756 617981280 973417840 496175806 340731913 135337014 423995319 738568881 671686501 860956869 150245569 529471083 795725654 25875034 89982938 307713250 388932546 642040926 823983948 369136305 141088793 43338013 970968508 132442175 955538705 649264441 616011252 75411949 226236885 110232777 989836028 765776128 322848597 218155582 786264439 279529476 150645268 11782657 462603869 92407337 252397950 565104597 185752870 654730193 137108295 922122606 872625484 843645997 116712210 929526953 763433987 613190456 117955233 346178044 681168979 171691090 541594903 195316860 335436598 331290983 375416382 316160582 836342190 122700909 442838215 396520775 682891978 212847872 419390574 656030958 731250602 79939227 361292008 91470159 326611411 182744717 281805181 891197204 445931575 54036189 948112683 394164213 523838668 621007217 290733471 625111944 559403456 3440198 630311089 101625366 768010191 570544861 425956744 137479082 65993843 495414152 631536439 368729993 400148881 530927404 295287515 855518160 290681649 754139590 375587730 48522771 271388109 112148576 976415116 686291079 152458488 214778717 658847784 829004950 212276108 754192683 267921781 481127280 30247199 204011026 429396564 115959000 593701874 138355550 409900921 77222865 804552461 556153709 72033544 634463941 972110804 3658224 147190424 514235174 69335662 826791263 661544345 845927668 957534708 836348510 228921149 127501238 310567710 119201532 403846023 37262166 347465879 643953932 409116016 917710059 518370631 707001110 540620113 198911928 628202358 960384026 480195902 201941260 795556332 475047474 571657744 9849924 191415043 182107689 519715242 38063139 570012139 269454100 819514018 404950440 626350931 115242917 4923266 579409779 449283349 345705563 123093978 252192888 620616279 162689446 367798063 917070547 507510682 719948262 247555430 781249543 539013215 902043231 198997369 916725598 359425202 780832775 183865802 3549375 672270350 729267355 900223828 832545853 387669291 92372033 13548691 665523405 2512384 423431789 650233337 74882217 705944327 752115986 724613654 201903835 373575779 593400666 163898566 214641433 853504312 449171596 821977961 221272570 633874227 650722194 701167228 67791679 646872746 428004102 187686636 943280650 786564168 667602416 939216978 60421921 898928057 529359126 707042933 243539274 853708708 943992943 80192159 317352838 192730890 822711748 816612444 30320103 429308554 636774930 365218703 515439967 843455143 411017748 667865078 704304849 321718073 899296606 281111228 965347368 354244085 955650305 584463416 486414528 846194808 4905747 846494437 100308125 689934330 107552282 597439641 327474687 13943989 866845950 343782174 8949760 680701380 695667863 981760945 132304486 434378260 298482861 872607207 743485880 707310108 84477136 320517279 44904671 739007172 241087328 800546648 595426253 848200923 716447269 388424548 48558197 659771469 113971794 554468984 821631527 634185851 593219468 265987427 537199376 481622216 551680541 53426613 292903439 795563543 803264173 378733763 29786805 56103656 981787131 779434010 90121142 483024231 493026529 97924549 283878144 578769415 69598767 515356195 582982786 16764813 445837528 620871907 371083370 505671896 234748087 276600442 314494711 755335704 151322905 456388059 495482301 776916682 731062386 4538787 559922167 338502809 532513154 384205423 650179604 171791686 877806806 879295324 481518655 958614461 803888005 919038530 223662611 1104021 20889896 56630805 251645786 808386131 209630920 393674554 884074443 199793102 405708247 270889876 973776064 281417055 17435885 780104975 629611662 24236237 902482679 349370386 647769798 472371537 694341172 365923200 825524233 486902536 458210676 63435162 795840594 957671614 989844005 899845567 917564167 213847434 39159932 30964336 519514350 602133520 115109170 550016015 349530611 986166304 11245554 818426914 668367757 917401283 623739693 325322438 993811976 17541107 46582413 226550977 946726080 918869131 878562334 47057607 61675456 492254332 4511452 100502822 228766006 667496484 951796432 236929315 636298861 953861608 379582573 263350946 175536149 740992106 389618361 431115396 939597366 365657165 294736213 534225103 885139786 925143727 108998603 928931502 345623618 100349432 236697432 34008574 144414888 317463278 48895970 894271339 927816061 718738132 29231921 320102856 522148251 127456109 906589676 449170839 602233640 443320941 67245716 60807193 931743620 157229188 939038678 358701115 496004448 608201654 23022252 387916098 92973635 825728779 984244933 138039284 743890622 67357961 947308908 770019670 984120062 186816034 195974718 654637769 731221774 388405609 730250424 242795335 235227817 749487964 652604487 917589552 640493129 225458464 119234334 162170659 238479542 714138864 38745937 308379890 855732791 395996150 248432769 494300587 36180885 940202444 590763454 937433069 143034416 945211913 240068126 496182741 664309880 288655601 269110628 341747408 377397372 43899738 235988839 655082836 976033324 357458807 298391784 489359715 599323767 136230733 205323601 660503050 731773201 273326032 323082085 201926173 541989123 378521459 963582193 751718918 493542719 390616713 30548284 969379327 547385941 888528411 43189280 618696624 111302566 996931997 768642879 466713842 94741775 39613192 851949146 435805467 308725724 432735310 602709622 853215827 250076564 204275741 228989206 330873012 147533795 49842052 176728828 311511589 10128131 572272798 757127914 1203895 344967145 804425956 222962752 123475690 225175531 658946697 343952094 924332975 160570199 109352086 781974411 836967809 900061207 453879775 495447475 191596100 870627619 477783647 668382190 12493067 665046504 577171865 343884750 792482367 557546669 215697216 63674948 530956602 786018301 83150335 643292989 38065250 959996785 414287356 578570490 21233586 183556272 36708184 65098502 41329985 788801686 766345443 153907567 154150775 739758915 138213694 966189354 620600905 904298628 805254171 464891797 890907587 227811019 649415504 214464868 826438582 821980650 266466593 607750 269997787 219843192 232638298 177115071 360646749 191041803 144492528 474875111 176741519 317787804 60753511 822488824 10391001 488340172 643733742 210371402 954053646 666703014 500848024 764309969 303434401 695782823 766410018 239219592 267257332 51151172 704272198 920436363 94721725 702632842 137583835 679093867 448000636 469006064 319916352 328037748 739891981 434191731 103952183 13096442 507025403 360820119 957387746 513841823 107757768 549054127 8443102 962256384 91167172 529276196 667743492 15314016 832096113 418823699 511475999 59446 999092116 566540913 58100834 981598003 748243361 61914689 218076069 242868026 663966876 759216892 603435142 516633654 578399729 298737106 57757050 60114100 20347804 328603727 307861377 938040810 974424237 437842431 538746389 712465943 839250101 603837205 831655554 456799527 175595458 590314822 46747408 852138295 112843994 133908629 832427319 897457069 428783927 763808598 466826592 196752447 486522121 507026712 175799060 510264920 120291163 744426486 129184552 891760119 523930814 22221392 605742538 642332580 76340363 797705454 88118929 44085045 55476294 382153654 880341442 529249636 221349572 780563194 95468876 961054973 19383896 953566078 62082226 324860290 816425128 29583738 145145303 708646301 274057839 885144099 790610896 108966855 188321444 520575402 462386730 737919458 287230953 740350387 548686785 483998471 41714102 447700095 860264418 249639847 661329132 376326424 578850947 646928513 217796424 192346874 603984355 802816888 303665709 288409085 213862088 285449710 74791766 747260861 728906365 482537261 898456327 43443957 18128513 890706958 796301641 323575377 902750229 551115942 508650877 910357873 356748408 96134026 816855632 29634947 5814966 533826150 976892725 916509532 668466165 423860892 419716517 484682596 654901095 68995984 767295480 295815319 343406822 349881059 433694899 343631347 621484018 714393290 226937847 213420651 663174061 526298491 13579438 596331078 230230591 867477884 227278677 292278098 22875591 863446896 404961487 604996438 633026693 645625207 935452599 217013478 711253912 943481554 868190402 672171890 74450135 447919585 47244132 49117484 676794912 464169597 637794069 106997278 297895510 945438607 755146890 125409654 78580265 789032722 561421623 917539684 802361653 242465652 136696577 237807699 159891798 592368361 993817607 112181324 526810752 826194055 214204077 945312961 790898215 849991416 537470640 745788970 406133023 174670589 871405646 23686623 255054769 328126365 81794253 326459285 127951751 292405113 10133049 447908202 855930051 416377676 557861800 862631570 586679287 221336426 352596950 982518349 977091632 964572187 210678900 827205238 822266160 770065869 760586655 2721766 647547769 35697428 257191586 881871332 472307102 965887196 837198693 485561301 390910501 880297328 142330707 648371563 848817657 344477372 15262086 959308603 939935786 404009742 641403752 852418765 531735990 290535 26511154 43833543 916428052 653536874 762853754 598632660 51192197 39274304 805730893 34707510 799508936 541491267 955495324 920159974 98924165 259060149 867533546 15306264 701808249 104013391 687314229 168671362 974128866 915992975 576627254 928025908 950669367 621700683 415419720 282859415 282355219 752772704 817633423 10044980 115216166 993792718 693871901 861798669 265992640 624814267 851313411 488425557 78799437 970667810 728083252 326357530 210734044 399505377 98468842 403402498 172872079 708619134 964945717 839125247 652899674 790851589 859326812 671164981 331199748 196534806 330618550 165758255 405663398 517112733 247367316 121606261 17937033 612964823 413687274 82926904 35571819 855091261 558241097 2046730 39635952 441497888 698986425 129279079 332991761 250126239 246184888 221386619 403212123 120723101 768578933 184951998 872354949 591731546 28286137 604180344 949320364 216822310 282052 31421020 398046328 346036063 235356537 765401357 673544763 880511598 448599303 940867745 35059126 266668107 92486254 785777391 329143259 140346182 299693171 93955976 510569859 595928573 55263644 541585907 398626157 353803831 146235915 504187940 63703359 653955210 203892318 581754855 853764966 889521149 193762601 982809349 779982760 723027804 111305227 248676846 508556854 330113312 264157777 644021462 544092726 374038728 577228499 88710966 50011247 872905546 462702159 389862298 235997261 796631390 570699526 877927752 764551099 415644086 758811483 586682089 61408218 734226069 696489215 108343549 449835737 39756091 899147570 923746823 253553192 653904068 137327302 662511030 913133287 112996341 546921011 664384489 188103995 367898775 669274906 131468997 424700166 493009106 12117610 442686577 349929625 102460014 911037245 37535377 289850793 29349749 152954405 166742570 123681496 536673326 230234454 577898256 814920052 503575170 354812557 920024621 764508519 492980604 326063074 556779346 204201437 127645525 795137094 78386771 38967780 741927897 292093591 862328667 938239507 811936000 97242156 906822297 270886114 117569552 306488418 485039014 995746058 163918929 911387443 480862222 870384687 44297886 923684843 211855332 124661392 387442713 372221459 99159474 918931218 922058543 588897221 636426096 944816606 831572896 215050168 926157447 966721467 973889508 833565294 696050071 963079860 691921353 291193138 760800625 658453331 641884320 339390553 213419611 438673359 264746334 798480726 440234973 948010490 31111531 845937068 115520508 813901418 563262708 648400574 336405534 436329159 874987649 742363859 29372337 887095990 236304581 873812758 677828714 659410635 698907119 589361715 207747235 592330395 710228114 882763744 438690057 752411042 388652552 231149062 124350805 462374298 528974834 690698230 416022769 680885723 853458439 825667732 751206582 472646155 221900026 442108984 25237240 900975993 589281126 646266490 976077745 104042554 384478192 939640893 97215454 251020361 34286391 164212844 408765907 328395390 308330134 226505121 530529357 47762527 378869083 363647820 90434572 662896369 947074919 339355263 974805650 198778359 176286753 471491652 938499506 93793321 131332343 836966526 671476404 270318815 113372072 64875918 595327991 344195136 359667506 912773878 160355150 144495906 324627735 55356890 522814273 583869628 37016425 950737695 770089379 801214156 283836396 670089357 580540003 910583872 7629954 973558408 918239957 41453151 711369001 730298730 54674277 373512973 330798802 693264903 604422940 731664042 379152944 632510931 360126439 829104799 535933182 882557550 475176215 942429153 360355971 598903251 511069262 753965275 386337750 335482563 103824738 664106905 172222070 521336106 362636976 281048640 267935921 718778260 910684639 760758698 101269889 674432702 771716842 591202455 725788288 616624650 1878969 953517628 247783076 312328571 649221301 890957272 62866814 626528924 752266199 894738476 982031610 238920200 884848351 114941554 27861197 697643283 822906533 795396645 145693134 533128752 993142774 507681328 440511937 100955722 836678874 131876534 38745006 292732573 864280906 389782028 241404440 480775669 208666994 225355801 541260940 24851660 862983874 858380252 1738012 293463467 263514482 776602054 92581953 685180346 18743202 129861677 741803181 343475426 148403418 780693931 790776919 958853191 521255821 953749206 637925806 26133743 143137807 328399381 168385449 463756369 135122014 898436191 852501852 780695552 25042488 129767845 750725913 983976860 74987314 324825959 239424011 407960171 818775967 885429165 493769286 696539566 600087737 884351219 349578618 645536306 441293492 558670147 563617717 965564474 855660980 189068673 548856392 980078251 768553839 763197140 134491643 248230451 241425608 43567667 742817414 209820281 74276165 464468020 3917067 55113784 731899025 240566353 634454411 811940094 959028592 174253134 652195471 485708581 511740392 941723881 598772771 465575549 645309216 712537734 45841438 96359543 105131135 352906236 92742279 232295781 862882793 514016954 903700838 141110807 827370155 653563954 70503667 691624966 604784123 566637204 528980024 777926560 731234178 951384706 552479952 958730477 606285270 819589647 883068465 472190032 145775353 560478416 97445164 23810459 750409265 104524865 693723159 509375522 997543084 94742431 843617162 779566012 161195109 22279868 234043601 528227544 15897082 687246718 34013985 442378987 475231789 728977724 534384327 620755329 559240571 767820719 326551182 170475914 445484694 133241810 362618621 120039802 460264384 427388588 934666142 883932561 110149622 739733590 712576419 548536586 107087525 228719683 95967245 161251012 21379364 693184893 259694870 4892580 418175246 350344663 990057808 991243872 450585050 955579222 537255082 270389311 357736119 664207274 504618784 507942457 534339746 664461040 681718074 810396167 987072689 419494142 249214687 958115953 222420059 237863958 312458233 680966888 863093525 553800962 538625430 34013099 220466563 765195038 146403555 735756264 437651394 268449755 764851710 25562222 127518948 22262524 504069484 72813367 856047220 238153412 882344317 979315056 826437356 801375268 844162133 201475374 762366340 996600150 279236222 871397653 889348272 583186156 287320756 102185761 596634368 825636905 233097193 654333817 124689226 855248751 850670458 65227652 64470388 15014800 536613604 580991869 915161146 835484202 734882122 778332329 901521398 18484726 435127908 805893493 265536994 202201464 873837666 741952401 703932319 296035882 548420447 302622999 943451291 714065230 948662946 52499866 335409295 872409462 714952959 836338720 857359197 813714381 921720565 557973338 589767089 578417112 590893187 177393375 536113361 408837287 528079050 667642071 458214916 341718264 887574164 37545480 459651914 871023533 43964373 760782793 151729485 847327178 856779161 802467564 668006760 938070576 474701399 197626160 138630983 98641127 589986355 761632058 392940811 643979146 39909136 737934082 740037943 739891418 70224321 291624038 560485984 17619118 357713290 73498849 77998468 393683709 244963950 382939545 56425950 310636517 128157134 803814969 46027547 76809859 891568716 247482818 915364728 755098160 453888191 429873765 546341619 516477733 312340551 57590583 202765456 969938044 993302903 51485784 471602297 650626374 90720488 25835640 427887980 738012898 710193386 506111670 36095117 60226159 549218348 621021802 535863566 505500016 493444574 888577345 511117949 217742615 80957589 90011544 433989223 202388943 729829925 972424652 983534266 871739475 984878263 837976937 680606327 452617161 542509025 526579785 446320402 146600637 753146144 858609984 715360089 89038042 813736776 91091908 411797795 538708056 275224634 20631194 3593585 60802751 502581857 840070142 501364410 498769814 195572851 135888619 543359475 142212475 808729986 900856033 927618475 899898946 667221373 977478218 19472148 643838864 622651787 220755472 532942729 807116438 699242208 926235244 919750577 660639727 881419893 681927839 40949228 38891150 601491134 848924481 785363271 165984429 912002522 435581809 844673012 552389208 226574647 344547770 991419850 260763649 433486988 351259886 985320171 29695174 663545086 112643303 55862286 13027413 494338647 528371658 497558855 170337761 271030870 402999997 57510135 205180989 765611882 709849722 172601763 460385416 314089765 391859223 793082453 698752414 491223496 859119976 342355976 868181513 522774467 707828764 211593940 26413342 547390906 971975166 78495427 717665525 536300317 403523132 52884070 557296404 304460655 409659556 315568604 624386179 98889336 28194215 852225868 791704827 167312349 755517492 704645105 745433371 872031571 806189863 951660290 889252946 335547143 41737151 42106060 154413751 864629253 594977694 106225820 571407855 897911373 828841736 764105704 165319840 479673434 217777594 875871064 912039304 699271814 630844708 273203889 210686909 607307432 26218627 422299548 155033095 743547048 587877037 24567853 33501850 424860630 249465329 875688753 995421974 159490082 283178490 350081450 506699142 319802433 560884762 484451445 857892110 180448584 345403496 341221203 916383103 691057609 13654681 506435110 177183903 163001104 517888197 188667460 41099020 847435156 731103182 897218581 715483405 368631476 891857309 9919497 360728454 209752669 85404928 320005403 31739327 659886205 894856099 811437724 105630590 950290411 695038132 342311685 916761254 958695594 20006689 37934863 354539632 273436371 30066011 660773026 974292539 371877792 972620568 188348606 184108558 936065820 786000590 139986627 53608296 637439482 796925932 871594557 903746506 115674305 665326794 200060023 596882200 695982035 819598808 37037392 510151486 361289572 50528307 411671887 924561016 698287992 128133883 767540481 911558410 413842366 896579570 713043763 167757675 650176986 127790960 91979492 504057976 26882058 273639639 298907640 569416919 795988373 146425973 112535590 38508473 612289736 804918300 262358841 474075168 409979978 51428795 75314665 738668344 988856073 328057972 79796749 907126487 881418728 455326262 977212945 855996131 734005658 287008832 302130034 41101702 892511530 267993609 895361898 929488351 114650173 425588024 382852983 749062063 936937321 755437437 506644367 192177586 906244586 298715572 488813690 366721249 998926825 83462370 31171449 498473825 308831600 857688173 254868141 131931794 174521248 508915106 56287382 567681297 897181899 98969031 220144433 646123422 719017516 429871515 508525869 602326995 71876201 137483787 790565709 556530368 314595485 94539253 576288163 523890765 349117849 698347733 132200870 47409217 90260276 880987144 998649984 371057908 77732062 772691852 798326349 140588028 69431599 853247266 778471837 98748707 250599768 407830781 437096815 892080159 253370731 89270757 868483996 164155307 589225195 853717820 890116905 616699105 898739085 500790369 795302384 708932154 783421916 749885649 894045341 69929900 431236163 821844688 128836906 698346160 105763459 242957469 19751730 47806244 906599280 610585267 75195228 85795754 800672113 556632861 682690267 763153320 545492550 278560579 46262565 938811513 42727676 657474206 11094552 782525016 501051456 681402877 600826060 615465420 846053182 919564859 479739526 328585838 7200954 767332840 923724839 884068104 93253529 796466434 738746259 150889831 974669351 55484713 316630365 935029061 895566322 863253803 307131083 548891434 421545498 366616627 595049940 172980695 741149668 890279248 50230612 264805807 5064859 18701105 776842467 838235950 531849102 753880272 105175976 106548923 559349035 443291520 572766969 118220254 505418697 274199788 768892226 362521577 281999872 868401547 925918611 247572109 61573496 364569768 346207657 971853248 969881826 402952046 44576256 868808630 118290229 119962031 507672256 495060255 126040501 736786137 566857729 733354983 881510920 857313559 401181584 353192480 461194246 23193693 914819916 188377464 669124964 758877450 340884389 550517499 188037611 45161465 966998058 180103504 195116299 905070096 886414965 882240710 592497276 13008365 381220333 226400924 572268956 692555420 210538972 268413920 517077934 455479101 605515793 771891590 233224797 651490598 730831374 269403750 973281568 560357371 210525496 41922788 221644894 449072754 101202692 692536370 890365622 708939852 912802202 990901687 141932696 401451627 951342956 998271349 449790404 484865782 586224550 814001186 447084906 903696061 415328837 902872481 251300237 295711382 744021310 116347530 681274643 947585938 131095586 798253852 922130949 12846285 597603998 149360561 42032225 499426062 133209683 177165201 996160237 475553019 478417971 592047423 249285004 785428703 118216406 440745361 936167018 693856798 607962548 92313582 824141312 866469406 664679529 58895403 12543795 956105509 438121034 926259716 331051481 645073562 253889672 866672487 930378249 831758908 46386558 82299639 230547199 746257599 46951107 773718672 669199491 656947670 899022235 964725125 633624219 98310101 321399667 842814258 377081788 389351813 453231876 343627217 759092530 15271724 559767978 42015580 219673547 321877008 68528435 499134025 667394765 389688846 468273144 886631794 24496997 197130127 746244009 611522555 795809115 635625483 373815797 125394476 261957128 371957140 158738757 747582519 840045077 873075533 817684952 83114305 830715357 834777724 391503189 897164887 167553416 512163267 606533065 689312918 755404102 946383022 595544266 684161767 79355125 927202860 357108582 500106081 31892203 288810912 524917536 219167448 405805703 761349221 288771715 866133557 462516327 414067521 385792361 552042806 847047174 445719227 573049225 567129552 213938272 565874198 235534995 824282738 302953963 63512298 151803121 144465205 370162519 854293246 30904874 874641585 368517152 117897488 168636407 741145250 816025922 910063084 844680626 325852637 521953403 129420 27661487 50127451 471441105 88956077 436151021 28505930 3274001 132005404 850158027 42734423 977892457 746157502 512104475 618415921 42999608 578362967 35383241 626123040 580046174 407755879 325702548 939869805 649572144 345124632 156342671 278754410 9012888 155736520 474087719 827946057 742814280 950125721 867555527 739246000 107585877 600544315 968123077 908428661 144737029 643741193 128578937 450607049 118294993 200030579 894995470 6362474 145858518 958232571 827913716 992237671 120979314 218257039 136947169 361561571 534069628 419555108 273870249 672781194 725087875 375180172 641146406 822171837 125241433 984730721 505722190 80039345 334965096 203712879 506385807 141526960 24697616 628471435 394815293 729121993 811629763 245284191 470262738 758978378 889697638 219550999 616717841 420656459 249902261 422248867 450721175 888927028 945789189 204927623 802256814 273415157 821005960 857699517 91021680 793002290 705957942 187964713 174469848 999540375 657978985 52464264 737046481 854513465 584641960 132698467 613565986 134520649 174207802 683279125 70155138 714822513 791416445 615443369 475442025 760425460 795506117 985589038 46554127 189621684 105894034 644552916 886305516 983193592 440998851 901606154 650000240 304704585 568928841 35312368 789465598 394317614 954565628 681649900 457574327 312757176 617356017 54557187 114591481 232130158 226740679 194585369 571664174 117918934 883584398 346519953 778161179 379508417 371516123 336500626 34540403 138425234 788101331 87402262 676943236 809567418 90673775 826687405 63486586 305618693 545451399 941440791 928825013 703346642 397002200 977245943 617614939 465797016 865516369 472350777 699932921 650146753 619664929 560240594 40833035 233519046 94944825 743264404 925425201 544764827 932622000 887776319 140197271 505956132 716935245 792881170 817777749 495269837 353517881 635241559 9151001 329518064 642737807 651561033 767148772 125061257 103996336 607692266 51672724 880062074 483384023 97599732 474151188 894669540 823424258 906866132 7620959 29400865 219082439 331564509 677600570 326983143 195014922 555731926 780082673 461803370 523322526 536143211 910526237 245979931 278663036 975278786 560840523 740926572 642693492 699737406 866114864 148343076 766525937 247008000 377549543 808459157 436978902 703294946 528147528 25573239 105660245 655723418 4876763 945317505 660247801 529749130 819389220 809459170 64328217 773030450 839670572 228242361 456529557 726155540 346578073 962005441 21051818 630570212 954716911 76779634 383577141 828062265 548438489 398833471 690646582 340953411 710570253 190642976 883858080 858347455 598002480 197175172 148810255 28468802 733768774 246161669 185649955 718016366 990434063 79532138 754776704 139123071 424724486 108776768 702539373 714133999 164001304 148380421 394183352 845507841 550974682 281977704 850329040 769466267 273010429 461193405 802037584 883783841 758096229 95804924 373584190 734764343 946304323 65828751 222701624 675159619 104108979 707904589 485984715 857757236 61104913 286051297 241224818 963857431 875655268 225618157 301205869 748067498 401152542 12567233 202544328 400923395 663282320 991302435 641874813 179606404 75786118 279465749 434090648 759555271 202625123 404339891 102272123 693615433 846308287 912147300 366876939 675146430 29925103 25973073 28714273 564432577 776014612 602357425 376291789 789719080 359622294 945874372 282093235 644574910 108475027 73629327 123458567 84872917 115914761 997660648 923156932 76673390 745417880 611674334 406296543 775467582 998358803 126651204 263453223 540000619 524494505 906241441 38836135 469832607 972217602 5633632 781112906 390038803 55033149 962623736 822801295 967123804 939011457 108219190 68744162 622868998 369432033 668938348 769905985 220899914 458590707 215186660 279716266 349562573 730373060 156454940 811154424 639174784 690354166 721284993 91673230 6184905 663445051 578838705 234155797 59400647 352718624 880009620 394768223 85500150 920401557 657220930 49252114 999059097 11590580 529333024 268346619 385950027 261473043 618853711 603980128 731773699 281695918 409319032 827811255 270175644 61602144 53078126 671311949 653807277 12549681 55031511 935093870 837327538 503575569 361518550 811015681 661826252 495992745 411509333 339999585 712002200 842077510 879460034 102315978 76181349 272640803 336835095 420531367 501986086 564365180 643273233 60531227 234045283 556496918 545379913 532954167 999354904 688251535 96609197 6098619 213236249 858896941 888774025 876256484 592837234 638736599 768229812 966747714 267539190 847876353 349345151 223645153 707687415 337930013 288443948 6825951 700086938 91226825 738885589 699630563 10866788 687936271 885913021 36002490 296422748 962531437 64510580 543038097 35779723 54366495 57114684 794265551 462749099 385804300 752701579 622235548 814961187 194931115 87649902 544061422 847912400 162208502 81528265 943944841 419225492 821960009 67036953 847094746 452283253 225484563 557880227 172334159 257732282 231930769 377598472 483325213 463685131 730803526 155867483 527699213 80677622 325068400 226184026 428852986 776999564 183597935 943959647 313564865 159799511 395805821 197056913 515736311 736162879 36200180 471514931 329749659 240187678 712514627 657482089 143584133 594370944 291491736 691391339 180203850 734147874 529749497 825557389 251176850 723934789 322616593 968336717 997087425 26416206 33999663 994647711 31353723 621490718 827000190 878013140 406688637 568435430 686993348 70591689 23527073 75486635 334000840 29847816 288536955 215489531 868080447 617136783 19363712 614333590 3255548 28887255 969752335 374080456 131067348 678162855 980351128 59830284 131176742 807737675 402954232 81316358 884412608 588364963 280700478 858828128 879717581 781436044 733073297 442181612 98412389 454596927 811202904 306494497 587208767 175867129 861322025 51992942 966998706 983973018 10414820 534161036 162870786 120612149 51292316 367469268 40485345 270817666 907626241 690849618 458412169 509465788 367160099 932227834 705479298 733329593 661802612 98675265 370765143 245176579 809111501 663506275 460346826 812991282 298992485 54944609 36058447 443913469 495466999 519735968 31899952 419048355 139785744 617829940 577330107 648952975 676169484 44524505 437503082 130275040 246744181 31489482 755708584 768844702 356764287 155990957 455443084 178074 638367843 12998661 218125205 275718200 873544015 101527338 267937242 740980307 398333990 92825425 836752025 213841744 298033171 904601965 253966767 369429574 420588513 107933839 567817199 679298097 940032021 80969162 491540377 742488002 115843738 803977087 475777479 310454966 224313124 196857777 109319784 239074697 979490714 838259137 921553011 682355485 578923187 506561124 147617554 457579565 193770820 913924660 174195401 681876940 332973382 734208964 409005480 59931507 98990900 587696716 934375031 286197278 901748907 694744842 500932527 830046821 336111407 935387611 124760162 899986456 345023365 394810427 647339131 676602209 727398992 917923014 802538022 59215788 393277058 315181 440736476 786836823 162169129 419786254 863773777 456399513 42494748 683115535 675203077 834507585 353265732 692340610 895194596 58105862 273125021 239657502 37276114 581889915 976234739 802178487 311478337 598745414 798765028 923531393 927788476 255117037 20159572 666977219 814444165 302298371 929879436 38143405 564537732 602892472 985913552 265231406 715656311 772673902 496640699 918759045 968809157 347451917 409294598 417149017 282383036 72809376 788970483 308349328 549098679 964249988 237931248 88896194 222676018 599304646 607842664 224906841 231019739 891281369 67514152 631948820 502661450 30306046 400073977 272015876 925610310 153903074 871615502 48747699 549764289 413739023 952672347 73530838 468153944 30721041 370917510 13030170 540675546 923552937 935373415 240673059 73357084 842837760 565058480 558148098 379474762 598855116 849547964 526823817 252798932 68979552 491122856 522168565 114368438 192456595 507602977 478171749 541740141 488848279 948058572 484720636 294239375 419298356 253606679 405376430 343513920 795372076 525740529 373330339 408752811 108290918 126793011 499319825 495168071 790620366 475150567 156858148 352441761 521740473 509360782 749807904 380363704 506917781 699500812 184646800 37859457 441696059 527657706 383069473 885620777 419224876 18628319 701011812 603198614 481769783 91376885 113460362 755787370 152538779 771250976 996822112 69289331 402611215 758680580 534079015 577322417 726728567 387508274 326621539 559987435 435462085 979955391 58150888 29877003 424577795 938308425 970240826 787192683 493635786 807310135 659740393 798698884 959332832 992647520 773881938 118243859 902147932 165728498 905537499 152122598 218947850 9989411 974246561 392104124 614166266 131503305 415357566 592742206 834579581 563302504 110230524 951969857 4199643 509401322 638185106 89221549 602971631 168855218 123734433 633406907 386409542 187585638 38785842 979063225 888881033 172751224 31914218 658817017 104882559 470056698 798052814 483747508 118746255 194456425 906491082 939585128 952951677 118757785 742746204 805972389 798563488 476710838 965034150 177935031 256812587 599981011 445112406 111626913 798759663 833361838 424048726 636180330 754689669 30830895 424255110 602887502 695361340 124996178 364718652 701017398 697082516 135513799 686210676 155630336 836936878 380203890 322912599 293837196 102326844 820332702 279670546 374125111 88605355 984017308 607313203 123211824 646873454 439903458 464183757 875781189 194488757 95389937 988832269 720962722 117715474 404494403 197166591 211610810 309947432 638628843 104658367 997029048 252295389 195866939 636174694 14470486 125746441 882465589 870049913 505697140 304518926 596041675 808685311 942981886 267226336 884706469 84835849 54439376 720499160 562058459 883424101 799891921 535869221 955048670 3180784 358285863 959315025 47870340 836377105 709517314 673766379 310244416 187587990 285337328 333471139 864581344 937254778 441464873 937081898 37859429 86720394 515732486 464854682 60094360 481556202 442183243 480329675 302780424 87304550 596224143 580457693 881704771 967883669 825160630 25299278 3186434 14771904 749227826 575432415 966698236 228941022 668528171 111490665 10828243 40110456 619530606 450157580 6520451 860515732 533012020 971690275 378278262 171137508 620455395 606195705 668775761 184789923 502865493 312173100 183703851 222101143 527315109 67492635 63291179 168896891 824132544 719105630 117824935 889700361 58295038 305122406 794290378 880016488 717220121 492846230 422144325 841167428 409075967 37585094 918422990 615700066 494781210 524077058 125639231 80587119 512994617 546646986 560835030 648605721 489343869 687505114 81908263 95141708 318836182 500973381 369196352 2815075 861287063 611870255 197152074 115107238 310523469 375643045 623696907 606218136 45773578 310341592 466319953 271605362 114047384 238952958 80906988 239560537 555069006 375804468 396271043 780613548 794284907 788065391 483358682 671693545 979345377 188558756 568615961 219189149 770534410 838399232 128646029 223717224 564479643 774074296 203721118 644858680 582830123 952946488 238567684 255079233 739292813 101393390 602630362 875598076 618897282 188794278 232066921 311400067 76240102 112618827 851515576 591245418 654888851 863211076 736502041 87023551 961419822 915971520 570538138 312963283 579407650 58996177 558768766 73623603 234276721 944286668 514839518 489127035 983638301 679793495 676251619 277483803 128757509 511404428 737627874 681545959 65143009 789359134 397955744 178095844 457607962 878060621 57218157 740357684 464306042 429036468 713297891 936898255 891833753 406992383 585548580 544896700 1527864 494946834 12752332 727546065 887790209 373646501 634541673 338090303 41975753 111827649 232067390 319282550 413145769 926292026 81107073 307421838 140643425 488978 421280430 206586045 758067957 620637420 725027655 717567701 39655996 216850905 333394570 577686161 397723034 561906168 116847842 61610330 190660228 173812444 480948160 960239584 407064277 793871038 67598627 904236498 908518908 661518358 409164159 372344391 17793951 355669296 79830043 112193676 941432238 139579811 304197656 638907726 496877654 251789367 281089773 604753183 46628624 3219254 4851153 514890235 194044007 417432697 755225502 446641538 41944673 27939598 429371734 698641190 414860306 825227974 950128464 913657128 327257440 303135885 766570283 785309800 60275910 237899758 914148833 794387365 155571928 2757269 682720199 473241866 644080215 384070750 888719209 747942550 94130084 496340790 966134354 489194483 117236837 595471863 821789615 350708642 310496851 135295741 877803655 826336467 460238914 146797945 360291562 309359766 351660969 490892633 947777898 62400012 784965142 917081267 894703144 595228108 19966624 364562408 222508137 718190904 421905513 122421438 833714990 710002027 584908251 165800363 320393976 913013375 38097582 941874218 770981661 765412201 855799871 730431132 132471044 86234919 591783680 111523697 418513420 946089209 952396469 731816586 795476305 130033685 485257990 381108396 492559412 689540071 278197279 382730406 629372649 154628393 384171475 434120637 56558972 837327133 496768734 923159643 767732098 191603104 988343847 101988756 226033558 840399535 595021620 844490102 418683063 295290394 110926935 333174143 167936866 514356476 960574729 390373929 452066312 81345892 380790546 238400334 382890008 371341238 337670656 224398143 478288463 562890114 828664157 927019098 416104295 258114627 8530821 289065970 723731470 407422876 378393490 753269435 576256752 788944666 228948078 432613294 699470357 465768193 381088208 946238274 103226855 352905559 726858871 430043955 111757655 410183301 321194809 340228077 611805019 248214269 116938381 21772812 301887997 475174559 560091692 40225837 411255426 367551930 75280510 957603837 998199613 391607099 496096610 364189810 402704492 178903472 353531298 860741078 818413526 236334219 17433555 947966087 284830310 401954201 808169586 865126399 715080997 840789739 503707885 230848493 160633494 380172573 796567780 501606256 623013311 647416977 984959931 63087366 599905585 970406202 626204890 601194055 357906444 231892255 877777321 383740929 640384956 909383569 161490256 540364556 198732723 763787570 467914065 939536913 349623594 608469360 227389700 365263081 113817366 668007726 954306138 615368764 14534368 258948990 353789302 547541943 569991800 75100174 74180332 1286436 732233732 216514539 122542149 922042542 526989836 895596618 579460097 147494328 741025252 153724605 19570666 152147243 278651296 777964606 16168231 156502089 456104020 371111191 766238021 495949660 41884807 376276805 892388061 133312351 548201208 705818998 793195130 799536175 792275718 24859151 195906533 301631052 97162169 916985857 438630921 551490868 367581218 774545348 530757494 941598861 438023856 85967648 394727277 604342150 728331581 205055739 453513710 785443961 374657612 448415074 992014589 873628856 527450025 833037131 409149118 119550304 30227508 227569458 884467071 356240957 157339657 855228936 724661175 589282 107089758 852206870 117900372 571612864 48530342 753138975 531099179 34826293 648411170 514492506 99347292 573599628 434839607 462407302 83673062 277304599 411843175 301409716 672135311 814171951 22164967 11912632 292588625 592430517 245494921 510013132 976436119 684783431 790243738 587614712 556133803 91978471 486898029 382461527 405290590 693779618 665303357 599132942 76518605 852956523 979900108 921988085 759214684 566325286 581541492 769761741 944074653 453492129 215710672 289829940 471851956 551677893 363426746 462789726 714117220 29480298 992586379 746285151 510017571 51042392 461963894 73765747 475807282 456848918 5709995 124083622 266796911 109811435 912318466 303201676 79341042 483488457 705338323 511446415 650324805 110196177 936226319 543045058 152773250 417037779 560289617 71784018 735647753 761390664 630799147 861965231 917916527 48016082 138379252 808260435 599046964 571948584 396009088 465881735 141904955 82692287 973288350 467321023 709698254 567341312 270999876 675062417 617918612 127178186 737526531 332779227 973034595 704449454 604610661 946228664 941711585 185092477 85901855 81922904 341212995 985452669 109105413 576603525 529212605 391948133 139909176 751889339 210324819 964111743 61931180 140735237 957616106 411426118 734383658 197603891 911839547 636923209 355355140 301798867 124650296 639425750 820393856 514507246 199598825 287978355 771538988 542472502 60221371 114241363 204190717 154495907 304962920 615797892 784437723 435663300 66808602 865693274 298109465 39391576 422216328 696816780 964256141 134323297 4796385 155930950 594389082 596337102 331475959 543845789 725757285 95557229 860046688 885219031 109530795 490569280 808151321 912651613 252930942 140187975 142696838 359484339 981769756 487412385 82803162 103323672 394151722 313902431 538303979 719332014 627693529 998429611 962216191 415643421 747634828 571718793 35900467 729205834 73261803 802976484 838512034 84047018 326953572 845498772 191530577 769382558 13596913 683011981 875233224 574775590 871880118 408202939 249505380 548825910 467767277 619954644 134513305 50777194 654253471 714776229 13521257 411461589 537566177 411017104 657041370 326354488 159607150 103256719 61851229 944482427 864498806 550038612 729318390 610485426 899156257 69749232 542232734 532429311 768034700 982467624 124556557 418459446 38948191 767200643 642352085 404160898 34398997 263803308 128911920 397579967 97841324 32599216 79655099 673898584 177708782 394707869 278151894 974449780 660122210 566424840 900240501 319790386 358410833 119223590 188617673 411350333 815170232 767888205 313304737 82795509 122183348 127103654 70824363 432090275 144519543 135937638 928748299 206993022 8195808 307974842 697563418 835120547 65383478 974427832 498263596 277501513 426409479 511166708 244256550 24064558 726083864 289403188 741882033 521257343 186350882 761078220 822003780 448191081 167826463 13318324 295733952 916333878 11216681 126136981 210841850 63917172 307048076 946771363 679940512 792661269 62363867 177476127 133947647 133697776 790609664 295282053 763718326 304130157 504452033 59863469 102959881 367862257 55516880 64282556 5606023 524109865 884047902 546697093 402983379 571189987 738192613 790201166 872107108 928256575 887027411 231180975 453691174 266092693 158921391 315123441 584982579 622052481 885637765 704742192 229690933 32875397 633483294 877267273 401298781 529943881 945085630 58091970 832620755 853568627 737135223 198516612 426577287 977010695 751747675 769840196 908162769 325362548 667940746 976056925 754120814 60019498 577855637 891601097 791710285 466066377 304720824 487352645 433258051 798483021 271785616 996092715 695215834 826960483 210657591 469064875 953847760 353860659 953860464 567376787 74249623 18376626 411269786 608900450 823246967 867598520 314345704 398458702 41376362 420776278 323237969 674384914 761522504 53655449 429939953 511279688 995627763 323218511 347354308 916263782 833113209 540308417 402688197 52517054 624288011 596463407 306800447 286859476 146408811 824093856 68876414 112187559 45645241 507886702 951770530 594572979 746631756 892956865 310288013 713301347 994983247 21234912 205842354 789250133 67964653 406563117 606304437 348750838 972444797 529132703 196518866 855693548 90944118 75374912 603756026 467280101 228943622 712226371 107730791 95651688 93114032 37897511 81269637 685129917 964161577 899491218 256987818 604626203 59959411 567973428 364576675 669315028 658315804 477951678 344995560 927491792 918221412 522745914 227938493 644387375 458562998 896965144 750935040 203807055 148739614 195710584 510304925 438150129 267775734 528504067 368451849 20349967 571978690 109022052 323038845 268170071 359170016 141394036 731106173 947488318 637879893 401957599 510774703 98279456 160854221 587942546 978093969 985486039 315449934 777383136 980820176 560206854 828269924 743596008 410747757 70588566 971038812 521062925 859229781 394870033 649137173 624501623 39156644 414176429 68725470 515733976 696918534 733973394 744747784 441294166 215492996 133338124 981368019 970848145 256984881 348242622 813771651 529752386 81134234 118421834 184363619 573403684 436576093 375735024 376609382 832537337 244540879 862319836 435311821 956457059 51654590 13757445 440611080 619768476 946049954 85616262 931433716 598145023 445411726 699847212 564140659 371737502 762250185 398888134 461883976 878067568 966954964 603306293 144047089 785337848 738700068 729062763 963634800 281379698 389576786 86869440 311738470 321328382 792210910 83114742 838060016 722410011 819981580 820814033 779466075 836059019 658413206 114987092 438713294 935933879 715951850 651852003 362514268 159157509 136075020 528717435 659560531 70725544 564217920 670263129 206158713 18349974 110813269 8746837 979184657 989326432 790930744 42201250 399767012 200800993 165463108 740095063 552423611 11807290 669589278 765646838 297355214 247596901 330768993 546770109 275658222 658472347 754464810 192087907 753514702 610513349 220974471 918691628 42753060 291124516 754954318 976797922 323155511 288513308 25075824 542562350 629834482 681226105 131807772 30545719 719247950 7808459 33229718 939083978 327079637 462284511 19924725 14870984 266981739 68731984 625214774 347205041 762038382 134082407 251125449 860038182 96763758 101816630 835100592 375494724 632854576 693317013 332752063 516489247 505856349 39882364 287977078 750076449 598832225 110313858 766607239 613450714 990122723 141808052 808548635 793352001 141099778 642005752 232814530 991562648 720307410 841304925 779525821 840210041 350658187 817004735 388125421 316098002 577538708 66964110 184348936 681131572 335970219 916945964 768149270 760561967 735274197 925485913 210646342 72981510 973016483 193019648 26395091 240646349 624442114 38988881 96572404 387718668 922251272 887631299 643308356 650843488 237766770 826503164 907410324 209416246 80615930 435694603 592918123 850754375 682642093 307997971 879271099 867347658 186053942 65374934 37850246 493908204 90872167 220599524 852386918 996483461 820032915 536117731 836788946 834372991 238628021 269163192 18169134 11897614 833159677 114274671 202471782 329126420 502828040 682700529 142648176 896127174 906580201 496945936 606426363 250477473 706923785 388502485 3940287 238350902 699570031 993505464 160961217 238740671 14988095 442287738 882072071 698643828 459197172 818109327 418628920 739814062 124607098 474923455 989259127 452714187 25741360 783786245 223690789 120186598 341507600 287406541 750995678 222949921 553320004 45098912 708648365 308747487 798506051 865872248 365663258 397141264 374032366 677323787 117542203 432790931 183026700 726126168 645901447 135767338 213999846 453264769 896459868 55717318 138076728 373211930 566136395 701817749 116196244 847620979 706746696 352629887 388606861 817725494 764503699 411970864 299995092 518869860 862113394 260608421 119537286 604412560 764228804 293799315 820165946 978991170 677852648 268690795 875548765 583105883 85656092 246351457 80449577 348809870 610090552 704959880 386384433 765578675 506244742 918131152 360251163 777857420 362176776 136401828 933433619 643754970 360128976 871744158 63585444 819641452 753755100 148893819 432928950 355228386 111906614 411748498 64678446 216878312 587002597 5735233 548258688 878906780 39205519 797145045 259259454 129306809 6071293 108473236 689022921 176391817 882797231 1506066 335609270 292927062 985573882 791827235 77139958 204113090 997302565 554328314 811895906 423382298 172943169 903428764 10814030 801232565 593236459 551555164 448204090 386468726 389312548 586283599 13459151 515129694 71147773 218169782 817902417 236059844 848463871 633825589 980746975 122896225 785052002 22432218 1611473 752679650 608179914 450616650 486680422 665602903 545656692 96832948 471714382 741460391 670149768 802889102 162861338 316324682 92382174 36504831 503838416 277199363 790625370 204747726 926211582 876568412 540443836 176686614 749504538 576658636 307979535 776438669 494053905 37680158 930206482 92354586 365811893 102271131 322437820 111182553 127357153 243436184 475580147 141379689 51502635 961838476 509838357 186476341 722183986 961641630 348931282 857683458 968601714 8441063 135008333 342304693 799246710 429226179 606803374 144450409 121486147 353686104 167598226 472306359 746378173 718933256 13713695 705304830 96013211 372275083 207439464 862074139 600849636 11707252 135734259 96514602 770745523 298629551 397563812 33345661 740254332 81774047 779835621 604567700 224183137 952628493 129455238 939191005 771377357 973423932 805585472 738100410 33523923 795841541 180609265 898485416 532342780 668213252 468119395 95550929 754162588 555093694 583714262 573263710 24495300 961587226 582046901 467214794 71791098 293114822 846288908 793465869 54879254 523594118 805822661 75063570 20503395 796138017 514009034 770589398 615098901 128419290 707882145 108768407 354994624 478035974 407253363 469850724 276710021 8705317 281358017 25184219 216873468 712610911 335265052 950106077 537398819 893198492 869324286 47502386 656151659 405367240 982036168 315526506 916845093 220294020 12748484 308367660 857204603 717441739 715591240 33530674 702284176 512983892 366391911 113215422 934048084 440671412 840789822 505102866 53974043 696603439 526117601 268328502 874436186 418364875 389955619 656959661 307576394 236277401 209977076 562046083 320915600 297034777 156979536 245126230 755874436 261351972 938518483 412739760 544949704 99387514 249610782 965812255 370643884 709165282 199615496 361146430 792224360 309168892 84103876 489587400 485563337 218108131 781734060 299377268 79541549 119968803 621489260 9517006 38513158 691030531 351533313 285840466 992755495 441134116 820499940 942955965 624550667 70460574 405834424 451084490 759732714 37425977 391627218 834236643 94510832 453121485 428747905 951365422 228373764 724557553 406497975 658946490 133451623 741462065 698284686 72569941 59753732 844567278 922801517 191159357 972738959 30662496 95961833 656248684 888582768 809283732 617730467 52971043 664546546 118817416 390459352 533265604 145730691 957327829 654300451 356885442 251780817 137389923 360477108 280347741 18323241 661511738 297901819 844452548 787512985 789005628 106052765 17377539 6505175 958277069 428307955 206598135 961264587 247399100 301294880 889570306 226965722 681915776 985690034 596510252 887102940 353113231 276739950 511722020 987450746 124025778 87591381 122025466 828085949 946495477 131070382 167628802 631692122 837810527 824215682 323427418 356465541 429934229 769581489 855041514 869626915 838820695 976745151 583716961 618625803 68497666 774978020 360224857 335732478 9178849 236032909 395767326 697555095 488214464 678443033 601356902 740370904 686494582 277766115 933113068 551221607 137078885 782333805 434851826 667772035 495036217 722033835 940042489 49883416 664912154 466635062 125191384 705083669 319422509 617953035 705725547 577069242 766583636 216755093 663544511 102979278 693867636 997138236 87418105 943216537 709016977 61558430 672881997 271800249 242029546 249513976 338793813 128450088 432525553 17785948 221162875 583208940 877272866 849805401 558600182 742221031 569324366 594955171 520660337 535384206 245852506 284514708 540082328 543272599 829571190 932115778 969637753 595784429 425614014 26688335 874230963 909644139 452944374 954032044 96616778 926491064 924350023 654117357 781613300 417247595 146204904 337491132 502105569 70527245 87900412 459415698 988887093 642389690 36188133 62019580 271968968 137227554 779024972 12375486 274819793 451898026 547930384 449047324 673800682 679753515 797286337 840975520 331161858 707201223 401930588 411305895 861279344 482137022 614090395 3823055 622537747 451568839 310251769 311169861 709156576 260315176 692957287 729288122 456276219 763271068 376999539 947455095 79500932 230297462 636873712 670942708 890424731 702384815 56939918 4457036 894943248 128667320 788576483 483347338 481034937 625722045 75952728 725174950 838649697 43243990 390723947 39851544 355942494 229017888 812931386 646825482 633638054 183351299 93715689 412528475 288850003 34436326 98213233 47844260 959577036 9038276 582432636 507811998 489198980 45334269 723831239 729735390 383574907 145020496 551477277 932135859 514160542 22017060 673523330 520287167 60472026 32032654 501887222 695736510 195048849 125943015 98338935 367539196 861260172 952891796 112337818 423564607 89526885 878259998 260663749 901951335 9006366 46121266 711482867 703582367 63864981 429873939 756287459 115083661 914264830 803486719 824097091 477752128 931620935 449767462 99279588 144708638 605047165 692616804 449241282 638685494 263813146 146775539 545240411 335827700 462091356 861514512 932616882 801758093 835850967 102145467 919413110 431282799 605655940 979858572 578397602 262988617 528323587 837113205 989226710 907881668 895865335 800819422 91992999 731070125 341629582 190074368 271703081 756410617 683011451 73346936 879301746 589453209 390981824 724517920 740386144 149654684 335885123 279716070 346268401 52315431 944620388 35725686 732123792 870741675 247239192 115709840 701037048 234361488 221481990 651607451 192791029 833467921 852480638 778656923 914521815 827666320 336241815 979671220 370034763 854581801 585681465 630811248 710841669 664385816 564911953 242952456 728476817 498553544 501185186 988540762 471076936 410818635 468856534 954249289 659907621 461816233 532489545 780387538 83680709 405827728 131523396 546005581 311138008 966781783 840136873 475428680 890641114 837145180 379146888 737749161 927037990 526600717 591103104 203479678 881943894 691856636 203494519 338398003 711500937 800263435 130432656 393807577 179329779 76022106 743727349 470712297 724781903 882181131 591153023 249489733 78825359 406338864 132251560 899356047 487157537 94540120 945364901 309348726 166111689 110399117 52071605 141604100 321189596 252613186 94630177 311469253 91565557 344008441 516851935 952081202 728091411 670507265 368890240 945936563 534358794 191622198 516278127 45508381 941121485 4700012 122147095 724820905 537687745 99705411 504559789 516413492 380125711 801936724 543134890 662579674 66832995 714139934 56729427 761702093 777040478 871239533 379309079 109188229 613986968 620030535 262529695 50651052 888689946 463140731 525512383 479342742 102288091 961989609 547941972 850828262 924460902 163155641 613202840 326093121 268800697 575188032 6836802 89481117 463542291 477575293 461543806 248776250 824734813 458527547 94118765 744575866 699351987 830828672 798800704 523137925 374016429 202449206 742670166 675485370 77017320 83398449 163872624 133139308 787351154 216595658 338425535 381252683 415602305 411103285 750980368 758613329 196770036 782140444 687022215 910264427 933685133 783004896 183481450 133679899 76108081 834204105 695128313 503478683 673617773 753085599 988513816 811174092 969734860 873356709 248442690 661042834 6966879 566675118 18716975 43569557 774582644 364612788 276266219 139659691 853762238 843671653 547912602 357206672 355726133 887605855 570176117 670927277 631075914 71137259 602987475 228123904 613106405 645772301 905672741 277651245 2492978 97275147 461302034 480281540 493775479 7646739 462685325 313954682 269002889 678461682 914790645 843903414 148152435 64411366 23032046 345502434 856588522 100386607 861497657 856356319 345234433 1768078 237256238 481421359 677865658 280328443 693981755 767652622 3333619 779500061 52756652 917770794 391660129 594393242 20759291 447509726 808216282 856967493 27301263 876767133 939885458 558147046 568815220 627672937 652339867 765088506 503403878 770875207 123723470 449151766 281673729 829367087 649240304 417362115 923458897 709348204 333523325 387166377 22809601 901836613 21335937 756285882 88579022 127395733 684828822 198625206 104232998 290303206 43120452 23430919 606910004 582075750 159101359 192361970 857702827 146652850 630690035 821098425 471296547 161358487 473206620 51700693 143115635 748733155 496926437 278706670 561151777 677205256 918370264 84039253 196447217 5993874 600270681 18628802 147603102 214684801 227885219 896494904 437545948 643702480 477929546 973023036 510177341 795834557 856207755 788781510 634268833 47435717 535645776 347092202 13036956 861749270 790248716 671279958 116134540 958045498 831261452 630083223 359827376 97720252 352247181 753423129 11908163 10456720 238374336 93425269 973890476 849834470 254184287 730320920 634643029 687075526 658778757 816351808 944778145 392180291 746821388 932618242 824615613 602616794 440539278 412992262 493783524 142859054 938365004 128185501 73557716 919892490 898287871 714192681 150269678 934671046 173375511 934371239 222465134 202460905 146316681 68643524 285951201 706394993 91029929 724621811 131977112 581675805 879676685 448602041 632380242 518141485 357733004 611853469 62513419 129470100 41492992 587998110 557453048 789692716 709501124 401661049 176131216 797843518 261076930 403833461 973616279 536372785 828514230 347658234 581897123 304401017 761828759 758432293 656086700 313601327 772616345 676763847 89543789 162365526 218641917 370162196 55886007 825749104 325847208 223686778 52773721 57165830 860897795 511893920 374585330 26550078 698029211 866747488 43436409 684247855 378752494 551620144 392839303 85417837 891472035 770048898 475355058 446254738 983448014 422102111 131676730 975606472 773291831 937733745 108550076 187494223 649857584 847547418 470406969 242606570 210138109 328065489 999113546 719693501 53733175 588797188 309676534 380613451 409448316 60225218 533402961 99784721 483017890 386453342 923732238 801401675 933479513 622116850 612982479 917453088 701447750 694579061 862134907 829198834 323400849 909920358 800389813 314005477 122714454 670489030 855393173 130487365 106280318 132850672 231213196 202250943 557947572 511222996 835783897 329405046