10033
658479189 936438762 827405007 18675350 30142649 469457010 957101746 1653463 704338286 661226551 870780104 784564763 318996180 688079363 612441484 756400420 939789674 371801770 855853262 239154226 529685264 692822221 282765925 576804969 691019573 146114776 351956521 965702970 224702471 41930987 460434153 379913343 157948370 848038731 342295498 796557410 427375849 492848895 731572407 33739610 547312777 573450938 976397833 98815932 581068117 823065204 654578249 383646492 394506787 123226344 210708518 197045474 5301884 616696179 219928125 189930062 915615708 521394385 478745446 835250788 468221370 242957498 336723425 647789215 158876947 364107003 854878375 495966221 576247976 801597210 992769791 194481662 345951036 215397623 611115489 11871184 600002898 751861415 771969520 8542731 735369307 449456645 648273211 149219391 129428745 165674540 945377330 695551929 241160029 586050520 595918367 535992493 654324135 182857129 558754069 771642313 875307069 777615785 609821951 767747319 984978473 668766891 464499562 498530972 44800328 840510786 530540004 924163449 2690067 73545268 823392512 343430036 975534793 778339952 754170877 87975053 17136491 338739267 418435933 123047140 377946641 857681968 250353609 393384270 896583691 34327328 14348716 959756898 676128069 104396639 695535604 56198854 552862862 627609677 119627075 109219336 191924424 470045208 381224959 253864665 165583079 685862931 928139471 639867921 8474392 297172134 428839008 182362991 80538713 136274445 721271424 464368280 243585786 7245345 516611875 686902595 570833437 74404773 742826449 778294574 522293861 345599922 378137084 694580918 782722045 648858382 971410578 748886247 757080796 100152098 689937236 501588024 553882700 922956004 132803187 294838834 678996665 84436114 500039791 546866761 236964258 883495306 959224921 77012067 75391976 137526067 899090564 469732865 87118321 422012709 867077453 882451397 729252631 960001940 908711094 620659298 10569875 202437414 404752292 230140281 886866073 439300803 372828353 927825532 304477540 179495108 427030149 663676506 183442978 191411151 54656261 28750052 702408734 715806079 260478474 445822952 495634051 25784943 97126826 981008856 116939948 33732788 253120433 510556644 377418267 757596041 563444794 608473652 185174609 14948532 364116693 505346518 957363297 396615710 795862787 310986876 494125758 970621490 643985939 789693234 315374076 21485106 646721705 245573611 535422618 55010076 113923748 821141614 840365399 130850772 742582904 701420609 36321764 46857039 79059248 39320925 526326983 742745327 728510543 334220396 913402602 103666465 362839902 605979575 53618574 106915115 909018316 670247074 219311964 81303294 266513631 503852419 516834724 628099406 577635130 322659879 25900796 912658943 56276478 575582492 246893222 144292816 303136113 946940045 989623865 956786390 598247752 816697955 572074321 511465161 301183726 421962631 541379992 448464572 81354545 18131560 387418198 716020147 404335108 380920193 178722693 43307766 832653438 993631083 919289460 561407387 366754862 267441516 210717640 38742187 178978688 328309877 483073176 310060606 985855964 701994769 857470275 106027434 989880337 478103719 644750018 924514455 90978827 894323651 893278545 60248998 866504672 335233902 711339692 806119342 160560460 18819188 644785900 352865550 598545532 266746896 261608745 213268024 844295887 334156746 710885239 894013730 314788085 32694652 284063202 562533070 521048439 171444922 532702846 4957065 199626030 414780834 390491838 589643855 894836309 702082676 718359090 655868487 833673159 539429599 528742917 809777499 784830123 718564800 600014404 894150235 514025859 342852352 289467789 958439270 414449826 517012685 14515372 330942949 771114537 603092880 773150293 869563972 218570077 419298567 695308763 324008105 354757841 790134352 870824520 890656909 175173869 727446825 288993788 422613084 386261998 315584468 435883038 893991134 413786201 735413425 187183050 884763252 749062202 556410470 518778150 445526362 145623166 93680252 825336070 763778099 330087788 277129985 858503254 776705566 465641809 803278512 15540212 381530501 167891658 941510023 107363355 577839188 660418920 167984906 565861916 17566322 256716085 173253643 956821010 213234811 554431842 988131832 30571334 112021501 264884412 766656162 411437246 13201397 155820108 368095427 132877850 944811419 236535325 294606284 557573572 879862671 724024610 215319870 657398847 519572929 421770172 233532553 614286111 466971673 657613809 404852575 633594246 345284838 268426318 380312702 311509590 917544431 290175297 753410224 226187638 128520279 424171320 682829522 966555964 843575171 902196455 991946779 221413217 336224784 121247803 734350785 68148144 896731628 9663853 919936393 12442121 236905784 634938509 997543043 749614237 521505472 355038099 433125260 336359838 977333313 229253266 616831192 79635200 148042788 502361195 964842674 892840131 392574444 136156428 247796592 464850967 906586159 68682998 874012448 680523513 101010192 917802621 645728445 842298290 837533000 27040746 734172238 909446248 23614990 269422949 951269150 303642861 868665912 877376943 254702831 833333960 141914375 219921775 945586490 379041038 861026310 914469539 973437215 283576578 783108227 815442902 657605181 52266412 266574051 65183967 178938244 709220461 356549390 261575567 419027611 231560676 584510024 915691129 452079131 548246118 240660104 181370063 470922087 675545257 218054986 863456605 24754810 640937290 191356918 51198228 436785420 651567172 195378473 508456780 611995052 843422554 970844021 382324391 842456109 913650336 813275048 924636252 706702243 723463151 550897627 953013531 428251679 101458088 567800227 167595013 56736591 909229838 22106708 740036768 251852846 891212869 43985215 117553024 5455746 25934204 241000703 996471503 723337924 590436506 691905983 855128597 518114470 938690913 434543495 31257648 106403468 303065642 441447297 840845528 591898815 495793907 357406336 144342094 893929134 752257992 183508427 426411649 412652211 975144066 239819330 894061801 324027804 271823907 272930139 693901330 679747824 37322895 9263640 316888580 635526769 529954319 878720575 593462247 205883850 782797022 614367123 499077579 157228376 725340953 197720083 109051723 492122668 19800978 893904878 347005240 552911501 173764150 215446882 686057264 417581151 330040683 557033482 585966016 846074803 348296003 530103597 712023018 940152663 484501308 163557187 386127041 229197239 189847653 179589548 922070517 227231788 605274802 668616268 539703720 936092617 444675964 715366592 360899597 955663885 780697208 961410917 781673983 842507593 564382198 242949945 685034803 123491053 966642620 67574332 24429458 97431849 63062639 432698335 91202368 113588211 785232948 68049862 603889588 856018670 315155041 112966170 708074962 300437278 264216359 619916745 255857697 793902273 311335998 529816490 96408468 840355193 166588924 990276670 235663757 90069455 678547482 197277187 312058235 326152091 94774301 358037258 354697903 534833476 11968258 914566563 458632386 967967293 514261001 762954538 967268933 758323725 569746731 939098367 404445268 918100952 839124787 544620637 994904484 350461645 386417405 99610617 943268003 219321907 975564965 119246975 605574785 436106428 491905698 452422916 309413953 655448735 507841983 471496990 935028500 828884072 125867837 165474132 786520432 903162704 589221631 125169637 607654454 896796266 302516712 375387254 418215035 57540098 266095900 461239598 345796829 159416313 304919738 79626393 292463386 182111366 626413889 642617368 137077850 441526190 18708859 441670094 421126260 311428152 24159997 394699545 925913224 199672904 892121139 816988772 923006316 561136399 763646495 436848424 436191592 664889679 193012873 887644451 470601170 392366898 85940990 449280187 464256986 349284320 163732929 482858190 989648677 176502747 616184553 778535016 509848122 160643439 560609583 30108256 327322692 99046236 649771215 203949239 603847949 322786958 26691120 77399375 333836075 197708490 486698369 380799740 312863773 856401296 148831430 369750704 931961165 736534791 761115568 994490079 440311128 332729444 27054250 800526161 610187426 897971871 479876410 612315010 926525107 352520979 320722287 914031041 178837412 206754367 227349425 969646074 613285199 735879610 839934068 229425387 433350534 243886547 502129192 139797940 932486192 520449492 665256360 983157059 319471029 551527501 655670034 694513942 362812469 730987041 225772193 522653295 813307815 280650361 540801724 657065360 26992349 570826992 875771001 583939767 249756586 939361181 106277631 602567149 605686263 437226254 948321951 14314106 333029730 798904154 990056881 818922253 182851988 86124197 24089837 53565398 609906318 679390984 903782378 231027734 985334378 284412892 191762686 638741798 98057749 527860630 604655323 526615336 912215876 479880849 261851512 235548372 388652466 965921346 631931751 918370578 524392398 597598180 52818559 910344281 492171271 339903763 883363792 80558836 197719527 883524377 747578326 487611716 698533235 320797247 939135177 746600167 513743169 620581207 59195383 799165414 67397602 342495138 995044717 771937250 544464984 741497861 339127747 52053030 59827532 387389484 916742664 259614754 278426190 307699425 681482189 509696312 885188690 735550103 157143801 576622017 496823738 416966399 594338132 156234930 217389332 767796597 998775262 576896130 903692375 218878208 131528353 807981620 678428218 453107682 946841315 881675822 556873828 838772624 344876380 562678088 685450726 390842469 389872130 456600826 632057813 649716202 113740365 731910372 949253055 318764880 739655258 315833773 428987314 651531850 760638048 237852260 254139793 765213598 413141015 394538458 611733555 370564762 587302732 546260534 498720379 332451150 66997511 830212086 258171369 964911419 925512221 904042809 994300499 418030279 159054794 273148004 519122768 900972791 224254291 312759125 164789369 584627615 160782024 97381781 984562710 797250424 352991039 19036689 899741445 575974156 34319035 24204184 598230940 161053954 865809061 173577088 415390426 336136836 268614250 131206608 646962393 465793903 367967719 787572754 32761493 169506619 732680291 238875788 96176007 802842074 555854052 338099616 824177586 212834797 742982374 911021484 650631069 39367445 677144717 161873044 808724058 213585242 78168480 430897547 946899461 89205442 739444376 582314739 571132328 490578671 285315832 622587257 252372078 408834770 997351705 862582877 361279615 948634845 639872162 649726229 901486684 95443552 767332679 463342533 846647131 43308447 166405884 230436184 51567474 653558420 660195773 181568109 871312108 96507734 295825622 852345743 519412602 3763975 744428985 446685439 422422229 443139985 518362366 128022922 93450653 293114870 776680881 644163329 235838928 748693298 137480956 940726811 234235516 792962658 984418646 855100996 537716920 362594423 437757122 217926520 847482986 520800154 863159103 279076046 302682794 981467467 593082477 380695151 735488254 866117170 644796982 510765385 773922807 785694556 297835490 529836355 191709102 852301705 352534543 326716725 381791715 866460802 500900758 809383430 235994451 735577225 225828429 715853689 651346207 195160652 305457352 61865331 979977682 611579780 225553717 738197429 360607004 532859339 89613138 717372268 987352046 932119121 413055945 567459010 805642388 489636381 805154457 627768326 201037017 877900730 926162360 479603508 405026275 212629434 815267608 978605677 755886074 773608470 311272238 364855061 648112268 902527944 895618432 217081028 982587734 255607139 999934327 177316912 66643566 150449232 191254262 213168628 937392020 541484727 607526785 337439486 457493351 999891778 104835060 138122691 50037808 688572285 204051829 835628440 558164509 419852900 166369051 352204324 993379465 981770661 534885708 738392321 920186035 141412756 77417211 535102787 965624144 990634736 307953318 789927252 576213663 676784316 765589087 96483964 259691449 827515343 813137811 335259902 929354933 165953447 14322937 771267907 982013626 637205900 529326614 515807911 781301286 562437634 446989980 361311921 230356253 910860393 526280365 481446881 245677723 849141231 713368153 111582091 469597507 691547151 491577360 810708081 289798256 300490530 872564990 738413695 787016029 123422243 505184481 904660340 921218808 374636438 497229371 585020597 843734137 93575122 67591940 147281067 831516733 719413625 159205282 833141751 135794438 852378005 875407367 393608181 276703077 24364037 238744548 536525357 14642669 784994549 7237474 796683003 781309218 716287460 293030209 72016264 318419965 533109090 390225846 912255315 140334623 623272070 849800101 969589402 942271114 389956516 949749141 7812651 603145994 789191269 585016051 900737085 991314427 115220018 716431402 855234982 593580804 380777907 540835227 264474939 111580179 958944443 767238546 585381928 437320419 148872493 8209942 835248097 202808826 800282685 403585298 11068036 302533502 65270985 355304646 538898181 15520219 428285480 479248057 558865233 882909502 752092041 913725353 295868339 677482715 409203186 598450083 337311755 795721072 168267191 23872685 340090485 567378093 618122455 769756337 434793879 662030633 694714567 843250202 643102958 790391807 311527976 111752585 795674922 177813342 212289211 777940952 218729743 863593092 532966675 413432436 188151219 395444470 187310585 660817660 823627943 1670126 706411329 25426840 12784057 293600272 458827980 194568318 250498045 928347796 619947503 927978759 362348053 64361500 183995438 587480902 834611757 801396619 451010297 502921692 310075704 689372493 242943604 880752395 900147087 542108215 411353630 857263646 783480454 704522438 726255729 397601489 811417914 644865463 529551784 707358510 141382923 401511845 593099417 681902546 296431895 189780030 957862043 5641719 94697526 657690110 600166192 984671669 347830555 284485832 119846407 625092234 573535663 12328945 768993097 802750094 259608319 606707000 890673241 795954754 269189826 889759585 724395865 222137997 13501748 225957087 524204989 337659155 955475071 110188571 688634736 103848914 187511594 676859764 587393609 700013739 376971489 973386854 779847648 16060743 720764329 37171764 558730476 432441111 360277768 180388318 506422812 887573237 935633874 741648943 839901658 718740315 43524179 789582255 654342067 652592126 987063973 509691867 403857832 470772207 830443052 268236409 288405792 604457648 746528592 953968798 416293692 846776520 56657426 391025840 130106019 144440397 309255469 924046250 580353010 947718164 500872966 573301675 804337139 43954769 670528452 710295422 96510489 595375768 54689597 754446076 129838219 719432939 869522228 848949241 929912575 242748524 662934329 782145464 519329596 999145978 147153513 970382705 614437976 884412454 401788217 319522857 562432500 618903495 169082798 544114808 906378878 749996971 380323443 258634437 194097955 247534582 723762767 794634393 953875029 792962507 274278322 509321988 577191680 612855730 867076194 999975615 125788137 868321928 166765809 441329677 44864141 988525616 513211054 739958212 89877610 94905332 561450472 303773481 954612748 528780421 484581278 316753167 344401684 120302088 256555242 371426753 492682028 987052194 538513196 652605793 189455464 797454428 569738478 72899258 80348474 637883688 593772470 256016557 164075109 1279934 644158471 203918969 131232585 82535690 565252097 147583133 834091332 312444400 91430843 551067288 133691811 954407364 913385737 970179487 125518154 537768812 308447142 917138007 700905862 376247033 99396929 211214939 509487263 628541179 316460209 664615197 584190294 617912544 297767926 574683641 847672617 516004356 809533147 360256167 198556808 842981813 203810868 108152952 624883611 685749213 746756292 350719376 496517697 655416232 805092654 274170433 177634882 358341761 10697212 719184328 295720579 402413 874067367 146303113 838552060 735819561 350713592 741182313 739612773 491297057 28177349 853509998 281615398 778568921 676824698 462535515 745256401 533940075 326880679 291610511 386825848 642732161 874386563 868056322 951633266 739912141 634174104 890933458 610501738 177278890 918121962 785396093 292415059 201763739 654892705 670283238 279112011 948006040 972810958 934304630 175858230 804815434 866835212 64952238 675110359 851387503 958392186 336018282 811666936 669913403 755261894 29103098 886569292 745400571 77953462 718591555 993038297 546327556 601616038 743385886 526549726 3962663 226763919 30688871 467119762 390805652 559085825 400712507 207715590 200899508 363892148 341823565 526018372 734794283 466150335 486469189 267615766 509939171 885993004 461063308 43161033 555743477 904178187 535747303 880700415 458579599 702620190 81381941 507139739 499491510 790075573 434574357 267509433 805869366 176347590 677804508 444398801 142755918 738373736 722343646 868413825 675823553 395107066 396064932 868907044 520685745 853304901 653509036 851423836 66990357 338987013 236469049 640831426 840297295 80907893 304658379 272365435 420154017 520925838 257870104 8880743 317918746 663172552 762843348 338256691 570046064 721744379 541980381 641765353 795280036 846049293 328440249 281967193 855865030 496569357 297718046 287143789 785454550 686060073 740909356 145755317 695685329 783554409 135293635 61654436 273363032 187994027 343338987 124648782 954729621 781290824 169041969 428898906 470576957 647892385 497818629 209401937 39200477 672546417 348967472 755651776 721606929 953003873 561415411 934650329 579727619 554883394 835525549 716296171 424230995 130095434 683306685 985641002 514825558 196900986 500623038 628353454 187739153 669607133 952695010 438771129 344862153 616004325 536958344 49904999 407265953 127223809 961488593 124828686 548034119 386698766 126327484 998856384 18660335 674312674 74017765 206015257 425626937 470003835 936765802 600053577 259497124 671367916 228740141 368383417 589293332 241278536 305738885 479723039 684123509 710851302 736424558 253522825 555056949 160640020 455097928 739115620 628820510 693007789 583353012 682098827 805049463 458010716 997225489 287028374 421226628 849709022 636475409 151435674 291653591 934598234 994239340 779128193 989576351 804090889 784228536 105240881 410459601 31281170 321385182 923201781 463797406 825224607 952025861 898017996 792604762 466732940 999416967 878366636 288674214 756240284 800723084 226937329 280014641 126322837 803518309 66657471 156030578 913724277 492342944 786254268 533341325 426319988 292772106 565881774 597906494 907102717 798545133 860432934 313830097 233474958 808792331 647881069 143786677 313739498 175165769 238636898 196595552 331560314 272957217 132395030 630999404 150742739 100638064 28363379 651945563 795159086 455493466 732629673 504350692 83477269 165242615 827542525 67882805 112649233 128514569 194507811 840423508 584321957 91423523 621878013 874953861 932313028 418857472 632521082 76266370 138704291 826280453 383760484 759970430 85234892 276815474 229536075 133790291 96195326 987417499 297018057 97014460 129483078 652615346 162865881 894890327 750933687 958841747 972152075 556873424 63725187 397672169 688205487 169076328 847480985 847516512 119301268 512184565 866154721 408879613 423141063 582275854 449417212 682004748 47145455 581061534 301609161 853982567 261863413 826437083 172601587 658781483 288072738 596385635 683549552 370963315 80894716 969855479 33263629 920351003 522840602 823449929 15902425 917968379 275203289 796441034 324996173 944249695 135620599 473804448 542590847 54596341 353032267 112343865 125350171 421021397 823244524 492305207 878325271 164773529 523402174 367506214 217040007 281154152 104125990 84945630 321723465 79843955 427721516 448578219 326917489 62687951 942896530 70031759 757343869 461071852 264353797 224040303 716929188 401755802 504261778 234136107 265203217 491173667 409181930 57214491 629025073 217931743 390601392 275175395 950107700 510228449 121432269 175282436 546652551 31492923 461133781 479735534 580384403 806158839 924670594 77226732 68901516 406507243 155310231 114529353 752737056 664615552 583066505 963966758 592368662 77711995 831323804 124605234 106382525 443551847 597552191 512514806 746720735 735763029 330107747 504464872 742972150 134733932 987882263 911822845 465656955 692434305 963955579 486798156 298327994 550657068 345280162 36954559 903641865 387178015 1428955 874617941 82638730 244489072 786888555 846396594 81807749 596443910 269867138 984720051 657341256 165829000 822600609 707242420 937818281 628605804 317877018 575922779 553515482 300066534 364848489 941917390 503423711 45283786 476146919 828802283 482726609 242729594 828772003 692330584 441596598 144804038 849189762 278369559 255208724 753573814 881824108 925340833 236335195 728795339 796561941 421350186 935505318 803538701 282527942 414147303 458655429 331122808 972016339 381374035 372497199 602650286 80347143 335614987 474440221 98501456 944333002 178940096 14312577 759016886 122151893 205069857 626932939 268725724 713465672 402410709 484459194 656629874 258258954 43196267 457892961 270162929 89929151 833274701 402051347 57388734 207808816 433998866 497342755 768502872 768497972 157977311 579070402 908507659 834699781 537576500 218960941 455358111 990004770 681506602 263934006 627225294 760484676 371813514 959469095 683860411 624299941 580085045 640942851 197446025 70437570 685134306 250654777 853527402 490432777 587663145 168946636 538570466 633919576 763113210 649639604 731991857 266807580 908376446 220084172 548522163 362503229 428664997 766107117 74738268 787435304 806983372 845094563 940683059 490047718 390159568 965026217 718728739 460019395 561102949 287307898 243784500 423907082 813531881 99854153 609617772 297173256 666472855 124349913 241973596 24056557 326584477 992944504 419723607 559763548 563476232 762048829 89367009 35455481 430799268 828270028 968550172 740543268 86649366 614882640 472963644 422525513 51597230 883943499 327330373 566163720 391338820 266602338 779708192 135218868 569390924 801789238 85071274 776132719 5059053 561738115 894590935 108580765 115711216 212135294 868377527 975191282 984504966 266925365 502241857 771826871 229967149 892654368 97384280 298179535 703668313 601086062 216141101 242208876 712840399 318867329 209092117 383900554 618678010 716423741 175502564 617169843 756057819 849936508 178443810 459773296 424012359 510503477 141664961 45815188 699306808 214263340 833065754 847362851 499808038 785362357 462985373 735648772 593913689 481428102 314260276 684104121 279815897 466600780 463258632 772956091 551721740 473909053 667732865 887365023 792325191 290780559 35531843 397770482 542896665 414694122 236495785 628393374 901238357 842467713 163178058 816505140 552881523 174887911 243222473 442346444 909693273 845691903 552325424 784817217 589896047 950872362 169452202 977177359 350836154 935179002 281475998 652532823 526937044 639640069 513883391 564130797 844460576 341927220 904245877 952349577 163160578 389294335 39081618 447796860 422114357 23972896 207735070 795861001 488086965 220945971 109505105 68938498 835774895 168938073 633291035 944620333 572109022 189619498 91458378 82241594 98190079 815138113 447532623 361443015 727656047 46563116 717549059 704958666 424236638 626763695 752474274 152989178 337719012 874345943 647991007 889587267 275426237 948726768 181605163 698870893 126844493 892220255 270207423 561252257 737689784 482945817 893829806 255768896 223725043 912709515 100314313 956201437 797211500 741393951 418863675 737897981 162260807 972024592 230157011 545769382 248172560 376607789 638150729 811098678 826701071 917979672 979805618 216643382 288981261 945331470 935487115 832227647 789622232 121288247 584818662 288568695 91916660 900939888 744371289 79398538 528700685 894996958 666420415 538515653 626933194 945570307 366617210 832011776 649447693 64543402 502973883 534657925 530048478 259608832 649658341 33731227 58956161 639981112 530193816 451331099 506081272 551056387 844756466 484668744 874760118 187338086 374826525 172144308 680019587 21422725 556102266 962610024 41074194 528202473 432760406 393388545 957345660 738953133 421891836 727496351 167085727 482380113 810380074 718554478 303987482 277705292 519322035 723321134 771197139 583923906 499486640 226919528 721744510 856928153 887610424 865558593 111878010 949785549 896888321 966761485 969300458 722696929 227127233 270225378 706346353 425243106 927242197 832907135 602959246 293641233 782158983 758452887 610244274 390132451 283310467 900132282 538398464 561500861 570153875 619955362 759942769 67754059 704329021 189090965 323799930 468758073 98963323 778070424 479910446 135862152 497591312 964404680 89085776 333105514 619446138 302440299 881938955 218679285 799308303 582904988 934095478 748579060 328569763 158170584 82147860 824042579 625203888 568287378 346551700 657387809 960849223 449357113 631062470 558282321 927618420 393835128 89906114 956892804 904060180 689886948 426433755 578049541 524928071 952578235 360351715 298953810 653898478 573578305 21990659 243877165 792053538 47272570 15128104 31692997 322515794 626570153 439303238 553978099 344465280 614134215 139603339 811547874 925839285 489935440 517660962 725286013 585973473 163178027 506923649 852351668 575120297 584896650 710881875 124219849 942731158 218330185 886296373 430219532 243560374 362685024 219872676 82588701 509536318 655619595 252771843 181155680 456467760 142218472 559807297 476834903 186058098 253318727 106837583 801922918 576380744 105635719 249872454 179831829 450589991 849220940 289454838 876172648 668804014 62316272 848213372 403040159 101587400 105501937 742233150 738530909 863607695 266376351 241541075 20945479 180133288 456792828 801052403 229213697 825726431 852714552 626298681 39567555 52451140 68570867 791295822 182428829 136136902 207573209 173750605 84848594 824636616 93100289 565758311 751507338 861423800 218875487 667606873 941514207 519906927 546249478 119938636 747155007 159335489 861481628 994714334 843008569 170890479 8561388 667193312 183607407 635989172 404330002 8461594 187601082 411270395 158729896 687815482 857899232 982533855 24054846 543125089 58492790 227327378 718125878 387536677 804639011 868485209 482261159 129257801 338096645 967136653 78625520 865496705 677343046 404394583 369706694 748344969 795117305 658133047 768216549 184062586 929995641 374173887 582771673 246126566 932713727 616835327 98991704 535817753 634142080 460613214 206186382 142251238 511283004 311367159 648213339 98019783 458983612 315241323 72651288 622263895 34601751 867542865 211091504 820527893 770561033 664468383 457910371 361988077 874228475 979949572 502033123 2886310 131943101 750881308 434812711 372428685 627452729 608111529 540446829 105990369 867179606 295920917 993271132 130248639 843924636 451696677 600764918 325083204 480327380 586854025 963087635 399859036 888507263 153190426 103257846 368624387 526844256 20749241 672317352 779860533 906374786 417996579 807106263 399572664 71828498 943909417 69106938 441554812 80892663 340930075 868266218 834428733 33653512 147807960 169505411 343797255 95264893 875498528 614334127 935713447 595303241 415611694 176602292 447702837 999527677 881024807 484785992 425863705 881900565 452047309 24017156 253242569 45574055 921503513 759501501 563478246 316122542 776094152 859021041 142478515 838255740 209183823 47380564 407799377 661876577 810376541 798442455 294884619 390313421 210330476 953695238 379139246 973788397 251968098 327325284 792047263 368632495 901408240 18256877 999693274 220520802 395354816 347182564 273094694 584404360 338575951 277604295 280747372 665101008 807392120 338948498 26242961 871424232 965585468 960433709 965722720 237125848 934701305 410848528 281082295 163439356 419822395 721590731 41041118 792808980 770513952 18154906 842393456 690732494 424885274 391068020 778672053 61728343 582764637 377152731 660148080 157577272 769744016 33872772 958148359 440738490 657611896 870418021 211139578 382849183 568545182 727529935 886144437 700055560 459035635 904314982 416654009 713928046 912481950 926268110 438962134 809632601 464077448 603243422 239789475 872184960 255922266 547775878 335324393 544981896 709516901 735562560 193517228 89940443 115646647 96114443 997236620 606971398 849384784 35271387 634318640 718026914 557537206 82329354 415305404 502046158 92132356 387245012 92137444 548603818 511961412 437208397 46795866 388691198 149690458 228913232 562730729 179396366 138883557 289163363 437500544 687220604 971462553 899059945 664742623 721382016 165996932 312441133 379798272 973204659 654014890 620881956 293861446 548863916 447738812 395743063 982160781 964387598 16095916 3683289 1208984 252575859 575371322 422189375 647623930 220886055 415918189 429685080 394352687 166608497 572535378 932524657 812163439 386298857 601778364 383392622 642855678 879102250 510601047 149349078 427155430 159838883 324791359 222532677 610344350 814954942 979080966 452394510 169991218 463050249 962465417 82943904 282450509 926281173 39243129 127068507 332567937 27483821 734463830 579798825 315052069 175950489 629412411 230495137 559227293 257351052 972752178 742722643 775921683 183883947 346882366 615563404 376339237 405762761 520761954 845641986 297261951 310151084 69164041 690379610 397293886 490068292 562426223 373120961 186879868 973708988 160792568 474878953 772889865 860715856 689045389 265087749 358839812 443826813 421806224 320416948 198127457 55471893 65384416 729324089 839445522 389543841 279350107 527934929 287059673 913971155 142010754 415404697 478328991 212033154 978731337 735271148 263571594 105035618 587481823 810638730 84411866 13727137 255414980 378324275 685712370 272450402 127577058 299864436 86167508 515997275 645841559 434806729 155621546 113609896 714284975 342944119 140241623 636924015 999422478 753460169 875855004 153043102 902080814 717862022 312714147 787692129 282494287 618829096 661309002 171593261 607467854 999395274 430643905 261766720 194980205 665827865 178544536 677385419 270116246 891725659 621612062 640600540 883232776 724720040 861716928 478605415 786786804 704054990 890506870 380028487 988788301 609904919 517205177 151720815 786171405 607024390 654476911 107491254 334307443 817075161 45250261 867438684 411607995 263634390 903470647 895757879 201217394 928990178 976305683 823589091 77588559 113239719 16255152 679904167 422810878 715041289 201843861 841035364 663462637 993784718 682054344 670363258 220187005 544007998 770231723 330352357 417712443 824171986 589184967 525150144 427060548 652835420 696354838 329645443 418000685 480412306 620789613 882350394 12545874 819970444 5971969 571360871 76255748 16014114 505063155 57247995 561244426 716935754 39572633 376448571 959627578 494513835 768697528 876970578 182058622 189582705 399445290 975036743 418921149 943120777 876417583 451675795 728659185 772072124 813525587 110073604 314401836 840565075 199935579 961780300 294845723 694288164 376548923 216760116 344889076 150781249 816931744 724370786 601249795 679064378 768799940 185865202 690317436 172562065 253614319 22158971 563431586 190622282 221511676 793095151 209523121 122650025 560444490 448660747 529496818 196623801 471990126 928707992 979987959 832029282 396215303 912048213 896352498 827915410 169584438 668889031 709165038 803516488 764763547 283839570 631335687 69564939 163387210 818653002 699508020 571234678 544982132 996098135 129306992 102994202 523407415 442970243 673856094 739967491 227976779 537354669 584454725 233324744 483655150 996669547 456528389 556922235 96736078 487609428 824773867 206708382 739698080 438729554 775812770 439533589 395089145 884052554 343899557 489867836 869215806 760194446 537447884 425461055 147010548 920691242 481249922 54655976 551661845 546743546 482131246 596740591 493934880 868214415 790743980 273109476 752786926 186795971 546773635 706716635 80081835 500551435 198142947 675752510 450456253 461951319 859428535 388989385 65376103 748385218 88854352 748064937 238292075 822957276 857909687 435680194 962723741 679913446 56827302 157307719 684802944 407016492 925326937 522586381 508383098 761999193 67161797 68485788 639239785 672970046 154714446 250029019 444672804 670328798 436771607 746568011 457526325 961582169 487083647 52525551 436640385 337528391 327715012 589269071 36610416 770925996 607502108 351150301 90911158 655102956 12369879 51618748 303394022 122662246 911465810 537106658 81390819 122141012 274705468 243879562 813219082 159884433 297238803 780995668 891283476 132505330 284053859 264946746 149839974 159235904 907428124 850440145 416134106 334843623 722396381 954744756 169879134 435570002 982114372 604719446 765304370 60648333 504993427 580915674 299006429 519584245 604343076 719557880 747102603 217994761 244436066 531785375 777388293 428300274 556301621 61678891 472275456 288024706 852981053 85917848 684530140 47826872 161425672 911665457 144972749 949238896 640289220 721725185 503057136 379640290 199456081 402503511 429801451 291287526 310818957 867509836 280213089 762791299 594874341 370641418 122926553 644228802 949488667 337355974 901638466 827480818 188283132 651221401 201446870 108946981 759558656 444703961 11582536 328083846 8631835 957429668 529359413 540691892 858274162 98019280 629870327 228479434 596154047 87220366 726947821 249369463 982450418 602713179 699077974 145834738 220911618 487547370 755544168 942035023 747503027 828035403 973342406 849900253 329510030 300176695 900733086 456994678 813831655 870727559 908290128 116651344 339055152 185690749 73929991 603039604 898768508 980935127 415198528 181122601 78262598 163554183 473260472 238221375 417815225 745228101 714841226 654149110 492021357 350341200 721500678 724773756 146107885 204740456 530300869 941660134 772768332 193079320 487583709 667966845 78222553 577660220 552325157 892368056 557882142 460328591 137102004 863493581 945083596 905264462 177921265 237554264 754141392 948551620 686267798 582140107 57842179 251874825 281340335 944128605 623118771 30250469 801259854 136241187 480603317 863560495 362325001 339120842 577019975 627153159 78812071 42648958 642128915 672076985 767703988 297805250 614519440 137414832 159027844 898439363 442522832 432946039 2828754 386038113 183924464 77273328 98412225 482675071 545243813 592936241 160367746 590063264 257860522 19341914 796550205 211871378 585558541 1339861 427706005 598150933 544270629 735658383 311022881 405486050 477864316 694773576 659958995 797945614 983038206 934280475 965878225 254897128 832633817 639243484 781294627 830829328 497032726 781779741 405757069 674365902 178058006 180287516 64928727 357062697 514415639 320198652 305104807 488708527 339749035 737496312 300583875 97598477 615291571 525559678 557755425 347033837 449272279 208559921 235933360 611961516 41143762 968342024 57194727 47330270 103159770 613830114 777278735 285763829 977014275 259131146 496558551 483868722 679627257 854676626 754842916 743996310 569366343 854093951 160475186 909854136 830462449 503407663 648069309 739456052 388231041 903346710 480398135 253752392 780617186 115431143 339275114 149373347 608738388 525022908 231657254 36467869 323303845 598401260 525008271 672448934 166413166 262850256 884685911 271415629 391744606 576790019 747435237 103496173 508216313 67152638 16750191 959407365 115455752 193177277 975640580 550899335 837466890 236782629 396379777 602957359 371534867 943547573 883496038 680872251 651997160 462615012 183843361 611928989 432786919 435251357 905456748 992134794 578649279 272719860 385211408 270096873 741181753 860318152 503742583 558324765 779977519 664152969 194218681 928602386 452410318 17238161 319477864 378363940 175811054 835914791 245484656 702202961 671930836 1725891 799459019 426890144 738601683 258947346 365876161 936057485 929921071 870494101 355576113 824095882 235078797 629369123 972539579 251960492 321200104 292533203 135287912 251087346 159284675 806097802 621616170 655846253 784533027 407916588 718149451 553549346 120413053 566585169 521992083 255201613 999889773 38342787 540502505 470927939 204432962 544149792 334180426 512760428 608811783 596755177 982961848 454529810 683442744 31283418 978407313 751724252 894869546 777426628 247166834 159712359 58744439 423052866 633627170 790533394 812914866 836280155 389943893 687558192 954982797 444975778 983875281 881090514 50831145 327766759 209099023 185652230 511844835 705749168 986883182 850190754 135128334 929317525 736262949 445677095 864939303 49901760 938613468 406630699 380379284 336585602 686640811 377759264 651181875 487315606 531502677 128828069 364007879 643342385 496673320 902057419 36090465 235201089 575233552 211953197 504441660 358506095 655165807 879548500 211249315 166965407 144489636 434461633 76889632 781199398 384125472 161882042 598194883 228293152 369050196 469672414 218805974 848630264 656591357 925373797 281845953 594003370 617300135 561922262 711243442 705297145 866774922 111509687 960953809 682582609 900448354 770795528 197383376 654148538 623271357 591279950 55021602 424402635 267394596 638609175 142756915 267240837 568798491 644120478 268489345 242474042 579167781 952156002 1460317 284907020 144708488 599402956 479632463 458720421 777045576 599268613 591165088 900423735 267776413 320882835 664450299 749363123 967730788 166897431 27495141 506179868 984820777 433696128 428390641 107628309 109375648 137445655 324349013 148646283 71750645 463248582 914133965 631088623 283047922 41501763 87269140 361267483 964244007 663372030 580637514 94061327 38927052 297969227 278297521 542830573 675176903 966207173 674268846 129524496 749013545 845029493 110429681 545943587 290508445 859404067 598143455 68097231 729611889 382556089 953234077 506393075 440565450 930528439 837892150 911688395 605257431 320852222 829583758 435717460 632206697 617288120 877556880 402134454 730713981 137248299 317612683 690099215 261113958 293720421 902999205 74157727 305770314 503181077 678120455 82443708 478671749 831371207 489308360 194934032 668633365 290402341 62910030 696360571 913005656 89927532 995616074 821632936 160463065 400729166 445587157 304788798 335967660 895335349 637360845 615931534 207440198 286779556 993684679 842119577 619704004 595286370 750002490 495068855 513350646 510439484 721944821 522208962 792044145 120283931 755610628 53301038 992377862 712711158 779514231 231859320 141431147 272192685 809548730 805888970 102202604 361258636 453407256 317719985 453638695 500067478 363721241 370608306 240537135 999140749 39194890 914026601 944693291 426739092 198713676 823252699 97559888 572521471 954368803 190059731 318327455 663930009 263409576 306463261 595432054 203515 69442783 767024744 446409945 460338308 165725336 238840888 925107344 962469940 829612994 314527109 74246691 680304057 929227883 518573380 95154344 401649387 817576259 664696324 151386758 483734781 888596491 431979924 870384398 62471095 664900151 716688726 115376599 965452653 624225096 425863153 151455331 343668247 404626476 137153233 66809384 36236102 587087097 477017199 600642885 130975019 812115595 833323704 171499122 398381470 397739477 610022986 104718809 744865169 460566560 684806147 797358448 375924761 936107518 434524434 334540410 306586388 315410910 191663747 395855067 411873598 927021622 241178508 436258941 616238468 156151491 531807285 875787975 126269486 325834729 49259411 432095007 823684117 435609788 728664143 737701734 611281964 729267897 767760448 470288155 222370089 210127962 914948814 612866699 417437848 118180438 438475796 803004329 979201620 85891598 523376658 333056905 827126226 741115246 306282859 652469721 413242136 504141212 502747418 889571189 875621475 259167275 705633007 803758048 353082785 801870109 209002442 479909353 361242076 441622111 311571980 267213490 329746493 97532323 191149347 881218017 250039915 479470408 226926234 570240819 345599876 167738286 919560887 857214448 514607485 146297852 853408831 140399174 635773743 216506824 874952740 644753866 583663153 281069776 941247174 729181138 816801898 502429300 775139415 720076925 575489046 314274867 471114155 338694312 391489569 231920861 563815467 152478386 68177140 918959431 633705612 56777302 648058736 513224614 316329122 631594337 344699393 232166163 350505994 87274843 871083099 706036755 802846673 210244465 501268631 763292934 597327225 924908843 965654625 516888500 382007443 893030620 540078096 133544739 700200883 804231357 99325428 866790637 966945169 95542928 566591291 627661161 882668228 933822937 163577010 505449326 855281546 800220348 756157653 348412303 335444319 193135886 942082443 32226269 137483985 59247440 349248430 54382919 692605417 342040774 339481088 872682991 770608926 890733583 998435319 176570803 502048553 342157634 337625714 870451404 334332998 365978497 903948721 100646008 880740886 218747957 67492381 138767516 49874357 880367730 96823710 354651270 466737470 980206734 277747003 456511600 38403829 339925391 242498165 366618494 152987460 267661822 314547956 408598017 821417308 526550149 586209262 93102832 748036248 495908809 182014186 242549476 470176411 53287375 130156598 437756248 306994844 331751723 504332848 228971442 862848480 384875405 23151553 216234641 367835912 621111501 16344145 717020919 895786323 611402354 709696949 831614020 845575566 345935556 287684180 436539886 146550511 297365779 761417271 624642875 972533690 618215378 260157671 954219539 860245584 845283147 479100042 636943380 470027913 331752769 523441129 362002295 40391869 133366401 590744622 961041906 934669179 455460962 592038154 103612705 710033779 971887778 276108786 281098675 353204080 247181105 744349141 548290563 971703853 375729119 546123979 351846794 483092985 213024227 628335706 233701193 509731643 534243477 8882410 208741406 752610432 396810603 764490821 28597717 540583685 739203786 569329508 160421666 626692468 710815921 905517601 305145998 966118965 376963031 129905859 768866966 37754236 547860695 853559182 677110711 519307961 94054474 635653990 913927768 748553985 130264200 855205536 102258048 408482969 444359673 949185999 13650556 62888122 544453526 456335240 62629903 325842152 846170599 974696751 850512201 641579669 105171787 962822639 114501644 113682157 531370107 446706962 485116777 556592423 319267483 57545703 822835331 743427607 449943679 307483703 26248368 797784451 59069184 800863665 651239459 856670013 545413086 616210734 870574948 320094735 560690965 723033098 508350407 257347096 560173414 586188428 824102938 649569789 527694088 374215443 189276059 732390319 781300287 129813475 650733429 124485737 967925628 632856314 118103686 589436107 96906547 522540928 249066347 702874171 654707179 294296552 627608619 554759309 473058819 631669022 734057067 868699757 304924238 771389750 706125281 989618403 871258311 900295490 112886102 651301031 138389467 773241125 612506142 56962235 307417386 297175965 753306191 429835181 175269881 687157841 375568627 10910482 160736929 124382729 904926650 175322353 95975960 991517462 691991389 837410882 506168335 164941343 680879495 105153077 852508913 563476267 807869782 578600624 915770264 764639301 203581819 287491614 718258939 61898888 97925798 679153684 739538754 586570999 225791646 907068976 227064470 31943307 164054781 301765715 962259669 322194934 411557485 304017052 295552964 4646709 619672739 247484698 907919045 450425009 216164794 804037980 531302924 19874079 442731775 833723339 641039192 963401479 77722292 164738635 439923877 756259509 152340326 188215392 797189873 134224001 771714980 351699233 452316870 461275034 429057674 930493969 983980167 746111171 443975432 924603530 485704415 396388335 934030801 421108380 876374396 260939883 628211139 662309652 410466664 655656849 290551557 585793046 357628638 714477532 153983775 584074145 106981792 371019138 261084135 35227355 973743307 297995367 65197684 226007903 309411962 607267018 494117 531016101 684361693 261757268 306791249 987574016 435916948 420921119 311181579 593312531 556794691 113768893 609643379 853810035 353857425 921956034 962329181 362726102 13669978 474626431 659129015 941199550 590606842 215958267 414341943 541559538 449086390 85616255 688312438 108577929 282195531 475733423 799487529 24988771 652133078 247767240 881332862 849290506 94331989 936820426 818468757 132497878 181111515 801029322 142464972 324401277 380647890 234661868 64335257 236308773 140605779 949500444 895417676 620900369 573996626 872649448 913860459 785896988 220433054 432396476 847210279 454822059 389387360 591717800 723296723 861364126 907408586 382346228 465362222 949385244 571806726 51381081 328491944 681381361 260165875 770793738 971063441 427291748 813892789 647187853 580178862 240297038 900216129 391811648 311080678 707294031 379870073 164273449 586326679 492145105 209628856 957344320 614114876 725089747 299894999 456857088 462442614 183630180 202926420 222320713 794497939 989500640 817569737 510818860 705783306 392729814 392639713 280213580 258100623 787869466 608398976 956133035 48282694 121170093 618135685 85644482 44255859 319481873 80871117 535301711 963831025 154527876 424749798 541970710 589281395 190609602 737231180 733381456 782896642 858007093 578987656 658864773 758553551 102433055 293403774 940626578 789945050 549135398 558004646 159916957 116210143 943844681 987093444 782100911 227862488 212645985 567024503 870176974 806282612 971837738 829186426 502100343 917988545 986742929 203669871 424820635 422027447 647548176 371616396 648382892 562378140 516409146 964053006 3915845 692664036 71980206 554495900 613640598 854637050 884619930 115806988 797607124 469455299 185979034 984934882 591870843 856146881 169014043 262646899 372832057 832115251 904825049 22192210 936166947 55223962 763815736 943909085 984198155 785386013 618804020 88302382 681804798 477322340 376956215 41211023 667891041 609786843 885278939 719329368 39329067 181698069 948816692 261252090 653068607 675047757 975167069 186053959 288405943 288285104 72688803 423104209 378759110 630453401 770271910 14694918 215641774 597798110 874885673 376854818 538226040 160689878 664148645 720386573 957479201 616067287 782559581 918363327 594285951 344471612 11153654 321269337 114175757 278367166 540433637 32210455 447334184 333315054 610149686 392883284 726069217 454511069 391370689 176649237 430572412 510442899 448799651 647121205 639169127 455938544 784886158 145280649 406798446 122754245 228166247 337040060 444600956 933683410 945953164 669870722 676528322 913849863 561593445 424873308 308053751 462443222 185301272 392970877 36621661 359506066 382847275 494885558 43360423 161161324 287564841 312399191 273262838 143497891 766202249 266663928 952540570 757052658 494068027 336960257 205803902 712401505 123928012 964205957 965371559 213337952 928024013 164487733 828989121 432346979 921755840 372288133 838658796 265695189 539189402 322965920 380017728 384951466 516239909 344123145 104668311 422471837 494468578 961986212 816143058 939678141 15505229 315949351 917398141 230645480 549833598 148682667 171791056 868502587 969576794 781267869 689508100 535146972 702599083 356081276 739153216 712027874 208115269 692106288 289480053 264935494 723327202 122888676 222808196 551465875 435430660 985618177 80445555 589217687 960041125 581429765 403113730 338488607 589974502 585403279 445749457 145879194 586780059 774336083 167933234 431481701 765345301 989862173 96075015 874277604 946684042 151743006 597978564 676829745 890533647 613410721 544437461 385995589 533489096 10999120 630373179 100301094 411064098 173909700 319570172 378808263 531987057 979596952 945968235 859500451 765953713 463039726 860929873 900947502 927131072 801169774 253617038 38438599 982159332 150806375 530882409 796630939 613491229 399684693 509256074 8281354 784172034 851055409 558444098 460310601 813676148 274630970 695167474 640644220 543998700 248732001 881796389 897273810 284730705 106855281 49953014 902977940 925687129 401940595 332968063 220969870 104064414 260606950 151784373 132695740 95980624 31523821 866931968 504708325 601838578 523416385 136796367 937174957 505108173 121172180 920128011 452897170 324020207 294554517 9256712 917630276 562400879 82491357 225564869 446931402 649044230 740490217 169735209 302966472 84809029 463181032 859653214 147350389 400793384 37724002 611730716 3033039 358680261 968483810 88859637 16684839 381977510 451355634 221319633 677629066 901134839 109143683 418629789 214974989 801824680 110811737 618474361 78363640 354612252 787149838 378373556 947958479 74975094 812969769 131405470 373652205 944641136 168087567 343145123 551781025 107219719 45544412 157322395 875812402 653909724 777417776 436635402 239602336 93446116 470282571 100442007 376574431 232705302 607928710 654437915 321794684 654631429 27058214 658497425 358372520 975006771 118241852 607239869 215741407 126918164 688074675 653344832 962419899 252845218 349779093 20821862 65719387 649736943 111381531 615374217 229967229 857232905 567513650 648316464 650405973 806280180 467845376 970962646 453702849 299915988 417845851 401509345 197142142 403345052 50547513 327708066 974418248 555462736 297409475 847429793 833214742 274207687 91207997 859881580 609810001 636075819 390193713 884375705 919103045 915343536 509683045 505900026 301098679 633559097 676646189 787083401 713550026 441103602 483421915 500704177 220212611 570910749 728469825 900120537 200995811 279451172 97282000 394833380 625255618 368646077 699825544 198825139 735922898 248536173 113478865 638863381 890586556 10791022 956871523 845760245 924412205 894998843 711226993 64311702 970380709 162209945 554712576 592502275 786574860 964373021 912720781 703530830 302049749 418777066 591541606 221378604 111584982 483553760 344925851 466568264 286251893 717126687 131568794 939598045 781094517 473654335 550139597 168854044 127259111 165810364 307865624 975730977 140362346 830995474 366393685 45776662 888014863 6687071 876588811 970285367 398347213 437634836 315989130 985027521 401034338 575408920 433876435 87357007 873483377 978757044 804475992 531831264 915718485 79609157 459116490 568605880 987882539 107351030 720638803 282497158 952832963 386954903 36786451 15204483 518790179 655326403 68607418 666560570 554991871 412971076 389611590 792876359 182161917 955778337 756625285 282552270 95017797 30532634 738156426 753301567 240283070 365665910 219162567 986579009 161504058 980829837 580179405 731573004 441836280 557115371 92335437 903048018 410220188 152314070 366507965 748221246 602385660 467480515 207991311 780235432 799038669 369965483 356777160 17442949 589891163 132279297 857212662 133657149 303487042 459693850 754933977 674310293 391113407 475411873 149096975 100923777 516792 328281537 876310466 513053906 225482110 801743701 339619709 796483267 933473439 56490863 292468558 327950647 308386341 508388449 269935628 338995199 655116721 74433875 344520078 401181783 274821333 742448262 346382302 300679338 996339513 471048310 881104306 372823354 866251669 506883759 734920376 228105110 439457162 984151094 159045222 812800293 527483376 269015916 388435763 669857047 886803342 97782745 29774229 662876589 552365650 180929692 703384382 80486850 852181628 859760261 566669591 915237858 64258255 417799949 446207667 168282649 434942569 568075201 926555626 127645119 598843814 636258100 908604110 808885859 353671159 622974391 621087515 95552763 256836141 169381297 894345220 379862049 630133553 464283852 819598147 372903399 991350888 230301182 708348348 436970540 722286363 305010153 928817487 624034213 144214576 776688327 870520827 812250446 673982610 455704201 332720186 373335809 332567492 553439566 362286405 665642857 543936199 27196670 586346505 389562577 25885122 905237619 714299639 164883146 387484365 772201142 433801953 561529590 944141672 148617613 741552849 861690086 222571416 419702166 782579041 703620609 402014960 195187882 137171127 968658596 766161991 992362127 601020416 871352281 593856768 760557621 172468902 569009215 908772417 376436281 753020016 366326318 378153120 217875560 835261473 100070353 664189032 377636073 422708678 298109223 211215315 541152562 649578599 45800789 999913393 288759055 953055767 379396766 516057826 680825754 209401155 355593444 712743922 286446569 504359114 140628857 439785745 778679894 466338292 562483209 770983982 705017796 750824449 519168806 763291170 805606483 508186358 211705509 96810953 584369449 525413820 243055747 826098812 990988636 129046523 761325906 108352170 253714019 964050457 896267139 477015338 189836366 669746855 669637653 43529064 193278238 924476747 119811843 252815708 720601536 122230327 268918963 531068359 995035048 650560945 781670072 774793895 276712208 78230072 162515415 440318451 661968918 608736148 448143871 856595081 314350179 972896455 583860383 960331486 852355497 423854235 288105051 273294292 174304543 860894871 779645243 872306998 299711691 479021597 891114438 795973652 133398911 136650918 208785102 756200181 349830587 417771405 831913011 727335394 56548493 93003590 300365114 921838886 642026565 600629843 834768591 92887308 801445187 618979412 440717215 653668971 382265178 39472226 914538858 181385642 696620018 896963449 98706628 943183639 932696436 3107598 356803602 409059909 793477024 356516139 482123616 980372540 674817411 897860970 100391001 80881517 543882203 790125407 487009293 84194682 317933205 463979149 233944427 880121780 150408671 638177333 101065456 749297057 986101109 311115059 762169399 290894210 45901424 545660174 298001087 873062752 159883498 497591835 703127778 794345634 449203251 781568553 367074422 122269687 671961176 861931299 169531506 113246467 427683294 436708519 608569465 958293098 550524759 616593474 781735317 923107799 228424291 7516925 352635897 286145109 83271363 464685174 303347528 943228713 848524488 493398756 737096743 920770153 623883108 488705135 721206810 173763388 379225654 163595994 743108652 945953858 7799677 31292707 525468943 136614007 950557978 657770309 172177367 578510883 227070489 936592050 785867462 339725022 71235 325995878 23140923 783918124 211294569 43328405 999569635 781173985 383583707 333755485 798567762 403679592 957089320 488065680 775759981 691850723 699045674 954108981 747255725 857668707 695342418 76002764 410295760 704031959 392099506 64702155 752341413 832612911 948012378 854591312 404150736 547378621 612208487 280412550 772002664 266653138 589265426 591312628 901041574 243678148 61118406 956039970 766563268 824440371 199718972 293321939 744248900 519853384 874762910 786787550 567708098 115758919 522069258 741681922 872767756 935865159 310177715 900763146 170598799 868313885 562176496 764495264 567781734 701546321 616395418 721863570 477630092 328547739 590037262 457808728 352036404 870465010 33114358 941741174 894153095 225004502 437405220 489474820 9639187 957411797 316829488 439590350 68288819 525554141 38898699 248301778 724417659 555992016 125904032 555899070 555938373 818571273 245063870 649065984 102727679 613011302 869578029 644439643 630380478 797577614 164260632 679126034 377045820 492768365 611654485 695564740 633828504 371299967 488044820 864768387 22226235 390161362 24000384 969932955 161081937 493599568 714811508 421674275 201293127 958793228 404593979 894915291 599328935 407674325 825539074 260257046 334586119 994111845 707639546 544799396 379197510 68394531 315580486 521089606 625514554 670028227 80057358 270281928 779284661 53207616 576459811 298311263 188780356 550203876 975169832 208251901 339727038 283694619 432660430 862329896 849954726 886165066 620116367 350520458 374439781 755724063 277004953 67047941 729303607 253391534 379534005 744233042 477973278 184069898 831076329 522650227 353686007 398913749 70337563 215392493 809483646 292064079 911597608 979337973 64112019 22679943 605921336 328347217 778164230 550118321 405438112 569739048 806833394 834083740 459278817 240219949 75992179 973782367 250894882 424721555 705515334 566040755 308300263 23516022 492796504 938310134 897657133 774654287 944622549 658992079 212617412 669215961 910199236 118487710 745950015 642410354 722788567 942254148 438014830 299628148 758279657 633624043 806794601 939523271 904112860 800057365 281099633 737142758 374977086 794846190 226789169 854786494 463845423 651676732 200584735 716030296 711590546 465448842 423054217 333584150 792603679 720908588 621420612 967534684 795676643 28168748 317982281 907661941 564176215 669033038 903166606 483413053 767286507 122207052 997518372 175352897 753256781 787008017 971131458 639172187 814325338 850720235 482773866 320190521 400114464 178774778 415145713 340234504 733938146 220865413 140493790 109460200 492413902 755871335 432741906 44854042 810362385 729321313 727535982 420939372 675960000 444051316 790004708 168743167 143612894 669424799 764811864 832903454 16486732 874737693 164283105 297141365 310174312 936189549 901497868 288544637 399216965 680021777 556650937 77123186 129273115 215264279 15746809 866011092 748296947 732417166 196800963 36068898 471610562 25484292 579442397 601642640 756509526 367399862 470876079 284125830 68529227 906676986 499624136 425018921 182438172 147000615 848477395 745240416 38295450 50745789 808078743 240451698 214425873 139867470 998016748 331443671 909838063 651057896 742449869 7619328 627968331 514255294 614207082 561002876 114066025 484129781 762269218 13137243 120725727 627176286 537259771 155292403 55898758 981579535 792405025 846949511 394617578 802546360 492128651 794263713 969957530 832880642 759632062 746216473 837137860 832744885 795253753 783305943 949122944 90096304 686245695 60952619 168903208 982652943 160401073 247269608 894643261 39588436 816268314 223890861 397725691 701993843 417907179 961217189 20048726 708628024 839477428 251435280 989468431 688026851 21334421 261854119 27075552 240729001 515707878 175046842 846810528 436035754 189393891 22093121 485753253 181703873 509969035 854789754 200482546 879857191 153704868 846483310 972984841 854516481 192672509 744858602 838666511 673896324 596237837 556006855 258406993 927711318 206346053 325960142 72669129 21899911 369262794 578222149 809904208 120262981 41542538 755515043 88556349 38236677 22097563 162108900 383148424 321260587 709875538 700647425 599594009 185257368 9952984 552360246 826727047 726812347 354525933 227566124 702606066 838617952 517278620 426232251 198128308 432655470 496049750 449206620 438032815 917182957 825255102 240061138 347055464 630039896 703697318 607976561 258704882 430791614 56754305 412207378 404957334 393654821 932631953 569756311 508320225 196174601 681462147 90626734 132227563 422422570 57440183 1513504 664967644 920966247 655413717 670419165 782506049 132832634 901094598 213146805 791072226 930997121 134267396 25139305 653562645 44595520 370957951 194641443 823532482 249094188 710611046 907836358 847732872 890188345 638993992 115529762 970345815 398070499 979614443 953523483 263272064 815503871 334382026 640786263 173683454 455103376 880907761 401484039 341990515 366008732 74286953 320321256 181301156 653197503 370558702 124195590 103446911 917605855 807570535 200982405 742726474 119653010 118662158 210915662 307659713 714288477 67954446 248457400 998189865 704051618 416123462 468080622 853456200 482702084 773193859 962132254 780006378 705540731 225684725 111270850 256130642 893334668 191112830 625528910 761181006 71243313 632345183 306964206 794388502 146946029 53445513 212541450 840979380 6688719 231353546 129972338 689727999 487746972 738840259 803111994 511285378 454262768 756120769 412635705 721761767 535878590 295659066 817599254 373472361 86070459 251215621 647157564 577791481 512938622 116205204 211387804 184441512 325491301 638814576 884709177 13996319 981257520 742789170 299482537 872777496 438771701 660150663 379576978 787989533 483935398 155771340 277455521 862892160 740095704 304927073 333824911 495354404 551831603 812684136 344940762 867340208 758676372 374637383 400940508 380621946 967851475 813416161 724442878 896132893 396673161 164926384 220833317 161370010 609295211 815606446 198197803 151547880 262629596 603519293 700643827 911049290 491917215 701757992 726035068 476911737 437669384 779880823 327702969 647091018 567993073 405296267 325728278 434037864 831736301 580666296 21229731 302428506 27468773 979760338 875559279 800300459 357657221 397869481 528474205 490632057 779889565 373493728 607841201 738814224 861644230 981759773 737152532 219528775 85533633 624204183 609747793 810327270 463549891 934360506 44219839 831353432 51339394 139530301 304739841 525250101 844146042 757079702 254773500 942770109 425603635 241749117 833013903 455303393 880209350 174832988 674538089 464891463 544932303 160782217 720222244 411020002 769282028 94067987 989743324 849432024 260296505 463976445 482386964 519088891 317161021 324053908 467659558 854391452 419572292 458730345 522171154 688062057 823723716 774305830 945845205 492095431 796675700 126325201 16803604 313128763 237993768 365492370 152545035 360832562 850964446 162761034 452614025 698159849 889613461 835026140 409194637 922295326 600166537 303918790 540722859 923794460 766786902 670694105 820976368 761472678 86014112 213359894 273340251 575068802 217431967 986641608 169281938 522470105 66064922 66477240 563000245 357554502 756138107 230909912 133157560 131818215 34705039 633389564 149181323 368030554 662443685 483202785 153049652 65147243 459752206 196104355 91777628 449051329 268931709 778635709 165895624 326477814 474408918 630029284 554703073 866339212 885926334 91518567 889920837 335997771 448525537 820203401 630968854 109409829 518096077 977827605 28934239 888073849 690102932 17155762 985398811 660360001 348761131 288252245 100830533 74386021 198683751 551777686 67433260 977855048 235126422 540593319 758422324 491575356 628201099 638778000 188233428 439109851 538368309 630325129 439511383 195613912 82811237 180965784 976605326 958593175 202382462 764351977 342318808 935005228 425990662 894910245 748034356 24134202 6147578 8317864 60876466 146917376 295598677 111847543 835674236 323479224 595280945 624461727 432910165 831778477 498070354 101620640 732481357 465622699 949851474 353702927 323369415 187449120 600946085 754564805 961855360 842998288 121077390 42026504 458028436 468367191 348252176 681089987 244572764 910788360 560975786 578219378 722962707 275654758 110871042 91551941 632067297 276053590 959648346 104547250 801424499 147025632 838019655 695929042 792021085 112608847 31633242 26922918 14961060 496937151 849023172 512101262 429054597 691823591 442859651 372104092 940316514 628672190 658159311 967464393 935002816 979144972 529542297 229921839 964458615 508535436 580636016 740043766 372570638 443759486 594639569 199889855 638872888 844999554 882548014 323545026 181828049 116289240 55516394 720235944 654569016 805622246 278647469 683955199 194384743 337245925 442633392 546820751 15367417 959242217 837159555 639037252 399887154 760721989 706006849 457482541 80559758 733629164 251203514 971016119 596902697 440878765 309949531 945195764 202916026 536263857 418737746 801342140 533126354 262480538 243719641 598146050 865601074 169308130 583991662 205604861 696177184 238010690 758747039 214435621 537877925 753866223 651903800 934462944 333138994 275634107 611320162 852985010 310784882 663228102 503994961 716202930 445545630 672354347 528401178 710745240 43524128 399291468 915979702 530620577 937898863 385529064 598684447 685213348 25798442 395251129 452779646 570166466 328903022 880671909 887813944 776116251 817272454 710796477 729974885 346258141 287545481 502922566 464843192 498774223 391859652 850445970 586909413 612036149 919824601 859803509 994977512 874979511 151952809 113129411 712108350 709917505 375946821 556642353 79039780 891954047 54739299 159106500 71395462 188915652 553770476 433828414 685917693 798712471 840873825 774616022 451592089 399866497 701237162 296226728 880157199 430367166 695849374 419597560 724735209 118907514 382896775 61876410 938721677 489603710 114418799 193068749 424731253 170218369 494278267 973841539 90317711 287296673 727269807 138223368 789073205 80555664 195516686 113489355 699741149 968951629 532281144 544752663 941982632 923479348 100587735 318920538 712794362 811309030 246959527 949957790 660715950 484374728 155787337 839779930 852207446 99435644 338299646 111924168 743109794 549180376 409002834 547011588 758777216 854043584 77257499 651084441 319634364 585665044 134398948 417219323 389447557 87358835 746680688 520546649 483498360 420820170 41140875 520910537 208643114 983939693 950116260 905318846 139481454 835066417 854285182 93490725 313393432 985873172 688532128 391143452 670499616 697617590 274786132 886292676 293436933 338643467 448298575 612366307 95546640 39783461 450553895 258337154 966257425 362895565 597513526 54627447 331584483 986943050 283788462 873969254 467948032 582985096 969451816 562122505 260243371 134798597 42032453 500962217 555526138 142347840 829427074 895715574 13310305 759154546 469170461 354540006 428019979 653778387 578613964 33358113 323179312 82504375 553678599 686623062 809515447 851694042 917117471 688274707 376447165 279754682 966049474 691267571 890041659 566508914 114685545 115503263 155535125 359589382 232079471 127440124 697220644 901555 491500481 822815746 996349554 951812403 845247953 17461291 546813225 95562609 472759565 950077807 195625561 962490503 620823635 934597304 147392820 542878234 748312344 167881762 853049311 743141827 168025608 98834758 187594580 839648937 460249561 189933800 839475019 816352453 524783541 795391056 342340847 390736557 993729182 16875486 825663835 888152782 797130278 214821070 80807973 694121279 733171532 35564685 672598611 52352416 411077587 624950698 989540104 618302586 331741297 652750541 295366821 520046244 630845876 219083170 806517852 856036531 960759080 734180758 713720979 400162946 710489567 276256938 304223647 722427334 977644883 730177933 255341290 312440868 514689549 32563867 908332225 49959599 899234817 423934143 389615883 575613112 821018223 374425711 55752524 275181321 244631253 734630903 512250398 26610018 340609480 238809904 415368733 50666352 983419878 848667479 102374655 117524204 664375707 745669265 533828308 272513645 197485330 932489165 772082968 375600103 170870118 889170723 912945223 142817835 758870380 395474249 34069131 635802571 727820569 544000980 307527751 467222039 718668116 737720729 124223514 913168982 256373717 91632925 24492219 867430770 828164767 63693959 417728963 235083742 786168202 162246157 418743077 129879423 419635675 343677645 741803653 16568431 70092705 447715436 489288760 779294438 606747892 781088647 695389671 838017353 923086492 715022934 785505839 589252606 676392774 579073125 42730484 520467097 422086321 81555639 291187488 459191197 823402018 251564511 293526292 789775464 785122455 873047586 595231383 307353872 287542547 847977395 736114778 339295521 625611688 969008301 398352506 676506197 252688938 36909193 543304365 107303084 634032291 795763545 469602550 131379078 990773029 29637087 493415265 488229202 744647694 116760945 736110528 825097790 304948127 471177836 373500479 650603598 578873704 313138951 337033813 508353964 627913230 835471757 124443103 658385771 120944692 618977466 98274307 302503268 706391647 297775149 10918128 702442740 258893831 244301464 603435401 503638877 156937545 37120126 923676801 660089378 804652647 451009211 827526297 988889912 478448503 952660126 507970266 378502558 852650797 539765464 746234284 560682042 799273753 218844251 127184769 802780874 374115921 806621310 993245728 330741421 541160831 181326956 166757518 384474175 333743831 382446883 968513339 542829357 485093362 681229880 517370677 783096599 329010608 17107775 690870115 861527125 282543440 492843898 542915834 712988375 579138850 307438113 479189712 392150485 142681523 238339341 704266972 440028956 830709269 345205047 140719808 912023924 761366283 725691904 609786082 301496695 634393561 388211792 835267676 656764267 956062018 344009677 323065612 229379968 171131876 136241635 673440254 549624166 34686151 810116965 579343904 600806662 722200273 497556373 322283091 954324412 750342784 949306872 770784653 53938755 601829167 58669028 455659828 460282316 395179555 468812186 482226231 774319633 678700481 217323447 958077462 597519394 610653537 398360752 423050607 614018513 651328008 501946055 137911569 678390435 684081899 268230106 829416413 484434505 713994209 428227790 557491540 970158947 138410195 213889772 732803322 158929621 380103727 990509497 562240367 926879558 611815248 105182278 711283895 374423048 778230593 456282157 993214718 15244589 406735640 674713344 321472590 212018007 359638443 606675923 83293721 814917125 164500694 378175726 214400539 265531747 849992587 398924974 519050136 753717427 281776925 988697175 47245228 223956491 850265662 377361271 784688546 645295739 354428677 611643631 70247887 430467768 27066448 234516252 740891314 886887709 363976386 557386851 858108944 677001366 373942809 4495509 787445546 194583857 579733720 148396569 817797103 691557398 563799674 925444608 983659454 937851408 531674603 877239786 357987898 266901442 175865985 813365397 341352444 55561716 691934169 283022685 558316540 721787007 908574600 8373907 910196026 853607028 735636550 832005547 560078745 311538953 730178253 480094546 381424195 485248591 885208329 82850840 981597974 697774318 608386746 843082667 570483009 403880157 672205490 954830314 45744298 380964299 632968235 418971700 662330329 89984173 234798264 578362527 993100234 926145880 191072808 46605466 8812296 888395369 717479325 780358324 71686562 439400453 585717362 426729074 696976803 352029805 437927133 304461766 981757624 581127665 447731318 785420002 822361657 979322493 699197997 586509526 490538305 578354557 830285263 638686531 19723281 148436595 236428726 632996147 252671564 364248386 29811720 852939635 687975583 75172767 949480269 793667352 200401610 658220792 211019843 788093827 294466356 321490680 723229098 977449667 576230867 763177398 486226508 752720071 695035050 995381723 484864164 249480044 612653459 623927244 619487508 532418053 787834423 405419039 637775638 206805502 320501333 722636080 475667606 153437274 697064708 561259756 466523446 874766957 472744458 574665871 316430796 87405936 937814621 72672151 257054658 112965991 855296371 59699931 160159028 585784128 30245110 195982157 285004365 428070296 876638443 727365680 802232248 286575820 389051101 285461161 643200566 945348155 835745166 608354040 229700784 29919272 688954713 122698588 270048424 942155656 788593779 277526076 197118655 36799599 67032872 450415202 65607664 734192886 830139828 768448702 276714401 952291545 278756058 304998471 282277424 471532186 467085788 808868995 4004926 618993115 162149282 824300317 861614951 346869940 578475522 944039490 602614919 957558169 143743258 437361935 224136486 708270968 492624339 877527977 740423739 488961973 108797824 567841285 158461737 807062276 753097868 70674507 339397118 989818308 356574284 290661002 138566611 611433265 579281978 438505640 58617503 695492024 984915056 81484578 542733715 923303031 737701088 945132971 107997896 986371126 307390169 509088798 609154412 467516921 380017391 861851814 735269087 337483386 408863886 134776611 754033612 618873940 194383234 645141973 480783722 978465275 815770320 662435002 120798826 668944326 425297250 672991758 885861396 949147000 320395538 512121503 376589599 603518113 632070410 560730203 517948961 440116723 398056502 903551234 599761486 74527072 968256682 826351678 965717887 624838713 993619901 679804205 475870338 336012986 744476528 591583209 563675655 715289964 594584584 158719854 975545574 646652988 633507299 404713955 5595212 654104368 851429695 654514415 787547454 506519094 3765916 372514702 835672650 197806247 907094030 781463313 577921435 842315553 35127135 382083318 29561064 831708007 543377222 891487951 62140332 945460516 295105464 756538953 564488347 85378800 729743847 470666509 936752130 183388697 49632603 84479998 780020580 903072203 790823263 40514564 73674758 45771497 117313947 564233069 571016702 590645592 40267950 434912858 741999274 339013477 941170418 364583691 336605143 300357895 317716019 685737496 542697890 992395077 352417014 669572448 574721982 882091949 52739618 572297140 27437396 320661629 6206373 439489595 302114045 36936993 214858190 86840313 38789082 837000287 613258383 80600022 204582032 386753787 331155384 447887585 886339545 934717190 106538145 593524238 720866178 225476463 444394909 456752096 78335836 497135774 932744379 19400785 558442402 315042957 703572560 111710878 138695263 413936894 627220914 474727559 344432653 676942633 523492791 446426547 109559332 220823479 894347603 89594318 477331760 188378036 137862236 911911575 96722648 435960883 476770881 319072773 634628228 677569902 24462355 219397211 101824500 345830929 294440391 427886165 361271624 628272241 732910410 728906873 487971138 242851394 970504779 961300953 709722541 899298612 973629489 996936686 435027495 458362349 691095649 863791200 224910994 562616935 274546277 115778542 778184228 904952872 655170621 997834030 214813297 344616255 12215340 15202360 699597338 207206185 17659059 32235883 20503905 448226870 662678062 830560442 353302278 903995539 81324133 310209359 297590825 18951622 180602124 799962572 251479869 379516070 374603974 796308459 438789000 311391358 447451317 120060867 3142558 286030956 880150520 207513590 772517515 246339404 475024142 776287504 542311919 353763390 510160910 731264868 591533585 945167608 279184483 172187303 690065868 718708779 772887839 247221798 591856480 878693000 32167193 252573152 488276596 963373085 257587074 448042475 730350844 122704749 522837126 558031391 150620161 660322864 51127686 856915013 831593521 50539749 851856419 6172293 961966385 610393728 113292311 968543509 294684295 30356367 432798019 882149818 512686479 277723509 13266904 151902003 288222326 438198474 92208342 751599209 699624101 432731914 377251586 644323391 725885554 737933643 329569206 731838167 467488715 408128405 539624049 730994355 184815719 890110485 551921190 679762117 20724089 856263099 921932203 413285467 261823374 303421266 888876006 293992126 472125670 935617596 362712831 545794988 974267712 967135112 278370357 226008112 966822889 945685356 144928784 849364853 925619118 602414393 764184144 908054242 479646690 50958918 613574093 631368697 339098697 240717437 588371033 104332209 987829308 135391222 912532686 662512444 774259493 547573918 823954344 714639131 844155833 558903027 509267663 801949706 944910485 996354161 611071391 849831887 485150405 770428273 977297506 275037822 176351290 204954507 321843502 856756179 760480783 944034891 96748790 257661169 835709363 837401419 348399915 183513758 576419308 953701596 598676384 904792209 28337756 899760386 660747896 560721548 134442835 750986506 462386858 641558620 823343307 494104987 200982631 235816529 620708126 14511399 954391648 855421011 344044538 291970901 13626324 934390253 491636666 244580497 833181973 940567471 144828812 431749051 6020754 265337251 751032495 629131260 921177685 710903691 423353916 989200416 786786014 6940868 49994766 626272659 762946869 433423974 989742739 195667322 167954692 765540909 52140893 481307303 10981166 781650593 241941945 733247711 909151198 61862749 827583039 910329693 28937523 907873309 824413170 504717118 517774086 394749082 757894151 751612312 48531806 610612335 145617611 222994829 136370672 477511079 754842118 879334993 566172317 308134245 423845947 760035277 619466628 637529260 262431882 926683705 123655692 13259440 740400259 453507715 639538291 683876655 326322304 904360599 902881645 352358449 317115532 743023279 162457497 69635573 26022955 83326364 772515316 903872011 758028077 694726612 181096937 584590349 851691553 35771564 784498433 502173950 644860727 182326384 39593785 147336940 46809804 10074493 471635438 579175734 524790594 816450338 595635757 609257828 883433588 399238010 146038023 755344182 328947655 438364633 55230214 431089858 176231337 516194935 115016342 756501632 55376315 935484205 74719563 780558502 643974719 599143202 740454588 592434459 602348254 592781209 538367738 2931280 340090841 114692777 432818810 242984951 519265986 896601083 565947659 193636895 18864829 621639039 36064253 894642814 39186470 950683447 72813588 19357821 968502488 690824611 900649402 661136414 301216733 799488109 750330882 608033168 422614484 664098625 249243531 752461395 575300693 97117524 199176268 169821328 277813732 722128670 531105061 159942929 236483465 298273949 878277268 587556154 117044772 296790560 989000609 907168206 285889277 913941698 512087924 397330905 625988751 947221558 507798832 997400791 457913130 200690057 313778743 224977339 23197265 478519960 566076798 63006829 826087534 543235343 605821307 464265302 241240146 703031010 8969112 221681874 898320790 941118900 104875910 733845761 691845362 333977400 934402248 568798605 805434898 630273312 304351582 241675868 250476293 298353218 648443958 201520182 342684327 787025559 90916086 845726836 641724725 840616072 521047748 538329804 657161448 475944318 675596383 32918136 321753805 442976603 701202680 788248915 120640943 635870964 261786261 324319566 970461845 729118491 632004357 116069957 809989061 321494675 274300422 816135776 331844236 437145796 245223497 164731872 255410958 518134177 527522494 409672503 260841889 613934039 27907114 232174034 250420228 768600524 813178149 682644767 823698605 367627235 431507759 589422929 173404663 359951456 631717943 882916161 590118739 597353989 770378499 184851335 126976936 195622228 158095461 722408042 681492901 101603932 455114877 94165099 404808137 906425490 636842889 230946633 28688821 576569670 947545931 221298868 397911368 641642611 362447754 298610088 638382162 802502618 6664981 163798672 457946786 225348654 577876055 730095903 595290359 18026854 626797316 460730197 867741215 962826505 363818433 825024488 710867934 447606009 952673253 410093404 982974919 388168054 941901240 158940610 584577381 362594346 349085854 253176910 403690639 898158950 231389842 867845335 477036488 625752707 227410889 629744237 248470000 976416694 461475397 215408681 422761700 504367496 378194975 642069736 644403414 497558989 797266557 273956181 596771635 281229968 328325161 229533008 73354042 58312813 345317252 726769077 300369805 585804141 600504584 655299944 552184346 50322707 817301175 900870031 700013924 566445704 66590746 279451064 105365432 435333631 351552 959615800 83790814 133374550 997776585 686453054 616736807 103851947 527814608 41961569 175234807 975480716 367481514 69886958 233658661 862961870 190182722 246709124 312263218 347704446 354650430 667995801 284574195 70105000 50585815 394991915 720137064 734940338 829205501 480892922 923456292 700216856 244025020 677934852 851973202 78875767 904571562 191180376 229249923 552405773 101723889 134507648 333501981 912682664 446849337 214482019 400807447 790363042 480091851 287912573 321283827 840811364 196511822 19735209 15604885 214884885 691360190 452904084 576671327 902657024 551369965 883007413 439804803 132611681 647321787 844523689 431084640 388918363 985814788 794091114 253222592 199565184 316069978 866666198 603322997 25099633 458047727 485937204 199343677 525065635 289497620 905574886 161192947 849572166 865134889 673691073 957906977 947790050 817774828 622340198 640755194 323480517 584277368 639619384 528550250 361243017 717735841 470791329 478270878 52986889 274399509 433521659 614027265 766299796 260133189 475832956 41560326 242226591 961442789 145550701 41786955 632975738 851596712 333923127 119735227 856303193 414308711 14945099 198871278 611909787 988390822 975333174 777441183 734410386 707080020 839358283 769242407 378406518 418363846 999229378 548020997 631035026 886895256 675135367 904934314 136864874 539773565 50390344 819450807 574693002 793229731 682848339 508420108 601855254 134802747 500287550 429911996 564137761 532051341 930815366 268873695 444723142 390346426 721937715 753200547 342864067 863161052 958848744 650260552 129471100 660149270 271288473 323583581 472600644 654157646 645246362 121121285 965065675 439865027 856660867 955839131 706539456 6481312 204837318 663902327 646294529 469009863 61116730 179202972 91321297 68115714 317217489 688922985 706407098 371614066 446675498 781689958 595262146 885661475 302082834 821867708 724496645 742890594 830196596 791602445 409997796 258646377 94838085 781433576 226601579 725928925 754909032 707669801 923431148 100659821 337009797 516237505 244614757 59423409 627565228 578383454 811058046 230607832 829151735 211994749 304062632 758715522 364655876 233612086 514316639 883997879 228939738 915123080 248999374 968895579 171447350 266997536 208557335 863567650 462033933 891807583 236495744 566019199 971473955 65360310 687509944 600690350 570485967 342589573 476931002 466001174 842054893 276557394 776104241 343781454 262932244 604235039 875390359 964783197 468090 453668025 227541081 85804058 503119466 787812481 918944184 989399084 474120417 525376633 886631720 781519677 882950197 174286512 322758568 429925899 155162182 886382404 347796416 286668774 403794292 969717899 624402084 947553053 419287188 876726063 47209603 453517518 263766159 411726405 574688827 333758640 92442761 686340061 434865863 635407606 559979732 20651409 14923311 988214717 96553700 200338218 792191912 931985258 553290772 183914658 451266135 358051910 169926291 960099150 851359692 632215180 727537536 583598310 948631366 141878865 663319280 96877537 917087930 347487290 184664886 567681805 570616833 954655437 679234575 82458195 667623833 972494712 472170704 913808805 290293561 575267556 18300418 916705920 265309016 293336643 511845596 513885835 278180088 966166689 460336399 505745932 854508812 770343603 884060946 459045014 428289566 454420292 779609212 154369389 113404210 656092864 409409179 479889943 241978845 98481362 20982605 748785177 655094639 947094214 786677564 680960681 539595579 768157410 950016595 377322591 527745936 61660255 775787106 71702260 40561768 329563346 488447255 390954633 715995519 901261571 884060094 222835497 254172397 727160360 573638581 303509117 11048640 840594862 347921545 689444736 472877481 178318951 793951945 694585138 794356263 69188430 379916104 270914049 192021119 981466860 1189146 103274266 168781646 905246035 613698547 852237867 157149116 855508552 824183128 190458370 777955862 112003279 80238724 210262271 755627250 173491507 468239659 426435713 480255445 614442418 537231289 713537369 463704432 13792344 210342551 793220006 499912702 289896770 227807473 370925955 73047524 729953399 801742418 899158064 654838486 152991980 913284617 501614893 766015155 962450654 303193977 273995960 788986075 363359722 223066654 382836347 164211528 507717241 151731475 495943072 446357516 984646394 910727648 928587722 845825561 525816495 355731720 860789999 318235289 711138630 996632665 394657196 615946677 485399005 87115965 434923735 746419533 974957113 97618306 816445216 827976217 754761341 868246758 112094510 748564487 952179781 190831550 907007934 547326621 515799085 734926014 869762222 479850515 10113788 509724289 429911644 582782983 880066215 410212611 141061584 605270236 406873358 501057505 135494426 956461455 504497548 145093799 119755604 495996951 524715532 968814469 100183623 289830169 955342810 257898232 292578210 922425169 762662465 800329256 782943128 356411691 253493699 545954017 971087097 442401781 996876089 961465096 126647794 990968677 361385679 915984899 598953301 123227698 345080869 748907415 515755892 479456406 865507215 241658782 52583453 793048854 835563678 989622494 552727676 51532502 699773050 350998982 956242871 915288493 906852156 999048253 845988267 379092202 401083441 418328564 122564559 956865242 600870829 954342210 642810432 254250040 286371265 662790727 981752390 684904454 425182346 514176668 144638814 466970145 699235756 665460587 272507084 969804783 907163945 542586834 260301817 154700898 420281787 210538466 583518244 780257889 359699066 267526777 325695598 892723889 551531809 474727161 289528109 564414388 237042610 387015129 905820476 985623406 645594163 810351824 615009200 905300074 642205256 32722167 830433868 730266948 213549465 290975746 9849655 594817786 100890048 435450173 950141529 777089509 732607408 600478384 985212541 306435116 50725753 219709933 716809200 271531718 772982411 191542766 293653658 496507971 805955912 983240899 207430748 883330299 861673886 130052800 758555463 121839983 888065472 912383602 126361121 807128394 869970479 448460346 859238178 578720748 228221271 666237275 827940369 100650622 501299452 116121759 575832901 13543905 348568583 348063736 715279457 369103351 106946208 630032398 406850570 340087563 125857375 915938815 337294388 388177319 31318752 309237055 738380249 328181995 31284031 981394550 437741189 145538983 133842449 986286815 173587712 878222303 702307794 845105362 534062559 551929343 565578201 504948027 990273777 134939363 630368676 541705648 540936587 795719468 123818110 495960778 964692925 78367589 633733977 135940928 832892235 614533836 402535827 684867385 715759792 359936299 131199376 31271162 210097561 284704377 254902800 309868042 223878494 918955778 987566626 820174131 703466184 66664137 802044827 533781278 661206209 841692832 277579277 810735382 516102577 285350476 617807809 805481699 900440769 799643040 354940607 842426186 129135255 903856024 715799528 194395413 858412234 410215611 822292139 206530726 532863194 590604540 270962871 80175425 768358338 164958219 508262854 974670941 73852953 294843698 905575399 960503089 849060901 86751059 364007418 375646624 101684953 543818370 147883598 355291131 44545418 216515356 586443339 537700514 211896641 157391435 208776145 618814566 290288268 611765760 807970190 314738051 331805382 818681187 299341382 89517632 58703325 961637208 242285329 288314042 59526287 980773393 769442710 382970907 756491525 996539899 379261816 494259869 319336781 123527062 30179233 159556925 880784466 11278378 686463832 785019807 689520468 169275662 469199483 323923101 435942613 6590501 192328033 722207611 320007268 960722227 393227415 233069192 200656371 787657012 468786557 4231747 605978759 136342837 50878185 275364981 638628066 610365467 626977893 318777290 729687208 678243459 900766426 301320718 981067891 230452544 570945543 218251663 174740250 561156753 310422080 736566728 117384500 253173497 829090253 64185218 19938293 876047211 177706035 441063793 732192686 671360740 72069666 7726750 124147683 383484623 435984805 724698112 486586252 688111452 15287505 22537826 581587358 922895349 469016038 222736692 47272449 30573556 381615182 115208269 311680388 118268448 168379092 567160434 412273993 656716450 651507641 934199623 42935004 304150039 290391742 386353093 79115903 610621314 933483650 786484477 420467619 857958744 342993817 328963581 494630569 934955953 374341242 527555989 621887274 880341918 961568468 8582408 384456908 178968286 562755215 540388439 761790045 938728015 224959182 398612940 459256957 140754443 540317585 709831199 922873345 307702242 365682712 389808890 627048681 941823578 908280942 515710991 337547549 41317507 216277138 760282501 238925354 836760541 751205789 802178515 192699871 468761093 141663662 378284035 598540699 448491350 529931969 782341465 307502338 355947829 921301249 961064510 114420459 337354045 915133422 159405220 511569636 625449702 454091057 156153298 7901715 495231184 389104386 621726086 231343905 732641149 744538403 900063235 845334744 185021297 263836235 536630872 511661290 505927511 406395413 342701587 3062696 643520144 268373273 916354928 924942340 52244544 24355130 79160716 576653194 642274884 758465504 140462340 96355884 388610404 232342727 534548863 72560933 157706096 233295494 913711493 829820347 361500271 264028164 445101606 684188134 923242571 448843611 576493246 97523362 644613632 44661829 348460406 901528349 547153027 570718032 965096694 648357122 65755667 72538583 83013398 852949774 921704887 884697556 249076487 124180837 950666486 539346687 387718165 516803289 542419984 800255336 649839867 167128393 774580082 716119994 621687879 904730065 614338493 26959827 758457369 444767909 545044240 877842936 723610157 27535650 68099382 187345042 323665008 673108275 262817264 610718216 524365345 981317661 771513903 939683829 641768175 216340936 329085592 917739117 18259044 622217766 657274628 753980168 442091159 154646192 249788250 958183413 262134579 81385028 558179622 828574757 439655994 646665305 237219417 126795357 687250347 947847955 208520172 780557490 86552901 390589633 224715330 484470787 339253707 607560005 906261439 284511041 753714420 974385995 688057893 598885314 480788542 959674597 885408506 503784839 231562785 86925582 61776708 924830049 79021873 228525748 126641716 527663604 910577169 532620263 109636121 308695729 370360672 1028647 964888813 497485204 885648279 896074820 352888231 623004737 123024486 539115494 228457809 172385448 560374579 700027392 654359691 75939973 4426457 291390526 90347614 857603617 963302030 544966753 658483095 969635407 487723140 132283938 625607777 313328680 677298232 391832148 119144975 395765336 229829044 439242466 416544566 470643558 222765782 429231347 719721572 13637604 944700349 333643094 463929539 529157854 804556119 187910191 366827363 83256920 735185876 644579544 961274143 893549572 976908978 346621883 171204261 748187305 497889112 762395011 220379027 469721273 972662370 477236207 512962905 812139286 665661068 89582513 469673904 670476559 733966027 68920856 234623433 748073048 244847075 31726686 576316440 10136390 270043811 170061445 888837984 496449478 942111231 597416617 685764163 463969115 635496243 937701325 482037183 675300504 959624575 73638056 258526346 819652815 607919782 275412339 470775268 365967591 420484339 520213455 71997893 595641996 896252211 513976548 832678800 427409016 297327129 687219641 657436543 78973974 208634228 154393478 618209835 343529094 933232983 126852961 923939389 556353419 542347031 957035872 115665117 215244464 720271852 143406549 865349427 74334061 363426726 728480427 17181731 185382696 247987228 785573829 930964206 972498162 718369298 302690173 294989507 747471131 239534758 810860577 513040998 835561419 723336148 349865734 273756938 780959129 802110857 817923866 469481337 347145661 465889730 42413180 815413875 910123911 911216784 584589596 641311476 677934918 733424429 482084515 365670969 909798468 771772684 768860051 308635927 879975899 141269054 480527831 987574044 929796275 970712132 9124715 206378678 629928884 744920294 555921910 35999574 202538179 781499801 46748943 47908198 711994634 972184671 130264153 571649073 575194607 112917457 918776815 124678359 424030192 73266522 327891455 869568601 541213310 181840716 556622385 818265449 794262376 330966565 503370231 129171540 2501118 39687190 611460122 467408590 506338893 467423117 844572137 372722373 984344216 326324626 652650479 209339114 509501043 322469150 156816340 556738705 54858793 724241697 479960332 144316970 224510615 880045217 790126022 634683351 522208375 425141201 678216549 738494293 419987725 406613252 893885192 702766591 90234423 447027650 217897547 565025772 606518372 273895101 16733450 686045779 205682893 373718425 867503068 796870467 6194280 170472775 524020058 869401098 836706036 638060254 554603414 875523997 488044856 243249621 415328521 598530801 822934202 624153659 754395695 278913310 936444595 382561362 898286800 610421102 283034438 571362000 526831557 422260222 115677281 841045500 264916936 297558823 672597670 181283614 885277117 193288270 319774267 328662271 190568122 482461093 30964083 437369446 86677787 322645908 85955885 867903167 57486106 698074019 920834118 757953340 86255513 250950219 108079448 171137161 759370874 93177299 885513700 886926656 216382043 949769630 943867749 851961608 683769431 785761588 385043056 582029456 762713983 279768043 647608041 447124384 842132157 778260003 299298531 825035450 349802331 45098603 214472247 944073536 486134227 285214501 618758159 975676553 171616217 145250258 36662388 675313250 10691497 956599279 259643870 185424808 794252726 291301806 719769206 378358384 984256666 20293555 553116991 162648192 151641449 385925609 605217558 381321030 600222848 469277479 600700578 736904372 701155507 102817159 589876987 766112328 587263615 151471488 174134307 504208037 43040020 966153317 238105226 538864711 682344166 234195541 382861405 159094848 689598735 360372822 301503958 698297183 954922944 602736235 719342478 502497669 508486150 374716706 79814197 87824994 617408274 931032395 401473767 535047833 635125535 540513983 371349860 175071998 426436259 523105809 447215189 249094178 294745305 503567799 762524101 923821594 468013140 605887878 709282001 289646960 114579943 526640772 696077131 646180868 401709123 862304896 885142112 165006996 316625124 793330852 440319799 636801705 314661628 716598693 47266635 275792750 996875899 686349525 27151133 424079479 185994211 63119878 292076369 266469721 715332120 112001511 190889880 731751775 935948591 796252638 166218803 564729839 432069565 846854246 450000648 419584694 910503597 205289755 3569822 708725577 199648467 777805333 60340443 765548756 65923592 714499831 846020145 463756475 489038 149340648 796052259 747433726 247124548 690503454 535633544 52134663 100574651 7613923 910678781 539214538 949093255 930495489 368317992 758576649 860075534 891159345 3193713 724818682 977637798 900359564 660205515 642207635 768423777 555407805 23837908 552809711 752665252 826294707 148153155 652490764 502614953 985496709 410709452 984993659 59197758 707082139 287654836 709320692 461124974 469137095 98541892 281337049 264868681 90690196 457457146 282088433 355704043 561241095 232336605 666657635 283657846 524687032 293285955 720557937 369062707 554472101 964739421 64491458 88139140 740168076 713433336 942410940 45935978 259224339 410232478 810055908 463925458 832330335 450359255 380615245 95759519 887738132 987102766 655370251 970271362 23309589 941438951 539453857 600637778 327214542 708472169 45040419 202045262 664444439 131605845 779201997 581551606 374370225 5541990 937470362 778698540 132716493 585744032 447986640 494358481 923068673 567256868 77725428 946489303 789852787 722572649 389713339 618976455 254094556 379694266 729526812 510896444 400075524 837043907 283865197 484677017 379104382 459437902 624722099 921084971 973726645 229432531 677332202 290184744 10699335 19538077 16390089 79569816 906037769 607995847 199006300 939486218 879567270 471272278 734666682 940897727 521331090 489024274 752464994 266896208 35701654 181703266 951795526 714016307 454082754 109397398 383278113 452290544 504017693 852437610 107337201 174793079 947619063 453912075 725054465 358353022 171098956 381903727 273323221 470929408 567033826 261411174 285075173 50476561 917305469 753479005 776904614 223423483 64680309 335574468 272615351 800040530 303032250 903660274 260748489 993842378 576244369 244687709 681738488 964816388 611117262 39481205 107790686 225895794 210767260 918084568 237195248 871329413 944427664 630020990 590188601 397298680 673498237 323067719 188014440 87832822 838279741 415980199 263598941 173800611 651784240 690251730 621602754 685867460 694049517 54866522 41709851 149872298 410979137 474648675 350705323 152981746 751867013 940715378 984483769 293747178 494199615 862002011 736854045 116072999 119625826 870730097 80705614 671226289 37667538 425611664 416120357 535305921 686763504 884464886 815219938 278580055 437458387 366975842 791637874 8650216 971551252 871688015 993702346 242170262 744841156 650820075 898418941 726148133 399140957 513892914 52458506 749892521 490286061 574698418 672673254 975091937 2499207 8634689 20866665 196853491 364701370 599446673 591157082 91708741 658864920 98397119 227255303 535166532 993585098 848181946 50531387 468912524 932342883 417966637 918129515 618715654 952477529 364057769 725498596 34352325 219265422 590778497 996279073 269752026 8854987 842357279 536288294 276205511 848056995 675617528 115065366 570582155 201908268 793783865 394231786 609842779 198636233 97102303 677862606 756423077 256409365 911954181 652397739 697453316 995257911 261053604 36737755 159180219 876194792 650282146 454452679 682716232 80979570 436488598 610121514 21812009 660550067 849374961 451739349 568342326 802745916 895173157 162360532 476176954 202538904 924596409 27012886 335700829 43068327 347700594 143909279 458840871 793757226 615787547 93887197 179465875 481757301 824527704 9178147 270811711 950909090 758973183 745160850 701984302 707027211 332824601 1489144 338275708 625775630 978459930 923837221 608922728 821119657 146017501 231285973 6537627 617611560 981892819 613389636 41270190 921664690 306471152 880105156 69694703 600273110 516644240 458593030 193215983 270934885 217540519 155813408 52649920 866018346 746782826 599615448 537282576 112615367 255591293 622132785 150052790 138356810 888201198 112557422 395582610 428821364 250952668 168748639 402322078 224488263 972378010 435271615 337228968 497624492 4031538 197640194 994074977 671109362 356550311 571486265 702167932 347335608 885073632 36171201 83113503 36984054 327051354 146604652 258256219 646350834 255044345 824460373 31069129 131126966 860713534 803669751 269025326 530649272 33469880 153460504 282073759 665383088 735971852 235719517 456126296 205716684 515088185 533702875 887859224 492955069 712689969 989506556 76369977 975539341 747893477 65501773 643583617 783315450 718182359 311891015 321933257 600936487 451146525 548772463 467291543 417739554 41263104 775586077 452153172 10061825 395075863 161157298 425604163 520632046 351060362 528566097 975427565 676742067 345401581 121239496 159880493 283394328 778775188 806168114 388627298 219799344 552309940 889792827 693074871 319753857 921439549 121008040 449971556 745698988 900730505 944414168 203694131 145817210 609414361 904047516 899556575 91444730 76215643 63530230 956468500 166765135 451175201 880276963 540680927 20048567 212779749 767713002 296782132 866768392 175429339 712454851 720000518 175750621 210337265 841357933 742855900 469540509 431857615 160177863 566303116 873980474 897082378 555836579 349752836 897352992 995531994 470230767 376125957 799811963 997442791 657131423 541629864 455587962 482982189 365258644 55630267 86277669 264965430 705622106 894287147 665437181 595795279 799190751 648297352 497679515 549232565 932692455 513406145 798799310 669797654 115222666 965201493 360100369 483774254 429360197 314014142 987839095 379625953 453994249 126674244 763144713 271428648 538129780 661157245 871580263 276575364 687152730 416117839 811652969 555895714 926956964 16283355 855597399 662227196 679951045 186361394 130050820 699461162 711535675 371682794 720700663 754188284 834908721 306016052 518984589 345962439 431750990 591485856 668179649 211845094 940279475 867766282 476430890 666740803 397611161 574189311 338602942 105571138 359587785 457268368 481207040 174624003 226060370 670575426 771291978 345481066 591152714 45244643 645961747 338104154 629528590 992572018 70022791 229997599 198550647 478321007 246150836 750169303 967699705 545882032 877950234 993853139 86146156 803829617 286715539 437649477 374427254 953837412 953383456 255901088 866719392 574156728 412709463 137310381 266801137 306919711 613132310 284953449 74394977 358940049 262254190 333888846 688018356 21650836 711494138 61895351 99033598 57871174 258417673 242282975 535958040 384473127 645406536 275066641 967816213 352235092 231446741 148280202 302839459 437245105 170791312 74201068 629844879 880592536 695982167 638132023 917336117 72147787 442031976 694640981 604238641 496559069 711150378 564695139 289655893 154998284 498139811 509862018 444478546 541475671 573547480 848199843 677993986 818471677 597984068 66552600 273565078 475123961 816320396 314671721 573216441 548063233 182762745 660578315 533173946 395313867 980224856 596941411 157973006 566096919 265832794 366689382 202750649 933886611