8
3 1000 30 50
905041911 334818319 462753816 907756353 535917728 673800429 784155571 406221556 649742908 189785714 152245975 665137124 413735455 518485069 695333272 168006457 653223678 517179029 262623630 211879790 210095970 641545419 46765107 289178186 146695457 436870535 952142481 705616006 272654877 218564109 940987000 38523825 643049455 335377304 865207338 915589366 801903146 933932512 956823982 786879914 185953348 102979724 933088608 579685332 646093771 142711430 563425522 663327100 425278188 792404893 412915412 86699279 754363284 749445845 451864022 195605532 728383623 158345209 546128845 469406380 830824377 666960728 926345017 215808042 131898541 636681236 961226314 510479844 413921683 571073169 311452953 274414755 882503731 765618430 335111079 951566655 763244270 863095385 469310668 756611150 424378715 733652684 638782801 320992016 742484063 507184117 355328043 401168671 64615655 872464110 813027913 488905565 186971850 21693410 897162876 215345325 708298665 998687611 502308597 676748363 961175801 936056532 474373252 552730580 396557195 810689606 543483397 274458316 975782107 367189935 124374712 773910906 317437339 659405945 466835180 784043277 134174689 393995501 681752636 817362319 212110158 135714894 981901611 969512618 724933503 514345159 303496132 321875817 755527974 397147791 149088051 770036477 302531468 407575235 358878781 234031758 922444167 373868883 232926292 504566154 121446597 331193306 486862606 17840628 133837559 536576294 597407215 101251565 888416154 385487344 383396599 175101610 903744177 714767720 79234679 825973299 117416995 475495431 506981972 289444172 333571692 392088831 129009865 230269067 399046745 185383234 784696680 579406415 540860355 787468587 560530361 161886383 249002193 274910674 690779502 326549530 351180867 757927305 550697010 927613641 216691210 981466496 503920833 390670654 494204763 786877682 325548375 454249423 705059657 44167736 319033058 316353353 37173077 556339776 270547762 285338153 994354774 677259674 36762021 428836822 100014913 151270256 26727808 628037884 215294758 762686415 525440825 565671685 377289205 838749227 541036001 785699756 749833768 377304227 787242382 657302907 855833301 849842951 783404740 991928335 589710216 627608111 659650129 155905410 69879020 869621234 418670885 769316058 936767280 962759482 967570104 245367581 638216515 968783253 127413419 827733541 144761282 899316133 747146287 554706718 904394710 911030375 746030192 782689775 5642218 235335899 527070249 376518190 207154972 932331788 977406058 308201417 85163654 540772922 569524863 382947761 614766566 416517824 52632682 887886619 353284376 644378824 395385050 936717750 536108517 232208091 550517606 498583327 448679094 93597511 505708855 634358941 798557527 806322698 191093711 486553239 874862934 544326477 59245853 308749267 103482285 217612551 644462315 954615074 22446847 679390551 945311962 365537558 438003623 580711677 863133040 710657057 604979754 23987871 192010985 177933339 530323717 295261903 89189035 948205863 403263379 55456884 695927255 56930749 706186244 274103113 160070856 326437810 401201286 873597157 743400100 654099799 261236099 664143602 328023225 52289869 162278343 902813527 898046236 713775222 968552681 694698612 937048634 571579379 50989210 730857345 648782819 646697245 204923482 247525694 677427573 964149082 926073479 2781856 137541555 909965065 588542522 698605584 250490572 338707689 462815826 549546423 801381423 541955090 927637581 335595332 772732111 626584970 245052193 904351322 569621282 632103931 170864944 962160429 180552631 201276428 201770851 70051586 720061155 21580792 667607496 407298262 274442111 495083099 898617972 979349429 789413500 67590450 815804147 735656881 991351228 157716560 793466025 8026022 941779030 55761428 617285117 577639540 37990825 862454819 391756173 775694700 276828917 14205658 577404928 475546754 849260009 602658983 8902551 122336164 112437865 192005722 522318870 294373645 441840932 865745606 202364772 560581852 952445897 313845824 516536142 541595947 275889007 990019076 930289769 622111617 886725947 186842721 426801446 686612697 276129007 202254822 685425536 945721452 53615538 148324863 158682026 478503256 230575378 831295734 505072041 632924328 935602501 425701822 267575222 846748428 113199766 38107547 961139414 561560894 451729285 219211693 189217443 199642826 832141735 608809911 480806336 578115454 806671204 222241550 470890512 866574004 610046657 763781880 694379185 538945122 569550424 281957992 503897414 958251029 821683200 864001165 121668919 985413648 164037041 107707215 766212390 462479708 275208354 807367922 255727626 236004998 931521714 88295406 566942368 486240742 634559371 181947944 69981806 100737346 782716896 733728618 782739807 245885588 818426004 143081812 28903539 362357255 154067556 643984570 809992328 492143707 237972226 495343697 621390377 202161622 483052445 484888694 50876753 141958607 986665641 768334001 522682770 379113102 631424762 2853121 374342696 851158246 637249376 714912429 386081637 223254963 16905600 574642303 899050010 399022048 796264749 161099852 238443017 828931557 563212738 625325551 35169854 47021355 981113448 613179473 117695954 788829089 318320255 273501839 947273395 240120381 369869188 690655643 54552551 686810259 433631480 681745497 412527733 872797663 172028493 152993202 175065954 705339422 639949193 504674001 268916966 132933439 413501162 254409994 260555788 310796155 631785048 501609827 778518537 327717727 953192708 63303249 214655532 27267847 376649295 112694578 973595336 300623901 631254877 764744599 375082489 925884332 106780915 948162268 997127509 57970164 435525974 421403569 86646866 76935092 316935255 350755126 866199072 440729826 364392241 412379123 141524106 683109386 429138249 598256032 577882524 956947757 373650895 777513270 979711209 153965514 384790483 503867230 276280300 258681789 916824249 378407896 637931545 315574800 845215868 414799628 307178469 995286100 185711723 241837810 235906150 688597815 82895322 842289049 896240674 746555329 765719684 182258474 952407114 439440751 191220879 226409468 786055980 666628261 412904423 712036483 924855807 342321817 721678143 236903428 58930626 65116460 673842204 538518443 557718686 784441017 230900841 700735786 364710826 468967802 696849135 287091761 462327264 43521878 863276403 975280853 963802527 996130357 510282770 942795971 446477906 173901167 797043618 335891447 848699927 534965195 164163774 264339249 844728555 957962586 121424577 126595892 669512845 28409198 869007339 102404637 148607474 44629648 974060017 37187976 920868823 673144506 117431243 145852153 278940935 825834501 417494712 584273966 410843901 897565170 847512726 637718957 829958863 926308178 543378092 129297074 357015502 706355828 399630053 746643270 827367164 309611664 508244076 979322801 257220845 32452772 550219704 972193804 71845612 776337663 216233108 905097403 827317140 547471199 940058026 758937712 597813816 237267302 572731606 200162741 580262705 154811659 360611403 282783342 281365657 825265121 876610097 600692872 112469187 909153569 351028967 221625490 594457324 765129789 604764668 224762068 462487663 926378682 157588028 75184606 628919038 99770427 305276622 604692720 271529543 890217214 472955547 940804867 858140475 945764415 362134855 599529462 86664200 376337721 497607632 115188687 243544904 836941467 866295354 273284752 244319779 928143156 997906082 89331315 876305899 165810064 786244433 214160188 810479655 775220538 796547805 476745503 669107621 399009083 393417282 330820998 906661536 740403376 486875566 348492600 378780166 91563675 633494764 287060933 343942934 98085516 376864225 950034850 58435892 276053686 58616524 365995305 958232877 167431438 254930242 506162353 443644222 19948628 419416527 365884245 129188097 179236620 139179219 828229844 14673731 982152767 78242390 899147994 993585422 712642119 470019864 656681145 892479815 735418484 917727894 520528538 856503974 567457925 886992527 880004632 759207421 262239233 266751573 393452769 14450099 492704460 154717920 952924407 842788550 82969620 590556859 156676300 627869679 822752848 605559241 73564907 184023375 108001677 600048039 290193658 285540794 913175733 118197480 393847221 15119777 750827793 964916134 503093899 753016792 281377196 80677807 603709246 289046093 970656732 699831464 539571553 168670482 634793520 668500346 226656904 439528913 992289924 874569758 880929341 853241775 728177573 634571344 819864953 739605423 837873233 849887464 979087473 89105722 471554570 25280978 123257010 149801794 466841023 626791395 637122892 86687684 676131474 130017495 697166288 270678391 116197662 687018376 501228883 447910984 772420819 542380600 739309023 795187298 786056084 877970104 65052769 290810125 969864338 467989955 326811588 363967619 488104366 183702895 563810748 147348601 676775797 580226539 604756095 543432651 557208918 231395676 102208286 499995297 755363788 187271024 423848775 926858986 859267475 839133457 233846525 344637305 649474581 850681128 335513293 177260217 929290425 980645396 864841805 116982584 248424144 257263867 924265712 424932091 530323817 2762819 533382666 455209787 45781569 656668856 279226214 343691451 244376773 671436879 747355074 602923215 615372152 156158207 320121009 904421437 77943110 237485322 513002350 462603188 882528432 909628368 40197349 654858633 561174616 944745122 145241638 583569982 907092803 947880762 938220295 928816903 385144093 580645379 664580629 139419909 963011681 882139523 519167054 142157276 747936100 161569430 607476047 802756857 648497811 341422000 284122507 615704434 858263282 670166049 135451737 720990006 898883399 6969049 347856078 880700664 88586158 745872977 222487718 294906140 902509307 98449351 870290902 202833428 739221842 523158752 695197185 441851575 421417336 342765142 422357982 51300514 505215239 550410190 679554754 648576642 275939608 64733356 775453892 447705914 402198762 386054490 89730885 849452332 508626340 217958330 977099722 540638894 866639106 199414142 965758084
424529038 67951051 822986423 769995649 181861926 359998697 751141262 134567698 487363002 159769853 411777316 162407106 161229057 142090589 234115120 99783096 103734524 619548898 572223855 403561953 978196300 570945610 69760179 910176549 592402131 414510392 170295378 298032513 710487387 913767453 732279327 479510326 849320159 257174341 365569311 796290489 941373080 512790368 556674971 959991776 623246522 869370175 657811276 661036370 576348699 651097249 515598221 158952403 894882564 743515082 346757981 833511312 27202919 283407245 752127272 339515482 463892396 128643768 329108519 556060332 130258189 207614914 211474210 594904082 83216188 101472872 431801190 7993185 280513232 941987873 327246846 51264969 95211407 295488652 225318906 265345130 53682874 543253419 532549489 466774820 783793071 612981864 232868365 604232687 829405935 566027310 195400591 234853660 253379663 210194898 683293098 780385246 276287480 645960335 869118292 157423123 971681426 585574646 551566021 205699876 689415348 72045293 163263663 57765868 271358864 316042702 335609950 403086185 281883635 762666406 606847677 402898084 515993712 513311772 500888961 355160092 231114057 910713721 916587700 491416714 238672052 836280883 267473896 663785754 585549643 966705072 383970445 974523239 514172627 377512055 214215808 136624476 292282522 957011733 596357658 50880141 579620747 583449364 310262339 131950236 79780883 146706176 967532141 402467776 576086836 47889782 276029960 501537733 679763736 573475139 800372681 226355673 422412633 411960903 993330850 832278421 602388807 17583684 59991694 30979221 947798687 459393354 919161298 597931540 274356544 881355834 217294222 112990365 576375126 172051833 879976008 21578028 797825507 964603300 622951614 147678163 882032317 528666342 992982206 159934592 426719989 427676692 231957732 874363253 312400782 742487056 920739900 762917309 886046860 183744950 945974585 655132032 503229158 660183405 125437509 518004084 437161230 576039837 653859843 298777798 655324456 942182349 497041080 523249659 10697973 462093097 452288653 317507635 212724438 281662907 583987207 496057850 674443000 12808797 761127491 566947620 519220228 517485584 749519708 146506303 450188984 703070177 966238561 458893254 874542729 857822170 332886920 295689585 970973072 200675345 787245614 972968181 868183713 623689383 807335344 344005216 970803007 842375993 583959302 934462537 409050620 426321406 97611402 975597940 890856557 762068428 193470608 581789334 599923079 132582865 343707637 804390802 234040100 484336504 550038758 219372601 492223924 809641728 373188424 930652233 943521772 893530085 759243837 241095217 87861517 83785385 7178560 641393355 311069314 121168804 585597502 26297454 299233584 328259025 408557039 984994269 578740054 876700777 207062323 608504475 229581649 9039906 78728169 753165480 741956381 629052212 396222241 754915592 954821059 751481581 971669462 128389371 262875875 320220537 562944154 517974461 829165251 213443833 956345775 23955129 645992106 721249570 607455179 790946955 705818671 129261474 447423315 899086419 806205165 794818640 200073048 537305165 984929820 645424951 639404410 954893847 461533326 116305971 721988832 723139788 379467280 839911246 498012815 163934278 238378927 308670892 157273634 881311578 28106438 543806036 233173725 515090489 846510509 699729263 792714395 344231245 803942551 420447271 147642897 703501917 755057020 453972031 541068609 992926038 938005770 666995835 461922964 994701648 580525061 529901813 44725939 78420941 542234713 33373325 112666501 639265246 546683431 812180668 575171226 985404373 840307727 995777110 622595467 51335706 780629260 761724491 783449904 443661561 169365825 632535394 617282722 194720814 879552658 683749106 971998533 851586714 788762130 896209662 775754978 511610520 525648843 980345600 314330437 366448926 17351127 65585014 979436323 266330969 498904722 677248082 206073775 795201116 995329453 320326200 580216954 892260519 602599238 869049842 725534253 366598863 595836697 199650284 455865965 551790215 584448216 921022130 714774478 290561921 740145929 623206996 473104732 183070203 352032357 80315253 63559158 908349416 72537111 286089028 856790684 789696984 798171303 771372580 79977059 597381183 301112806 779476832 561598250 171362924 847927450 525161769 126716550 31410954 589704003 711976645 446717355 82860265 713364693 17272430 702133069 605578888 82888241 223817521 921431551 969825048 953963761 526478043 975799106 748519455 207959221 91654461 322521866 730316769 232849455 859029530 78544867 467337316 928088622 120762323 975625708 736991470 211093399 720147730 458079129 220837510 261188479 289789872 616980587 448133575 890849907 147293379 633654847 576647781 220334785 108008203 535923979 640434112 192295083 249623014 717669011 624941081 307172779 796299818 732954879 605879991 135849752 927518096 975931054 86667963 315266039 608005196 186809491 65349471 636112257 662998437 648818059 149639393 402501736 179477878 654857194 565098073 725951965 751618268 560080084 894353582 679818063 124116815 508354608 27132290 950703440 564720095 726655057 690168668 240172828 131542282 69684716 989846435 232542051 262958462 168308017 195423201 125736232 575892249 241521219 67696662 801078625 883876389 361951937 246671613 856722763 327358666 467491198 353810537 956719419 276682497 486312214 819532643 679511897 900007910 603839682 943721316 482984212 353716488 973041065 925578309 631990714 33939695 130637056 591285630 209960639 867717002 235226058 4008895 152815848 640238295 160860379 197473361 259713085 109657644 81332268 688512082 751669484 562509772 370440042 598895454 110741852 253080334 369873210 278389989 424802790 541327150 126314584 299449660 839246882 456180528 542209293 665330793 457069429 438060865 293458927 297581943 467699673 251081276 340715711 839151483 668381113 804931255 797113126 393216003 997385443 606967147 597804790 512253115 855943355 313426339 563891748 60993528 768170847 452939058 410357264 553346289 93061977 320361107 361879647 270423161 483597917 13869787 974747308 744129682 195133299 560402941 454767233 836793095 595685610 755978434 812711164 33028322 894689697 197163331 604378634 617085478 740266592 854648174 454065362 271199928 441058009 549759791 298609046 271557093 184771099 494124616 424194968 882293136 519486205 679786737 851191358 679218859 857832751 646393319 982033974 357724716 963794545 836129414 788819027 307319081 178937531 932845553 542019643 500041090 588088828 877295486 61941058 478992259 111094216 596611359 109743358 909200860 628702227 397704991 127730780 29565704 318281832 132803961 19466526 262988088 607375 297591397 681459416 391720222 508999185 942001627 707320539 987509760 818894212 48896440 26261152 376249247 496279460 709733667 154304985 355739781 133558210 595301140 934474990 660783653 966503466 648910576 429660129 58526263 247886872 177464236 417204056 168125882 872042579 407725932 782199003 39937504 899339805 678920725 986669327 81701084 779448087 570812842 995283174 873599736 227078626 531835023 412200113 570481793 977315969 787288815 247155147 16677829 325954276 263281228 942490174 704763134 17222042 515321976 986858522 325447836 66968917 814317311 447838242 551465101 700848479 680365196 878851486 171861352 53584056 954471352 36572461 909184079 446279932 282233322 148869034 112658410 170370837 704155305 412253361 129803740 364444679 191979144 92311600 214599858 764383661 895188612 743599281 599586818 77281027 781694596 245910501 265257226 200119892 580000075 511248006 177823370 514628195 693422589 141149071 912552781 584155009 81353550 716934396 476630681 522643083 360873054 334281272 20064277 320916376 119340101 595317390 30379860 43380346 576583804 835993644 369468333 16387212 430417893 551233748 365418753 310068327 988595557 231286187 947736750 875343175 377598927 129134228 553716787 664716105 553103953 63715103 653151365 344244552 18126835 877268472 156671715 791513959 81353622 345513709 973086620 439940833 964770436 332526682 904847292 788075949 918473936 944251520 426030249 406249104 913743673 815705432 174011438 107201247 790985771 452885848 691880643 614860593 427950007 662349990 872767090 768888877 942404053 510788185 450577113 426641788 98171405 302361550 508348054 231009958 350456537 912361530 27073694 780299333 455837119 994177869 82053320 459446807 266728600 404562740 685893072 29845758 795667868 847773367 245818141 683707816 531124346 223877555 858621320 908012777 542156415 125001266 753985358 874867968 288441295 386144529 843160981 580176693 557011263 368219691 116548108 969074936 611389235 327380229 6111305 487924869 108885835 805672113 18342766 301393876 799566566 749187230 408186952 411571624 826030885 148670654 316728870 61402965 936031425 649681367 191350176 480807307 830092267 924640376 944094815 463198725 234385410 658429480 765358477 384667240 202715635 742122071 688442589 32089020 390075708 999815290 97746867 513052129 90079204 456274925 743860520 361545558 362125377 779357764 654974634 411606172 924878680 705726279 97416120 139783745 296221316 303245016 314555798 48975851 498838259 635080791 579858620 522041644 117538411 789050412 23306992 476263701 764349822 820544814 996072932 312080352 784366340 110705953 375055888 579465562 773553594 513226345 321496425 446112042 548026513 378491099 120089274 278448023 395526227 865814694 953194987 124549227 424641627 802916562 56459595 988251877 348508257 705198675 848185010 368565869 748730590 906414816 915584895 888438895 133849453 575024450 487684453 67963801 242467804 686412288 323575523 752896865 931269325 868460064 869884963 200545909 522977128 685872003 735616482 190682872 230733621 387310875 468479831 591319288 653859124 570698725 325077147 645734611 941150698 177471754 237458517 972561384 500164732 421149912 524611243 18976657 233153543 81578607 322098855 341060708 928527196 502051432 752070474 902470092 434572786 20930352 797070882 417790356 860538593 120522766 455741897
144271276 423934163 342257840 818795096 654064685 13603195 440344916 820328009 441177030 733448365 760482059 234629105 278806096 809193419 650755728 948908593 693345711 576369428 644693848 963083837 718121724 533400786 831826306 793010441 706444823 434465833 337552931 727512137 418847300 224589428 119253840 346503689 345475472 431654275 649495062 329584402 674262531 803453961 397737743 467649492 273398384 326787928 223301248 337864818 73161878 304626359 117836860 115230554 715467888 810554037 336853502 236393381 799268669 630904003 50508759 60412095 550475762 47200936 459380587 423580232 73587314 884459180 617713136 803965239 469802037 183927834 902547283 348303723 500828733 486164067 328442405 142213219 188884009 296638456 825630313 788802021 773841781 93049495 344015694 426166073 420117401 31468912 1878966 682283231 730266699 610659014 686334600 826488970 850515767 494448571 911199122 365506796 943457891 33212418 196888979 465295312 7354900 247929589 839958722 107543730 798816549 764357075 626646616 457338233 428297030 472727548 860314442 867246781 152530810 270513713 335705430 327817507 241136418 685351252 88879744 101426789 779036234 780947869 119671218 523945195 403176397 490320561 563037389 789016984 833101613 430194628 553805602 406685614 456896759 562902370 781475170 100571262 292794950 198146831 966583552 500901340 120137539 801235704 276158959 947713302 338636522 560909127 550189261 256075427 337312291 376386450 375326255 451663943 760760733 730335241 466833398 747384538 180964582 87372562 57680499 426288847 881764710 957146211 40465045 957938056 311628333 902070955 125584720 899937374 308254065 583248991 325367700 223345853 633837429 905306140 222723451 481890728 402747230 705479443 169247199 993022331 734901675 889662003 64379688 314819479 739212480 396481577 183783603 3227026 777436342 805788400 231377389 330408800 497174223 470304066 886272852 140796082 298122194 347586551 826428888 100563644 421851762 394743744 255494152 427410369 715429548 417129173 322691621 133513469 425982723 308927202 769494511 157460185 424618496 654038447 363260480 946963919 615946673 880192889 807264024 245972499 875650242 965156806 548936450 11921250 67552043 412019317 757025169 155495233 446241502 293292107 162594855 598381253 43528632 549087639 112484006 476457000 13784877 716572701 832763826 703857728 607841236 336848984 124694984 695862757 445111270 517929347 637347821 788233080 354049989 910454786 461634064 792189662 46915848 814804744 874398250 777287177 559531915 949269033 722529755 919305984 683784361 910796736 152819758 348647862 502199481 369563991 539482890 2655864 289720987 477999728 474579582 252452689 447794929 830283511 641539313 769163527 41731909 148327595 439782355 432458674 425226657 4230640 327179763 426516848 321313516 662948809 480527193 731930170 386087750 288289576 935854558 67064516 673807624 879252992 997817164 21949823 799157885 838265594 983566886 767578898 899419832 381159024 449294786 898566625 922117572 68637505 559093476 847487057 300959134 87300210 863171918 736833481 47309274 36229781 765799895 593840417 748212182 649927597 63732968 215508007 702966455 880163338 537493965 449351619 664735562 487244307 58233558 936483122 601697269 798020472 409628061 148374647 976208030 676717215 508974887 652252581 796559608 583763521 352576421 307452492 935427638 323812985 78096518 778243336 136250144 509099117 306584058 376028531 432906978 620904498 931572309 508333438 6598919 519384436 738432810 295139101 66027693 150809248 339557612 669190051 641185198 192924099 222732613 60185230 893307031 595985420 851283602 251621138 200677184 707022286 296499295 130679878 180653783 238952196 72776405 303816968 18838581 139396668 442564451 608546731 215825126 115112679 945808712 850379005 778669131 59999913 728016461 165441262 123646394 654331705 491310951 981175139 241223551 417147419 923018792 716184703 54367299 59518695 502234096 225530912 244623580 454817195 251486771 760982578 844998634 864777639 149904396 327189569 115757703 206665327 847048646 324664000 505943690 372925258 507316245 380383049 56679023 223379349 963628590 875379549 676816814 307861271 836993156 7821982 767569043 78404529 91737215 342122431 55747810 676518362 939387957 510551363 943640010 413676095 847165636 555126954 385512880 514874410 229121361 258778014 350114916 893147001 125638608 112779636 670668515 241972474 324817057 230751433 378546939 636996501 909620986 664777617 523013342 54295601 942843155 209562597 888992984 360412340 859791000 61219927 970751833 350412973 424417155 804116710 177981909 319122289 722617403 579007029 41074328 999564519 930770460 118358232 919518796 508831309 906100392 215871963 227974533 262032865 998168304 363654657 987765289 145222579 751839387 267779994 194055933 108202645 80910673 814440231 994914885 82500984 502664377 40129764 202207236 186239243 308957356 638559871 2557912 302423516 430959919 299098522 977097733 393961841 906650323 695118410 728539394 787949565 395534053 206730546 108478549 117614113 759951260 637492858 496935217 579948652 783632509 261622386 403083727 578003066 623849850 608725565 986800410 564326367 244383742 792903561 636746760 399786784 786764958 84474698 827244268 945746775 940757758 301472720 916730307 880116128 196452280 867784377 644078502 992210018 676834516 269358185 647288376 486139973 812007226 342102482 395749676 440668081 983828226 356664617 84174579 390049079 326539332 638073228 842822920 902333639 28697024 841643748 567253052 354203308 990680480 770565787 920434359 481644361 704934517 372492073 207130828 117666043 882109826 81431912 334856878 473962483 820368383 766242931 747025274 372882593 712439087 985064936 226459247 125519279 539623194 17520435 958451047 410938074 517902239 624693160 489101961 735402057 636447612 538137644 103847799 135283634 860759505 735322488 748470488 419145457 61493320 897685080 219641091 272553394 211597765 279193013 580136136 705632195 586205710 192423840 688086995 101549661 538737211 505904268 228428204 941178817 447433500 643486899 650109516 607988215 137176181 909191141 430554753 380966650 759713217 879570126 572241407 222638238 500510539 689997714 170045196 231981403 734361131 254481525 304409706 840283714 672643701 334699570 949317827 558477861 863151656 134831081 428295071 835823134 615757821 770684436 166045989 239320930 178830540 815082650 347392234 32299086 976500178 209982196 398509624 19379636 421309523 261689047 963966796 364730812 195044761 719403469 192536056 192548605 304508268 527394076 150480556 848769456 414651948 622324007 520218029 114807934 725959279 949649038 777243787 89465400 277537825 259977600 312518691 735087455 826736057 793983787 170853135 639147449 543258160 158150722 788872730 459177430 955325742 528784810 393307304 902210708 502208127 897351370 682049593 795666069 668974150 680264839 109403652 88999218 696206583 410803139 818587846 445842904 218529886 322772230 53676337 258055481 976503007 169283222 859258159 896588414 411680661 50499836 441227665 595882441 932539947 927295088 748161912 166723342 990234686 178978301 132742202 318224300 869041159 42687368 497489090 135129573 242370728 625313166 680138813 887890999 578751567 849989141 324129928 260922483 178132501 694800471 445571881 230142645 366377252 42214844 456281581 143261394 832214746 417338160 609168361 78192374 807896281 997465486 95881870 840854434 14097172 289897757 879210177 673343365 50440790 781689886 394921947 567691554 364840583 267918666 20055830 471234640 608338496 812089577 881232460 615741255 401955833 660940786 730128515 903497468 755637649 331485054 655871254 475928139 223795702 451278797 241914958 153536187 429014893 510648108 861142193 28734059 631194646 538648135 709833713 183398594 560922978 688838761 801833395 26677754 846099002 461015152 365647385 167144813 476544099 304370145 865016612 159043800 160704990 750832170 821352791 604731733 277698422 617341621 137603496 178465092 194229464 774742280 669139921 840438624 956732694 956120780 23283394 748274555 13110625 53069512 6568229 524891881 686945705 655426602 100196879 753642252 592004062 204183131 155291883 912615001 741145409 72970155 633236393 311879694 174414010 280677467 670465925 548429286 826511928 318963167 157409330 439372147 68277805 98035159 114224497 650236284 129164741 126252063 280505439 658424142 629826041 770201754 289955684 287363633 161728053 390046768 777969142 760566521 905618366 971534554 753117718 406072643 399336225 912340908 805093282 86204963 525894580 764677441 38221327 900489460 536899868 510795137 620554194 309380036 150423741 722964037 675135774 594101747 716453183 322122742 250096326 511596171 177376559 544635497 540688010 656741806 487334989 857214882 350145609 56619582 60772582 569962099 70117952 645998339 980858855 421939484 638601602 969595167 838110903 642044358 964173848 292521804 128844978 626585127 456975593 935697261 642743923 736770135 257550308 391815756 433505237 88903045 971461236 946239885 119744750 450771751 189267744 166157371 948872746 220276041 580517928 217713069 947307217 601545604 371694285 240014658 245320768 262372669 169461920 335247334 407932939 988743087 315561998 609260823 320205008 952153987 737641241 123979640 141439682 461146490 175873442 599737229 567654184 576941766 952430038 842391286 622319467 988131919 749677066 538308059 777519091 415334546 83280488 508447576 720775542 497584240 926422695 865234870 243777870 98804517 253775334 355480405 127742504 806434250 862438240 28412427 167231005 365459609 423166672 14035664 412485450 202948461 263201102 386628490 902480969 471734278 262650447 269134521 977974731 948638521 826102572 507516213 774499154 366030928 471874365 775964330 111835833 317778508 923032869 166378114 414976569 807534625 784193218 16081850 136142297 989964509 612850470 357141467 282051635 513887408 124739209 421708155 177336548 318952245 399574549 824068440 498993691 666924339 349100602 543818345 279975022 791163833
1050576881013