100 834131585 762503460 953568238 280890342 860202429 692125487 778640914 542969900 291015036 17581174 342125965 353451466 157078698 234084766 512779690 832291217 827631377 19910368 496624466 562633015 823357938 170374744 479986129 534412568 348475356 783654551 127101799 245267998 12787092 718425573 353092488 676607203 822055593 725551600 345984723 409762305 818975185 31009369 690066537 4010 439322131 899835314 42651382 530988840 709522172 317427033 567675154 715542975 465092545 43917725 976128690 643370548 748393568 374733933 345001701 886539260 340604698 256180615 614689781 362189772 154885105 358369097 541408604 4281674 557746445 432110172 659076710 484731912 851652730 952341329 659510352 926766902 903652859 655009349 21152721 356000586 605795781 471312161 31033652 656109498 840773108 296505196 126943013 49351514 492528175 732141512 107314628 842034199 642992311 509805812 548771780 60820751 39947286 476015115 750777465 80494720 531732963 45408728 452873827 691909399 893691734 589110428 784448159 312297452 871650453 546829398 204224555 677393716 490935303 727315120 368846008 515591580 318488345 723497832 301898393 420608319 282711205 469682540 608116726 564899004 550018079 716728348 61550572 212327568 311725293 158019127 351360876 798408725 113526873 298940879 557345417 433290130 715043716 221084813 136011871 67736256 243710078 795379749 487626296 331596669 175462532 744277456 889781770 723732155 297725213 491732811 758235361 476541135 517932829 760154093 599106406 415201659 704780759 694555052 180251636 539971240 531571691 838380837 252839688 911973861 109123059 752517387 849337196 204263705 329851111 881839692 767900604 691480137 723058886 835521346 595144387 465252813 611145050 698237791 515869486 900387797 402399608 596019626 23322489 669791260 594119469 205597509 547082728 236568527 720231949 143696708 245253043 610665277 456609419 21818522 729947484 856234141 850554118 612251183 523801566 387248122 613138751 369957612 277835680 432810780 453721687 584245654 496174479 422920042 142966053 681175156 69158704 197606797 185809796 365821936 834461364 363340321 479578087 938171774 118732315 923528437 957683152 406615576 136506462 138060253 580769632 364719437 539366698 289858126 209995565 829926450 133563367 971642381 920799103 814342156 123313178 1192294 294082091 887159393 555193253 628483069 701633593 472372527 286697978 919839721 37195926 625377619 624781699 541122503 542755778 806198989 57688303 863132411 554556644 890491308 327205148 454983277 810408674 289701308 354623994 696670206 562041046 195744401 519784854 494251157 941972073 441296366 593237897 446774999 650819517 398060596 425993550 577659205 135688982 995415208 470463444 163096 723114406 324065669 510151161 424847267 604549160 426873491 797420358 727561139 8278620 45394359 553428587 175809238 717760757 563243981 969801803 249192641 846846080 980464668 776760464 336556843 329987261 961490454 492849042 909299054 638493639 721213217 949694717 649369387 993935602 931242292 791840275 832115603 604939506 681863183 995840949 484016737 836326815 555114691 515923999 355981573 530492531 214195268 320378954 276797406 334530525 4663603 796292497 741726382 200281906 213682780 496149057 109144434 661477203 355748924 866470845 360372531 686494149 739759696 225926495 218413918 366503308 319266573 237277222 561467234 460523778 458590082 34822749 618028916 451919093 701817822 108607830 634840157 606112594 689681681 815386051 38892859 864091794 631984355 935930126 726538266 974277237 284419290 45637299 554237742 902543789 5969132 541479936 37818249 811175549 634190752 426464745 671965340 112847461 693461723 512086271 487283243 524359942 597956916 435703700 143911637 121331389 327005911 35731376 502279893 36540054 126681548 112541679 341751587 28143107 120426651 688023629 884643795 937238604 831955861 211251192 200796199 878379669 893716663 524268796 540506781 75700464 100690599 873476313 799899559 472182204 610326228 959574660 557309521 7153002 840017873 338235193 65175137 204674093 797783701 17091253 140828359 337867597 181079040 496701853 537542101 523526636 877737528 779612475 280611998 320897406 787092675 48957103 415703733 637470148 397773531 908618616 100637896 587262627 844299650 236790447 548631560 265645638 363484482 358821111 171002691 870966749 513243509 828225723 181049580 83451394 202887689 144538925 532818812 689857208 862656955 672856351 822744687 880014384 623810483 461338866 327110019 565817673 253393631 874074382 570931296 284524242 622564129 744338433 933618985 243315100 933428216 71891153 325377993 450393996 161213012 18593362 970459404 735673746 843421393 247954026 39824868 898491554 722761534 24887781 175427558 387289719 422346034 411897786 577706757 989333902 369382095 396677709 511030766 688839402 157759235 13802488 463279466 538667003 548532623 416016771 77673372 247655686 666257065 493025636 251886671 886064686 384599120 875941497 26966391 670443604 756144541 352665371 536785203 774466651 301837936 773610816 14655476 890830816 273652606 906330747 823802635 306525290 665369343 542926699 481295063 577511513 177122290 200608805 137335731 946798391 270992460 697213725 739159935 762896813 546645443 464540986 23439101 866133669 479877963 865903353 99845272 68616872 393653592 843536726 126288113 850202516 216652262 825390101 928710718 388975434 728599548 582497031 799687872 554662729 626058522 750454935 111771179 982460795 813520817 60850245 486407379 789569171 141180151 417831224 637511394 375179992 149803797 593317417 832565786 206010114 244917494 869367802 663285064 52732290 794743101 103354891 646349789 813834069 507348033 690673755 213333644 731438788 936905738 380304988 90205308 713077991 474421956 306656659 685692659 781989878 128251163 135251783 328016726 927365644 852754059 860316047 336925932 1017639 255046759 387304123 771960076 274715058 216900380 777136008 468878977 180725621 901842788 278015408 974261799 65862986 761911379 261627289 2342466 192798760 149433639 929980641 622127071 806973201 567725628 939277918 526311114 265935838 605350743 210450259 76991672 569798478 374860536 636405442 901906568 934317115 444401945 621630055 556866605 246932740 630787182 462803800 271059103 381886707 571816356 107455786 549776723 348265445 955729581 564481608 942636393 483219866 709715663 159240722 251892001 217979351 311301802 942137403 423812963 190226908 328800163 528655328 61369068 968147009 471580448 760810683 510220424 749433156 9600833 729263121 633510331 955254450 115926042 913967797 114512007 439755605 144768287 185594217 182787787 221032754 379955735 927840662 175454323 991429890 231500370 985745191 172507608 296785772 88013730 51919713 301547844 590022842 142300299 880706146 598595235 723565708 391135621 542119612 94376621 264047447 296860831 11004913 48704479 655937172 760635899 711277807 662927774 212462935 261109390 771935137 580863717 399628053 712899802 890657246 269186237 756857635 921032044 97023277 945035159 556010995 648443232 163004235 265979390 565879419 738771652 571317820 903643009 293285822 698260410 601282898 626371898 126681911 569401978 815736424 268409366 802472189 270450341 669783780 470029303 134533610 916407819 660206384 76832046 375259772 403482309 542837631 9044416 418579614 504874437 736036421 604546223 40412968 717435242 164203311 953167916 432045719 552320035 601035221 824096580 21541710 613137531 771759770 840771607 203754980 881229633 74874407 181262489 696262528 995699669 165624924 850760515 68114241 140895238 60548388 874297473 558359597 146014373 517037657 850534772 519440247 161323309 589137041 598925392 706585815 796936394 407574335 491532426 404687270 236575401 446119182 505850414 877699668 872343520 780287343 282123984 756006266 230761338 251873035 467817557 50402531 296482842 21720137 807583011 669637962 853938922 990248678 18733877 745810928 683357136 346467560 561017063 67286732 46285 476138973 357206214 640883820 34977415 458448972 164220177 810730651 146305872 190141329 841132780 887348098 920640313 683028387 546533130 976743570 935672607 305854859 748507567 783123488 311360734 330879170 797511170 522944801 835877278 287196598 512184957 103276674 193392948 122900652 71040515 366197381 639758012 14996214 182683864 936497529 898317266 524767886 540899258 380066938 247166719 940896704 63366950 733710356 613622357 311691087 405856759 594031313 253824275 555274880 426971351 409288102 836109174 5784635 667530898 861379092 82347270 557025123 691932767 112274801 940815044 230551410 956765182 333112066 228493331 324073077 591241389 248751122 565809572 973039 804677952 58999002 632370589 569730927 383020517 549314018 706029674 710669049 810814551 603276091 224396202 188103925 962577031 540566426 39108737 761399767 790607110 17920851 328672114 573155100 333975042 683044868 592841537 67412289 890132518 314726708 928207054 178383220 338108674 572410400 647555651 825240499 718960709 838297849 734343672 161999560 151489640 688620410 815339742 631435484 433147728 230760487 669702229 239749389 284882894 595672375 294273958 96967022 718864065 285927084 181579211 666087515 124892823 70891443 721978602 976800332 823948842 734964279 323015835 598743509 865103334 542483733 793744176 634856606 987225732 789838897 696354536 126568804 460824137 512269218 190282980 63358985 733066506 728200771 818043964 586467762 824012704 656043737 472507735 943653407 189314738 449043556 674099820 319517083 654587693 380210038 142786578 906201328 675211823 576196484 316922931 981013121 921025665 955014659 159866147 598154922 461720497 363791432 837034168 902708611 83480150 446635136 438305466 716617813 313741833 472385128 816006876 90043937 586036213 907237346 432349502 74653594 355239127 507116481 708072629 627965265 73320932 956370198 795158807 169754161 772518207 292821696 409971142 465478132 511556085 856406956 993559113 11246459 160331170 771008066 179477465 566556516 704846807 876884815 179698422 147341304 774999949 852589038 723838448 799388026 231565700 780150835 364859454 949572235 138608856 472913508 943929183 381653304 687541098 633466554 241492481 105459809 143379195 676813163 82844402 339022721 260972294 421409087 503345828 217673863 21894300 877318827 552615303 108424166 560863939 10248614 210574963 964814860 9784684 433274336 455343626 607653660 518002587 952307429 942191368 478704994 26681052 628991256 573385712 815628853 999540117 939844322 119870135 753183883 331833229 102456103 528012125 320595056 27311272 249866868 746607739 31072786 956259651 853922739 505075904 74260790 657168155 136298279 324426087 919453989 380962915 461600080 483163626 849885266 341955400 899709700 336738925 90633857 54595923 295001810 554992209 791083058 19469457 195308732 853315247 426630326 266652682 991906181 731895187 411982851 37278125 430245982 492498549 409699086 718104223 875599418 135854367 535029210 884716057 817591459 484247463 919927031 841617170 366923873 160640456 358177104 402795224