1951
137861771 412536014 143522023 863574995 362912702 553837620 453349856 756903737 315321078 519123894 935595414 612616750 665049241 687586650 924495625 807522944 649026847 605347575 762250153 688970478 115558076 621741089 106975703 408684160 533283508 910735126 84615245 483714495 764925867 281646442 982462077 917287834 682862984 289311389 527058841 823064244 586874833 446262634 896482514 51866112 456573199 395707791 2141537 913210563 850070459 203624623 570557687 929300505 178470899 747965907 737704809 140406763 776523253 850770563 2143136 429527366 930022285 292291744 519953594 361218351 259907920 404538627 354524915 992821109 311197172 971569358 1804192 92778257 899853856 736615802 361490986 739967238 2418727 827733108 703795880 560346263 402829586 754939077 880857156 594935368 103431182 521631439 582176129 892426791 28297347 505521193 852791204 498766366 118831402 583666120 649156400 665138151 825175276 143648762 418202348 984233444 665787578 900246495 688856925 708174032 483013638 521799425 944000519 174026450 151907399 945303015 217555304 358114204 658267159 266237818 63798293 381402308 222285643 866761366 855220640 209379999 326883343 51704841 728690980 397084331 234971698 355965255 418144358 220701607 586989710 683363905 656788365 416505538 668012969 275284389 13331203 380395209 383704990 318228497 779235149 231580748 191369521 272207369 969060749 278783575 964574684 383330642 74731572 78444039 671628250 377141945 377506370 262561374 929147895 750758348 621481185 237326232 949688595 454734717 653863460 720825978 192768055 308453711 881451351 223512574 532961743 144753030 230180434 405253439 842916098 368346264 956481476 746519259 479801752 270021914 328610467 716135891 688504404 210423098 579072166 234795089 863231338 908611712 657012504 156173812 960877500 297358266 964396686 950425426 187852984 832837365 542869072 498162174 596263137 146809496 409834627 162064655 39094800 773433872 548371107 549494702 580109347 417144230 288440982 373240809 561079933 945235028 934084134 349329028 143622056 495749325 747892592 572257711 122833254 555152684 576052018 342760188 751513163 867774368 184941526 167877945 826350997 686787760 230183270 96267591 903608411 510868415 328878583 438675777 520853558 615557686 506765297 437551063 991304512 532232127 49417742 75591585 542258885 155593467 528434522 357471344 176621255 159141453 610716771 701225142 614561893 811898719 345047014 235604804 874585829 561190692 695817393 40232326 618875730 47275063 363933679 593216151 440176501 243557352 464810321 370681120 969225581 424890265 27874285 959304718 259048925 958530760 182981579 40312400 62559631 256166479 749983450 965848533 869470312 543270772 518319736 254946639 309498099 328350218 731029040 38018683 413826575 337061694 145696666 224284641 846206353 307030057 936855111 903901424 5420378 752478379 700884188 220004259 576144088 861460153 789921941 11622141 558679301 99454262 777656086 262519257 293068084 510942837 803424930 286089729 892691569 315256790 941089569 574326571 496156866 527935685 339848504 310458504 382261673 946307251 67184364 754515709 776838331 691298518 742849178 433668915 351108925 994328453 968775971 138173501 28946688 56951245 942942451 275111026 630409910 70278178 482674119 802061525 370349651 968286296 866164886 180860213 981871975 290225161 654208655 51412437 234781866 246561913 11994082 566490219 450499916 716541233 188385284 634281465 559345525 369019684 994005231 891096464 839995007 267997023 227217614 538582122 578079333 423020210 727343012 658226219 791429355 321182959 997399339 40386814 600516530 750277901 917847649 414648007 766562072 497669741 275622283 734962975 442849834 6635807 502586232 45792647 736954761 945076184 429703385 115332138 873637414 154289959 219816233 213858663 124801344 779919060 582329129 974046044 932968590 903714878 751341814 455321427 195557958 442027033 15323238 962469663 943849703 739815108 366898627 11980022 1013862 407994022 133530689 554654523 73114421 60356450 346623007 281341284 163519046 336024133 843103854 732679065 758871771 318327487 447226424 472923962 659275616 970213224 412924253 134177240 711067107 552340221 926257139 67794180 700412597 914869819 334915143 923143245 283458091 343408946 849732617 175996169 770844558 75627283 607309676 141141947 82563403 609275064 986278584 499830207 931600828 531094623 637263070 415108483 824728621 669974160 460975569 80338177 266211338 656320146 996882592 190762832 421931348 243958068 464663359 270542613 636507860 167721851 481977051 365187154 337477809 480182557 377838874 162323547 471707801 170348534 861250297 280949287 864838904 854612395 344598618 842744067 143040031 51290985 366184975 490926310 959655577 521956253 940735017 765878300 787827343 452584726 558254965 622850690 372989286 320912783 524314026 102603347 862447842 67742195 118955461 208569286 219928960 574824283 841490929 359248049 517234154 260167292 498457456 812942752 463789428 680297910 509907557 78994524 173018344 415018840 857610842 384433354 797051014 680507626 579773975 375904692 689150427 568427505 586687403 809141939 578415632 935006712 519236 924975256 607386614 936160841 858305773 60718138 385255703 450357811 349246381 942666151 319745356 992146558 445395606 472746794 448320072 141755259 716463967 517334589 133128398 201705364 885195936 550524427 517558006 82248392 36344231 816027205 363262519 789563871 153841736 351581601 704227234 286549716 981806951 731800233 798120254 155993588 203487874 264375749 223776580 148627703 84526326 259171060 128949064 982718799 165055121 374698557 210283689 62339416 528149280 390140054 86994537 985217607 788015190 43804182 267897394 498126596 418675812 985841197 974716748 536661350 396048937 229005536 745438821 235321650 473889379 616641871 565272291 343552485 611119784 578907639 174519143 513652748 481056254 450556672 62554595 110832558 695607804 895121346 845477077 46062731 123868056 905428426 161903431 960735618 871339793 558664428 346371408 191975546 193686594 213844537 127195471 49925508 818526453 874717288 161285526 221182128 900920733 777118736 787731386 873624720 96919566 574282500 901160991 119444399 350549948 890566692 520796611 297420092 846158393 251894013 993528466 31350309 54834592 956537906 711059992 476118872 973558708 630682690 720328304 419591816 580534920 991256461 282593387 165938129 795279785 102999334 998443203 220658091 658647706 622045848 915969162 208556416 326390013 931925326 43831631 92012325 957826034 206772958 469403185 70673659 165817488 646331740 599331892 245889006 600952721 138764839 284237688 915270537 438965422 391683335 216276197 137013323 345493060 131707699 491305365 399761953 847147897 537362346 716083669 199246017 859685997 692696975 135734898 756690957 646011254 919403649 949886464 34828774 928505948 492705038 701822056 278232154 238543893 239683705 368364804 563633521 325762473 173849237 487895013 193952968 776167683 796064271 813766679 875894544 894494772 113365110 979994244 208034118 782076480 914314812 884372009 374792636 328608343 618315481 11981382 676144922 596576754 828087975 584086218 888145477 316873093 82960958 653568869 105624860 260839428 92484603 848840169 296796733 86313734 657123886 766107776 630329325 16668806 531297718 319805929 869127560 697023465 545902180 719342753 909978553 865200348 106305848 83510964 622507615 690135084 490534979 307490962 798167267 208439216 622409645 501201270 429332686 66199609 701203587 564047454 930646506 631961488 961891877 598069166 756976970 83292534 144704066 511983141 640942748 232452276 346783100 483337820 749389400 947411205 326328709 464244453 373154704 670158481 230029169 197699113 607731109 833258005 153721980 581705359 23187221 938329647 984782849 853601347 858677642 620162903 16798545 261609017 92223584 714040348 516429990 519258219 966945273 922497755 145137357 464256031 741392606 756373338 569466810 153537225 522452223 736350222 310652833 682101827 940567180 888049087 912496516 505211729 928607863 280907651 428189797 33266368 959978621 743430175 134179110 209895060 695556712 207516008 991156249 620393587 360499946 974044281 923017591 222235823 384473326 138215409 296215539 203592856 501107665 35900978 29432574 195166073 142580932 332610995 392638560 600264606 647382400 177387587 410301506 762225288 830796769 391993943 304877913 768105573 410415506 327603505 368507023 518157991 231198747 813950323 989727482 103268378 585876965 263567913 664087621 500753356 912644489 973736873 420411656 32462451 413683710 577028517 884785956 788539153 775126985 737557878 230430138 987023300 761212189 281395428 160876582 503700498 154291404 327891768 822849836 170163521 172311129 932799342 45798050 181622315 928219778 108440837 250475371 460681657 62296038 340278966 812795924 211802018 440071403 87899333 14593581 618861831 783121768 780727635 250917170 471765195 122587072 166295714 378608189 223863872 653569871 40776245 34247844 445654259 538492630 572188274 279959130 191991860 404585706 69799124 290764656 446471390 185638947 350182235 185220979 904473939 76315567 212724868 129929471 150213308 219859782 188809070 842770348 388335626 227038322 635899100 103055723 920854845 410245187 831086161 128923143 388378091 848532307 786082106 697388527 635466439 418698924 362164596 668846678 371030690 709016966 308448386 77606156 693105572 348631511 234800896 930890580 917620278 617379936 193180233 954444173 578711097 24803813 222115983 362871072 821303188 222405072 31591727 975782978 238658850 730671996 273907829 335761489 147622905 839553544 163832452 763358815 129583668 192038648 325270305 539120707 577720434 43145465 910685141 381180764 805099452 38126412 725551511 861982009 474704468 585848803 755390269 736812609 365633898 982706402 64012555 764881364 395021823 434108552 104308208 820242876 812711558 303088430 160154289 626369804 716360663 86790230 987959619 866310145 305909665 42753398 601641438 760449513 156078487 576159523 493360028 976789812 213653844 196300073 315052017 755680097 485747454 752924595 100970351 114888159 209336991 502840798 496141225 162546597 353900031 91948181 542110923 623150647 365900885 605282880 73434839 364506735 827952781 982153599 673577264 464811518 83022352 390077650 691205944 796483923 484052780 639978040 310829972 805738 335571548 424916553 895021708 128966899 247128587 677814552 204046862 200260006 355262220 855908536 350933192 889954082 637262029 103370854 181048835 233314404 824355467 358694372 523219074 33926394 810471801 385845642 827166119 232058738 383949328 195165178 21261117 145039107 490633164 672958684 703409745 642798607 757844727 351813587 95193180 758123190 34733323 907135018 467838638 108039885 234169034 626356271 303870385 300307529 112755099 514965687 268699914 61121252 58907025 234793385 193911868 828050849 471222499 443801675 637775985 262428748 469428715 319519364 263540846 815444914 719115628 621107886 813042742 108647216 939506200 707845925 976629909 292500045 503983026 791153051 197154640 169724534 875375019 920324727 59811506 566964192 54062429 21612756 994027064 284228927 993568830 381914500 754283237 356964923 3450189 27732324 124440292 317889961 367450490 544959099 164154060 611101131 745556168 812763239 489200876 452972000 264164973 506004956 882265888 309539754 893516364 246608350 49503532 528856623 611595182 830694993 798997171 712517441 132364574 2785836 902039245 13335696 751780174 406402788 476444830 91432719 150218086 584714212 475875322 390093749 898962244 742435209 865543875 171153487 612516342 906997865 122188052 887901248 953461629 787566633 733306009 844699576 836484639 610509010 349516754 456310266 496952765 173864484 163394042 682355042 847648077 96525778 670478328 577099796 747624051 545649141 430398559 380003047 875932055 723358877 833914800 410554724 472844097 535672744 259006571 743033861 659065082 272976227 280255526 597544196 667787877 164344673 11127749 65860524 859392185 318566989 89655032 828344757 278759067 729478785 889857412 267553032 772127339 89788169 92390935 688996462 256163855 166956731 245977004 341498397 474630516 841156077 343299541 538105475 107207320 355800077 746118546 794116628 148285632 205322348 711621202 744842839 939569108 322322091 62089149 90762147 428988021 209745531 667342888 581730769 265852267 469317640 872989976 292154373 483353993 66378822 29493780 562317784 431162795 167717038 655547804 726680384 450152420 596192766 872933070 701444845 782731872 615779217 511872328 545652418 76286453 680706150 653894284 396271789 449250663 186561048 13194527 781763276 204994467 301539271 4036057 884878665 45437207 212805833 486393559 174963814 893959614 818269650 701591920 646432377 243238131 841857396 688215229 932600676 947476325 281485586 977429931 723726852 619147790 69931174 658265574 36186487 241963065 513063928 102302517 383024673 700813751 471017223 742848878 897463934 836372238 792001242 318214016 287485718 793012270 820400669 262688779 262750876 85800442 216250862 816237146 503735963 316337550 662906774 759396691 517315674 967240572 660792047 408774063 408954554 123814818 856323936 75989848 684236907 668133905 502728477 922715364 86695619 740311571 891037046 913197390 566756686 147181089 657601047 823247901 367629578 3150906 984668148 146787123 50502539 164364171 102652128 757121108 862952754 858846038 344359905 187102035 731687621 127217000 214039158 111291658 460277663 776861399 739905818 93116289 327674417 620061070 811357698 52426887 913337833 221825971 172270194 455916967 993509121 663197292 918585841 424128177 951944041 210253978 977730041 489282478 441708360 45863360 130551361 966525853 926031614 701999188 835989108 177599189 856708239 883227994 655777241 497745134 66823970 847058836 606815312 948473320 640404487 649847576 683607056 672702035 305099337 714484579 222877524 716563494 736822713 616937696 971045784 36371223 525590845 391589937 45446157 306149244 137025896 840331173 987962878 119518964 376221453 859600610 802020415 942912358 515086608 879838388 642608190 949131593 138958040 682420454 477998646 513630731 978095691 912596313 341622456 184003379 124867887 244825967 262792499 626592443 316283945 860502032 787708806 801127753 879052717 550512880 689755066 709544287 883001733 863834709 989188943 478338122 80237861 289229868 948627973 334465395 248299253 319248168 12412001 191024418 406661332 129803939 533621347 383844995 780585490 530692995 455025629 343402307 884686705 159412271 346512157 309320957 67961886 429003813 566868485 365935020 919829138 502061565 397680817 644241841 688809352 931838193 879152918 349952795 159263994 682993322 85859537 443561661 503064819 356387773 892085231 937375291 548803858 686996085 177990992 772941177 757167358 966697988 152169005 839436888 588313696 296998689 866449822 421700295 834924366 447036452 828979300 867446597 898523752 141893212 394538037 60439892 56739489 615681995 385923892 173579960 228084396 225954416 317737315 43132007 969600390 151912766 475008568 884273578 475343071 919639852 846077726 11750453 712818308 963653536 314095146 397599603 634279998 536593371 500886381 471702120 32639328 237678146 741917553 590453019 73647745 540372650 403240359 2549422 790228774 23383024 718677190 962894673 952895168 857585621 903949349 715970889 309256875 935294953 887767547 327739563 66061119 390438770 461211942 605800782 433743672 637923996 429730815 89520636 407066059 279558921 473215708 344988657 635090836 369636001 242581524 630761877 800451906 722784721 638220298 797591582 113828376 486881363 987840494 604381781 887061314 316944035 107236810 567009819 130426606 433205789 968109179 516378352 993842406 682045963 226894470 875323431 878331013 186637498 871077437 791345856 296152690 445434477 241426300 525347608 573077656 147400576 767093172 680323953 297995011 890002155 879724164 202113532 492538808 927251474 69050960 853352802 540171089 279070546 172157332 310239088 42669762 516752185 623256516 431558965 71323786 483101767 640853725 373964521 363803518 257839889 849848268 707777871 90494971 663857953 793179730 107167267 127560489 735677389 850902679 784265389 909237143 221870077 784360574 994143577 261288885 592671754 390130633 703785595 128771295 650360013 825163433 802171836 532383179 911508972 531501201 495465997 138065867 13323898 698986721 653799138 867245213 359044014 231797908 233949249 851993929 945096769 575625619 815463026 154416122 460268079 498954721 549715019 402101927 348284048 761182800 781385580 209270344 622689010 467620320 780382682 322967854 522963251 418552222 219834320 687977326 568097025 647896938 830970654 844813382 603132785 474916745 943172092 814744312 933413616 760443239 804682021 160054058 272738821 896730330 512197813 517880631 267543946 412204742 571874218 867555410 219006330 288558444 344395010 117259179 205783566 707774495 903728387 162272097 37579084 604091405 738369020 889484649 620148037 757527460 721718367 104168518 605967777 771488788 669407055 789380984 789670976 725358290 83450865 395839265 481903383 836762452 150111528 753458697 510629459 272692748 178763968 263491001 6863178 679893693 623416448 898279793 182655810 868310329 193076687 665817104 248513636 572436758 935961142 85871670 714396363 862724265 609739564 630879051 490622903 521996562 503474803 232892989 590921831 971933208 499113202 88267530 529018884 566270539 980504730 203867229 36627000 777508075 73790770 479298689 142228352 56222338 553989376 832798234 769935211 107507540 176435977 590279457 851287530 790161777 916630781 383165378 507987154 999579841 10747275 573021842 869737965 328031578 482519969 752027691 83436710 29586294 766013161 313493110 436441542 769320330 652431380 105824490 767876278 843864398 533969869 924023021 269876416 154615849 634996161 682929292 325411205 235205824 656278182 630168176 278320577 873316276 302208350 783069925 788531771 891158682 997883927 488038425 575493447 17580282 51851403 558348550 110724930 904611779 813395467 431079603 759609903 549203058 112733954 553968753 891681564 130781836 437892377 667889134 500868289 62882549 986654854 910791503 822777984 393218743 502853271 891539672 909489420 871285050 883176657 680470195 410435642 736870377 613646362 286198429 772407399 32541486 516365499 673529559 337360977 41950757 25394761 440289874 748051396 443252011 953107545 617364244 642886050 481559924 522208117 438531780 804113256 579996079 611082092 392149839 645847560 92944585 660014571 381280875 993458125 282347714 334076175 479729265 599511253 65817904 506375966 244007943 887303266 839507547 608778554 143977527 609535386 279150179 183381153 483240603 781319027 564067529 656114233 682601150 54818499 916379592 161071281 447766237 126601488 151909336 77470713 598478998 242881723 628063307 730801740 492963050 682738855 629773968 830509213 567402791 441626108 391702056 903772715 928123560 169377312 451408002 258439684 129748795 418124031 54942863 153706278 280923452 908063007 890077186 18197745 798668864 477552479 76409468 309048228 987136705 475581952 556564583 994447157 363217711 369568833 828498837 646280308 879229123 597261106 681657721 589592884 161939397 292726513 803963183 290900150 317677714 73787494 275353671 39613136 220079858 169932215 425239459 255496066 212351421 719682195 435040334 304458842 763369819 758331607 81068588 106023877 871800810 756898019 14869719 202718371 487060078 986668687 319329779 375818510 948781254 244842063 691316423 618508981 794755081 977857663 118096074 562216899