1000 11 229411154 684831466 935936169 485160344 800689837 202232748 528239652 206180156 244681596 396343266 196920687 289462801 358670473 333402313 412672089 659462925 812328603 346730308 138630190 575436361 549591001 395298696 273500945 372425633 242508494 317436713 98239002 443858501 152547557 582973763 968466358 135102738 91194374 265778329 118409935 539250134 353277944 972123126 944185587 440069752 576459850 465055337 227009872 401111095 921914634 657968967 444900662 744745091 667282693 570155012 473051592 330677537 5098797 278720356 51025097 609185890 548702660 24011465 80910704 625024212 839873885 458442906 831906912 626776247 631830380 587247258 29893197 459952286 586858847 532786930 747226834 936166250 57015603 286371611 20759893 447626814 5346494 448339703 2010847 674847248 211443007 672447013 561513172 42304460 14838196 169927842 268989974 399996657 785468366 82591594 409436222 215523556 865221210 737185853 493538249 257165318 525963941 541333165 400698560 520695724 881219335 325093737 278689540 960464247 263537714 93164259 939052491 374048870 142396649 569471941 6347216 165101638 690480282 953370953 116120539 273622000 533602636 539958945 259829080 691457151 326237581 684939823 740058402 137745553 896646929 744068075 226802733 203120505 881866837 786341654 780690092 188793434 101091382 399608210 742954519 346870747 81839227 659528091 205949101 178874924 875653524 436101729 285495652 984655649 298078767 848076326 319649203 478352869 986868757 238635428 314516083 774361171 294116021 969039800 947413618 385239068 223826731 312058624 849499368 180649091 294577216 725053867 176099652 578003887 26181002 837091457 403656746 261370888 644471045 140945274 106910584 132322437 387632152 164226554 665345638 650263332 861820468 178405989 28908774 976919977 57552687 652176031 748921307 40855713 217817066 861500384 507030390 508766589 15728184 416242079 509422156 714177625 571865460 462341005 949688387 283098139 551861804 211991257 766005333 560189610 659859705 672140300 747676278 355992785 15322219 503034011 172727947 611171068 949837137 690068611 435288605 964488154 290220375 651256701 465265156 110784456 307785815 554244705 50203898 704880004 895868445 313291650 859359685 886317832 667936462 684037667 69995026 24357516 473370726 342500835 247027992 214818093 163271253 675066898 756892952 707361737 50018717 128730549 869333303 660490337 745815821 411035887 346633731 224923673 624405683 638607803 443109135 816626513 773815479 576394312 809784907 763000753 562167235 806306966 341938786 555780434 413848161 33274593 642711724 205508797 83072194 595907929 885151565 395314906 255014757 195324109 990474214 232114619 278597186 518856740 601702981 223397701 401873739 545298438 273799001 796447400 688704605 321193863 636002741 568756789 679238022 115366142 161765735 345293003 585198868 265040534 119946222 147303546 182461443 67570626 536699443 443380153 114014864 800750979 651917533 442181007 487476225 528999332 69747826 28378508 499939852 837422640 339284063 905918489 947376722 689354438 325856147 457084230 287421527 416390398 98704597 834547245 241644628 375095849 81659885 595918217 694222939 498561447 816102189 503399502 686516148 810172790 407655726 746391102 324454633 156307443 316213210 378921249 815873791 457128523 781099050 119732338 912559004 817887812 185272900 97423726 361348115 744218531 854010842 112816578 434735990 608335660 665897544 106518152 510553804 494765802 602574057 828555818 777828350 137354367 468630983 198628280 859725405 292599644 693045798 447299150 237466492 905892607 837929746 662332629 322528553 718834187 162107482 164244064 331525855 949634039 771926273 823850255 734001024 570445583 806119987 6981547 656686624 790997284 243388954 681776555 2751762 49306934 53414128 556200286 762142456 397650391 960604192 616719944 660200801 67655317 258476185 610064273 785251027 889332830 17668132 486361214 344095276 338773176 713024253 685820917 701049286 935210579 873817032 709560281 681287470 944922372 968113985 537584731 92664375 114568013 263079847 505192913 303550477 342394964 730686509 142335768 487672538 823955766 190076504 974609521 911065011 543836172 107265264 365047776 129672604 105461499 979422919 600681521 852076068 818742749 671054489 84853139 827906634 56321355 70905865 235417276 941476675 698905661 430989010 866256537 45879010 779513788 740369814 496547800 584091317 142459529 158499175 279984178 432018272 530761547 818146771 636377624 207647179 828480904 865576962 362649351 565894267 800096477 710633927 84379752 36133450 875983265 768235974 475140343 928394350 993702391 606997940 303230141 205553828 638339945 649809296 713824312 322064225 45499319 824565599 358750637 176641762 477158189 146721289 595894136 365276701 418097234 395851727 706748763 479466517 143250653 987988987 466564047 488404781 478062351 414798719 181691458 202255939 757798842 963166177 299436377 857725045 202649371 342200570 701648455 98405860 306662549 89966135 287893478 799096401 370369930 20680444 714198369 728756407 283935039 720884484 522233406 558144087 417822712 985104873 363364626 239064743 283809201 515805025 21525412 378336401 877693139 260006066 468711719 469705883 97602596 961653418 504235970 182987701 891177547 992263024 886396205 556268452 443525911 464438136 977276568 103710276 134935584 427064203 772301426 620368102 66202978 270360999 951111508 531907623 991034345 638194367 538169855 66834029 484095393 114374152 113085868 229780454 14193123 115658784 573990882 235255780 510571230 274703346 66174192 461891135 390995657 576677625 727314336 112039615 985739964 513800299 690516683 168883220 614176305 849564807 126984937 799732798 893138912 465127893 542757043 97833171 789134446 374911865 472667615 713520963 76580203 671014197 199015750 858023101 108119749 640121375 962275458 999258654 852516577 238439547 515917810 16736208 939780474 691066008 152671174 833512275 942676627 292587086 881881662 892027206 939171747 578900188 867859442 399918809 33175793 88818944 842790018 329929814 325007884 320617980 359171995 865291779 901046989 203451268 311384945 541182989 68985457 363816876 982988475 777037988 919059780 74698759 53201886 533708943 863422212 640524765 476511837 191168804 538626541 967191215 751134275 342780513 819859652 192898468 904809525 813314150 598566848 722805069 235728974 9225666 489529887 580201279 645068600 589890321 830317299 345675929 491878847 442716351 206148303 366845802 380259685 398259615 175008229 105611017 938918731 546162451 249380873 580616490 501554487 23199294 864881118 290116965 205146423 377696162 330990133 426884118 572058956 173780993 326371974 649332052 75228615 194913182 106673724 464724683 218440554 334544431 121706784 57550439 910109553 359018987 465719544 234010498 614405123 803526994 182935661 457534264 741942700 827654757 7038032 844223571 925532134 558605414 461911587 641682058 421158893 864108177 48014567 356239082 1886131 198214528 453126702 975376832 505174358 597458103 988958599 653451355 626704846 674382559 280758251 299531067 618210247 454315214 40285967 902281897 696547554 451342034 620466972 902666491 507531189 306499020 415321445 287884919 552469695 181307153 664916855 244547427 216895619 575221877 239068696 861058446 799308483 346159711 112539012 915514784 201734394 449536474 736437698 181812614 29052867 52624328 697246599 597361152 86159041 148644925 564820089 535701245 559365346 38967056 774579131 885159745 499193879 269033443 250533561 689554635 510718890 613332270 624281762 762516763 867976628 15404906 535569991 85803689 196947582 829456119 492065675 275905667 977099088 86682295 876623290 182974908 520624860 381802499 147761168 49829904 165375207 731240075 791066888 664457316 145594765 914359298 932313579 163301980 115991648 180098874 359854960 431520936 282705838 141834519 996042778 806572844 715714472 209547304 323718582 122673339 27316470 127107487 268794282 308961325 741023223 985894900 263104678 296300505 197343806 546456289 837688624 313258488 818471679 332183315 1027402 577594082 15229922 43494109 441871713 289706920 930496611 530068327 148045059 426213128 845613753 906707575 678355550 270735162 595915345 315662164 526990486 509381125 557331714 537626384 826197206 521018715 598630892 562260771 521706913 962051812 113584123 574899419 829725836 752160693 348684689 839600032 810901383 998653043 683661944 880504130 823732892 400637044 514273131 837109424 779228066 803164707 767651111 291270876 287868209 451259401 549500500 865496054 144690830 134304041 34848887 914444908 154432343 225185507 520092014 523448064 962460786 339801053 499643424 282662818 23918298 684674447 373073026 794827949 559032266 110007137 159231158 414777498 839779693 553889905 341607264 581114364 246221696 396188252 775206208 414683486 81240488 95336397 261043900 250571391 82778793 287610216 357657380 431021311 4161200 700437844 532865895 445207453 109266926 821835228 733691156 285921773 192866277 696526559 954539265 326266588 734272527 918173526 883470363 292791944 997950133 59392140 945373223 979170043 581535106 899844206 489945983 401733297 693165762 889006101 417383366 828543942 42352284 231044607 900979727 167625576 905942090 58057989 757118935 188321609 391535041 249491442 76109716 33909739 451674649 442679961 752713256 843672445 119086986 651861336 811117793 79115919 104643037 844408099 907154951 941440144 482876202 713792425 364721202 36974983 602005214 676564827 161405092 605247072 235249973 869531533 5918630 474782113 700063547 697676192 480450578 284518804 261106146 352041485 9251757 249704218 808155818 503499731 295707517 180100307 57718554 731049535 861575218 911969265 778246616 747126093 473158807 771035816 368270715 277083193 249141653 619193919 738825550 672001861 397388852 798848696 100364024 938164032 84219285 674393504 773237360 433317203 965741054 210204825 350408356 725334740 603710226 141924628 150181049 6535204 156618488 586836478 627700851 464443960 687892249 570586601 438342464 557806720 900961606 576792984 568001136 501879312 806394678 598374528 883323135 133172225 289188944 656766482 458208024 990095903 443989414 268349034 336087294 59035019 304438566 46077693 826688661 963924512 708295148 391613312 820400113 148502149 69111302 499292393 870627149 986566907 233298797 687352180 386494887 857942304 303674959 504994079 824744837 396208416 732594952 731814685 459007486 811036211 837000506 176855850 234738943 905314520 404507546 428068587 94525981 94089504 361492601 237057355 627491056 57469124 475549389 379386651 994818743 22633753 976121274 830139848 80769790 730141448 271241298 317146592 585003921 406952391 682648821 796277362 729376961 707996397 15224808 713574791 937241163 924194808 533059635 263928356 261944657 347885081 821704447 127788306 531273282 417049133 271973927 679329380 301797969 99061517 158864902 805353935 583500742 742851857 343745963 206865567 738630889 602323020 208512595 853040206 2719043 5064987 268800599 182211607 778125404 242695108 972615975 673056245 112570511 615119785 666089169 408487156 755655201 431108277 861699702 723225304 330309892 570797156 943716228 458881219 899696366 18141667 196908438 921742747 688600935 158553088 868935415 42624392 662623357 730466481 811103063 815734871 448357503 407547006 607196523 578262852 885889789 287030523 522568912 966667653 918720581 674053513 756762565 219652075 243826492 371737645 514577483 43396629 988770948 389433982 941940410 955669205 448619731 219847641 599178537 554931389 882466447 878809796 290444148 912426100 801664910 486145946 612777223 762904127 673981785 921599627 501065739 437558736 617026979 902836936 332837103 881193940 505205974 928627342 239298223 914954659 178850469 309894071 695348525 47917574 676602232 899158970 226174573 398529326 741726055 626569052 953187524 330767543 996393247 489193915 106057354 770180531 207134392 835018440 550364023 450138523 878566070 647888100 353620970 832842446 849084902 823876187 113311846 532222268 842941430 843661237 130889439 678319170 798842353 377171668 738486652 792022562 568744777 392207166 418195272 67225355 423165973 917272090 737102092 938544378 905838025 977649393 89032084 657009844 975369736 682614921 738019642 86415267 462037838 755107664 643675323 623739556 92315763 712034949 435980604 127472035 401693966 270307104 382111915 898731413 581537828 842979719 755366428 548430761 63540586 599133268 776094658 546662212 542011286 859040968 661854117 606152952 912641902 143901535 328727592 49734863 637061007 205110973 90920487 443586656 85079163 892595879 34537450 891705342 484045788 565355382 814345285 534038657 394219607 854030080 202920251 501127263 37904658 162701438 746223656 562607339 472949592 434759774 586092695 335264228 628003966 675451062 427609888 5449238 806031431 381999728 402221166 246673389 252724270 300076090 260122918 759240715 885487473 101975184 315802614 33990249 804620265 623637031 251525313 366586380 945864958 650398293 11063146 367457499 935321539 89528460 844176793 766321898 290805936 489238701 420162345 188657504 684012908 674995295 727995818 648879472 156951550 394540401 489648018 948415204 659522907 500690592 285865699 707804648 556039863 440508676 471375029 987940222 377958516 667743414 495490855 388623401 842749566 24498106 841534999 597141381 933916846 17051098 130062962 194436224 201201960 487754545 975957525 840043785 766417723 367490034 348354392 506656625 726187638 353315728 844616466 613144617 606519003 433519948 305836585 327572976 607969030 430884093 808512017 733620933 312949441 448997060 46605319 755969236 454709308 97226465 818237782 984610835 411386206 180324245 528366787 207104895 918667805 324405628 268352510 201784072 621168404 418237594 794387028 513734071 423784018 826003850 71800298 443137454 486527018 149854446 776167135 462042285 366688654 268152441 147295186 74722721 542277206 202680464 473735876 119777038 772328685 689906124 225121923 825032654 442534775 773117502 198556465 818140499 855502823 514156699 526964339 447907662 511983349 713652001 608319062 23928302 551737081 838423643 215166222 688382680 257183383 16327059 583148928 366091287 659323060 913804007 484669367 652450957 662788402 381914212 194520415 906423263 851029076 626032494 459081927 543129427 994376058 358165490 563822486 146394236 926818888 99767501 605974626 406611268 395789274 234559171 843286291 114639297 151618611 428136744 811232985 720740014 239818831 667392364 292912493 666166233 45879161 134606694 412262750 358606654 787351063 250608447 196356550 824259439 333895686 549771086 723219060 211093792 992267250 102256116 467489775 925441578 97454866 371009907 184412782 264227237 185667569 946911714 729147386 940995129 973232647 678037990 85650749 118869090 738736101 226285404 404194375 299687005 52180270 154918238 70332582 978756030 172551693 854659580 50082077 726168927 164147786 668451160 15121134 260697718 376357633 683357296 3660790 450681694 2934620 870343044 357755526 161615075 369951979 981985903 309852583 310287733 221664735 397389094 696938985 969736731 294048666 582488206 29333580 342062467 591548572 509819996 922357443 851193090 804512817 130944252 481247239 353072159 114003635 134546010 735170312 371390650 907523048 293667657 314221309 139475470 402956196 741746169 935321875 848777224 974042550 127175735 286800357 482489619 481655507 886120116 683290017 743403623 239713882 2484618 560035008 332917547 678725728 269537304 311807357 425101830 714270021 526590232 301723785 469175486 994521864 644887850 419845025 644333799 327149825 423229274 144323826 847154565 296091652 351172104 826884367 694456843 587923753 444840468 315005549 97578259 787551573 236022255 231709667 352938372 226312868 448485817 254689436 834561343 688209318 247904449 262505653 330535443 193224981 702565123 496106422 97650101 731359388 698088321 385932703 697115335 928553887 588255398 619288236 15918344 858973871 898648248 660643160 680089016 895749107 588013013 356503010 412581136 705445849 416518943 24434224 578528290 39822076 709853932 855120512 556073769 634648818 165772709 811102572 530770816 687486118 728613516 260987762 329050232 481915603 884107454 235163632 514006155 83219625 5700465 794016928 502997441 453397934 800691281 453723353 744660735 895585456 101428096 171165673 841484390 921427238 918265373 819570282 313657019 876314126 350839349 11317927 166171396 696846948 453945215 714287328 487570137 670761622 91452913 70576308 436951508 373283191 804775260 251557491 543842557 771330265 880614728 819351476 128937334 457401228 876584628 747673047 4871155 286572078 265154888 145783567 264854516 899762531 85025214 784631008 787235459 108353358 869115650 390203852 479485228 829685660 502134953 713449233 885008943 262366154 490588405 506750275 191777146 4080805 715814149 355412216 573228388 778147898 630404516 545216581 454243899 825022916 877104056 48926326 137300840 251551161 446865590 737065781 665153850 916398230 561947762 723252001 341502555 959960828 99364610 969034844 634035079 315774749 977105443 828158687 818909490 775550121 538662262 49541422 976185912 510079232 961494385 592086305 938900877 508273508 243228519 788714605 565147981 136619071 385329631 388553710 401609606 163027165 852180786 894326784 18105595 436163902 907140464 184706890 144755686 98683047 105012393 573415490 988508210 36142256 473714561 783966385 522593865 174128351 95423829 142286425 657110792 755852436 144572644 590964266 386152255 358139986 134046830 315959786 730627276 672004009 956591624 858557843 904709157 801649624 664794208 9505209 274654834 354083755 517430601 318818523 322260046 344776913 623898781 718056453 892335211 535016034 751732200 354005306 149389004 762774492 43669946 446146153 500927862 645047493 579532676 128355121 809238016 602928034 505301049 145853146 928556781 510513392 328742065 845255000 207052090 741622121 481382123 269402684 437604003 85669418 743311285 428319076 292312235 252401212 155890716 828874178 634360685 629412333 544945611 741200100 11244434 925765140 452547372 246946525 369375990 965168860 54975236 23896075 567739467 671346972 907526429 848779242 391809781 270472851 817666519 283087102 442740667 897719980 144955398 172089778 883227069 62475658 185514064 170088988 214205934 121168968 344961710 340971966 66631458 200826247 67161792 38925654 756050875 20699288 182905513 272290832 752444588 373523822 915193210 146968647 215010189 401215593 822473512 888954463 906117066 950163065 506673103 709550976 938489448 133250025 28315390 840033833 629132231 815980889 494025331 682739633 668997607 494352679 350475416 405623442 700702545 646745687 903313527 317670146 369732234 108421122 953988279 817861930 965921995 612276731 504426558 730164694 6672919 399843641 693254044 475990311 701535221 535392149 409795405 132990543 20038062 219631433 301952634 378738686 725208075 859277180 657294790 696389697 513443287 988010290 785276964 410068329 541899766 534622947 903250725 988086050 695006378 808354316 239786299 868929333 904089469 140183745 608649397 888552380 921975350 151957559 764924355 588296219 568128876 707979856 766916330 449557448 747335133 40212326 450983508 70493612 776112871 202394106 867601560 24939117 647802175 730683460 966037000 329240391 984070151 315845900 948510176 300608039 860910568 696847286 502492296 728067895 784676372 111851088 98650782 706512639 140446088 327653832 447918770 314947096 980576801 760636067 154709330 557969020 931869283 850160648 748941177 147529357 115741553 742541843 800956637 7494435 688165029 514575368 760848183 211485034 435444706 628001445 406851251 357252490 417059573 736304333 612106710 978177526 110409827 132094395 206868427 437146142 160447852 773043524 208256072 279633338 933055185 892398620 56192176 238496225 920169454 29641853 948138043 832384853 653117644 292760004 986646407 388396676 671673450 806781732 269372929 518368494 181924459 202354359 896281809 505492527 366792873 853328341 728064270 395017822 255492636 402437839 605823273 405079251 148669180 272241110 424566955 565367637 995230788 350256369 968127368 593752169 276319223 566386959 191289730 660487835 715143326 600676845 461382111 273983584 150790611 975264588 406192391 504660554 26477056 615131685 150875677 471407612 780606518 208824752 494829309 540105435 780302093 581587351 77255694 227605954 7287510 740748526 764002134 791811685 423360102 328057732 969704088 671303587 330533083 673777622 320782084 247760622 808982587 89993059 188207210 483352157 588593357 841067125 278928970 67502611 37180774 416742195 906204269 534675250 369413262 671072878 790063912 982382066 822419424 281760828 681451549 916381434 626439701 503775713 183628967 811428186 405615958 808897147 512042405 649611350 889296310 267950615 521070252 813394955 485196893 937547673 383710980 757500079 864814278 654096769 933638137 721868710 114376183 220041977 383792300 978749335 954779738 440507306 423356692 590571828 247034870 904165083 804653973 346754486 412338886 801273966 761706412 151479334 596559952 767700675 325390627 931020407 189674843 901702770 138803766 393430117 103695082 224278642 618830661 789840834 303538451 294407207 739880475 414197688 150926404 32002314 2216462 368843808 324186284 187677243 850724421 713578921 562413154 152562897 218263505 151440049 136247064 605180782 7444146 100068538 497325902 853024471 52492451 454836489 203623361 596256472 555002777 39453659 44462651 39337729 229846013 829346435 13574115 223335144 533382887 123150505 126570051 418283185 59575787 499623370 368483008 468960098 715956646 694834830 861715993 1754217 770230252 836063912 182882006 85148868 730876601 85027633 343444317 829571418 190536940 3642764 630407497 205839219 299670808 8362079 2688858 234477374 826403427 651478629 198295000 266424685 242667549 101754895 421783310 647031401 692822539 53548818 357685464 605251895 996702082 385673657 624850326 888636927 112275908 176870488 418510918 522570142 610412246 466020738 976301434 520314414 729597276 586422058 748276028 630994553 525129142 426342885 930609029 520891795 61994891 336921637 546331551 565090492 217235269 298946118 72769674 651524394 921102989 393420614 913405940 969172709 457278484 381780225 479392048 452724895 143872932 1515606 318031376 400789595 519764640 170171292 7515853 570337901 510743085 302144356 534177077 596311633 727586859 891113776 198363240 171665263 770195309 460256514 994641727 908101237 113234227 189700837 854692620 342355546 219151302 859062513 292812077 625915409 452199459 631778324 216362618 573845730 840174523 864813189 670341265 412703891 393356636 354081396 573831421 669111108 597204494 801617364 739926605 86438488 892008803 61234586 800592299 813541886 780307661 943224407 930015646 779420987 316960679 994358438 685916862 957498989 593635794 738506532 302998642 635167883 162217344 364783475 589808659 225568823 497297302 956369239 925424611 106707463 509152673 905408441 554437335 674951997 673056015 159444126 401527054 326710808 396208801 50157022 486057208 779674034 845013042 640079529 993571087 773058610 45394954 970953616 355578657 198835464 546562514 648599470 220925297 396729314 902120016 335660824 726377018 505715842 566322385 448586606 399792525 532373670 469936190 850925739 435174134 4786594 709968647 128898677 25680312 944738570 382736583 547068533 584987672 397701825 240274778 50445302 855583672 491123537 633255009 789898497 458811867 59412030 959633071 440674328 867675749 156290808 614368211 884862626 639495145 237833895 25782803 573352806 974010983 956279302 476331216 427513152 709603845 24902940 142603343 234605440 1427378 106320587 802691507 511747864 612683213 800498877 640712985 819836519 741580824 901374587 589386101 866089468 921461714 548707507 110354963 736285706 79291691 853845680 507399889 115063768 25571417 977863964 445004889 954887842 524040634 723670358 839715721 689623562 580608081 434969782 970684391 413667797 44046726 464873622 423565277 97487676 200289433 43862577 182902500 528699310 139522242 246433728 535797113 718040029 945442310 240143666 161670705 722663445 775771342 235188734 272421527 660539961 740688116 999064153 149497216 656828970 104976268 227424303 35229959 80776507 310524147 60855718 101728164 927757810 372451112 651453264 198438065 886884138 811306056 538780843 686490790 317042040 678860851 443254956 20039645 91163604 511183398 201729462 42891052 320143420 734593761 277252146 26091538 96480174 477243043 673871572 472925366 681400643 391610796 142290648 568586621 551037820 540158625 229857401 193981333 489103523 113517254 471644086 93465504 22089322 364174121 252367171 767144140 730896145 470629786 197660537 555766250 974025171 731558859 945137197 526157417 408406552 85674456 116459732 764988091 609516904 365728699 268271106 664924963 678292966 536264892 149769229 613729061 225544714 414046926 868688392 419941255 933744896 890402496 847716230 133140395 163916053 352649735 47209859 760194842 203862336 835123152 413091414 651283577 948803416 332824967 851006427 913103259 813994569 757547120 297221089 709376942 196856165 591181331 316650157 473921378 714293781 791309611 910877740 478918828 23134468 587182932 444454753 456016852 395075792 325744849 833900139 516927417 855726962 184924481 726086156 821705901 585868175 898647303 105584168 306525878 360064600 570595123 279802740 119650621 409788922 753335488 780152528 972187226 618668370 979181396 892418706 937616014 337327018 800882758 175714783 542910006 785313595 494262983 194969418 496439906 637779935 13767281 920524625 691754783 621801488 701146066 841201269 62204123 571440635 866635221 747600126 108271569 584241567 809546254 537129648 762160587 844379968 210001518 109757882 6118622 168252158 620137343 183215331 37210461 388925126 381258949 761553691 649683001 562138697 50470250 469316343 330120982 542228846 893132006 797307556 819388225 391459090 461476361 264130995 121925156 958369013 568667793 783098195 319236787 844707694 679307048 776656828 504128979 41724431 444560517 830481475 691922805 729030946 416551655 766501655 652176218 926046022 237002857 97077599 284381626 403520021 71994718 935972675 823619464 127023810 499095164 525552587 772702439 306049096 899591049 995024729 977751496 13746802 476124600 919758212 760896148 428923574 611257503 616325966 810051661 889941085 937247171 409513977 519270653 884983572 359250315 663161947 65122043 220887574 965134278 125071991 408110315 605609745 451307638 757661559 783198618 103760787 925660820 393261584 773269369 625285849 122797331 124377983 923202021 937376306 767713202 467115036 586455780 530508136 510242707 158832276 427343348 481576326 985828944 323966462 754798811 14723370 981847499 570027692 817486895 297474202 557242031 610402268 431673223 898902517 769782728 356293090 699096884 755009558 905125526 812317420 367131946 109871835 784881786 821983513 632747708 230811728 17686777 855363536 280223855 580102331 720725221 85648455 652831781 212108960 739141802 113169671 392883290 761961453 678517531 767698909 873204465 123970611 706595798 903406372 891037389 579642054 109991984 410619863 907480705 787947184 464903984 528356985 17974438 891337537 972470128 669849887 319583290 807220566 92035306 498414457 368426843 732772503 632188601 40630516 537748661 52289886 617143207 193213187 565680372 670235518 496854070 426929808 230748451 65987120 758004610 411805970 280314407 712089588 698705685 667235653 284442195 222472932 142786571 640827618 938233624 506923025 522200451 966714617 788729611 950326462 135975615 110833249 770383438 886589166 683988617 124409005 892693786 27999578 98704766 269470347 621245398 648529524 879508679 680203001 978541015 444959480 81524242 160613719 645297647 943475643 434519834 444469493 668989264 446802984 761236228 809451268 867617776 193571080 760074213 457714864 773990469 536554151 70685920 616423048 935815575 158922392 397867968 11193125 376066813 703104491 711859708 56451259 222116386 953860952 116354645 317439622 213684226 655641196 229300878 728710370 482029946 537252644 842678942 339014929 485099915 103833126 432209446 949443539 395527686 644726200 472825761 380990511 868339490 143317050 1772141 951735022 245030829 356865043 840662287 21717942 465086860 816267440 746320526 847274138 671426631 451522118 657969064 295415108 462848132 470278079 988736490 184484782 323311660 463478354 650662072 860183557 179214440 967915252 179770002 465495050 874099951 544106865 793627395 861473118 971875410 695414910 271040701 27079246 539504692 771354515 307257987 659306680 983942124 760142780 379533319 67361063 216832273 792577183 747335299 371473711 159297697 74804976 485558470 88480503 826849423 709522494 571995709 952161854 861032339 448995606 501401948 842618518 85093408 823680568 861212551 234865520 334191493 250351708 698780825 673273401 672096978 549303066 530547062 526213619 871364971 801133597 878500812 107156963 721041678 641272311 442928927 463805464 65677483 593927842 479734087 134452549 581225827 213877968 146394116 993277824 472993678 313096700 399122170 231189357 85731516 643869985 387245995 399453853 958921231 849975737 380459904 700515935 154593250 317220838 911013903 800826794 72617770 302977544 703769223 595606341 365013233 905183248 288422043 693793713 930422849 839546477 306468829 608425615 150476717 967433784 656364417 218635433 66132121 167212685 137108753 576548493 444236889 415378252 406805680 289864078 661194272 784111960 993816094 162822844 516219834 740020011 209204984 376291073 376634137 952573983 140125968 671362577 312454338 862647285 983327959 88977192 706946720 759461443 603338581 195860362 706394549 198134970 823161024 209499394 87762248 163458557 895732661 250962623 925806621 10125057 569847102 253327673 292719601 672113526 44653390 217038227 590712334 24877215 530380382 617190677 356222901 416484658 55070140 903403387 265337113 185463348 176620711 37837940 279377646 941272857 584647420 620840522 22176248 269218218 622659127 437867183 342427061 291813140 109568860 81861075 392867648 775080280 804020197 806129836 995006863 612797790 647299563 730946425 972081640 884534518 460829733 173654192 448233233 795558695 247410740 717010305 441442589 693861431 930842126 859659556 184569782 982261073 343913531 187217199 420700134 106561676 620799491 915249931 118002979 251517204 483846912 206348776 696870302 60238777 271360679 422255738 425225049 699284462 93784354 593141519 506835310 98557814 57419162 111271436 330043766 565256230 189998738 965694368 266103854 147984003 610628643 409849851 987775565 513378112 346786750 655039248 664980227 100271296 54913691 5554005 465571523 766014298 115627987 576109061 954454149 34081579 735187585 848424 377616538 666412094 312633411 249505924 676153913 859920099 164080477 895649399 852605688 112103702 703452984 670069580 946801287 652154807 79421421 796724126 687448364 662209454 482398121 754664710 344822951 613529930 612734145 93426942 199417258 592158389 159017472 361821290 895758943 459272725 739989498 420448943 178790369 983418177 945664257 459211391 41286441 314883478 128752158 447958344 923674747 50859086 9169959 884326643 719640735 999221819 634112613 159001345 745907594 575615241 58492341 75657980 233480393 810887231 535165400 573476195 715677932 130036626 779184828 54559621 714454277 404886316 774639516 265435124 173376943 510056877 583511976 65183510 579561276 405954782 668251750 396322289 728111909 236746942 89975839 627179872 77367112 742350389 283779341 760504265 359069183 713651866 74484424 180151326 351940401 340138882 842645873 200143664 145371394 77148760 947489603 755932459 320093461 944306191 536525480 539481573 118228462 744277015 23588920 148606757 764050944 657010921 915850387 472725735 391320749 587197835 35423262 499114959 587328195 557695630 825183398 879947214 349619819 979214951 528393399 619565231 352124779 122269583 894462171 528933232 607009650 610556794 186664736 66749105 480149451 574256838 883321236 847969942 697081469 645673147 748652993 733415080 85264174 555574504 971499109 429009884 731176397 874517629 858623622 813700606 758815987 484393649 725671350 774348444 579228055 656191430 224587467 311011232 88190592 157534259 652772233 133664555 211486828 194417244 306917142 75388160 420041567 323903444 248480291 51767178 776294785 254955809 91006718 975402889 582100257 997077916 337717959 622416991 722261213 1291281 471358039 719214353 221725486 942083901 294748843 644263093 63061178 46762664 8144537 121604043 228476090 630490144 63512030 892350394 353383264 566321361 639800922 227844015 687460186 711631250 556037082 270160398 495376724 250476830 309598269 446986876 342079802 593268123 831242534 747009614 648718860 203051968 717738539 244961745 3714135 455263231 928659241 648059260 294556271 238157557 263146343 27602158 798022525 576118963 577825740 770067294 822509280 491902946 346620753 405553447 782750480 719517958 64132661 896890693 1440465 139250988 713735833 442261828 305724086 321416571 453772101 336167611 801185553 46534501 998902639 901511515 527245958 893540382 65649166 263805256 990321126 658876867 782446299 391396992 33740242 862642665 110941360 135548955 952206981 459685787 894208453 496430089 731200009 662825754 4041373 420952822 446206553 192425824 810217740 914976789 569398555 335065223 161316304 423588340 683248208 86389369 405783086 542446834 73747779 130043433 181451578 766250571 639906106 150763025 955271726 67730762 567961814 366865426 111404971 456697416 40813236 571650614 152239192 990939487 860589290 573840000 904924079 952780817 725507028 351775610 618129875 11843898 80478742 120057016 258653878 816001137 220649246 550699593 150344016 468390523 19543618 433029904 509806567 807436950 966678157 274038257 828851138 390123991 807350496 967770914 723395894 546452742 427250401 680383519 104920077 764381427 262943221 720829699 659872554 7281184 672517047 854491611 932339156 350990606 323410657 105567889 514484428 864884203 381285495 956158976 278674564 116716677 583111359 908932666 627629107 593595862 764387416 59510016 157736499 154400797 206649760 353283772 806543659 141267039 695757205 612353194 736825382 255305013 398822917 383712462 452439469 850621083 387581811 8195567 107776953 750484486 189238889 869611314 589972764 713709408 401805114 707249152 622533358 438661595 830804798 338411910 83514580 23707104 798887152 330304379 533068103 689357515 983102331 794110324 651223097 596331571 605560263 955777501 66943143 158796187 950315074 579559194 895234486 119542202 836677761 516990990 848505965 596654404 530406974 572667337 287132058 291395937 132921848 683813597 795121242 726047920 968431452 477656359 680175607 267347113 742143630 529215432 740563568 801890179 336302199 997387164 936287699 760317876 350708568 401653449 241299600 924598969 502174647 530006625 132368033 856687088 336244164 826178172 380875416 54573210 415129696 825858268 201532219 444012774 988019170 701697808 325368730 339314982 777196246 358743970 516055759 901354483 5700722 712112559 315966445 943454653 371905844 79191084 583572483 60908837 743028255 129705730 719377158 808339201 853105042 394071794 759857504 442523872 527264989 43195380 991234991 373578591 803279892 328853598 332138700 594918199 401091455 727560832 633071073 14901117 588179666 105526850 982893464 546037309 621491588 169107314 6997250 740107825 986471928 426007073 526646211 328256898 774797324 813296977 4431061 632520493 175469825 477449689 618924067 646701777 226210004 941736509 55818098 567917380 756747342 982872797 745161252 416424005 299152579 746327270 185594653 347833415 21061961 834997404 55105413 199225258 266720877 599895910 697666824 873265100 362143664 258840667 605201072 761896576 431071423 128522140 889713003 979739046 385217104 349199071 934043983 649525363 674989667 212365365 816755794 949873158 656447703 567264816 40426136 981214194 220524537 987912834 954024431 93576596 663767202 109162591 884097979 164363648 103593217 147426950 892487881 888332641 987167421 450155210 551543976 37945332 31036506 220655079 743560781 557232961 774286091 380710684 574429877 187342937 806364369 846214637 552360591 101783151 87298567 73911489 920969000 43286910 526116056 435828915 907352415 512370411 860184146 406594186 147918289 361730462 410970012 397651133 310782772 475514310 33808101 438900981 505606101 769162509 122876203 504863389 283655738 316187809 223451392 236796848 62373488 53945969 727485947 596142314 936585344 564891059 744754239 843583727 813696171 10157268 22258530 741483097 541654959 749667045 428820364 798428453 463997700 736707139 777651832 265504404 485784152 499654591 878893601 799494836 495956890 600041489 981717069 662840075 733199504 271248840 726302740 480171112 760705656 134841017 52462167 645909907 569147398 59532864 738653927 392665691 776820825 958168875 453058680 440617896 888304537 697133330 908122637 452117035 727457459 897176457 856249762 495824442 435233286 140376087 121559942 279548346 456027348 845392470 269497638 69508760 447925003 870418025 344520554 184710908 331172086 511733028 558769208 868674005 179125070 896431830 418991796 5642429 261304590 344599237 999562386 979752655 415177756 35534679 450866454 332560439 66999501 42790974 62843145 73589697 517468247 673065552 935637490 819578567 726011362 586192806 969523797 244180296 618522437 464434233 552664314 392283754 216997003 360157667 34489655 139233901 335049508 404763372 202826255 939777951 959695035 235203454 36631951 146407340 42950434 267839117 881941032 51531676 113902507 142312201 700875995 810138038 681053279 559624249 358379779 236930914 737233435 217998124 355057928 235492971 630677386 306445703 863706229 632004584 306930024 301040335 52948154 994430585 172104258 73082707 24492838 637542012 513656472 673452221 935762016 396009008 906087415 686006715 98456908 43665184 235622568 430359659 631048750 576572415 343996385 431534315 315216487 504689100 328207453 138322210 4936619 10839812 102168438 246302989 240094156 73939627 652052330 181208446 941802690 891149273 714839038 662353834 793453482 397205923 234325689 971215780 135011607 709587889 383681969 859883087 119228362 430801941 153882664 592277754 319541509 151084212 818623462 410416701 779466000 925414591 359606772 380953137 728248954 964737672 842122534 812296031 703555212 924470018 280041904 895521771 798747712 844978534 525240236 70687347 604975801 713683143 67810624 970647974 475059979 607217802 671444637 249898484 829267112 598691627 625535719 262198763 577816083 862503654 724584351 287077190 587468772 937302363 426173561 494253202 338125104 830601289 118419839 362721673 761685727 48472436 523553000 770004496 916935813 149576369 781843950 565504164 867214145 499673150 44523301 665815407 126928251 334709364 460732372 88695041 140158699 662818 666601979 220732453 148802666 289738980 151234788 17261264 385570757 809772848 359047680 595098799 518984716 54972599 352769347 658622179 191665879 973295271 838113676 833831066 63610846 548295231 569541630 843123039 394214238 930205609 822979262 828815401 702606171 211993269 13286500 861834940 299266718 568569760 442020918 7214845 843830497 954309317 158838690 378005699 115216895 991320488 426398535 142052729 431196334 329544376 700089271 492673269 557602793 954300251 87474481 863699378 290592242 894677523 567586951 163552446 216138204 518959159 216968154 263563412 748537517 187411407 741060506 23489526 828242244 312708713 253813475 325289621 715097993 201696760 622876738 123466274 136666521 247346422 614227518 867129870 715101410 796386180 529357804 216661666 921522990 402206019 50146434 366717886 357914314 682450386 156485456 550944267 258090803 668269706 456852085 700669107 971695232 532577017 582386537 334748112 607515194 639295059 832988851 91787782 999531663 465546058 489825274 857289272 124627628 337059933 552617195 692597599 52469465 584387203 653837842 186045420 63893391 928931679 363288736 973957221 8707185 635004867 41040813 888448841 176407201 462045131 942504660 584842745 354201571 171283246 582825134 156454454 412587166 983517328 264410402 108678195 158787750 460142744 756834655 249224038 709768934 585855890 180685120 668036147 118300308 21869030 264373324 697711107 606460124 795578689 300692943 309947050 125028070 677044915 862642189 447853449 852618565 419198381 927584690 130946557 402981850 354292644 394258676 559387227 813704587 486642735 770372518 289819797 869589383 494595373 141300384 941023182 727605387 149613111 381430961 729101105 512893906 451039886 38744966 445888357 568346886 319189477 669612202 890559123 47795991 734324651 837483647 94409576 359162320 761945675 657155465 212327144 15289562 319275685 227487119 266447740 689524078 960490223 223776805 208919240 429533342 219338724 437333810 422056797 927146701 362685128 192865958 550472845 882851739 279573670 778694323 737911410 623016339 203320692 830402605 437327590 667727948 642976890 803590259 275392629 676041024 172321311 776301477 253476336 422694748 284228152 844592553 759625057 331310403 783732603 896507028 107359891 822877644 792623214 433337295 630886947 434887573 331311857 394904181 909949206 931062032 531194145 364771808 799999670 8446533 642430841 695444408 413112660 294617800 40854318 550064636 854691785 349256037 143570057 793666094 439356225 538035297 245578348 905253770 401233352 140155087 157319044 637535599 630029128 866280213 957036484 569944523 262402614 307683126 778619441 172027850 13958403 591903638 974152836 993962871 910090513 47711844 984620536 227461388 349556760 325440370 766447281 109072670 63854179 779546322 542454869 210244479 7156100 458376544 486970024 795999326 977355744 610109661 80943040 78192226 215912752 523781144 676689676 150867814 411770006 235869005 346856282 15997102 403027230 514747112 60067136 940655835 483089960 959457053 254873671 791190196 174957271 414065830 488922327 444461574 485982868 330430442 572647137 360399108 589721748 447209768 843398077 771980619 957871966 286708109 132499722 914037144 383773632 91365870 411478589 980083460 868818551 114759257 585820516 683520089 237072414 877433636 725143781 469969487 717080745 366675855 552243668 918599971 296240084 772785584 582286156 37514760 36894311 208579366 739060203 848776869 995783905 590617768 382858304 486769670 139872874 487141415 124553929 263945088 346338218 885243254 435834270 126178435 822746758 213602929 440094553 455670062 647768700 505514824 100385892 686805773 257211335 496925228 321826719 331309598 607293305 491968488 517201896 894855148 64916009 969418948 199254475 306111538 729846364 620897881 541510378 206469204 8746491 933248118 658415474 286601461 798394852 136502247 530294207 419231397 651704740 272581353 253148068 972001549 131479601 861794500 162622277 797082355 761068015 568743417 893362504 217305681 926552081 934575873 259300325 741894823 69193405 535773749 556124606 40445561 344170952 172781975 692079170 105861743 670229230 733066038 879701082 513024744 353506889 243364631 626411741 523889247 980138360 7831825 713710078 137021851 992781471 331185143 23129171 749703715 460504230 859489581 577147190 352117449 463344617 996842031 697087903 477492380 806331187 765069916 58593510 756028961 676096043 249847704 947082635 915330429 378051713 374618907 12802252 482756715 953575906 524946579 475689830 677537576 418245569 281839125 187042787 489600512 130160478 358247454 793758418 415893889 260945567 247523606 112311223 193367108 56383552 556152076 285807210 499731734 354211500 764045157 451409365 211252294 401530578 514199917 606792127 718578831 793773556 366323655 453918833 637723481 563612946 169385981 854575756 757603143 408080183 105230729 169510753 203629642 844727612 20336610 582057576 427410684 804059327 866790674 549504363 885823194 332977680 813416223 239092179 847606762 327111682 145809742 327394121 904435446 646367751 29044707 858602446 307336630 420364509 435014214 323686618 8701296 395985329 763418251 579380074 899456164 99521287 282785080 708445262 224949932 74386094 837870393 703253179 322230302 775199673 117100047 863242550 877818638 860542589 585507352 646206748 35262520 618465149 573216136 311990350 914433547 379517851 439308101 52527921 62231283 695483331 309578763 508519845 381269135 696773682 185567098 809246095 354149422 982300575 679624121 906796424 962816962 527982737 767739778 975434884 881519122 313069189 715581067 223054868 51630000 322284510 970443752 257003366 744801924 1862840 454191751 519904889 397009495 605773630 896468836 885175597 45469565 671043219 108477250 750804512 223734035 306666253 981203997 10642796 629913738 393771355 635856873 601216919 221978431 752895993 50851372 7802405 151965972 564223593 961957436 289725816 42701447 994219534 262923195 466496239 986881608 220568135 64065550 203323662 336221576 462548607 517889100 587710275 551065540 347360326 901493714 688381368 989541269 569510936 449822203 626996411 61574002 865769661 383751961 351153847 242557629 225922369 75186503 336776599 662456637 275268963 441913496 294436494 981984708 362308698 566771592 830042385 663758391 896381595 685640825 669272277 266907245 911699861 661295666 77655868 538835602 234533447 461793850 711047075 579771381 912358996 843388699 607425616 125230131 650059824 234485414 267352743 76900864 448284921 104802137 331625122 419237003 66371611 165745234 568019725 139227662 482361912 130923440 398497514 113603780 809023897 193865294 955665627 17186634 702916128 50898542 62861522 545859909 67305597 892920788 17183867 76467167 304976389 414830093 369514681 342621605 204411665 978386582 946221034 664760547 892188817 421158886 963345682 80413782 695431576 599233669 962334784 666220337 808932453 502903149 780504614 326325753 433651823 193281001 610636271 676112448 668799355 664162681 388990068 571258295 387022310 9371109 565203595 544095775 499160738 184412256 382191365 119568632 43584970 58825451 880338528 925802821 352295140 616258919 121289414 42083617 915719063 436867820 701697912 869282247 524843797 577655551 617103234 246048958 383327247 344221369 756080362 175731876 150172005 332130476 622323190 746622938 659234131 318354580 845890814 515649555 749227969 73140857 443726181 561856085 938509128 324530381 138729328 727489993 858949854 618224205 57779429 352653149 727450128 951298505 476037862 876314202 674522516 277127882 671975554 665586820 871107000 40051262 713234673 626196021 376570220 990491863 726736362 72035955 440063801 556590914 352708145 385118950 562597866 822731249 973567052 107781213 729301923 961459714 473619997 722197707 270709454 285121859 868799092 245477385 877615444 840255637 921782380 480319975 895333872 55754319 790751379 785159483 576354820 626381749 835395809 493099381 796679926 833537809 848222543 74361423 529367173 503737611 272234742 296030213 373798342 511754968 842265712 561241348 861535465 719523020 950671466 428926228 622212449 900936908 643264385 790099256 864102876 8083943 226091084 110171614 315034218 713903602 907240814 296726863 315965712 144811881 57903897 562836908 964611074 593890823 211079288 886372526 251230524 132304224 892106169 399868075 540092539 503534919 183781451 487478003 53533801 618890890 319160450 389470007 605506645 232422647 885493877 550245566 623035722 406372500 386872203 646652328 723303692 584112118 715641006 47206477 764906441 781349297 806833771 633952650 419454463 723293471 309634109 555274476 829101655 57585919 360866837 284433032 589814173 890154852 55669291 623778743 210259866 988469114 921656974 52638111 5441689 82057001 611859968 156692972 455264429 645496213 635955078 43310563 1673343 642816614 163874225 270413193 483451470 538141312 93821143 845748149 463568673 711828242 261210743 783724425 526580726 172082076 740538012 458680427 665422877 638212963 173554445 550218961 942727130 410117055 77030899 126016535 733503677 482229383 599272830 331705845 714540651 546385060 149980693 401357664 287782562 885833214 633819569 995495941 638267088 130735447 809534201 318024982 972523700 145129520 866407135 455342954 407174490 772252192 162802311 613126842 932548846 187425778 873362764 322699790 258203216 122332945 288457963 286747256 514309007 234823456 652752450 602705516 437047102 640103194 329196030 967448048 473768931 444174529 94959995 203292672 915207393 400537595 306548052 177122563 61173657 617773068 338221755 355800020 401261514 328590126 441555195 877637846 490213331 580241880 418590370 24259284 808971507 366711307 457359165 119413070 865038223 452920140 755412948 106506172 947997064 999855627 531112637 958260592 119894144 334774463 791114327 98577397 838456089 240522878 469776378 854354555 675339556 181036324 947320745 600304228 383120779 577589401 579252363 898007568 543099260 946644352 768038687 690309101 929365724 520888027 639118122 634674415 385032881 922363674 917403283 125303599 571959515 468637579 403962553 384106598 403370888 663787161 28823815 528935378 456062945 164979226 583021495 306687860 329929517 914579790 657981003 248713434 967731806 582465177 166590800 616816201 824188556 911000906 267178511 728325939 356094313 862182889 764561213 723287032 25472359 105183146 498295570 25700369 700230165 716455404 922363262 264543267 423646791 827716288 998687825 569790964 548587220 995356795 690975356 161687522 581965551 731871540 787708916 324565883 656742822 167467299 892436965 464826056 584558886 819181649 967503995 993941636 988399971 173853000 728966575 135848655 803039750 136761769 908725307 791105319 189513109 920654607 742166496 813443365 145308414 806820248 938005291 591191953 40058413 573180389 357657940 546797665 395745097 142706329 633742783 131549764 377948589 378248226 322121032 104667930 694027044 83128596 83197526 58855460 110172147 390940333 907981020 755750695 956140062 726348728 166254511 282747774 268139994 62248611 995574626 757853171 492276314 103888910 643691757 319962908 140557570 403641494 326611754 479767516 224777620 42470624 931987204 669630216 495056099 180152121 769179893 284523517 993680112 391883653 876375829 39145878 430725788 462894700 916247433 562994553 699003573 509799534 677759620 664026783 549664550 201026485 15292380 768779400 814125212 818866778 152410384 85312579 858667452 646950054 700979615 94199785 749569592 696593773 613687988 150216173 864231470 253223278 124222869 637809799 773203722 131654111 66035354 429999797 554275372 5709888 558381934 602500169 781386977 861111247 298206627 285558265 438809352 775995094 376337499 485208739 307518395 28855174 655884446 134387800 672090889 625689593 828198717 787211060 80893522 781304712 5591997 858290872 132156952 964795071 505332271 442021074 999555099 959722714 786912037 26733335 628073545 260007890 242176355 422294114 933527193 696331938 788025409 294740850 711780156 967781032 578179446 819718134 49804778 481502511 661431369 792278168 209441478 729174873 430426780 992032853 864867220 597031654 105917000 26278394 120286267 189938069 64990451 674215799 482041341 422324918 850033792 118951611 888316513 399495573 930346161 461897089 388872056 188532063 997898499 274573887 5959302 51802848 103403907 575443424 384484800 583168346 666424375 260580857 228537801 30793131 455773188 733392483 854649891 110144258 957649850 293247129 316165966 387994457 144034367 338279439 910763591 12616875 862199274 291923036 765869415 737398345 469709874 141799313 918632866 978127005 699391192 929735574 309061153 128684674 114876005 678561899 372040258 352707050 706167319 224571313 815018062 547824152 624300961 755730264 404366966 494525113 414316946 120229064 35013467 422256376 323495008 650248110 370818842 109464318 228352498 368832435 454440997 446018793 154798094 504861452 459293682 924757159 382107647 772726768 254416416 280607916 558157660 620822880 646771295 673158972 72045948 698735968 882377924 265089156 496215472 688871020 847904080 623761404 826571819 450971474 963299280 106227775 647273496 62691034 604324554 531452611 153445195 151341136 123367649 754526722 867360913 576439413 536652199 112841431 200214789 883449449 330058588 762250261 684861882 25932069 646089196 651355527 874407161 805224779 719285745 601159042 398708030 682296096 698397435 123657363 116374840 68761625 924242695 324157190 818555810 605791231 819908288 828329776 136448923 86795356 153853435 910987152 286697747 82651800 170095062 841294530 719686966 925560849 812479469 257515964 774134084 267246653 505577932 213951460 588331765 782340030 538310946 8542179 376945603 114546512 269493537 401110856 662305846 535943537 866436147 269769192 919789695 628788711 96444549 275336846 373108436 221503421 102241785 804250905 246138486 944445914 448949361 709891885 340332884 627020619 504479021 289613321 876119916 827113674 456272982 27653078 22670315 450594728 392868451 771380186 153332221 345185533 507604037 336767480 71250782 202276122 471791124 916314342 825493903 308826598 514670592 801999372 634316767 842428029 240334196 559231856 240899997 571401969 929528107 939883387 894935022 549502582 892342753 828084552 556374994 142505974 488493839 3664855 947451469 899495255 753839245 301562801 228723623 632612437 226075566 507718919 57610144 585851721 603894315 18994141 19571249 570563734 237965207 780808047 736185315 586993674 294345843 434110172 577892285 577338700 761613897 690326364 954757772 276130220 879559949 51299304 623906588 416003178 145824494 981648912 52094389 831784607 986941361 168574423 791268457 506013157 650891681 182566054 292383403 748803247 214599125 198903336 484046642 630671075 976023708 704244534 338403125 731359049 77893737 771975120 463575397 909371455 918363654 43706792 249066142 43754834 514275272 346436919 182780480 656744287 885454783 122200090 849939029 618986768 563338844 710926491 818726247 698937792 605732814 712115766 672094453 235202897 432841548 377135650 788517655 316137525 763363241 750427052 682330152 259845624 644779786 713495926 292403846 654767933 196638279 835222919 95974364 683702582 865360856 269521156 583086694 2584332 860535991 625414857 358703710 374919686 146980129 573358933 391907673 906986407 925858 696131624 945066248 993719787 246213678 635923718 916048194 622373641 155332978 625821697 385685652 701300894 999685001 769904352 325145856 931603419 640380602 894442614 736513962 938711695 463120136 235982430 646278234 698141986 681046875 808430997 146855279 693263282 964359106 805074952 463669736 672429101 509949335 714589090 604467863 812210218 838581770 325527221 707649738 846448044 6831636 175653536 879451146 427628819 620916862 356965647 821486161 909032554 234738999 708663918 564607379 942004376 702912949 780193209 460870683 668310401 778789737 236120846 33135038 548250038 922479030 826792506 469312448 527968426 841079659 378573107 851173524 43368646 746620343 500708857 399891480 771520813 747593615 460449690 761271285 685526076 903509831 378372736 701354199 969405345 160623347 992872446 798074249 600026219 607770090 530979700 432249714 893061816 948299024 274288322 104637190 10164004 441077545 570344875 923579960 516288489 39419505 877729336 127404941 185567134 552429024 910862933 472203678 103489970 358302853 454868218 645731610 626749577 540648353 550784964 789530457 64928658 339123728 219781577 345147934 16253698 494149907 322250012 575551203 824966557 916441597 227635710 236071171 531512206 591939886 29573280 199142119 57056260 401267593 596482523 157065524 638690646 396789137 760370600 906058556 582352453 764536396 600334162 100076083 984404796 362793753 459235924 739163021 35092941 957659958 805768084 569172255 61480293 207019212 231684494 838238287 85777214 430674663 793636039 911981338 62928296 926692677 530064458 355677468 917615290 300974177 395166609 234326343 181046800 418378600 578109099 175156000 264385313 967108156 894341789 500663467 278318760 626083472 833538882 46874686 222679431 444431522 580411126 391451207 875611840 707657592 666541693 288305615 263546498 755531274 606932310 515270007 471865192 467474838 379160647 98669651 845294987 570493418 865819416 475957253 859732783 420415741 957107174 521974077 786223054 786576521 965743896 974180294 543777989 942077303 49206425 150691532 351214822 989655347 139224285 715205797 973035403 809512207 474971437 803397765 900492666 33174475 397830846 435441774 474580242 692205731 639314854 901929381 576765107 404591714 820314904 267050836 368902588 116278627 473715469 687201975 100199397 982920697 679993946 381190571 430592969 947784615 829043995 132030894 215638148 197257555 709766623 10910330 20054468 835740726 373921385 480523808 582969005 538774437 597501546 502401835 310480201 357839571 720914588 582447824 776526529 597052058 832361813 12807989 921943213 995685723 486758284 370845400 677232926 556311003 617787999 383652318 204755598 834937004 815298859 511275512 686455940 33867240 840405174 116115441 726730230 610682791 948354754 794627330 997978557 576894393 388968640 203142112 125460902 263878202 154629616 536979338 831425665 753164159 795926383 262817478 84523979 48449823 920131458 949180989 765384950 203064034 6766371 904518720 49438157 958047343 749353574 387263553 142010071 929399981 966634290 42078112 322806072 967209548 427578086 470741578 641416133 753687997 280060478 686748795 710801092 783275113 714166057 61595809 436737123 467967764 60624224 460837261 79194811 940713126 669026843 362849521 76901100 977388479 170250074 343788382 703459168 246768396 361287679 923484784 722722952 233677186 873592196 174333470 339953375 139961760 834307448 887734906 408374167 103038276 276490575 997910649 544683089 501595515 95830661 501531278 217996218 804620983 187712356 881929199 772874205 835503944 813778804 174591633 57692251 866972083 819827026 987435848 148056376 223405203 728634694 288005474 160590357 147684013 717155231 411378432 762828183 968704276 57133037 867484869 120907916 927763176 740434393 620565186 301149929 742724515 794739893 101055298 23414631 568882477 441046785 885628401 847019601 736137925 477836566 448791917 976785647 104839817 75731925 966737554 305850965 170396316 614163864 815699723 501763372 737401254 219608712 353857562 850855571 20920659 784456018 959120340 433350632 638602058 367466662 582999807 997727410 188813772 577297286 465801584 105318129 60255024 973541711 247874693 18064586 681160724 505466399 49038549 788316265 621005570 970057067 141523797 80088551 54249701 849617069 654405209 23881339 804249112 94651658 383938904 526649882 942635987 762166399 640598838 13428536 668852898 68876252 903842565 395953689 215023356 838249930 48150782 363962779 674587503 903608603 426338976 103839762 555186010 959536776 523010874 960364017 473826852 348326987 556555515 265145149 657124782 470355023 208010151 538603518 967126083 380502413 735654640 53628783 527481955 681741086 378383163 240388944 241584236 697613448 198420490 761021484 952291228 563029803 713328815 730597556 706244877 938397018 204506359 926160711 968538352 410131633 518074784 834135072 607571011 546034409 292198603 220127945 510078799 552347451 22840793 518180476 285967041 500881816 65327745 494868270 688866746 220396504 395937978 51692763 397000266 975993948 165218853 717411455 215675828 323046873 697639726 14168936 946825284 242065282 727182410 920364535 621234142 11328846 928332571 185415825 210931104 868044192 308236745 783405679 61424708 315232425 102648953 392847448 774200630 817467966 147666425 772415494 800787531 256634272 225984210 17719360 267125796 181890734 779336078 388004078 131673700 151764841 847379119 47528149 259305745 105434497 912970090 512518120 189499041 815423438 462067076 410396846 475366079 266296444 571235141 569209645 638610367 849223022 287463111 789841266 688359596 458891730 675455641 600897819 662643072 118952573 13303514 826063824 463208219 310926125 355559069 34282772 849638260 514677762 710856393 89571967 893518444 64491893 344126990 710907181 506263478 73341485 600220949 460284689 402961123 832684579 134831330 433683287 271510309 703428763 5191586 262030279 474043254 179020399 9393581 518086507 572154653 337501714 906572116 24022746 629497159 811469857 650547646 253815761 10011417 910799382 901513375 598535919 789449728 684722587 85680545 213544103 101521981 722977997 955712450 183789578 663161277 347114987 145761768 413346949 534025692 479139829 496860206 807480598 262926445 987051970 481638072 792266133 299544630 942085253 300725554 759803301 998424165 46878956 565380739 444827013 793665824 508665292 357068430 36156554 794304029 283601973 757605832 435195297 750240983 61146829 280552001 277518141 803624788 288854219 193140620 856230777 954793234 476708496 294281032 177009945 32015421 316548648 965227749 142989465 9692855 45239016 761041989 297884869 735526183 643339785 920023020 648307413 703495096 251883154 733252985 267828649 318954025 717435360 695499402 238111443 11033455 281928577 483771214 72940635 298161911 623359019 150212308 103534965 889308181 839278882 601293769 357469417 533816731 967842124 479562098 477301751 400630490 789005395 722405785 889646586 186024289 128128989 632664890 509616875 210525963 480185725 450320414 224780536 866028638 181053433 448704359 500441124 633605797 195268752 379576003 526922358 597444279 104328741 303182247 5531794 478433699 482494606 251497766 9851795 209579031 823152496 495655003 725419334 120637186 209438436 412583641 276662247 447442358 102204759 82907403 788192673 367385801 248395998 42818543 427041989 242775365 600965889 89112981 805777420 448507804 489304199 340525598 729321631 113066955 914253396 547388301 466248795 539155138 999435529 330060615 213137881 413657197 329524067 942826152 849793992 153210610 428949040 941619182 244235116 325209964 238163774 304755707 506280321 584103106 655419770 383613398 48202498 627784895 989427802 777495304 102904237 380384383 292415038 810462101 910393064 474608188 169504983 590541217 22481307 103363045 857509957 997855499 528230610 767313971 972733912 664054803 285721827 20613297 543203969 11633364 34186150 1504667 44798446 326626397 443710092 230388290 101685981 472088106 653601916 578502459 750969934 955551451 564107106 26504894 793316984 633621813 990112041 42883450 312980253 383436212 190476698 372074676 337730750 150766492 422107195 737780538 252050251 957585607 717279615 662123706 869563937 823170238 613432353 977764442 739726920 957521872 452218291 360255510 225770002 370061281 499025822 907923545 976775506 318569180 289698461 128509453 706490074 800990270 123275011 275080807 2969820 85913833 939794409 751772969 168697053 953038637 486175158 310895877 238194419 826817442 394988563 98172617 425423298 137135101 437508585 212301551 68898543 272266132 757571740 749251471 829249733 685334698 895962397 673928206 497476149 208310940 3989604 298940138 84470723 734402910 449022354 398640538 930131356 176429873 914847080 782748221 563878624 615204412 66531478 25702302 428091054 895565786 774711 639587091 887437453 841578092 203336494 247071673 880897828 666794003 104811028 232117512 952535344 552160701 694908753 578810569 343555986 593814207 788897888 305912042 830738506 107956606 702192825 358903711 602831739 613649872 997819495 429869563 603807921 601939972 308586572 970125876 498486907 458426677 79325167 392601405 531134010 603596051 90209366 271939691 752027031 805289675 223082791 205191865 303552527 779498786 726606162 992958417 951604794 235319897 628670746 189263703 593317624 450986418 849412616 196669283 868941830 771587528 514419963 580337662 573159630 7407041 563573083 207081509 407531918 791537702 727124535 172910662 204338178 551378918 487863450 696488158 21925772 365192017 797055856 779303254 299347061 620459786 548751489 52608023 956768647 183255802 43930672 589843865 91363642 19495317 850546295 22728635 605855831 579462360 439445017 755489566 174412007 450293193 917011855 143643626 899914821 692906556 190090334 678411938 443911025 200114932 903362564 260546732 108322476 321736601 681871588 135941482 822780820 898861363 90684960 80921553 406901066 732133718 375113124 53235410 586495141 155996959 204237423 445234243 481119462 6233894 598610625 176901427 987487855 550913523 229125883 715520735 297898551 762619017 220796910 467803010 708138547 589037302 665974481 398226880 770754001 718343538 299691962 454009913 655472273 380342114 463991467 717679837 733719295 869125480 869958014 248377902 841407468 876927273 367089267 694591943 379969188 930254775 319457582 656110491 201588392 317465933 68422563 886111500 704664123 495084202 843246844 246485797 796947637 950956232 314446068 567972840 63617391 615680119 948422733 718562767 846272980 295445373 771726850 118480939 730959169 805071802 792989052 434518272 555987715 179504054 464180214 344958775 592444911 690914942 621784312 671337298 125823050 219639366 891841293 312429481 32290865 835015953 708838772 421226512 668304559 373387436 138232334 789305808 677169420 468667950 192487912 800514909 801026681 981728205 909621469 891837125 977912301 2402883 964271959 758928800 631087407 855825550 907532214 288620357 993996931 446430569 484093605 552071615 461303238 892025226 593638964 634727910 653299774 612245861 309639947 188461684 630890980 615329800 842361359 398803337 83102862 833588651 144627052 200721023 83423271 417520088 529720251 95342256 362248041 308951423 590381331 731824127 489496556 472469148 103322968 379710401 578307441 433082265 746150550 45453649 824331168 808228805 637202556 88573521 892885457 992905369 397332163 558167132 680171924 868469580 677533881 25941335 577061786 629905322 463561090 111793656 475840416 918661820 533009505 370323328 505196098 285040261 965796873 137844289 226233842 113462599 181141473 840928707 341164896 166626807 976050277 391800738 536056122 962007397 717161692 348812754 646124610 225097901 132155745 582601179 791622285 490948612 441061789 316211244 585001300 875167052 494047532 462961944 175789783 735577530 310331845 398846419 121508772 373853312 527164685 457278888 803302937 362566511 748213155 231604204 487118808 192234853 112480925 728682653 154664074 88761659 637513942 657655042 539292383 75006342 953617929 908021314 432974197 218440438 509742652 552741706 164131313 500344467 124284669 509969976 539024150 128143107 144860729 163012253 628648065 251946735 623048944 493198177 273982838 402599440 75930314 516881959 924282835 971766236 914709337 5968830 60945208 684642478 132296701 751001348 829974609 533544608 797958916 161580410 567647557 318489575 75728075 918436415 855023067 348853589 236373028 720158978 850910431 349006135 415207308 419280921 849088032 986011352 41948365 642507638 327956800 746498179 487290797 934418498 906784187 839758271 166991597 288118286 137019541 479534213 207137469 834912634 89271873 149632125 231286954 76732156 157686431 86400795 768192291 174034096 489680735 602976867 697337377 921147267 277493752 113311335 718249444 59457591 765803078 441152692 285308156 855646084 910390926 37219021 627533380 267980327 145574668 516813272 618302833 727612481 85017982 865931794 985586750 884744148 730451149 731901232 121213590 374005016 981485205 743947148 218181655 822349045 447618918 374396217 560611912 326746526 387743715 457352145 134159249 126888363 655658342 458087191 150539939 859387498 482146257 816090088 964300449 93021367 511076024 12768047 95635399 431018963 835670111 343252453 217614796 587162376 790823401 641572070 626950048 677844015 921630035 723128084 576743216 933962736 486409292 785074952 646680045 146658834 844160685 59217202 301349804 6596493 367724288 770494365 214557606 1855482 589372212 216434047 956228777 312362042 419618979 652389987 485683280 241217732 872882171 279235666 488341390 2658308 592804703 438122454 774162697 78705064 581092685 367326959 501379275 824933132 20719669 109684235 113449429 60044412 686711645 366464593 684494857 152421038 503415873 42588738 587413934 595371194 130198490 766794945 860459827 364510713 900900453 395302314 341198867 724481350 446789346 634507100 151450264 542778682 936165625 949311122 479286716 469226898 656536819 35821922 410929661 577683164 521833228 641324967 364091274 735388 516744020 657577322 395668099 946227412 730854785 240470011 727287978 127750949 822865360 226634731 597789206 983595030 32130206 69239050 320815369 89699446 308292051 615144849 977877983 812620957 145044844 969444614 774550692 873451808 868305161 159490416 408662179 561972501 947191675 600539530 507152299 113333832 314551251 557365247 226380273 543276962 514623709 616435201 839151877 753880753 741701442 952121352 988253140 927562703 608822953 105227360 333248408 835786857 447935463 51541303 710987227 240012051 770796121 582876039 498863659 865371400 610609297 933465364 621996924 404423529 348894453 449561113 938428411 752397343 63492265 869935425 386167213 505391356 89073263 906137004 149287102 547636083 986636483 698477272 371180749 468140495 206847588 420470452 704688560 298139023 321057117 423299960 159724020 925943507 516141793 578592137 156834680 581473647 694016928 658850299 792411066 211957575 343666662 578335246 107800535 427400695 309212862 903025784 369072681 527529111 863850545 675184390 781559795 385126325 381154343 185414621 301376473 519327203 888273774 398541438 616071963 828360263 5401485 869368932 996406938 616828030 701719931 961642265 228316564 479274367 521347152 940433922 405821583 986527208 343399270 44225965 889636298 408569687 645215360 226616654 162387219 367809933 750603730 971910321 623591980 856467841 349408444 207345030 858695436 485271966 786708265 758733341 438796951 20285367 70671580 891803547 581925689 802201983 151821454 343829943 130025313 66903581 324889815 987956128 803331418 180190112 509921959 644517377 769865641 442262353 526269923 460576572 364627567 401267529 616603249 958944895 241630260 284347221 456855707 945041652 95248861 694377120 514106897 108064857 380217205 901143165 102276685 931035364 53054679 497710155 595790037 326791944 501694478 985812918 315029198 82137081 541594556 643234275 279721053 196675379 483757619 108366996 199619866 194033790 779380716 549426609 347101805 439116632 729265285 602900928 183456890 444293114 524189025 975626834 203278097 393978305 260384252 50996151 342594777 309116524 795859339 429089725 696320668 947244902 48702544 562715074 774196719 885464363 426809111 137158050 829380494 644414874 50883551 635616756 433022546 269332865 2792415 395498766 3588272 894793799 515682108 974945261 567866727 509176183 570522363 778673283 30143610 508904368 806254542 970198956 496661000 900128231 639964765 792635167 889901865 856031741 192211866 80310244 296381451 332854128 619358112 888082561 493776779 623639580 523104744 850591719 404209924 214254603 580302229 860651560 223894836 982952510 711917545 962443846 958792021 628567655 801478411 267219079 155078739 969750723 749007802 770029774 925522890 955988841 113692757 214407047 185171708 268903274 916327752 393181534 660824264 843702512 571686053 969400817 95584625 26134066 272763096 508801348 369613827 214667059 211472113 412548477 647274252 810488794 475672987 935940231 581706412 236490006 68020941 713813041 689163056 406502594 405009223 500424392 430929248 510996921 884306776 270564168 722572010 96349350 1099218 211623582 796611852 264312271 679607884 265921983 746997125 634101897 664904200 763261466 453096337 893146557 389104206 782804309 585820616 103709779 406484091 251928163 533807564 271613102 202739672 533556713 673782715 805284780 206329059 856599883 775612304 988937064 822433242 931118603 743590079 407090474 502330085 576892304 295165929 108719144 391868798 103033940 89490640 354727122 772248935 486397299 569665476 308777638 867518653 716579088 720197119 759778798 874424359 958613520 61356629 368917668 775320355 408630530 369512454 864958298 403795537 811364057 470648508 966199723 986329734 272886112 782045395 633341313 579716751 499877133 458382861 790544048 540183435 703456770 494097940 213991058 94716470 309569385 706158354 398963740 536297234 227688873 876575782 344969823 895595681 284446787 665944539 92834322 965703609 872800164 770149114 127188775 901027121 353468817 693903788 24241917 144718879 728198293 92302636 193070090 460031678 932153918 419578775 474786206 302723393 61842938 149972581 831078288 962604739 279392838 231640965 356961046 498017022 544282858 819377161 5472103 839697860 388292168 517018772 7123256 506189680 270516173 142910262 217097330 794904718 812506807 78902737 274313315 396405636 931672780 610450121 934466302 965951279 981538021 656662644 932139375 487967910 928354101 300567935 854438218 179709651 714923122 9496383 528007703 859781896 362093551 312231623 279563497 910237828 18344825 533908871 70875681 92029740 547290496 815042365 604042126 244336975 169402573 977130223 658327860 211241784 258503342 776588056 364333689 812692189 864028654 162983341 698564286 549198615 196610246 55695721 474996552 943794632 557512061 162401759 566418175 791091792 250699799 613633230 716082696 263357634 129693700 468388373 201734329 592223120 178626683 462221632 977929013 439643584 469841975 99658156 558504302 397516827 636582534 520904551 724643348 158947868 883522744 455737990 75442316 216971620 666991215 742247551 299119103 509486979 762631001 901031313 357889240 700533675 459223214 566558138 982549003 445019438 550903803 71121737 746343333 452378146 109656388 649731753 342085039 169768517 991984455 303408965 702403528 226017140 155896101 461244524 951050046 903807096 927398327 552728976 416986393 408445690 769120882 416034705 201409100 735433196 971572357 92660721 507471806 211569927 365908611 272013463 458246117 151086108 508168629 374860559 152393496 153212473 274441006 792312288 702781383 713483138 923288613 383296486 42936813 96559459 676898253 50427232 196389520 222237940 501665995 784641483 236674795 425237318 795168969 961004262 963878139 105275155 23485631 432152700 927543541 425249757 417784643 726302122 597216146 594731497 621185921 867412101 329017362 796562087 637491854 400009684 812926538 719791170 56219892 720758520 232925469 799416258 317618564 736348308 993147235 280874737 211848154 30950979 187534689 462140745 574585783 864579202 975434687 256235012 526594997 486003087 963092426 359536450 319169814 739808035 225398630 548031218 162582741 406093771 611788656 601631532 20437919 214889274 803815434 338139277 672877914 161745786 462588676 818577116 973542911 516540868 573058399 182351858 801664263 467008651 866442554 773709003 956207196 642065643 958359355 260894848 125760452 154811874 192009919 429385066 97051075 393303286 103896152 369868338 551021647 796113447 670013245 359373660 434742329 260652138 672633640 976810493 598097726 457751193 911105211 838981039 981761111 619225555 863633773 505814717 93526839 511438355 302310089 38639874 62257562 336675942 590914070 566910269 272142776 87441881 834633509 311413310 406785881 878691631 793239268 813294223 106087274 860912640 705496638 274021489 528299954 825174826 717301415 192926879 344996666 391450078 249083941 337970357 735837170 954727549 127521252 565035964 706517276 585132714 29016381 307321957 705447014 32795442 34741494 686420233 285091387 766638373 549309421 65460900 875540072 108238629 876414013 536846283 985259371 958918490 738302568 704349823 558581603 574491762 209660835 414772484 201861638 894481008 231382610 754063463 603765955 956604116 171430879 251974757 212778282 39082657 367690245 26543981 480316697 516198783 284687810 408960428 227104670 452252786 268397867 280395225 935624132 826109255 222601057 622878500 859486716 824964278 478948246 852703590 355946861 243064431 184223505 582583294 424388028 47839252 821956104 94840988 253784845 253625518 371525615 156526712 785728073 961972868 794836116 459624422 266411417 597855268 478606746 209294060 488673838 321572358 835963005 71248113 633968037 518513922 944151434 642473084 512201930 572539917 476003601 787211465 909839072 894469282 273782219 81489684 504022424 308592213 998278493 961690631 183216662 89485898 992589039 626795457 752803529 184768106 530156709 651559407 421185188 534908516 117469972 98700366 724872094 92096646 321137451 593072874 147618706 281747920 849783526 675913550 105167267 842338531 722310680 817596919 777956548 291541477 733666526 523722916 278129310 934512927 113329904 536304826 708559854 383790260 860574291 250765521 41780086 531583986 225319307 337521270 314693724 257212786 868721063 812913541 966060517 131627428 77053433 757117477 603080057 775152754 608648748 644225975 724716636 346134748 257921921 48988622 833938546 337982844 796592315 908428867 266709007 204598772 214358481 568567536 406617988 214168892 215588954 354136241 986391061 433694229 302102730 26576143 313836076 257978058 664490035 854785774 217843803 993220346 22458320 582999371 157973969 778860533 182218836 949640845 533003324 954178001 133754736 504861065 341595916 986977917 450579788 325819525 666735726 56713209 420060947 868496447 994425305 257817975 882187376 63465744 592033335 921914841 718832105 153714853 430463003 982931863 695463677 970692231 785205088 639571669 824972961 281761821 58914469 155113106 63448684 291898170 538305986 544633494 129438990 240828859 296635985 834844131 123890720 893710197 567852962 654709761 809829375 679164897 469372111 524015935 33249838 223981479 54322570 887349180 178470032 728611960 864680717 43464847 916988400 315964785 104248287 250780013 213569948 444019811 788564695 843295805 19572194 527685278 450262611 264866541 807498644 789230064 916300305 185196728 607964987 623540458 513040155 312841417 724853046 256908798 69388906 274045239 714988403 872025975 392284583 716952834 701772837 559125611 400277266 630645657 421945744 444067263 505572624 384499368 222534487 535665609 461517821 669329757 704733198 132135610 638049518 929915355 708834204 636451743 670719293 272239009 992261956 82340535 472118070 573552846 708052841 900632016 446436611 359871587 948453917 779796413 563951951 111422484 641746498 73708902 938057359 308455937 220904763 592561391 382165108 598290948 221573815 936670128 126472793 673309441 166057438 753081631 290991226 406917321 438242880 740068726 748618405 968778759 521057511 382471590 197167827 238587979 746858304 641558164 571642312 246117062 627592765 8562057 287789144 934107330 28657296 247740553 964272971 246485222 51359228 449604827 64277990 140353908 455027294 152398593 13339608 731421309 910630 181385861 969618620 27684839 140090215 890717721 78179262 184650663 637430613 207704320 406203486 859656609 307972236 855421475 926895754 912989338 846023944 759768913 512851839 348800080 471522945 99442865 612160266 557084867 314856234 174239488 224298638 124572015 413878349 411825886 246892818 989324930 451050747 56244610 524205932 420548475 671015740 975413866 832011235 2058443 9904050 970256277 118883649 922704050 438915620 701676194 798348620 673955943 350475932 882172464 597019188 625085886 401280233 754682866 47062900 1044006 516987387 897492253 41161529 930619439 694809681 350131311 851418805 343327890 279386323 585183516 375353386 488737780 542486717 478615734 544293282 1218086 539124974 350872318 3593155 86679267 304824364 716553324 560767859 621261521 341373269 477079911 608156322 231770875 590785722 765775844 489712679 472462257 72269473 803682805 721205142 523470499 194524986 502788097 921942835 243485943 877612251 866747872 390834508 111846983 264455677 338547620 243455976 596853175 612599526 796493285 140978283 515570518 170839731 88592487 746824337 659484588 275468173 119914831 8369382 397367415 200763191 899784871 312376698 193421809 360943176 533417781 959330028 297820387 32503415 142151850 929950057 695256967 611269246 913223794 511257289 278115377 373516417 60316539 555390179 967204296 304691374 671579631 735564532 221490238 110737469 202079827 251423537 475959379 159308095 479907530 737810261 393576292 968156879 284403971 466561110 317299405 909543637 70120659 32326450 211566979 642599869 337114532 431874591 209287777 764947816 247917702 789512662 977609253 500765215 179066420 812078055 393473501 739166367 875927125 640205515 662066859 519182315 946853768 697789068 102336322 499206147 491075743 482274822 968140965 971283240 718270030 82669824 847496605 348678779 358146321 506019999 620121789 973121170 394382719 422904722 920098026 527505608 748028409 959168007 365330698 77643794 324827294 294351663 763636821 322317629 540364464 402279261 10335003 973274428 807984223 44811931 86466991 446097952 284744887 909257614 221531450 333775713 926602176 331390918 845790355 249680707 910229463 995997445 906180827 430712677 881988668 516891011 178182444 824167666 764473865 969548192 324184739 994740737 199605673 465311763 175868194 643851007 603293543 140872901 703046750 216911052 540880992 466735869 552948616 176437392 486126138 654964895 385317949 441639720 701124669 553354426 718680588 224472589 909975342 484925521 706047018 45284336 794963939 285272214 175385355 139400759 535524972 552077842 431408993 467337561 975587151 692503610 921151425 953965968 927452175 751566778 637846052 984218329 236612714 783771425 652968592 441572239 774968513 252244178 144143350 83268568 86193086 889757858 682487275 552835391 199021847 780841807 305231019 502298740 94123445 103578022 605130421 368060045 716489832 30911501 838845392 827095114 758763639 728339553 490712274 987755342 695979897 40329907 491600581 788487832 529651225 603614061 718033915 300499404 417748823 213464088 514886157 343157728 973492806 804740414 430273772 923572040 516474807 379531156 445578209 560874127 196080022 779568099 578335627 594036535 732211611 768241071 59643191 723992061 276115938 258793103 234328879 235523808 793093641 167465361 784666537 539518745 651975766 354688548 9092478 474918720 898377755 997588238 266506619 883024992 540446572 125486145 270466390 476338358 632608893 446632576 92826279 541321542 109911052 485858317 232775971 556608601 852220300 153288522 523947942 638467318 510463719 564485457 444033004 383990912 780816813 475724818 827108625 254422995 232806453 510639968 407480584 64343438 931876754 291975466 20176216 961405180 48760266 230709088 802237600 190879972 575258161 792071614 576542721 670393783 145385376 428172779 358474509 452715596 861941856 856001523 166188986 867883469 246367511 732374942 846534192 952834553 831486843 785899109 188717614 781157629 15483870 287825498 45040417 971211921 438854514 945374272 353279578 768966804 272848968 576112780 122706403 309168070 597618705 41997380 469769534 628534003 578258262 317467560 535912736 375857192 446516825 819293109 986511260 715160759 150774750 861785203 442882412 533135512 374080184 784179885 829280193 790970034 954825805 559107059 649463502 299961755 875993598 476089624 441079402 253463475 532370948 744166568 272334790 321414213 182924454 958817520 645791267 389391148 531708709 957710977 826614471 837913034 680434381 369707573 172354537 137279257 282700924 278667494 828880904 340644572 88890459 24991887 645479777 112079960 325380724 261343251 592756147 888936781 687604556 753476799 970641472 378085177 750429316 585203 522597275 101435273 899617057 170916425 308978504 817968679 43502327 921634251 436179516 729273720 455642643 738497000 857532347 37853673 280866531 603825685 849430510 330812060 450287981 55941147 882335724 575735957 94416511 589584986 296848768 796866910 508784636 402693664 459170125 683394245 734469639 792877304 103097725 787064302 907133888 436016291 853480234 525002569 25788521 263991123 33791732 727390711 964583548 285118285 398351177 364261030 449114848 173564245 124550705 93117947 108438727 82411799 809907291 150906543 133630629 228171247 948446493 175961419 185728181 413228851 7999754 642451315 317089394 552476915 456676458 688208466 497182055 862128951 326524155 106310689 990211012 797303722 346898178 587181061 31652784 386911763 13296296 484867840 814704891 366471546 521626740 849430502 994668636 682454680 437376513 368881594 142292183 328063286 591602642 665154773 418620627 216478383 207425130 45938224 622345720 470197651 635792666 106979920 344370474 87408832 111034748 501455576 926437770 39718512 595429585 141661747 169696624 780468435 297688599 585333026 963719051 364028449 564587387 194497525 565127835 307635108 512464259 704580979 834459968 249979419 970838602 975059921 664235144 829162502 790130492 936970045 907746682 19279448 304580196 127921996 771262807 979738461 729014319 886463670 170736076 821406147 977367167 132202123 62894505 871465228 579419180 68335266 556263567 469493471 535854827 905962871 417251894 947525789 910850014 479749944 615739502 806176372 54528664 847860420 992387768 782247322 475398625 888353672 77141389 544550963 840175672 521497908 121987743 822585680 792210206 516176720 976553092 590783759 537736700 995698388 487525213 407974191 622113742 917563097 433038052 401147412 372381107 727895612 743848234 227423445 54284992 337240377 497594717 14632709 510017000 679176126 881163572 399646790 927250381 195300495 145114394 451018521 886852184 726829999 294682809 661859422 418340472 488022725 501852604 189927221 851948010 821493360 434188921 857452151 895222697 264924702 856209160 175016908 930103156 346387387 322792726 288573884 131046042 832981325 603131780 310160804 999421749 891956220 636731206 560788448 924719041 79681553 329898222 988101885 512646289 311518233 416209739 631528564 335764071 607049504 546934440 277173105 984366102 588040503 267293276 820237563 272744393 230351789 509962561 959839916 915575304 808281499 884352426 653953610 753581037 359383118 539417798 412016496 575792459 721704296 927298425 24038287 852586199 308492787 139410835 862568509 844652398 493318726 928364745 221816211 936850076 108945891 1113326 594602066 215045381 920389654 157379453 132351630 537652695 865828424 548274262 901884750 897329217 325980934 890091109 396237015 590066030 459943786 289277834 100115864 357478931 865723780 622951949 816225721 102427887 588325082 708562723 418246812 749029790 891529483 916765510 602281925 75450477 623633909 364000081 726524534 793366468 280028924 605060278 550532148 848893105 158752695 376977633 307234964 738972716 206965591 795880436 97905673 891688555 815250063 678149680 791341764 69017882 443985078 861326602 909784166 70698127 181694189 28391636 660328422 292690070 354577166 587407451 513918224 936164466 158083101 521100831 600963209 900324335 281366112 800265991 765156274 478045162 475972861 255160824 464023461 523095390 354734644 512582717 220034103 680152078 27411771 672067217 691279884 462420918 751706190 15061059 70622707 304250156 795457579 107421723 887827837 509701986 643298653 748138560 105457759 283487988 957388971 694120887 104479881 384316848 318570980 671869415 931536113 732074216 545276872 99527294 410118985 248566571 613750717 592985878 842369855 290416001 272263942 74311503 186521606 560892121 456771499 994767136 853626138 212882903 124280788 6420948 904919332 228615188 783908145 167685644 522188751 538547881 721365976 321983498 386155576 264176623 509584119 935634518 417068806 219169130 26288013 72890594 312580374 292171281 423041756 471648607 865597474 175036459 330416953 388195898 821893337 344386477 463811906 952778134 990587151 677690810 525358640 384408890 422878338 501595434 451111048 507469986 281624582 520900890 75814154 528963451 216843796 688042780 621691763 453427269 486471979 737695090 995864043 400295518 853571017 741242536 85404627 333883627 337681637 587077949 590363133 792385943 283518313 610255484 426290261 828993604 132951872 694476205 852116883 489337256 65839192 23830233 250538389 548200930 154848055 766502005 959780368 228919494 80818277 634466708 985126483 188290949 548026353 461051894 555929445 681331277 635607081 539626959 283188462 75231722 883663691 931036494 877530316 328963437 461451739 603506892 317723631 790813694 20063914 76463548 424864104 190505643 922785110 55494424 958056644 144394496 493582116 92562564 224658422 450186111 780065536 27583020 782565243 781552333 987900952 995117625 194617572 600005293 454868194 372972237 250350762 247083349 465290710 245265007 422022791 890420174 259125723 842304413 484094679 976800927 275543353 203349463 564242911 389249476 910569394 154464590 985699684 196981681 852230480 825899603 653421157 550156269 774269492 66583619 992151249 502828061 316171730 238100435 639038272 146006216 884087821 964065119 399605399 221134484 699782982 11376496 315323543 917894449 330961606 494889718 536966820 606658702 86784636 167552660 236698870 3891115 946729737 434306081 535686787 853067110 932139235 310487300 205396198 634909612 754278677 794871157 616674133 956049883 553473728 570165141 51283637 413156628 833757474 254005442 316526606 972681396 134090632 749555066 183231258 218699030 148515813 178218854 686211160 219441609 299113974 916242598 474972643 613340362 150535827 861410066 329489023 304551225 17796374 174345177 514648976 131842868 158278722 69891013 361019201 311559668 735214558 813581226 97929721 89418129 786709023 126661745 229331910 700705681 78349937 318268508 900216260 546634228 756215257 694085974 561383234 761373408 460064440 459397690 8293836 898663162 43831995 100619033 345148038 95784096 40991299 247274025 417308222 30264093 855149160 505307000 88239677 430018196 285335448 994965845 858149915 496475744 516659010 920997518 166235530 759619369 525954964 927597422 469226191 977461273 762033091 61094753 507866753 159567583 245464213 732704988 392582346 522604890 347849455 854251100 751001910 65101807 923465833 557075045 491283344 999655844 528984845 129412411 328544431 310483406 889371796 594633027 793657994 593380411 579318518 938967287 388067456 535645798 74081301 939783302 672724484 56410622 213708468 897938080 678085885 653714052 485285194 783940016 972876145 168744781 681592858 483244337 697551840 22599023 557316406 761757546 688178554 814244408 404331882 284862214 448024518 127863578 325183054 672596600 408537581 349704775 266159676 722987723 267891556 38193335 795068024 493514678 501709996 299018135 532558598 932899042 990458385 89626806 340054399 421338732 701454145 876370017 815508315 620885949 859179407 608321686 55899146 736400687 265441774 409367593 757485059 952766142 4000905 436732515 132388385 712299204 961679124 949357096 660714435 926870917 764080884 643899526 466853859 84311483 242724450 987521349 454262542 151295199 907564530 368448542 777359845 52443193 28535183 612392028 953275205 812481576 418296672 49713374 910067764 828914253 579009279 553468886 126530595 734689085 655066832 268205619 368457027 875998477 176016243 321732424 255087308 557576405 9348492 146315969 909083981 11155834 641598736 318422298 679565383 793416717 848481853 836404332 271821413 705074592 864485327 50880961 993427421 752767640 819228934 797262899 925754806 887110881 859489521 767781889 831951173 929718812 126178247 601091910 855548531 291163021 595994664 110718743 448352621 831445865 188283424 447738352 993045557 734537716 44450899 966745390 124065195 391012694 905979596 496340302 246323712 752746992 806336250 69018705 554158399 238142880 591980970 486888094 495594984 817361087 533744188 227996484 734457907 667225852 483731624 761639823 273097440 972421259 458580618 558919314 86628247 351267180 55545929 24948338 822600683 154168470 9441337 42283845 202759597 593150437 929039493 882677816 96077082 999478746 220476665 5986484 498312161 772171097 547028602 403937861 783870428 57409120 209713168 318317525 700013419 407765940 948730153 882289582 344941028 511205634 710210263 631989342 551804391 373279517 513479403 630483790 969929277 694634201 149541205 718135418 848778768 298393944 134866864 869550135 400688492 253588142 336224391 679477935 595276340 222616492 826637204 35489375 582141393 552712967 258470223 139067556 247452494 352457182 403185064 88777940 595972356 964072977 590583003 610607790 227779698 497264664 77295589 547262123 983092964 430673728 840841060 911581736 220819040 13455397 91085013 436767501 953903708 167209416 636431568 416023482 193121805 178436828 514074329 461661689 393549344 202865030 597152033 164806340 359803039 886004650 771660504 528149154 506114965 719575991 124622926 82434087 149425928 211520146 131849641 906036297 929076824 754930029 294559906 374508402 642825858 976651323 859341213 871623564 190783389 843893876 2399942 960015032 877668108 393649385 720503454 833590519 786077379 999787413 433754836 686712693 791748816 728817067 907529851 750628107 502770821 532017175 863351364 459419562 801787898 181321066 795760773 827221916 858005531 231124939 864640544 329782621 522527711 623474039 259384987 6854301 806927755 682005428 629845357 410111219 560158495 810632718 583736919 23570603 283573530 416555154 591733383 621256957 949404279 104038997 433906501 873301767 640705646 344579410 782401843 207610766 306434291 335413281 502543224 162883054 27378673 696412491 640078409 705712038 410359591 922208992 522230575 170044997 540168222 104219593 856153156 988232534 48904640 935376231 749848660 226919359 681253881 21668422 901314106 468425649 590250420 208485950 860201908 823388923 473054673 400670895 41991168 409262853 459322439 807661150 635107740 440538260 685490543 97812534 804095628 471005522 954052299 344974203 55571192 502979604 355402865 803207380 344987638 447620479 228331526 560386093 651165106 417323901 122347489 499717836 345046539 904973135 9789842 303559517 985254283 462441493 884686719 594372272 170769897 702918004 257935315 285570748 316972478 756133455 350628172 739392716 430289021 181221307 766963188 179059661 653058280 620873117 938302150 106268076 921288507 959409328 431477403 793538046 488720647 652124000 605992967 966961421 344093384 362999930 404339489 511937114 74757401 310737258 252083831 467615778 300211976 878990473 132413173 167678867 918048916 704955379 505774822 2945959 203734759 857894126 915255258 980453915 737485541 324455763 249331136 616261670 315256847 787022616 514440066 147008470 574656333 304752090 551573334 795027593 715228435 900113879 605858342 594366347 609933303 626966023 902532833 872121708 311423421 573985439 632355056 978026050 449609837 489052372 744630588 581821069 23524859 739182256 924129595 345591040 648978041 713224216 26308079 593275839 53542684 451125486 815391565 267110298 360482935 255377631 373115935 928094897 953939039 476234307 856619535 500586578 7390243 486261658 684589948 30136698 913439511 137846049 953281477 647791016 920289144 850220994 436414150 928201803 793840887 619797244 511158943 278446732 403085486 986648865 424778147 973795289 727724394 229417745 447458984 661708796 636858462 462547802 399619641 785032775 947129299 178027445 511683459 493573086 268529197 383035856 776319689 501153425 664084416 759975226 662211233 167208623 443033164 846059473 439732142 813525391 197586899 434103027 47270264 833499761 886159318 288250229 852772905 889605223 394161484 527305879 236120724 711154332 646096896 226318433 791546936 105109267 143654553 137802440 243242864 430716788 496434497 469994665 105719326 359474807 426050943 17071411 404608762 635823181 631356858 560947502 662140595 630400536 966014002 736890135 174289171 967880723 84389542 697399861 548494360 355820711 316816848 811933957 64056048 65443758 169300406 166436631 326786995 56226075 122780707 463375128 834959886 732495184 954831609 308969231 834082856 400980435 443295479 745641773 926556814 340720421 499052427 587483482 132381209 374862885 947839333 54428087 783033723 831206998 51142430 130874589 970070054 300488073 618401129 198692367 924209127 916615500 975001554 848309535 721837157 216416866 532895140 173551992 852640266 522631908 973364479 703972259 513012451 124404960 262082796 610428656 974890564 548688390 900596732 861541213 116037100 723951843 729948410 875852364 434384092 896614418 663506424 352455535 424867302 909900265 708201249 547490041 174193640 276079547 617349261 747980173 356839225 962939561 483807587 675756995 990075364 759051949 730202611 620174224 96673281 179546449 140339922 516865647 348700296 626732610 34231773 767380285 219002124 168995517 653442802 688588896 106439819 568161211 639783213 143485729 644333431 778191595 454844864 311770836 680370921 484900847 319172845 59981326 914084065 840280301 830837532 166304126 849237968 914903859 932702116 373308213 428254915 30124187 24469174 732217705 584767264 274537341 374569247 632766776 939432987 22918665 118693858 776342315 364002310 974815214 664858114 502932426 321366087 931571357 18080224 783026465 745765613 813438278 797504783 650312506 521560138 320504534 930342066 691214866 618138816 327414704 654272473 808494593 266624763 944748724 180578604 565338230 943267453 929714986 268992543 480304143 737253749 337191648 337847444 607645312 305253907 270234191 332266180 145611270 207868 87238697 153737448 313382617 675858603 778581829 371553705 788900370 73292119 145971904 601962542 257207751 655102422 811471576 267607061 115537080 383552567 844314177 837274732 695936948 598775936 14984642 583584399 489913903 857253197 123127642 569207288 346277325 702745792 712265741 882748418 90082392 708370768 257896763 975503395 532075871 905465426 102922152 75845409 455758629 794151617 928332851 923052065 790636086 133765154 549066209 349330443 382678867 594623693 632042989 988014879 129701470 21460887 26671467 501264187 827381496 273765668 733635627 498035829 892365486 825114752 578429806 26214957 839788341 886386685 578492527 414030428 246718920 534547138 689433153 610219851 920861030 107669439 941994236 548102461 188494980 538520817 823013892 838642558 643537771 88236730 629431941 502633739 825388155 59328888 234372772 870450545 491048553 580296470 751768790 188252123 376076997 751021480 297400793 484680589 55955913 112706802 565928271 427177107 355266593 540323558 382595238 773726720 469004300 365179403 744255806 51102855 833002113 92068740 177207079 348421733 463218016 864911383 581561189 270840898 390984070 169240738 763992980 347043953 886610737 137754555 535189591 254213745 820327982 242423476 622359190 984870571 531140435 983143514 852904189 345875837 734229555 630676736 638997420 339054491 758125411 878996569 503318517 55582633 177016662 343585115 832536505 226345908 516824779 826279913 926919549 253871625 971806549 202710314 675129846 431731811 312100104 402614932 575683771 775419381 371286470 310706607 269004027 876291600 454179774 552009803 413777127 585482261 610589268 752083573 853617652 837120452 349633721 281447557 448911987 841422956 833133083 133201242 190897166 869125735 125470625 657683036 544004765 146985887 831114220 920726549 373333464 668363628 631911158 804104874 9823640 569027592 909095018 720006673 603386918 347069521 258615262 736433904 78228740 708745506 224445524 284526264 628792496 587720003 669168773 212321477 710357040 252777319 846379757 105071014 535474760 607607409 249726784 341861220 970367489 480393092 113271816 180139971 293758726 965447738 713473026 130997178 605635506 938460519 543864649 711959711 114470207 515741543 979377184 863075036 147839954 125054409 330244719 332111527 381685588 229863286 234607270 547763463 290628877 826180653 698735018 783134466 768483315 472765734 587373754 297541352 862646861 396044044 715197594 995202319 462644041 993207506 599931869 667556347 442086932 88946154 950591660 819592719 493677433 478222874 58136203 102183379 34313455 509680696 424320118 605637024 75818370 180407405 881717608 662123632 937937317 310576756 124786698 441954968 523254510 829224677 335657782 651592410 875032338 954387725 39292529 695156048 965299468 510764339 858274713 587497942 88080380 30725229 851874617 753685478 687077503 389299830 251389870 476851461 595527438 310285114 236264232 966044139 239624633 212278657 722538484 868807282 229398417 233413396 422893778 880896187 995723756 906135069 973988283 908596828 660560618 109041262 636429394 847905836 220685625 205727990 132519124 54764298 64451336 617999318 326939761 550678889 341041756 853027819 493401511 846096661 280463950 387395873 531594595 165450806 239624666 211402550 176495522 76373737 398182272 280401840 962415616 93224026 228889703 935108729 865423975 149307117 473973922 133354769 871426939 117225861 741238039 717795616 47941055 366030912 971857252 289577399 55113402 266162404 723740687 682609573 820998656 790238103 266758496 29269083 169431247 513608038 632173579 29511588 970943043 866282231 847481827 958134891 64485003 11480703 868982070 290761114 344856943 491807367 827244539 115275067 17442658 210828065 600380497 407380280 553834027 101778447 9922382 953953373 548436759 639319411 235634097 747832088 5126517 720018163 549814410 336366727 344120803 227684992 786090953 888018061 825600308 977484642 79681353 96215385 419122395 53991984 418833176 395777072 214374002 659141780 589793487 196928248 710392512 571452194 86826011 10290394 503894041 791349694 469339732 197033128 304910152 725296643 281883450 423560987 351807054 571789342 490317052 148443935 274450663 682885172 538857682 376377081 759017899 477544306 396920478 699180582 124536877 181643900 652917021 521239767 710646271 483618618 253977369 518272469 839823581 576016805 275384064 723711010 734216864 749084637 226514334 264401484 427201421 743147280 769429126 621025339 264856064 612212681 742383924 16746044 368134737 797692469 999801587 862166908 252623238 737433228 106873289 986647880 422436126 69364076 720154091 643451027 955566361 186292842 667048444 638525179 540640444 373126118 762495219 857507279 603053559 358755538 682513534 75996572 555946616 930060935 277689394 604226470 755960800 869764545 455594383 508439034 383651728 726180592 2150958 213846603 351682216 624110280 908089167 229743659 47731738 337074181 140929868 37197493 691490104 337886195 637363372 906901083 615052788 374979091 548028731 523097171 607038417 182447507 678700003 447171722 523200152 405237053 628411122 728955300 12357016 829417588 475719256 397237950 422464266 227736930 775831368 474790418 226119179 901648971 769192504 599054485 503130721 75907225 666812289 514507184 47177056 692583983 816054240 587403286 548650235 704717218 586385986 450138451 205469516 680704489 845974827 465253357 276696648 899801104 834751489 626906790 908712842 893206059 798386296 16058394 938017215 969822517 184332577 958110283 194491445 22879879 871516593 183232942 468745508 68461158 125890340 763406006 106219399 601696354 502254001 717756513 641948039 951251756 816841443 617304713 574560014 388089297 43976916 607873005 964063165 160208831 544510807 980909469 220553404 694832060 382732963 98215843 363221857 689910335 557802628 47999733 832997663 161239214 954486232 887205929 131014918 820960199 442098605 974616689 364061142 389008470 302280275 22022873 690696972 97529844 468776485 965266119 676857326 854820770 986139093 541687092 455909628 630941115 968090719 790098194 165960041 522180713 807857033 787008385 51411111 535623904 209120782 865449238 315188219 567925475 159827842 317214611 490015295 212829520 313442319 634580048 606140732 628734180 262867833 797459148 107465775 576293767 188090939 318702172 499546694 884174981 73941720 933655912 370071938 818526847 505065990 926133128 656868427 356759382 723012012 564275081 698320125 151922341 979076324 303051781 122603357 967115781 647498953 543844448 175650736 833103298 849803639 873264641 474731291 623137314 601712828 15635316 960600985 822291991 366134191 414709102 580130865 24616832 241246931 666944938 492356837 371099692 216646159 452946593 319283696 26704502 973524803 934508231 253660002 876155140 24196005 625742640 641087648 442499086 712248024 151296057 18786236 895753423 535867922 696969038 279892856 401788465 430934782 595638710 682142555 252886949 869730995 385628324 334804338 625635160 927481923 272593363 439696343 603289559 769026201 162638561 62201589 231032195 795637352 282007994 856182197 140550604 294808590 581488636 180294756 939537920 813732659 382997513 55245682 347602968 17256758 663587848 952883488 152979293 549807032 232406087 789249536 771618536 152277636 153571236 596426253 405413072 392775527 325446083 168519674 61586412 532711350 506799765 208606588 590223288 7271532 422023657 909649580 870949994 111926413 538883376 491663627 121098506 984117176 798552608 41750273 611146585 621502923 463252365 44010571 176462684 550832660 454020602 284626422 58287061 267187248 209358563 447567061 743706934 710420091 857172460 568970419 559374765 594936767 577826426 290405021 744844711 760475608 69633174 37820284 121180651 903849767 782756267 930273694 472050030 18016992 20513703 224781312 754171664 344476945 59822623 332989869 637849261 477858730 818058610 876459864 447774295 881428081 688227158 993067230 871081233 127586935 460012268 2479884 341032634 878243102 294081118 803748069 968835467 574575636 341252067 119140552 878814145 378929984 526624401 91249176 152398570 689906389 112979361 580788914 901852088 829486214 425975376 674687160 9786298 207015020 66650913 785711190 548916211 875469480 196140517 255217255 21326495 114901375 650717570 663027404 146383055 706829647 264404890 48087662 213928782 382360709 521058468 549764305 343417052 862220298 234767051 321815784 489823326 672231427 882928982 506390375 422783886 641874491 409856603 44242720 790118485 333540390 326754670 319528515 244640819 17537678 700683865 467437833 808766567 221077108 445240064 604822919 881026116 206745956 756418820 930725784 149836656 133513201 656105987 483274561 426535709 203911457 604987986 272758327 704950530 945254243 950831647 901647475 829453533 168399212 235753222 414028692 925950819 322448332 424174494 154923136 83848579 90706726 666414021 219691685 476343558 496832781 382836919 575484541 37209674 195953558 10112797 122493399 620577275 229214787 592110613 402721324 418164690 439848951 340374725 420846524 179661942 214726440 251591999 535590514 611039794 319813530 53473787 78780517 798073235 649501594 518240014 588452580 787688159 848274896 491649830 100385951 653391393 557603686 539607166 981777390 758380521 61101926 300824235 385914216 331690775 740351711 249627644 913735147 353341114 567265637 225751851 96907253 447373831 424538100 832684836 208140987 561162567 732001671 139579769 140004587 347452008 316845316 74678065 592431036 303200082 980580811 423903434 539435555 493910216 189561403 193201493 561967687 570622184 787143319 593804029 199809140 380156545 222856442 510161261 124843310 815947142 795339815 593778010 608573125 79661678 860661618 779567285 926963509 800396451 79706186 112778716 111098699 21507670 648110355 677861190 383688628 582203695 270843295 321087108 389360207 278462689 418624093 375973781 904107475 458085553 167802731 246776981 1019007 76464013 432410387 169503014 31817914 605519934 573649534 110758967 591510229 605390222 543204816 238029223 123416072 919371609 586765010 687355371 200714205 551620047 220498249 702138160 688976838 255751392 964062506 368542002 839405759 417611074 704444265 882488027 865311383 836041646 878163958 678961006 456648356 892049212 533409156 883928447 679046357 24762969 891534892 74522338 95737133 815992027 385556485 813865710 36483715 352767182 248437265 302433241 899399836 757818446 933970771 443254473 483990914 923233387 438653461 599981599 880620454 927856239 202201570 924643072 287676505 510787877 462190462 639308992 201975458 457090176 42217949 689928003 370014172 393118477 706038138 512231583 291023722 695591661 43858580 803397309 965633400 45219255 939102123 516774014 618365521 17659812 980857207 838577915 856868062 542243072 24829336 972952460 680349326 54631890 589522399 205491447 203604644 893946994 853906191 974171435 220100840 898227195 331125746 711533104 411068032 920033077 777502805 38059521 41874899 699076041 721327625 129567037 20746351 528637984 128781712 263040079 815392382 301375902 90159365 818729038 324029533 437267336 155233419 393786012 658761741 507616470 53091370 882959082 141217505 538787751 952077827 796452482 488364444 862148977 636245766 199895127 40887698 714378783 593242783 660597568 945566228 239166232 578030270 272986342 431677449 882510742 27405968 310877527 266388462 164721679 317546826 291411446 260015528 581305982 295394085 469366800 517900689 290192442 143573728 157066768 66630915 806603117 186219421 20885737 102967001 686267408 921784234 773735395 525194978 142388749 794246233 572634981 436013361 818793946 416305329 297652943 315606418 463483920 431708135 866161026 510797510 191790347 241886314 885451442 572035141 705050921 188755654 723151108 487782000 922893879 850411325 766630287 487902979 392662533 472939280 419082336 646079682 946405422 823676360 454182085 764515693 494736897 576884815 236707906 770481173 473717366 157787548 344144051 578843226 559668285 54109678 436359717 708280354 877262480 128686350 466520529 391718141 648264745 686304653 309017982 100808350 253258049 127968807 779637648 978521128 956134151 671953259 580926108 506478002 910183239 413345095 296937180 576573681 668235016 419449633 352606490 89055286 483364894 80795858 615773732 204666450 377502476 809685654 940648658 72270564 167509437 303247298 894082216 227369065 228445127 594176377 43209470 675702357 430571709 359977167 433563539 683513811 874926374 489828134 503106355 945327164 834441520 503156232 833272921 505323134 564251495 29671350 305396155 731298875 14045899 192449842 128970355 566037709 924841556 704987763 769440812 638580353 147400876 71202336 721847606 683344472 364849919 942683212 134790594 455522662 311529810 65709276 410635305 878938314 803672915 431237936 38445143 51972669 292331478 916360856 347624874 16071027 145372606 468319544 767732206 320742190 797077 228464739 365889793 207179634 662882338 204487628 95261830 205513682 667568810 925003346 583528973 853536307 542530284 435916432 965656905 560064318 52818234 604701975 791542798