10000 94708348 77983746 942380304 105869106 598230635 896920869 223807561 227881278 205609071 564623731 18048659 684277492 982270673 404704493 709366710 456802051 64654064 513228429 665880489 433633908 875164390 823286758 780179686 679937045 483175869 698460015 950549395 900200974 500749742 101457247 345139288 260567033 815278449 953562788 918905521 905048070 808657278 372646222 596670349 261197364 742535354 162357257 836753090 73842392 437601044 542528510 874999507 487388862 190730041 607434736 634545865 313755196 690806405 551468651 791968206 403683835 476239903 899199635 115201725 688592389 985383210 534436997 589998364 678000600 280853554 721051905 500790246 322889140 282461641 830880355 285349126 772867812 249587907 586121146 248720359 469968723 462738487 829460943 955160420 815978576 82967323 220137113 60672392 338939166 953713315 818098921 175389393 663273846 847261 983149678 808119123 656949693 947636947 727233916 559529931 846452436 703100397 87760146 656028556 759923431 182370257 870809889 25783306 702252974 957042952 122353562 542018087 153412185 746480425 710027712 653458310 880143881 661111798 856555854 740693670 484015408 90930885 147899635 151907664 19413586 288299223 462494516 608421027 452758908 398898102 623901984 478071452 534977805 769144847 732972837 67959707 17029069 98240816 718143845 573244818 917807909 339327361 751272479 146643255 680407820 878294505 674134459 86635883 376084756 610667461 370572477 710587401 578747015 552434064 262810467 487529066 403816387 543335521 832803163 753303046 307405846 537636664 891537145 267077262 712180343 784394481 767305256 828460027 613742131 460570052 587764029 464945571 484039018 652988557 987101351 831674365 230315314 736189079 434056668 520840947 431683643 994455875 896528185 137597801 918286020 599796888 376548569 763486618 600691760 459025622 809838210 853488610 870244660 457310690 585910596 485306978 201133245 492265547 405474275 395516339 565262804 20668936 297562330 414919596 90437575 978233860 911707455 495477889 845258213 485575367 740279438 684402755 984718987 204983048 389398989 472545938 944041132 351266200 834002557 103097346 195703938 530077577 499254776 995422316 327702447 194987450 252987391 102781959 733689697 797225914 149723560 74777358 690290042 105074812 621815620 190550392 553955650 69205514 217953207 47648357 212294892 338823705 943146901 231313235 95824470 368890619 603084021 133657690 776632620 100632775 100737108 413157378 20737331 578043495 925120775 878798115 474803092 551374714 190486483 261424862 165359651 845966326 163204532 219548739 367491062 397701362 473325175 714996369 792329462 929912907 956638369 979153067 829875803 688311568 661596000 616317168 109168308 996637615 201979664 269700682 530659008 30984611 583154255 902427861 644810897 565090008 150464704 402299779 729203399 306557865 179956683 554866994 571939583 661392031 342945355 90221951 135506608 60287972 931536985 112672628 235412185 216908744 757960922 807276825 855586753 435472009 465847305 530056717 334241761 468910257 298377422 591660536 339721139 275335022 24030587 950658328 991070842 333246188 715019395 711408501 478964205 667406901 418868783 654409485 26321176 820144649 486603177 536087280 223868020 452690246 382046014 972745940 75314319 627729037 406994507 919746900 89818877 752911712 865778487 323093413 824284958 87605026 779406724 54733455 108241208 821932152 735952521 183974755 572842732 104158505 223394181 919381142 593647722 301213513 324839482 357762551 797841928 865653437 436992400 121918914 436025424 948392606 951906909 607600660 374815316 503203207 317974982 39452206 820003164 974830181 715592033 350240512 990061881 741698318 241514614 483323512 27707638 647266482 350099561 517878483 596872894 1140569 732274680 170148718 1255977 834106059 764701755 345537437 388235204 713508561 990923569 521390750 382935034 144754819 164690302 322288865 784853861 734683449 455300346 973894991 783206660 473733928 337523890 361359160 420599649 171168751 423506402 134774400 335022610 769874645 209701428 941555665 568450872 380464433 724625278 655072649 659973810 446709153 441500307 881827914 848297153 163180324 755750419 508375819 947877049 32103237 783198619 732658817 385403369 940883425 17500736 464217644 874937502 236308836 152111048 766504875 817311784 610154541 174821009 991514123 859203603 493525427 953078383 827061963 234158157 349294729 931921869 97156105 681477806 663350580 400932329 237950185 410762779 547599531 849821827 783679982 108662469 931158191 293404472 164461316 246078579 947958417 664479037 238518994 454233328 447680129 476689106 702495412 913231036 961241694 786960224 558856783 586505517 483572444 47765630 362713969 436097473 12757340 64989144 72193953 978823325 395642095 540672901 482654158 528257223 987745959 478200526 921123969 26457121 813929700 447009484 754481114 344193758 516276534 464892928 211433191 632333265 884435917 909017614 410801231 824925312 425967576 347745611 520679966 162444141 304772325 487300593 890558648 564644941 212979825 96234014 634201826 16719889 178050255 536219968 592033724 296300757 35436409 881207529 153871911 330235113 953855908 444542251 290469632 477533598 924375954 120238305 633676322 939301773 44478410 357267766 896439502 998842140 993141498 74908276 463698969 368997037 884265580 261286920 528755261 795518799 10911960 845349524 201312139 401612777 555244112 260914258 467004508 865498706 411052922 51582946 15702043 929160149 222279865 485301221 178002156 208290224 673520616 960591506 395936271 640654484 532011371 604136861 246769608 798187972 661075514 678253248 769800221 129566664 719245625 403416321 783969279 219563974 280125473 446845891 470901403 443821158 1726522 703979818 37898863 177663996 855558566 86251695 330726092 676345411 763670747 650018247 474042386 649980466 905169147 499459291 6759487 967383707 841585508 566069484 843235918 463978446 733971173 832712806 631125117 934480992 778229251 216874525 498302738 104095663 904879088 43528752 879011160 130791846 253576800 331753364 381578808 190077719 868717796 497512743 683183927 608414806 598102698 958429776 102074033 606421470 615093606 224023045 523916250 823140797 78199334 210660294 76492612 887694614 646939925 400506041 540044395 373386881 46070584 307710273 572500987 80395073 160759689 388432480 981249522 283989932 741079103 247883264 645711663 424385099 631909574 469280429 718926607 52217834 676050836 350001296 84282376 517786208 899539731 778239220 890530908 515327348 506435549 473127874 483363126 584289232 873243343 891198378 483053486 900867704 360030301 158510083 41063535 321723695 335356512 446379448 743880235 156508357 146327672 327706058 733657042 865835821 274641898 207987626 580356254 164205610 322739261 833621919 229697754 43147642 387206678 600825499 226732950 511770636 209180530 452623228 621131803 508152268 802683790 906567884 141068071 680139660 846142599 379256296 14549188 699425195 371508206 182432974 256866939 774056142 594725598 903701284 651504096 529133827 631724119 332036160 481567987 177351968 507971747 324817753 731276964 69402983 620394299 236015777 906092242 295636955 286051610 43421411 329136901 228188829 605738637 988746166 56775259 445471780 24567730 51995592 320900572 539285453 290435387 690194943 241585543 722247423 844519795 9841221 209424943 63773909 654841968 226384066 542340754 147185107 876086965 774476623 957966706 554294273 877769129 377596741 899018235 662056419 93111855 200080640 369383378 983364109 983442381 471930393 723197874 903076903 259291917 783157766 291172143 352383962 502670493 75566616 73907801 253453596 925819576 349234562 312963188 994074547 673408455 992314619 635861333 752633596 418021418 900334443 129108756 829742617 202869729 127565574 720965038 167447858 156700512 553249233 546779565 580545530 67028141 631299865 651249499 462367092 435150975 613510782 861369644 556877607 840560723 526796594 873611095 215142256 86495153 524307972 578233612 948746426 397281082 345510101 663714768 393402951 948639700 652377703 59047441 620635866 60189031 535006668 711225277 467710427 568094065 292222961 87595904 894042287 916390557 174959392 807228240 157484834 976268396 193912968 327410629 667995140 763759768 360078686 242449167 679330108 48148113 767187732 845112436 164218970 840233081 611596381 997198910 869590157 836323184 442770263 265757301 338199488 253094298 221877188 650427021 892026811 657334551 841184501 989527654 831198619 343154279 198351941 608752076 686319686 573640891 592826502 829710773 556191630 290938417 960826473 219360199 279389984 58978462 565728326 27795745 759167150 197921281 690031822 847673885 573132585 373114560 738760951 696754204 59311690 381259334 676998606 424488567 544927695 610588601 475614225 606840870 714983091 886108245 989145017 217973647 397434026 13002778 275953964 594309899 86516848 691935730 223638783 452688660 184692429 543507178 511745504 382413584 148977828 403622471 579580430 343955607 298751006 588715863 122649494 47794510 437410638 463747077 654925021 790008663 894092562 992685675 726034080 508456632 985150366 947592330 683799385 221936167 584812370 992221289 485392809 871262496 62401484 537647359 527061958 643856234 991943824 342294420 74791663 48375629 630499828 126657266 294074005 648945761 444695470 454533253 633132311 289983966 458065275 507874736 416861804 7011026 211040254 783920397 832904283 445553061 793304801 965440997 383547343 138323299 282679960 214628917 227342177 672659184 680958747 707099682 312702362 26442856 735105703 722786218 66022532 253189177 157947943 232612020 705032501 287357800 790490012 755599474 300623275 456275329 586030888 124307585 563060518 568798445 856113518 938103127 76621239 215594947 364471627 951517929 308803146 677529862 441789125 691752655 506665589 852446004 204522006 316806707 638056319 369162758 226819976 982096070 261681149 625865089 72917665 134800719 598206825 437935489 391929169 121873293 767561919 463663331 403843266 140612913 897128220 790171540 61900773 770147096 282830525 699256978 45238801 900926882 750856381 117340768 152511658 731937841 626167315 331165550 594733708 817700771 633925035 728956177 587755443 788982213 581439213 624499304 671464038 543479613 842002306 307340682 878515844 592097519 964902501 126170960 589329788 565187105 681365382 630850642 821283796 345735556 27119090 341432952 99653956 279121864 311830706 902744896 969442522 756872204 813867533 849698325 267691390 716859417 928283985 885390380 917101874 109929316 705590291 285288427 362110078 722922548 316307228 987736832 350496642 971173910 888013492 666279157 584560496 16665154 37572135 644201902 120448647 769045288 391967156 796762708 746081104 506514184 823293068 861694259 231300488 623034140 811014823 28013553 4896034 907433612 200599400 861010292 520530394 900019140 236930113 839741388 784408750 404628769 990779872 362882343 642587002 429040586 751992807 659271326 859143715 161438684 620650166 117260386 530059285 181963764 594036346 328771660 78760072 43667260 934503899 430994888 522410370 113279735 576585295 477851981 162369676 6096560 804083983 964967978 900249511 990539114 125832594 415877554 210390978 785116084 312518987 941470706 603807979 525479175 262769367 138107265 302466909 47438020 964664287 762964096 557696994 914845023 58080352 387164022 810959331 332255892 945742120 685779052 780161663 165623364 804604792 611474753 893271019 180735414 429773939 385138397 140387080 405274852 704097420 741104322 585786394 539361398 923020837 919313108 828929512 279763892 98056669 543951811 470184718 527820338 691608616 93897006 283801816 270127116 397770543 282565952 232514091 354989906 573500046 496715678 171455875 826768223 880800063 903979677 959330235 836129443 584079368 26176987 456371199 503963794 60309826 522673120 948323407 971247009 443573734 120215875 607611574 807183360 422816287 359047489 835956206 629382650 284047606 502299650 762645256 697606065 299005980 999024796 936594442 463596629 600665799 148801121 84349906 211952650 106248721 642112486 787317201 465002463 821102330 555119592 402330597 781565291 851782494 31369911 484352559 153112303 886901506 29061480 222899006 928935731 595839995 283924362 737872651 734113246 672426385 246476718 910996447 192993165 36934181 57670054 545684111 38609190 766089251 911649739 739818496 845303403 161920263 305695169 347967159 812567573 450036385 316418205 562629546 265702138 439968465 696969351 425587178 620391637 834503512 428062387 920188573 190292968 722453647 418209326 999686151 46365287 72998908 84305545 516198578 48577544 585162612 354739774 520065297 578745170 513529290 463037872 558333493 301225807 631724478 302949118 844345059 538844777 831202057 666721796 465440532 46185449 41833897 285835367 516067317 245049783 26409730 337061910 422579651 534774941 551484177 917788910 849932155 69436584 541111141 666925509 412253055 106081633 724630511 776365846 443881297 819309281 566850475 500932068 547095383 814200127 272225542 42476236 11658280 598837997 639133262 778602669 307864866 800333656 783127219 331693422 959514637 330450597 995210642 373813846 62113221 671664883 747980398 947073078 588536931 31240588 312665029 163494463 862690119 107549104 350138197 468937288 83765019 619671004 513273146 865494210 525518017 350127391 362771195 760397559 945030937 743261055 304976028 282448774 186667384 982462973 348417349 278029690 104178203 59209150 292797613 885496437 617583439 884488249 209959376 394332491 899359805 237135917 982409118 424340900 927886772 442618628 923991079 645090681 889079734 113025487 148842397 85387252 83551451 596485957 368943563 986299513 56658443 340080690 235556556 515529262 257202115 715502493 936984798 75370413 27814782 199372886 500077399 8840918 147293341 551660671 873111584 130443461 231815638 492136707 854621526 31943981 3227139 983410158 850793003 420594289 69603619 722577922 917579789 387875222 559546273 234055639 214223839 47804193 319265715 311501606 147619381 233501585 167654377 352822972 666422 799036739 483945005 124810708 769250996 237114599 416156676 160492558 629916208 117103161 985878662 987035893 179263468 304636591 299948032 249896265 973633089 429786736 392243240 880004041 810908793 349947617 968215010 176979929 355149616 969467749 802478440 19787652 701031248 549783288 880249664 5847158 96862844 26909246 472870369 398017413 416015967 486721674 88264142 383607279 223744341 116730058 977783664 556671808 509691850 424771341 452470688 624472526 804393510 948493964 863913572 966854551 496490024 358516248 908817800 838435088 703530140 384002604 969330205 517749191 246835634 205376739 218697754 332918100 561003939 201199252 401217812 562734553 882160834 201647905 727081546 576251874 424079295 40789177 890056552 910311944 684106084 277765992 810251963 212637146 605436411 604091372 813725997 787861630 102124864 710190865 653023930 361157540 61066484 611895804 676484811 226601966 438368335 698449939 181620516 408784839 391486200 560273408 273483790 102033777 377182413 205175152 332996614 795373718 95625942 645951006 607509329 846311647 211289688 138775213 594202576 173296962 720939095 153938015 365159112 842684577 533628188 351441469 376657745 738725514 976401500 896525066 180583205 934800233 969139807 576588922 8989300 494696378 288133083 771695515 769508017 778616953 239214558 262074995 769638861 507486344 279554213 185994006 908732114 475744881 828824786 513319002 532085234 525284807 316160512 793373333 58200818 176921262 453560164 720349119 157739381 444786334 84177165 201874598 209573746 452118786 518606526 501329738 584339220 999316183 936699489 337034353 392464358 196478299 451633039 598444176 963225180 747726078 513845654 809434898 63744597 412316172 291355303 702338530 265400555 311989076 476029997 463522370 152188614 760996667 523037951 210458954 361145145 544998470 227634115 608649531 82410979 640187139 954696259 781090743 413280358 536982541 823500385 716144177 430223726 661798768 429644046 837678191 513475877 170118461 517477307 83005263 102669976 701834432 212938911 669336906 960906993 12790792 689768357 690539954 586575859 29810475 373976218 679299396 22820375 337257237 936451938 865252942 922393599 600555718 399203713 772266319 508663186 427340434 118340328 923860656 280849199 756200259 21011022 952521836 616129145 337158410 766747709 218193075 603765010 182556988 178852957 433183717 36424225 685735006 640546926 808778968 478699116 558608039 824101183 681967395 532433745 923820125 433465863 534377284 170377566 249687359 568637843 532332893 964752443 744936130 285354255 261483866 197144037 347425390 66881958 889658942 833979793 284620869 930940598 742414332 937170371 749943736 892775012 205204989 640976036 512926360 727631943 438160747 458712649 129191617 499383873 454848439 780338130 519414673 258631222 147500312 963809261 21235074 104432051 880499363 661866943 153235568 103091218 79404545 294655338 367327686 632638336 499485819 631790829 837020647 688593539 290109876 754229304 673327089 564488086 814743857 290197558 218189927 197550320 285236470 132988364 248975971 537844900 771875167 753259511 41209905 421413751 520670566 931911493 342363090 808715964 332878173 719255350 123532340 884835203 203400197 59431841 606920644 373219609 193139578 761300287 129565082 163016718 346626264 118215179 386419727 110835882 825546354 825730580 332564173 681198824 251603999 206928461 328177035 366193166 408434275 750255294 497836024 979385099 474604469 634093924 888241642 126640041 509024480 623385529 828645390 466623771 245712284 883151665 922828521 786699790 375792058 905671364 222322893 305741680 158829399 392529674 752564686 786188086 279082864 988607512 849245078 571220028 628525340 891755530 446596046 176809878 530061194 318606806 154123781 847221215 997662143 895567987 54565802 330014343 125969379 579541247 785711070 390479829 458552134 779297359 670475086 332763638 412961726 621817497 744168713 295992630 101052483 362459543 753239854 352065853 720625717 966493465 818690452 921856619 24536158 541488192 106254421 807984587 97543826 548784689 658478943 845641831 622891112 709173457 635319000 240345401 763957253 845993743 163109486 54382337 478883546 213544392 373498881 799193880 119405870 685381701 1485344 142091593 485571385 789468017 921632514 651307367 461774466 454428441 923968602 85698081 12650158 988864053 341904896 556286041 747960962 459713156 266685431 172538858 478932368 755150963 81673715 788367984 718369890 748372547 609091028 829775367 886186971 273535163 193630418 49380082 806533169 831168722 717256727 343204010 256838613 245844479 27845289 842809090 352298718 484531762 491521636 722414362 418244825 644567027 686132520 434487135 180408453 552211844 81683913 17318339 760741694 946405881 575026659 756255155 855286671 152706186 614298939 131357513 747106071 15045993 95234713 960561179 938985454 757097720 112269491 12970509 973444621 813654661 32900083 94906282 455722862 616510805 933844243 362249612 552203798 749657762 672013702 643215370 606817365 654502182 74865427 302863253 659187535 725855006 913814712 8902071 646494133 575164999 926511492 815679729 303900360 970643087 285244252 830065360 343543459 181952552 921924608 786097500 629649726 561106038 367760127 882145851 431523068 157583622 638555356 113862447 413322469 402113969 964774473 339343743 481472943 790354047 208025271 746275280 217778758 699224256 959809114 891623291 762104906 5276947 401629469 215114059 245078331 370081188 28027174 189143505 539924516 867899113 548746 321949408 916709107 693615759 796889015 191090486 912778643 16142018 504057985 476288680 44205884 864148455 297443960 642971014 598284566 919384974 185763810 655323581 973658572 755382980 7614918 519158407 753488729 945955512 800363653 131041950 602244413 128519280 492208433 954637721 369896387 604874319 490600352 69067415 403499666 501571074 139454382 953494883 932987743 491277567 895525420 667497366 430600078 272605573 313496652 332584432 490206303 322099053 926605169 758091056 343333351 781738272 629825751 982367412 309089903 775386773 635348455 659406878 25237654 612807605 356622073 842709644 205647600 129590646 473107448 176372333 180150649 758185668 797331069 226862472 933553548 610303356 239745194 746784994 931494343 720673018 925033157 121804306 162242459 415926792 208813330 521462629 469298223 726441987 515751767 72568068 451355891 516263052 85543398 808342750 779961577 683561743 962056734 327749133 535272004 884889279 84500367 159022860 492519496 807635273 483475895 367718884 338950603 313176653 230204730 82459594 603850354 604434858 459755636 923639523 464755669 461403002 963345687 602974668 872731079 235805669 32378959 752531580 430697644 950859784 410705448 869366752 480252588 915279504 328371428 925007830 18753205 238737113 162911293 941918659 818018703 751822585 125423989 162358197 919982950 530367541 68605084 778571016 64210232 276608821 352199006 593735716 846091242 840168404 357882296 554103240 522169531 990851526 533268048 629302972 601549267 35744298 955386533 183077620 430417901 5960996 177310823 901483533 545668176 961603251 644371394 999566901 438399007 285706564 908081351 257629923 746515584 459885803 326581052 211003618 365672577 24517521 205159925 698483510 209002250 787926254 685234337 671325142 192298210 570620730 323690508 692905145 380595352 948198135 808147734 54672221 582951430 618668826 171992926 217213534 456713341 396547346 664401 637501449 556026060 77082689 132265056 29415601 911376658 372791482 25609980 931861196 715141473 296991966 626776893 87174651 327505484 999113762 315637364 672363622 349784271 256362936 922832195 281822281 406709514 110448796 314159653 368564818 89859220 149876428 151897862 539916766 116664267 446564977 355321901 218559690 369939703 23244233 792012579 860744945 91096193 431019370 423267240 243000765 269285454 129551076 887706647 351024443 410135994 963181340 299101159 702305553 475464857 688831218 6115455 693901434 825349753 101396276 80803115 245449083 61314049 124466670 233186645 879911411 75377568 935697795 742518775 956091510 973007712 108818389 552015612 438243289 982325472 925802933 545064638 575491725 999474335 844255408 87560355 939051437 183658185 705393476 49885414 512765514 874641184 346876135 296906778 250134147 579241783 691182229 30375470 968179310 742705418 59263735 760295060 181881521 908605749 72406752 825666968 882981303 351860349 984297712 795907788 520642494 49652377 732622183 98633134 616374124 714926209 52598841 17321486 856636923 322849120 325431421 146932766 434585790 918135554 618644877 98879012 200101549 521678587 694234262 763660641 978256700 161093729 217645323 30757653 901065180 725611873 238394279 602937144 997965086 426989257 195616481 188702941 31390888 278624289 479277274 824773756 505594397 220430894 29277874 671736578 8142471 394865822 391594996 436677286 73703674 151451893 331659636 532420583 720616988 767097572 28927690 714149440 474944717 314119775 580808584 731582929 544515276 629316894 285257884 855496888 701152186 264738360 755890892 700414945 32108561 686080118 313690023 618457997 67242731 949931051 986414316 567227127 567582454 527864112 660129495 735112291 422142912 816166997 462939113 326079103 340568837 17423284 86709090 14373670 241281129 255324897 65312081 237938286 207090073 208081848 61361989 597840482 350859236 938272418 355786926 557462957 123467907 787997924 312294720 19390927 687272060 943696258 695408345 864116086 146184141 33804059 585628250 822250552 972947450 730970536 67310102 917656138 786477054 613492196 267970043 599705176 196913786 907768478 982444107 54024638 150556807 22049597 5236611 661238884 896409701 311797464 525662960 403279343 210507438 182822785 67842065 114539165 81602644 44122974 731441134 515162955 565991388 633442287 214207430 867988792 502623621 422935841 830712806 647047298 465275034 640461313 399827291 946036529 986103855 517402211 285513349 712271828 160005674 361532113 220911143 45710207 475554809 801448557 16016807 133027169 384376716 457745828 926845851 872758345 553173022 755254733 14568329 310298229 311541635 157852228 794287462 411138531 82192037 937463878 249516071 947636516 984386553 320714324 656407915 170214059 626170375 262419469 662767735 746312803 947460128 765731582 483257671 989429971 921445941 119062925 158263660 506758596 67709335 945345393 129590865 260349955 615698091 765692407 534930492 607883006 206933900 785596709 880688207 820918140 363131484 112133124 187220728 40051654 94282463 466274037 217056497 729850445 419105018 860841647 712343736 134959386 881147806 32160061 859446812 588100055 456266367 779699932 713340791 732729299 206383811 514458742 151254128 131750966 524696981 376819010 380412792 288194821 785702926 99546149 198658449 50341814 659817920 356848184 708322671 148896901 693251681 696538870 748053000 661625399 737062782 595527089 537367747 984330423 173540206 147642639 90551552 211912583 947033172 255872789 639152226 46656410 570481470 122878450 423568505 423132802 858490429 349382779 743671424 163456927 711328833 737560342 485227284 187315793 699482648 151523875 150896772 384755334 165277866 607285720 862420046 540463827 169149535 356210803 240674546 763829943 852739966 162198948 808795598 83699357 673200401 973744047 183763716 852012830 170359914 60368461 990738625 176237713 86689011 700493669 682667184 735274315 832219204 54105779 301388834 51496558 508086118 691785514 30263217 99868637 56606147 76747888 201693698 587745896 884830859 542388465 900138957 289416117 895857666 742473013 266612672 4700849 289011527 480151446 951829184 331990127 325615093 429816417 232527822 710221247 49306931 547780807 951122941 467337113 209212155 617436105 143442300 485571085 555825987 204803533 100331405 739588934 877059857 271626280 8128282 428931792 151655200 476675063 958556858 304171490 724067364 740367606 136634540 963557160 289488563 184553837 528646547 155819886 457645309 217406879 175483919 652309292 768349883 968602677 738415757 706559631 274021938 922367910 823334159 223925072 943071151 420937023 196858166 239198919 375212 170380382 182984755 622369600 965512171 491297068 624924818 887730174 498040596 930192331 824341306 916450019 309904980 2759963 728601939 397068918 457985539 85525450 736458548 682092742 376082464 784384824 63850161 178755091 761338071 713686217 917335786 246775912 488533530 525192741 974763532 810961896 358452015 808093190 366066103 508306660 76616090 680817094 32108424 369723736 429915891 839800988 727183917 140597108 605355547 923804979 155936354 460936708 176341348 513798705 623349325 527976576 517932238 430671904 624013466 615011674 990410527 664783925 831785932 434535672 622221625 956555654 283021381 190061099 503852975 997634583 168367651 358042261 763472631 657358446 872212345 985449378 793782012 354839140 554323510 574198683 484741971 706869127 127339922 741976258 385815750 107525861 79785152 653205484 791353565 706206217 437117572 282110061 446591816 594880651 687596811 5694768 467518074 377838821 164380788 584077006 3387966 785946768 411187435 371519524 261462265 708660520 490580262 739904925 29304733 58410333 410704181 199952218 222593330 772935556 326210867 672758629 661768852 370322097 378218493 179585632 438787527 298047737 369829545 254689255 937655774 278616615 516639071 723165978 91388390 995281214 553909665 454217025 580329180 247799659 91657468 864174817 649538285 715863300 931878663 606121416 52239127 86448062 403255414 61532542 180089 958894805 584935805 418820765 557860940 161535364 845265743 130339379 708354903 955184108 903231175 199528048 498575597 86564395 211609157 25805541 173879055 54108170 767879555 179701390 730987307 621570200 22929873 239038726 865714095 722117580 883818155 863069196 562898390 604607013 973259823 991961016 132037830 822076221 121023534 229047837 241750198 557030666 985041567 856744620 240607853 403089892 274704664 24954608 359837907 608586641 210856316 168739513 406531977 946437799 308547593 737523234 548333875 909180139 386203769 447168711 998337161 944399002 558391848 263009040 759111241 329469565 24886950 537319291 966158701 671409074 81085460 120194767 588276966 930818757 281865660 530411942 212487082 797098631 762412791 299750622 237649858 684647097 823639154 582282523 693147717 390905130 164055814 387813232 537822723 48559433 956088248 467524998 902490058 30301401 459142842 67537664 704057155 529314549 214161034 825648324 488624292 267163750 259936618 753790632 64172001 329096530 69422276 712209737 775357578 962827537 368506793 43017558 788169949 294351612 792721881 480207281 909079445 460300671 924932133 311188111 512811797 766222080 548456969 736898047 362427049 528883751 303296853 268731487 208365171 945657474 576842854 709188452 875151710 706331980 379298402 24824531 585762519 627636462 105668488 459185453 332568654 575387254 722533203 820653640 937594128 272682305 498193701 845019842 476807463 860490203 853463781 376781128 26664806 672971407 33916584 8390819 999559705 306524817 547631855 374238039 196592720 999090478 131915663 73420985 993277484 167061792 86953354 237521898 324905901 500687856 798000457 172526597 100730134 134538657 609314728 666280506 154848582 950097605 934381142 207061888 57279320 360403221 827851321 988310024 668959182 664436475 677200743 564248749 904130689 129314497 922763136 625260811 630658098 653101519 236428325 714021136 847094525 339501999 740546483 595157694 83802444 655980306 539535935 331528343 957354349 415052253 854723875 780696741 183009354 959058417 653965286 253615891 481029511 230709037 471626346 164193029 448443540 452017573 609151481 848155948 593981565 551248948 863525673 149208166 631774434 678536471 272016788 552323929 521974866 606530505 990994503 891808552 36857036 992442609 335320233 327916417 495691526 77401292 455313688 507217214 241466525 768642866 954327997 601590888 687319996 534279662 85747973 812767500 578709629 719795392 877057969 527599970 757722982 424662767 148398239 487642623 104927123 699112164 935329609 693123762 268257154 462588834 256145823 700682597 312764538 626767273 807245214 616463914 630034409 19683752 885681969 175844174 833354732 984235115 24489445 268515177 359555358 419667561 180075810 33407702 328391444 295952266 558454507 856588011 524824518 232429364 792412272 137768870 513034948 499183821 479986892 47357429 640259702 112210379 549955428 584394174 256368283 473015853 766982733 449245343 437017988 276684261 453052375 404370171 759095908 941361789 631781160 379964798 577869232 998348291 793279421 479675589 948890029 414501619 806958987 621021337 459074076 472892180 744678937 250078061 627068627 658763667 546237051 295605586 708076895 373571769 763947496 451242852 390447166 603158182 282533574 937352529 71167090 708482581 856224718 427026181 13445983 802281826 89200135 281885208 533563765 794103141 168558121 870672848 413554617 952328971 700416509 78644170 926892143 119870443 870967908 84435930 492599350 188848483 81631872 379736931 633608504 264440368 1434212 417875404 116703442 889382560 868792092 551952081 245888869 484666379 432237229 354381593 162004167 990397211 186320887 543189382 846284500 852435110 960445900 483873920 578485836 890579434 989795005 209837962 631353539 754664878 100411574 397619979 47192505 639992286 487476150 396994774 112087660 887410275 728029246 791258470 921177217 409482161 101411112 505319339 470669104 487574710 263584795 463749710 158390711 974824467 576810695 593965878 441474165 560996409 168448829 547389032 288867622 925233278 571966503 408653047 414502724 433756594 272718456 183803656 171691411 760140167 555823038 694537483 324259779 211307944 438414383 535454524 444775490 16405184 728223635 741195823 653674524 116614909 974033912 724656828 549101809 87464047 359162421 214551857 229649671 582069715 960299077 94684862 483520448 401746488 575018978 353205519 897411472 285751435 424734666 548101893 696300405 285315429 399029695 312452650 927275231 856475351 86086435 825028517 753520991 564278825 99056966 860809 475425459 434015851 284358479 477766298 894398027 992886194 201983951 369577595 765062263 767843786 284534204 9214189 353405527 208182128 377166922 347041767 341838001 260517603 247155810 410876150 386650724 718183782 724112314 197715961 709461769 300210969 842526633 148412169 927070390 499361762 756183147 52896662 586979910 488575636 462503923 231550679 29828604 332380342 453140985 749467364 967290424 622635771 417421954 233940648 371940963 580756585 173403674 74197345 20158035 75015055 482453287 317541571 114913864 743591542 40043271 412473582 316041222 157234117 685913612 372983830 524256152 849117214 253584306 426222255 129775769 638937613 398178801 575345497 669383376 119179071 652660518 660630995 263877591 124251467 311559233 330891739 547112752 242246706 911878441 867001210 391098709 80259711 300783040 380122408 71345761 983743139 571445354 225529418 434852418 567358061 600100910 657614862 942566138 712891725 444541315 173161302 617058372 266422675 546986312 234428885 748371621 734948824 473702154 498001244 126141095 751799259 845390969 855042129 469224488 623719499 523415174 77227910 276798024 299371614 18871125 246605003 732902615 420592172 469674963 763740284 202771159 204314247 650315736 375716535 331194531 450197430 198844680 199840122 875989601 9160953 741026165 445346220 502524605 924826416 979991810 637572901 218419569 113392580 684040440 771343546 692722636 718029410 15271844 6494541 459058972 851856319 510550866 100997684 156024004 474919195 724066708 240586162 900497910 346903422 853422532 416919111 635059201 274594712 24655274 400747933 716133561 483320477 772213099 681418125 117101069 405965882 894005763 144449038 810212015 493179306 693905128 599372674 647707375 125746482 83519011 334005067 468922525 70488684 372379893 803545946 797082038 505962784 998721321 767154319 934888298 181856354 882849032 661012513 631329094 732005084 202041302 409358614 231021295 85960542 817589001 721968672 244138319 762826673 766759697 345704631 776143729 105755437 143697336 600743061 307092138 653997521 491231780 146514632 90325408 547284850 440643978 713411761 322887873 798391664 247768623 662616822 133658574 971496728 948084463 717049251 344286712 777962210 171746589 633323882 582989979 231187658 385008438 366908059 91031659 550333389 871230117 612903799 372960732 438508105 359083720 356812763 809355040 197115875 94711069 923532836 458100626 242507165 481513389 49017508 114794170 559721251 688770842 366214964 300710832 951617863 236105573 769080289 724603833 922995844 498472741 361968626 962711513 829119481 844254241 968961270 912307309 201152382 374350333 766616833 763459710 548978469 16916209 593569895 192435865 704208687 810617131 122075518 786882761 624290023 260464663 417336036 536120419 596467644 338000044 389555583 647867162 634385215 458831837 572384972 930553698 636993141 660315729 710860600 413918834 524343739 522596919 941251351 489290611 3982550 33950630 914565344 315270586 96183709 821195224 715595019 719921171 596229222 983645672 491297065 813272068 370921749 220144056 191551553 201466127 382931261 889040478 400631763 962978780 835739146 762366795 286829030 505960699 957969285 702268913 477432766 617977680 90927475 674538620 21987578 740746044 799739388 564685184 61896789 257815129 352198421 764819626 465681799 794100644 178052063 952629755 335371227 706197902 772656983 867715715 40513256 191577161 915381633 892899127 885603769 840655120 817174431 659374372 286767790 509437968 943440288 894049579 71045330 677460794 96768018 287059697 77216580 169346781 994616829 208682355 44136501 815877267 909492448 148458895 437401345 971798674 552605261 679966350 843071223 845128157 783022949 551193967 698356875 777348561 854921228 377829201 90286963 148671862 387188467 939272036 629071785 293785569 419541371 373066712 426051676 441966158 796555016 264863010 39842986 424149790 912733301 842045344 543854519 392991083 228079153 693232309 14596095 264107492 650571143 134721835 28993432 47239155 584926466 620482391 446653179 980246099 574313164 555062695 959064643 732385169 184187585 354195848 914543057 790833208 453217370 596558260 184835393 649518785 790829185 48571575 7134625 455669268 319017789 944324347 388162653 589152167 944357616 307646218 367745946 798392857 601132663 855264586 910508811 877159951 225160544 324838052 685501918 213744465 233660799 754098778 603926254 615866900 338282037 986717509 567255687 982022687 776845859 378793571 24821261 9639089 629405978 251836922 694302014 493140751 155314007 78108760 340508132 42365534 663889892 864486327 215162577 671785773 905072357 289492784 172492205 188708746 635727624 974510256 316964495 786345602 252747148 625188531 577035988 907578567 861706474 843421765 38396960 416398475 30499733 181554053 661159982 839821807 147757777 393231346 72408282 845200002 631805670 591107853 631459757 578855178 158462634 791985941 237064158 956594987 380520253 632833035 351384949 939177841 156451940 2116751 748896499 258506863 534894589 200946648 217332992 493755666 747442292 91302793 928586203 109766422 608765314 200044298 976168251 112733948 149725514 956808782 365903621 114645155 414046564 478777564 805481995 240013831 116185305 769381908 174868079 398072971 879318242 365754948 727543345 605404165 191110016 12750609 488769153 535909914 147999824 51442665 574939223 227050409 119252097 694379457 865284988 856018573 620249883 409612035 973285455 220694250 89013999 314333233 455841039 944534732 80295324 870234371 528867941 85288691 64713093 766859029 495521754 861413965 33887956 155704150 854645479 245232290 862136057 966178340 491055367 97729385 106382848 48593165 618914454 577051144 567689866 779483041 850204959 451924366 127139739 120287178 206412858 803908980 321618953 529201046 794789907 955804539 197114730 707088839 308143742 536808225 298054281 876572702 417795389 726142064 527723977 674669611 649552123 72990897 800483944 202540409 992140987 504984131 977862956 467694183 423051622 532500183 381097101 960915674 598469997 229694180 196344548 66184895 628729115 18651570 174350899 20524508 994037953 466879440 424042380 55998105 418547214 949460457 347132558 848336025 68957135 654088366 199525473 820192074 934392819 84871496 150184991 842617403 336426567 773828299 466949378 70137216 417637001 895931915 30180001 13434624 680288608 38635494 91066348 228739802 117789518 735188512 236916814 570293022 802252015 663847085 648817673 727030250 174186194 827163136 677079362 210187419 768097647 193932494 642740914 925436350 617552761 374316195 23913881 540732971 980560877 421473592 511066741 392922565 544094495 452709265 471917164 477352067 770849984 805721660 608160567 559515147 182417017 584830480 823208893 269169748 155023338 203658058 923503918 769514829 285935449 490102632 453294579 24227897 684782780 192448077 855990694 938773959 223826691 893646374 780971396 752790252 450897514 775237360 115251371 483975640 593886828 582385571 295149738 265552150 436977832 684044206 517620935 673266346 380756130 36088805 869958757 325653175 411938632 194983801 421265030 740855663 360173527 921445286 438282941 403623580 350892808 489601526 574368513 590418891 966685415 479504991 721767399 951545859 590197989 695605167 416295725 199696007 57847096 842043861 486365812 176816650 808067775 320399493 806843748 937432218 356608124 8566258 658500370 780424379 732398822 158692846 431825789 135094289 600645326 319085420 108147572 673659599 61614345 591165955 330527409 157651198 416975928 552058778 133471748 953733865 874137183 436164858 336890205 955062625 671506832 870023077 627199756 841216540 798182018 345023011 710296640 204319331 134486638 900419188 967317841 802831329 531006343 294647821 807718880 951940932 553287970 766596546 510107867 269678175 567604919 469460652 321882423 982332811 208269304 819947644 696794789 292635422 755548724 491353362 455335208 691348999 572739131 245693734 382039367 155161135 541767027 713535104 948333186 434045521 233961042 829465171 683539423 586960953 189670705 13155443 590059001 730013227 212705575 894560685 625384721 945771803 109866271 535456528 544530740 538591443 53097624 195260880 965706052 898773099 828549031 44025037 787025457 64171301 651547458 788783133 534237991 335801572 514557236 96725381 990718148 394175498 357137940 933884411 314284737 886420387 713996972 235692944 241256707 241717743 583297505 119126721 161893468 499208266 207697904 157008247 843810762 64083723 570653745 533738903 380990014 221871171 125291159 436984174 386874439 581137912 310885717 140232145 794922013 653185606 681257134 839484410 660405410 64963125 64672089 561304102 391518095 103975058 444288347 549008875 871192979 405240572 368499139 8624445 888441196 10370437 306022163 740333977 601490262 907582280 143114203 665266258 590672410 444734134 874129678 317287384 969141395 209294060 687956840 143871189 635599227 213121076 748187235 466122403 71107333 988621887 846015260 16989813 27322585 376376125 580714537 121355322 24214086 149361048 593963682 629665367 934581317 249837860 957712946 240957650 113434808 699637814 470185893 452786000 41375899 512713160 428441595 862221397 381654777 730517578 887640891 445170522 471931687 531166676 612929713 739634489 26836108 82147110 457148649 911068938 588334962 182505841 351770107 425321331 60690099 604447790 253876815 372893889 968075907 378684376 780028815 910073072 395905341 162595298 894606424 540413673 21050762 474786788 986770203 88192226 595958585 517530926 830893642 42450777 472655581 952617661 122008786 721173120 805825750 640826908 257044827 46191169 431017756 68964620 760785591 286421264 925536825 668609598 693230559 768828822 981362333 472024983 323501556 595325760 658706629 319767636 188330514 750252274 459017696 356411424 211053665 836377821 223825863 813796084 825662259 505277713 609224411 521130681 962448760 992066293 488796789 577306556 169428049 946377639 177633216 250825034 741982364 524246290 383429972 628713259 777368657 153773482 617105277 449725846 26833483 726941278 795692679 740504666 412925419 919249667 403350712 430518309 608915208 654307757 966241341 673019128 251068234 13547495 343237185 669801971 355562946 111076907 714572308 186338992 748409556 552332081 446156294 699065777 371866484 278984544 323262916 815639935 178436372 740169361 907442732 183976604 835840206 330745191 624003315 248761821 318818260 318532740 400291789 481369275 365389915 934176829 730798506 908935372 221515232 284513930 475088705 883446784 710774357 665668304 290482281 710257606 449828118 833859309 957288577 577598412 639974558 803903642 176875830 98569122 399304422 277734011 307748850 122092497 660588241 966546152 636193473 543309014 778598411 198767228 349991446 75102137 304462321 961767315 415956724 560917212 538387571 521153781 607867127 873662190 363278797 281468778 243877509 87999159 71758088 905634404 969808660 59191491 294715016 154260653 156269189 698013505 384189551 226276707 235489346 370187261 861666614 360756965 378456529 424556260 110179931 518567755 418869928 814741812 914789402 957125728 711005889 927520547 659008594 144431509 736020181 241074658 924941095 258428917 770473344 682120641 930584259 672547901 288957990 1262750 258810910 200571253 135054800 98309458 200891181 163085544 178731582 967455854 40337369 579397455 87175806 88190472 309986907 722191892 788135885 646665897 408720084 102732385 322971108 644788718 173995505 42649526 585397810 60001057 379971022 856962126 408814399 777808071 876802261 45780170 714915153 530196845 14289660 383865305 314295348 90580202 85450871 671861048 783909604 142674171 375746996 840037140 881634738 890674522 547998413 297932119 145441673 982544707 467271494 961909756 137234161 809314590 601035916 714929339 517768852 242211589 773533584 425584856 658309160 232372928 640266249 618599509 308541356 467882924 858371904 296213719 396329346 804298103 711829747 121047346 522353508 833751852 503580601 375506850 277389997 759748734 929330466 997633123 518032537 968520204 636794384 531855632 443001186 497814172 344437247 90849008 317999738 177506709 346997538 174701016 280617323 501069291 904421196 713199058 797335054 79640919 177707392 448875058 111176771 965960094 409844700 735276050 280119767 181039778 968935773 530899015 72969994 32928508 919702978 132197632 965239132 301590151 177184898 658643082 950374371 175863903 798337734 58096876 161887415 188749994 973359897 351277911 905554746 620374195 665383532 847358502 960274334 866608087 310683126 24391114 12680960 126122886 68853694 851069979 905986801 290691669 839225923 439753703 901982327 120288827 559126087 317358174 172405457 945977508 232919412 41141581 735933614 433099133 362123241 663499685 178347873 121636847 681686477 363814940 350914268 18811627 3217537 341860887 682748946 299695191 31125302 986306178 193936114 791592618 142359438 457078988 420187224 107006398 982305714 927059502 106014562 746522745 41903767 334015833 524260901 250780704 917876308 968413243 185239327 787068172 546001773 841868909 727822094 287563776 523490749 524829319 862742103 50787141 693265355 776803538 540418344 698145883 472579903 919222254 303704829 902051159 554394452 540248780 536932328 803109154 865988752 960996292 967516687 104860294 370228914 793951835 446572408 349162452 210593132 600342765 798607229 540289113 89385676 572030368 953637542 474199659 645707923 584348393 966155067 527269511 785319561 49130407 188982017 35299478 193906306 340170400 425337304 156735619 485148290 306034685 82673626 403530209 656743582 119663897 150041588 712980361 992197760 116468500 976070554 715175958 998565040 346001984 14590710 369188872 437371533 227288745 782505825 323966128 556963881 239382418 568445031 131423015 295918871 917569950 723305844 231295622 221912764 688595652 11442996 203770222 183024192 506230210 541384194 769220773 853093007 907422674 245462794 673756940 668646745 925161418 458678490 954388684 243072613 921379284 54609937 970267669 230132187 392218276 242821961 247919451 115818738 582367255 813904947 694018803 737191784 127519306 641845363 149216232 940444556 80968429 846506254 629141784 645904507 364257754 106005832 576837499 966116789 429812744 989174094 990109681 677407109 534604534 377056128 887686320 613921496 846223897 955384423 244769894 593579705 593415617 81333373 899598357 583583605 468036053 696022279 183407995 233802634 6502296 469678056 65343382 188558302 599792684 629042343 739356734 895496831 887143027 233053719 866208954 933296904 560705240 335479877 553791642 170450068 652193274 352396961 241593842 592229069 982698417 704684252 810992852 969974711 531076237 197019684 67987469 737218155 201518601 177936743 485116072 738699496 64610711 487196763 999781446 650092989 532338307 753027950 662961209 836965777 842334401 258089222 775949079 279767885 142178085 288807549 991972867 743229714 28827025 399446308 917765358 431902670 505882214 92095975 355121957 55546278 43263851 331556428 70256219 816257153 264363285 127441045 366216929 930823888 248657313 882923472 681380004 952531208 45800903 443056165 274680436 108146068 619674545 342057151 638983762 736715147 296546951 943567964 529476386 249201956 278449270 343162353 924937698 18457823 399888781 628594169 116319465 739776332 681181907 953733278 923376928 462217204 689031447 660201054 434953593 310417988 387872974 37804120 236365723 152055833 557581135 760788312 870666103 591209047 889463822 920642762 325430174 785706321 553307217 71205838 106508333 122336679 445032575 656450864 641647212 892518106 765544031 2804334 474711681 684037737 261535742 440839975 222639682 978097770 452474417 825126603 992517205 28046210 77902444 212801427 71643717 690297741 258288859 80425973 23905336 997862872 760495316 343967701 123303692 597026188 786700395 34470403 386174730 183267811 65030561 891116593 420118229 177198310 85168494 83956606 373701341 501745905 490669594 767004457 938122067 847555686 390855947 818775675 534822310 918163226 669324191 328903616 686997430 207086550 756479198 116432984 581633755 284049522 954707567 682138178 802426833 369456996 765764204 619554058 670802571 720629332 79083621 207876056 682959137 799604678 307408271 695912121 596485959 643535823 679636914 486285321 5916394 450764105 690010670 430098708 578325190 588996151 913853369 568715464 449389415 934179949 721026008 262491797 268303345 765288042 767891799 59854199 723154424 161341950 115025874 931103921 384686160 435636485 888304034 981136389 807707651 205311973 422007375 83413797 770145212 673409485 855147874 985970214 46378539 132840125 975029929 620238305 65048767 527008551 173351452 440323020 354096843 84195796 750190982 654585779 870533605 304497096 883623742 240404500 831787349 640262408 260605602 26348396 463211509 43832470 479685403 217361348 341275207 808867776 71723670 356994765 693292657 903185522 517274756 47439764 708369262 328746446 523548953 561415092 940396811 22048498 427733478 675117735 573692405 173266580 229544077 550916535 262293488 287163016 536354004 583253896 410199776 51747456 585289019 103947692 39601720 494792690 523969797 316730493 461632029 90910667 757371678 354706599 107940663 970283484 245171273 330691822 469717610 88899290 283021037 79294662 1626438 641577267 806708713 620656869 917603333 897423165 835755515 155944889 114688588 667395872 946635673 187379503 757844910 45310122 313346851 199883089 750653884 697399411 17242921 224592117 64529384 971320424 627242535 578031423 456549345 482093505 291022012 90142425 527859083 289937867 934862899 124661317 56747355 728217965 422035795 122929731 359993224 452755454 113661688 241635534 991817311 218891999 569023710 493392484 767009133 960965462 934491201 52027376 820473066 714513723 626324253 401196454 493164729 911467448 650816557 550655609 683044481 116849727 943875567 534292178 143828511 373146116 952652162 659954979 868268311 697979232 825880259 878020189 443932302 425384722 265520627 358877658 859195310 519971057 639498285 540996267 81340367 492013640 71210996 962310950 128695271 257494593 356939189 917225472 556216649 770780970 63309114 583569551 966691084 85862153 194315541 42290684 894640347 43055965 103251318 582646769 162397885 243043306 934758793 72191958 186962952 117826406 727202594 471934978 919173703 353723779 437596960 925179087 678411317 453052687 599051707 336792977 300386968 195535494 553047970 96279592 613407783 811685901 110695302 174478066 323399892 369472065 688536322 593846238 594320901 747052136 885714510 930135538 223092546 267883469 751630360 745047179 718044452 638367956 894035643 442716855 984480503 415104642 276562432 985307033 554765249 554025939 762427569 598874660 444244557 402033044 126192094 196686603 743719438 877912889 974528227 619373127 399820074 837449702 648307229 4478227 610189584 282837628 9233986 257909742 859218993 109147589 993857626 861038786 379113592 140529748 993210854 293988261 841526913 979635924 39394520 274579422 735093081 794020544 47375919 277728816 171706732 62235730 205355101 9837823 849650449 794081622 805317748 550348760 535318562 659995812 228856438 922388734 29915744 726527408 216850291 649998808 618103527 784563406 201972851 863297351 751010246 209184482 581137115 260563873 233603191 528487841 735686286 299956703 134557808 559698906 111368259 67629640 758980928 602876778 110117980 700206056 876744869 407505202 580269302 15078370 96448764 636769793 710463691 517394571 661928489 734081137 21319773 727925187 161618394 854200496 2726809 969607797 256779506 512302127 875893444 870406055 625293842 253433754 28680352 815419491 70112954 544988185 914360777 460827278 225442943 284344001 109405917 331008809 722893552 614410724 810161370 589035425 89532683 185428672 113722344 714219023 759708295 99230723 134178421 458289004 327036640 662655982 185964054 175148066 602190586 36060747 651616110 961972764 572170942 399199714 467158865 235732529 144126464 204458332 835853809 299145414 885683804 313340087 159516687 83225835 140993967 959951867 985878662 136051241 865265201 832723106 253785388 811729708 917501117 881714839 705101338 562187645 687140624 338340636 400290592 568437321 872158312 601993077 908479411 144557708 986570038 61343766 255551860 366454877 738523463 922917254 496314605 158279285 696365580 660712880 744794368 148541274 245643261 852111934 637115899 903624384 256329067 988419537 416829447 178420051 622888334 766832301 450602794 211359367 746706741 406462681 126551397 881654806 663006310 411670898 670009658 685564023 164259209 652322889 989081779 494347434 253793981 506079309 477519716 525378865 560243726 312611691 993145316 755588330 37845395 578809650 892533854 37359867 251324556 166745579 212154725 939746022 5501517 280108607 910923684 117842420 680590126 516970233 254162775 188084926 923650894 601265806 723385386 284135964 356390739 619022059 546121697 360652127 840194456 551605346 495409761 426002152 521627693 36686145 300718080 630441453 421083913 627654603 742214047 296087599 676552260 713307186 788113221 249728491 998344965 336542508 291728159 960599763 468165724 61405439 704416895 195272091 886886786 416354296 616782370 433916049 171555026 59939791 92382666 896921305 789256546 550736010 280742357 529757003 853607704 979517563 758743795 906994029 690362401 412241271 261205131 40636738 156508985 719248141 751694899 376069409 389255022 623639369 383660635 247601059 744268206 327655976 677856411 800080094 110118538 940670507 632800622 417252383 425680273 750564850 985187873 603883716 362412433 41265823 119769668 248304786 116739105 938016498 519534282 528138218 714361814 223702608 692394487 590135233 654126993 162897399 535863524 428496853 970921043 815859157 303900318 265933779 41354232 948626321 720686999 6491616 839370035 681144617 997768065 120564735 499280833 818949573 446570374 97949912 622218286 330359998 614779333 508473596 388346937 794312397 402613013 624167096 795857753 455359446 9830408 508409686 412840197 43704977 715395381 539882373 273701064 84367816 415183970 481441484 643618004 711366727 216234927 805632253 485269159 976369154 459083153 136906375 422796550 180771854 395210643 123408081 716481780 113328101 191645156 333470420 683430791 944823924 789091499 198725389 169473714 808424875 795329252 278074463 300982008 515948661 823628105 728775608 285685232 971319597 574103223 360564904 488061592 331510209 92708942 160419399 841058759 336743419 346979321 94131470 410682069 603266279 240874237 460239566 464958735 981528651 707502913 71128055 635775581 992832687 744643967 138993581 600155247 308269758 402452931 736497082 615515306 497190961 480097029 85061940 207728114 785898164 471330525 729867133 335940856 446122790 841115726 640666750 260838226 824699776 652868713 998186086 923947211 637722154 821774807 402940493 571862282 45192984 820256327 209299003 94165108 176093898 814198119 357771425 307571299 201602744 456323379 170596834 958212145 314536131 333992858 294775280 910920642 820891639 722000432 66796962 135280558 177817080 193937115 62599858 988106860 494313801 985491153 365496142 136637914 921824379 275303371 448729959 973164645 746961777 47642515 223237632 319703004 736653833 81669728 137568801 336329439 396075086 671084892 657305358 17914038 372816757 119630365 550130621 240156884 206213360 807931902 899357517 474238221 812413702 336181527 646091889 123137256 772417311 714168319 333172310 686457017 767254316 130917819 365626286 778024088 694546743 396193038 975327096 558714398 225255036 122274064 71958419 737618176 758662506 502941944 609060405 422759121 681939097 617163355 647336479 762538342 431460472 271543849 973927776 462733167 458524272 854157150 776522974 82899031 646397655 601536577 122895714 893939680 546052773 350423644 740985435 39008897 921986000 213061502 840486592 280694613 496357095 445211653 23945971 824838908 108487719 746799797 427333627 318455823 177829157 23906118 197577263 267323767 849249027 982995604 833902381 319039325 442804801 914915228 300049062 405404472 573677578 639894169 177228666 175222724 917052570 428340155 868807996 139426522 18674740 752387148 422909649 142156411 717211925 387706237 300771246 420301837 172388079 23242567 183181505 603610535 748928764 621610187 453893049 106482345 731273181 601346134 633258369 153531871 938507332 360887695 88785246 981916604 465990151 37614912 607571983 287332846 974918778 679414751 994987893 485845354 898030899 654097249 794366066 834957493 852756550 870636917 475060443 514352376 95649686 454542866 239573645 32789468 75116 886579853 950999311 30852866 784902535 926807047 172310051 892808219 207545337 245906731 618921708 885702688 989664067 401013281 39388039 854757621 427036314 479748452 494691772 351271286 757191233 767987032 591618262 439288396 397686188 59805756 201739144 311660725 647723439 212133922 296922218 772888997 511943712 875505302 256013582 569254963 463599929 313684069 387457265 742658349 330194373 989524749 394770535 555840578 163818200 111492340 859891365 852552695 282590131 312278274 772030143 194552212 989120077 89224959 726777002 590285260 854244534 296633221 567534992 900745551 185870306 389237314 269710295 620272125 608787665 50793615 902884111 288167953 760902373 547591506 469276805 464015199 93283764 838438665 16327232 747981362 666042227 289051262 996245865 764565910 608324222 172306983 189428039 441592385 197228754 931435650 688799655 136443041 829880326 939464141 991263325 401588748 629737663 49547994 181040790 534666275 619143037 182763834 832567736 558308593 950946875 964329652 251739621 742403056 100057081 834538990 195766369 711946747 68580401 156386791 304462439 358204317 855010519 426513591 427614410 811681582 952059373 715723160 550383481 759411632 37108034 429912094 633487463 351986931 166250338 156196239 827838662 877369142 639424635 958149586 399346977 908160526 639048943 519498928 77695956 272212961 268101441 624286580 858479473 905453480 637660319 279535898 995220014 329525109 2259478 838453646 530596576 22960812 554981327 686534149 343334737 34696731 121446055 478799043 606247487 567766643 131644726 177671849 533166789 909484519 801962363 605455704 586909169 149477685 55468986 12665344 625673917 516249706 689157883 408559654 230350612 847919713 558813441 187556237 233635945 45598573 156124210 720042351 767187298 243695392 224403663 179126709 637671538 617437643 144707690 556197602 880522365 41689287 722391307 16718656 578495116 803055321 314329249 469175093 603302265 460577298 635571518 947475854 373114195 499766460 221411041 404411656 296217 914462864 514562883 963555025 969406443 555175655 942716954 460470651 885894145 920605065 32683867 186290317 407990243 90228549 173635868 772856855 338062046 871644926 32807543 340836546 303763581 579027179 503522537 638529343 493032549 496632734 987135625 417881977 49911525 12159176 486198302 995395135 130977106 42817458 976383324 222311939 312292183 377834752 99469299 213959330 163208321 474032260 839054793 18293794 697750310 785674776 140814880 431963945 8642164 595849434 287998057 319361608 593301236 489463874 329988706 373177698 614157060 10215650 893533478 192005972 277548421 655193867 980336366 208865610 62969732 843092582 548608516 748236028 797876151 375608124 746808677 755447329 973658593 645343546 563019201 993715751 146540292 519276821 79836551 70618124 434721915 837721760 687483535 787886565 225642343 877337275 869754102 850794405 151412454 326193621 495041555 222974290 140677897 704562166 683828127 701443904 908131118 425828702 788934541 389642135 620316019 694688187 991060657 638710824 798995413 190096098 353531656 878205002 938193134 423779445 597744932 675520994 175695295 77565114 529404873 560292212 721573950 561168820 276022379 974136552 85706792 57131702 675644666 190248060 202276069 281792194 462830326 807078681 482209407 288764651 371493646 316347500 265355748 312962148 3328658 846946103 187188689 305328734 836834447 483594100 833455878 508332958 726373718 877428922 44621925 137109963 669916101 499852224 420079789 507995472 413530515 604334862 933015229 833702081 773103872 227010851 830658884 300931725 645829782 228818650 207257424 645604505 697693766 121184961 703845986 295965622 962460533 545887447 105934579 120909409 194984409 5061092 124308539 413286721 129067011 424882037 113379623 477109746 425547964 159106987 418384637 93347704 117446189 978316456 491366846 469337497 913922334 491313260 852889281 855633996 525285241 639957506 689281879 612501054 865354833 147351340 449528944 633855434 669849732 670609203 90429536 533258192 457355122 594483134 541722116 712631489 447149406 866342376 478673835 772881292 862234312 379869706 331083459 373269517 89228980 659678779 123891049 636558334 885741492 821290019 709485103 918231088 663803262 891399576 77633301 614328859 147153598 29859050 473348694 951337485 537487083 21096407 254664729 912751137 399481047 912093980 998472714 866114386 236620089 269165480 159487424 569903982 16693104 127266033 494448394 770137868 936439540 832136612 297959770 704923934 816649001 828613230 538370639 324035109 315009700 485151619 408729948 564357965 989372281 419761611 904250594 939136711 658660021 207374620 605401184 223933632 118299399 767380393 903767929 167730181 898736498 480456262 362967907 837546991 820328944 984010076 667208949 286846835 716069756 346596798 191691921 926601824 31935869 698789614 74763130 366369646 689918633 216116494 733727431 467451890 982217302 349295043 164374081 636164357 388243991 701660964 861810011 337783181 411383385 43986839 873628013 658643489 619903731 428405848 967317539 940638542 71058837 927743248 654472325 333366403 685369406 669155822 264408021 755045342 306324821 222792675 882438482 229797891 847090351 462945947 498265094 30070617 112654510 174026869 351446416 85264858 614913569 58055683 862500025 674590701 34243906 371884466 944264575 96064127 628884810 100459774 589148340 705671288 622502496 175141457 375171164 651702430 712916898 866690707 850800661 681995791 433993455 499127867 345650965 8188281 459891037 448964881 393256734 518641953 767932128 140508853 10050851 188559369 563710481 907377450 906364624 132892793 420282640 811192911 926289321 867947421 686850270 830756676 366558516 227898650 327896240 149672465 501657360 902143341 351326163 866109000 70409396 90913354 880933520 342413894 668072649 391122092 831148151 633978142 370237040 422352402 98235137 844515133 952396346 80349026 88099276 70760176 705991267 975479113 496846136 933901532 164054586 653369265 810609305 682922399 335512444 530094248 371043533 116169580 627359659 176356925 754525657 93695530 790746974 159826925 804318946 762280863 573825173 914524373 346078212 967865591 221849810 11470500 708979489 917469891 950321879 847887922 824345356 572145122 727093927 916718681 590125135 165611671 376610037 1441725 565157409 741157781 181677206 957419460 875257314 786756020 845122526 419004969 675679943 512881801 969173277 441782025 323871111 327626158 214294531 101565387 290227086 546956118 540053345 452694460 296513678 322977438 788413743 787145528 129757176 896621533 686995147 275884323 851713650 994232302 462285851 289220279 930266567 354133850 230496175 608409106 843563686 43609502 565280261 704360278 726889295 967373778 766283522 924440105 530622976 158630955 899943330 851230247 453315929 957485844 442091761 583619132 537577347 916317809 274699067 643462348 165340880 187331729 346336240 358731095 150416671 669414169 246090441 243679203 32652959 258807141 404893115 169219496 727235337 250532811 674434059 520494701 618103285 792839213 46667375 62464005 216487764 632333358 469032309 545978855 6220035 431446978 186489617 80489062 940367927 409528535 114462699 18770807 122852039 403940770 405160585 420301766 768845161 490288470 242204757 221614293 690135802 482380154 861177265 398661660 822524139 36211580 804944583 45785683 296679672 747175062 431269831 344596480 388533696 569774947 363466525 359886528 30993064 889087285 937522183 511979691 733438708 634335236 260770525 673309293 144061218 809325121 555992908 145727267 571696030 433531263 952210157 936388688 579568447 474091105 778135028 92321599 405048713 883236622 276397297 534082627 169967504 905017547 348744873 287661084 91307027 616512511 926912683 759323663 459302542 631147920 872964372 473314293 898486936 330330641 355044780 583247743 71112366 831231933 366238563 915105101 812689498 250206914 350571236 142471549 539120725 36305513 812639541 264838644 710342194 287811002 378246197 13057750 915690214 286099116 392717834 7674840 890473188 596500119 538479755 748228854 575658750 564153299 697502511 11893207 146609779 970870868 191986036 478972212 996284790 383261463 755855582 934259289 497844455 518655463 478176949 312661378 132163055 899116395 445487771 76424367 757106434 651092220 955456034 162504132 580886351 789399369 33693645 241536962 10071678 794968757 527638882 207499580 151545139 997328473 206856468 577109163 421782718 474817550 847303225 21269987 898749230 376181133 634675580 215687469 353274500 109472641 194532867 63959711 289003610 954170899 28573590 888803557 452292856 701380209 895638560 763953695 625677354 992986933 969228384 514782413 82384224 610110000 322693448 967590420 663784537 581814222 159895054 84116638 320367778 900230302 195629325 902803036 111319788 34599042 984555624 453652192 413306074 999164667 930448876 997449200 549258915 100535385 898847455 974663425 975964518 739191717 112129893 904839579 300178438 538997392 888223563 904935091 698580349 621731359 678943493 194073207 979256380 128404834 2123507 305843630 143753977 832518144 370396289 801527410 738501412 917592728 330354263 964680954 197968833 358089199 613955810 47671707 698521743 255488380 472330491 820313546 224075582 712191392 696175650 79635181 571612775 440791176 361116490 210728744 921422246 382783465 970292392 781870701 573217694 358011028 874359333 245930351 199506926 588176771 174939048 582818356 86705792 353426475 3017044 964804043 248969039 257351199 564401132 377757498 61132911 244450977 978273230 88246249 272301823 876753739 88146807 446628292 855233142 853305592 374507810 326530934 136933969 808443084 571779383 929103725 280299940 777908487 402384937 230482280 822500610 283403322 300094055 422865823 708823138 350193821 161102162 699018991 891313273 186779043 221354031 242523117 770043077 14492244 867165386 38389424 326226998 741613336 497155413 60597490 850266811 848933663 462094899 30003245 103021789 953455438 286289935 34667618 545062465 78083051 39695277 781991160 220963129 542896845 386909599 909325157 387801331 693911262 695065770 345110523 728814776 947742843 331804372 953363330 769855988 399386474 926567348 463455419 820464286 668200570 262771651 80896148 274074552 74241970 561864608 740982924 740368052 334223322 369905305 836724014 586057871 68375590 170528402 957545821 471050039 335545975 79331418 311679340 797048388 910020678 720091616 716860485 124355375 289023619 181653378 343179512 167841554 47472691 889364456 715259393 301914963 8150224 623960748 258151400 909639714 903999483 20974460 138301262 200715118 199222661 50201954 564955630 702539399 217260748 139013091 773474847 744698901 748035246 56951158 943790441 478754801 357445559 630842815 332025864 493580653 645333758 423142759 347992295 555521969 573902021 321461479 495045749 339872456 578502370 93214410 565782451 86720515 147512789 974613069 886197674 16161824 402331907 656102094 716922556 949467479 536223547 21430189 991893173 944535345 933492477 971218015 785841465 450775634 161819647 93559811 137741705 710953220 876900883 985592701 68898524 730067948 410220355 188426108 602498344 877886397 124066130 563222969 825789434 186809541 992032407 888306914 206806435 830827238 40442165 366520007 659256110 448297517 10229104 375407827 138347915 476191276 752503769 706872891 728397053 661181950 209279601 964270442 672776196 643629451 727203656 395194035 652780352 7605893 166586373 332617492 101885511 911814150 100811088 241226662 214150775 163086981 854112928 752397927 733681583 329782439 8659386 200066689 786655566 512323926 870411351 278956345 564466195 438336311 229455540 353471800 282385783 712325295 614459378 43350157 671791621 96376554 112497787 777272488 328668960 311775838 305902559 792159437 664025852 754365714 752685446 584396820 40038599 339934965 50995837 460861276 116349164 692207743 333884177 584498019 722292276 116708822 29052756 605870877 842527617 820976248 507564989 529791130 701600687 490349478 676636007 424673012 550561389 952009206 174523617 635468687 16792604 851172196 353240782 864163808 38343741 564505000 649813518 354693904 495965783 372974695 870134192 296587096 149188650 338573423 801004491 141978512 389033777 604847517 109055015 96775070 98945103 691637821 687916545 321230065 204272916 941661634 252293406 962485064 274473641 232006029 210638167 755574069 439866517 792617912 953474873 43312492 389573338 418708301 53350241 804175983 963384909 346354098 747320068 266158819 288398877 951998239 560813354 822283789 775164903 536773939 240306618 531587425 290354165 407226758 677395470 170656987 141280748 866441225 930553990 210970501 780740136 960827942 261831019 964522158 955510460 520073578 198718631 534476341 114791661 342635575 594268272 699003640 258420827 500039526 338351379 676502213 571481661 304441637 476591335 378499732 234306720 955363840 153813233 61682360 695618356 601238575 417626162 436776359 291134922 726989227 789535379 838880102 949797742 370177108 955718143 604450232 636350186 66402907 512827386 237007813 908004057 647891570 222055124 412271690 981607737 661186031 665338072 306658513 725477586 623690089 541789276 387301950 808367403 113091190 375809639 502176142 15027800 608040201 318354144 759691459 218872547 701865943 534270814 450130005 917723888 909724673 818478704 630214591 160174194 211560342 858881578 770019171 926373616 700523711 805490992 145532301 489910399 785586685 215283490 560528592 796816847 454253477 714667699 163160200 13512602 990924908 971124361 531780816 555749107 774919239 453295103 982257876 871061667 900022621 190096803 435517039 547822079 69753575 129459794 981042478 547083801 195308300 263353078 286661716 930695483 703560064 144178102 131666200 892637140 811717481 222606794 971992325 664062652 912768829 272992643 573891514 599276792 364456371 406083080 426387131 110149603 561872567 178803480 983643022 11298613 770534970 823321986 807801170 464148561 351543807 888178739 293198088 836115736 355240266 64079622 221494259 314371272 514566910 277240540 983533242 567965851 242972233 656766033 645849969 249799045 68377191 520137681 848259651 596083176 894138434 42891815 357197238 435502086 634209505 272997098 322753410 111297063 943242700 360727841 225222966 156449940 162745184 624204455 768101598 829922958 328773713 58230168 67562655 465410579 954272000 143634277 170237689 305514814 772915046 71895735 862806570 487359146 613111575 666756657 947805873 808143763 894181491 128225975 9478783 809006125 165674452 949235212 695241242 660994750 886341159 943820377 831105117 734363844 908099428 127040012 817968335 235663815 640473852 144577798 80042790 720441817 213299899 839492397 218914822 631085263 510452886 901683840 41799340 9790762 294190489 302388831 555722741 618451579 719055495 324662258 548831287 136090676 534126869 294310621 743995394 818984135 277640755 731196277 456371545 825589061 979888573 592410373 414710591 72641762 22976248 188143954 134416965 441474780 286300701 615152769 698155356 145378070 67892362 298343031 3288630 396235726 350312174 784222746 757136615 211161552 196457303 914185681 47188079 592867491 83559420 833600924 866113290 90175242 879648822 618235167 184137490 43895409 995578237 931793872 49790217 390650587 941771651 770477558 895032767 163194967 22093424 325488743 932860959 945161711 231434626 991405911 763575769 234473188 266356902 251040853 367748767 747599566 166749124 672075494 250168479 596510665 980595087 52458819 133515636 804928716 801717666 928855200 319465747 616915426 99708330 817024741 168960962 66708139 699761550 460650990 74495105 603540602 893242698 214262350 507262760 728015273 230258885 107547114 362726459 125590294 64820230 937511195 101919610 537503929 559322644 245068211 59198798 518342297 421694846 604622216 843585137 77896441 345160534 971499286 54826098 630552018 165920912 184436198 181898804 855063711 707577352 156143086 150950801 696666345 239033656 347104096 944576357 726136350 44456766 317532258 670136074 544097285 873143943 276095167 356180300 835004260 931568070 810549709 977123678 742416465 359396358 550329575 351626033 993270488 582909835 337700569 81563804 78937864 862685566 246347258 970355294 202772501 133214847 620910733 460959383 785969860 757030635 953683975 384584377 934959797 281225861 219930640 939106528 909831478 760917115 114456797 642764444 47347754 126355702 85440901 103111802 76796011 292486364 166391980 537994595 482412682 234803915 19085769 252483939 322211082 377928192 52307360 762975812 403905883 820831190 641988269 408906069 697795682 296833995 20161684 621452192 863593609 721160652 945167941 535404356 623752068 622429883 278300555 160610507 189817178 83736793 637960480 471010959 390834438 389032897 231120179 574455544 373589287 56838797 184571016 867878447 133020121 72062248 951442517 905304897 65468589 126357129 188046169 106476286 873268352 853281170 182447551 769521344 453715344 630040956 882726216 986348117 691837055 599814066 466607830 693679304 550073899 629654727 745575142 303633255 365512390 754286954 287304621 590965307 722243684 954249356 295720081 353106881 915574268 531302284 467740738 240881336 235402755 367616477 801068377 318646262 421845019 178432265 480869608 360857048 605553650 807066657 372008643 42496769 490888323 815179277 985926088 638808144 708019565 423525671 278635707 683603756 514520117 795848158 7860560 205784430 830697890 11322081 598394102 680440491 94984059 164052491 768458319 442184547 804484205 895541680 781030128 511545 585741632 953979465 136537881 897718928 374305312 432719283 43235352 675389014 836839717 442282243 484151378 590639416 702216040 162135073 666616691 690689479 226057224 78064006 880451299 813455836 339302611 668586491 806162674 719261124 216236744 467494048 732957829 797693232 754701854 536215231 360009564 352749137 464070093 282583778 266115465 281318866 994638971 474167686 140671222 632804638 116837562 822999493 583401225 716521594 489617101 888144728 618048291 189297838 585755129 506634786 465957730 611438216 875756353 242732351 969114984 708600441 788476830 243992527 646264991 647628868 748775450 139850511 870849713 860546728 314969493 813280349 986914861 186954866 850590298 580290046 770982156 537331569 229068056 756308583 680112434 675159891 50915132 342265235 387579631 881863595 285175212 559730047 24612413 998812086 473250217 268179708 148905205 542250155 980290908 526548570 599396018 265374396 120226026 982852921 952881094 605737756 462334523 264269389 725642841 653721720 353975167 516914940 250046064 129457200 986116953 871922274 26271677 849116188 575651589 972011502 357972881 329183511 907977632 306987357 629450677 657874544 724417487 189894466 608347210 341078305 419333817 283208749 581693751 491173383 432286529 570127780 236292672 231489652 437404969 375166335 818728066 668078676 125289247 869570458 110876942 558504702 574374649 591836599 828262630 825985664 379897938 260699674 167056084 832702306 592933710 44614768 542692410 999244194 765830226 375653493 826854415 548815999 102967582 631042198 518823627 253795963 740399889 619131369 879389459 89977343 717097049 238305208 800468656 9894648 413853589 709450553 682181164 640896451 489859301 92978723 566902673 731115640 146209882 489081269 70222260 763211732 263126826 668698070 814635659 634607130 787225686 587811618 23668894 361309998 11352577 520219253 821607946 629796824 293919283 516452929 854929619 181724486 338792738 348653224 605702269 418417488 1258884 86978485 741585437 166015453 324947745 319057464 689765617 546330664 907544684 735896235 731702284 222501484 564586619 151695191 27360251 383886963 412950130 630289447 3576367 95347246 947091286 749247261 415975498 304058608 39052059 868858512 972395706 729112115 574390596 948496198 823228785 359027088 631107921 984082739 742114758 9656582 435955267 391262931 788021591 694979532 475877888 142943132 230601044 697966232 709883633 812270455 469701664 333478004 738158000 717263185 229831246 468473188 749148136 138225212 869015044 374611577 593490020 905454116 653969604 962319434 308762574 253655250 999462253 374536590 730527657 629903797 152392531 904838083 281967076 534564215 819627824 910907823 286431505 990766977 333806041 29907132 684511339 322159016 192664995 306438351 145259043 829498294 272058689 69774463 456820318 218393907 542626216 483746956 831916733 242536914 533208837 561040419 674797935 973608473 159937202 781155972 955233543 518465418 106634090 717997295 919316181 235240575 110434114 367885316 702729515 562021555 257985386 741801175 140107791 861163048 759887120 478103965 183239150 93851439 489598871 776507488 797222656 567202006 108332206 239540958 48787797 122225199 864766928 73880351 521825527 914027269 900495421 577589280 437559968 440826481 127982675 651644884 915061695 651330621 364230727 344109284 671252285 716581540 71321058 589137655 426976156 9280202 183082141 48552508 264406939 235628132 156404900 14727253 224427635 517782321 307842211 962684110 425322528 599410240 439660110 174931443 250070774 687986484 366252606 486482981 192262051 827343485 804557666 946154085 409686927 732839281 624387404 256021073 174120735 844603060 613031237 964926155 326269302 988276439 1778633 453296116 878840017 643178881 498443002 165112433 410892223 330545752 358123310 572914240 731956458 532512537 747480578 809741882 814509529 823900316 821099512 500306080 896199734 734062832 294522974 767807808 671773803 354094616 378402209 645260844 494850874 587079177 565661122 738783585 284400920 375249315 793597274 899531528 269410751 810515579 325882188 292955908 229700170 937025009 816217909 631208141 643506052 718007335 734549600 367896936 818697758 526388299 604088870 274799016 428041915 521761705 223489592 250513551 829161303 968160051 45829869 972088406 404146531 805664495 586145014 659260444 927366887 763638947 861327090 669111181 483259625 300398023 171932921 21629991 37746481 650707928 131128816 799206784 231464791 953777739 299272566 557126270 291207734 937516015 97116973 897783843 597780579 825327812 202320013 82536547 788595802 31657902 666226360 716295556 319748333 576525561 348879675 94079576 749200224 993172475 143739786 79227011 642260403 662681274 515742701 498747523 520681224 978430784 468742870 280712726 915757571 330798496 894553686 463914332 574387837 179254392 933582234 738233271 69602399 539229586 672987867 830074466 607984517 253157491 78209141 531152518 224082232 231949741 139408116 319597621 316209467 452081951 161162548 52189887 143205284 962866771 578978098 405881052 447971034 581238012 530106923 724161158 143836968 869152326 571144324 318306553 511937669 104888412 537108945 839830070 622618896 585150054 11610020 160899495 509760841 333866881 897601864 388748778 223468049 571564954 512619083 782927274 503266543 749667043 909844927 932680427 953496567 418403813 279947570 145938089 299743955 294922872 35686035 67999450 218211606 883811687 739166102 464542921 955797563 163410348 415312734 496643016 337178951 583015813 697488690 258632208 956021330 936449173 5474820 213842777 140421430 362043942 381020364 45653371 506468719 405118222 633990111 388129024 956857181 512648307 258419796 466252802 711197420 611967415 740879785 166439747 696765514 779816703 262600861 575456348 633406591 473680107 814173084 505421220 295292335 711940490 186972585 549747033 617238390 472959528 425755153 452875712 278928277 853539301 66712295 882104748 656998212 512136789 745482607 831832318 96850628 170935811 393581353 593935243 228250491 253479151 816025060 784437342 296604295 142990110 442641036 158461955 652430466 441908090 566852239 467142674 470752208 606172317 988133325 237107376 381568386 694985050 146754999 293093286 399744017 339516254 978087892 739632350 198885206 311241972 155604353 677022956 518091080 594690414 276747342 716012132 293656227 344372711 34367061 260010804 355842659 318132728 482358850 278332497 155690669 759867650 323278848 790906105 124135021 138680479 730345346 150842240 198681876 72710881 341344530 897406639 517498243 972030452 602303423 711433278 436859129 742837457 244633887 643610492 878313172 215109682 809152035 290563481 570219368 718861849 93346270 642435326 285941783 508235131 431959671 615218799 833172348 728441648 32764386 840836868 823130159 503053341 356967578 481837980 838923177 752805627 397526855 589702545 728238880 573788710 273194461 543853966 164610509 497478785 169421415 343821634 673314850 189913023 426913071 451797236 495623287 13943912 218154116 884802493 625394265 809163041 526525994 758151256 72577545 91797229 216369264 47244745 605756225 757492053 870091708 339886008 291188833 818727259 782704429 904876325 421560991 241189494 770461136 498541621 582135919 714951306 415151563 193010335 203282414 411591228 262941106 876523372 618047571 497297272 892642250 788679988 682698541 45698912 974984363 542042991 532152537 801121250 659628606 998457337 925324498 583898027 266030176 933677659 849670858 828806434 399043610 897706416 673946582 601373228 840913830 912756019 498509055 994770100 812110096 18281483 367031175 226470206 235452217 501227807 47994362 122053899 888852717 614464311 281414419 735753954 779609940 422459168 102424846 173076302 305400897 53503830 166379803 956843816 108850610 388256953 755967013 187144300 68689074 627737155 818048467 56044398 561791127 339994650 345516831 31074852 638270982 961577508 299275739 580922741 918454148 368601084 787726627 328475195 638511295 243506266 777621960 135324646 931378376 970394382 587252677 954676486 21096063 908900404 680232917 625908336 551364475 908114847 82424399 826335872 196656581 574072173 916763620 415489583 748161 313722736 769792637 348454986 789952054 702082304 746148623 501091569 810293160 589232661 860589457 535772391 687837261 413586324 904276875 844670385 411034599 519617888 972077396 912637211 111780618 864931244 356364007 546821708 89052776 653590723 999905628 712617449 841032051 662141975 218717107 445203080 850109550 317807499 637899780 180245305 243087577 903816646 447854712 139945196 634148895 169277477 793952086 38266537 636308440 943871252 706062079 747311477 996177606 13645066 299502077 95108515 558526420 38282449 72381810 556966804 499684747 344230124 625932193 277627179 160277311 729968877 329277497 905761435 733490172 891744946 346632073 533634175 170526839 711287496 397369889 573374673 861448533 411881724 212857938 36887782 342114390 943712752 330731942 616631675 504809291 698809177 337840885 323579567 798494706 516141542 163142315 690079100 119886604 512884942 634694405 874308703 494337110 10061778 936607685 920938362 43904269 89092151 582712306 196243186 767617046 283483009 70152121 344914674 881799264 420521924 959249442 749068927 889599533 913598449 54205139 194758888 84405234 201571733 470594055 736906005 814420908 828563059 479640178 634255545 88295742 407865225 714814624 93826244 877576718 329622933 160881487 121949802 148554766 627330207 448144172 840391043 563983275 254066660 847420059 549534674 330512027 714433512 379989370 806571045 725093965 352901425 984844654 313211641 153993677 394805092 794653978 673842092 273742446 935402394 524419637 54663588 515040354 14608386 444321657 607500740 161114155 447300053 187807852 406625012 953359629 916049124 908496064 185489216 259782712 733701014 397008306 872874977 848322940 587684636 678380022 131735514 118234919 795238439 523655480 829962120 177252782 202819499 547972800 881793186 919305775 878955099 715893319 515362754 259973172 239964614 772796537 950830282 437418265 407064906 761007740 916802248 396521175 778608135 954819303 441696513 462489258 542365832 463501686 493752600 152658872 784080499 476344033 848324792 870140975 593573502 540952472 432808558 318125462 250090164 441212931 501016001 553862226 967744664 880380947 367031094 79310091 531960593 233979354 958557342 693367425 673921227 527989301 88990244 638263488 695961555 181860114 303881644 261492159 752594509 175739236 507881980 10367875 676778956 498738499 566122001 135384854 543615512 504175902 573668531 217613558 576159779 143454514 734513028 366187144 384072483 11336134 624454332 876042570 526848912 123647226 47283344 566346175 999841447 17606032 997527079 511782968 639356893 430014191 681312236 922940426 982473907 110495525 534213690 63040870 917828597 150773239 978210282 750224399 108330168 978232982 787713609 401630025 706953624 498928421 22840975 152957653 380670674 145152624 741154480 922106127 835687440 978585 422118606 595538566 723321149 493933420 394167798 411744155 709228784 512106101 180429 490239227 490498269 170496998 555031559 784548469 563848463 390042185 288130345 740228300 775243298 882887791 142111417 736789440 66802352 386885535 708343216 273714899 968129960 371906603 132281201 182428894 712123218 35181988 10809269 457769920 620005088 359976432 706261895 718101246 322540457 870180934 578959210 345528224 403641996 532830158 578217387 568776873 367163432 697622967 443065897 865633519 132448803 702948696 766379286 85295460 855165028 308790273 404620478 511969568 8399632 888596652 958237904 583905313 187740139 914033296 454224380 747221308 145738241 552274181 306312550 580005652 426805478 853910967 668141270 192887944 548983859 469875388 157595685 27862557 436417673 24974142 361064014 881013178 180630936 691691142 385595146 310988372 348250597 646918519 685533107 162181403 791753156 177332610 132286126 218947226 553814972 382810780 169665173 447008206 864070750 550387640 211638904 197742005 122700453 414665145 229824701 291115875 761797486 240699474 452844093 661149312 747701940 318906345 349418558 302977243 756908621 498479925 419633487 836123147 389309947 891479512 408439250 668719359 351679033 880507770 927258542 733684898 297758231 849263891 863500885 364970526 52446839 789053000 407810812 117880924 174111261 340059040 465092901 794082327 117014882 398521530 672262345 391873356 110381559 711705767 897531359 545842684 431152915 252634851 557401682 381020914 513464983 542018785 101229326 308609118 576485485 338330292 989743650 321746241 755766974 305424512 442086415 176979928 515585906 436925006 669761856 186819403 548748280 5444673 316695546 918827664 584860670 261233263 13054748 601221927 263216277 12352575 366055879 119567609 579302165 570310587 368855016 63535508 436470418 358970153 152848272 750513184 468455815 58468745 281480770 331922540 454681836 178419818 658103695 999686260 505611240 815155215 749712421 992691610 733706284 987906596 162527058 340617405 126141651 461195982 46295261 756274834 687797713 593498618 974170509 977446206 23941443 860076400 786694489 80869700 835522093 601652122 703309887 958646144 675152882 383467516 648520944 389292173 363757290 364991118 307008223 224805353 460245870 820090775 260166206 804142004 424530740 341166039 70210273 930201374 165563720 702072046 235478237 309696023 853929048 336969215 381978410 742305397 901906781 62512587 303846123 981825888 236134913 481518485 784988246 861789100 635177903 101866479 738109153 983271580 667315698 143011800 285185515 629610374 166669275 474252505 457533151 275396938 593613692 165625817 248390997 387581994 504059599 56988371 74897173 146957778 622610473 468496566 829038925 632529118 599652799 508297547 433730568 882504188 646162915 394166806 713921403 293334507 43953514 427091192 831758193 974861315 97292192 993773949 747848002 81049715 378251748 307347238 801966696 174418124 48248218 122306649 219172020 762129676 466492409 489856087 101725353 705431805 873264974 778286991 561030725 221814836 524437889 60055 285078951 527686051 995557138 329898867 500632507 502597237 168590233 522693079 848399770 212407581 671483893 775614140 135763440 1890068 477606612 71127380 457013303 454238671 578328425 127970445 35688792 996062683 133002643 10060791 650900056 179835661 172092510 721282265 306392780 892894608 998760394 572878332 972726743 579308302 691278206 464075977 728989767 618588704 358331343 523865429 482052150 113636047 290128620 733506618 654627326 799431486 269900579 332241460 556213445 672125442 30306979 577604176 98316077 828096971 424597256 485774401 253092142 918958735 474065252 79611813 386681567 581921674 553912323 505629234 673136477 199404223 60092591 669468915 117847373 323680323 145189451 799774040 696463490 605623260 16547536 554149573 725910672 932414353 334591318 907101694 247878192 863170758 974031427 626557074 158847083 77587759 611873462 681483218 845039960 309774772 546312969 928242041 324553562 369790880 277680793 490324996 460342000 612472917 102866823 19887170 307416670 495653144 717034759 446920483 550762132 900692830 500700669 504230209 705007050 195850494 717847820 893418302 34586279 62805983 366205944 413386644 231473472 115914158 414351471 128143800 49980959 614447357 156930335 34613180 554942557 58664993 876404863 675136751 332950085 614012105 797399686 951576003 887936461 877873499 754995742 181225136 654954179 808695531 997871723 478125415 529073742 533376274 128474724 925163573 373489237 646761894 196128174 511901594 899944793 952933626 180703502 146171656 264259796 342560064 233023298 450811522 510715766 754418920 459219253 528482862 326429944 787107187 398582045 970764092 782655460 58914043 492967548 445821142 748361265 286095307 341579375 770325237 575682468 128255478 120905139 4998648 742317750 954298197 451691100 964850536 915326210 353039382 590104966 619968177 597755427 198647751 602244579 654132453 49117970 931475729 128891911 361115961 814913996 722701980 521201820 278964681 709093792 984337651 293248747 49999894 571164487 942676527 838912240 545237035 988052083 58022567 269097509 785567153 66437286 147644473 845265527 963821268 556683203 801791869 76916607 773688063 340816410 624279206 834897083 164237889 23108242 600070856 296728485 412261799 335956720 266172864 898789915 140392866 873217523 866462286 278214325 578206636 255767559 904348491 60859009 2379627 75849242 662827384 856106164 530218389 927201789 974686023 634893599 573116580 166202599 754707430 228566841 858493869 378547868 833075889 869164733 937759078 45296552 928155658 858652122 696179913 279935915 280257846 985110754 486992050 247620642 291169381 225958701 997005212 948323183 315908344 98786111 537063472 155934859 103033880 609737288 303341273 422837720 47813893 838399628 597589388 134608927 948326823 901113331 2024796 156343598 43354510 381893006 664952126 768507934 426336444 997190332 783865166 909191974 430106519 188858086 89851896 609223045 997472502 541974530 708197881 98681439 773131859 656433401 432070329 639287625 570044391 19182531 754749162 343634197 763769077 264261821 178722133 430442731 146430257 449127881 723196600 257689276 104697401 181092906 81072023 413155714 932130854 697851712 443551506 899417777 218931943 89039836 150618407 84552952 299508951 600021496 635828744 923492609 368107392 266228801 639458754 808786279 621107424 475300185 852689238 761601488 193367747 894758239 206397114 342619571 766765335 919905297 296236990 435977843 491788242 545437030 370807160 267243702 740931038 319089807 270158801 410125002 632943170 144938243 965570027 329239721 687622725 475377031 74385612 144853462 835374652 101332490 64364855 617722441 174521719 939331563 840693247 462538468 582730551 847534060 638104562 87972177 416025941 637170116 344121836 324571214 219503256 527284889 802482405 875939904 466568906 920261306 120689005 745617741 15532604 210327769 522087639 15735930 135788883 811202942 703336417 169488362 52379443 925470251 118183792 516543806 525196911 981924976 283232548 290435735 343790749 146172243 942425631 207490104 416578760 87724764 485927933 276294039 969845749 315983517 484972885 905283683 836876173 60654511 754578268 148293729 671493278 298833204 567181422 28316253 763309424 295338514 967749628 545693845 444131100 329930359 373963744 245153584 290285527 180870209 171695786 438112504 536608253 77831225 201305317 774586726 328026914 980943784 637283150 414316951 119239472 516037577 586443837 739139214 453964406 628556944 419535665 656549171 301838710 167866548 722271690 171209599 95055556 993270041 931676345 593488576 229262935 854107483 757215349 636614540 177477505 387741626 986435587 507741572 313882474 670827092 605524515 153985144 390987006 456145992 804141278 468197939 247795682 700239652 286656645 568013976 59430110 786470126 108236958 63913191 688531676 996541793 421539309 777084588 899378223 719782522 5498780 288321343 883826131 738173001 501736513 859656008 807819368 744090082 186678289 734839677 647719343 404446589 934624017 309576561 900977979 561327194 421817221 28690516 126107665 391653205 346754548 732486898 649455983 759968826 554605551 34236525 972232410 703739595 555204877 656590311 360735812 185854351 711950039 452776332 731140228 889212618 231288513 845323967 725121565 887679455 617856985 186332941 509508318 177504857 41443107 421159986 880380460 928440639 767771329 967883334 752401890 976790620 640090398 324610816 412928189 940183335 863870575 781804504 775640379 427159335 724795083 817785323 165834279 537826570 990954185 382901270 868475677 372918940 216105166 501462686 610390565 687683944 492576091 990447847 743037245 853927877 755419450 420910387 419924939 981077939 317771483 906966058 374459907 467598771 566584027 862723089 844387728 810096447 52838636 880457609 208402386 551405825 253621599 970594590 778203497 133441242 815997920 129355108 614978766 128502161 80095676 756612160 120843245 934496923 419784165 230371454 189229988 92534312 254921501 812167063 63669647 186596497 262015497 537957543 5223914 388197413 353848874 44250434 922528033 622519830 572143796 322819339 289425480 791344012 801436230 533455943 990322956 859909639 530493341 120720846 478855441 758775395 720388476 58795568 535372341 43032982 467890049 546405967 414569009 829288340 459251338 319651244 605973197 466951847 988137278 508218435 544982088 656392055 865976489 284342700 181863103 192430146 41050977 711518428 847096316 467902967 167782021 748454447 202005380 765227602 108303759 995827033 69340592 90769725 774255349 368031137 910257667 562233027 30030464 843630191 963569796 380520433 623170375 348471626 699322239 295033171 161764816 104980779 52139868 829380873 160851079 428643048 368009820 870487763 624799291 143533940 739408932 950379293 41331615 616241729 840762203 787322267 8890421 844161188 426783036 687881858 498556100 110328749 918815711 222925185 51890362 601276513 713955074 56804091 175519951 566642345 30207013 929633892 722993364 710084062 692143065 267225649 962241535 920026059 413481267 933870028 791373718 688706941 4355358 613810332 849491503 173979433 141843911 593160914 192437942 640198838 955919884 586374911 685748810 545788903 947533670 610167711 134982802 215012388 312187616 65933216 950178577 926941069 166933315 606588815 293816903 209503544 463931835 327906388 553712316 198408533 370159786 452095097 155121604 990841843 551709249 386821 476142960 883348016 610924449 917215305 792589755 292279517 385224030 119323727 843421946 47683502 561216557 47425764 116013234 471786664 870781954 847238923 834227295 139106379 813450396 871411834 872018025 966516873 389299283 127182049 925178319 573728216 652903973 42548169 524810689 21415581 857761649 229784599 967787699 17485443 178524695 270550697 281433465 712307295 523093617 968088065 158512777 560893633 524961551 372629169 280613515 432576772 542117010 548687935 677334085 453656864 256464940 791518827 653857344 366577243 217170306 437583646 184980878 676056894 108415615 277053458 718730573 773856242 572366961 133117551 69932411 631107562 712364386 457160464 288930733 151433018 841160950 456964138 178775934 523967788 532656245 46711645 683531379 145544699 724318255 748524433 911281069 435210067 270674090 527831596 973684474 651501182 966319502 142162720 392710595 642128341 625650503 711715637 114359508 353038922 882492861 223685655 594305915 611655353 95252327 990015813 447981528 269787137 402616810 925873122 577165326 788572977 759777682 314984133 688601496 489071643 325774274 844837490 812102439 772095079 829811208 680297139 615197424 237718988 639585623 860228260 679020841 594250416 949335754 632733905 233068140 127764341 89301255 956006799 301597817 265298534 989346595 211225085 963151574 413599466 827495172 709545921 135948906 532247632 101536112 125101455 913338397 726675628 548922213 986358813 420830837 979680348 538410116 29833916 128419484 345949611 108307755 987826473 313276709 612794540 676622618 110128689 366251582 714143553 143688238 797486201 692279073 163169549 325219536 21337008 920473776 913537516 691054907 458046308 530433905 488689848 164408795 410678714 378272674 496599658 767009986 879055295 217104230 348699071 643423829 696762254 263750154 465253383 488420377 283466890 3794498 891451003 288848301 637328358 103321313 290513824 694518240 983740429 798710712 478615209 277498231 117927180 268440576 870978087 473238008 705363211 705330189 22332207 945439332 225248771 507946184 163554162 702300788 624063896 835692713 963023119 107085533 447617550 842831806 879380706 97366795 735632545 669809520 248651189 909627433 609353828 159436361 310628053 171560599 718744345 983092805 36543004 794262110 216308936 379373568 651147981 533901914 452748576 811771113 478112186 815055595 481219000 904310667 419751680 673988099 338646919 871319254 303974960 763623780 825023499 25808611 606197757 839973196 192559126 500198170 948093686 353665795 33274680 710754236 511346772 926164309 113895211 851518635 278497107 266705889 84318201 908750628 596615843 703116889 827701805 329605718 892867121 836265978 560979693 495331657 560259503 96005470 836056850 538555899 651254058 575805749 968547236 777441307 195571470 407614286 160225711 334735529 455796248 145785753 368519892 240262257 444624141 43769084 950233868 367556082 778788017 932177045 988936600 256027612 801611036 510784169 835621125 462277289 690522304 500607463 357655154 386311283 781041272 806801055 973522908 331089985 554826471 71180853 128927675 58856805 413785163 647431032 893906614 313821289 994645936 152937531 781553017 440939831 555240034 756429200 289155861 806130338 926972354 609331631 429404804 893445636 475880 816616205 977860937 465189196 742169095 770004997 465500953 192489424 723141752 561592577 794258523 601345889 772443402 338613685 836674912 649162792 690150339 527674038 53815808 123741523 635280186 997437210 246307958 902549198 97517594 129329535 666302049 242127462 335908922 936588003 8796055 825174993 546910525 38773377 880542035 322337500 848011829 409769084 398914766 438480686 556473038 363927420 593767260 652116379 848259981 575947077 491399359 78435593 428986892 378549462 340300234 238751118 391968298 506889546 743309593 8645561 808734381 229258860 334233675 864043843 14046725 56173670 318007266 34791471 738866447 371301280 63300049 778767647 222800278 792384903 492931386 405132636 176073720 230891594 465412183 114650775 574623427 162508054 810471013 33999505 404309787 767237631 221677878 245918782 582364510 108507908 272131844 320711619 271114350 848392687 217720796 492332051 773812843 658933702 957897543 813548299 649881438 172568448 794776529 276723605 52168093 466722283 745984050 478942781 905066482 188897457 315479196 565919158