99 19 62 2 517102135 191023325 87963603 507760030 30114396 756445982 272962071 538320276 750437233 706882692 524210267 732316761 973592402 517102135 799970431 194598091 183179060 951881484 14750641 638231310 715370217 534574420 365164671 352084908 73232914 858553808 175655085 128316791 449194833 591522776 907599486 542536997 337787976 517102135 70483230 218550178 836999195 35060615 876439631 118166827 712897390 224106574 979365798 411586748 766595651 582937272 181661633 115078384 134333973 770924534 390438411 52093985 517102135 4824142 115601394 816347763 807690808 925915651 559265305 827152192 94316414 723038056 369394264 291344514 699208523 635261102 715452071 306014117 85145252 207005914 340860209 725204669 110473022 765013861 461933721 470587966 544374341 371009679 301964527 673770808 17300715 89356136 279043012 525563785 736427702 4077638 780375097 141757638 825709305 794578593 691517426 999551273 842962967 277275883 517102135 303892965 794680784 959544719 994934653 502683047 878614188 462996681 403972607 100814059 426419225 276823825 189662675 78018620 1597470 978753228 28096032 570222895 398965433 191599325 959339707 935651080 444948384 927025330 567198443 493887972 275394120 891929192 441585497 424392544 571368708 945897428 200545000 622064144 948751767 481129355 644154136 826193177 610487753 603753308 75869072 259202090 218588782 930525742 540093854 264909075 393315836 127934052 319046397 357065542 317909786 136124668 347524429 506673177 592011617 919492006 220096139 212859585 857772244 179587321 432279029 869592297 86741393 903341473 351289770 268182287 991486810 265930539 600059760 814366722 731361171 574805844 431746434 505640315 515394120 899424531 387295340 866169161 787943250 576446336 261951894 672700949 633338586 517102135 740883002 282223671 611455278 600686560 703333851 100125056 689005309 866832765 308796249 834357500 683162815 822871794 458405973 695554168 261103315 768531520 90261718 193070924 773573612 165555008 596955143 555297246 115571564 365498541 414663904 877033718 698193547 379281634 644560617 553687307 256919599 258526038 705969680 41753590 851739523 166431189 792588922 516545518 459146232 592972522 948651321 742058203 37203303 283019515 689129913 821020180 653314619 604944380 517102135 255175024 88279864 325870007 755778379 828089747 633559401 102935494 972015131 967896579 847533480 288058533 337264269 872439523 613178244 459813493 904325332 138340403 257225014 905024764 528697625 703506586 904614979 384395744 614091809 668701017 823028086 719138691 441511847 16772220 76140275 519848549 768772299 389036359 952978939 204594650 702272522 4414613 153693751 485549997 574491576 460718929 495735366 437136376 103298298 126725708 616370789 756096864 770222449 78494424 100597548 536176402 483916041 628659160 906024390 995517932 239992867 785396527 209467422 51911436 820813769 740717917 855444061 65936402 638364852 284778850 517102135 108988786 703067831 746770665 978341279 538621626 383539742 268116089 318348083 868414817 912562819 614164338 277146329 63484555 785334440 682891906 819895246 445844552 819549065 412480220 517102135 609082161 854090499 476188032 388867436 696857874 886090354 994752312 681080581 906314406 517102135 196943175 797701436 328811569 636199529 951404060 912703142 894556367 183611124 116283856 715217344 916180064 499535340 189869472 838767182 621166500 973773993 441515758 913774892 700579790 735105576 251885939 563052393 822184866 302467660 494482101 651199382 713804007 282186019 273137145 272064118 789589766 59269650 715122713 482194567 267933310 468585771 410105870 841781718 966254539 47500818 180693574 489576851 26908572 882299538 834315771 788008403 264836323 73385966 38510039 117371097 935411526 449185430 104973692 940244430 837251797 161695874 473565626 448777687 379981714 517102135 229507694 517102135 77189351 280531646 988903240 66146672 857192232 720009549 412918890 287282741 596966308 792994777 146566127 744839520 923883717 589344319 907787214 297994870 192227628 974989289 504616671 314532069 517102135 997278956 517102135 223740066 517102135 48473990 245373938 496641682 588700091 476169937 433059325 293458081 891720748 927674868 40688625 626918697 361652891 630117345 845641923 804981400 601680107 67172516 220230616 816248737 394004749 581268231 719465209 805413627 218207593 200930684 378951592 556679249 29745282 414009827 609120078 326946688 692281581 875030378 838253135 597719222 919961920 599207849 304589183 937187309 854984098 114212377 383928013 5552215 863354148 594402882 983580694 110665888 849923815 806914735 337714882 980368580 394775850 843403687 519186682 651712262 329846105 809389351 722547009 866757279 201903578 60036934 76155041 251112034 968345381 963883635 939241692 361553605 281561908 517102135 990171571 325433239 170794045 756439179 517102135 652966738 434438953 285589660 260265796 276186541 63834707 962019621 168689356 843345695 332699429 232237898 4795564 622999077 568610285 100222285 988390339 513559783 52417485 77697236 343089717 179640393 571288506 245454595 914524577 447971330 648805440 993372856 13731537 256049401 415465679 668941329 173812634 427678470 469587652 81928738 250691629 69422988 843251538 275595282 888813309 606077754 889451032 19170373 591072412 269218851 21290331 830770551 485604238 545061747 450354312 223870081 182963315 758729585 164158596 909793783 950148724 656075605 389740693 877261300 439285550 440527501 111911697 522719971 180075884 682433215 482773907 624244668 350235276 393083774 8947487 993450583 158136486 656676856 155751119 18863442 662437257 956507470 619416081 461656740 452183612 366385910 386909052 883883681 538876695 920109817 465015826 257828607 254460944 645781654 671477928 214676742 168906871 357069232 66824129 788850609 192428698 792594678 230912601 345181730 569224984 341021543 203308553 451453266 390108311 550770604 586332911 728817875 195810868 140688042 430560275 384288908 706088481 625342121 153629908 504579065 27785792 875282695 347582886 914158956 189813606 846994741 466794174 413739615 402602789 907812464 479765545 276193255 457190156 517102135 481468594 395248066 81747415 207340231 400900026 832336319 30131820 355453339 193917682 79359797 86942682 851473893 629901565 327469016 393267145 809085134 852576390 526271932 795410953 191920742 812123955 544035418 112360519 883409837 686480976 91712719 702375390 175816550 812417393 56498224 948687024 332752215 965757760 177779344 82368389 625418766 642805772 470130811 228680313 76241121 58074077 667184253 952175800 122934032 707988010 740025451 723931347 287730080 977758516 781341931 338495033 48940442 723798238 321122779 92383424 107971482 958013400 460539388 867921541 501441027 450780532 892837390 833673073 118713802 965807058 925341938 469203035 229338743 306815221 784520620 334786774 36250155 253669815 927667371 953579104 518193265 994618308 578603526 556814704 517102135 435356332 670201170 694268951 607537669 596765493 144072912 702498513 187189738 480266227 323914123 387926652 76388465 398119001 378016152 160998614 626547674 467944849 720885234 771769998 812620303 369743267 821217311 401766428 894798379 885024450 517555775 63484526 517102135 406491435 483005611 426126081 313058900 417220072 231642792 140629129 34366335 3104890 567379618 95858703 262698182 666017479 253072753 464714518 549561472 882453815 633660151 238483864 24976809 38446398 107878227 271517570 85662490 306521145 318814192 824554217 569217425 823856246 88340781 500745404 318835236 471292122 735253695 767103827 368368664 630178102 971391610 587594655 223807095 540847675 92128821 981290521 681091136 333940777 487153550 974916762 517536385 354217047 54276945 370705478 237700373 175423795 280865383 8586158 203508045 969736751 170962122 215846456 241168552 906830451 201810126 537700063 697656601 388527985 488846908 880745462 608196644 486912305 343960747 370056745 280587943 58801217 517102135 755317221 471604952 826537681 693369763 568254554 556308527 436658279 739385250 637840630 55111423 819132117 853101422 630021937 305352319 422167222 16568535 112284285 155673905 21229074 185148103 579289998 868631013 849191100 191711988 762822434 937012441 517102135 517102135 202155529 531345085 801345559 545539363 721708891 647642369 835129855 992526092 679911832 910684678 556938839 994913980 236285308 702981264 641646357 113123411 162618436 167109824 95784537 399860422 137652949 451684376 22725422 427167164 999681501 649399454 985423274 781914762 687518824 22623360 748088871 42931925 313952339 883648578 856874258 699267144 118555198 958345374 172645063 273321326 507561014 678108867 449648394 637077590 45987815 129995396 760998842 664388398 212192268 949285214 160455284 713353567 13685256 999659450 803068804 874656793 971886825 830818251 558750061 526106962 227895291 689354490 711155881 731967724 74350979 499310422 606888756 522828337 553416275 396539542 262080903 699475206 175223019 792324006 260738056 787999896 710039332 311261610 452182953 633564678 206893565 854796364 616980096 621333725 750547783 344987173 193971971 791092520 927584278 325687124 164424784 320727749 509066261 496326927 169136007 748947709 578610909 468561404 258484048 282888785 320694147 317833927 774257477 127272112 793046282 766101133 271718206 992948848 617803223 597788912 195333177 367984918 930270836 252759328 151540484 558424645 101741816 574226720 11598467 925124194 12120138 999809863 517102135 770521306 901756249 409161236 419234570 772692916 819102096 236228880 610359868 135077137 182052558 105163864 605518617 202979932 573957945 718773572 776802233 664756447 52307258 18227047 809158707 495006672 70548635 570274473 307730707 483680997 25417204 855460418 794367316 517102135 764564804 290042633 753747688 165438300 769794830 608267911 478767811 764725719 4713916 932041458 486826345 141450516 683946298 627945136 747271611 672822730 723364727 146421338 244065714 207230887 517102135 876396929 118680606 354631535 158646388 532208580 895179256 303238610 723570038 293537781 777065705 936181138 645158839 676541533 539399443 895371991 721557753 879914554 823876935 104195686 760450904 301715696 14677337 286313762 78261328 719718106 209592733 923978767 921433163 581005481 231154238 34884240 327522505 753458495 314710206 517102135 967782856 405290607 592501555 93769128 199511834 463361031 339837942 917585450 524139976 126301904 233584535 369634285 279857028 907166151 636862068 779336829 380475332 623151535 751069921 634161536 907347376 42976239 313128893 279404392 526172519 618973587 4222865 829040287 127947863 324114297 750554650 109559645 123250657 148253277 303025973 865615222 655309597 365209544 485883911 541913175 403051637 605367668 522660377 233666365 168044385 909946745 463774849 181761654 950085438 170594419 937984925 455590353 138987927 850680837 559218266 517102135 899615599 196616007 480648623 898368275 100545618 584295458 111669315 31360419 860543110 591791983 139827806 468845485 392358466 191056224 533341887 504438524 805145304 549073402 493628694 301741362 392845400 118010915 782506499 184859475 408151636 533886786 906243281 462230797 794856215 517102135 833993204 402297137 997128908 517102135 526543506 36799815 121461902 830055470 256489351 702608937 887878223 275016866 805034523 146705386 180043324 9332373 643253288 602339112 243305145 122136576 864473146 517102135 241971109 381733980 811248433 620698819 999695737 358574671 926291382 460032652 443262399 648436731 381535961 313963830 717452310 6368973 517102135 760548127 392722739 398725307 109914456 228955432 653539612 423730294 882709804 913182581 340920558 818634858 279894011 465947569 60352005 297528180 822329834 211929297 638179676 715926086 13178563 710838326 291646391 977640603 666742584 773268950 600393472 872858035 85709117 184240094 229609963 337114350 245080856 79918502 696419464 883612477 579484876 476153162 952408115 49824777 801460934 382641721 584562230 813853667 539953906 336300461 841542151 717796876 437225329 188680292 741159282 808577120 456471731 81348956 572262095 499269402 830685085 773722286 26849524 656937131 990874531 164960962 571226200 517102135 284846939 815390915 181233035 936759181 798028497 297982706 860169325 104294507 559471584 107731847 236901726 882936785 517102135 728489551 703445680 99409003 341549210 583689186 794968908 774206023 882356993 606682391 533798558 846179752 847804516 65818140 554412695 918691647 813002621 597357857 517102135 568794549 133262382 6570960 825742685 389186272 112485868 456875588 149628255 676613040 2037954 635035110 291197160 320863349 820634176 245168855 104890070 655368547 291630963 800468510 517102135 387976468 536348456 457483436 751902072 341509958 65412331 845545577 599876071 28281069 216375354 74431272 673872648 20241473 916012803 517102135 790914286 109023932 957549294 573481655 334591430 676945820 358461718 355912298 16788124 125922865 434626503 326360645 513793314 276224111 521118401 285976889 258534539 703952728 782209442 554694881 261976517 303640185 810933629 517102135 252027626 591120648 918530915 100968314 731302005 774513238 26466139 455150552 222053550 152144830 809806205 705812275 256775968 530125726 413813206 957116193 193443514 870861811 323617746 839051997 869412787 311547162 927095994 838210964 16406995 665511651 835378729 517102135 262446259 517102135 805500787 588699516 604053917 89462199 456739907 279844583 860648335 111923772 866849751 990558785 87298730 777577437 727501786 191012881 727458088 47512226 879683931 886020819 192386829 783222816 568937611 623723256 777383840 273172566 885641672 678427723 517102135 782339364 997219570 653834020 888019009 762065628 196808095 423211381 730660893 896332400 441842404 187472542 715564612 381145135 30583451 133292406 672439027 744100933 759585264 357906954 604709737 154790182 854643518 873552883 906063752 73609363 739258975 485521289 593888592 113335430 25574591 973433110 951405032 618797956 192502939 27827055 128461221 923143669 517102135 460819788 846233111 8158768 251641110 845496672 959877842 862921075 795660766 757535472 57741598 376516887 45058135 649500481 730378621 860442723 215662981 704486091 56624181 739535706 75313056 52763828 600436326 453272394 927546872 329083991 902958727 764693855 553273008 946624931 629891501 840134243 912176950 216174354 502867903 498423032 969032802 954649644 798065157 705521172 798109773 676204908 984401446 623208594 619373313 786644061 587326110 453513324 884534898 850855906 607340033 368747129 955694847 619707875 871277324 749496173 547172884 517102135 639352588 109677453 846944022 25693659 352272939 595477603 333322047 600466449 852366168 370818091 74674783 321585925 92992709 690867383 471667220 878008934 915517582 407622281 782800033 3863855 749845775 264020623 718615779 673557165 64925073 534423003 946348310 604156871 398114291 713076822 533938785 115631930 526582088 943351694 508398600 117927035 743077556 463775199 369887224 127918655 406329979 849354060 22321316 113953216 875211868 825739182 282602274 578044589 589327501 446101293 909553668 125449938 542201105 251216403 972232922 555136670 889145791 728584057 404610662 198333245 523687743 942440182 884891781 405070521 60004326 302275606 476026650 67861933 501119255 2082630 496386086 208796808 675129146 571864662 167064078 27635996 755092877 366123103 517102135 881625979 527321913 529327603 495989001 870750993 923610931 383665317 832584870 968247861 303601111 794026796 463578373 557897205 662056655 240024388 636319448 307869157 960408588 23146904 826388319 886227991 683270872 924490207 257839474 52080483 660269080 617402765 963254869 778745991 71820917 853826104 64726206 726243709 176006288 167898503 288777720 29208246 114575142 608323957 952449401 43178957 549395066 153206949 580263768 628816780 293124576 522110518 968495600 702911800 680140168 892600348 713131872 599027525 911728032 999448149 901709982 744629177 802528909 852220437 44198806 416949224 244101762 234170760 761682233 127014496 577912162 851858728 100940521 791472431 54786791 807263040 712363076 138218388 755844657 508797273 181983339 288769884 789991706 779673859 555704954 683529048 827647320 525904422 895116251 59279186 79370106 848603189 718904519 109535040 801241897 303340174 740699188 735468547 100981093 821055865 695818656 537411269 559233341 414642259 586282744 35598571 671100466 985185272 406192131 422889348 930062182 957501954 1790026 141899994 435271806 18464905 299903584 605174339 487660925 460433514 541690121 765145152 456789129 659417323 517102135 397568288 97619125 646266757 920513315 775657569 555384233 815805951 910902098 471212625 82952682 688415931 184134963 437143245 612041950 870461699 25682943 901575205 940602971 698160424 298906677 159829442 786122140 828827217 703418104 950970876 175388016 144778351 515216320 587281972 490826451 712725507 541921392 236977124 255281246 668327006 693874686 668910645 260396069 60536642 376778634 721143085 523402606 513434888 802513661 629124405 701241768 332108946 969782527 629179548 79101401 782153065 639592190 532939495 488274646 852637497 269842888 908502687 36858659 836561991 159359507 175792495 439864022 442833171 398017298 905727053 375502837 98392047 668180036 977862485 47116664 831570811 146487825 770376335 853049402 492140486 231203749 369795344 465060017 770576449 285457320 72877866 389964960 517102135 100837668 124942823 604502685 788358022 894044531 464354382 128788418 851855184 397251187 780516991 8814205 176326767 838947816 818417527 516218400 243185702 322824064 13416983 227524525 615419528 517102135 560657657 87235981 524339476 660666601 991076270 734661872 701965597 892109150 436979553 861527283 658500633 654217624 630231934 333081125 888624921 803784047 685594677 30088947 680985074 164441312 299436140 223890624 260068927 931955216 823106718 479738377 561321856 361933359 769529765 792263089 309427442 459571736 517102135 305062805 139687558 981641387 11311685 543257945 899066905 495363078 24593978 600749443 986914804 437424236 202976189 335997444 879360884 206720813 245420045 14526147 881049691 979151074 480877199 790763648 55839365 365175655 558326355 276352111 554390463 128841937 673143804 794380131 354017673 281986871 259584330 279999660 682019522 973202775 592315667 917103540 77395937 577573187 322679782 895974117 37149058 783104438 439758312 911942016 238253932 214101944 710225353 458878376 577644836 995064853 119489288 400984481 972910073 767958969 857476089 835198622 704928107 466255772 954399548 290296108 134556743 41363294 789517826 546346101 646485393 378747416 270601386 336720373 294949484 475460631 534759000 723884904 401808893 481616330 49734629 401800793 783767999 464512433 502615094 441956686 662546897 48217072 168408823 801232855 731315875 824306076