10000 8523
613899399 533067621 141076800 692475252 911240600 360924133 791333304 828608101 120984673 234394592 916899913 941543065 876578386 329887606 628682026 699480101 934372881 201069376 773515197 84299851 689558757 209619851 880491365 998625694 295716557 975848072 295815034 30841287 81364594 482179349 768933603 658649887 885619511 121596818 694376501 373111184 863808706 274642084 868661895 516769838 455044091 289672858 718040575 435051502 376951497 295723231 283965806 15674227 962137090 844059321 422016867 858675738 858932088 965408644 602743249 733412129 347525526 812212350 378161995 62772434 840702573 960517597 199424958 305831483 457428681 47274679 64946550 591190388 257965505 51221314 136406742 191070684 342723479 971576186 715633461 598892672 376875420 783947272 458967268 14158366 473590449 438731474 604247037 422025683 162204431 784947529 82741657 235906396 946911505 395760136 288274626 45356525 761639737 356909224 533912402 154849517 684464413 894555451 46014319 910815151 680989330 985925331 843857170 319603323 763174041 372013232 547065574 717038712 37078262 700859403 493415422 537863582 271066633 541199483 561790430 221252924 578656646 228195461 395783629 451337245 753156821 36925547 348873784 469658142 229620392 595149475 627070349 454678672 94239250 264400251 312103079 715647315 400643882 57238164 75638905 794574424 91759393 374184693 544833413 328128012 712282607 880009702 900264291 684494141 888980820 427430417 391632127 638454416 617643519 149418061 112320010 837934743 88943866 475126976 261031915 839698638 667581769 239771945 118343035 300375408 327146587 480212548 995937364 870510876 248285687 435483478 758727951 792918301 59498292 733553597 712687009 407117686 418492148 158705014 657558605 202304984 20573595 286754540 764260991 992053923 164340379 59424901 250817689 416557104 714507201 861651422 607656005 304044931 254390614 246036689 843714301 906857749 56551287 897333451 207723865 83059224 179120891 132347108 43447240 987170705 598630413 509513860 976569866 35460021 892388739 363878327 661069845 651353636 241368735 148954862 757232658 7771869 927297765 373805565 673576423 349497840 755383189 982916760 792822260 872415678 630208208 730380713 472169809 895172203 523248303 771118844 928277833 756123890 978284040 449992975 841862642 152918297 357032628 510909721 546370566 844422856 69221730 931570917 237769025 116606113 856827203 260817816 49393622 791838070 613998342 674135241 578448594 393623981 24886261 713680214 136208104 209237557 590262618 66941151 537391934 339894665 30374845 903786308 516044383 807888393 21745447 804504309 291064465 971460858 245215028 932570061 75286784 402698433 673706127 230318571 428965628 1296817 247352573 632217692 268821046 655178336 910423735 933748102 550176010 464550463 253702703 100618027 512940205 825983149 378715658 369074430 895346769 178584131 227189401 451715617 165127080 556291236 897383785 629927451 208974307 238574998 2264202 532543650 498786414 804257669 899162189 253801068 178532515 159949134 834131586 762503461 953568239 280890343 860202430 692125488 778640915 542969901 291015037 17581175 342125966 353451467 157078699 234084767 512779691 832291218 827631378 19910369 496624467 562633016 823357939 170374745 479986130 534412569 348475357 783654552 127101800 245267999 12787093 718425574 353092489 676607204 822055594 725551601 345984724 409762306 818975186 31009370 690066538 4011 439322132 899835315 42651383 530988841 709522173 317427034 567675155 715542976 465092546 43917726 976128691 643370549 748393569 374733934 345001702 886539261 340604699 256180616 614689782 362189773 154885106 358369098 541408605 4281675 557746446 432110173 659076711 484731913 851652731 952341330 659510353 926766903 903652860 655009350 21152722 356000587 605795782 471312162 31033653 656109499 840773109 296505197 126943014 49351515 492528176 732141513 107314629 842034200 642992312 509805813 548771781 60820752 39947287 476015116 750777466 80494721 531732964 45408729 452873828 691909400 893691735 589110429 784448160 312297453 871650454 546829399 204224556 677393717 490935304 727315121 368846009 515591581 318488346 723497833 301898394 420608320 282711206 469682541 608116727 564899005 550018080 716728349 61550573 212327569 311725294 158019128 351360877 798408726 113526874 298940880 557345418 433290131 715043717 221084814 136011872 67736257 243710079 795379750 487626297 331596670 175462533 744277457 889781771 723732156 297725214 491732812 758235362 476541136 517932830 760154094 599106407 415201660 704780760 694555053 180251637 539971241 531571692 838380838 252839689 911973862 109123060 752517388 849337197 204263706 329851112 881839693 767900605 691480138 723058887 835521347 595144388 465252814 611145051 698237792 515869487 900387798 402399609 596019627 23322490 669791261 594119470 205597510 547082729 236568528 720231950 143696709 245253044 610665278 456609420 21818523 729947485 856234142 850554119 612251184 523801567 387248123 613138752 369957613 277835681 432810781 453721688 584245655 496174480 422920043 142966054 681175157 69158705 197606798 185809797 365821937 834461365 363340322 479578088 938171775 118732316 923528438 957683153 406615577 136506463 138060254 580769633 364719438 539366699 289858127 209995566 829926451 133563368 971642382 920799104 814342157 123313179 1192295 294082092 887159394 555193254 628483070 701633594 472372528 286697979 919839722 37195927 625377620 624781700 541122504 542755779 806198990 57688304 863132412 554556645 890491309 327205149 454983278 810408675 289701309 354623995 696670207 562041047 195744402 519784855 494251158 941972074 441296367 593237898 446775000 650819518 398060597 425993551 577659206 135688983 995415209 470463445 163097 723114407 324065670 510151162 424847268 604549161 426873492 797420359 727561140 8278621 45394360 553428588 175809239 717760758 563243982 969801804 249192642 846846081 980464669 776760465 336556844 329987262 961490455 492849043 909299055 638493640 721213218 949694718 649369388 993935603 931242293 791840276 832115604 604939507 681863184 995840950 484016738 836326816 555114692 515924000 355981574 530492532 214195269 320378955 276797407 334530526 4663604 796292498 741726383 200281907 213682781 496149058 109144435 661477204 355748925 866470846 360372532 686494150 739759697 225926496 218413919 366503309 319266574 237277223 561467235 460523779 458590083 34822750 618028917 451919094 701817823 108607831 634840158 606112595 689681682 815386052 38892860 864091795 631984356 935930127 726538267 974277238 284419291 45637300 554237743 902543790 5969133 541479937 37818250 811175550 634190753 426464746 671965341 112847462 693461724 512086272 487283244 524359943 597956917 435703701 143911638 121331390 327005912 35731377 502279894 36540055 126681549 112541680 341751588 28143108 120426652 688023630 884643796 937238605 831955862 211251193 200796200 878379670 893716664 524268797 540506782 75700465 100690600 873476314 799899560 472182205 610326229 959574661 557309522 7153003 840017874 338235194 65175138 204674094 797783702 17091254 140828360 337867598 181079041 496701854 537542102 523526637 877737529 779612476 280611999 320897407 787092676 48957104 415703734 637470149 397773532 908618617 100637897 587262628 844299651 236790448 548631561 265645639 363484483 358821112 171002692 870966750 513243510 828225724 181049581 83451395 202887690 144538926 532818813 689857209 862656956 672856352 822744688 880014385 623810484 461338867 327110020 565817674 253393632 874074383 570931297 284524243 622564130 744338434 933618986 243315101 933428217 71891154 325377994 450393997 161213013 18593363 970459405 735673747 843421394 247954027 39824869 898491555 722761535 24887782 175427559 387289720 422346035 411897787 577706758 989333903 369382096 396677710 511030767 688839403 157759236 13802489 463279467 538667004 548532624 416016772 77673373 247655687 666257066 493025637 251886672 886064687 384599121 875941498 26966392 670443605 756144542 352665372 536785204 774466652 301837937 773610817 14655477 890830817 273652607 906330748 823802636 306525291 665369344 542926700 481295064 577511514 177122291 200608806 137335732 946798392 270992461 697213726 739159936 762896814 546645444 464540987 23439102 866133670 479877964 865903354 99845273 68616873 393653593 843536727 126288114 850202517 216652263 825390102 928710719 388975435 728599549 582497032 799687873 554662730 626058523 750454936 111771180 982460796 813520818 60850246 486407380 789569172 141180152 417831225 637511395 375179993 149803798 593317418 832565787 206010115 244917495 869367803 663285065 52732291 794743102 103354892 646349790 813834070 507348034 690673756 213333645 731438789 936905739 380304989 90205309 713077992 474421957 306656660 685692660 781989879 128251164 135251784 328016727 927365645 852754060 860316048 336925933 1017640 255046760 387304124 771960077 274715059 216900381 777136009 468878978 180725622 901842789 278015409 974261800 65862987 761911380 261627290 2342467 192798761 149433640 929980642 622127072 806973202 567725629 939277919 526311115 265935839 605350744 210450260 76991673 569798479 374860537 636405443 901906569 934317116 444401946 621630056 556866606 246932741 630787183 462803801 271059104 381886708 571816357 107455787 549776724 348265446 955729582 564481609 942636394 483219867 709715664 159240723 251892002 217979352 311301803 942137404 423812964 190226909 328800164 528655329 61369069 968147010 471580449 760810684 510220425 749433157 9600834 729263122 633510332 955254451 115926043 913967798 114512008 439755606 144768288 185594218 182787788 221032755 379955736 927840663 175454324 991429891 231500371 985745192 172507609 296785773 88013731 51919714 301547845 590022843 142300300 880706147 598595236 723565709 391135622 542119613 94376622 264047448 296860832 11004914 48704480 655937173 760635900 711277808 662927775 212462936 261109391 771935138 580863718 399628054 712899803 890657247 269186238 756857636 921032045 97023278 945035160 556010996 648443233 163004236 265979391 565879420 738771653 571317821 903643010 293285823 698260411 601282899 626371899 126681912 569401979 815736425 268409367 802472190 270450342 669783781 470029304 134533611 916407820 660206385 76832047 375259773 403482310 542837632 9044417 418579615 504874438 736036422 604546224 40412969 717435243 164203312 953167917 432045720 552320036 601035222 824096581 21541711 613137532 771759771 840771608 203754981 881229634 74874408 181262490 696262529 995699670 165624925 850760516 68114242 140895239 60548389 874297474 558359598 146014374 517037658 850534773 519440248 161323310 589137042 598925393 706585816 796936395 407574336 491532427 404687271 236575402 446119183 505850415 877699669 872343521 780287344 282123985 756006267 230761339 251873036 467817558 50402532 296482843 21720138 807583012 669637963 853938923 990248679 18733878 745810929 683357137 346467561 561017064 67286733 46286 476138974 357206215 640883821 34977416 458448973 164220178 810730652 146305873 190141330 841132781 887348099 920640314 683028388 546533131 976743571 935672608 305854860 748507568 783123489 311360735 330879171 797511171 522944802 835877279 287196599 512184958 103276675 193392949 122900653 71040516 366197382 639758013 14996215 182683865 936497530 898317267 524767887 540899259 380066939 247166720 940896705 63366951 733710357 613622358 311691088 405856760 594031314 253824276 555274881 426971352 409288103 836109175 5784636 667530899 861379093 82347271 557025124 691932768 112274802 940815045 230551411 956765183 333112067 228493332 324073078 591241390 248751123 565809573 973040 804677953 58999003 632370590 569730928 383020518 549314019 706029675 710669050 810814552 603276092 224396203 188103926 962577032 540566427 39108738 761399768 790607111 17920852 328672115 573155101 333975043 683044869 592841538 67412290 890132519 314726709 928207055 178383221 338108675 572410401 647555652 825240500 718960710 838297850 734343673 161999561 151489641 688620411 815339743 631435485 433147729 230760488 669702230 239749390 284882895 595672376 294273959 96967023 718864066 285927085 181579212 666087516 124892824 70891444 721978603 976800333 823948843 734964280 323015836 598743510 865103335 542483734 793744177 634856607 987225733 789838898 696354537 126568805 460824138 512269219 190282981 63358986 733066507 728200772 818043965 586467763 824012705 656043738 472507736 943653408 189314739 449043557 674099821 319517084 654587694 380210039 142786579 906201329 675211824 576196485 316922932 981013122 921025666 955014660 159866148 598154923 461720498 363791433 837034169 902708612 83480151 446635137 438305467 716617814 313741834 472385129 816006877 90043938 586036214 907237347 432349503 74653595 355239128 507116482 708072630 627965266 73320933 956370199 795158808 169754162 772518208 292821697 409971143 465478133 511556086 856406957 993559114 11246460 160331171 771008067 179477466 566556517 704846808 876884816 179698423 147341305 774999950 852589039 723838449 799388027 231565701 780150836 364859455 949572236 138608857 472913509 943929184 381653305 687541099 633466555 241492482 105459810 143379196 676813164 82844403 339022722 260972295 421409088 503345829 217673864 21894301 877318828 552615304 108424167 560863940 10248615 210574964 964814861 9784685 433274337 455343627 607653661 518002588 952307430 942191369 478704995 26681053 628991257 573385713 815628854 999540118 939844323 119870136 753183884 331833230 102456104 528012126 320595057 27311273 249866869 746607740 31072787 956259652 853922740 505075905 74260791 657168156 136298280 324426088 919453990 380962916 461600081 483163627 849885267 341955401 899709701 336738926 90633858 54595924 295001811 554992210 791083059 19469458 195308733 853315248 426630327 266652683 991906182 731895188 411982852 37278126 430245983 492498550 409699087 718104224 875599419 135854368 535029211 884716058 817591460 484247464 919927032 841617171 366923874 160640457 358177105 402795225 93275764 157884782 411064657 540845339 965584372 307478285 331884112 481806909 320054651 568438258 435677089 435066462 886280478 701900169 521925827 460760872 441981023 563201333 27137381 222216284 260486888 960102228 563931540 306125777 261184030 404078441 53817471 436905664 107030242 858816834 355324967 982510563 650877154 910423356 973704115 434577159 876466488 638840925 795517617 476540703 25164592 184101855 107270098 90175045 692501751 353731238 525205280 871839248 751868281 561666318 284215320 178139042 498442986 570019418 271469225 389726844 272930302 604685957 709259786 577274093 202859710 77892287 136555535 139019616 76344472 986147540 883501371 427137454 849597768 118796279 841039675 77821731 529041070 338248774 51805104 512909226 268983665 799276619 142828221 181646038 168994956 154206528 942686975 526195775 794081044 149204819 368601678 697118080 203024707 139466139 927017779 684379075 608540163 940587189 916754643 400623121 712245448 129756259 189109545 980834154 267679354 560724437 309782906 631767596 440894834 820802273 186041035 694434999 175445105 440274200 70115958 514562556 199325989 556077344 374316174 445360414 742259190 709786101 624082858 465510940 403535448 227163469 711198369 263732408 225824344 853653070 338977703 145135993 548021814 262073487 492688338 695173994 783071359 21056001 227868243 800598744 864297710 587217182 815721618 257063742 400009598 384340112 873840305 585680578 635515247 453477874 550521282 920879290 587098188 952735138 514487301 283234840 647451296 59598863 434715486 207895185 453681727 83475642 228069452 325329909 511960165 682812352 303903016 855656188 356361327 586971604 103848423 553735398 573450082 511131048 979081293 655730048 270122599 240083365 885828605 510241939 20064944 731533480 435040235 451942326 860888633 621497244 302134671 942375388 169347678 22115833 658850291 565525765 949646740 481093312 628303452 961580887 90307539 321636699 749090866 976228293 5935056 993921972 541863035 668933037 849123691 660081355 429756836 685132748 219609019 896554320 876943046 892837789 154618078 706141179 398086576 904172055 460505558 723626767 31467829 713487607 525097407 962747634 603092412 251919656 415718083 497482470 35105099 588400889 110305503 890005971 392271012 535504025 424011335 980750469 913395522 813480998 372480121 623733581 724461512 633366264 615364441 123680240 38461668 697264873 460148569 813343021 672545599 371531989 309867225 622700599 736023941 475417399 934872842 767889110 270448572 14817031 587684070 50799155 13995929 472952703 633009972 634107214 511233568 73488963 380775419 715905290 904027488 638441732 940976150 530035718 339011506 520290000 532238812 686212436 89496015 528582608 532232835 667841663 879720159 399412877 200583242 651347584 48146557 332510107 392383054 954606020 199693853 885483461 286842908 445143502 925785967 872431723 874921218 729810472 332508154 879831124 901560411 880098149 840228557 116966414 980186673 360333831 526867881 859452643 521909264 378286089 944271135 510468189 881734228 990416059 956586410 964581116 347705980 453252237 439429948 516622032 794542661 176226554 627496343 755896356 52739578 296845788 886608178 718419802 529617813 110138258 400995155 942114309 757986217 93628690 102544319 976914633 481088436 456402802 565531087 719466078 293087828 308030489 783152190 276703840 937958025 575756479 631082460 783983352 654466148 929495444 924695883 994554480 518187623 501608166 127814382 462507571 842682253 752174657 944039602 776925541 232600626 216076053 206285924 469310313 532320633 758548492 299117632 575893683 849753703 2156177 458446269 797456763 234352957 865381111 633177 351344907 102935823 739312148 357399040 416539794 882084897 602139860 370371387 183171536 135020848 737811672 943677743 30214720 685772762 625264711 416273720 541176687 704461452 48397172 906437152 356820267 176939905 170649606 555511243 620737117 741358431 412697185 979259631 409236955 209076286 145519581 457979871 1865113 137514529 972119802 571477333 251944494 515411993 710113213 679903701 214553333 517514666 177379591 227249911 653655350 442836673 87628857 171474836 883233420 211150147 681638271 320582792 295265029 851425245 563316272 485101654 698746207 15071279 489963125 954585299 460547306 125912045 163978709 885432517 558525013 556884004 778776641 622665259 992790735 679999857 640446794 402291012 665692170 364541748 425226417 34389062 520938509 960433844 692619477 951070344 57836283 461398937 338690588 507153236 264005033 336223477 963479718 187714567 68287057 83567598 137890857 939408914 420578186 20908803 184535561 512296192 612572623 680673322 747398522 908838346 391051684 707253334 842646122 389508126 756876673 47098374 564792922 54714433 659854154 764348801 737950104 942140282 631660936 794850503 802527357 448389536 588293820 339356694 710812701 187411224 407409454 542547075 943457265 428507963 234459450 684585766 554066563 829454345 704827829 88684524 445441996 248274893 593816844 107457360 127613832 229397842 917126888 198197612 842956542 59568764 457366549 58439623 568618072 131297194 360625295 485914583 880231265 285904712 258206146 873865685 412975421 45854716 292800013 374445467 16153707 505865043 279009677 797710739 540777836 933863272 78414420 929934581 780171837 850506762 511920456 668748907 461099128 348461930 146658596 261132073 385723385 857154737 791248892 569424544 191229813 300767267 998068145 693282606 310968680 871276638 48732305 424109800 405989388 992066504 733549745 555435650 855494917 892624324 299729404 487672038 676921902 341152320 236410999 162317169 884889625 374044638 122698740 541258119 777904466 805827349 759617826 105123869 796304425 632221815 881795821 782160596 809936703 633899387 17336331 697718215 390016383 799352455 251354235 879458690 379362223 73140196 708547382 621353658 568841302 140078108 778024340 216737475 548668146 49709547 194716624 40910288 881093178 48314079 954607335 391720356 170245718 73066052 582875490 820439126 75068014 905109088 350704770 300946403 232551417 324786281 918754145 391849000 544707431 444743192 712766439 961540879 437265400 256820783 457608478 134103188 425762883 22390476 26699720 41505620 975184649 839182949 469733618 312348030 349166424 484561574 849629846 496055007 448735962 411005192 40104303 150753835 39686383 682378833 708799185 507289841 57678891 173867934 163607003 751115680 633908851 794385065 37282217 224746825 239656570 90289527 779109269 816885340 961773466 514084563 270722532 263949462 908532572 196743338 272740674 53814111 559536143 316425157 660179084 255591187 943105388 166885507 518249868 444204605 72353544 572834453 665408892 58395732 511441142 631017812 269650874 896808419 564253517 323016865 625827432 241515278 655554512 105836592 805504477 371875455 872733636 677726810 615360528 115597948 754025749 783014524 810887407 677183510 967830927 387799074 716558314 174769803 460491666 403813290 666392660 491159724 968161193 141530327 279805118 288155387 152057204 6720380 426211080 7647855 901705393 693241435 831409845 576649057 545132874 734339695 450039159 309153986 139167095 600870992 323507632 717707425 205024413 101770781 880017570 723881308 703229009 551320866 678189792 166734383 772912791 403975095 840883885 43209372 95315006 247274090 720250038 914729190 44516751 917547542 174012408 797551217 517853364 22690594 228853348 783231427 641444330 260498006 813056886 434148028 775180225 623190637 363891192 448738346 251171108 40615294 294430118 923988187 101141883 32420989 818346838 232261417 669874283 382669762 139627693 939763012 107928027 480381474 730531745 218577601 184030430 787396901 723764266 608982254 383423103 807604016 195890611 192828754 502019764 336705559 216300541 494915005 336775085 528166096 987084142 253592668 388310931 730872356 54824957 44630114 380371381 757817728 619501750 511460106 233534801 897987662 544076477 430090447 399035580 25314463 396652919 647367633 424008031 75541363 274915338 127572346 325336932 993533218 18914699 679337116 201564248 660075708 260008985 335281462 623335278 541842469 979278859 384091914 386004577 445602699 763808725 228589112 259641537 497545405 567045498 34401120 793216625 722847628 109657064 709673259 17484484 805843014 109114894 62563855 501778180 538407553 733538449 281700098 184892060 167927340 555828716 254563276 304251290 386313549 397055593 317457480 131855487 356081603 836439535 110701351 621392730 959411955 862678289 597338044 157231588 6085504 848723356 874178200 201392208 202992339 223663033 161602109 630953801 500157450 40951147 1808831 225840473 834281386 93160718 86622793 908626678 231294506 243296697 334977672 234569497 339689574 437927264 721737549 365544717 140119786 475204894 896053770 12916619 155031138 548110640 677191203 717703456 981790191 165975855 739135269 864673823 763043482 532750448 326165657 827052152 594283263 454202885 17084190 212145928 661852930 409323802 593269810 388161765 616277623 649851898 826943967 91135804 494175276 62994307 939211800 805871122 534337675 794588021 281660321 295648222 31834605 19208254 775622331 260372810 126101992 554878687 780592141 692512589 616668250 840498883 474318177 627419708 480458528 727935433 92658076 163611768 222780709 132593652 642847222 47872830 873098206 475227664 237202699 347852052 84776949 22408218 149034859 186079395 249758562 150321631 32423756 579455416 254010767 190575206 310158029 183925699 645882915 918565521 803551170 909966700 457092784 146739562 333031408 125948755 392749266 114003166 613149589 369623394 9750228 415897481 304477143 424408612 551112843 341610468 848822272 130078005 75067810 202346327 939149905 632759956 262921309 187882294 479313025 922501557 108938692 393973910 786519946 142145433 783925944 497731509 922376349 31800367 612807734 603123173 927024291 673488124 822986011 103408150 414975073 744155250 913492552 418159630 291665213 56144105 445838370 939398094 822879324 923703909 614756729 512651300 331189897 911311369 894697600 490247343 7400135 988778098 851089583 118341472 249459929 677706870 983829776 875980382 40735916 858797940 146951803 711284544 270738793 142502034 131824676 601732739 301553952 526120229 583747310 240066437 127868263 341761146 704206473 936443068 440137262 754848849 669269415 581821006 400341058 27938063 542245145 89492847 169859980 551252327 819554883 379519303 722311996 587766662 224357285 622694461 232447250 526074431 229042411 291785355 150179567 312200896 552973547 21355329 191062003 726216107 442445618 318845013 155264366 791389151 577900675 458648922 63824022 365634732 821169562 845878979 342396866 186672156 100151330 505001891 498605237 622488918 899889862 171355581 522162881 631085728 618267854 307976341 738552701 625696902 32489851 417872728 818737754 357741514 53237366 165951424 103340855 221279216 98405298 563579994 959777024 236176594 531552600 590569800 1292871 476930777 915154291 808630645 959772218 438704361 970880474 224854104 392274152 768683288 320835087 974986342 666110372 415070282 318304582 284038946 558514123 405107729 100412834 710836504 284236225 269864335 911832556 811296467 20561377 633374494 503542728 429357522 178115218 264169955 850084468 274828062 524183493 601869878 962150844 395888120 518746942 858487019 290427211 948246827 125826084 808479507 12369617 124761837 472579326 273097579 586606644 976742008 159960129 759710332 337809345 272390241 380651465 330406058 351832817 291069617 595570105 702474582 523551133 249256759 501097508 958482259 267684754 213243871 802517705 217720976 977960608 249326393 767566683 860306650 95662902 524781593 977530431 5303686 670739701 121547186 83963383 40241890 969067538 546971479 617426010 340394438 24903061 799453849 224536367 299128883 519282381 7452335 943600685 957710614 50588572 740516451 452828983 86372545 90533916 987046342 413765212 139311428 136365271 188241555 827699629 741125002 309193685 487346471 766322787 800664427 113263132 669754139 960898600 351932077 560823343 744513341 236987290 600341565 802164634 511507507 577352275 364546014 242746827 468055143 661184222 611997434 632939927 468815741 961648675 726678832 718533810 764214055 664025607 673468177 311829166 278456547 776273102 474558727 87059165 68800702 117126203 829511200 180717755 647626132 606929054 856456508 191286755 118259996 166441 378536121 582857907 364288186 283869632 413056177 638824173 754030729 479960890 384335378 863279891 555341129 23550435 744962175 567014032 403575460 474131039 93798861 675120207 299084508 569184752 260345142 958619695 108295542 251585379 273711741 673245537 419863595 793390871 872212062 524749047 176634511 280569313 638419732 351585179 535897827 454706103 630839821 108521100 304161416 318753335 836745499 69708420 279471183 451250483 236738607 238437126 435435018 567582101 683838964 865705259 431188290 198372640 768939381 380744872 532270114 131855431 343285536 486811201 714942925 468223556 644924971 479084073 730735023 987973668 132774917 23348009 775662603 349679576 300866414 654999186 326386633 194505617 769614698 716907126 123562605 127722207 335780745 450073451 867099984 668612213 355082406 116613476 997425398 918387961 328086418 353904835 588628243 878460507 744417531 728847511 234880318 174206695 363383817 926245037 879259791 315211830 694319036 489976778 14210758 718842266 31171879 928661015 654587438 315497348 939179946 875097096 16116177 146087771 319192631 881823317 6920244 801820356 697973978 327933970 417080105 288366734 708674343 751575072 512805061 323575769 498473812 746039043 890622563 658330890 884496238 597800951 366153018 282286152 827015239 643329233 177746368 518494823 942199158 27351031 901409310 911921354 235445736 488523887 790597642 877866491 350245606 16866755 944170190 783541246 275756019 954007303 548518034 337683528 885693245 604555705 441907848 1903916 182168370 364500058 252176960 369984880 877029331 910279761 840495895 336003043 549284604 769079436 122943220 883375400 766806795 893505833 938117036 434673121 744170748 963936819 483200308 973533503 668472082 824871095 681110160 892892967 794419503 84527422 510164660 430847875 17169353 385237051 831794010 199276547 26072018 325735237 459672241 258250887 925628081 638900311 391433438 312130049 606421692 298441991 228857799 171202495 354011815 246889171 329741475 595988706 497038119 633474697 180208280 423065813 681222794 698266850 747838021 165320417 811407891 553272192 569821595 667132081 229392067 635687633 171517033 525500062 236808542 122700678 553696751 67776111 749382608 328869269 925272338 421923829 114734255 202239549 226206237 245891321 664957350 1538173 129815635 164707585 218598086 46155509 559562628 492506986 476270940 708871179 964199439 801685110 353354358 645919012 463783097 267076358 971346950 390304173 370694713 495108927 499869746 293911418 801551971 586806069 82088443 493568206 743446873 794480514 970308924 901932911 694235154 382266533 403690496 877785362 312629035 537767711 85307444 263326580 201691280 877909294 175445862 927430182 72853400 903087082 133379232 445542540 262932300 538708062 435797187 156280353 819789651 937894891 594323964 35600084 502074850 823756180 35335888 203218403 763435895 313465174 189647169 714293494 804768459 66076597 102234868 774065983 641370576 52895076 188187254 828589750 709785034 501927148 713791943 918034713 604350375 558371206 626562607 218448010 731805115 235330547 101398343 468078704 73580083 992052866 774683075 364160306 272296919 811889621 589756634 575332577 373764871 938466497 311284188 750452687 492451049 18093781 74841140 97418032 772789370 169510644 722055818 488487129 354101170 821918022 344768784 865562069 657014339 524614512 746833112 613784093 871721706 229415275 391309354 79890363 790831717 69402054 929306133 105978638 399755233 311208719 195460852 364054830 400675187 864424164 397360177 931910246 242597670 156127876 324749899 716427724 995300501 566442605 653084006 564122853 570413857 530221107 354284871 88514862 188848859 162535650 864869992 340932123 785183629 410748169 546054868 20382300 91560007 36931360 711636605 93713942 722300647 65656867 245558114 932672818 897710659 219152357 434736962 960607525 417243970 73094683 184122766 829704853 910251441 590329608 387574845 399765897 995024435 511134110 302682367 993391699 363309175 147647502 350848426 450591072 334521240 989920747 742040704 644202585 824668649 990474111 170903332 113001114 414757179 152203912 822228530 284611170 436741916 631301157 195187956 311214192 246217270 629353325 276205715 50576917 903801128 222766043 760781294 442234852 443280102 472802980 331896517 455436633 160833865 532954294 1701415 417755441 532601868 903418787 959939389 806300911 951760441 422942445 692963615 822157980 804132495 784504016 953692741 537190042 40300921 566941185 956381841 479273824 831758180 550338685 762557367 510074330 774702622 276105587 760178908 339464349 513224833 974377610 813973084 972635743 160701418 74490388 837162375 840478997 206486664 844739514 792417180 657876461 204331822 911518287 230750071 938033558 543018002 358040586 287661363 933222942 836375537 387170099 136365510 419387602 354234936 543072453 989281926 901653905 107110563 317557140 391431778 663988766 268440313 401933747 24942196 658854927 121348032 833595911 892349133 328753185 542073439 236734166 967662571 879845549 860635287 397036990 865105567 697336351 971477140 595507837 23323020 812266413 989352743 50977285 790165756 120920978 13474948 452022251 937812883 179378644 866787906 502054343 394898854 322948237 562645813 719544502 274584697 787536862 734094493 692916722 627735907 248048442 58243309 301877890 398158575 44677498 697664196 814776327 632510467 505236999 110957315 299178028 125830722 675805715 71128365 959105173 885471119 82541480 524587869 748038966 824153631 435665260 878080802 319268687 241230638 435997495 888129692 201785806 205067426 192813167 869384384 318346157 470856849 897468160 570146486 54574669 523630844 301263904 276232030 247715212 120422951 601279881 431648734 207074504 518629277 10680533 923815729 153853908 584767564 361933661 600031098 803468923 268421042 846918430 28163813 646598730 388596176 413849309 317993816 651555831 176102128 195256803 168309350 791070714 898187259 443282381 39780634 965474533 802415680 258110864 176442494 639440665 153055375 853539038 774623969 246300868 646411398 22009609 807993165 437026056 209982277 511873644 122355556 216040950 915345426 804551847 442861529 728953931 991837578 565349093 585075896 983203606 5773858 566150366 925675253 413870912 723858818 151171667 952820081 968429980 453287290 451004176 980017414 334551419 959495230 769953851 971187461 802038150 613013509 91648155 686696925 87335529 625685124 88578301 402854402 33417486 200722423 561672379 212056138 183899728 549947022 668446024 249362669 848029424 245515829 526671643 933346988 829211137 903185330 366857298 465374225 791279178 178201862 833581749 401656051 235705300 382201271 990239067 624290108 724166363 941042653 49699552 625451703 164453179 330756631 836180425 865088759 611060429 912650820 440791592 807920472 539608441 404453 285353091 521585358 575422432 801581033 23554442 374436780 964449159 359190362 999962020 53846609 226990336 419448221 357253704 786444062 328402095 478229363 247840744 509796503 109575046 273548888 688938081 147426791 334282120 420951922 195498470 246711427 532429969 435492183 374116741 724429044 106711971 31522734 386137860 95489579 712476593 469512251 580985340 347332785 463137742 170126875 943645955 759021155 742396411 747328072 944466647 972409587 802606085 684757709 154052458 953547633 206870255 977993413 66079177 147919476 396754460 177514471 493937999 48999207 989760680 265631366 904019167 649926633 212540286 223624570 398540179 754718146 514681047 454153216 572751516 396800352 237033183 160390229 288545725 818756623 615746015 889230534 337679131 314123525 719721132 639232546 298353039 31565503 210421033 440252538 537649888 530960202 106004882 481860917 934715163 293058409 222756833 564619501 461616753 795574937 715660205 843988013 604357551 904719007 291293935 117456284 935882353 961547805 456317438 715941688 681306242 348727510 145057276 110909787 262295773 988851638 163384325 393452285 613113180 847860934 79047249 897599117 422310073 369935397 408154347 471243564 182403785 198657050 181567176 278926017 328269707 583106677 517643184 671313283 613105380 232387591 707818683 613445236 810695526 426580328 401635570 344089219 412253820 329785135 556988447 224371547 799044720 827290434 574602630 424031374 155341072 283809670 142162335 210404867 77215873 490580521 2930881 304287650 750882130 96572907 155212036 990339968 50595799 780146079 703186089 759105621 406826367 533546944 775223821 334895981 656781251 244785686 428178425 535858092 984548187 142563177 95913202 75937534 48752531 561399890 331091919 209693895 963301847 992781001 13309423 802479984 60147615 35591609 901058861 712116310 889351710 558864760 829244895 392012429 686680511 45860129 925817091 782279834 649664106 270555181 330360892 360744652 923917587 886160035 136656131 190663804 785965267 203006169 11773818 784970818 368574922 651558223 978544836 198334634 114930513 444536740 633328419 716735906 895605285 342311512 249048666 197312917 199251018 388404062 783838486 530223691 167962114 837064837 869808908 453494849 643459715 290426430 870191820 331160166 980740580 790644773 668583332 163834427 892395242 855871280 688693918 909306442 51012224 175426523 62463185 610856256 194125966 870028575 587406189 616124744 475442677 374145836 662087428 610440997 308883230 266324405 39539377 343265253 393055493 172466572 244376658 885306740 349443417 544957388 948524635 831136157 938393777 701904330 309058459 167642830 286677660 683286400 182396936 358927276 930151235 531951313 231866171 743444905 419916883 153017443 696333697 811634936 739535732 544977448 992682934 906303803 136252653 5534865 401261383 447682479 565813100 107598598 811999386 864710573 345942781 975346327 903602696 15035030 950835409 403898891 978442425 258145059 130660224 254182664 164310737 466821856 317654829 532686026 419658861 35111614 997602746 550425137 772218079 54019655 648029728 7073176 719468621 844956338 351603497 142293491 641954165 166641558 39267530 129747608 275864456 995228751 983732117 630744436 552108079 375316870 763040806 467910270 620469844 306774490 750194445 671715424 496576300 550167523 998210631 624975147 924570133 445645719 852624797 253739083 72238897 804021312 11611038 197358852 366564639 47362310 547812901 30667841 320444466 617170350 683371982 996256060 204993216 615356803 410701414 102556163 721948024 607715334 367812908 753837960 991405428 324913933 513934099 945909098 801007451 612135564 564094177 831168357 675884346 133477139 642960517 319710070 48108749 752827336 778882938 380502318 232807471 48129960 305512116 687984116 125046977 570851841 483236942 347788862 445294329 689494221 299044667 708599169 992554733 68985160 916401892 127265286 105137490 512393581 739047332 167736209 337020106 551607944 656428797 760182310 874897080 902805249 725384677 644373970 19487681 365740882 887057488 913673723 599620150 828472429 857355413 76097576 947087326 245915045 769368930 503716538 501139027 57916091 149416862 607440711 785655719 567490040 509942996 204261002 918181417 762260692 937042505 387940512 89586973 42437853 683677571 265073444 639964821 455394202 503735073 958291819 237594066 602615158 302109313 434051416 605223696 479584212 932240018 509407351 948068374 903656233 694890079 53396047 2029910 786319172 181140046 542675060 25297377 43419872 110443625 997084236 346566529 534888524 246031170 121394663 714004794 329948881 74972085 960516898 868581860 552759159 147737715 591235860 460999899 587830992 986168456 465170187 31537959 663469315 910017350 950304980 906395056 655240873 596220586 91812977 809387408 709500485 227594323 415747415 467666147 632212885 939661605 597898003 542750530 946067819 989586518 512783609 572691814 671476651 286005363 479020232 529795978 617539646 322703959 206643494 288780369 905739676 641650746 52312937 928205307 518404760 248366473 866553516 374773663 426473581 184060072 947723616 110193354 869027658 386787346 601035232 917434696 608044035 476587929 729086079 450959354 81118714 952327064 735562254 964680265 218266191 515890298 433308734 691123223 628620441 631913482 381019295 368784778 892566769 869288518 768189610 521256068 633512437 655148091 278183371 426722116 383712177 41262440 30820113 336525866 116965850 294752892 492792693 128386140 536699675 140301942 123427955 896087281 444662569 666407294 743785892 438163280 182537060 814235018 246085656 323907810 39361181 298280524 844948914 872767117 644880927 472606402 171846737 106409013 353217143 12069817 369765477 738511629 956755578 662816382 963992206 782516660 155712409 4942967 860418704 284141653 259124747 668472071 42808855 685250798 55030474 492313339 950585084 91846514 156701912 419184849 708712968 562261947 910167026 988704572 996948489 430346956 581453920 656127362 601457719 849045898 999028521 439883185 146632774 154978347 713561398 789998466 330473949 941178174 645632780 681607666 799648546 609515916 317430576 880006635 533556802 924531762 71176834 273571986 820309716 825268526 821599002 215168960 808800187 225448859 157151320 394276480 493603854 236440523 242401600 789164430 350644168 566698268 117209153 968344960 162349847 351346822 290894960 753743310 840969747 881753886 152581497 627402731 315758066 679147061 55067070 413058072 607599053 483082584 510614486 580187431 711950445 215684508 723234665 55920296 716079302 75626654 441077934 943351756 951232778 596363400 339232061 5363275 738510486 119046612 879505224 790722931 579554616 326128070 363421578 718853905 81456036 726107268 982843142 721544655 428909171 22919040 102366146 266424465 504955924 297499354 481945976 108460637 385075731 445494807 857951167 916178412 977769160 92920527 937950764 199990797 192552734 451624559 613840406 405996648 101202130 680935288 61099533 198740702 874194851 397958715 367553460 816211186 90861771 615805187 213618828 468630813 728987131 567724300 161378148 532441165 714497872 562028107 218937183 20872196 294103051 977650317 539884859 62444302 488171704 326470644 690788238 967310820 435990631 555799539 228530350 459588964 796345737 688137284 602474452 81003657 341142829 839665043 47654633 572891874 581693859 932773039 278789045 986654947 50235430 929803281 360230296 997571309 78640753 372680946 333014789 584549119 759177233 931218887 376646241 201529208 610923898 64889974 241142466 449794219 73086326 844022699 512695257 111571539 651090706 110869686 332264281 275894298 746867379 760629178 855923330 781789791 439498909 344030944 260567291 691407626 153057096 233383999 524159981 190538161 282930612 467970626 322199659 485040607 318539975 530504810 652251513 35937208 94146849 414978368 717449386 753125806 281963591 267473248 95921340 75959075 498199602 377168277 709149031 573309929 674509973 853518288 476675434 427261149 663242990 126997648 686140467 513083544 167120996 356108244 806947481 819276147 197027585 511786705 475033274 188663143 538675659 31705737 552961949 152993949 524850918 729726282 683984884 985915689 269568640 724322536 183733555 684102154 307763830 195556046 625552994 290634357 265371569 43511234 759315435 527927312 97415984 287583267 983751712 599693856 129371161 509197919 352611960 425548470 42720887 217466551 968439121 532057558 778082371 753753598 771853933 729415974 162891183 865580116 456057444 89474078 348982144 378975001 550852849 869966242 303034763 468827967 203483910 89777811 803911019 307656776 444073779 308318743 485709591 408557937 944046948 640530141 230606678 120093413 859057305 517813511 330911517 104594473 971130656 188047524 930629830 355201335 309462017 556937404 995966110 503287328 42054385 460057059 47316397 429210064 631296597 342987993 446211375 60761420 658523845 597903028 375404232 499371150 625220876 487206476 356367976 728360299 706647574 653794264 407750098 524072402 62322581 11945511 389664014 952856498 960708840 608279709 170439863 43470406 843147893 182396426 595053702 440154459 912270987 829659755 713070291 84846059 218142204 429025722 192983703 314148140 79223013 650281059 819719724 884702744 887756362 566561933 851721385 657168094 812318389 451630332 88191320 925820728 64358688 627368371 965012257 25704999 31068706 165836562 90797486 825737497 188952387 89421865 600951297 749487989 637187172 80012948 559071868 574008266 414308293 166024274 991838997 996998358 72615437 774699141 205289122 604371002 471511083 798174236 355275794 260500418 483489533 804034048 643334221 131799868 744204897 775177812 192114206 830947163 884451701 218725776 830727325 972935722 124734369 153475956 694584131 701336124 695990288 705275396 175692063 985453221 358769938 137636337 974665388 672617927 323058311 346144943 327414657 253246262 286629372 934873350 911104836 18069170 644104555 893504914 870720022 344741491 550360435 508015831 559905116 409747459 795008682 823315343 595955151 515259711 681258957 103582693 418258375 75315626 626445157 797336819 796921874 342049410 709705799 392144492 570223317 989289773 212226181 177756981 928277830 74831352 38452243 401030240 592138066 858625530 50916019 101825902 24164709 602896793 47563719 97954898 988990185 504977162 436414434 174719735 553447345 86535679 919143351 453783416 409682249 542307388 509092311 822860746 898459926 576383672 374320500 586346937 475076946 317778444 415376871 297468063 420706200 298827195 499357495 47155554 683870772 283012028 451805723 792011541 641297929 793163201 99163582 744352791 33220681 642308573 60999620 878155044 813936955 865458689 45851884 382326854 473366133 665268910 308064989 885335896 907249758 739849416 506551161 925164450 969141909 977314891 223031965 507856107 643204639 596562145 40712527 457980795 767606572 435503085 861859772 89829336 261730365 367338963 523226937 447339630 568643633 596560653 249597386 126214121 335206153 981367978 606220514 361558461 370476815 255455867 453794735 409826540 404008394 479700849 228726446 342906625 290767307 769016794 996069860 953194238 808729390 222912445 27382925 45385618 308111390 566004550 700716610 639767716 165298455 855745071 113959424 904624005 644414238 11166476 743734208 179824610 164392386 326164246 981758329 311454363 906020210 493183772 501565280 140008082 549398002 846878172 125144392 520777996 436193955 981942339 480920590 622265766 461709317 407669152 532289982 331510760 786957611 865407507 307778961 878188829 174510182 243553240 700577359 490352125 316829943 432094788 43441890 866015624 949820223 228244979 935231711 150965006 340533829 449165866 238771475 453125804 128380464 297651251 870900164 811845662 442410292 820545061 445434462 693084580 893700021 952720317 129751379 90133746 364420390 945231207 273762951 152895883 467870506 723938544 883680633 445344187 907553701 525730082 396254347 381545013 696252257 357699375 739394980 602210688 872685440 596518818 27507433 713776728 185874731 716625993 641609556 29733337 874229764 541851864 225033593 665817263 813968942 779170833 8298571 888672312 25482911 326005826 531031344 393805300 287665038 98852892 522766723 444547941 685432010 915821723 936674216 295227828 335823745 238062905 905432474 165145058 830763726 580576791 826868800 523416461 980716514 446876227 734891167 267473622 73386348 977427788 73979192 160864018 308506540 276977354 857004022 314031676 767175735 418807833 509572777 180263158 4661220 153672422 171098983 242285088 22788819 524635777 689235006 764653150 434316264 277622690 37306431 788432305 717254499 67222025 683245368 234227132 466622132 421933246 164018670 343525186 745182936 277069908 742821801 371228671 8901983 825103915 846652293 183886381 284437670 437693149 891763407 646172385 332480798 413994533 922150109 903575292 153686827 99578931 587769852 410012119 825902374 955439777 495959030 466001112 680320352 834370098 314551902 68447184 103942835 732345509 98785363 278293510 27207997 79916194 894273025 632237260 645957834 804717602 485413886 131459375 251550654 65994887 664295643 929759080 652774174 401662452 258625989 209435298 14551460 962330568 418062015 936465328 474371064 270710263 297508624 191582849 112457310 125553146 40425495 409120817 846817483 773485655 234746314 347173360 21000766 249050877 133979957 780889562 442168918 382289102 982997585 62728552 868044512 443852720 886356099 860132527 774937735 988034925 142498810 577549238 846793023 396231310 244354885 560674508 167845180 383368918 419103522 287639419 906709453 735314517 359956887 208853327 721997378 115897568 229402007 821184616 717508175 53428261 785652959 85631094 776247425 436938617 620007629 999801445 940335142 107039504 370039093 379450566 953723556 98890608 72278024 441184131 956708146 341347488 80026001 628210476 677207663 956038801 662041578 197189337 647951504 679784893 632752968 948619094 442103724 798316544 767987441 865541573 703582826 420028706 712551203 972904898 726201733 232600829 736057800 180873389 98187830 938050121 704135998 337573668 618417922 517072522 140100122 725540984 750925214 995225930 760311866 165085460 913162750 777287810 362717996 253697064 301854027 373013473 663814033 549770385 180703067 99529892 994184783 901724546 979658146 472704982 716437177 472282771 155127825 470477385 181652970 86397049 916661891 173956674 447543675 278577370 109896350 587710369 362443863 996111505 783241570 367684056 767788467 848249795 885545652 13798577 885091345 773082531 501971044 461489759 689279293 666162856 119389776 441612013 865718054 365396096 355443599 898853675 12275081 599647693 228920138 107150725 235511420 56821583 173647000 118497171 580971069 188518600 761795202 203412155 795604609 957575361 871531368 130214899 171290648 714164688 265269689 895152281 902939064 432611717 484174526 759690777 371190718 812492674 843237924 452633877 65204363 764432017 837760685 14786712 838579123 160984708 251197221 630478665 392448742 296325148 81447311 286783040 423177764 392385091 542949750 343667805 166217951 283141792 245296342 430214462 348775277 464499941 585930466 642676855 364134 581420840 959889040 162273525 788980576 785625834 915898822 971886406 176994191 305071612 712823664 882252626 838213489 639207570 141401511 376100811 752194513 859131325 604429112 866165052 431784475 483918918 253366774 784960036 306851650 579861375 274212350 156515588 856829296 572797083 310534956 395537294 331304422 640488668 195603929 837758652 370348667 693095134 488699301 311295700 88949241 43674979 484668498 354675749 617293114 182386591 347458516 745529949 513676638 9071132 740854434 571567383 289848537 67438962 657414422 217472255 523077462 388897646 754483830 471184855 194817030 34294284 915609449 60333084 78432381 736611442 846495613 287606099 693981032 533708808 548760607 493520684 446343639 474232760 260853398 739012970 35249446 560210521 24545211 508056129 965564694 150061192 497005664 186882469 860998191 919477059 397727981 238476664 947871065 208672875 573991012 185769163 462125867 508397687 39727054 797929192 152157112 737817195 593651258 134042592 256515223 117796409 20937301 722414962 680263307 574243563 158209547 45331567 523011224 772226386 478876538 527340625 132461319 313395502 543131179 187692207 689879081 861865028 759244215 784610413 799217928 525667300 32937326 303907645 287757178 152898424 817846670 80939628 80755083 739847302 296806186 241828936 817465873 378478146 198716531 100957558 723983739 928669172 344601733 729575449 111314943 881936697 456325070 41657857 369745248 79126247 992635020 269995177 314063508 8185875 13104072 177632294 742285220 300669583 545082365 198466646 164363076 628174408 875821867 385249392 491693916 230103868 86038614 516809356 79222097 272248315 223552040 589248730 102107217 482408668 232610503 90507310 478393015 402745782 555543116 132842326 2509743 305973285 978216321 549688127 518676994 600531301 443775651 726437833 224258347 655997248 649323324 449303980 783275489 758929770 535883639 28204613 251708515 947423277 396407765 239757134 249641769 694465105 399381907 297462391 13803100 690299252 655822754 468020568 538509042 252122981 344277712 913304827 928261545 233650580 664980943 82151442 10653877 52220146 895390664 316333798 237079912 140267837 987932564 258275306 581839077 991959170 316788438 482589611 221975015 639381713 832769192 926552339 793650887 26343523 82493129 447605420 141552052 809558317 370859268 883267396 771588569 847102954 485204891 368530385 474110707 218594484 526049519 776460297 949899 261731613 409399342 182785007 128316472 80900052 865960835 506496819 465933769 923311484 374990411 295005822 400455162 766224196 593412421 91663429 892868322 169913014 499425268 308490123 640513636 278069148 821762091 540183972 92669071 65294837 230536282 824571937 923333667 466608233 124394612 580594827 304085703 344201284 183292460 109119521 73355012 220855153 781164393 212809772 5619230 279044629 713482584 932345237 319993249 245464816 92704678 420412395 752478927 546335674 423156179 108700566 590809277 200347946 436271021 528095528 8951041 72794026 697213830 65648090 629655159 394809244 6023621 491085839 787249626 152950429 125683163 799553312 756162851 639795557 235323462 839341174 333906704 385257656 196054770 825926322 196776570 31692903 928963079 26044883 281967974 84507617 388194904 464884982 721103428 552409546 210181356 908090702 942249043 841157634 951849240 449760859 748216776 578620007 316866557 357071596 241777199 532307700 203985678 79284522 668582232 517354396 726836365 291802821 437591089 242295787 785299759 332816591 318817119 366689466 946190337 635944273 918296148 828625101 928408908 185275358 231489306 216981469 970732528 601117117 752653077 724506938 199562853 450523489 16043662 696890909 606956616 450756657 195781908 893348650 635522355 732196402 411366407 475085866 874214021 369861914 267809704 400630992 115580601 799020459 802221594 305275657 764919673 143693993 312608124 37358179 613908861 222485740 404180465 856375661 614144129 987385961 114729913 173609302 734187712 677102197 285928026 170386944 818732984 320941722 494750768 656937539 660887560 391106056 739668141 642599022 774576536 242959940 926952561 846157605 685692997 535192454 504236707 448698664 908419766 948335556 333934096 351626139 953231702 846894750 138237363 67563735 539080868 499124065 885020009 883370669 568666567 985058117 208467664 782107344 591136676 157784784 449634937 641247935 500131727 370363755 926578677 265107168 261050740 16463688 112597308 752050818 17401463 565541762 608744129 25259478 999926238 516386045 538426286 694416124 93452303 673691475 81900252 593377596 328771933 101479390 246504569 214822991 484935208 896711072 324570515 37925305 391505018 809689494 356639842 320644402 83575893 333370515 47317781 536115676 196569527 574183852 842576262 404175746 377112716 592358198 37184095 993105103 699585978 356084311 41462681 540864987 770271413 428867693 788379778 709394756 97262876 281998431 696220270 791772297 429566752 779571199 559090165 880628705 138152458 461763571 880196614 91262674 791307169 704799677 644403904 996952207 236616688 855052825 396431851 187714374 947194391 389389092 270137440 932719999 794900189 332766323 537351058 395537384 93745003 844017487 914709477 150441744 947522711 306309396 583379757 94570228 788599098 351477514 469856712 9799243 449397415 491933596 86800461 977535458 290013957 951673209 311222174 469060013 224116177 710022907 201457279 414279638 878013656 726215859 896365100 109338246 593147004 207413077 743314923 159975326 177140162 452867732 430219142 839551810 557178635 23764206 730602412 797361168 831832682 150929143 111941755 860736668 867287588 804321568 586892520 997777977 52571232 655940165 65215177 189311610 27057157 359060975 568177087 378580945 395530135 523669470 902068612 501852537 986111926 832710393 930805390 422818487 13697023 898741321 159158638 740657128 900167371 332683721 980661575 504967237 362479598 956549873 209851362 766706985 422865987 400783576 824242317 409363062 878417477 733198792 105348134 273804773 204469739 139161223 419429285 446994802 304396336 179976326 209706969 283653229 162886474 523658943 206329877 780885865 273815697 285865882 26128102 354338209 870209361 506133718 891918935 889826835 932035130 590585785 117854132 703506243 135181904 732748622 661847457 198307346 295733643 201849965 469098099 61088396 943691580 767653981 34998478 862624832 751720100 340174765 710911896 313341625 367179856 212527266 970139275 201419248 975117442 848314629 206622516 557290952 921414794 236082547 107462990 797132731 727144369 907415469 623351292 312488343 826239110 769341111 312918459 912081025 80460516 821177806 256622915 80281416 993722490 259090646 124165951 914285035 659213844 120476638 337363010 913062913 188555114 515673904 655128146 891458506 437020781 186653876 783028259 895958761 422869011 9660458 670220038 113945203 302070362 733207046 841827963 945237936 731658105 216965476 532325317 758705253 851604348 161329134 702085650 358655534 212513749 307366957 436147632 872928769 489902389 778357169 75804862 399876299 600098689 87366417 722858127 983682609 417822552 917679181 431811160 370051235 332364950 632442350 273476843 125679262 122176540 502713590 885300694 330491315 385818272 675177117 20825259 347720916 495859974 43078905 295229443 309093186 74827282 109634198 687199723 976782426 667597321 797517716 910959115 956874365 64127894 469982045 317889914 465230995 822691213 263045611 932705836 175266127 895758992 171579127 123146236 415910418 531422519 728737333 244178033 676417999 939091643 833138357 801418065 821500849 126898338 191690340 922571591 969698720 594048305 600164640 333101881 802822725 735658316 333791352 913321382 302360657 19521059 78272096 660543394 455175800 357092481 840363841 93899680 681402308 648100106 978822425 832799567 956675011 864353514 416134040 360563794 427518385 392215281 719292162 52372018 155322821 446219211 869297718 206805488 949916621 399287511 664813195 41644060 111244724 311060453 270037699 784249320 371724284 49250487 845568517 504621024 366527673 748757616 644364465 457142690 901770721 971225932 692384897 808351628 152132907 829014494 680827846 662330759 358390759 503661674 268272005 968636598 884724515 124609749 4722334 76016735 694567277 366018645 660599749 150362035 659317396 608629625 453654284 114440573 906830050 94442287 395923914 804745699 6077910 390535424 486057023 138597126 713466655 525198040 658799333 522821197 503392548 979561106 860712078 18594905 851217453 675451250 814303469 267985120 447347812 344989802 634132810 979975318 807985646 308902317 70054104 332610106 93962698 964612000 466533504 620263577 28587869 894946449 442646701 977673803 220839107 71876828 695268991 15838809 561167046 887210249 677390378 54793840 384334378 454754437 276457911 939360693 271783270 772888259 412716241 377577305 372993649 614102181 745197450 457927182 192500935 851144883 351999405 624748209 21307888 139570942 621442299 586735050 950350596 309752140 778227717 166395179 954119763 169812230 572556247 955021600 2282782 701170713 113511981 700629743 282436079 586926532 97926657 213036293 414729099 184329490 466928643 697933387 209951801 222059393 476634043 290430156 331816600 390729239 979355772 168042837 983439728 229652319 814562719 41026663 575122358 124684683 879591146 924927798 836791364 200207616 907005470 343743027 43108005 827896645 721331302 187068107 191696067 876124532 856292531 42204930 644563797 529634454 306841209 194951207 157361513 370653368 599399684 72325990 27885056 160153971 791547229 69859153 321594266 364613869 772806878 390209549 84283910 511608558 996407095 419260558 713309696 924368141 799410006 591394397 874895193 678391970 458952172 332411157 314000959 306643592 563646669 374070144 128588022 381302806 864376645 61741728 50947894 562410965 20918804 578266755 607467805 801658933 542279819 796142489 992500402 675385986 834663449 671892736 537018375 716470413 888817483 118779745 51254305 405354042 539008942 464890776 402332443 765736157 44411042 174145508 141254047 667177667 16543189 409394331 523443473 377644579 43114305 702148295 440882651 218466206 629330987 916775615 955056307 527726316 53134287 194377942 456816122 561944452 844172597 357020956 989786010 619709159 79254341 609679007 86898514 589393729 942214214 397967934 984314607 150106452 191739361 703512010 72546560 546928165 245347302 962389017 447498699 907585128 731456687 395049234 698656604 291177592 667027475 289730690 942400044 674935761 36388852 700831167 604796326 949356782 156602884 532783602 808645257 622902278 858150444 395835403 628032927 457780756 96537363 436912154 148831685 625714694 483787743 350485680 923127054 866521469 190635683 286712452 896612664 935348525 986271333 423182756 18199778 423206706 137500932 634676240 251945941 759346917 200276818 39142818 702633531 262993629 564409953 909607455 174933421 171824775 483510140 887851890 472675169 916386445 48373136 670465512 729397119 808902135 126260521 165186110 154819949 166870243 436917237 695845821 638113457 305184915 753411466 425632542 997197386 289015210 487795844 654618577 985445233 58163036 589636975 687326542 675065750 862762838 355095100 992576647 325902568 738264651 618453863 221167767 847429400 772318926 891727108 770775315 597753693 507051449 355724052 301750949 300254504 925957607 54612091 517986286 954630361 149798583 512964340 738162949 501108043 843992997 558866456 808121051 174817408 809083505 174635157 433018378 59640393 584308458 443096422 383354237 277819496 490144980 944498461 92018600 105357466 218984033 89936653 344598362 55456482 690180862 910692568 724655261 175062812 177209208 260318461 109334304 273746794 660304791 993909544 257155427 45901237 807568919 560411893 515232082 21547914 320784328 733496742 807370976 454435587 104017907 331883179 917313036 159213580 732684053 471087112 531051099 42892208 3120892 889507787 56601973 733548243 522656661 758715805 747930436 588775694 996022791 915301815 878162204 970356485 138671072 694786556 265060396 782054358 378282543 991620153 684836550 50411465 979737646 843038597 236328500 350471283 666411371 886021840 175499988 695193247 88107132 259099023 240023129 306044973 471874847 655114719 879320841 636928759 478487837 34201637 9573239 605679489 19088288 670263035 692045125 149579691 346548475 901682972 156903917 242690700 420188272 785149692 489799966 14401678 87201377 400817354 64739554 197868291 678919494 221017894 375109886 383186336 54909852 13770861 412844426 467121602 236280917 703104278 185646752 662122904 553498996 883582390 842306308 99475066 720044936 517458641 445675561 454328643 35717830 842523384 252786055 778144830 150227554 660017117 595659097 810258363 615909602 929854410 646364128 384300885 921439624 11696884 934781429 838517447 803418498 333036101 168935251 885419614 454062940 710396402 292725897 523391055 136624806 505821854 226164158 989705211 523821926 204750035 807609969 377284270 859518770 469949363 744594675 456407289 207209093 829174961 446705333 800099250 587000046 918944007 31285758 213830932 996519816 634068246 222503913 522983934 380764415 549848174 565226908 436114343 63970214 604346448 152145687 629087445 617370988 406476909 196299095 528263697 56748314 347069133 487909832 217340905 909898237 737509940 160330544 756635881 11266968 486574595 238471933 805623237 52848976 296185993 88509560 554795299 218998105 636687666 395948977 13481527 101642547 179227036 631215672 838678330 694849522 693977879 161063348 894287476 773531650 367664189 831483349 861053058 291928630 223242959 490747921 554466662 404898683 736504990 440022566 938523958 183356764 883058247 362710250 989050339 181525296 904526278 15157928 605095102 631927560 430974551 921220984 34672859 187085301 326681431 853463034 256513591 151974099 379910781 723808360 325550105 222373415 972061344 565732433 123382113 367702428 720373621 786523527 421478411 600292855 481150283 680539273 108093680 840360281 480323208 354173078 368089113 214213026 851461565 859645556 64728215 348366065 133081527 381002652 346749428 235244307 663265221 451053441 452138280 790314962 74461132 152850460 329592773 445133215 488701686 640444814 384897451 883012677 778964146 729309640 182665240 355501264 938583331 9997945 455936109 630875361 305278378 942889047 395633982 884183440 564213605 391657375 35312189 634932585 910054398 172902227 27326143 89048816 878296241 326837137 271082952 845448147 45131631 406845921 596332981 104597480 834081780 637242132 934764708 402727812 835617190 160742749 61866689 572966565 294917830 787524952 807327879 925071310 800812153 218606649 241795333 5281172 709622041 268103100 910990400 784234922 273133572 446635770 134241031 624817996 87690401 531704401 660799789 257454762 616840770 493890120 544590229 741104458 500296125 445224009 797450582 337221638 216724784 166942321 121740067 392061987 740287649 119077290 639690537 432874598 721608714 336970872 464770252 779251629 536971381 933196817 85857485 946799252 235330035 239929322 682123577 124618594 11002658 38279082 910953603 369992435 837341402 677040497 717216467 767865124 542367711 233856942 299208754 367307430 950704267 581280502 262751218 548693142 385965006 777329240 630384671 64703538 361449150 143736267 530085938 909645626 852516540 73714253 521086937 551435586 405768110 343015730 575670592 729132070 305184321 229914236 986015514 351890492 92990236 801823409 533759076 317390779 853571565 995215009 291689311 911890504 718082457 174273171 990192779 616242705 116237002 183268171 390800098 835199215 294855508 856803278 450575747 267667891 52550538 539081457 471395429 466477586 685763893 307046971 472663692 124363407 356706662 590681772 575719532 641591943 11373777 493710081 389968723 483568217 918235582 268113957 46134059 239065992 515993657 630963105 508973920 415570746 158938575 919834983 97930367 306915998 415903075 269203716 548974343 204990198 477644299 326107058 60324783 16949428 804766749 306939706 935207410 413807868 873249406 765185387 514567184 633756551 916005818 533804123 725980442 54061359 445200061 129564717 999584578 72476578 77064003 640236276 529819885 21706682 135015687 661363085 107027680 850782933 203752340 166550544 568497519 742852001 95684540 841043786 109298664 859663528 850554845 536647460 419342780 981167442 496767304 334384486 247496187 422911489 381198862 447463030 968624781 364424404 898734258 685749492 766836387 416413778 15188352 384433472 547483907 153699394 808937595 581309079 988427765 766556031 759892249 333404821 753127173 895167528 44326188 453811371 937367118 487560192 197440084 986977914 375000621 116820469 852447996 546926045 697723497 814602657 764641783 514882935 587586057 299473360 239827156 571085516 939543851 990603467 210078066 369912457 44892553 203695756 12914013 332139398 158674359 457293746 728495165 89460838 53832006 168506919 60588430 556491976 189623430 983033321 696330404 332658091 890970507 551817168 966279402 263916129 725632749 67953125 921954974 51426127 550074338 716624077 556477172 436145881 791867931 926982724 303406063 301476842 429202184 341551139 576395336 465521634 62021583 812930356 483684892 173134385 306012245 970308767 84698493 771040315 249418861 101491191 990494375 190066030 729139413 116401360 691466335 371652716 407598439 981163741 774370955 328008914 837496504 789652614 86976170 881100117 352134750 733349780 894189196 743032204 423620931 283559629 509848833 727221840 168034466 340699576 89008318 930051245 951539745 20779758 210117931 346228633 135164304 970233926 789195042 801228207 87407508 890534095 152910266 304564052 856027738 312107910 887951154 351366400 653775986 957483810 669676867 602447846 161420301 405317623 13316105 932520502 644774488 970534995 872888705 130754053 102777564 732479866 107513408 881568903 141282917 540427213 768287513 127778442 805863562 658528514 994613368 640940831 658385956 450953007 660489876 107124704 911617105 847940618 362509181 688729703 778712285 178543866 319260663 212585103 401144107 869571832 867191600 909554246 162947974 949610430 993532506 647509617 491563777 334768124 612399670 520150423 656060088 265335854 379757928 387953311 850334452 447536200 591487312 302888855 925184858 26793112 945532422 171712857 700951529 83464943 720105878 379579198 437393540 840171743 241152951 689593893 674491218 626083241 399413794 313682671 673503290 591594144 440393813 457544195 278552909 386775648 612995060 139399826 91533081 731455244 739237666 593482575 862940875 776953144 207237332 866152212 248861597 951975432 423370788 337191196 364269334 523640603 913724611 795209167 351119574 159516784 984360523 13138179 663047200 87918819 380745271 494580462 62883257 839452619 330920274 104922403 77060845 429383838 192324140 83131153 113245774 104882044 696551287 957240031 356057735 163636424 909049979 991223347 312708850 810197372 355910942 80445773 259414455 728915457 958977408 529063124 145622390 106227077 203172245 752488822 589012211 619373965 913792159 821209164 360816659 351363463 896719758 940419489 939142505 819093453 775121235 618725457 539348013 636267874 812670141 313264815 914733454 959311421 965913979 240533784 147215433 155222572 686676523 648558133 251346227 851600458 572002992 194632411 89678907 427872955 127246552 581701368 125552953 251461196 346950321 109577932 450782890 821767325 754674509 985000148 905320294 979529408 632626732 535992077 315378710 721839554 442916743 924479739 346617534 664331644 591877853 755338513 628132037 963877431 793858174 306321975 206337899 229890327 176641779 517560245 521225108 60692203 84274625 275118306 290658391 355972142 980033443 905314469 806267213 197340575 213049280 681553826 115031668 490598837 656520367 858350616 206743681 287390343 290173519 354871398 574162757 815767967 514209963 786905798 22450372 324087972 667638816 572701083 958643864 675414790 583541855 969707462 256369762 783538230 449264024 236095215 322155105 202868343 291976545 434307249 737854693 539775935 749644142 899794091 173332276 997572060 698139561 358516833 786216999 346408154 277951183 228172200 984658734 97286864 697169725 477863050 585067690 339928990 842913054 349573116 726695391 287564335 595136108 868355058 670418503 68696201 594412995 321565894 862890538 428721148 89902143 126478892 86406699 162061379 291354477 420520642 485937088 739422540 866935537 42880846 625417159 770508756 485814433 16653801 134942950 118453499 544549721 105080758 143401648 478186416 373429505 841542172 416267508 977569243 180018344 963546115 926225633 39543527 356296854 432176905 400868652 363711060 743462485 967295766 559292992 18406440 265735094 152947009 467197246 1542618 262034892 199338424 404371705 299796117 74729429 400829667 918576365 626270850 928849299 455519315 206524091 913979170 941034229 655604964 510989214 625585743 22810171 772847063 196932756 290241770 615982408 302648366 508559123 485188136 424857772 890252794 283405352 50363135 910167001 840533149 324017721 115799842 119858343 724643067 629020820 136698634 563452394 284989602 819777838 5797567 936772929 337289635 946263445 296875202 684237850 849547725 102114370 528606852 37906430 937603484 369692421 116257637 820956278 457867156 737360129 419033175 362756387 388551124 895555155 906635642 61334873 65585252 218058355 815267449 514042055 38907674 169348906 210202100 476320490 64468626 834611601 853473852 143710842 562172285 830934572 700130171 858040135 7839293 669863667 311054986 68686020 695457872 84250598 622061638 363439048 503440442 420005645 769577646 161668797 871381941 610076285 871522332 338343679 423822656 681134076 740837503 313389576 138023929 510508425 301880758 111314345 527854848 907011581 162054648 272541977 8164835 804836406 524806960 56970289 377780817 850287272 970499588 39258097 717103861 872793846 506095533 177912099 445443082 508068945 397832159 56175503 778739323 150467278 762021381 298785327 944386176 193998470 355896257 451782201 331309740 807927458 235577802 138036542 985063652 619932955 694719338 430379464 217609346 61105992 25516937 839421995 517312967 724142965 817026151 644171357 522500845 179386580 485291356 122792764 697680429 906323473 839910245 903451824 739023874 214735331 511330043 340872817 273646321 257950394 978385225 656630385 364145651 276069219 673069371 336957858 454764082 464669255 96745817 349911253 206378810 735936119 274898731 322035734 958924296 661429298 534511186 827151040 769505431 878989603 683857041 711913261 357460088 135130520 901512181 242401596 590585994 678916956 673544897 492608951 375278030 617068387 693279069 155517943 86189959 169813021 662632033 590263431 334425625 144923519 125059121 587938587 823480889 302742036 9269880 866286575 7118349 451075616 733370163 840747814 855793294 982594698 762606534 96750581 982038196 118831133 434282180 290730968 373402389 42133339 965749635 251516015 289832855 861134747 743619241 799635429 318457308 194322402 792100690 191452296 41522443 333558834 369072790 654331277 624557839 700803087 164131334 986679221 505370098 439619094 484876060 926801997 279493459 109362722 164115053 18766139 779949523 820932483 804640409 625996236 993761268 64871089 448336642 392211112 925533251 806064594 543565916 309268239 595965681 965379271 339090810 684041588 635102195 724152697 226201283 987447483 845703522 763732330 876368887 680971361 476059111 641711289 288983526 855670530 732944905 657354426 144168068 5778531 306859248 682922174 454714533 476803146 58053539 600060238 126841487 493235973 791574656 22578668 246851126 884186836 697959832 914812255 581702575 464662462 32724426 882433841 637392715 900579913 457767211 807441822 100918337 985068105 344409037 159238395 507004861 438045156 9699777 406887329 369575330 914770096 702234190 177031604 394325929 770716464 473492210 165634271 105145056 748973563 829914406 727297647 981977466 581918199 568791639 253476840 784427330 779448056 801290720 870875170 494339662 29715734 98394260 799326837 48461391 414510334 394321919 509282065 703937059 31733720 82006481 93520142 175687217 300704172 188322412 562581668 143969111 867578100 814004384 865197497 864532220 957991156 325505978 7161283 187455978 412722139 226995060 989261804 806426723 537717999 270080802 308507273 747285025 817205203 554810430 488717636 877526977 453995181 807191 693724758 894281808 104368952 50449930 385147532 918797242 592365074 108316117 696071165 294923595 34686249 227568506 85365660 175167922 247217199 698587057 480218284 518092780 524787415 864201558 393426346 801073992 53093497 238765088 522114883 151507370 58078193 937137702 332084864 413989420 627962936 457697536 312453280 973160050 81468978 963847193 535628098 119435632 149378091 62648404 916673326 583143563 305554889 737333754 419413387 373918391 606693764 274443971 588913078 670931718 996676105 166357893 10602222 528689998 399426488 901984939 140283912 545419068 936974000 582678370 966449685 718721052 332917673 470372913 617957450 453761278 135441902 105608146 882720414 900128336 429993941 4588022 520212127 730049543 144482265 983289636 857316373 724612417 544005359 976167437 737372018 69005078 432685276 531146155 535764926 899858529 86923247 282303620 556842250 206908092 378111031 286558007 902387790 549224695 620505594 546342609 274064273 323512362 148787594 103519558 687628834 696480915 762752194 984739744 297843289 483608381 680678771 177940773 988401977 646892943 468000318 88274805 229610909 731995572 303440562 395965302 54044767 715873196 885418688 36887951 338540033 408452525 784955590 303617065 803777113 912583805 830706311 672955755 252970316 408589584 32693680 423973834 908447982 648250802 358561761 270343285 804545431 1732803 995486373 67391130 87650336 353283027 800320118 102613310 441727153 47199736 113044510 452778001 744001469 807502006 868703319 598592539 35405616 470801806 885870899 201264944 406094174 925955396 328290719 828016488 21793443 564625412 238538380 156057034 546588949 982309568 22509832 319704993 540894670 121621014 392395400 991819576 173209266 668646699 312666725 34911884 679134633 159666737 130440531 73573805 43398979 604974103 490498295 735291481 410587950 868117534 277791743 537941359 654447898 729825823 125643303 55196723 56386987 773087968 884144816 472633767 109040425 604503401 120848627 535412432 46246359 558757494 957125146 916378033 541433480 407281959 323656934 854557778 258862288 93624857 651927746 258011439 536465541 313137087 342977681 682099040 114781276 623399063 164489860 524567569 491171789 533031003 646792569 299538391 928784730 927624284 429239488 126729519 51353634 553345957 181116778 504222669 365064123 891098866 237274468 429028636 295896870 803809195 507443403 311182761 803682665 491788769 1112500 356447136 643212638 452100201 499387740 210707187 113308015 921982328 237633405 31792479 702066807 615698826 894463734 724177680 901894274 842450805 356478495 950157247 598222517 346011743 402790013 997119022 431450382 304002976 176068852 727454543 547437378 377835 258719082 96885322 720343187 872529849 970608322 922888918 281107453 825565599 527814847 735950629 717241372 82136242 721921855 466216440 653230855 848310970 264811284 95137575 555953292 25859695 714659048 448323689 499569795 926153639 907771418 474103478 749765456 820192791 930890407 301197198 565988328 458257301 74456052 687436983 886237569 271727535 864706087 112448887 207125291 951533776 227994507 603127581 553295596 987408549 52031681 510646907 118573301 629344319 343937108 857235266 527520323 952250934 947557312 653248458 598952253 27393518 88940558 100752857 595958374 926046714 601035135 344759203 898720628 490150431 257204109 192539288 529524166 315576809 295514480 717131562 178132488 451940612 721509548 667492836 735618662 181906379 827862119 124518448 232285847 723124960 520225385 177761909 450568792 272902708 854269801 929734975 611782553 408437727 344044593 833897736 944998947 104948455 535464717 30002057 832984709 588464381 142937289 506366583 343534535 741683228 734048895 502779080 563796894 609050693 972714262 764561049 71323279 69949514 10224159 323827416 955564862 493302597 322381198 930895340 88521617 905802252 118703411 948600709 856357250 584854220 441652175 517494851 298171551 960474334 350601539 539626431 853021464 442344585 435478791 102615630 454391211 609738337 33336525 477475381 283720194 999141270 289039637 453558959 649835199 869852650 923908286 339626810 732305785 750742138 763374751 230395473 421198913 106431289 242670293 893522918 268001352 401508391 296922216 699674328 762268526 8465043 413172204 128451032 560174630 899003924 892311136 65244651 285815041 12655355 959225895 872231521 964166014 452635891 431882901 320948434 95432701 499368719 504623445 782792987 433392344 983286151 436205245 224491862 95060838 860694134 780605812 675142391 753055064 197913402 378667051 387154225 45752741 497353257 470740021 765592587 8838137 611753030 216869175 413140956 728623648 113885901 514554886 148730816 919619601 497418525 184911537 49372797 504568104 953577315 860214082 716973690 938093309 555939159 67862624 766222347 832232154 729668722 625533402 921203719 312218082 852321151 33794648 858235857 584109236 203951785 77778030 518337193 656885031 193408036 882525686 843894062 995805130 541683542 105932099 295486912 310029831 88911191 857087658 715964309 869062341 360160662 292952133 183604240 786822343 453771402 629360858 634258619 389628646 662889522 282202160 66453070 219815694 573344002 588936679 968168938 231884280 532810146 543945188 633525398 36012778 423567885 969177042 922368193 2177073 215661498 91355643 410549997 947578576 30189932 853783131 938621467 537453613 924277592 630608516 266068770 918961146 813259712 829109068 447323900 613129891 315171333 107318912 763897550 927165625 128316454 119399337 920867447 162843102 213940457 343155024 258426504 8413188 634177628 651346118 332787229 156292828 188200177 616179771 206360002 544608319 364330099 253140192 696316026 127822248 945576937 812638933 668497667 381617751 678626070 237715273 24937991 656101152 885375127 560916470 128887956 397933912 652100214 870234778 60660956 715546587 828733320 297055260 64140645 166149866 564144693 580731904 915833271 424734716 251908646 915319537 622981937 756184998 661600889 990947402 500326902 574106231 955379814 148279735 121310986 672225710 168453703 383779709 693259845 579169540 327537279 579854321 671721877 149636761 625134463 773948096 574781079 852535126 445356451 965896181 718605124 279127953 388727841 613397291 889476081 426304711 106943212 919631088 969378150 825510271 137715411 553138062 208005173 602928780 10714233 206468393 83229828 435120489 359908718 470396553 750535205 164415473 793039017 133672391 350051301 469309457 439136985 963090788 445790772 352463798 174216236 986207288 430678037 622928025 74657622 540411384 615670836 843317671 526343158 559064280 143684632 26441202 180797430 600888898 183255603 146357767 102937334 131250702 950089338 646772100 918881956 160779998 695424893 162746099 363763258 563563854 632689859 237732101 546492036 62526542 993143933 909632908 666372260 548445857 18389953 305129380 451118546 23949278 386855514 830450075 118030923 879122886 873081394 627759007 396679739 368114084 70352138 542119494 384929567 137860586 430806551 522686904 922856954 114368143 276888907 3366935 932629897 573464702 216045029 459525250 547987992 220067621 566902757 902428779 518493339 477740410 72845924 684033994 136361295 30574283 283159710 299175434 585182504 80364343 891246082 299417637 772374754 577179990 717233525 506680522 123838832 930940793 216003585 911092168 996493610 188400857 241969376 418210915 976319262 895797568 421306851 916633926 367567095 532824335 476689976 959389744 841045000 460646100 491082608 959247556 653142700 888510183 980804366 280316311 543888535 66011356 524542548 188956409 257211509 398997311 127313120 385880969 274235157 673470422 635479412 401371957 754857793 315654999 594528690 146243621 787734454 904459384 642953406 364819523 829698448 178063982 256513655 541913903 915395953 226813460 929322040 958003551 241973554 104799315 823062923 501404311 989866906 572320619 118098249 266494782 143694675 720145067 833104475 930887574 965808952 258926868 799859273 583947182 485974410 594386015 109041123 611281732 914927906 696837253 33674824 8200755 200877302 177807031 404941501 478359111 333713880 277102810 220794658 731511047 304501866 131285185 762484230 498646377 914420558 620182041 40491157 197703688 813802929 807890806 516227739 938626242 478412785 762059302 609452466 466253562 448132145 636996878 452229715 818227007 745887994 212612105 375462525 749354045 383244652 367974033 806179212 308810712 994079843 592511257 797666600 834249772 373988034 257148658 685150729 320209695 815356732 861065113 392489699 70726256 510162055 352409387 147030138 979731903 434497684 321792773 785937320 243447366 281168889 953246971 433073145 242959174 350943383 305905346 530076772 666958953 405235245 127691838 936836033 482446367 747807249 142365391 678584599 615405859 149125997 755177271 110635169 496194063 462804660 852847170 324923710 319491076 683477280 580249294 82725312 448715172 326821922 305459953 5936988 338392249 53720367 289761508 115825588 186905895 961735997 951494237 121557225 341132753 512420574 971510779 41601010 616601795 858921281 208657268 364217179 70026115 434593970 700410952 293732774 724758965 950403595 395889977 873686007 598137259 382211246 859435833 803900010 887719924 494214740 224861532 657636871 236530693 385033902 598096950 973667811 717948879 997241515 196493039 807412859 956441 245623880 219764651 704668285 949707921 707779656 441895854 118195486 930219410 874474404 953373588 86309717 632334596 91100901 61801904 103516092 136142977 35232946 369662550 953461321 763965484 872581761 453320914 941393309 47563270 267627075 525181842 331617802 12755329 429679972 914787097 54108204 674839809 578397009 938065831 587550460 556684299 491087227 384566749 646083699 796211198 970097662 430396116 620903726 934951744 178302402 741960598 43483178 89089854 866932510 774187378 431404290 804114990 466386285 33413156 9272917 42756474 621653517 127119403 902210710 761888628 97054992 984090166 108073877 820634234 631623232 725966030 847213180 437574592 636727132 661254040 266897974 292472011 403080435 503860833 832052649 371370487 490032434 366577617 861768527 101954046 405824357 495143880 844911073 209428361 505087763 560708289 617886115 310802906 319488907 181518447 72068230 802487228 66711313 679188087 276242865 884370077 483127962 609353982 323799438 172091738 778987924 439461529 195107030 821768559 512072485 977330781 410812074 712517456 506360388 143544875 884610495 697299273 396872015 987398375 545977182 679630833 504218035 652851837 554997007 921081588 383447490 797324417 766402162 774200458 93527792 817850877 83302713 89100257 982499392 692822214 320905067 853815047 963910416 817811402 593247762 145335883 606971985 318463321 676001587 510092869 117765247 274074711 311587743 239933764 537690354 803532103 870540569 793508766 369734962 901670035 598988043 561304037 856472527 494634016 459703598 859419574 748370617 851495829 918034254 351125676 239891174 564597646 39897826 936110791 340884003 60775557 337842604 28926125 67166682 63675686 699161097 280938744 120195907 842635483 540769593 456883332 796682052 281560562 334757927 742710192 121865962 673847310 314054071 18450916 602733894 98546639 483919 276898549 981044043 832906003 191771130 950541446 761341006 515426230 161585267 194248877 369599323 562670033 418732411 32272555 76480423 583598525 200240533 347255820 865921313 529602927 457439134 740737309 530632719 196412558 307858093 930735140 85704669 278596375 635093937 606041624 749141123 573460909 417764059 284036043 432045047 70619758 103855034 645987779 3634195 914316598 822331762 356598375 66555148 578714582 289340099 224359833 742094558 565150164 716526597 262380681 59312237 962220235 177170777 95198649 877047159 345720048 1848397 258397442 379250602 387470762 977659759 527184325 715774608 421249831 597616075 655267371 683934829 789099425 37549736 176200897 763933890 18095910 705073622 938878975 218101448 362784556 824836646 592293001 145402034 158052759 155139907 771166388 791873749 430263285 154609624 669549562 827704894 579788757 700657063 795798636 641654518 130780983 357654420 612969052 664550320 923777845 471558546 163703950 285025045 576854859 434922620 960000345 266503396 107471321 598532066 43303320 780653449 190225898 916499489 21860674 551526398 570004398 76107058 682671985 264719464 5524974 155777010 448747554 581997110 372156293 862199806 769131469 394588196 783084874 881144452 735973165 490693294 1685148 235768899 188143573 820573577 9833336 432946982 990252588 493682620 935208721 327255998 519175387 919592980 224679876 487430940 595959737 332967688 238988395 881081408 425406070 26317582 850062333 972080228 507319407 356786738 854728488 625837478 868333778 75496002 550356456 301697559 843822422 112526980 440617914 754156165 879731413 827356532 150342501 294530102 392333527 500691332 923169788 807597033 193855389 957543680 755318458 601194592 397679397 718882628 788238931 479681996 310076575 866854101 488322149 802166849 94537419 156669019 535554785 349643297 231717658 234610739 189534796 804136621 233765844 68684362 754758967 359098001 490891460 433999165 134184382 98626343 479576589 103333473 934823076 745211004 904022645 726835790 139688616 428477930 491738966 664744074 496509844 873342402 752142135 801543364 537141563 518515823 103085069 55920411 969885746 399657138 914701127 970060692 553316606 558492679 314114599 95679029 349275678 464507096 694584340 138333711 64339970 725023132 85818623 708636771 873038660 31547834 456232911 967091089 239182768 417681362 545903123 706954703 42610761 158110416 603415908 620682171 621851834 400041176 942745259 198277078 368326152 751787925 718075789 56709166 9818759 585147329 134076291 41426886 758459163 164470966 825833788 567661633 832068185 340869324 791477571 889936378 768742980 613323398 37237097 932547212 144979658 889079412 402722710 516205928 692783435 493793031 846164362 411930794 712961527 19682215 133075593 201658832 990671892 772057856 200118835 772128811 668878548 121548438 57358376 784250504 432160550 818688403 730507188 826692712 90326302 290109412 931843125 524907831 308962873 734680411 217353853 125425350 91834125 948829824 609363497 238761568 118137379 215165847 854446020 5976646 721509995 50613629 81785943 620735286 996821798 852546247 929602685 429870900 995271537 855871257 114189880 607366803 217897388 447938843 499908888 122861322 578799115 265528884 185520506 588781467 950840301 655365971 974031315 546165033 190874645 839382078 481369914 755256188 276864306 439049437 529946359 993329127 461095746 943660879 476222840 609546427 871998242 363563789 981177857 650514537 75999171 482771080 28456810 980001570 659996591 527765069 171376978 682557844 1509432 859328449 717714887 699700397 804370796 252066791 590093506 901483281 490594844 622297376 44326883 736252463 502326977 641524423 625623351 916212488 896217578 721489963 437836036 849535227 230854855 526147401 27076555 107509991 682657107 147741334 832703570 163431607 306195289 513435516 617008949 763151398 659681123 483319512 23324749 732749160 249917677 927762202 698266382 784098632 999814013 260250422 299494112 205319577 924556915 189992953 481824262 613163312 113457993 321714697 491595034 337414560 314107800 954018190 677399068 72369995 19726678 792498962 724898620 379638542 793457795 991446833 408150823 998769338 744303853 707615599 842343003 62890086 419283455 178094329 661854781 794434391 583741827 655337297 777877846 269798614 31663022 194992310 689274442 215100452 264647067 251467572 595716204 224234370 824452557 421673061 535397539 61667396 662137297 300012494 810794127 126289863 36801637 108897710 533070858 975767603 427280429 806648451 770653082 811536931 970586231 565123678 424402901 201975190 266631597 248153695 628299699 113967459 530248247 239523660 458036572 161776487 61844454 231807323 395434835 198158276 574914222 291762703 206891097 105173408 672182842 398659673 499013107 52157034 301082791 776361950 976190753 742662226 421418557 785136757 596085351 102898081 885253611 402526454 609486206 352800467 635078381 636469025 446276580 624318748 76097865 901223999 298040588 785603752 473866362 184970118 433165375 2475486 737251667 338666331 375972219 875533325 836890653 188286839 338866562 560895690 832072425 461635381 598161875 491954947 842124993 714275650 909358751 18684770 952594276 734014730 780729441 719132074 774972797 170747580 102230216 7600203 712435524 832400507 624854043 559612403 452156729 405370835 556600925 379123118 768052162 862140899 363162312 602111068 779007979 504146975 120396743 263697736 899873151 492607530 240973175 10930209 532279202 616927043 416325445 871701819 77980955 201238631 828544568 549967316 129891876 931487835 510771534 887334134 187278684 181676078 969561958 828171280 645098004 303444533 257237630 165643909 819245990 138519987 33134714 947775414 301470812 498856654 578728147 635673240 239079714 237207708 796218795 725893118 869658513 293961843 542516286 351671561 792263163 107392523 884263980 139304454 51013968 276726319 531699159 169166468 928313151 586205072 47874112 854877080 808195054 327178624 52220170 337994893 593582681 206574876 988534437 713784562 422155415 379446568 803751401 97805610 576104293 109314746 617116473 847326555 603688307 44177577 661106430 411789517 36334090 610591492 521270200 591244462 873659217 760517379 196199650 329696787 87159820 971456534 430227668 790198340 541899085 426390012 406462876 129587316 715789034 592185499 24337809 538160331 388813493 197100964 155701410 752947485 70180937 91471967 36495820 182576643 223235737 806351651 412715543 880478006 908161514 299100714 116758336 428419728 867319595 164736703 544973485 40353546 660494945 127219372 888729864 278702334 414523278 499121324 380102377 742829105 933358101 31198377 658565500 462338285 734721531 684864861 327119517 436036886 703434858 493989068 121800464 962955587 221838963 277178356 747767650 30629743 708049791 929826078 379869084 169771563 855099107 317865040 271894850 583069424 985415012 506038322 97006907 32473317 890457896 885017805 330003977 416054874 103563593 494620424 969485491 37772761 272050039 481606293 940090399 545431553 807981396 276577315 601010209 475702837 582117038 123736556 214377610 972025692 857521457 12952143 864205776 878520332 197053781 583407249 510863284 91044986 420270297 336113582 126006029 207453783 313867222 124218111 88475300 812828120 492922949 301321660 435218292 54523365 952174938 135952462 372745741 524728010 561227647 978804398 877961162 222701919 862599282 449306354 237899836 535327534 554899715 991792343 775018446 875730446 369630392 755847336 770633648 187947233 399224114 402276544 551978904 744638055 652935046 981655652 288540659 891708452 569867028 951244446 50981364 31561120 242200955 427811049 919278766 632323856 436203848 284334627 954682494 66917315 159300014 957979632 490269383 4166685 552592180 12997818 279283423 25429428 896524733 599293245 871426100 357879764 457123027 945914759 150754893 366919260 551190608 837605037 611244718 365431030 345703710 633245073 421930955 970020476 574229739 961952872 716074702 376892918 66057989 352031864 24670530 649863546 289680230 82308463 533079986 422624073 13159523 184629649 886922879 14760971 576538318 786543951 997692501 304310848 891026955 856849939 572084930 685550680 492846760 946268296 179341798 801312816 829617455 753075199 62752931 6338206 781216061 630762699 829149291 376306941 831107707 374479431 478265595 86571992 77494785 540308209 60479635 49995683 978247358 656087596 676124610 125019693 858650253 355162570 849004094 303779106 271046690 146037788 953768045 998001610 335273917 655005759 159709836 105027949 441134544 408588589 985739918 363619353 397886812 746321998 528101499 108677466 525623294 615431724 221374303 538498304 623669267 584501681 448058113 649436014 458399959 589662593 942978522 692755388 845318321 476352925 881318837 619657314 848842151 467181867 503343243 560381664 622243727 695115534 25874561 779114161 110319144 613993581 827692631 819136638 6450157 456881726 64660600 944933215 54084062 38784394 176731675 589414562 823769148 423378603 673646496 101296032 341797499 526584213 551554092 56571008 997229158 410135427 131526159 755564984 28239778 76805965 858260167 207778868 416608027 421659648 33457156 911077189 674526101 118621646 649986123 662574176 659255691 885361787 674646562 399527347 121320859 555652346 643873150 398193121 449302694 966239249 355670386 8377755 539379210 958077323 851747943 523335963 242202590 545361735 42883797 705109185 322493411 769806047 753249963 746030164 396068943 529815915 632120841 636127421 401451130 261569048 873752573 647644458 535610835 69721478 354582054 277990004 935780991 21844972 814027105 286999997 851337155 100729586 431136588 53154417 303456465 684127307 476658779 830455711 911264695 464107162 60062771 513266766 596793862 398093283 337510197 76081686 281827063 387079356 617469918 927506234 404125113 124823424 308072756 701661561 925453933 285919466 722057151 283788477 442739042 645350724 46791350 180995630 495166127 770943403 882375082 762012082 636100240 599757723 700334898 256590257 26052467 979768116 177789678 123297415 938976413 730250303 871470152 489065112 719198340 175021078 324812315 380367882 49360749 58514604 746911431 385220269 59282545 192146430 954348290 508645640 591795545 613302790 585202006 125169610 794385148 287723113 394888995 338931160 405935346 653331478 23104474 828380022 990365787 460969694 373123103 474045251 831126362 955420550 216541796 497310616 979299026 579631069 546921268 838859693 572413997 412687639 235157782 255818950 333412585 658424907 18864365 339642254 107558045 222655576 7624464 670818215 124065036 516688161 978832450 182679883 630857227 635782821 859788376 551991951 28123246 191344339 165515667 290142909 372401582 542232904 10662191 118366167 574750314 227417082 91122078 770835394 734429384 314704445 493807851 525432820 561165672 766724347 794143588 167647118 477264220 585481302 758680842 170492731 44274338 376139744 740533353 496044812 5872838 651688173 525526769 913836457 510628168 188277059 25659963 354887279 165832005 896599489 565139211 649836805 595280994 589563967 317403693 307094666 461565199 999968029 63625665 419183150 719017629 392472976 853133751 252549329 190468185 786687094 275787859 785968423 56805334 267616618 133920146 574284342 405939678 940883407 801661790 231128471 478729365 99465494 184379023 369212540 853072567 14904129 604179954 264895641 73125257 493747654 705781814 149520960 897892377 853486572 265474253 877345955 303364678 864981438 286018420 762352809 754609057 254689805 917689699 692154867 39603850 87426675 108259183 649610107 153758321 371174498 367788304 681936846 283458467 146504797 536449809 880944571 102085234 725412151 841003272 938156243 645968431 792091666 977569248 558913244 815239536 631268691 105804738 335434255 414707964 980746996 349413308 297467271 268019790 840981107 58558128 754496308 19524119 86142111 397175303 917327903 201814290 494431989 670381137 658543077 585667757 16395382 653096152 543873538 148620355 111309080 556317932 992877110 141380537 411235994 331021431 537167379 82973694 623541158 602195499 686059803 747505674 432374739 994844410 99654883 94312827 851231109 787684381 299087844 585194544 763893138 48993009 195267485 227131907 971554983 392509576 281233048 107428609 453876008 822932552 187580110 605702492 462563200 641743236 814822955 837322535 714872552 359212325 455122621 3006832 90111832 618733673 33570853 925160353 276287553 777129464 722182480 606173247 490292986 282170720 330331562 284964735 660671189 763193941 96881251 576189830 234563540 110450391 395167084 621481923 228398634 458421398 852018578 769562067 365480389 310568354 113989039 511396637 526276207 931127514 733194692 577386421 675522870 897938372 61870114 515113839 463505228 722149954 979636273 994752680 67051050 273371611 648818174 274281075 493730908 748245879 458564588 564787144 864734651 560255936 890315249 51360948 61782413 647450044 692509196 271118046 368428449 599624744 938069587 118615102 635831739 102304444 597459008 565142940 118730380 328130308 768375557 583350634 489060856 301864366 538391011 691346777 533231291 542503733 747688472 597999697 177243935 246046569 726863878 767807949 570710902 179885750 748503820 784248350 577628586 727502668 91018728 51089368 56751792 831106985 666170814 225930443 366934534 681262647 954269555 187106555 502234891 501189086 915154069 139997039 802164422 172482730 550772539 975320564 309175462 869132417 938698461 733434056 35952813 795655109 414157901 732292316 447330745 63450496 248973060 687681416 855549503 800102260 149512144 475829812 222955625 830962193 588135253 643319139 164908863 741942948 222439574 522499962 975360848 925829001 389145920 648890519 256163645 747156636 592564235 247269724 697484979 714770074 752837155 709727445 143060617 172276787 513309310 103662371 853245023 209800065 870073565 688833698 452278701 212741330 738947433 311444430 969473193 752409485 326456424 807566757 247556692 834713221 74310627 801298169 977008610 130008934 87085665 826104413 928417761 144364299 9208250 236257046 522963170 792483224 802821141 329701834 565572934 798266160 679735250 629747968 623566028 519273123 315225567 556310639 612435047 689776811 355762738 982561900 805410795 964371573 42392824 157253190 533801623 740789785 446803922 892396764 224553617 936450640 948984677 968911274 507542619 770473214 482243744 435173390 271329809 697404992 196989623 724800972 453496093 359194680 697352590 657271291 437252086 711550576 499813293 204926733 402076699 544325566 626448935 847969044 444393258 665308838 745541011 770477424 961940483 916245000 361536377 9241775 730107274 229770700 699467953 227368766 664305451 760999294 745233199 819817530 31717964 553846469 183942629 156186265 285052852 301316741 606981106 415745392 823211574 880180900 898977107 603558469 990797892 610214165 604703387 165994970 504825531 976175611 328427925 308018340 306226115 789037444 668474384 267023739 714767817 788899178 450376189 628425127 152642829 255612358 807948191 881944223 839641482 571559237 341742663 700587566 856328854 451960395 796312849 994855791 154236538 693402470 113422314 305260836 628721403 173720151 672458186 12743722 118083882 83503601 528174443 85410872 316416449 213799698 228227221 886852863 303945810 604068459 961175583 131184328 117290459 366470227 514461424 118928377 831289198 511005227 154519238 196457519 749519895 976567696 668533892 501027417 567531396 296159701 804748130 738602146 488769652 116103412 158500068 805585147 845131581 242978739 871324219 141452970 438565991 180237023 273036740 582893232 711982311 879563316 725439256 457648184 439149086 471736091 951034426 278806376 133772416 309839352 862813036 993522252 323311100 277821171 378585304 937410878 436341374 322434944 479286187 724212356 425693233 257951283 128062117 277446112 170235424 926588091 888505173 797607262 176402349 875781249 86207905 625122994 914498613 412656868 279816959 831077225 92198156 62511988 898539928 32670394 125133600 692711967 480707265 90637958 259552739 31695038 327412218