1000 225264149 803773770 773614657 728009195 476729281 345120581 217193052 977334796 305728937 583043662 74805557 351683118 762330395 505552108 931042453 689839200 36547214 693787481 256267882 243533933 510511345 614685626 38331584 253323987 707840986 409742661 374308399 118031683 226985745 884088455 705628648 151953207 2497486 538101092 297960304 326019355 228174781 739792754 254656481 591699785 46807444 154135471 508513310 727390919 712465664 49170958 832152634 330046087 403036922 639317551 116015801 849217921 104910999 521502627 512427854 256275455 7573870 980326047 622292877 432458641 188422505 157960376 507085702 407654730 822185091 438565838 545982206 111728239 303640065 270585059 369017933 596658891 433890702 891573922 144129551 286737900 931248090 389470578 432298133 608555792 658592191 975828434 207902433 528911109 107141334 840980125 588424270 913203890 941386008 789650578 936910373 813973761 13408669 250684416 604772802 60837467 167445395 823918422 582245528 36031385 454944118 668832869 7707489 758552769 166058223 14499017 564397432 456969045 776395382 485197087 544469807 712260030 536860677 353353682 696949482 667252794 641556299 679314867 663463872 850877958 486144178 252054452 401571449 378752077 27167875 544813173 541971242 672160168 90957903 91994001 933245036 828086024 798683827 757820568 390089333 496558967 352634558 723680192 755679509 384531527 130414341 617611958 403333196 475044389 966249891 918179178 575864879 100156401 877817017 323257557 761726135 743794732 268609397 912288949 395401144 21108959 976969843 169717961 99268430 164800947 304960022 872623929 305969130 709009339 38719460 745314313 136831146 854776809 285508105 270019319 585290529 343101890 373807454 733772120 155081393 608122735 486888919 563593230 888781435 261660418 826523769 990573577 893261151 488031200 484474554 231039024 274319186 678485130 781135346 90847305 385930183 57298859 734524955 565628935 349582731 260790271 658256113 922663473 325343433 220864166 577301900 106322078 198174382 173965274 412912332 595644801 84371970 474230084 557958361 195266421 561256003 153364330 601649792 708304600 442667617 19482694 404594027 815381752 795647232 759817229 575174140 880359677 918209765 275795396 246460262 134879976 882429515 804432488 77119287 807397225 675955673 26024913 721684853 930207213 675167062 459406074 653225322 693685306 783873022 737568055 361409947 124751814 318918200 808287200 160889015 359278455 158192816 769818068 969325645 457704987 466250301 156032135 834205491 19363408 504422854 803109761 286780896 409113801 214927068 726288072 483043545 374202600 790480721 749639973 695528843 564581648 749127767 328407516 968939573 448628987 261875978 571947891 560706848 826208185 373749663 26513306 170573650 762214245 671257937 715585004 329468903 197984872 788936104 663117783 191812514 778424355 850776157 771287817 746519263 140552764 893597761 316181477 559366060 549884760 810769978 384536827 226915529 462847237 872153062 26494660 672583060 426810914 657002564 491070145 354597606 463850590 37675266 585724173 804294704 953760227 858292807 565015079 944311294 831181760 991615979 950245685 792704837 7217601 925023319 847544973 50278385 168804769 126066479 88624632 100672080 692146105 86634897 451829768 298531558 800285830 642542169 811581068 786256005 685721483 745755574 701299229 15454829 477625332 866919152 232799199 237144054 619573589 830318108 487571380 862393534 378232606 24831173 792491683 198158290 757692553 345128392 920599504 732255042 108102437 196834676 586208019 412204445 337920349 849709390 728920754 265344608 601110463 519475006 57958285 313804526 185789618 202467233 569689642 129093408 890529943 942566991 270085232 152510519 338747634 828499887 660434433 160008664 165903584 731532678 619213588 278447224 182256988 744476896 294155540 422257640 536068652 677533505 293243143 345713601 975693236 748249566 398278678 673153139 263484156 491608014 220146351 754550082 301512107 446866527 672556405 909600708 163624467 1950257 134107869 449483505 633258475 177895319 971240702 914673574 115866111 61323126 571349088 6464383 877283047 71135430 400055944 72513733 748155758 168191141 866438757 853531057 99604130 749519418 355049171 891137939 581861451 156018951 326174430 676785418 237961376 496247364 777598223 196856453 510973233 50586743 789811862 469374589 422706142 964833210 625517523 964016228 256438312 673894130 630653686 632359312 405039344 599236799 620057409 416563985 974411516 210609916 731822438 151691563 47597186 536527167 876617355 549497021 122775182 302218618 788509685 796368294 145858080 255807026 675878222 617947169 875381650 453194199 169153842 576529929 77671415 477114675 341463825 610693171 761468349 481734854 717355445 962997065 614000940 480527076 842495898 754117223 554403259 148810366 896380050 835843905 255907349 94845736 288492356 551340840 271613698 379827500 832920952 736202445 42440647 909752594 817163777 71576669 383868504 367932185 935037183 580501500 845160820 193553778 235809028 345816678 246370366 431712623 194770025 62340114 370690134 458341218 760784294 666045136 934569976 865658218 810874904 909951362 751181431 521621161 95428815 757191697 60661253 643819952 266268991 677865454 543520704 341767964 577187805 207638024 57993792 993813823 479618947 772819738 153156342 456049941 425548427 703776685 883547581 790642548 921099337 87177644 205957522 179502749 838119747 47572963 443614988 174605163 364756795 195302421 701697317 457918024 600015239 854296969 560834637 34124814 247566144 275040492 125365366 135543226 690864504 250352301 218851418 117869179 992346660 620418739 271775113 292193446 62232656 191484936 204599936 452887900 113691043 468326127 307363949 520082307 138905581 420457366 316786053 458371791 174563339 323413443 570700655 333578465 594809313 280113130 73241130 947812193 844878925 883362760 582871681 556660948 255676350 494797004 678707217 150246362 851920087 809184262 644491704 111282066 352265433 7295074 488708298 741644284 847361615 688440576 877106087 63616928 940571550 659406279 561661240 777541712 131105874 197569859 915880062 169075627 436091624 231059486 590645168 35834616 951362244 442703258 288989553 584296230 15383761 755129155 84848141 698662122 526930596 64267085 984008052 894557181 5785311 987339776 562154384 293494693 728418119 247395153 627238155 924411905 427630298 320986840 55165543 873596954 287246994 905366944 520578440 692462465 293287241 145730530 346621017 5349199 577531430 590140316 130097703 602437795 556688188 16794641 877598968 617183192 336203903 367404415 896414637 778217326 709397813 573084266 634810043 312686835 625623572 485067116 360401483 155943793 989325086 597473474 678713993 831104017 647411817 835106449 486534132 874364335 225101662 135051748 917839520 76788770 352968326 608646598 157010409 239857678 477007121 43727686 522188629 220046386 524227658 134862466 279564369 676502137 143167906 472906832 843401671 427879437 295658901 544216211 647738246 313127273 418395772 998575313 527445840 536324340 199524772 88016218 989775066 430512349 869453206 608243759 436092749 612478006 511616021 719547702 52535146 354087004 462410117 921952747 84045036 595992074 895948153 819688725 292371903 728110099 691381641 639591012 170643232 796070907 463050850 972432271 951967069 872555282 851876660 3819050 681864607 97811598 327877370 254036872 847959734 455593029 277476445 226263551 105594124 164816157 707152565 932176301 311073320 580538373 434508253 522627080 246838949 184659243 33584746 102071994 142997252 560465119 49322292 480478576 360525549 788689011 547949046 854254574 259567695 657190717 856913446 906375551 799106747 179037343 96983775 766029208 933205397 708719219 151673521 895003880 966528029 103164098 96199250 338174714 802935570 777676713 261407301 462576256 32349375 874780510 958084548 982760801 757876134 512231516 142654167 208870888 663748627 787451162 952453909 740018974 859782366 96267228 984143037 738974048 584153898 399419047 691088965 509181258 725548927 584115032 161703199 103757856 307764941 620289807 700353447 403616642 334065067 83939252 482254049 755612085 841235942 121990614 537748728 614605666 508335367 943863790 957915543 521468472 956387569 958329454 704611930 874742468 302262840 590588939 515716073 954669437 327146696 332064422 144669955 795367928 633676090 527694633 357020856 359675159 278437960 203566432 220033063 286868955 558715991 310952725 867599897 550837921 272783061 204722624 799688686 978044645 854091209 990765779 315495749 713175985 616753782 565664317 692451218 129523973 46359721 594647629 94920859 218161729 850669138 488856681 866286964 105903342 349655191 343062553 560057069 119240478 589412306 63302366 584656779 777252087 345160193 200141078 371709512 441591493 730366836 947601217 916415580 732687881 360929440 612746314 893357815 29696633 479730508 123588875 923705795 797279597 985213405 641899663 284881210 565463058 122543846 628450121 67332912 921587964 876790858 425839496 918033774 251226137 200075579 221563065 237561658 903717099 589546261 732128600 735058815 180472965 139345167 2565881 343925278 399414597 356744608 824700765 944026902 469649692 359087037 808378138 418899597 551180038 13961368 211040159 175414750 76471069 936093072 451848067 374330807 104055944 366628391 467228960 727515802 288997156 735990655 373793600 513075009 211966057 75422180 23236442 671083508 582144589 862473399 899657640 689845364 139118926 362393404 319713826 565230324 43720850 362593301 47568611 301758792 648067013 192548129 848410561 138784857 69933494 118911158 976285256 721223318 559214992 296719277 114211449 151291878 461497753 795643297 428507267 666203790 190145721 220837594 840565560 886774962 886079198 780127423 918340982 439608899 424934776 695476941 845285906 246281218 358470805 549686113 595289879 966996890 296842832 414593564 141274423 666513683 928543065 827996618 249914219 486032593 981535295 511876362 726486577 496395354 234959021 248051683 93425651 433717695 188173094 273223408 700636810 934365986 69693412 51463313 195471071 627299215 778325206 778112342 183051042 819356708 881811536 255805332 468256154 207976378 126193566 691543068 321646743 957650522 278462831 791922144 288410922 714495087 102160053 364003627 788281515 653319675 323563652 769889537 458983034 4144754 873256989 744373873 320490954 495024201 267710857 315637317 772210770 518606772 931919262 990822839 467826199 312735415 349827131 95954197 983425278 48649752 486749682 826081779 733596269 407337574 198754910 440758318 670100339 734521111 623290629 663047224 186271833 994734517 844222826 398069588 264217873 964367839 398592984 971824835 301150100 884970726 723593315 35972630 640911788 425003961 271429658 851129244 625090643 127560237 971605428 637538498 245827244 448009309 126210707 542175543 548093309 21316686 453053295 31596326 382191709 257629407 489091694 308412405 976927050 726667219 544449279 498494869 55723469 104323851 116438513 230431769 641832068 768169343 131459594 231668142 309559141 466953442 724616254 430774936 720250941 927386341 133448750 326483560 184583093 842151155 214824325 419825823 638134669 732024701 600443115 465246102 322253476 217203948 668384122 649311341 852019779 108998964 992388225 247910530 366488897 11918170 748246573 44530931 744379104 276563539 430615484 440503794 561317877 174367660 299504813 506393093 306111679 136130731 13189256 531806831 585169609 494631894 401412322 813708970 498114397 167569125 814255008 303748942 384496656 246784274 671414025 516461154 106193851 131559226 269995437 503370479 293811204 967506503 313447771 435599024 21535834 869220139 486821917 664281303 734505079 215225750 555110805 273471106 41743107 858074827 751512988 631630143 83575301 681044377 818009376 645391713 593484139 222201880 661381883 666160159 42340521 38052612 190712373 503501441 80907880 656784338 160405763 129647632 696929515 434202420 238655893 294944646 519868524 392466086 690440823 717467912 604524954 434166501 877816354 817513918 186375953 198055797 419228620 201447308 751074665 531442614 253115429 335324720 19513215 222581741 880353212 442179657 372399117 35856063 372685873 297332742 948271829 393630093 827256820 11088168 632369718 327655747 218247509 679796096 286452367 697649058 126494817 490397958 213853354 742202678 701093333 471283214 915196778 893056718 884232737 71351232 679389677 636749634 44959014 766927602 571804126 728264259 211332003 71906725 572255537 358734668 613164761 178567226 221350947 870061343 949658796 181645845 741737697 33427252 721099131 581292545 553378580 574559636 136318157 874407226 594979412 352539956 707688957 650047297 908897579 481757590 100581502 435874085 622448335 43109453 629451585 998093691 659632785 655920427 21085598 534027550 462738320 341406286 434997361 343028402 142009971 741578196 812819835 263418390 153707013 339646171 816961880 772765751 907209801 598265722 666960992 502698588 576969248 595061137 257893532 426117204 16193617 543706972 257824601 949344208 805015558 399477831 565868414 104569729 264597889 144289259 531483850 983039629 981516631 734940351 568872666 69715478 116459938 631849073 886385779 910883677 257433614 863083679 826082544 719192959 475865652 45474492 463285281 138059315 261312747 442885166 20182460 332527689 537181826 307358174 39076212 631522299 911475379 398552025 392700585 916224598 805825019 347062515 70502460 782449439 803021709 795916017 401266128 371764805 471677946 548678994 727489793 707794962 471900991 168309085 316279511 657023662 93266994 101024414 868051143 855736977 623037938 949686756 384600901 619022900 457234398 914372670 198156946 149243230 346356719 537050975 643606196 342404205 9012194 475613776 50700748 761792540 108778962 629736971 39965856 167830697 97664148 730751674 122969442 956560057 270109775 545895010 825586693 10357421 770350744 678309067 487784841 153543724 337975905 873997847 19312169 405069661 925313533 484765767 598191329 656941469 259560362 295583753 956916237 286964156 73850728 197559991 118757425 415553862 597398756 884462514 564231492 489575333 85333071 755410941 535626067 860066225 67340724 189800451 363245224 931112837 915840462 46624136 919030751 985836780 924706082 779501660 876167608 442803990 129971583 812729158 456913137 449331354 643192426 63892264 443286142 406267903 657737826 970914027 567305428 868876118 764118412 166156642 920033353 231580740 282552891 844247625 643909486 123517927 768156070 819848604 572085753 149431230 20555879 421390127 4252297 204957864 745287069 522139971 414359834 317588878 396140061 756707089 180947617 584286936 596525969 373643267 66558823 443044650 119370800 676195758 482301781 967495683 102676737 949984420 902507516 488587065 99412751 488283918 954469683 431091277 772956521 795380202 568682914 410340275 285847677 81632960 688409648 920047172 16467058 955226393 403709964 731126677 811763924 324002096 649997580 400112352 822988100 22867424 936115651 279648850 687215712 221670580 324594206 128536725 511215824 859041484 629035481 384500892 689339704 772069619 50485048 677235006 74214650 244498837 327118859 60530186 197992971 700654542 206921081 341157148 76341100 405191828 403424250 386671129 887392674 564952538 626369857 787069012 303728995 253767674 752673405 484939766 7343009 705215336 664023717 452438242 857867831 880435098 363852744 925069194 209163453 254733374 991702579 475633427 264831656 322571079 908209082 24123319 624202489 864284005 519845741 765341671 62982463 467242563 921502492 563302121 62056822 848403064 458280504 143308568 590857381 536377673 333373563 109249720 465484633 632996633 729188025 964994784 16602607 969326510 599677181 938084861 700108362 198799741 353402642 696192418 532082489 863206310 378118372 951912788 590745084 881333935 491590492 824204392 488786037 615154363 756805950 577237847 397013962 230362615 268506150 352376021 24688305 887967287 940790654 455170451 528188018 253083707 405113351 819617454 897725057 906614928 318732066 460984320 255603303 49069968 828146846 251627981 528691440 870788556 107423648 716540910 190484026 434630773 121737029 573981768 798209291 656234572 639507910 841747441 403789876 860782472 846896648 944323378 959444038 135991625 808229829 448260330 494812343 172663288 540180808 326456968 172823047 851201909 260264424 356721527 382467187 560413286 830093420 319031876 215242764 633180141 256034414 112706080 86278728 260321844 530617791 478442825 456525290 635395437 3611194 325530500 300219164 855223890 870343852 961825271 227618010 13191879 294078326 310039254 837492367 112843986 902578307 888262682 622026343 830244262 490493698 711967607 260352564 344723027 6298394 946567048 901310153 92598453 543404083 423053986 377403891 106713214 853404465 608525182 347982480 697201189 918926160 924185954 230340602 667366520 643251082 485611131 315534197 673609795 782106240 336178004 923668462 281870746 410238784 14469087 635794741 735554046 356044234 835288512 919210537 723493930 127144481 9265807 340076696 832783046 483573864 433082710 626654185 526657506 328404905 593562436 306384212 815140862 746709966 218411402 427047254 282945008 273331806 554191622 755772382 812988142 249283112 519124481 202008689 841099563 43719625 803186921 135276679 721727404 996426126 307965661 181459089 685748201 131153311 535572389 424478095 598969594 629949539 226852415 460292425 645350112 672467839 917278346 906400482 661118536 972225335 991920939 224024063 233407373 121058891 731771137 856817187 796311278 898275360 708308060 798399522 513587865 761558866 900390467 209823547 469158226 303630156 787000281 643096216 81607714 473195787 812076110 448366492 132742849 720264804 62890630 751715492 401136683 76902063 624964101 376461317 229845605 678447886 213187009 810565961 789232966 812032030 870755664 688746445 887895962 806210432 82636220 319427520 755031055 628842788 264261843 314056978 133733455 711841656 374592240 810938640 640593851 383896053 416312766 417703059 148966871 468980428 970067750 686417498 878216322 919593411 10822059 396504672 519334427 877489135 749487116 882605410 561594227 763306349 213044450 216010033 297562051 77810228 977430665 452020321 563942545 955945468 341118496 98392249 832319728 955175194 589031013 297461367 83708104 161093251 466382097 394389383 275043390 618196089 664423249 318447008 343651530 497247907 916132067 326829141 342517068 497506904 38938799 983088146 364689587 102055252 378962125 748492011 5498670 915063200 198075194 687838784 679033845 885656715 850448310 596544431 707739656 56498213 902631901 140176205 653505658 789318076 380326803 567695814 845539864 86394742 420309533 918769423 7480387 424141969 705955832 756870675 22452771 422691985 142336798 659162993 407025779 581188601 686635528 399169617 405219282 534011972 357443631 63475526 410162229 76055287 606204951 174915865 528618174 667755239 520381395 659888257 914589770 950006638 386232930 724792188 643747929 829432119 669532680 896302793 52065443 540366462 577894953 792210703 47904213 576821775 430980873 876946319 553059933 163746130 396182061 946116376 652312942 934167110 472641241 586364171 976034201 153113385 570185200 636405879 509965771 303878366 460516055 158062459 932073916 811844482 323230660 878352353 176059139 53531832 238761960 560552842 55348950 799931715 543746740 375713388 551023808 859886051 164736539 382652154 534576037 209722932 422527118 475968991 636802744 838558508 107211475 56696098 949449294 470128800 460475051 856360953 697110557 931808860 381050668 595410712 174162166 777752552 274007812 88118977 53692798 104494976 82209240 657379663 786631054 812434024 616763312 172525864 8671742 406058296 178302301 875815665 376762158 989870452 244765000 964700214 97100477 241362267 466141910 380053686 921147377 972374724 628859080 731243776 272767937 991889943 849130898 751036478 967667089 282708206 745107018 58687085 16382627 988770067 933174728 922836158 783255494 268185971 778188240 192659384 829118091 825964167 731905790 912437749 673239640 404153991 748425641 28970400 871671910 16152161 501369545 692278841 383915209 644739223 140051133 776456421 637257832 313675527 820048544 951261582 593643229 341441481 238441187 596929945 160517235 709845918 536634623 850190329 351884781 652166199 302658992 404796472 19837837 498430340 33492344 132324553 651065304 839809221 420991132 866097313 949357661 160236275 447707889 595260954 802960672 560343499 392440102 516898789 117219044 275976074 81588855 740698118 615580190 782429144 877291143 55668885 285430857 730245798 605896438 39720462 818558941 431700189 564481474 862071137 393391480 483467281 873082554 164819307 523982539 566008648 724046566 397082464 715404654 550947347 635816961 216223174 63590620 345716139 952232286 66714520 156666412 397862845 406404842 484868464 397282757 302879625 906146024 254408848 506644642 367054511 492103713 240170120 475308504 687113741 580439559 124661661 557615593 127440549 775762054 641260611 164698280 375279335 836724446 287584705 395929935 113354583 650398565 828035626 643244501 300481604 653890465 402342895 823288747 823212780 708336668 213966325 179275099 374653541 491460034 910631991 205155269 58361156 841100401 520898033 967448336 734278643 287456456 16761389 385681599 920841495 503891904 909133938 699443416 460347621 628450416 618638228 992869534 264677712 684555817 355648274 579184446 390341060 725897859 639867220 913552665 827198081 813676693 271509296 619990425 995880471 217120406 210207053 69098084 763638377 411867905 252525598 434449674 75267597 441958284 794881976 176673044 461028113 694069701 337699669 173611186 435952043 3168241 736187960 644179472 770394311 632195958 138523769 829700432 675093686 472857225 460559214 204256433 743995069 692404654 229112489 692272829 228130750 634431753 16814050 964661214 437340384 821569024 122006623 539978956 207497743 446822031 351391567 244264465 51979905 477876526 507262355 374956629 323514771 757690263 525216224 697774898 969003251 91887801 537504589 459092000 255581295 641411475 91186359 22260763 207115611 475648009 1612616 77999901 372128556 389882671 712666030 136079010 894300949 523138345 833251819 214030460 886289996 772739228 666342244 525937862 704191572 618033246 313808224 352616314 164912092 111644159 333968298 321122567 388316182 503991022 54798101 160630703 350156212 719094889 298494643 445077611 763017816 421518116 517077760 180269080 308537204 840933132 696123121 326875014 104277339 129130900 844146816 826751490 287564292 861134746 854795702 324835289 32037482 436107176 84887552 478722047 490158143 821430494 605701259 423355094 850993372 419603068 315058925 14267279 11428901 821837414 238983694 584859360 257582756 296670541 168078021 829340693 926296539 320572759 383350100 246702502 552182744 35040871 987022604 605719627 76026795 514488936 104711928 680075838 116980054 296773215 511835158 948558569 143516762 462572419 634158761 5761875 71528012 506399807 322553597 215496193 110079594 297532421 766087107 710702550 324003957 22623878 66338754 891308493 96654406 86023632 69222502 126775379 658586 105435920 765194347 30610460 902672532 625006992 684630387 316356157 118815245 327543879 237214306 244344064 877174165 500014372 349277739 117151297 436684558 407894330 59412984 737839272 25853659 354690758 334288142 72391335 64578221 235233565 786131880 916582530 21115778 745603536 848453 413836132 554767943 541679633 898849254 223585168 238407026 962081940 923031885 35328680 756508194 794279331 912772968 977911411 267314777 471985212 440635253 377627054 505890880 353026937 458610238 346999926 345600397 260662702 965911815 415597743 358264053 754897181 689215051 456964370 437885698 193044815 59582275 243843715 823719936 34908792 620816456 706604847 772708483 840625677 467160258 78640843 756725709 264408336 497440717 289902758 920013197 668430558 516390808 709105962 177046692 557485423 139179230 957377111 680463672 503135560 999839885 843292091 368871196 760604226 483125778 260624921 360452531 983445052 887204824 605449679 465368158 480836796 366055999 687233389 614459813 757781917 795666017 933001445 458916372 164798161 867883355 698006559 740937168 998053839 887756086 881784299 522386429 831716706 415294646 377524256 411876035 895300466 764866211 243176444 227315423 82711898 377673496 416778846 532307066 693788127 910486473 231695376 270175053 749064707 119837121 330938938 150486774 658831317 57589506 892550759 789648522 873452942 522476862 306597971 277685154 905883496 452104582 99850695 937293096 840239765 223459423 989517013 413027341 989621802 725300185 488874505 591403652 185178888 176592196 599991755 739130362 234360018 253552410 665117415 257136748 441226348 138695519 846979669 586378749 483593563 988308023 688792269 797913176 851429429 631310382 673401976 564409892 244876260 378474471 279997986 743414332 110822346 110255005 158825214 360574880 14512293 230925335 1334639 400833425 881038386 178218968 723116229 607950276 992491475 893174440 307174107 843800992 933963621 380852893 164462458 841761100 171064986 951175703 743359790 157956833 788271980 523248236 257808632 50894661 690191761 558766920 221216114 263388473 293532897 461514498 650492605 953325333 168308402 971720213 371718930 32092530 73805387 570555692 31103011 713064059 626386012 755184482 644899588 279535326 473726111 215253635 769299016 425750575 348187589 944412812 329651257 904988186 348384242 213379109 768213644 60371136 441152315 788318627 316679229 129286277 451197456 358036634 432709237 912300837 504793287 137969587 574516558 127417271 318744674 761479848 507540700 661093594 3802465 323998932 55584788 140238661 434476025 43842621 83472086 329238542 621970269 440122347 786565095 829733924 135709065 782679808 129848537 89563625 800651284 310351320 829749507 575106365 954963265 863703817 871732199 871217612 227519007 199864871 21290694 539599472 72622948 439014361 215460479 540669374 264300729 947842579 818908852 235057780 184282657 484549489 350203266 322452796 583206134 89609665 458970137 939133476 666757414 154525291 263259802 285637330 205664684 152079725 21231329 217039649 598671742 843157742 905059446 54091529 372261366 842617570 276131389 243556965 993588782 256202135 38000649 34171088 233563459 650145685 839672376 654233858 518343314 330401887 659799811 133294037 55549059 775695469 642799156 889591910 253474365 141317505 915103752 895758710 630606938 360570083 715916702 351586980 671394413 187245528 368893464 368156656 99377535 831633740 54324723 244320448 474422039 990247115 380546222 284407699 815637704 245319814 241242001 809863037 83957708 106425073 262077483 774067834 479065235 155471578 423035474 950744464 157305192 247708752 637744097 835176440 87777001 424370610 620196959 647573662 521974852 398179783 81134875 76741406 181721493 513375440 307165574 42668032 629510248 436994995 236539912 134330492 930772606 198298238 951516243 859875488 220791356 384956355 888721267 940964465 458012523 951333186 770532743 181307484 5376986 113217899 797484471 99673517 822489234 855011112 174047004 140826278 334006792 654779032 231733883 433437264 939688325 417511190 463387855 642830642 351031696 121408289 299450476 547963561 341203853 693325653 671201674 786070550 415015975 623383541 927927931 764153526 967904869 78044584 245974078 315998272 887342492 44595175 534315949 108949376 273271644 94418747 187775337 731187172 625481990 998019578 511376374 947742756 819307089 738760143 445583455 461414789 906696890 535952708 338247633 320037405 65855377 338850050 82853017 478533063 719667873 920571258 914303971 573932638 901804070 819566713 811063547 431450602 107457471 985540698 883553823 562167659 581111659 691194244 66108759 204167352 986850995 711576628 475015402 218096623 923233976 344586892 878357770 100319276 378734615 915941939 832747299 387251920 510784606 792890023 290831232 420848488 639217084 42189012 91868811 333789262 526287877 753065688 811508824 843172530 343303634 25649767 62934436 258730781 764544248 607118090 401431891 644994424 779776874 327335645 253289851 203617796 688807428 416702787 878756905 141096882 392045586 25084173 769085253 705860794 729979506 596652682 220322309 507021280 839267714 208473904 953335826 866771747 243087321 274298306 423420382 295433602 80909911 540651576 880964335 37568090 537469758 903600409 596002856 354790600 360019178 245319336 399555816 836601273 798776788 741274099 671897309 165671948 360508432 456806057 787547275 173462293 595709440 476730810 985956747 369187412 41161969 913646111 162448292 706914894 581077701 470041191 466031851 931150320 342866538 610666537 277537166 918225118 98795228 535752292 758227903 216095923 800238207 949997031 716609110 317676389 684476823 129620085 703904734 965894702 994542767 867431513 851581909 665655558 528227061 34567786 490536892 294964270 141361259 70821811 533035631 664799465 553504042 305483837 817831991 769311130 404353976 994193706 944903131 521199724 214349193 143386496 136593415 122614214 937339242 808816285 885213833 166437809 989177381 407373155 605021652 494001801 459255003 390503017 811397793 534937075 572396318 577613710 721228889 540943723 635185660 140488293 773994984 591175925 527217242 2253303 999416879 130903466 26927439 274788087 787468157 371824038 460059820 889458917 519661340 930586479 502166084 195585436 208659437 66871544 845405426 579338706 529682503 948990865 286917062 191365229 435953174 541745699 618017836 415810553 290875464 603998550 115552341 890974692 510029259 499276479 305218927 789304908 420773157 62597778 626390416 350701302 498614637 279129642 350785395 741962402 485719347 64101291 900504759 107098982 937990623 178889234 45195750 581114112 769085417 30322845 294594957 936653275 567268655 785289354 791576163 440549118 27956013 858269268 361284099 331437933 656555546 300508933 762996875 354021793 211943260 838218152 136197796 214693227 186492199