155 1587 44271173 604671618 219189865 303375720 193953788 650491568 550886482 912426508 65693428 800206307 600198130 462127034 416627050 749257203 603942408 1665760 109667062 32732494 873293087 69067235 985199084 685067978 678097311 957890160 822415854 491028097 565157713 236634394 173065759 707452767 416590113 276824198 457462346 510913327 633562670 23448912 919165524 807478141 397092157 927541070 728149356 553709299 358338401 620891922 198307019 488777948 78890888 387762511 163211845 507284131 603362171 695264437 456112093 170555939 547756523 999164071 785171571 641283902 91150276 584234367 501014421 886633789 767300763 231036887 230034615 180980967 239914064 942378148 688243436 498613299 813053195 107231567 750186028 978980217 731174755 783437489 707249764 718558063 550784954 678681707 569119149 140033185 823826461 607943410 45096650 329891580 984807612 373511119 565910791 326091171 945017686 472496255 231605800 840144165 430361763 284286207 855567555 813951150 790066511 220418833 108834265 98903899 324856141 494388479 440616797 520038985 404175272 802758947 685424847 812608684 655540457 487207174 521257702 203322070 1003210 31676109 930477094 751900175 551821774 757270708 181913765 824099461 395868363 459637421 933171953 159566338 12670469 403025809 546975116 611982866 204784347 551570726 502172078 142906656 585021930 960680810 937346202 19827969 91041702 644206131 720486179 228745225 796278637 842018656 4240900 626988426 287938591 159053948 593189525 945874508 749799131 491293689 136096292 269572652 859766245 806507440 238601742 895179142 524600267 780800035 34858992 134502383 473103514 824411899 847174564 875258653 29108834 102447922 710947860 411104183 776744668 13934729 432760475 978221859 414833226 671503760 879252193 346720644 933535423 795523884 486507603 97012684 625224505 510691727 379290459 375349379 158517725 538635201 317912608 831208247 993081365 255099332 839415761 182806664 319969781 55514694 102473788 784476590 990790807 958889363 99145562 935104984 433519982 91743915 282694699 938129412 68569599 453636172 920489379 696859562 183404729 463530789 142980705 630718670 599850242 423391361 579079671 374944406 784236146 36225020 854512831 482933792 632502596 391412940 160863318 809970751 779318984 446220172 434644133 733367373 761407959 227100436 137198594 184668437 166363600 184570892 274905840 464907334 743188430 837254766 31743455 641067268 781580782 198297291 282152849 526888171 644834530 919796118 20527353 934141445 499045821 54581128 520713026 959490583 1029473 675849451 73257466 990665886 963972575 483858630 612386211 447504523 248347167 297770664 899235245 823437107 421903219 581976868 417007339 289449921 363727805 528348332 187393468 122656118 812669515 781189000 575872433 862566578 447923532 948764203 322093919 952422727 13148044 803767525 801732982 222371524 205408284 926386345 627829933 10603152 517419652 221749380 63072562 976941673 270182825 815019787 590903655 446216603 944629514 994384997 986143532 47143317 250027459 274114396 974756812 171105970 700865909 466545069 999412788 458710110 507360284 413140798 512796661 883917792 417221842 239704427 179474541 935132526 356962716 942452138 452568273 709353239 224035973 533735227 913678089 476194698 576501003 93090561 888863568 615000283 375146659 935761125 580866654 809754325 130198357 294093900 932428253 966881618 33934445 523100369 851111930 357388775 729551218 490516323 417405433 114917735 408548816 699995718 151103937 421463684 740180312 973706577 718141875 234133284 551004633 855274098 235896930 414513619 539079096 189628133 807545151 732959720 130668412 402516603 194680062 455224107 418202367 502983947 546368158 507068931 900113330 978675169 899369433 724542358 396434275 398046651 587878305 61384876 699745637 595810040 261253770 930626399 274120959 420529348 722319255 43755490 882078278 775907744 362021815 571861170 66724741 531124826 354519256 815300209 636915976 228278022 212468846 72854593 989765138 619940144 341570571 377272504 77200564 223754428 378639356 128676809 589739135 231600937 939400860 737194992 82189087 228965194 452065877 104996351 921456568 730704613 534997923 756571529 137543930 68260328 150933446 20396609 413683567 828294324 68387376 526558076 583355693 381380467 151917841 175204751 952000847 1409862 177736089 281264229 806176551 427983754 302224679 262856476 439583781 985580474 930886448 178929119 304172523 781486366 967281643 894543420 557179052 737323120 168780193 436071163 529975118 326005786 3019426 587584224 718700232 713960209 33137806 944843954 144231137 33878320 520665222 357797882 189221089 606632216 379158087 789446122 18995942 652457105 544489957 682742953 662948681 911147529 758673790 893929133 68137040 432084495 726332842 35314212 593182249 231711566 904548678 794317726 561052724 695735662 86003704 398970387 800195308 802854937 196676217 635488991 756521414 559819185 738024889 546965128 141049901 248622452 204851886 255380183 891828020 94454650 799694583 540000334 251765723 425480276 399660884 515338874 102549030 481487383 301157194 939134528 835430598 971758001 690287731 647805881 486879747 852351625 296836720 142021283 969537286 83544472 252876500 872538900 829938176 332536651 635487007 575901696 82181963 695540475 561306470 893139008 348373195 79286859 120045908 212136418 754424338 371221669 332969043 847066126 472608685 385479717 115310253 811691406 96139305 174006213 393762501 540727465 747810621 282843609 478182327 505190638 476533658 607685367 121825440 588621199 72543984 816190096 355037577 427363314 10150720 639306981 321243020 154628620 571021454 148791512 155851520 388121635 861074667 332673713 976830874 842622769 122895990 77048787 701849821 97976831 766201151 704118457 392065092 986497512 524922385 962853231 277230655 900668224 214710522 922303475 428843342 42298065 394284257 779821498 42926451 936203638 636176218 442984315 970507179 361241000 630499535 176270974 533629949 634831448 358634276 361907084 251193915 887477581 126739669 219449773 609761124 41331178 683380674 134712549 648878751 558544017 183400690 269770918 133128025 415528311 116444555 418179150 548498243 864781040 764842061 301952632 304637716 693163930 626771023 879909424 888061828 930831231 1008080 478574423 261650331 671169608 563087800 372584622 485478548 588673083 769751898 673670311 535272653 138806138 411872685 507726699 726423615 946512509 495952363 643513237 504432836 617624588 267807590 949352255 973174394 64531682 218307496 751735470 1284564 250477593 518674609 479173977 283835150 259711893 688525536 486826753 232150175 666118911 293243486 695086469 898232980 44320833 940863370 486079432 832737297 133494549 572142812 492834804 945711489 623211100 256887916 409444068 883508308 739086535 288966844 812218715 578558001 107771145 932330524 429279287 480392137 945277810 406597788 828464781 461359125 492084590 235167007 752587384 850996969 166434814 295644537 495478821 767926553 87810945 85580198 312536508 942067237 624013413 856783539 576865325 599471778 469763808 934106526 50299480 474691553 736664431 423722002 286682013 317058244 866669011 414139229 935851055 511852779 683378181 648568492 921923885 278381302 806627652 162624201 965738001 768086130 269233598 35792117 605988664 409938476 531807754 792536709 979839355 773479199 184285079 614809060 552820437 214374277 648890549 735928634 710574934 65281696 160191511 101621147 465042642 186849030 184091667 279069946 767984897 995745207 439458764 13026241 176784717 673751083 198772858 33972699 8364068 973716182 26308827 914062705 637422466 285700134 514869118 616491175 483394388 413275690 206439704 152933959 631684552 382132275 832373834 814484807 603196406 683034362 868257774 877612364 546302872 919131079 669921212 906281887 955262647 906399615 939548508 543765230 324645741 45256277 518013721 390547424 145923114 822315846 922572871 201563957 326995171 52356450 764298315 948188092 476059098 863961896 981175480 161445796 375324673 489666016 697050349 664241740 204943967 400720628 378862232 266655386 753875574 591217931 588720439 258276208 417247131 29288720 479465432 76789112 573201908 104968294 26223335 984846169 394084939 715908743 373394448 218921251 471896309 401904645 933614032 677229426 571365723 556877606 201997301 675124838 480828510 302131217 24336241 867759561 191211198 645467450 312979422 119049931 472960750 577328686 895597102 531687423 464162925 875430297 338248680 772176933 669948252 767439451 472076368 478082511 122717175 532600497 954870298 928966336 537984257 574603109 442022699 191709979 386291845 674740318 562300157 30703139 527140046 665762864 523371058 370330934 93921153 461945619 872516043 452229972 376323086 490369825 755754952 376483412 440479361 622022606 669126815 902790239 194093402 839603768 692476569 585358384 652177841 837672855 997390704 382382605 672669622 63889117 793564428 730665559 927855974 251078050 741624452 784416167 361949270 760777782 988215964 195412311 393821473 712532431 218952887 474910701 115097539 862510192 669117337 795305888 513435737 792654397 257632481 448589821 434228877 539722754 635278324 975670488 347586384 890140 272754843 810619507 510631899 153599839 3222564 179830568 335152566 655190383 357430066 29391838 374621486 83951133 317009487 358384803 284661305 388436897 848165594 749337281 105934986 891973572 332958675 705424723 174244247 364455526 307904030 839063159 555766967 646640693 469355967 196363878 70418175 105737993 997147171 283008131 577919626 886371561 554986849 644838305 785681972 620570478 739487437 958819472 170546138 900547312 152173770 261348931 821792864 444735794 387047195 85134616 705243942 729619005 913916650 544248351 406763779 856064893 679706718 778737000 119086271 995141040 655389264 798026637 301151814 952130032 892067193 207365808 447482021 152167714 502857853 891037485 238930785 913153623 595909995 214108068 791938202 716659836 194111506 480850326 774047329 410375171 737210727 320200071 809135222 287447117 514814258 929957695 506441005 490871941 675557996 319765171 851809339 706007972 360293121 280694088 413448503 921604754 337247639 397952400 85213266 149897635 69617230 717120160 465975564 88025668 532944149 649718800 426891877 585835539 41153338 259476236 107136345 837517068 19583969 662310940 996003629 739027543 673892492 313775015 674448228 848630500 417394864 636900569 304947498 47308397 554984065 382567557 925549362 513714393 503369490 762967132 708130424 567964124 12711567 643938539 736193876 327855056 718169620 901518214 461430838 838145056 946138900 872269958 543121931 446949991 935827812 582992995 4815950 74604037 331746672 310709460 353165192 119321230 730600617 103798225 970290690 900505551 455550196 114730109 720946357 548290777 2708174 683417730 908796254 146330011 2028066 953015650 479244477 747462985 924155595 522603981 575067329 253956393 751514251 83453557 213999179 97534619 433207033 757655646 921357152 134555320 167975492 162334062 716798712 313056902 370335119 964346949 867594515 965203932 815720335 908231525 250077634 2040013 619442771 408450301 269606282 536390131 173371484 873321994 849577418 569317179 630100112 926812067 497209601 929270116 785941399 665149508 196883529 438612426 458144913 810558475 463021829 854760529 385108513 611011508 437577174 523178142 235987485 841202605 390751051 408478281 147674435 192040789 977897849 700404852 156613238 892212602 380045858 289430552 258635609 628306092 112677542 233040824 70730813 123328573 912289157 88574352 834328032 695667062 269351665 315420480 51858545 384087126 747777090 901445616 471765533 437384977 418873473 161830616 900663072 937203566 818079779 990237766 668155188 760685516 344975052 153070386 351186751 102430485 206778006 798693176 53419262 898395864 16038822 929676122 716647783 779554161 756025554 741431154 274523235 317598164 155540415 688229739 890813325 604445074 802226568 368089418 819689807 96218015 404607660 185172746 669440409 104069427 453318973 650630305 710440595 714279028 325200684 693853095 852411225 635600309 648890661 338665286 283919142 422535987 577136811 801407188 757944418 161957673 789905920 11963922 989182326 961206305 835505225 364070757 38277339 648976038 152450799 597860744 895317835 166130065 60314674 521578169 154018197 223301713 11214008 696270963 423117012 858078547 399430184 990815154 597694914 30869768 600992750 771687952 699557294 306904736 821260312 944215197 311330768 287771769 341643965 941876966 139381513 409227309 168962185 996590740 953106645 892532301 402206784 980814691 349467634 412321545 255817867 531656811 664204604 599081486 615575758 346660446 358783091 138466462 567682445 41351393 442011151 393920936 824045050 156289064 855322516 930508708 941587725 94749013 509786680 180173333 498401008 740557179 861354215 482171010 258242125 255687782 807536616 16432928 67044807 864107352 771604606 224014575 225573876 781284218 888602195 637144511 508904942 698393502 142044181 670798101 412890125 413394389 220669585 85134646 461733309 612837955 227219514 344395981 776039459 670496268 210387661 332371278 51248822 643223162 233502433 73589223 892479984 701799957 262187440 462357865 348648802 2361582 415565339 79450632 428212360 808694045 478284452 964000686 974334705 244666688 191839526 629270414 908478760 233970249 915893943 896301818 868147228 774276035 683684157 303952685 217475712 173250483 855984477 960007116 748413578 764788442 861283683 851212926 568197476 969598563 774229844 427823403 45971798 199619298 635331489 436627153 784204917 525250445 325188753 925004942 802273925 1857500 986643766 813202455 734433581 194704876 606218639 611791765 396283897 841628506 303373196 708111062 978417168 704774287 112605473 835796951 628085196 392394233 834986007 829135622 406890894 352528520 592676996 742073440 629594410 627600392 978612888 87829254 276802246 745887726 173901301 711358917 166973249 190769449 484540872 843372274 710972802 821128745 542445114 143596050 259873370 7075501 547203665 971910879 825186710 263888439 523824441 659250227 757614895 906180871 173083096 197489143 419491952 12994670 242339221 681554193 643393562 922340348 273392409 914412281 938214286 738042728 895352085 552066177 718722244 140997873 331814943 704223237 342663320 325805825 620126933 794186267 541658574 473517858 311353375 524674947 181467812 189780150 841290825 714913479 227974158 329519413 902244731 990550043 237890182 369440509 375485632 411000151 885424869 800782592 878025764 532515056 694684562 47662558 86187901 371428064 220874409 692525040 290720912 208832717 244546605 416705185 413689912 540752389 901112319 286313784 939017875 744512395 272275666 64633779 480501258 101089060 120334501 696140969 251614798 637761684 270706606 429170131 408094728 264491308 307880912 311342077 385235205 462696368 465331900 478467675 862794866 781288851 498958941 979046184 448448486 891536002 658558644 720519641 93854333 861054724 483612638 802678075 663815690 953855053 669482817 129143219 954859791 133262809 668549278 739830527 485305001 697116115 837806054 9275885 949262892 180776556 899963349 659614108 508288757 4807717 864952041 375240271 753145975 350451244 918460658 351144397 678086865 357632946 914414147 403367803 295270243 297367417 536504242 339391834 512211353 376815819 39460984 258057736 686263092 971323688 79570017 757436087 349409627 980077850 601242881 831668773 431685222 279061982 272896189 999112756 436052959 604666399 733803158 861938876 580121487 53275524 222962105 302550844 6259323 910562767 844301627 509080155 177785453 656445170 972020636 44207918 113239070 92157392 613888977 55458707 620408116 574942719 393624456 630314158 983398401 937418682 683905857 993403210 484968687 231204895 100259837 508851492 221884459 889344771 993264914 373462864 548606909 344224429 125700028 436497840 463608536 202903916 318536667 214154250 412564705 789716043 273673316 515382893 551657471 745988662 95927714 55307960 259672066 335675222 921893156 867152254 978717223 986673760 401395488 373800225 622990481 193786486 701797703 385189584 35801974 635642556 82407709 870127299 449692083 611594806 138597045 255991659 209367361 482079975 964896006 182880582 393956236 518245178 618274023 23001050 821023365 378649417 993577883 831309277 102187278 538903116 128311009 991824398 177054707 350740706 23164848 967455054 146498709 900676080 714016333 101417513 155726747 357081374 811753037 954337733 201318653 692739665 963384787 130253788 882507121 190931544 962660727 751301971 360378522 974069369 515930257 520382417 766604023 665082490 38094151 160979480 873876091 805344423 84623188 285159419 465174425 966553086 615002548 483381384 544980921 130569207 242723805 659146142 769097064 643069976 393018863 51732119 819640104 360677790 933773229 164504747 207405685 272948741 312933398 531465992 982831193 671310154 492670138 203311346 859070672 810065968 164011803 120529851 599059013 298366135 246416367 640553734 510676519 552703108 434708920 982821535 202542697 244560026 564205423 70654636 385687388 450176342 381366400 303130050 829539575 672649950 250207422 673800630 57979732 657218687 429605177 491613766 169493967 31768749 39661349 586986165 82342690 492653161 428863563 788518438 290157782 116948987 421051414 675411835 994614763 371061502 399694511 643493089 651614175 912484021 552120354 98768671 790355908 710314750 736274835 624509532 746101273 794749902 415551015 349830890 851073866 997780698 416973838 206962686 54254409 151063974 646619536 777524108 70654365 443846215 602767204 446888984 329000306 780321934 693669941 325742940 945018248 769184258 179759702 576942035 511052374 25850917 787508320 803763411 975457117 570836091 281672476 810647388 672361420 478209019 497601348 429662821 650393472 511387439 42959665 998536030 215308505 60243907 372782135 963258937 950861248 459912852 461596111 834777867 528392028 554617085 82618577 612362270 282285776 535290490 723774579 649814414 835464673 955202428 303746304 785912310 239543679 847022543 188785019 141732928 103803501 710426587 957613103 292852016 643533580 367312262 381598677 986196894 501609511 880733004 315544726 144248034 90707382 584036437 37789049 908474909 29420684 285094458 521119851 857017801 151868229 316784806 608787144 119922900 15699352 199208097 179733387 927092155 468264014 31164828 87863161 232159175 559899103 983504995 446653810 908505340 112648921 433651821 663534689 593754992 728544335 204607263 598765000 905934435 896789446 680300416 599571818 814301337 686329726 121668130 693989922 993513772 97339417 400648929 634023119 334449130 643690046 359688903 352093680 310373793 913369517 339902763 305062073 796603512 846994895 744685917 627682214 71318623 565015667 576555679 711774841 513267411 271553702 585366268 854211137 937012472 625419842 374465000 882018320 278841723 713469797 954418137 799467479 228272342 774693327 778754491 602408221 751679440 496247914 520282582 252911207 721810566 964002447 586705490 115102660 691433332 443140876 606269631 372481142 889647824 481078218 168971964 865832512 602141795 874290979 893712187 238553386 725337637 387762729 265898590 371628550 607288466 394941232 895069672 180105622 236142844 671450761 54607036 837804117 222511000 701973273 763661306 75786737 227561666 433196129 154355638 602386877 665462588 131285894 460617839 773965182 129352622 726173884 27223249 367959366 34693441 668805272 433578796 15583115 8888223 324169354 745978460 182982130 266448615 402704217 317151266 471008361 756016430 825439237 599814588 744401312 27724242 794045549 686400021 561990923 744433365 217479607 966346511 273907706 408773023 173980028 631306124 251858830 316198858 721133179 840964085 703202806 869182650 291635040 972657691 411173097 658889124 607410600 107338918 753094529 725757208 554390903 134638415 543088508 731918947 534513491 764075227 372076938 362339979 406460179 296833218 183173376 389396905 922495899 670773148 443763248 486465141 181230318 161027169 720277161 439441685 887533079 753168255 208854355 479216264 96428992 526647254 109498207 972733186 418015862 61685766 215993844 109642221 125857233 457911787 220899541 982100626 816622066 826769399 249252030 540142854 192011724 341534660 659213714 508642988 774256469 402474761 432425159 105832255 335769541 726576116 501197581 757920699 836220553 504856021 217777739 627993712 75509116 348552017 157402100 777575658 258621370 242766390 125238211 911479087 437972907 709931851 138676672 446629978 21653296 633925984 142774637 53981394 149679083 568495841 395913205 652997375 300076228 536595356 9080910 448564358 455480611 545650661 370399014 940549479 706638855 58803732 612539758 137495426 923844560 946228379 632362589 358615681 660745985 137564512 931119175 466611728 769671398 34351512 981720529 161639943 868950678 876060391 516196107 169798948 836462831 312384809 355073070 760761544 90773415 400031068 694897506 811158190 89934292 424882288 702229686 897354085 624415530 335581096 90104736 603820572 736874402 557534349 898926752 54333952 832167050 38361943 831962635 246498829 104980232 984863464 702501001 709356854 205494778 396147598 596127590 852658486 423197272 845305829 413007957 218962741 841733403 77417147 963288610 211400743 199347943 964313460 843905061 314693516 475779943 624684723 331363597 236246960 25342504 474624660 238182402 901081674 888705957 726767493 594362340 426249023 231854618 381309322 765610310 950663912 657958671 750385762 108271583 522363310 419734648 236942708 484442641 741664992 946032271 943978775 509559152 12831674 760503016 405415423 920310316 704056331 707890986 191969758 661535786 332355008 125145268 950772626 385865488 301844794 387939626 646901466 948385893 923982 133418095 429443982 435709989 76159674 470022497 602139816 188971580 357339374 3141926 64424315 986716404 570111372 395265142 978321150 227409006 137683308 181228233 895669788 17075968 592635016 154083921 405149357 989322994 327968424 660609667 92365572 641157654 272791648 941104102 777613647 500490857 482616041 807125546 468682463 3657171 626147427 440599175 410395130 69481633 380673603 209647316 97077562 672418711 682224134 595241035 177333405 788010848 476557182 398222948 864869750 921762482 928146816 605385047 269546445 55159629 934795985 887877629 699740833 279548050 171230054 628540060 526464435 286727399 868509010 403626554 72044137 753106001 271823631 631923043 709882704 911688931 492140665 786361631 280398005 405205868 606350275 113963854 34203789 724643611 775501965 5205923 405575127 789042746 338486094 279749689 606703114 560154358 584379452 8619999 310951708 636309776 940129213 741497929 97138534 6844419 107699540 550808117 530111893 326170652 269551917 482343436 967590915 322389957 723204291 338262294 894477399 956656684 419065353 405312680 841984992 427941750 462513984 713065615 842798356 204851764 942906129 275946004 531152359 653119101 716486923 646044376 276571817 524891509 361029035 738254532 35069291 121123788 828218973 7387998 534446497 880704177 995966895 88722804 971309964 909576145 279872712 145713082 436846341 506694025 103838612 171139541 674879891 86014834 972083015 404286663 243790417 596248598 24570477 949011760 969595148 998665492 699667923 585545034 25032137 903924159 86513783 459139814 886958173 809880794 330506670 606023232 520893724 692638724 590024279 781288138 509726812 420117974 772133082 257232807 263994234 556588053 766263056 179692322 432624530 577821146 254311191 363042637 715872424 793819544 223130678 783310196 120850506 315764601 466869714 496552137 302834993 733167468 542181539 186171631 820677225 463988227 853999131 288626501 194479840 271879566 132179106 65937613 579198896 137472664 508741175 605171807 922579917 536877822 821601942 777494281 271526880 694430250 597211358 947353537 488813756 119357537 289351518 624485632 602836232 281119185 977089444 169372584 808466851 407339535 233684195 108897801 106499608 379889091 195286845 140275238 386294409 244913635 599890917 690052648 576697079 569358484 523260301 616244759 20563942 453835704 549749432 46583114 836786345 146933228 999307719 293244573 503764901 687640527 165736119 188683540 724211967 480591823 882156047 901625407 661797822 35031452 930914657 761675047 241881758 112984910 809298263 320201160 182666704 116403838 294025177 255500724 428073084 643784590 737265886 413481741 77605545 49261149 508477391 227336262 137723220 814388725 315616972 910834368 781908445 176489734 927156921 523887306 935092249 269555463 986201960 699384690 935517368 876266140 416280451 526986256 207291632 764879712 977668271 644537269 55708264 674503718 197715528 954706672 614972326 501374942 180255770 228607394 901063736 342212132 404563510 601518537 391998701 504783763 242877899 230041897 828675777 660168980 350669021 65430770 586379947 213083154 835822651 483723407 687723689 909434213 509933424 340826614 411882192 108646326 290357697 702323052 585002200 661776430 762820452 110284432 458662332 507165878 694781049 516315812 719396154 915060102 838383109 33695870 885540074 298812946 468206129 161278251 718699922 554548051 870402327 796025500 910381239 424206218 255425320 37925370 916520135 387481372 630636532 227982505 69121306 148373802 79745238 522860253 69560802 739480631 65200629 626009660 805248020 485633626 478743892 578570145 28677181 525406825 939518671 218278834 692742201 197164358 395981770 885935896 106688860 643496330 801455026 517532213 166659713 379300707 109976331 122136471 695207621 192735748 412504070 863953200 534289445 540077851 341674824 278421521 603823008 543245368 693319953 547307069 947764536 606953819 746435695 405689986 243301879 580421857 263389529 443778892 535731078 586754441 409953142 561967638 682284119 321464201 508452907 125492350 460840432 45090015 557533156 240481824 3187481 416731492 604348858 557452239 132592566 6922972 666841585 668524631 223687873 386395503 271263881 738384970 998873469 453455584 363515857 100582607 317270873 662640838 495710576 902189683 976688389 916621612 49944845 269440585 58769738 942840671 234372482 590334026 445729073 833589426 142154280 258641545 534230440 584955890 378928169 352728958 285106622 711743190 211507992 10172315 75445911 794362050 542356225 66161041 695492555 57552983 812031010 166135165 974281944 396583298 831353723 324391149 358061369 202205893 716247730 798712369 880372958 14820175 95405012 496455571 93641961 741488988 145007900 592139459 151448198 68133168 273776860 679819385 92101560 228736618 957002013 527330930 104610823 866212155 51635424 597460323 77193431 991911253 670398172 737783282 665394045 815593229 18450192 523237410 865252844 36564119 551589645 266604808 160948051 577286944 429446282 443919682 430427790 618457753 803079731 673309865 770993002 42058108 523199832 406650502 134436729 148518208 919129797 321576149 542461124 610608914 269599149 952011972 116417933 560094066 763761826 767660328 364331871 984300940 597301716 848620553 179565226 97373720 756866672 899733840 450897422 797723020 646251559 176694338 414194772 268231024 448168387 680362863 332606193 362956481 957740892 589871588 72252381 605492703 212618206 264353371 404803489 364319644 889055639 515817324 368476772 551447 483818447 475165741 56693579 963463602 580282233 475718172 709098752 936126876 238579290 44734979 648243807 625215620 135395981 232798037 486350181 968270900 11914902 991033393 856451736 402293782 738765435 191525511 635050922 692359402 633362953 963394270 83179842 188281007 62553515 310679002 154119635 673334742 161148383 665529874 157995854 940157941 835477771 851276055 54328998 113632045 53847519 405187503 732026350 890548663 883390274 695289751 156156815 394231193 668565745 919451395 664093857 407007519 82541514 957326969 540359724 790673791 818123563 848402830 83356060 719827244 92753169 145438198 292497440 240917848 928082459 338314997 274179479 928608124 826548633 20592043 618277089 610368393 539111780 382373611 613201625 558910346 813426111 848652587 79362908 49564017 804138516 742142060 934561321 803089527 650919652 632739315 845937015 239886550 478650794 367052741 947954178 766114872 561470897 450596318 793556638 800961846 268845622 101537824 526040106 247105254 849055679 279498664 681609038 469632436 470235865 803910537 454346895 365660320 36056356 858751018 459258196 692072117 741698983 776560802 697119478 127406082 115184071 343275006 852615122 293353308 941840851 144351202 457263525 703384745 256273430 345948355 448683754 292800203 842334506 714494919 573844882 392225271 115777289 31309665 335743367 491807003 365032655 464277704 338037390 753156899 244674099 470908900 306560071 363317160 27384648 612424515 551510640 705416014 140804504 490684102 45303771 631647071 453076157 119158681 759318643 323507720 834359614 916596956 293982975 63878482 322898769 891002612 448870251 834846578 161538589 752486273 379933693 208203518 821272965 544744285 525413824 681589763 480538122 159459526 940189241 982055503 54774881 75486167 693181661 878644220 612151201 16865143 931361733 149240754 783800799 921334121 992140314 436833851 864572103 920356718 881059396 286299262 109123866 509637915 538145267 651340111 339042751 520286086 318272955 338594181 999363724 458104988 193365640 71868407 333090125 359887325 553017973 98294319 40060020 837387959 159878647 442825893 126115388 387544710 113556992 313152855 77397892 517530667 842928450 410878674 636532148 991187057 964923909 170473818 974982190 394091936 517960808 118725144 957150659 972941548 494810005 556497580 594571595 566178129 310855804 199019796 791216321 456495255 685082034 345005577 159253773 724757230 917932373 528577783 882903206 884280389 787866657 148202952 777667196 47204059 789418823 825259149 748387574 453062378 127377091 25873887 466634019 488514046 772181153 376464189 875337452 604852822 749652155 585167086 742929419 957764214 601341220 338014220 487119380 864589267 941944279 264057108 4553655 662212509 493190624 345139621 9570831 597961961 32899484 690124645 643973654 44375748 478039211 175549080 446962032 877494681 88553011 423525909 180598482 755328144 212491225 626047213 55602106 765444435 875449729 213900350 437983610 293896502 161178069 731464725 352210107 79677794 515740187 967425927 66862730 221674726 212202446 620472332 395475476 687075627 678362127 428985270 791600480 197981553 713428340 882876184 223459210 866025214 816917002 33770023 997166150 354876869 935776258 997319403 188401443 814725919 175058194 502754770 977226721 911017912 449982257 440961798 530153265 925107837 13871802 914681654 566671707 600466146 429685553 598129059 261976240 170256612 201619239 355779389 358034583 136748973 463687538 862123629 151855547 330699858 616323422 909831813 246155536 540089642 535847426 212913198 171204251 674919822 985726868 136733331 146049117 296910304 447733334 832843728 674887884 658693974 790881633 152563862 675408013 107662420 822765691 399014986 178777401 78036871 335833556 572370029 618305933 880610366 344812636 654557772 43093132 359040441 770576894 789256387 585644103 266648264 1807855 27049034 105187989 509974286 202186819 433874570 765490533 22319817 900190435 109140088 715754796 281882558 861693325 869725005 995943870 22004352 98883331 109895183 339508703 235704172 820001535 758170880 556431254 444814128 303005352 202328677 542445927 166011614 586248992 14646382 692182784 679361523 270975612 972636542 683322024 209703890 964579380 534477037 517572551 209357174 191618638 730070866 952406093 805194213 906887723 356167697 474372443 222738821 57430690 82525693 888400707 933189600 510435202 198555303 871533568 690230186 73678051 595568994 330826153 396892135 747472188 640364148 513705206 103744768 908880211