978 431346530 733298186 995649099 999044250 410538259 659192391 635697104 792398977 387667345 413786538 602263357 641039982 104148837 278479132 594278143 760979064 857042404 921537444 244035522 493313751 175954477 682110162 842589489 956982561 437512522 481087449 556674493 616861760 352446181 955606522 225255988 927132053 51785158 897165784 501542315 778673326 179832995 298257231 414261751 441118774 862004105 998744614 655414050 840921069 457096254 824047980 843515885 902645227 994720959 998365545 373496795 549182121 10435538 95689379 483546419 713940760 428244071 743665323 798052722 953443095 641234356 776868498 665393659 674592423 822052253 904176115 134720120 796436652 835235567 872147468 108630539 503679618 803290322 921963426 972526789 996243102 578006063 906375021 496172774 704392880 272098430 815372544 431316287 952230758 722151235 842596631 417987110 946328057 17914115 768343523 750452283 803782466 701827946 721750982 514178011 852997573 60133331 342501951 44717240 757933893 31977601 980886564 724165634 992583817 925082628 965827248 138094229 255377639 745824232 796498288 890191393 935179109 942976713 997922733 46833294 392220641 197576758 306625548 34167438 689291953 59603511 246746762 955625703 991729981 804430223 980537209 304441172 658877592 402744308 834800661 443636134 446539845 37934811 79077797 46174653 758882040 212623503 253268506 285358779 311503873 637328406 807694550 124057791 604014994 468137142 598755683 330261355 908109305 442550382 998953362 423861888 998362636 437197768 780476707 213645107 689596112 967941860 999396621 881369512 929438513 111100772 452124189 310352836 919136173 160640112 911356385 183616434 763264536 26982739 238129637 457369094 993846036 525654243 587368850 636111848 811783011 128383324 355873140 515443718 854513323 629193801 735465216 913227839 947654004 813017454 818921413 248771881 283019481 770809279 915012047 992237317 995615682 592485897 976238344 554297335 640676830 671633984 972625915 102426277 812029039 111415690 778706529 629172441 905766885 488446705 866847178 317029799 338164016 995183988 995920468 44713951 50100940 259270299 652108732 949154135 996497395 69408576 295399314 395537102 591529280 481864780 612413569 152920523 831666695 67612116 236289100 908800516 985566976 139868872 664911628 958506558 973147887 800019329 892843935 981768909 993913643 941199402 964618731 86876252 486212500 40503731 680968285 359751149 751705097 359716476 916385793 916634371 977819692 435745923 804988413 52170558 659720491 929263848 985083910 49449002 484269433 82995029 817386124 702069788 870755893 993970156 996099271 626880653 663881666 209711816 878298373 440932594 781948041 833734043 983998224 879851233 889250399 915792339 922955096 626074921 712524632 249489558 731657211 760004397 932056498 496078443 552717442 422791526 628217734 199895653 898314337 186952695 960233890 685630148 997934858 287097007 506072600 227912693 910891560 941437006 956199211 45526761 616870159 833398414 860099632 894496309 990556953 124924901 798791805 514122957 676656206 106655640 912012605 447272150 722674927 937763369 970440530 254145976 572843806 419760539 500216989 767390744 808470262 150453114 672384265 462861263 897639567 810775629 847357693 158405832 548426465 382876358 817533227 31788513 736200039 136876930 276881730 387838366 438056201 135225588 161674158 151759526 284569847 342139107 602638851 194459586 229109001 554618353 990090059 873595782 996923595 874517798 991614729 581396817 815248564 296679456 987189702 35196081 951477745 128016502 798094803 389135585 878683523 535642213 977482576 227876929 689172277 512244784 628472590 350129699 899293884 801499218 994411918 415264861 751338115 45973008 60720781 678745872 756167956 288940235 828316268 773191831 939538124 891916710 945050695 770835661 838034643 576587451 609785394 171483388 572699752 971166243 996551176 477009331 949918586 421093408 528181472 912630317 941718239 695226713 993500721 818604913 989326943 292410535 356428202 440801280 880891566 885478624 907333101 37888597 558961709 930698128 986958449 697698164 788836863 947923544 970447942 792993080 923371539 226090417 902607498 935457954 963565445 329647143 544106793 860894786 918013277 44635135 86149925 159038125 909601615 186172303 835368747 715483412 842154465 177990032 230771673 280771692 943622751 283725447 364311875 136089478 848234196 736131854 737851983 177488302 341355636 838705477 899607686 856737461 944328599 466541206 758184595 756899458 929583075 317252053 904583225 56703862 299807764 251542922 600522289 206870549 524372162 314753273 366401021 458437138 502580124 85368011 132730726 103916164 158019965 913813116 957812611 428001783 826685833 160360444 436100554 711238812 925028647 537373908 910409234 875600816 886362202 831018043 853736672 987001204 995868128 139583826 825804117 815561463 913854937 519788904 658011335 511970972 824532278 894701743 897645052 60341725 712372634 375049485 966409759 178626573 639968506 893090615 944527507 844003121 989778991 104719621 793045564 72168408 167230743 333586836 565982943 589585803 617372372 957545615 998610509 302138990 344580229 779172187 839453548 507431570 694410181 138510804 886793217 894572675 947707800 217714648 588378044 207514615 383513343 937898096 982212425 748732584 902926809 791936999 841302952 669249699 862935156 766299984 803859103 923927601 976135726 515232880 996101038 156309009 409343675 488418183 513876358 673773053 831704640 420064921 733207386 313249178 907245182 467198339 536044234 223801995 792412457 557339691 911523368 431003348 719977361 368418743 480353154 606599083 780477898 788262451 963325977 452492009 844752032 675611406 768396178 249054983 548505007 833154703 931951197 224020110 584745380 169218222 974310260 377412927 506488191 683499946 956280699 380506919 393382289 600709826 660204099 666617327 835860493 241982954 291218563 760382882 773948908 749336440 939533206 965758893 997786484 585533635 991495602 481406115 615030685 382824372 675141866 221663830 346186873 428434214 536443069 896916462 990590330 330644793 922238972 762710928 855842043 17913767 114869870 729618837 868644173 83892403 665971578 849806719 890521972 225442820 438255796 757499824 831165053 51894175 407109856 228044337 788649988 200972118 471991564 302871114 350629878 123110690 209585416 58067405 347233808 374905034 524914459 156498005 278337419 977526152 979562341 773532606 977643067 281137612 360402562 685167192 985620229 89602722 201798365 343566622 962624226 701279556 745967983 913009965 915010551 465502626 839290884 700272769 895372978 630489269 652987616 64422079 498273072 883094657 906518644 492113276 683531883 82774363 514623299 786832590 902709220 448780830 851659420 542836764 999863630 292015560 909786046 382376244 883497173 272913076 580600769 519401567 973395002 398763417 821633440 141311102 229219482 496260566 621456982 267778611 292391372 792542357 970128573 53590806 336089177 877015533 908416738 686613612 790923491 629652454 803011774 864011848 888764580 558733987 956139642 733658849 949036922 956558897 994771200 870875944 944075404 958478217 997820229 749343932 931315056 494905956 570556693 197105691 236791242 710514015 791968250 545151382 860566843 956713243 987005362 998499046 998798784 489072067 515251548 364285164 462965061 12145044 443752898 998924506 999709170 315795927 658555684 101749283 930223220 415530858 465036387 543262846 736046813 342104069 964562196 237284192 501857358 437779361 852983840 78981214 752033890 733615072 807323144 154085948 716206412 900735764 901084226 280923462 856196348 937148423 944373208 366005660 477427151 203507518 728992547 965665420 991615193 845177648 847682625 89337750 258503790 997493144 997959103 129032355 198437404 297032246 390669222 680155749 768351789 869850815 943403347 753679524 901733699 590166774 876294544 971188761 988362027 599593921 803255634 236957935 852642542 354046952 420317452 973140540 994780913 775155654 781910737 705037375 830988611 12941451 810572710 14759154 668378206 918927941 968121218 979075166 981267220 497506324 600138801 160400609 859922102 439195075 449076849 206347373 834142116 446585887 844467775 609831757 828704456 932496183 961145474 416690040 601410708 404282595 703901048 531470596 916562966 249616898 579239726 905338761 943091406 123476114 786838504 531551396 857437690 745618785 886445788 222581550 351869169 687612596 802664210 305878334 710353632 211974424 537621021 916894062 983242951 823519529 940324782 652714853 751320774 529475322 637723734 324170833 538796681 424367563 573943769 945683473 953668514 558268135 585840249 721172261 945514789 413522443 419554168 477750036 991170967 716586071 944889169 507406590 515583228 967689621 991678930 151773413 241412788 436760522 853632377 408900555 637497285 896139424 896527552 267456900 821238386 454272826 948530911 211399950 220135189 972009834 988032210 735039830 965125256 931285932 971073828 359980861 628843764 270848448 596310399 666359955 816652831 543329021 827495255 526770002 755778451 776902300 926519839 320997928 644214727 918062372 994125284 700253404 881034813 499129347 873353770 270781542 959510361 171769186 950594987 790505528 872427005 38454402 759632452 407009736 531115784 872292376 900597710 509623682 586226214 17098656 137646211 215691811 695993555 123532640 775179615 511524095 693404676 629299780 960202900 159604268 295345098 85707783 916060501 851184822 869834589 56211637 808808639 449302253 708824727 817670846 872041542 67677246 213957956 301010906 560945056 591401168 867591010 263731857 474403895 254680706 384576969 352292904 887856476 353195375 747465337 485864460 614386248 874703524 914169054 819168096 938632481 599110410 633051049 495188665 945169177 847882509 947317646 607191150 768339567 86702570 294227442 456332741 633655646 166969031 503057558 858600154 880521363 56106676 264018801 46322150 920394302 540001193 709583009 835437701 916491682 848219047 943945286 458254427 463761049 668318535 729582771 768688504 893349263 227247930 523271037 273703266 876057144 707196646 882556022 493698991 519126528 524129558 749262095 531315950 905966108 878668142 900416059 319530699 762210788 254928384 599511170 704575894 726810294 254114109 312131632 438680719 882864824 217040551 701607945 595308809 918741060 745863269 788732764 458882821 987238221 35195738 698583834 610247218 640529206 104048400 212177196 471096006 493447751 920919934 943103123 420662733 733335057 368539560 497540707 695429932 962145956 266758069 623175249 83301544 832441481 386091109 811005626 373884225 945075260 519306741 852299624 168474936 320665170 340104786 642963879 399408306 618781166 719212584 783308893 212837046 821843669 348016829 984537086 818149354 937302468 153712566 736975830 695022274 789251921 862577162 904040981 332098335 958337139 311951570 464102383 645395307 730326611 268559613 945423314 913797952 925280198 55276808 320706863 213729207 283632187 857019031 909335134 794160627 890619813 733053957 912959401 420569501 741952878 26855806 859596056 429780767 459813435 602260001 767144260 604926476 708653797 810630143 813384846 478687062 626464327 957023400 993883487 344707773 686874449 769691011 899082019 380265586 512888253 528699595 637863410 84737645 529386622 470170396 499695984 856973779 995475779 575438940 703021887 844511451 861500088 538499240 649124411 394669775 761785920 709144661 752033312 120829531 649110303 693837582 945201078 368711497 947815976 569179269 587401488 362106271 872303892 223502227 989758100 409010308 620644773 241234595 259358143 401994075 507927841 757705999 945564524 700160460 752711720 792194409 802806023 224367604 279833543 244344218 531115772 478923599 997600206 926852972 979475556 399244933 515075749 689840134 940410950 420147470 606788368 537592707 727396550 669678604 915340833 864133952 947216962 250604026 519547497 773901168 818649353 559611934 781815468 876259185 912637598 88089313 304825675 844740562 961955581 699078599 961147559 640377578 661604144 636963788 695889605 298417166 512272415 504493620 808644924 662429925 864258331 293220138 823161361 73761057 954530061 61552253 878383960 777115690 836145337 537596153 819900932 298093733 993849230 334411194 751517116 827115229 893652458 639666939 776637790 280106730 648958053 432070575 539793226 179795571 594075116 382003780 835523154 91817066 142931792 213610480 643745508 787118760 848394305 171593398 622006999 372715502 991508490 167527448 583742049 107142788 900423003 853902982 951518444 896585298 919743669 956742453 961568814 100136614 657502051 323228391 354748762 45273716 720285137 134668839 368282814 907633426 914646390 245103021 603493611 171289855 651895673 467770744 521027925 576155771 989356023 327693475 766440660 141411581 951620532 989856981 998778473 596531148 685218689 850394512 929498467 906862620 973597222 986868600 998029622 236340307 919710304 741935111 817245523 270181017 909268666 808033549 930215683 616734358 902888516 527760262 777986262 829628721 965186554 271159391 902597828 142611212 218847861 366346951 942111613 608662316 745193055 675874934 795629646 411376851 435228624 445542618 819116930 983255878 998999678 321381714 546411485 915527087 964506912 932791903 937213685 535805623 619736519 595544004 892281672 658576982 702355652 156986336 740144062 124023045 762912945 296289079 954925813 663491886 941343991 222385173 229475385 618184959 635499611 35871442 909585212 484511285 664357895 40260135 827528170 349815849 396753157 313365220 628956624 827856418 995687192 63785723 110592296 834117699 857951298 990546059 999981173 63389664 92677189 900426240 943920379 933826446 968464206 288365351 442100834 363179945 463239077 965117614 994933664 158290007 919923205 816996048 958300451 39100052 252610331 976824020 979984029 24696780 914287324 893691183 974287455 934511972 949075518 32246507 713365243 346004969 443074264 313572761 328011462 787624837 889400122 886189177 959416707 379045143 705320011 118123922 158775837 368955957 647452511 600633127 964835026 130408817 804270126 473149624 722576686 524775797 564274931 479687794 667004948 264428345 662006161 356108319 847738127 649658838 996953695 772332100 935761337 405313023 629812821 772578823 827461757 351499007 559067701 175347703 265984417 974059418 986043323 940079351 998314886 371832974 459405046 837516233 923563715 989779391 998346893 788576473 818340469 677522440 813601170 241768511 969511035 588448552 756550934 879101004 927435893 875861365 988658828 734360264 746952552 308964326 362255054 558396613 701528510 468603067 645130377 187734618 905724132 552238391 644740234 342945730 596919571 927369184 986648364 153409000 315932945 483006082 906794828 709612588 916185691 123775053 777758776 614695877 673352208 304159523 409442716 682039410 689802957 310354288 558190384 142038615 506344391 361584081 763972949 309714488 476906919 829184714 916444730 518440176 610068065 699470106 834761484 584974739 648496985 946636715 960693272 884030264 952020879 337480152 572218621 612317889 739394944 105554940 169427850 335408248 653037511 460428677 886628090 738511356 927047626 648828292 959511418 846098392 938871073 124565993 779344265 530437519 890515488 795138790 800671585 262528538 680503846 799348775 970459084 32327146 731868870 937703158 960028758 97985579 919944185 165290174 364596431 480618354 659938182 936283954 961050670 792987926 896503163 986497100 999799665 442610326 821492862 893111356 946529688 572518319 987684131 83805089 689545253 899897335 909531129 18743870 291881381 79955361 603111167 792064313 975181418 78539444 969292181 264390984 631408034 631371170 648732235 118828292 878196572 871580969 964364324 700481306 907017198 904353620 952008344 296476323 561242156 949306441 963917568 791099318 844988662 298345237 499935165 608912011 860647385 962749468 967441494 73658197 933342203 539447455 904098300 154219913 533211282 816944297 987934926 636356027 760549494 730423648 765194778 344152947 895176175 725445138 847974098 287469368 886712822 700671834 711516810 641161657 779093902 595671859 648780431 353932466 380066182 986118106 999970686 888893859 941792090 771477188 953552587 642839612 804915110 196046200 242679304 850328608 979557508 568634945 972233168 397508714 833814785 251161727 652992543 448561595 589696424 546152691 678611097 913051340 927843839 844946338 868856273 196548319 501183664 940155740 963359024 922442130 946226100 248500651 300087438 326001589 625068663 918034332 951314807 297951346 555922513 311810568 397486215 363359635 856904789 863776624 938104260 251870200 441128253 171323634 255858882 466124438 502963273 943878785 988029735 462194186 792573412 960026640 983080631 808799044 941870585 819218595 963459723 507955401 927510894 670950488 887824529 825301237 933699845 936673311 937587381 290637523 318668205 198814471 833936615 730746285 945112451 531937210 958761251 268563161 352020103 704886895 972464210 199365491 262165263 891584152 914199459 175145301 714982739 319500689 829905143 594297219 690502228 32976308 81264227 594832348 649367296 914365355 943769566 147941525 575094522 336073050 784510317 673584202 800932635 194207989 979596316 414021651 528223898 342419914 836840352 648964491 655109696 224920468 449695436 592685243 717012412 794298799 991464352 338812794 755867471 615333152 951839227 408393347 877441598 276882040 759486211 154919976 973427695 110366185 555557881 330167905 398788084 853883127 904064137 650893659 666606617 894553120 958149611 864890772 870922417 346067074 748840020 789898348 968907073 299676968 926554385 970646650 978582931 948707754 956903972 391144636 903917132 969899093 977004800 85477905 616624493 167742278 786761905 451918319 581064476 882257712 935194390 83875189 326349401 622670107 794212437 141950043 882583235 774560347 852324034 124781266 726006142 693820726 711060832 472159840 627407237 124107579 309557820 118843226 358879777 418087372 560595183 372079026 518621929 526627682 919655304 977645808 978793866 54101390 113290690 556061833 840501072 982132241 982538276 754913858 853702931 291488145 859445167 159198234 778313545 152518974 226257214 794062374 855488984 457841236 772515665 590342304 933643475 214713361 675065537 98033091 539962258 530449100 628494259 546129468 691413106 229626084 925314419 628746314 893002500 729862944 875987170 703235122 887889306 115420464 161649273 116561449 280058220 731776782 995262103 173491659 889081457 161541739 252079859 483093812 915914688 453938832 710873203 407628371 504200786 193516684 842737732 643320723 741559426 264841552 798875931 182161162 398299818 46248033 886534081 761014232 970697677 808676749 830819742 980663293 998903352 214762597 964467642 805040616 976455527 831840005 890338689 747740099 778201196 502069472 759563241 349594200 491210457 147962882 441974924 880462200 898072244 705266480 722656750 224335436 556025046 666218258 875860188 212286677 627992471 133739767 202755312 388396821 642509461 140543660 391611381 958145599 967588914 479010181 550711925 508998212 746928279 180877259 677586761 151445557 444639270 535157234 923574155 954168430 961354160 501724191 614791396 812896198 838610370 751218541 914975388 967341504 978933390 860936807 865153972 618742224 846703687 305708778 716560870 891555742 969547762 559961812 895061717 890969895 945015525 232363459 989156888 123306535 606422613 969019804 972585086 506660788 956718666 439367046 564652787 134337815 935037299 411589699 820977219 98616802 462506450 572001941 613505112 647259070 757970261 549512558 576668824 270402005 417598794 107066450 192874056 139467490 359408403 698020936 745243896 486826300 529084670 583947154 945470551 668416861 995833186 491758808 723937195 267834392 551358222 683961744 872729080 865260264 989188937 345577791 700775017 904868884 988417447 494812069 896901918 813888732 929857034 200418807 264250877 381999664 392416366 225410344 447039709 886046887 979702002 323491698 888560133 344869027 573793787 473983762 815905436 206900400 910164144 317635850 577745960 585271877 830048792 735443537 890942942 410285647 867425425 725416468 979809837 50558044 733162132 808056798 952889516 883364670 970587262 446126188 583171506 793773208 805244979 705135282 762665891 410150776 905162324 874554608 963753922 741670921 896761456 35419535 261787327 196574951 361874806 93393496 387138030 522356379 777869294 697340020 899304674 784915415 897585317 718986747 884823482 486217382 774571674 903421809 937385439 938873780 991922942 482590177 561692091 750789000 823999033 532640196 651634936 407479594 731770071 683561089 991998848 426700321 630775636 260704853 635293036 546328777 589218395 116044379 501015101 552431905 904085935 10520868 212944351 340601451 510840245 554909262 716354472 332961390 434680349 361627780 620637242 653487104 794994415 465288717 976870102 488442663 868068830 20649196 729146513 419669279 908572025 833794625 871282549 926456905 978423135 565714953 922015165 160784417 476324620 509630292 831631566 84093320 756449971 364993839 534071936 328747359 975376853 344783486 494689460 163316414 336270529 474960251 820801963 577687463 755121223 122787831 917614509 944621528 989280631 706084190 737385155 520343213 991111127 519425641 599712713 59663640 315875433 143151490 380297392 155754799 934393480 299410931 564833593 979103621 984356440 713153699 832832732 925501545 992672339 498168855 909967357 481033992 544940807 474075050 766450875 161463198 233263183 21240601 705340917 433027296 823605054 211167387 617432466 719730858 908418617 775360372 970555683 731568990 775104503 164157966 423771180 172447927 241001259 111272901 155369968 874246604 898483962 102790237 217954486 963321042 975640021 268178917 769968586 956970402 979232779 890157827 961761673 514106444 785958958 798876531 887176374 319457532 468594681 360220289 549353441 784615446 893777349 545627263 653619526 942808457 987394428 537904380 888542066 688016800 755496107 839255342 905279573 325807158 385277432 442050051 567489357 516903656 858627103 935308065 985295567 814587254 923898407 244708337 417924964 420970025 964506411 450585854 486672705 944039728 952450886 229795566 291613797 974724441 984359678 288350646 840919883 314627235 477045672 102786613 362977059 90931739 824159048 485809745 836440011 249062398 263800280 106837010 625913080 305934817 318606540 555257209 721374549 44324018 100720901 53080718 907219532 953028559 980333383 978001083 980412333 580362903 808346189 284329947 654329443 239328281 591361018 215142539 748477239 396828809 494510966 125960009 725037056 979104076 989370552 40140418 663028363 926627475 993190099 651185424 888552952 217280303 236312804 159678572 394178865 824971945 898688729 444275774 613040702 728596549 764171615 449038844 949201335 861732277 975826089 863063866 959382167 40532603 395225979 627018184 717295540 861339075 964547894 38370247 820000693 784769474 864542777 835712244 944035365 540747402 930674298 378935926 783250979 508211190 677197042 65611521 756427733 251374817 672450640 538149666 787715459 711680848 750078888 84973058 924691415 243409749 786696379 269477970 681681049 267505250 609170581 350810718 482441143 547069030 833708229 616783328 767467841 130371957 646025337 804562446 847316482 751890104 803787385 802393697 825908581 580700114 606339108 649931378 797750173 702224922 934643594 560968093 704836543 717036981 915291069 487335426 672051814 357863839 489669175 629669876 980989834 865379991 907026942 750600256 789540324 594814951 839288783 351218949 616520043 486281399 890348412 870769981 930486918 792934779 999336657 29966763 675919148 659399982 913273275 927428630 944032457 542548354 846427524 963254365 985332217 226148419 731988492 897469505 942222175 197345898 919037846 512641221 753967641 174143907 838609987 80355375 241216211 389575840 724150143 299666056 609789126 419319988 994643526 797610237 805104499 493669358 598024177 725019478 909772365 607950940 779069573 951368714 983552829 836425118 954193711 433959172 866536895 673572726 704513339 49450678 341119106 317309525 703637468 103719212 255333498 705426450 922272408 224604297 427543212 873054184 975326776 751916151 832110487 462878917 557883018 688909581 954320948 189967481 683310143 407580698 478110731 498318657 738939592 813477474 942201698 144933458 698016334 469830222 798066492 452575136 940986745 763025155 971582129 240526551 934980443 751614678 849388844 102083359 740582805 321515114 639671226 904707385 927828221 975804965 984501514 491020028 528377183 215032865 958937108 35927013 584563083 522892762 968802088 164454649 545220985 39466105 852778113 838017241 851003509 118529360 176884495 645924698 740956393 720902732 847335141 606407678 912261066 674584870 892873646 750612516 906488801 510171582 550604666 529623640 892795216 313880375 383393694 994926573 999222441 837978089 906424642 293522035 652048903 345484826 977747371 879465718 880257881 493985178 494483164 461697559 542233445 405477570 655006578 248679283 539045200 382158011 402311847 317524460 654195597 690977205 830566374 579980256 819119124 705829869 710425228 889094204 956295122 915946918 966661123 814626589 972849462 762189661 797099189 356026810 901029339 443945653 906653285 735037603 853252767 518276384 943126694 428737860 905814840 53591245 827288865 854833918 927684705 649995053 830303029 384967754 520368986 907674984 941623452 896484310 952463523 161459122 311315760 401315115 859325150 901610747 910860474 906659972 997193321 824784865 937725258 631474689 979334637 859420766 909816435 539497697 836010785 612543436 884946769 399610604 846711981 641619923 825916573 645395056 776672294 177246880 551917418 478391158 947118303 398799207 822579729 489437883 639129452 308585987 948865071 594777225 895830994 984583362 987701978 813860791 995100060 703940156 930172952 674510370 793317867 106796026 804119063 180588109 944744558 706593751 746251907 514878560 587053882 996332073 997687166 334771917 364876701 738998918 959970720 998837519 999785895 331895683 854509533 209505594 309053280 381743769 762203925 940037579 995325057 59396456 620112772 639337825 988841203 179624140 408682062 400734845 494640226 814511135 961011824 556135711 577320222 933196170 935494765 217848346 790954069 292110643 941265297 156420894 866494585 633786521 968109988 767719690 991551062 907265687 953898398 449314615 939499389 54335117 603436974 178428897 940833906 736683086 914360972 478689110 495499975 636354710 993655890 794422905 975486558 781858408 864001550 54847882 502702444 208500131 609431048 130587597 899701121 185013570 813016696 728335573 740128551 896095354 939385974 418816651 870319361 702303039 912433591 971407648 991805742 805208265 848570265 199608670 966414317 704890667 942075406 219616754 756069575 446057816 984010635 342315627 503928946 558089803 867036149 31034315 435562921 134958659 936131019 162408405 309711670 566703373 790300977 781194528 806611537 996420994 996600201 480801621 918098330 747118793 845910438 209336149 558080325 143436889 359441640 106565543 453869119 39735195 109059667 856244558 896646667 982309306 989390895 353664326 976869911 496237850 822048311 655674871 976198339 50511820 547114561 242574351 531511683 444078384 569096540 683083203 849586071 30661227 648767577 67732702 118471021 324493400 785195540 31908542 267987700 411682454 482882436 611169356 719734219 119628620 336473300 307122154 684717907 94470442 911642367 414191812 884237611 968451753 982975934 733100173 903401322 322814800 979359721 302468560 925601684 950499882 966030785 281376937 980918122 32933725 51442655 327937357 482898066 609570847 926650804 305753514 405015147 458062843 789167966 87319751 188303683 589493803 704987909 121087154 621399576 973214535 990518955 502791618 672201440 191400196 655273528 537206297 620563507 113717800 850666562 926921779 981865148 83700821 757496406 985010355 998966122 722894846 934731499 261251353 872982601 743755442 771837493 127746481 753827881 161628389 697190975 17840136 673487133 700211641 996935931 169834105 280252224 459896180 986313804 201609366 800518730 301030522 308715687 862368828 955971687 969365338 972408591 28517085 643596827 947146499 988120779 248180591 722729702 161875259 796959369 385777604 861135979 579759918 884635089 824021454 835695762 718440241 912969862 555115514 773469884 930385550 936673144 364274172 872349717 435072321 868594049 78546301 634012197 784950116 929423612 36622140 82009810 711731591 975120872 924634648 976786624 295824738 958769895 187985904 948285158 185319295 235901537 718795729 814725224 220006819 779434191 422551233 610589612 292769853 423602340 888684564 947150709 183223331 864668773 583143455 586255453 758192599 947910942 655058138 725763303 121973899 610637409 689281546 862652578 203387762 513634695 82937832 539641834 15743820 55027134 605837306 790003619 202411973 790464721 371436805 539265186 845810804 919783603 996405388 999520283 52211574 166410231 577031350 950813523 232772145 964519425 682035978 839959088 510021404 563935457 745368874 957521603 178321324 634368944 447052370 605602324 54280716 124924228 517996322 891738349 668530935 998028065 730400378 785478107 364938861 888536336 71578392 754698261 861201860 874328846 784877703 979547479 36105675 81247952 925356635 958159278 53065690 995828029 35455225 715574161 326522201 482479460 668808796 776880217 318452772 973055708 314429738 429655793 988945913 999049774 986367228 999443508 78120084 256024739 562164129 624072021 652198055 672516473 249912180 637950448 516511431 991827055 388585375 564000747 357496842 363978882 550569988 746760203 166554407 832848418 238368886 851821448 138835436 591924855 814194012 996968961 814671486 969015821 307923144 693979475 655031326 791071195 705912964 998622764 356712493 668957525 574379497 618638117 842087858 901878202 309410345 347869003 845684804 865809580 982258660 999774595 274223055 873219791 232802865 931834053 374942700 523427851 138192552 146392163 822151309 938105096 268378075 733436157 44258885 750915227 867735642 908815934 601703628 729067801 927850059 985214521 742609797 748885260 572082310 753640049 280475381 690843551 167832477 886678492 209520622 688327023 788745320 975608617 134543095 733204880 395547318 938390552 49348696 669015414 931461296 936253191 961083045 962165338 916360270 987556461 555824516 798906698 748672256 999661713 528753208 715995120 996510791 998129026 855511700 873490559 919308292 984137491 120845065 318744817 139849897 533189352 290798200 681688814 712117019 985094870 859036736 901112227 52158335 929186104 136611874 723424835 406325024 494099580 123071754 895510391 772343839 837259395 789241582 903570620 743271754 794015292 545582440 929001561 708636925 849002942 721764691 788714295 986564986 996009934 453439150 471146087 732731563 813757530 457083487 764619431 903593776 926447998 739948532 742759557 535804957 925436034 649715156 900444893 45696536 748115597 495737617 534341790 728616287 747771665 477179472 524894869 852248468 929679099 60465770 793054275 725037458 937273799 645450732 880370367 608568501 715442576 317939019 411459445 402924116 424537786 515380264 518515038 492075652 928837841 318208451 718261554 868585886 929174694 277313672 885818487 914455084 954896277 82049641 778393307 966957572 990008433 15452033 889607577 55051979 813218273 954257935 993947829 422968288 878938482 416660220 429416758 87580595 911223179 980594558 989058142 219049873 849341913 368338072 553611068 68280634 932403449 768070831 868098043 876712301 894185231 384314994 919891760 827642365 840437607 242219241 284635941 323084982 333233206 809009935 890291156 873154437 876951119 871615387 976095962 524988841 642491052 489908194 884425274 846450221 927033170 702988849 994703176 360217392 849599174 508947804 751770296 680883579 806399923 140109948 182438416 501563799 777624162 871859601 992933756 613055848 748113734 108306052 372139160 227290334 783092492 609308060 950409730 190852044 679008647 186008998 783740172 714992309 919394495 987193972 998126488 572072099 845773616 198116918 632915255 845943966 889736446 43379938 730492185 218264154 458112915 987638744 990842109 572137679 772145651 842553561 935368019 444335643 894709451 890819015 967045076 316646961 835319396 823651476 949355396 507199788 533601346 706816116 844952782 906913153 976487373 419824054 978268876 562868458 837933210 462876635 986524391 493111032 802457982 712944832 781150704 357858369 585269058 16716204 75284746 11990813 333441058 635491520 935027011 16463430 355918870 421690114 445351555 29438865 379388325 290347523 816477859 253261954 302408684 49647363 355316361 946290423 951372641 112832085 627365276 900645209 912491558 396126627 450582602 883369913 915114365 636616971 873994230 68656262 862427043 646718216 884023674 450511597 936502709 712934960 825248974 75087782 555172093 607237810 706157241 352419234 616208560 854249060 959846064 933026106 989592940 970711705 974469004 160986053 410332008 306757629 871593324 161629852 528804407 890617345 993764943 331530318 589291768 44329420 300489336 257110746 607258678 960694499 992755388 715706389 719142866 304904348 912428015 131012601 523111705 561794946 654599559 726083470 797179120 625378641 965046495 948495357 963789490 198120991 338373728 802126929 936280270 817431695 851553181 670135924 724662166 378677745 643790472 903959621 946833437 404463496 732208158 497086505 891079305 42476673 213162071 972524133 987617366 233867644 877606463 465250428 578682149 59035071 743353922 950355658 986018570 479996644 867624506 314259776 717938567 315488655 806167646 263918578 840572368 379498284 820718531 677144278 713670683 519626408 861617609 842565929 930661334 939118855 979822893 664772748 887701523 911602362 923814144 688538511 785111666 536919482 548477635 431096838 616126428 722628350 748915474 635412606 831616092 922802800 981071468 83692109 621339051 635344759 703771488 847979252 956009689 957429228 991863532 129113892 514350903 44878882 871869074 176816769 852679216 245686441 494004710 245382372 302463409 550656469 788418800 473373063 600545765 834231343 945635876 169390640 476107209 566654298 873218545 909008110 990811693 938841185 983248149 259346032 754186894 740162476 786648457 755177615 858036403 409299992 497536307 771925478 774167341 351583382 532916561 521060206 865575761 923854849 973605471 162909517 806160407 575678767 818001366 164096738 776821545 913314763 951679093 435022213 446094838 780068085 871235751 920840037 945255730 331765361 653877161 331462162 631785212 407350101 661459512 957171895 990737329 879576924 974705266 134836493 746016765 533598400 869301391 458320254 583526834 793659805 920232659 154654895 397779992 437549481 717593216 608865815 770149001 915336659 960528242 16865451 110710072 284629470 604215086 358591665 543081732 486263961 686006108 478628545 543746627 472092843 790995647 690673552 976476685 617364014 926191060 885665457 939699499 944456086 967602700 324082190 881799151 793838606 891191603 575979377 976470457 676293052 884403754 432953482 586314482 400174648 503601582 638223857 995678084 673946815 887924656 228854805 826729399 591594263 865892998 899669469 926735365 476180508 631326480 673186306 799306567 732304214 854875207 426318110 900046873 841852348 945294274 626463683 878046051 260334670 459953558 908417295 986384190 674567366 827862453 512894749 645605633 914798938 942921107 344665485 477160699 657874758 760398294 219692421 708368381 914014646 972005639 316593165 316609953 405620381 697502395 277777215 989705464 39344259 141147284 871228726 964323303 369418621 598611642 724493467 980091023 672658955 695977839 946962898 963564586 624243447 876616202 326238585 489016584 889579954 945813671 158542348 204219053 290263583 854025110 225683058 287921217 264986854 638067521 875092449 914237081 814448231 879589283 431365736 926259126 308892998 699889257 458848524 571961801 195577148 941351183 136045214 633604164 765960264 918647027 59170065 166263639 537417537 681170950 636076072 743792859 355235163 383052138 450325759 670350404 655384104 681942917 251581196 462897733 311413571 965786719 356267252 843508187 865874100 888711810 279028010 659380871 403708577 646638998 25673726 245396664 592611530 756805492 395338492 400306572 930362662 980340142 134563386 531176124 823425952 882602984 732826259 863783486 909972469 938616667 91086093 916969433 204214065 776539007 275041478 983596994 654484886 692821551 838475828 854850647 886077238 997677849 585832367 910108153 666160696 681825948 223665819 896235999 893920490 906549387 586535199 824284660 759077504 947212703 709159867 941988544 918163255 995845112 697881486 989040463 937424741 974266885 952810871 958943062 21072296 736433264 522406170 523303945 998967925 999728438 293314402 332152247 267902712 358006728 386707097 455770425 155952745 724555648 802357274 873376095 174623412 622016509 595274451 803567321 412686387 938587977 618223249 737131087 654237028 890321620 570654359 681473371 341662348 638781388 15782513 169470196 85252084 762549181 837263760 899227234 964405545 993024832 143267365 909281813 439693336 492517297 418306785 479064958 13981758 757429467 170645337 894227760 561691234 784777924 936704209 983243973 537106983 965104684 863772926 986397601 578603329 842268174 736638373 961212049 190147964 655485316 933880331 934092472 148130561 975957788 312674105 798596743 566820163 780048030 136158591 506970406 781204059 812707394 491420374 769598817 55062378 249827981 453272617 850823893 986987102 991265172 335266350 966134903 488805900 587168906 175020823 984199966 985226379 995336974 898889848 989309927 192471244 426446111 809381362 922258376 837870211 937736671 89107788 610052357 405594472 843195859 581879455 986151331 668221169 992780036 742441337 909394299 992177073 993015257 619271030 715459253 386993956 602704200 237157535 390452146 399261835 966893450 16792965 785008168 822445862 960780067 985405556 989685959 648476881 701110156 128994921 982056103 905440403 919117251 592862819 763683059 562212141 707574727 918085177 962192325 39693826 697807409 707674465 910968503 284583543 942877540 393010265 920666543 430238813 864513022 733917874 757482984 880112147 883498182 981599225 988170114 601015339 742199006 89259180 633057161 631520035 797490274 545866300 923032964 921458418 996016164 407659955 976527656 402391477 560231653 246814685 633692783 777214670 839622106 747346280 988181535 575887360 884940535 224769933 704649951 813307639 859916499 954133111 959937097 395259571 678366173 575350643 768036127 146251697 814027010 379578413 899532178 454746041 476955254 78283262 345982599 570772187 687540043 711034874 730505451 597390110 672863391 933720306 967347580 949864105 995613058 681893665 988584298 838472450 884232522 101740448 487452848 993912592 997207988 983375344 993000357 603325333 698550790 126058775 892103571 183104448 789627232 221193928 406133475 133891815 288988174 865246023 877172630 63893057 512373064 711276193 817985948 390662234 469099343 276948254 677929003 489778910 549465135 154449319 798682478 385075456 908141061 364906312 474135960 648158460 750092793 791881308 886728971 785633107 883101454 608899701 919252769 221312377 232964766 877703986 883214555 497250487 711805049