50 100 122172789 883939761 637112919 199200013 715715150 520003119 666389572 495812910 274005345 361204744 272972440 45588072 552787076 675432841 358850383 66666997 351553766 870923907 458659608 711326357 416651418 696364562 399925362 338409919 393556361 733390536 402291999 174902800 568891629 338934196 877786434 386463350 200356509 602086947 589882698 257443913 744877375 167755824 624484200 31457285 474414943 487862200 102406808 471416929 733963787 56803267 392992681 641866704 145395675 757404596 779086404 674284676 385185913 617659481 102810474 382475210 329133800 638424195 247796941 386674391 330787210 786623402 923777781 202329177 762312715 83614935 859594041 936565310 725622065 633641313 495906269 851750348 453263943 292438991 222514267 716477338 849427384 377632249 614736614 845668756 124767464 308000216 22404384 930021459 235603009 715736305 624605061 518133890 903758308 112526087 641883639 401865356 711841776 317955115 782625284 416829890 625382520 950327654 591938173 322410726 100 742097902 215900845 810647947 842326797 321362567 243208628 848473009 417607963 926040138 716890839 902118692 168570781 172694289 49416473 409841467 871643761 494135152 16848675 367651352 330264017 408403285 387902420 663067991 6606757 970453197 404549092 598889651 538312880 964104368 513512489 647339255 475095174 615678628 253960164 94761541 134170872 834286738 488361345 345070309 419748994 541907091 957171951 45725301 612235720 523190753 822624993 945628917 852011716 359782339 776219220 689788996 488704068 508133949 248543440 472989271 742451034 429698293 994808078 808353749 317103393 989276958 452181699 160866450 715136592 291663084 32473243 600514974 145810523 622255631 265815841 633054254 899927473 219349845 295881330 59155534 415122926 261225856 756817926 800432139 826946178 441867393 120014126 832338564 427748142 514522684 260126857 491463676 832358993 827059370 931202640 848002628 557421675 642475786 958954610 962560587 829852062 130179888 759053725 68431396 334995918 100 750794330 536434713 237564283 844707197 511006436 850262936 118713964 568039341 287876874 476079350 417321786 682773297 735410856 916547799 955345382 115697421 854342554 49400670 508511714 774090841 26302560 225931164 430199712 113045219 284703480 648885272 732395433 233644019 83785600 525796134 363966617 24342102 342671025 276142370 198032911 827436203 983246602 145102171 17644357 208871345 561004373 819074500 337782645 356306342 629907297 626453490 174434269 407335013 732576641 258874972 361821548 654181427 792191173 844580742 970418046 562096585 880285288 320638765 509075162 882043469 241896515 377848493 373437113 610877222 287586958 372892198 110613868 800750697 248638546 357867832 925375661 530378590 417077839 940818735 153549749 792806984 571478286 100862109 659536457 358128772 671766221 668129336 722003137 515001683 378543809 323531998 338666675 750976763 634780000 51184083 304311877 932902886 686824857 452864013 61108716 197249215 736258729 131672133 540283995 336374509 100 368524077 298691322 193990179 571316108 316973568 842317701 795698009 228759258 340074163 908113332 871302120 631116507 23977176 562643242 83773360 792560879 753236485 790461274 897344460 74166738 907593431 693834226 997770305 580883491 991898610 526337358 688270047 361568317 240803413 496762918 370225170 999279335 958593713 55439937 803621609 905440788 358510649 850594741 394963458 739708250 281952060 981716425 55899179 881450396 329816410 751068806 139758872 945513402 233371213 167878228 588754462 282898465 559446435 875824307 820048831 414515378 135021228 853501170 886964928 917104857 193643520 497289838 500935411 602115658 417909169 446345105 31493718 334728455 715264654 574195634 590752632 861434049 555714267 839855935 167270103 878392451 612919982 727756931 814936107 625098148 312771637 520145659 756122231 260988154 86189886 73603729 655630074 847521558 272172478 908779810 898063934 509510399 533328752 828949382 397122897 442489044 263883377 216469683 16815927 148963003 100 361261530 792537166 641940822 379137079 642364764 977514149 277798484 635497887 318671290 413207998 11645766 684427411 542658203 280787540 459852839 254105401 883147543 736107561 254311451 72712613 870698508 766338213 982143567 821853311 823736933 855721668 779823237 651789791 768331703 392424580 551790725 565382058 211034428 102930616 883161881 376393452 119517866 933724245 478925310 703931553 880695300 361134199 703493483 428158060 530371631 5456556 787610741 776381859 406190054 897227383 462258043 905396483 26530784 701015474 736503207 451658420 979605571 861836739 174322998 683530838 178627551 779126307 356641445 436338535 55482608 618835902 254428868 698501663 12662669 863165535 856871628 146006511 430880548 983388127 124917505 349556345 952859621 152524719 110103363 408284068 708410860 588399876 714542188 834932097 715543585 687382421 179360973 951896596 515409700 782045950 345105117 888875388 717689429 481372351 741123752 176482456 958119118 310557003 954598228 468622514 100 537602232 802249109 789423774 59890229 318410966 250287019 424974968 811404021 880234807 584110367 742447010 88015748 20734792 776217285 762347143 765274349 110626685 682251055 688859846 370292321 192269154 373628065 60040926 77012699 736550299 93742720 478538213 205214775 186659655 289736146 317235474 538298875 853689758 572443500 713431577 644116957 978988492 495706956 822998467 779219634 251568793 641402651 516525713 269778371 438172498 180616058 779984951 358100592 67759554 883688323 291184346 800017151 636448417 278189164 49322339 157477313 518607776 514240620 430568120 550659877 831749034 430582463 758998173 440982804 820645791 7949464 72886991 878975543 719626368 984546232 252816687 778399252 610495489 265592512 207274457 452297730 891835545 243825975 482239473 306125246 336429618 35887795 925754843 419753547 944339527 905048572 907301466 703729479 487787038 988627430 543616608 779188232 716466811 836277921 933785051 56967828 908843669 822014409 28369238 448330043 100 974717607 438690441 172479724 136234902 25016220 143005409 234390241 438549608 568042387 622400443 777906252 144607451 525311859 740178930 573273332 734780156 727689452 499367534 83532846 888559729 693592298 592019801 342338616 398157349 455536215 946580093 264403011 618435526 841527235 691636734 944168617 901182719 466946555 943485932 901757749 406788838 8778056 953474789 282296735 239194260 797802525 831073085 530978359 377212278 450858755 318376100 722720455 631128320 861294731 214948785 90479789 351865413 301905071 135535866 457717455 781000658 557746202 958541297 892749081 150013956 33182560 664672884 935715849 884197571 961726208 719530186 451986124 280326978 662210755 341036918 322972168 175173255 923807963 910002195 724611391 193733665 993492998 259726888 385661541 486668709 159442410 514980601 415713197 986538611 796150035 189331867 850974486 637852965 300174936 433707490 936107409 523630646 511963876 522628599 134462046 483667483 361090028 252489978 611814786 994584211 100 990449507 99531232 172940928 507571254 377077177 763868950 909019655 799919190 337732127 972538829 829903521 813077063 481731153 822191674 340397374 983612194 790864378 149570696 52344850 97365619 366195381 150761392 504996256 399263574 954552064 46600063 436294982 256631135 41201947 19757012 653436911 196405095 7080548 840331112 794485070 585198918 443291035 756948097 495262528 180447942 571107602 144562907 780160930 534912427 420352352 797428446 737473483 252566858 879039438 992914677 461845714 939805998 776437267 123822384 911704507 734133143 521676168 519376389 516592716 576898849 443815195 259274475 185003404 984775156 977064781 504963077 550263404 223493622 448407797 18412381 784267810 959028125 393736003 23952112 659828799 958406762 410109079 965332621 511590762 652316749 634049835 157333026 515178156 941649706 131088100 746738813 196201221 664135056 684884444 947309373 281784650 266292993 918870448 382651449 703164126 59958633 155459573 226057269 505216873 607735609 100 917114001 164806942 848020512 497632651 923595108 679033713 167626771 268876866 330774603 194698113 872154052 966029575 504397692 286006859 427977839 463636222 363925386 261743401 160035847 744562155 991427534 605707213 206800889 827326870 17727180 228866842 91203534 533644204 196612240 27560155 429469696 764750745 137107557 137029478 818916481 344221867 312587505 995977935 582043231 332887479 74922565 118686242 170992243 518006316 828150073 260806424 344368359 592361176 344917645 34573555 714525859 148519634 497490936 320658149 88658652 358140249 945216671 630676580 109718019 58572180 304087101 643353121 649359855 694757300 936791792 518837936 528896022 134197455 669836390 127158285 797719361 956974511 110723615 386695602 477807372 406203699 538018806 359145525 291861761 279685430 873154558 690739263 582389801 700495089 542287414 668316522 352273534 653211903 1742270 319413056 963102026 3899208 417378304 27710446 767976539 610215605 327687480 144617957 335252146 802237334 100 68889661 439930116 695212602 879613812 517421928 311787923 289336640 195118795 370502975 883542148 707669453 588028491 434301233 771058744 816605119 517886909 586717388 764700941 752519790 473028286 572784831 623360820 391038684 423227069 922030283 233942203 337150438 208973982 673248857 420974836 736563974 52762780 155503350 751411994 736209400 940316429 405639556 924088858 56272730 860570339 169615078 728267582 90044298 914816463 53792501 680269015 88471044 748054254 234830977 886017722 311320440 610436030 881728364 966076232 407401987 613096111 139422702 790090550 714785609 117273597 225110375 14826259 971423671 202889691 64087264 979016627 960437665 530019761 693260017 976991204 661768575 681284297 343328885 674383144 215886339 651469443 375338595 703910989 384895557 746490184 110988561 960883783 545870523 227241342 129655525 181158489 426953248 716440387 370005777 183969240 686469014 189335873 877491822 995672989 311775199 912266496 948076767 230579212 451622578 92970734 100 879717583 338396428 638931726 168565259 159223474 175173945 780613120 444333693 591994780 550882792 210867919 607075892 765857587 474076380 306257595 828403691 79810414 556606620 35433366 643904050 822420094 742415874 784278416 334532060 782072760 703009762 507681391 507182973 858274910 742963054 305918150 617404514 882974076 9632430 460978354 715002382 160655345 806551611 408016266 880519491 382072795 317598954 805207461 232774204 170618696 969824752 874887497 772428878 966488685 893137677 233117902 795333548 539925485 147585403 259493964 528944677 157878799 778494439 855977218 235888417 392131984 258229599 318280867 652278282 290394958 602388386 196818651 98494128 984616318 637726386 25760711 190683706 988879600 788829211 694529429 651236645 17611656 693767269 3695985 530890303 574136834 939829095 769541983 885938163 135213827 754070825 528297861 473539098 32875689 44013123 300364089 565614118 39214866 159062772 690280287 288705606 500788830 544346587 244297270 749070675 100 739029031 991526067 276263348 356345690 379327316 666828987 922096621 208974846 966372111 833640013 693938238 159507932 909685766 940368103 289284712 74377136 981634856 302886938 550922040 546603409 146712288 222482738 88986581 976227486 769463593 39496782 775546125 99636236 91910 782096038 615959005 462799682 311716031 956567393 253476455 644808328 611509793 449664228 980462158 147357660 700077729 69979967 215163695 598066603 770855971 528635967 991064790 657382401 126277257 418451327 992249747 366961355 539002021 431257181 503150847 799653614 113029155 880768705 657488003 117589371 924264601 453144984 755849868 674582748 813732686 518421390 222597285 805394982 825551546 161122971 193874720 379739977 518731358 73481696 460379262 622556530 787016665 103458344 466865093 991713408 669951671 731568029 352778967 177535270 597415348 338019594 10885136 732646232 316830299 769192860 235854108 70099283 842118422 172429592 971435089 858402573 996224240 913488783 679617089 420478348 100 451705473 286779757 375398362 517367975 160936399 95819650 416333819 168166231 21556564 548503882 453158500 322370360 141051114 456119506 190220636 469732429 53416331 37567862 154312439 817016774 952335776 665420176 287924773 403588171 7654627 944809536 645212984 639887272 14519641 621487867 110048447 564708359 910701653 34475613 77947695 114299024 6833530 46389324 751942681 187234816 746220158 530975898 226756728 573342078 519327128 235950479 631257611 644536962 506744918 733075658 670048265 623527595 912990672 11723623 644743903 730755545 906469820 213137176 847057524 284809300 792051705 50621501 136143757 227605327 15625730 136562479 301372578 891351299 283063535 717197520 917026022 400170656 964798051 736050067 259972858 25899383 714098568 802591515 13431880 773480373 557537925 732241978 229423586 611195165 265727012 183780592 594279675 96994659 99949207 501078715 48900360 93954708 841205411 319492177 326608962 134979254 739722971 737670919 262999138 250961541 100 913168760 761055233 473121553 800737780 699021609 354629587 94109003 641479250 967144847 93877454 513706156 331897759 605027205 592031109 120313129 67853986 305708478 419917008 505766666 495302580 930418088 683180156 399799415 88061444 778145696 767374723 217443808 143280215 612150412 299967294 613782568 176616823 699322285 176900880 721995807 615511714 627746866 604266729 796162688 223011664 372581701 108012493 708480404 470924226 422574847 295689734 773593721 286440763 331646034 991099533 313598041 191395572 635243344 948627987 971131005 305138363 223409736 268107576 64697094 417065870 275862374 440330121 201311831 243653303 955640934 953834821 801683863 173966186 929677242 821792366 849033888 940036620 196096961 859574921 815388988 577878102 573151147 395315509 546628131 379319010 660370588 744741265 554983514 723690837 886905329 256425564 419079311 453630097 804571940 108554479 93190277 807066045 478202811 907495947 496749425 278263888 442447637 218571675 31364508 333723639 100 160375110 658728272 582641084 886362759 29385339 787168356 299996287 955909805 990341510 253645187 490018934 32801806 278927134 269851971 603703034 956410236 672852849 444804788 172479350 644135438 585366918 785020887 503690220 746547463 870041246 549517095 883740939 335661786 749523486 484845081 720646445 317096557 515244366 118731349 943340739 443012520 188864247 556760275 795678391 439896348 745743166 611512685 722413107 41053941 704043 695061992 752843914 855920121 305688639 49072117 134948073 999566721 720601162 556174230 802830938 108275271 246286823 171129931 968639838 516133457 586787303 854804075 752793793 458643154 186307064 184356799 536838369 958633935 120454753 635487272 152899431 964265438 493002719 8997423 272148301 576767579 198603131 501801203 118704417 418006270 14702833 921439189 660168989 699012320 823435644 31263705 397218828 584344471 561565836 569077007 361451569 396109002 963512963 833946978 480741367 67002143 445701064 160658455 772974227 517663098 100 116391459 93478208 392625767 556190439 983206177 388044872 246181574 752119957 606374545 655981751 665153868 584799260 685692268 690568404 918030513 399081317 943313378 675220178 195407595 404558205 916155357 188112236 838023821 607916103 525140826 605091849 557954917 317906120 442503990 558513251 316682150 761452913 344754167 925695748 295624592 372107715 232324398 876951426 568400163 257359613 800416926 144023856 657105924 124902768 244216173 642106015 135811252 701320705 114968643 330165262 473620796 562817437 855292468 930263339 808547399 45347926 973255412 425587416 506567010 112784559 689489200 887122083 603995729 410197393 482960851 701164420 756151769 537693064 114144580 802182494 410111127 271992160 748655378 329202402 330763228 52091776 699099306 360475225 791607646 696928158 193500969 493587220 917924419 804834971 441943742 148305576 390531312 957354925 203646689 51843690 935869877 348858179 742174618 801401440 133984957 923536694 395822286 435409967 974750119 733308485 100 149744659 67818599 159711817 184480870 224085633 666502386 927599005 244145422 257268046 579455438 996997736 19499416 239892969 999326792 324621209 137667870 841747900 983182284 937417486 22631093 207760651 127142965 126503977 574188362 614631747 697508706 431310201 186289686 931849330 583307125 450070693 428173363 702311382 499288099 980895464 235852275 848662487 42306803 290385016 548295349 545607921 220195679 847379561 509834924 193690971 228363939 482192883 989668783 378865956 406470736 515637654 524492139 489530570 628566276 815850321 837441765 807623711 445974032 836726440 581387726 130535172 84200553 571142574 79292804 935485079 674702651 310973459 245209326 361168676 284507331 263683589 407705715 883394206 640135831 402370754 616542368 652534360 226783119 9602602 963120252 931382565 262074698 259687340 363948583 493120642 788609256 484197238 397565332 446650894 900237737 775923546 453869637 226874571 867752762 804626237 713916612 545590463 785253287 47386137 151948153 100 353336453 73061957 75904099 20726754 243956981 946779344 707052998 40657445 205053104 818143845 674579155 262535849 659271623 193762778 319640264 250745307 789300534 929437515 588173797 102858859 462251792 571329553 821454340 277643763 961269871 372534215 349772630 977957397 51940145 115037322 450497853 505443926 157849276 309425294 351684641 309114124 641942266 891068943 66981212 580023679 601881671 395608174 208947933 112459737 442528622 405751109 362151883 638655459 984050602 267121602 495283290 366803757 597453177 423315999 518775404 262576726 446596514 154805744 471286524 229238564 950102801 644949331 589105976 692393030 184348497 57413852 75612456 749347120 824155205 301547726 722946023 901215032 143109694 993078680 334949773 834724582 106140536 568590210 73846778 536038898 647745482 861984921 133568786 867602388 232432367 199906340 208192028 687618193 987597829 303495693 903148140 239309293 897438783 19127646 800510254 557030029 381114755 133228205 365393657 127295336 100 936089226 111930560 4819269 415551495 439946910 703011088 52960380 824645112 437437755 599080664 477373671 145242977 654366309 172127489 235258721 426177011 282433104 293690325 22256199 902791760 586410971 837233314 78688863 304224826 280214218 208511928 674684064 873521367 729389036 790774900 739908213 987258694 692781650 974501304 359788453 310349818 348383435 831612841 680448139 231647320 711081693 770390484 452014974 687499010 716480132 214146385 459643013 185732592 67140410 896777426 234514976 898173069 550738114 111248091 577032734 666625502 87964879 27274594 680157109 480350443 509810018 386786478 16851613 22497019 349261146 535495224 549095431 937164007 160652006 28059363 294821296 75556121 540797945 371220508 67393108 881018751 41108658 301040665 991800295 669536235 162647675 854917027 194496914 847182390 399805431 53183846 620310258 657553396 7927398 644295104 21983542 106401167 685926981 368498288 663209251 405052068 888047366 631173515 293813048 488475643 100 821183555 288799047 4494304 167109276 312119913 603579528 454221307 713518672 282568300 673418966 409866246 566638601 822966618 921272447 634583036 551557706 315617010 241914740 531052386 384176630 596622710 935880227 91625118 730705802 410330174 402356481 604217600 4228731 6327659 131940486 642066038 7715985 960681646 621438762 418946370 285055121 15586342 939916021 839619952 283370516 965379734 422882865 674310645 843678928 898714443 380503771 788704528 709045656 382655619 433367104 465914960 952264442 325416177 609612246 418828046 514933404 650373189 325085915 413432691 73179396 400986577 47441447 347914078 951696939 169114781 68290136 632183631 327155326 961820081 304402150 863903509 618171779 746280576 552897061 814687599 335648520 712064912 588396688 631073203 937626892 481969132 506352929 220400963 74887046 575738861 514242767 512205901 383870411 534277244 746943634 337363367 237281526 196347116 509515730 732892435 175919123 965066050 624629385 318494434 655895373 100 579287352 195102069 725506964 631125673 782633167 147654858 675117512 579522440 396634881 467901338 814151592 810323560 436103263 191603159 681064894 972844882 874606190 699534042 443822307 818695716 27056720 141958091 443070577 206335467 386695698 426718494 822587169 190864079 138533687 673439964 452430617 211657688 367417965 197727053 482891670 130620633 359339045 951614664 443519943 826192276 209905034 375457139 949592135 933184920 614320768 763974870 42855076 700973980 313326366 859944558 468107747 379997741 374484413 41344015 574685576 149969127 541566309 614381244 532367325 239428817 757839694 486933842 223068661 666218185 751561375 589190009 559954676 422065565 269024809 48345460 563263537 642969662 786137481 575489261 403604302 439636159 869047207 999890287 942562608 98623508 476099301 158531288 402594494 39947121 804546031 989497117 807406117 949993864 255763031 990808455 249318053 583981686 342674157 495797920 335741204 336637362 71170993 834029669 170450408 844413276 100 769778314 264121019 906101260 462179021 29180258 167285424 103739104 921929970 444897607 577520567 91030539 578540046 226285218 400587013 919826053 245710838 912804770 927286419 172729242 84456461 227823947 222485478 576343626 719609097 879149265 371192157 34686303 374449897 607409679 427211274 137337004 430798131 68280273 73651985 295617602 261262633 632876262 203105584 382679494 505562633 149188162 211947925 822630526 788096952 697264657 81248960 137095641 322657744 179863570 900375823 967358864 444686279 973672221 281706131 744769010 567717290 520334736 126877705 231397534 110691106 115236854 578867951 597816975 598744575 640496607 476600001 315780824 863068505 897307271 460863992 513276678 571812112 114350724 39267695 179317386 688587168 256956485 227752903 375608339 444497210 795483780 193476995 671898245 605874304 311621000 295848610 937962920 958137891 657034877 223524724 726774092 762148283 277503760 75552818 614135369 292850088 402583316 808906596 86222213 811165579 100 561568047 871924207 779843598 42818399 450380923 31728962 536192752 50586485 110733689 781462334 684242728 888398598 603934331 288304377 33400794 735344800 726844187 57080582 27227261 723146200 224536699 776774893 817322392 950064658 130503061 510367192 509839239 15135594 302776913 212990048 78299139 485729957 314736551 816755362 926448049 143597108 67804039 287577681 959581050 598278686 849124321 477906320 18450421 315987638 437166491 926026477 894365859 543767559 389754618 676317218 108287770 909809004 286344173 310740745 468432995 263724445 750065121 879076408 404480078 159138857 679489079 561564662 872350242 734213128 146587804 154063185 22586247 948036204 184435678 383556888 364715297 408853653 695196735 964662254 952064037 408095291 857459375 257505286 330068061 734536918 977569697 664996642 978627604 218270862 353904712 714221880 502336124 737098981 402573750 897106454 538167731 834666958 189750194 15487075 792755359 151588336 926324887 419877459 745508219 819683926 100 306915276 221948368 765088104 798888946 30798989 345291206 462745424 379434821 568459395 380685263 365796221 200412912 7852444 751816847 958976619 339284548 114407736 420879115 80547735 783476131 82171816 184957934 566403671 276491052 24895161 747901357 618760814 2047306 87906701 658959644 178874588 21387638 508709360 923406913 70500622 472719628 555319079 281253417 476399489 937454778 538346757 90432431 861682063 686442943 787169725 244722286 55291418 392835804 623699020 415076455 304487823 379720701 90651911 722121055 717103139 399732114 440396772 422401684 549505316 319774228 301173702 73937697 153882621 151644746 889161035 998895445 567040050 110480805 532430910 734377240 78086645 90560875 328406113 710008816 26907166 396690935 101538625 314225465 31179330 68875874 97639935 376903838 783259092 134359143 62800465 794385476 233969634 938331154 211798843 654836665 594286320 532344602 14687840 841793957 492331885 91313415 444114819 394742045 357715331 998747473 100 334361865 305762145 652823563 893643770 649104667 257219795 355396832 951031382 98856172 664519765 536494820 646685323 863727327 802872517 470325484 709658228 925519975 145688620 243146408 984060921 567097859 552238087 391751331 440724741 670015410 333455528 658651674 16534845 676660539 331334245 192727886 96469929 913173324 609684319 622092632 20547418 126246845 163161604 390362748 712364919 666314859 699774597 920141340 610354357 839940399 34129982 795124924 30234822 685741287 688858015 176943850 472891227 487689604 605590421 434961814 719037013 650631726 876704657 132588307 964999854 181093749 482380487 745934749 282943055 972637120 104116127 422831519 795067565 885846683 586374008 494091532 518320374 461512118 497008107 652330646 155492730 563764733 490841854 857073727 65905375 712430327 241294402 628590255 41928120 39608857 187256312 742111161 874582060 32441879 791860352 510758740 268418799 504128009 188478135 121756751 767723993 118212895 323517865 901681797 846168635 100 498483548 265541780 100567463 91570673 604893180 839609068 710749554 172905607 745507009 563060414 784366303 575705625 566471061 479738978 286120744 4529507 942192990 513878494 270848655 562896933 647982120 345480704 187525498 829945950 139227755 293577636 184474493 656955992 43821963 407765233 374626774 261330029 76990386 6222454 873584398 354245013 535628029 472279782 104608968 368085951 13694427 931216162 391243294 781749629 256838435 29018289 350150876 474136938 719408136 216167159 574288986 636899582 744172370 206382980 363962917 726045268 902421689 805327043 592811726 564115960 784178608 509387036 44033801 496386997 798916781 166349389 675625864 213913828 22258808 178881710 752597407 954771534 252019190 623660385 744393439 257454150 84609447 594682882 891029664 597860507 803136685 422141548 626428029 728898645 29217998 601278828 457190852 362957479 5592 52349704 452363503 482769398 719558573 513157643 233556875 9936160 506297777 161251233 390038302 456304465 100 286612407 786233415 119525169 237371680 416352402 847503990 647235336 869295378 913208647 577023049 50575161 655049324 462109623 541614022 839589390 805119921 467028350 550350735 410522928 935810193 976181704 596336802 26190343 304480310 883230946 37534321 132685893 816982630 905182346 346595731 531343648 189050882 506319697 229810387 550574595 524056330 736695036 376411945 916576230 216507571 860668038 127644532 618157663 786491228 469113414 460293801 950133522 490021820 131737511 144655526 454052489 595092275 35911230 468127214 970141071 227911762 961574782 946322037 113006416 561857953 803201744 107357316 715498417 380124977 455706880 876439881 978490375 186588884 981797319 208658370 997084941 935166291 156189358 767635106 612117705 923070606 538611896 356832928 103414638 627246613 993471999 393252567 374836598 834584315 48128329 685284602 973960390 443580903 758345465 822231783 462886361 9457338 561213363 585340354 39350915 379167615 618358165 288565389 301615533 11631860 100 282020803 579932711 678085109 579573959 895057123 191107107 45274365 495894730 122087392 57577564 272146637 408238954 952446441 455466081 999336067 108956515 926449965 905096619 26140735 164567799 254361142 360448231 801959569 622112587 12104886 299428678 452795557 965969520 66599152 904917242 238634410 558678782 925860128 925730631 96850475 792184083 429045412 154134331 896743805 326334830 45915259 498753717 962212762 58201497 518323967 614286801 868764627 364850902 554692110 792451667 901582422 671619138 448248659 820844016 934656437 282247974 477777548 18536623 447125863 591014415 890951139 433539381 165924151 2915759 128657880 225557852 987076524 738218121 877192268 129169906 825752638 147687726 581326007 686536414 238337825 924690647 996725406 592913919 873418650 388800818 534225806 746828219 380316916 82826611 662389240 479785847 376653204 640683806 933990625 221085113 3768194 755307524 646766158 28511732 554701706 106237424 694622339 785618666 240901932 907001440 100 720739500 637046905 872978959 340137551 203935383 885201958 391809193 868921890 2603271 92743147 943956937 299032469 935863363 438213850 628231442 63813001 297148046 143036068 8271752 74764501 674998196 86528463 536375291 967302627 926182811 813161642 409633843 777618654 235400237 224750206 2201397 403535965 691185679 802235051 301907130 855819336 725357867 344065181 221790749 374998924 636600508 321916950 525750213 818612048 27851140 920330492 548816343 824538350 502233700 999512804 740531378 939972999 844029915 780249617 616064246 894212297 232731730 582889608 76831657 113308066 988964918 456214727 321674838 231309768 724134433 831060475 684399019 618135589 30094845 610816109 624775310 224987680 42960342 980719409 690291591 973345710 140916354 150427720 36674582 227119590 997491600 37158584 782854973 303642107 351278538 644168102 716988700 272531320 150957379 46067978 163314762 852064957 742468183 529264265 292997497 93254051 156382332 328394033 43224325 515404226 100 634049327 738118023 920709823 430168857 155852057 228173931 151198306 309334301 478670267 560331253 896423252 715408007 357775367 710215292 648263100 357878743 767910821 220867439 984828325 647222446 143697679 862195645 586668881 959267110 798469308 514223276 758045739 662527849 906351889 199346925 866500494 74155941 510451493 567913676 894896957 369437297 712297002 969677720 862791275 679524861 402625722 45709795 392459050 812855689 417317849 525952315 892013336 608207050 597902221 234536516 306432762 605414270 25230450 176042684 376438857 714197612 476975377 53852767 19882679 352888636 929053532 30542028 713967193 763296829 292803420 983819917 212031117 348558902 635039663 110110488 139421326 92407476 152057165 901698726 31046752 512212457 942779579 336890890 550767274 453181892 402612486 794359210 862772317 587487747 726597194 682211857 966754083 311831058 315841324 933553137 171642292 9319416 236749448 761813005 689307624 174500102 430253426 126745481 546056216 39717752 100 483102955 607200071 933430322 598108206 150285700 835795881 422529651 865812418 653890947 127392393 551838305 304240699 653847019 312742235 319533665 164549753 165381617 37333711 406026560 939116752 381899195 933103075 855824189 454050535 327813198 714129852 645102531 553659406 630773130 967474806 86123231 608880343 751797101 193439602 850293365 614812582 20332575 138183500 648117391 447393214 157553351 413572964 795186251 463895300 450362224 49392842 731627767 246810472 449546011 190933807 408190335 217909942 32364236 601780134 784694593 294835278 607816562 839806514 412218657 820802400 157858667 334132282 967992320 401940834 492750458 30120127 945470421 927342775 700886324 795283397 734606546 826569199 323358557 18353468 56876489 906237493 475447054 20092960 558941954 659040716 867999342 940666509 634487681 425875531 803646207 663169080 972553265 815291704 878966056 99388696 775807513 340321140 248174527 731798352 406308942 527574216 977611775 345243430 123902167 66822557 100 399210476 747248630 769268021 852661079 277816034 224628242 689289374 635120745 604208495 30587040 554782311 205734563 145442906 44414905 165818374 269520909 382935123 626222589 82127577 644487563 15719941 338681286 165300769 518876405 742471512 369576711 715651572 671994549 189268438 28063480 119438598 631778134 518794253 119905192 779666745 982083183 298622304 142175893 989945005 161184174 568753929 982233562 599763104 113940362 354193217 535793880 985609313 120527830 381158778 174343790 858128336 233012071 728969849 915742819 115935829 87661186 394428560 700198831 779828537 260257561 92635402 809125091 542156319 400358169 284232282 318850821 139697742 319281124 556536371 164131312 496441449 373805516 177949362 660247102 229348554 42216908 898743812 451566755 875370759 391558007 880708145 530794352 89898073 616041212 761442955 930687494 485294514 511318066 54438033 401235565 176463756 160604203 858299747 542375976 391305367 706155584 133001668 296511468 825293034 69748672 100 507958988 495871875 793015585 708583210 786641076 161132996 149471751 197271025 408798109 721201823 337697233 543506173 188348619 281205778 31569695 501425681 223840347 662089589 653277850 734636545 689304944 870997630 966592190 129861627 725406928 472457776 622496 751744713 114981137 616209732 444291534 292405521 638355289 485497452 923054504 957880418 39221228 497015484 545516511 394005145 49794306 596870460 763073052 126127520 785016714 576359298 203041147 474179515 780497122 658013371 923519588 750539219 872581408 400332900 31086912 65851093 983413825 593024361 822980643 262926745 946020623 596460877 305588808 668389145 379308910 115352732 687244121 626146478 797587244 23984422 84869989 206288272 525412339 115756310 438845285 147488050 576701980 479576648 500598662 208143219 333519032 492205963 809932435 88606024 414449257 1427786 868201818 774699126 6808931 332065978 20547605 543602059 682482106 461327316 776509459 407875037 795103403 847684286 571370413 376110451 100 123202112 521178694 659335348 304056821 938233788 581322799 967752253 531888837 134298071 839562306 190293671 484732284 183193837 356463861 268390734 251095164 289875038 707910143 309163875 931789598 653398395 697528256 745322155 738441202 576495554 458337096 638427198 604457921 942613624 48148932 751999824 352537797 961056308 974691742 371980795 246435267 870479233 535350953 282805333 70529565 831554573 853663854 770215756 62431241 705070819 286936825 737473806 233860485 753031143 791765267 664897365 748825019 191167613 712801492 655482666 410073811 803007478 387245715 958151736 6192491 571208559 190604921 92820111 76159978 272726437 489758894 126150409 20722235 438229672 156150620 281538670 502756353 844088801 66360686 514806082 662785575 92766839 36620504 625574897 16726047 577947678 653751406 101160539 41360706 434555438 258310346 62016359 582231909 686756611 649401682 413501708 796342012 153033620 688009684 127027677 448839715 672709354 304028581 967338400 573294716 100 802995546 86112560 472070184 460782266 90874953 896108540 662779199 271332855 102331279 933194355 805180332 101326287 974657521 397119143 822866631 983172580 138221284 985927782 798440447 406040101 954270159 175198098 399339137 620671778 618042836 650158327 613062317 795386794 52883308 230851602 626919008 492564955 72115444 549918307 950827246 420146256 338844009 581089060 947361088 742268876 889678164 844750529 141810901 664622872 551210958 124133113 140393819 105795392 937992278 936408431 427814347 767170618 365316533 591793373 637999268 701577170 163401065 556360795 199645168 324282690 778918054 509017633 781285117 626361081 818777700 633128095 626115175 981128447 768539804 915626252 861738069 839402624 284802931 324335986 424126143 134514086 51974397 188582699 912914157 757419687 917460940 951150940 768190594 740667657 531409721 272332878 246186159 965116971 885815509 79781011 417780168 847986109 747837948 466420245 466601446 798416761 261411243 57672649 30051516 938150820 100 137326960 390308891 119598563 569231153 625758090 840943018 237072122 90572057 318362447 995306828 81256962 859897438 244211953 812275352 393125508 683751906 586774795 134656554 396997213 415659178 315324210 449127677 965511849 268575651 858346732 467320089 642704581 356884598 240849383 291342026 122577704 53453945 993701653 955319176 195476371 644227491 943551073 769363657 267428813 543528910 883957764 585020426 726038264 355380952 669575130 643048123 222397162 922701755 225582693 415948705 514470366 490635289 847610586 610515389 848392058 594113853 495623441 634421525 627592592 698369682 633281768 819793651 401417963 311198536 624423983 706155536 814468049 366111939 223997480 174275743 427861305 718039503 897918153 324846447 53417729 522113546 589623462 351294287 386603959 459171704 432155323 890559581 878174070 604318648 828965189 854941792 217567425 679755685 185119781 585703072 528338245 630148035 371786350 567298748 481229804 761940632 329804625 532128467 459920522 711551716 100 137363419 747584238 852150697 839621930 399163235 277436902 869141765 612220005 389525050 316866992 973848620 203979044 140124574 812218653 678040520 218615025 740587303 142667679 46027043 176893960 964022146 702025540 767312268 653348510 790848430 11170417 832135645 467004903 827706119 123017679 199840154 992803056 502857300 95244132 758799204 757328065 770022526 895356370 322207345 788624331 563315850 409099336 441722600 459865049 146273156 583527538 982528285 554282276 211191790 844448661 222176933 161481534 420407850 362470812 119050394 780381581 43441740 769759461 187345007 44145505 123379783 413098587 209519396 742920809 316912081 897077689 75915490 749171693 491241788 240733191 905299562 109826370 34919519 766264959 226494740 470154247 179305072 512791465 495123101 120694341 931301295 407403377 568654680 426081021 276746351 916003265 135911715 289417790 58007525 530525559 125400764 312040973 328899638 561651408 243046666 379697913 714308573 795036057 439372860 443654195 100 591552874 722830500 372661781 600705512 121756427 786766112 37951733 164725631 153960965 599244486 349116232 256673208 5325948 420907489 597118817 303804402 861083548 567713315 265864904 198838522 589865872 765679292 844365715 711495721 964021882 176450378 808429361 626816781 876744668 241165984 560061980 794194783 178840185 603312102 435678909 832118172 580495757 56038314 324821379 239058644 891938661 125336887 786642071 915973814 29191384 124385905 165032957 984525847 47343382 6318599 881919526 621905251 54723045 572021480 789121927 651705896 649249257 940635706 406331008 506572246 569184064 801272470 531045676 299123299 282001957 829861417 737922 809159459 897739289 192345626 409796673 8409434 181963970 84086428 262237804 567211810 741599198 630893564 976259225 424535870 554421259 527292262 584080322 46497412 431888374 378346275 937772299 124165398 155416873 559305267 25982311 209794856 750601495 429304987 819163175 878979727 197670745 367259170 367281178 662999207 100 258699874 178746936 139798025 864359575 395283400 245873425 108720578 542931536 698640878 92405409 482581691 617595662 158515906 456762620 646566603 533081037 180777811 458228165 983144942 618556213 276072756 690816324 740906488 226073489 73722813 841354324 949887574 558021350 833371425 404533564 139016662 441028682 341785028 883228687 186673739 721688118 381393931 853607506 444529842 917198556 80752838 229735352 149802636 799296261 462622491 118807136 619152190 442854608 741785490 45406368 179735136 798447618 849161107 167035537 452948930 869923781 462939612 496713474 9578347 455070873 613907829 511339555 762784742 124085114 783537504 693557213 611591222 464349929 725138630 30898783 229496293 526916297 19436705 696707558 883777306 164573991 684324732 998982993 332288820 968057544 134917963 59895954 267594198 910293871 857548033 163569078 861578289 579083306 36316472 156995077 210339034 650083996 284231795 983389363 808918005 417794798 324442802 5793017 361551877 963443236 100 871469199 359298200 734140712 983184035 852862754 848627136 804191765 671117219 272450025 347179239 171087326 137097587 448358474 953278267 653233766 153581122 471600100 356660200 534235542 271866381 178077448 650056588 281746656 392779431 827233873 620488507 827956680 16654178 126794469 489333140 946183140 777848347 760428441 209952617 176697196 93134468 320324251 686912622 591132308 667996391 151713078 900303246 608119140 211849001 788267422 965579691 660256061 400561504 493735357 715747802 835903724 392239971 520315398 172354418 605128207 77258660 705153755 426384440 255790786 323138692 167807181 886284896 498774953 563955357 821840992 536545744 678683808 441208719 669010267 157125965 952416548 302878866 434534757 53144995 919875643 439420657 611436643 693055648 852083757 223750848 510107556 203574551 243042044 772552744 711376095 731690275 901283980 516687308 730595365 301836883 435038642 838430277 273161293 824800470 403978013 268655921 221176589 38648561 692015990 774566798 100 99108126 482452505 162184945 339049812 383636414 876088233 129592479 689372047 770078791 965693448 174745936 386074318 178994843 667858059 727734391 462884362 485657948 888152888 475347105 422169259 321062960 214533527 541158380 378440322 368142361 358821544 404250088 66166533 64654542 339451264 43485145 855830257 442041602 83280665 59599841 332089955 59432396 283361051 943963846 757009781 576672768 735630585 512372034 301592742 644348432 558163349 445432812 344481848 534069193 395886987 399190590 215670723 555521720 797274922 241742759 822965285 532353691 748197565 527592423 152503953 611388497 595048410 416328453 727542191 150126997 502948152 669437007 52640092 406267799 70185131 982458097 162914412 275777796 826605849 783939604 947335278 596790395 680656071 232704646 724114084 695484930 414977683 189547123 159289777 492644022 939255198 679769743 104651800 657997469 665761600 705417302 725662641 729735513 504443212 128660313 807109866 855793655 57909168 803680813 850490741 100 347992357 309456861 962447303 60101319 736450679 739550395 157549484 449540148 280962924 919445454 279292588 940532414 468492913 843757487 663509328 94095944 517917921 834542782 748142069 466040870 258820127 536893609 284358437 334738746 56030922 556341106 128245783 650782503 83130444 499698958 883442962 442801321 863509472 835770367 370106098 104333168 799846593 601187756 994214506 215983315 827391396 561747969 256598062 655161413 585806658 833915679 527784222 939176532 231396121 9204123 336082127 130338823 305910322 254595863 772314806 903803947 185086977 895525739 241328401 684543804 471639006 244345577 913103713 419450030 398400026 576654491 40006238 478003335 136850012 548010690 867633679 545944880 236400335 105574152 350865681 862924957 278558186 848331724 741847814 62543407 422652714 978527027 392729124 945074915 676819838 787112721 612005263 949808190 495029792 137783258 677868391 900797059 772926700 400713017 349398085 179765396 514887825 634978941 480735840 248968400 100 62914569 948829885 975724399 350037807 88058050 613151766 113606534 785985361 283733407 290791349 514809191 703396999 348569352 770371825 380543153 350845140 764950420 658267599 276848389 640818073 773348782 806798611 573246804 992779753 404658354 524625429 312454061 719188082 873130619 596468321 267282626 137036729 703500696 906527885 730102173 590252726 432954676 844078959 755264498 229473227 836561703 249534928 761224623 44808768 5267109 471206018 431472609 394434313 181491972 807516616 370276365 283767278 803730711 568907743 781134422 710474760 978883972 395989232 45879500 183876346 644821451 484195803 577025881 766520086 684653594 787949325 486417256 696946017 980440117 997304468 433781678 949461575 482365754 345388578 244057137 964907126 888511714 988270304 33697349 735302703 660528033 816806569 775804839 326135981 158437705 86130586 954322376 343003494 221849952 73432928 172249170 439902702 950190348 376581447 507920328 334747273 268341744 813797667 976722690 690140617 100 984722179 83814182 59568093 236674794 224471440 191605697 645249986 891257833 849247623 719564678 697662631 379577992 122632327 161492090 497086880 91202733 484902068 859396585 134840347 761931690 779430978 123778108 904363398 466957091 430273184 728550359 210170678 201029948 291621045 244511261 531631681 266108507 799854945 583923881 736986852 118311068 975470043 522451712 513635851 746088469 653892356 28958977 385252444 809901320 855496284 174269559 520253714 128151543 664717986 654118739 862405279 841229447 260067542 430175764 917909220 70345365 659704124 405583967 518107450 282086983 815216028 646812852 72869426 620352757 834638586 167237064 700525872 237427927 281302873 575753748 97382891 834643572 365546593 470821711 833095597 910690763 231394841 708685107 98801339 162247619 693405874 197829312 597086520 5623616 226090438 569406959 442994735 610015058 467288038 167571199 196816459 727933234 48684203 685342049 552284739 541290013 800096598 111717396 435428534 180512906 100 417742690 267232937 783373192 820789482 712612684 259814593 398131171 494092730 814670026 610377473 517749944 868867287 308362854 729606537 689161484 940836091 269417361 760570576 641277529 163374515 909311130 629017222 900921178 746874226 366978635 575173916 745784395 366451927 601501394 642501283 715735664 995975513 205981372 834155678 26861661 307099498 585613967 142956571 201724217 464297105 861481736 488756634 481482864 444006274 30003365 757087617 792288187 822557542 501953526 269559999 247592357 753847946 865805772 373649713 50952217 122217432 539722621 472517458 408568457 225792182 817973210 737048154 742606835 533204550 142632216 779171327 684635402 736620209 602742708 825372518 961450856 742604240 407457205 47954352 270510675 167546720 730345949 651697162 580922548 794688919 148333475 960411053 532892644 995540610 161766981 983797219 197898907 376540094 723136633 626831017 138750028 885674532 143782862 62411618 256104066 752467410 810881576 862245489 701189482 789926915 100 479416499 563904119 108657041 257022550 908124984 804857012 502137612 279517743 36250995 611966618 480980648 177508924 711021121 264117062 751648614 640097661 974254947 415266648 852226532 919154048 979433906 387287040 994579675 147095013 204231316 981042529 892690210 62987435 669456909 430529307 293615459 326729456 868092290 111428534 824936061 334540206 756784901 225839963 600738053 629872214 395420487 625543274 185515509 657468654 521976308 317603963 147207458 311260147 840267307 689569148 817559620 941352059 164244990 66657504 803122955 939469986 884978088 672990945 578163558 178856046 443150198 867747252 585074332 429105835 903498350 284729528 100252489 700821160 270995774 782566771 826415996 168515723 368854822 230540597 561575080 64929869 508210802 911519277 472215122 508622901 290649417 741397016 532676425 964287133 643706621 647473865 856667527 704870666 303579582 681887597 784849160 248805641 275988308 567293048 351085424 766323762 752786903 239035731 12672681 957850620 100 407863105 906614791 722268398 552211157 1540312 60743262 10913111 575221481 697987909 812380108 794454765 69740277 810792966 53061567 547255139 473006414 48541031 104435334 723673478 493870187 512285868 357255102 703476805 858507082 872677070 256189407 237671804 508857735 542227517 170549530 726331070 858967447 292013022 6985287 112000446 395059202 844336882 50943434 450273630 220206726 816568135 416821719 322023943 574308568 669864194 431087169 519989033 358721946 49017383 176043592 564091900 835434425 777750776 435378857 107968893 627471696 352964912 916238235 766338197 54420648 82469220 75204464 604498217 724071739 265004650 636821932 645798229 995174128 622808042 905693805 168220734 484894019 176031495 41469583 697658761 524694286 530548697 366477561 509726302 377719692 885808833 529762500 747256130 120081851 154025397 473100597 187485439 957076425 555653741 373319310 724696483 779695140 76597750 707379515 290111191 426863154 288233913 103201175 136638104 645996934 100 558439267 648361777 282805302 33051425 684780933 21569188 361232116 705194093 861425376 135519108 767376645 727592883 745258494 418121026 556378328 98644677 460178817 37215552 173705431 6360432 246543946 663498068 6389117 517996346 27189799 641291582 161123119 290998174 903175278 439252736 114316655 505633374 556798503 366215169 676409216 559773106 49819652 783671090 632876141 109703138 757474684 818083428 71775590 996733877 984731286 33903246 810097144 814602931 552683149 120798268 977254860 87233215 703600655 578157814 817780034 867570102 259159847 962911530 789253010 56738476 896660085 94659405 22605074 344959448 417693995 50032440 431235009 468780482 877099215 136084773 244800885 555812503 434439093 195847910 625582052 291770856 469560312 455378903 998735067 312289883 922343650 387184596 329263793 684677232 796314697 911072429 38384377 528806022 236871051 683054469 383273467 888337233 802365437 79117301 886971864 948739689 958801868 17556112 906949577 709817661 100 623612712 740829242 807370362 207180910 754424556 46941701 781976392 590665102 407480832 867813654 575121762 326183770 703730826 603810141 416295923 60659102 707225508 260716596 62306786 785498162 445252103 66365120 474569959 16655890 768395142 923452415 439060371 903972247 705878147 469645702 682073836 645944335 350346509 847615925 965228581 449222782 387467329 986985995 664677967 916547274 973337418 318884819 29961201 831426393 973077221 592300069 378663733 847173163 275705930 600349871 867414979 872214817 192485483 169151944 190481390 414148284 112559158 867404248 650204148 223629572 989168421 980899013 199062463 491106047 160366700 899378546 527737900 963263501 599838380 820688445 945077658 659807041 626154125 108686497 789607540 826018940 967224388 581728755 299141391 249913891 339955430 877614954 446746976 9992512 798527147 909104127 238424317 17814156 513262270 227628085 39514024 452098013 392810190 14161095 825886415 588970140 315622027 31806262 513896194 990525055 100 506120075 287439396 289125814 705546051 69824854 985928895 594856892 474946965 650357907 903303068 985829354 68915619 24836188 552874534 247644767 823409013 613490477 188576528 38752778 178409623 299021890 32854582 518548950 370006807 969550311 954129561 155150345 100526808 592211435 896815594 36824761 713759811 63280442 932696198 193128416 319657598 916813523 820218157 75889433 23181524 449857689 413323862 314666052 30356311 28523603 262176200 638701817 392402442 328270111 369768887 39842937 563569300 532585985 837740895 910527089 551552444 265141458 456143338 452114538 155657937 360695410 979452194 329613884 696041023 995265301 992414407 503291618 335253542 682977923 806773398 389396226 889532295 77283342 8795384 572013717 855955677 927272443 873074963 523486802 320071693 489124309 982855067 356638617 413601778 654653739 35454359 602957875 327631260 212512600 538448672 200344502 858939392 674725681 419439306 419283148 783057154 833667926 625175010 991955869 309310653