20414 441174271 539802526 787153157 231914587 997775833 351813035 932846855 843557632 342894370 292873603 52442638 273577175 434142523 655898427 43769342 899491960 834333489 574005183 703436646 519246138 156663824 177269464 545703735 877554879 976337365 199136551 781281969 531428382 49944690 316200146 725739629 691485286 235670990 674159263 961656451 542024582 70903722 296197490 419229162 792420733 898092819 948107320 776275450 54983233 673358834 31316381 883726391 137559622 879118363 546421251 798733829 685794932 682456489 44246751 504626012 590567534 992758588 471684106 16284048 196426663 464441036 809587113 844204998 335764669 696672892 471043496 122087626 570702965 915370425 143930673 362761201 732610952 630693568 369268119 284641889 907041808 261458984 907845059 248642880 953842701 456818964 89686090 920433797 737081335 962451484 36001058 24268376 872804198 929791142 524162417 65215299 511308664 700275219 805742658 55247318 354772021 478681196 210819299 293316041 32378421 901830559 894033545 451162107 957740559 382827218 403789108 853837730 174478572 586746313 148001132 945757940 381912588 332436098 697953983 576931459 463890990 802613422 888045077 951562689 66465700 499432135 488797526 992325233 104883164 811276300 211450393 440506011 847037800 593382479 598275992 631682868 745689619 922228150 869505324 304984897 893483727 350421139 539517979 813296030 297431517 306587155 276735553 640559130 911995785 231075953 21908372 317459053 414018080 518779287 975039397 812120285 574981433 631638692 358568714 383958219 871617293 524935926 929738042 795749768 993123885 374662816 648690436 833509067 112417906 88537019 354430493 613730874 752717975 931512301 604149522 171326975 588693117 473511545 530549298 710920153 508727532 222527334 708499696 949739039 216506573 97132573 236651850 933619666 361848951 778563642 55965910 596399297 260254757 807700442 479300263 388932378 351092835 414848381 51362598 241835429 998094793 828658415 229096267 689398703 947260318 95679066 185649253 545473941 544609304 583228690 349458450 248689573 804216411 230148128 514185553 206149105 541229727 938648330 973894869 99790814 351937518 295629329 941937120 273558106 283129481 338340616 23441271 147047583 642914848 19495435 774610995 369506312 361043272 223118185 484603476 381575509 460272444 354281253 192170462 261895992 896529244 626833663 266562949 312278472 857472153 313377823 184611217 233966871 809834044 616223479 330766813 982130213 638922201 980577590 973171933 264586802 185044440 149766201 763859933 178189051 309785501 122406128 224594685 659607020 410480931 561553925 375649466 364005554 806537836 44343937 704996598 228333678 891398696 607497459 516584819 268973052 739961147 272447147 989145732 830646717 42931253 338392658 814339708 401957268 263189799 35616975 445957763 591734813 888143749 123917931 479172426 170875790 693375132 504981044 831770020 601371502 802495976 621952127 498815583 719600314 81076694 146285347 892223552 741249954 448546291 860076792 359508127 636755935 876301653 373048625 900313517 229418008 710764649 53544136 495931556 182411368 537300143 937421152 185601651 772235678 350355478 106514675 194540890 615242668 311632106 398603085 70736818 350158562 933967498 552366636 658112869 397453100 418480393 490019242 233819955 39087378 441722952 974113821 894974266 158660731 553122820 712461663 822624922 350340524 243918388 907096065 396954741 580039128 876246089 361335285 884630200 97733181 181970961 118546491 780018744 581335202 886488975 867456276 91298981 914693081 25903632 428779878 804899629 266914898 760469877 110461915 965723854 585798289 15350458 909815601 937709532 974144524 139938773 248174917 297522628 253241560 837008476 145222439 476326168 114489615 525929170 27926728 896059988 885037263 82071598 600114624 129170478 643902432 646486474 679620430 810495436 690598015 56713811 242175860 538488290 815558753 473850740 673279450 293984268 135711919 163575554 301697918 332405349 910871022 411109246 721402659 453326502 943777951 412340140 991937197 93685575 292660058 651864420 79597321 353928198 226746687 211199328 627295506 652755857 771445999 641835170 108226681 425024085 49111604 859665101 559416067 417977328 305167220 594434890 336367439 656730724 990668923 362332148 836125830 70369208 837010706 195493381 53538322 236562115 436697520 359069561 722843073 561632294 470120009 75814796 20021222 86747664 738756993 124786212 661438634 275616919 181169235 185665293 225755473 207690523 48310471 802259055 394418266 294440705 780471344 574557239 986037265 799044892 327808689 362539553 858404925 531550779 754231610 34478630 605996520 717473731 914280908 790628004 530718873 328588605 741920618 590022113 563701585 305404054 26335943 667518704 955448577 719848161 686159330 976426035 984515814 678246075 611844295 230120328 270715293 593057651 453439515 321088490 305535714 595375813 382947271 383751553 732249963 943618472 374212120 746298698 961190590 161673752 314784533 26107271 117640451 202915172 525304203 345973194 413322691 941429883 573455346 324644785 778142262 160510070 9055407 371971081 977755161 762019428 919464087 356117883 837674448 382462003 37369712 811897474 432224314 363100016 855039410 282628702 735177376 436650435 921445473 923504812 280161119 584390522 951070741 193871835 621212750 793152970 979816371 447413823 23881614 413321360 418979084 894547484 827723443 1781987 914315082 336913982 3738439 529911264 788952516 823417193 455954713 407843962 164259699 573695927 893954314 362757252 133317309 96000514 580427139 769901570 561896301 708093619 328435158 405435166 887306991 415012763 446929228 68957891 304582301 132274967 268363066 434354724 461572888 981099324 200691191 752400072 676709296 853383268 805050637 765160292 661987263 791469122 876157612 446613053 208624654 483071698 487590289 495199191 787954148 84661897 42721283 586067721 777791270 605121435 484336159 428022267 425066990 994578408 317973229 885332398 307088879 196895257 404750480 167312048 149262652 310446496 779032746 598080403 315063298 904988492 758176906 668388793 142952564 578768201 269822419 564839196 28355201 182892342 448855935 309541576 474715655 533587832 814719972 779460155 344922705 266191109 123073049 114989605 138594137 8623673 698757662 207862679 655806501 645443110 678493069 112863936 961665106 886027861 286489442 632221527 407302426 159705151 93241541 73599113 719247860 881227301 947881999 406369000 646996443 614880146 574053808 889614296 219946943 90930584 293403 328650797 711745646 758653055 272364185 932976278 405098250 845626845 364344459 861733851 452640398 470867351 122722792 334428543 331162275 501296744 600240271 213049968 78144911 761886738 989222122 672064951 18624888 581306419 170608205 523979004 283074169 419945714 928737581 30504772 79126456 334629262 941105287 619377364 48939502 216318723 173466409 471086668 920381487 414444415 172296996 893832811 494093912 630485039 374412789 702676181 510725361 840906760 219094589 836984040 605853049 450165427 178078912 188110247 294072977 741106122 821348877 706250443 880146999 695214113 113282495 710378545 27127275 801971137 771553970 698955284 563471807 180305669 974242375 942035666 600417637 49785788 373554142 547337858 10111755 760089388 730835858 661763274 884228581 262470297 778276929 114068497 430487009 760775588 420150117 725936755 523993744 165067392 145495058 635151367 46561657 419210761 831008227 912739564 690568989 70036162 210231652 932243989 158335503 966118545 228948061 128591534 872985361 852306573 400751877 849835821 994163736 868080929 760527530 891207940 470000660 117822949 137667903 81653855 468140664 14769585 138640369 338970853 781586422 921813814 54842635 515702002 944455167 290589794 659507177 942880925 804654199 196890139 678429057 307206024 254512519 757428971 33813758 585184887 681487103 112576963 996014732 61696789 560244362 218505470 801008118 876826421 890009279 451119101 209125409 660761909 484131112 116511181 127136411 95999587 102188261 171095572 400944459 354486554 251949615 855454916 608928540 935143422 577311468 598255202 860429697 446500246 513464742 245305959 304277193 148713064 525981931 149324832 774876005 961573295 943108125 940603066 675101114 423088412 543910920 588588606 945195336 708927430 243269384 749140788 409168484 819031376 675749330 846518440 686624305 396099684 639297308 624432242 339016542 904453118 617207345 517051197 361542275 641634510 810697642 135983258 394123963 703169236 434348209 485404888 47205695 968402711 105505982 259085090 884534583 397021789 60698210 327023007 314640729 361753250 757544018 698895967 521019288 815154616 343055135 398333884 154756608 676812771 106860272 604527881 604521173 24291551 394593380 147522362 35547572 518536296 224270741 26545614 619491412 947298411 759118740 753945347 156178570 997032878 428108021 972813330 843965687 765100945 769299825 681035581 296422499 719661633 487588563 999702833 374669834 440264304 874143310 381529264 150236681 296427101 582653761 817379231 285364921 446367537 744446258 879549584 883270202 306978370 611559199 341753642 344791245 926662807 565972609 583157355 101063506 597925289 396447284 757392248 576284940 429829440 339941016 623770795 670615913 173150247 523234347 204896795 353596475 79070984 366276339 966369031 761202673 13892726 608126539 819850604 2606038 771047311 100238427 979576990 243700874 411889753 160648597 435897641 432891942 110051577 946872554 78431928 247549909 623787470 287982714 901911361 469586794 283853745 174560919 249713897 852616423 611799637 794240939 272349033 958247946 288399955 840045531 873534591 470785492 470220154 858188974 508593484 6198941 111412519 519997270 734968337 694530838 134611757 423167867 481963630 8261696 567768376 166863763 374872440 187455347 591236565 67927590 727189936 763676839 886063359 332085853 896632413 452448677 241987068 805678976 716313093 601805891 380076085 675173069 218433287 733825645 329018828 822814262 6425049 272576447 676365882 706884540 217535386 515527092 822148744 425249866 65351120 695355782 624385375 86693478 554042548 101972407 567825221 257343176 844914180 906728359 753314769 850209451 445267773 14451132 701884314 703823816 622243056 301332205 819222825 899338260 333599124 221865617 682032774 179990985 54811052 681033281 822331340 787415945 641206042 487657667 567795342 617498150 984700818 262980399 992210284 599523320 367484629 166156121 244605500 82852379 973672564 926847222 300580045 799814526 977171848 26854137 717819803 13343848 401285723 522371087 241658855 576626211 141332786 860549172 293092932 589213697 95432397 86183367 611091215 784843854 609824520 736189769 984794127 634270042 682085686 558243776 984902247 42086822 581963404 390580342 165620822 763885616 409125979 117541773 719158473 546999867 870035705 96803074 194199746 419982128 82499764 371110860 93777445 239707566 82323537 527761365 88655984 529059834 461400889 580860375 556840107 805527587 409043527 463557880 734177031 540899866 466054751 413979729 36421522 167379397 284361885 295774816 932423582 993516415 750178390 811768275 68229709 448067523 36942535 303864440 33457570 4104751 259339177 665805531 472781898 552664510 442212393 521762212 545401913 206006375 917239021 934114723 167578913 266748923 635284461 176752756 124058057 766855955 778689815 432708869 679876468 616187723 799382548 601091973 179078654 380606904 115310932 911624887 541604890 662511429 181106516 963903788 333919744 202337737 834127208 303969926 224578994 926830556 436263462 217659080 452016611 147595063 311076908 678979074 8307975 967092279 423943911 839702502 993395811 328211879 543937342 128595568 482309285 978862942 202695529 297172323 951904444 981614959 56633366 123217153 215155997 97447696 680820063 992060753 9269884 833766094 53286903 611645843 945314882 961311585 422416265 554293624 282326643 538539236 660706851 303429917 81245816 799082037 380698069 402251402 942375317 668421057 279727256 12822942 218103269 37057819 16095483 613241222 353314090 791367151 720487870 486639458 430739898 615763176 803881711 910050170 106739898 349554696 636219209 166688843 730987040 279280108 342393614 220564520 627866884 529305830 419305812 693792864 51019902 514188804 176908260 313601408 354912640 193752810 303818425 123716709 801083007 478169870 592381807 82868489 195423136 621990572 819573651 515668584 406078884 677186631 106738878 542352616 628224395 169078543 47333115 129364526 769259932 333435834 48737502 96818690 101699749 744789191 197747150 464939320 313677687 546842314 820483656 373796202 865162877 372889762 613083512 521766964 925696822 334776081 416261360 526050837 565948307 846410960 613886028 51141161 126329374 291020571 459740988 922847709 144569198 777434106 793061756 221384516 85458173 895698519 298648333 956024537 179143115 529873182 932537657 310943342 434616299 548783592 388760298 168965255 79210757 5801082 635100403 989102345 189342524 768100435 220358325 700989045 564944437 182681376 92573114 650097608 956069206 385268552 212829794 610674668 169767418 259620665 801122165 840138546 526875242 869676882 225667513 238628423 855184123 738510805 540755274 450576872 360353972 113441568 426040856 744706266 286179815 589548229 756988705 361740221 13732493 896653502 368127574 397717801 975596848 576898828 751361456 946152767 846083184 801295372 417526209 744940989 89381794 204667993 776134455 248920205 274690447 188610000 765292154 128105567 372389242 521515547 671929009 548279022 51178126 678751342 783226707 301143007 36263839 909093965 249050081 728343522 734133392 474834054 408395014 33558135 734900431 644983045 817517016 32793423 517056696 603785035 785933202 772031737 563989751 660774364 593282445 888017118 410930814 575034388 486160070 444271177 842438424 897305880 422661960 28574012 464712797 42483847 115608684 259860211 16874421 122416862 66196986 251700307 379738572 553955475 639940164 927600485 18742702 795835045 94551932 876821231 640346122 384254157 940601799 98895288 760597396 223820877 187739498 130638083 190460903 875335864 358566505 352097342 995370124 249061758 845289774 588028370 387614748 195011606 16752446 90008041 20830501 904004794 994363610 252901069 233641919 364434964 962381402 258583689 105727622 177765069 520888582 281221277 409346228 485161507 238988379 966892261 159789621 558274825 54636767 316336524 329361504 57436052 571983398 21574227 928640184 449190978 821829298 264948044 567618596 807054444 232120417 370583077 875371021 785371904 309584803 635751425 679601924 245464623 170336110 223840472 193614698 340108663 430043837 776002390 834948174 47166401 124995679 569911456 797459961 924415355 487445998 214257823 817058799 79353769 87968787 455540055 937510758 702040817 96036513 779921185 496821908 344176251 324760858 535842628 406386169 456283893 81896431 292971393 496247230 44828261 708937155 685765749 615309721 140084428 65015590 331901269 727753577 401600634 762717005 924121482 230348678 142227788 36678109 454242648 595567960 210511748 953839724 666152435 129833308 957680953 628977276 109449368 373053814 923098049 13146633 294535246 453800769 280407631 264689740 551983704 512835930 611795124 338688044 763009546 441605310 143277121 104661831 429020284 856600186 416118577 576940484 307440794 111224107 37152979 436683156 790134293 260017046 167541310 836970299 641961852 8789879 365520714 971938350 146124036 947778923 843190307 762062200 688698524 560891705 712040706 152365349 861469144 693469369 754361584 337881427 559848695 525329924 788850723 982918449 257677504 20887506 958680111 162028149 50952093 827306981 530914239 143459354 810623373 151310691 299635257 541254875 505488981 746159614 171942468 441456566 856259 251192339 154898818 611781359 875809812 917434865 616094469 76704643 358351426 371082641 147300623 763691323 218361988 773936421 748521159 671720715 669558864 904595741 53579265 128011015 105940472 243346123 613163170 670797176 37661187 618258837 476273138 905848899 250145983 178762468 187930837 269334482 794317154 962005913 56596804 591392963 844445782 10088165 305724911 345615938 581006533 586378658 624274201 45524307 20200195 116411463 337995294 675121391 798360654 411024926 573578022 540168802 596922825 744935568 655432513 375203886 854750156 552892479 125530742 920946576 377528783 101474450 926277235 613671043 101848769 73994218 560091856 211075740 326083205 563125983 185368145 816455369 435986400 505716254 696753721 918175122 747639436 591683717 902957724 745141571 814988025 998294597 103969031 480111858 764752163 502726549 665913396 454809271 907506891 80267389 487708131 385029941 188744496 808560702 548925414 292127321 608742713 858390561 284687964 162817805 541383447 994079145 110647787 76041111 762950549 903993392 956421906 103836543 933810024 488544165 513297405 985835018 589815457 251295234 929294473 856375128 776931181 226883420 18894313 898257629 760065304 82855724 505881903 815754771 91583319 230781965 819575000 176915578 667145869 168249492 330572930 867643855 109505426 921776234 429199385 492495544 893539315 156378131 654612738 482692558 539278275 906110094 554968125 232536689 67047149 17874920 760988419 8997444 384631564 679643308 983448878 175211011 349858867 300863402 728132723 331321810 177537733 855330336 592710761 463751094 359248137 38707814 585963957 492500339 574933768 710924752 931157925 338263498 639540369 311691726 1444312 113157515 560442077 692018428 445786999 691943787 438834680 306393326 540385515 593731921 69810079 470711106 265764078 888385208 268017425 595142377 768031271 733805655 182780427 394989540 699191246 897325575 375777806 464116775 558753572 359840875 549502040 956640602 881469218 365832493 567403611 632840611 58100095 938747974 112930352 801809494 907423579 129265613 533377385 402349738 652515804 113195310 982647408 742268904 606071248 658723330 290835672 805205139 430041998 547913972 154937383 543491524 928587283 348846157 404831893 29453678 516220915 867225317 552957599 64022462 429164356 292220215 711106167 526451251 241472540 696509580 299951514 869999044 73269341 781461741 899603190 23784518 71219407 72987718 829363177 193848519 870515013 796985666 509562425 259633988 572174037 26670283 416335321 243670924 147650598 359699217 610048522 410497802 913913217 814684358 717687815 623001672 352691766 204644115 117152184 860938489 867915999 202360097 964712850 430935259 574202034 458832678 555575278 856538693 950682800 935912345 248122902 501112540 558604828 758731375 884026039 435810474 882950909 575048806 991012563 23362008 885871963 432570573 358868988 721657038 71680690 785995190 469963259 490118772 537227182 512208005 41927575 27351250 86607638 802493832 659177548 485864757 696774761 269557904 151472651 695605890 945345345 235827970 91712213 60599143 855075042 285976122 50653001 293750377 377207006 220004246 980017931 143314052 278767568 605955063 883340601 441317422 617078568 598531075 13902577 363017220 885552670 481235149 88432308 309801077 564292482 784153554 536425675 440085838 807324620 954041731 969704105 27483468 49070826 74323958 361283895 556238446 613004804 766062677 723321776 73391743 564589004 220872455 303764556 346285628 828851499 75490194 958156473 680114657 943986207 105857160 681327343 805761791 797076834 690393182 20893105 961579934 504295465 434111825 437423094 147601139 62734243 262754901 308979430 196326408 124614237 123149852 975369205 759686632 509797541 354646902 197522822 765300705 997130683 85595162 504449568 370885602 417376654 796921510 718036816 972050079 533857227 713352528 460838860 439489809 133230558 950176355 840005415 938667146 420084666 958470925 8392416 531423819 989756000 855824077 808607582 781474982 303621480 243576097 340256883 366529099 732490731 37610584 942016760 400299336 524271995 435537093 845555786 726438972 229968381 714004087 345416396 224967301 3115556 187027146 589902619 772469890 992496315 975886523 376006931 271004085 711486921 344590909 914633340 236036941 957122297 871424753 947189892 385252331 966241163 48206582 702781128 794720900 76328386 811522387 783550625 699672050 927434627 442402372 94507878 413792897 734036551 828930043 853409254 455859894 533424461 946511803 8569888 22596815 205141934 225009217 367891508 687507308 50865152 792028706 710123956 287662761 417026739 495098806 568538178 620933204 210843797 297851072 956307165 517771212 514742079 805853383 752972956 261371968 160697979 879106289 948113019 475239079 232765089 459109640 720336611 556886625 231132575 892033243 123205734 604062630 923821822 640859048 745213617 723449790 294255679 2188511 495265003 833594984 43060453 739787396 274639259 129285273 484629726 724866567 843278042 287799585 949617799 376099058 121060143 662418576 459819242 278695540 866995517 47248365 465347027 25584741 330640571 144549876 763509036 259664815 514445311 857460369 440844487 799287500 77459981 752675212 427170059 906172017 180656314 227704241 489950568 670312701 459710614 964977022 797651058 192988772 137370997 113843332 716131066 898432660 415944923 506848682 27881243 167748420 763955940 995165459 542682531 31491340 524487710 702319905 634569253 384872015 208355060 715827145 241011130 451862058 149513145 816143283 785018461 941909348 90318282 277079594 465310652 278104833 609829138 802371500 127083572 42922696 932034868 145850094 977961439 220543423 220202214 349518357 190992704 511935069 87141041 85572861 641380123 485085616 630052743 277808372 505597580 425766428 806276078 87077991 944092095 569411528 741793416 427227734 23139288 895752499 814113807 606885487 717608318 455558668 204011594 921642753 718360855 667759516 976489863 650250574 374165505 783623319 458573342 466330730 495211893 138338559 322885252 451395239 885464471 662681845 211215321 193685016 437559867 373555802 75065067 156970152 177698398 712784988 162006134 72118420 526701830 147181631 107503416 352736578 703107924 837014972 952687919 316776204 835184706 355305962 596681580 194977039 216989247 701630926 358435474 555920382 140071222 554041993 830679018 450824547 80620145 752277521 248316552 808236804 168312012 423249901 640843530 560437757 901784983 239847145 12934713 497067807 208984118 304029 688215912 894034985 227109257 350958464 803683885 100425677 14210996 831840615 206140270 230715685 56998843 179042739 488184035 176826749 57798072 969748128 280352185 507791748 718961757 844720793 320937045 36886905 549636724 148627300 894281533 508751561 230437133 694445643 662935075 616926604 364260703 286527792 782703160 207224411 920863546 977278699 590867616 391299646 403778322 691155823 883802030 698075257 226369411 158823024 84487815 219919606 921637777 535134467 367380115 402917657 369184585 57896522 754355008 94162271 453510239 559503392 762285463 930858714 846427558 569214934 165383975 66071188 505950484 731989556 979253149 647210070 977665221 797502092 637091316 847458118 717671500 173107029 501821014 455722137 822794138 376577697 260345579 960822298 443782919 333370139 895242815 911080019 299706750 835637804 559887804 42662857 90497436 437373794 148334297 219106162 108823435 949133219 259478881 965726505 192681307 207393412 388616077 893476033 1437495 563147524 898730839 880838381 320978308 997229530 123428761 286165847 553936251 825996675 921102494 563171437 792551750 93076091 597678663 826870377 419665239 209844254 878237844 649215825 474695785 341992998 588513810 67024036 278108838 694444972 915802464 967471069 527958479 241808006 140486168 393974423 457453794 141000809 30189817 964857565 560946780 967313882 449104506 483474109 699515655 752685615 623431642 199948166 452465243 72785425 114121699 926742770 681116947 489161423 672965811 785048556 280475224 88999122 906247415 626403024 929307048 397777706 288929275 148257665 323579085 427555285 123716712 397630594 241367098 827245211 278978988 134717006 739877869 657912340 625598318 493814015 359570809 134763614 995225910 948051018 156729121 3118936 395714602 930445363 144538305 222565581 89569923 278748124 82784800 289573620 683384425 38931057 887058061 223667857 201299511 625675521 762959001 880507080 788518877 11040628 481945602 741228095 627773263 653594452 188395368 643413534 98799329 135624374 328943506 894093301 735745194 335888801 730362670 715350817 811388110 337541671 44433624 666709432 681062091 277811807 715481548 920389123 13616292 900306104 978932175 800701715 144731286 952720833 551594135 939848961 484539729 901394082 943347898 803942855 481500991 217952622 911430557 194225668 759720544 487531286 589372414 300457322 392284182 985339502 290576359 118062373 492776040 405955262 192107398 111266120 34023582 851752420 515720927 399522723 742862226 745800046 9124236 535818196 5243822 487273384 669988719 921631420 631541001 687320767 407276618 624407612 354415833 605058699 143037864 786705775 900706172 493860548 25723056 3960274 702372408 973806131 498812358 116990336 800017803 286333988 977919553 66495947 494204431 430127727 131470056 533601934 86924521 372849027 389260595 35322778 318913063 862556839 786069857 247613049 737974098 182253174 667224750 81674128 633345453 423783529 31050277 605781395 41898018 672090288 923666773 97269098 616065916 598703414 477764107 875960560 979581562 659549014 183807128 595718046 927520312 535728587 394874350 53285334 496013423 801127971 5058487 275137763 66354762 135147577 867978060 522251088 609679816 344112679 976578620 407488859 282860849 212928058 847814895 912521027 607421219 267847718 970165720 163016501 964474796 3003764 926293393 981177290 562337220 968617852 583540666 557862576 993226435 188504573 952667126 710296023 889127498 501852351 912390588 246355769 550455976 356247330 764375887 936186090 969557376 135370541 48978305 117361288 941534696 824338110 647530666 303269353 278459841 827697568 803358759 892439318 165472640 986316096 845260459 599618934 724845624 459240142 136961002 184376981 677910410 590281682 554439154 362419399 471714363 849018898 871321932 754022549 267793754 876498003 93967408 266029351 885412093 245001276 781684626 979655064 320139291 92604696 331120388 980449600 436507164 657370242 293361842 657651246 397515334 992535779 965684950 979283260 74657718 780158858 353632539 327369965 744676206 632327232 522049360 449846845 175780716 978327560 298083153 555395379 279946689 798823048 969282698 538364713 850581841 342507980 243852763 189783672 67463083 497838741 615561512 945932518 760801558 236443155 114109700 406745693 315049474 516034594 604148318 647416984 882248634 403356814 670475542 19716706 350959806 593763992 865574457 299838650 768735 837939364 163504187 858710513 500999531 770770830 197760570 247841693 705273818 649200275 984495174 660777044 11591282 628287170 947271019 893339008 877586152 494865986 593709386 866714548 204203245 851445753 417738892 499403117 944359632 253943811 236082469 772767577 242118686 85680305 503776755 814153495 472294992 437112297 929984041 949160537 46164466 887663564 997588651 191151102 637559937 585906446 170683758 960874670 215334523 205512636 127210263 980467289 122755037 326073575 247126951 298715902 897454119 386367163 653550721 746512424 798739423 370524096 65205158 88681663 945940641 140537818 809629331 917880425 178905861 572561902 800249405 375554113 359436071 981164718 912928384 242008141 13898434 523530832 493284497 285125519 804970745 436829249 162062200 654047636 35147491 60038223 637813877 657136860 304515415 729076846 241765559 793397239 186379560 189432610 228661723 825000036 41189854 493865354 104987428 880211178 534788748 520977135 106113158 696093003 17891264 39331206 646995208 545302580 730707803 855965662 834514956 712290713 68900550 533210409 783283014 637609103 553715047 202391042 365320054 372645950 451194435 975106753 853245998 94259735 510302770 120757685 115446102 90476490 958555861 193797830 197916969 661542886 286668253 642347616 748026347 700081898 740762542 837789805 744709455 105921771 595476964 488793678 373052789 833110770 457184576 681966715 700764191 806954194 741006368 508309381 11057932 271402075 372553972 746924303 857573141 651550865 879233249 150154332 63903597 854948193 816537747 384275981 948152704 617345446 160223556 744957281 751637065 801040678 252721649 135852119 883574848 783372942 290773974 429316031 482449647 170692145 813057415 687484886 989992768 276612310 973939193 642598991 553780554 654459793 660489500 178548558 854462820 125529334 45761234 360294712 7778075 361590276 612236957 5952045 45318815 862011408 683956161 316353169 577785441 256696043 936612766 663283983 788471086 417108607 945152535 104152977 870953110 277930831 369394897 995278211 81952149 143345490 362729856 680339809 899180121 363889455 842331024 280935040 140201884 843267978 149028410 480318009 493613369 621133199 256979423 575590899 181028031 611516489 224578705 823037809 804126200 702258305 305942720 40482138 316370866 633191054 722503723 304164060 987988051 425995285 15753486 514115612 141251672 772247871 756327500 27299191 314593122 862339616 974784576 406261385 946537369 301026239 566805108 220455396 925041321 119709955 170753268 35336023 108847168 823465737 624827741 303924743 420488049 276932011 517697068 183347816 17767418 772178893 211627488 991859183 274555107 340815349 309811074 436222884 817853544 53962954 246526410 612897660 524807601 136198957 101443006 174262179 622289128 27825902 139519155 908742783 10254440 225663482 264684069 977080267 50966760 295719734 515735730 137059632 220526878 580885371 154444875 983593418 861454567 262015078 624529634 498845720 38426136 987570543 972627721 449507585 591634498 147503258 470592186 92838779 923986359 993234408 869225065 472477349 220081935 383571701 909914054 513520207 778914919 789621990 218951076 82021079 756717681 273402682 264988818 486919475 741905597 211930198 365829775 600030741 603468921 952949023 210005177 147764533 820312383 722845062 937173291 291929916 268672200 852679472 277803891 464488511 509508467 117889907 369052321 48411105 487032119 388049205 351282775 458695719 907753437 600421397 266056717 734002559 20086333 791825483 181067833 151225962 423230901 354960132 738951739 33459841 508741698 677264876 175919009 837497537 555472689 70425060 171412947 175153688 458070690 146623769 334769468 317050970 895946415 984467954 624673912 461047536 121432211 296069863 27946110 880517587 925403039 140922079 487781549 483176612 236230562 692205915 252927112 912068768 371808919 265292980 42997742 648404139 92531095 735461064 531847224 545877578 75510266 61681179 55696349 205767274 137201802 934570308 939528112 357844263 820029074 232001028 608585933 218032940 973636269 138688198 323446727 850403644 386271019 244477770 868785463 184555739 568625653 802041029 316805737 228541898 879188932 893461172 554306704 592966080 724507060 509278820 350220112 835727334 492306384 615438423 89870725 792491815 479044908 116825013 276380211 128785915 528080037 727848387 633341741 739394192 740220831 868134688 400938312 416092473 605728892 432725213 329031743 527876160 403070489 478754944 799930537 447375900 898749764 191081222 232826063 185875630 462896191 429700409 155668641 700784473 223125258 325706875 783872404 986021961 783199569 426614306 681893121 379189101 818158171 824338206 758143770 620599427 695411620 618259303 226796986 190037148 692268551 467952708 18986750 848628578 194160574 560590075 432340453 838481989 617502463 516178537 692997386 157467991 823680010 749755924 751036708 54253915 852317448 504085878 892302789 730161468 343151564 937738182 326716639 960628303 263988544 157383360 31522928 157328355 761684969 781310718 314753218 321108740 795468564 740771200 872002927 694472484 378522692 825893876 760552148 49872453 331817100 720145715 226400497 604745365 700006037 19914497 552064334 858857622 376081992 26968929 992574512 609657843 360989217 383297483 901548862 221618835 641327322 752231687 849812721 253466430 479850512 698962221 701033832 391163704 777448557 329573931 707492822 829682967 147266156 570395936 933757733 267813437 759401731 762725477 919922642 598316082 942212705 264992870 958685588 670448881 13035042 294167314 592088218 149165822 765348104 631414893 464361440 590077754 685139430 595183351 838102232 355281992 914076917 148141447 923450254 510727660 653338706 281625901 712441378 742058811 859989291 318880121 505223427 258763721 705584895 883058722 883438298 395362567 748386518 369014658 569123416 730736252 351768907 75793757 621386127 231608706 119923048 806479951 917471235 397726623 848017319 390200741 80684596 937289343 282984673 678215916 174080747 733166637 246976241 712555212 278746337 832679299 115773682 651160716 484103340 478613003 59133206 472440338 618826032 858948306 796784968 563952741 746154635 75895579 246365432 784528139 981938356 669138689 542627514 302754648 155984583 994679969 120950388 477784646 146059274 613706537 431965645 767516568 101681928 753149954 558374881 767468511 962582850 402297909 328516919 115184068 932596425 818888493 692223902 632136641 898747419 519819285 563485181 523890867 128893844 519610967 549046337 577335212 446159006 431896811 879226894 153360555 564083370 417000061 904705458 605146637 370988977 797572995 930153195 8949267 328805897 152593562 414723024 221603570 678921040 224490734 222809360 577656149 45938048 503516101 346251154 54172908 510265476 358655016 912660724 816202270 998758471 242449820 743384814 25504140 306481725 615420422 639159524 35321605 558269976 397649781 647609012 379261246 63963834 874324511 688806866 370206611 873120583 445495461 301194791 619224886 50717391 362167525 629345186 551478264 606181279 99929101 676451055 869854913 887981913 839266799 594470617 416974607 834358205 409424276 638218774 717734284 579660068 41235997 870312022 928815167 874721578 823178671 455141864 944604718 294689846 108787563 955529544 72169821 383358309 760465687 894735207 860404092 991874897 590719569 125991434 754276790 713804818 288976227 220413404 20061109 932392535 390357329 343622002 580012185 216098838 36174076 805541516 341143609 414826596 411151333 453582063 392305609 751341816 405353314 95094877 661960998 971948589 178174466 444883985 969411005 188519086 530209507 531124496 929407616 566673865 2010098 490138938 833039839 826896271 759524050 861340333 247067697 222669974 843169046 836190699 761118100 344916022 911195441 971069651 482038352 629782874 853219437 558111196 675098598 129155386 648013938 305208773 596481641 811857375 726189114 846948395 582749941 797822923 581602710 916598925 460759895 254471263 616238270 695651287 17085067 49036292 677986445 63382141 693560950 146542195 467522535 164899967 83251441 554379573 796256529 919347242 307863722 843983419 308617828 567220948 975114977 614208401 892674432 672073278 738181524 959730084 957635831 921457031 457736250 172114507 126239735 546627501 333643123 200406714 579152415 881211375 926913282 993625602 69423618 865330278 349163787 622183370 74062976 870099699 922917572 668979117 865412847 726393399 197608992 36182972 796337940 777045404 422996715 191589873 536608645 556117035 330307496 267470495 867126580 50757216 453934052 319758900 11585061 824604283 25443342 602417152 679870148 33795939 363588782 576512187 81143923 93947021 590984695 546113790 455813654 630202385 186426672 606540169 644698110 917092586 100377505 211596868 270911497 553565229 508482000 221013622 423220862 3680862 681324676 984441513 472066326 764921495 607236845 966889077 67951143 292153866 762614969 15792183 680524154 465193651 70987024 403250633 507424145 2187728 481831983 14592734 434948137 803558806 121862773 200390717 221495620 678696340 380644171 623222483 880467907 895878133 851778276 864776056 360560554 644432500 390539046 350212716 571860595 714727661 604187394 549623691 618469221 235019562 569155910 620915613 439519094 962565394 14880975 232267935 850144048 290895749 585244503 650840285 167377873 122747868 44188096 784371201 496419143 8955624 743087083 314318019 69568018 380729353 761609087 739207520 18932487 800772153 355213324 164673908 964967375 514947624 197434715 406992271 536741866 48754674 194210910 956738816 831188990 653196741 39261310 452155069 875675259 88027259 405555087 924480189 547544560 481658442 814365980 514976612 262784866 660361088 353431603 232864561 767471157 500473766 629408663 674693899 420902277 704696455 131398056 515349650 795780056 890411120 130331018 541440873 934372678 858126591 288526896 617650897 902263623 292119142 644976504 766014043 571912792 676031471 125947807 126728893 645007781 488685690 353889109 203472382 437180419 681786992 496686612 122718723 993313714 634273776 99356 723103299 496560081 78825037 143022271 136852534 48069642 504945938 732336126 159772194 968737946 123511247 565125344 396095155 263093176 576086302 549715470 975824738 374777013 454917831 596001989 73446370 805941572 914056045 768410392 866381771 128035200 239560342 902601427 200359662 104846652 944966147 783706121 686591163 414056253 935531211 558688935 243460881 807983451 959192648 73698043 803930156 831196646 516581383 586461580 573755127 693986006 902649508 424703214 738041781 145947376 158954390 599758597 409724532 462600085 402982993 367094518 44973688 795598712 102187278 340110209 212956843 436953460 416059699 930092448 433571486 153938529 777654136 255272768 62191499 466023275 870408254 747863117 519411067 162142490 831409953 382232936 910596112 655047577 237815399 754727185 732697304 828148266 284288161 747253306 145449210 846803198 224383552 818297829 932566170 371989099 701066346 774403929 531825109 200169063 995120431 819511946 110077917 926375917 183073469 85640882 279819695 187317094 206205314 739793722 235582808 467668408 302610838 149347176 758407317 863517789 841425641 40609165 338690762 299513975 130537344 853299390 502006400 571830826 529139772 850011320 305236174 967727826 429146869 823498570 868630757 914918472 739936361 544302592 414206490 516315895 770688385 159369029 122214926 188143720 701532005 577411782 100921506 765697619 674360 384473866 65852408 467184702 820188654 347981531 701791754 217081328 429684781 775630378 694056349 604048683 545245885 660244259 415731826 419424121 333030174 620432485 45733304 365350589 471277783 554509127 761753033 928556103 562350805 120880042 375558839 758104718 879728904 406362710 366448756 582980930 165594122 12058528 358469224 116282137 187629954 800002684 109192231 547407205 134839288 492945946 213676284 574596628 515876852 977929627 842613951 446876506 246241757 129826306 70913630 207806913 204098887 537418878 864239257 969438834 452805212 136001370 458640565 904712569 484351572 163039619 119964001 328599144 859847794 292107846 371300078 924144617 713080477 336822545 790311994 127338805 377023616 532884535 128526750 887930409 723670610 128649892 312230290 410653132 702713208 57564660 858596723 529695730 487519944 74524827 220531635 429795787 694329842 193469057 595883947 293755387 188190581 729217598 143989399 635713240 603280556 565658972 519551586 360837637 365014505 145423877 406754081 745205125 907136814 939550631 665588578 277037094 607310999 456056633 735985497 131753930 562475509 760640935 5204331 467499504 325519939 827227541 832355054 229575984 30161711 431984628 888242213 148444681 529333260 726649125 149059566 719981254 747402245 588035473 929692140 253669447 269825272 122450954 732783235 285320953 20657914 636537790 258541854 707360431 761062707 517393121 359288903 457846457 905658232 558766776 366773808 276244216 150016857 995157387 201170911 43994715 989431856 54770504 288054927 388672476 626347441 983847693 8025620 599061134 379981666 734777865 280955297 738445936 695682851 834401348 136975236 716293529 961711888 816784858 522275260 527568566 582146868 114134648 938259943 644107378 284075705 692163410 372000880 942217760 460226787 907410408 826095756 450759226 777757125 47501075 881535832 674154351 165835233 588804252 508256331 581939332 259729761 362983327 154832348 426407523 629479551 420591314 344967836 148492322 681371126 615501260 607054575 149001620 887900407 242322186 985201515 888011974 473602723 955919488 564958059 443763904 928533792 757743680 620615350 598550051 556009322 608368366 539163262 275294000 201828437 468990520 28256417 61473436 955918147 167008719 455200467 676576566 46072622 450230044 847553336 379518512 519231940 744989028 79515402 150920561 145414709 338635822 421591811 937684711 360158855 289148101 147984335 485239597 375156824 405145216 9004236 953540552 991552917 650286542 34234421 375086283 118639110 95958934 516219771 890963001 353276026 218579303 609811912 366453166 796533877 837729189 348030568 392226515 555210842 253822334 130728366 293444225 387988090 436696198 398850729 552904450 111734167 24119242 540245866 366082822 388046994 654440174 377419236 697437051 577451606 707397734 71665436 660921079 716730374 134595013 832373380 6926890 173129378 980820538 562511428 294702395 588777652 486675135 320912339 246468437 580145756 518957693 998471720 964338035 616713533 542355389 294735401 191938707 632495182 212598745 682278728 948120937 78449628 331843900 122303616 88638685 362948383 565209108 446205765 182888548 490067778 759299875 369396091 603949064 77249779 871529899 613798642 666156198 377228717 66503365 935484248 733249237 420686140 491747945 113127488 224545147 201324452 823744676 192509356 852468905 665513544 238558799 222996628 198541280 437937030 905242668 603119742 733758498 35556011 10169790 718882786 756483564 583091791 696990736 929525804 575306266 571416301 652336007 927618106 60922299 736628996 672845575 18039597 521320267 597682764 585907859 510247559 531622236 434084728 636580470 99164764 795262145 48587928 369053374 897525748 69772644 311215217 186633218 878957075 419369752 356369455 205257525 841512397 108333194 565385404 475414957 422138034 716225925 743961149 653969724 326041507 507473869 463413453 306803745 753134332 271030657 219707035 253904128 659284931 152869084 630865244 192099104 40614754 844140064 667091973 460714247 944825798 571159192 276468397 938193410 276159410 497838571 784163286 865208253 804847214 296085764 319207451 902822683 422611163 823363583 311631350 298496841 982434174 723899634 289038342 614352644 458668263 863911652 148020755 580247698 321527545 666745360 120597913 198804820 996268702 702206579 303961250 120603966 8516203 813122445 933304669 769050637 557882494 223801416 917147907 790994863 509972654 584484072 646501454 883322107 694051310 891693767 844439218 86965331 981907076 828374261 213879533 278359133 310676361 156011365 327006771 602831544 842909401 105999134 938638640 710509687 212162499 360177965 205562243 112890168 514983985 973515410 20063643 856738604 682048070 769957088 292147380 555463700 740919912 653349823 275757091 427013278 31880501 788381593 259528873 857091815 156925325 629382689 594000533 358647713 799546091 511364685 887240763 737339641 600643222 244539316 476564397 996380385 648772665 535067955 983664561 501016172 867949367 734822648 740117852 603878882 263611485 586096505 86620961 611334162 657437531 660170697 596993006 578510113 284906820 634391238 234018653 769802319 468788095 926550178 910637094 617343946 451123363 963943027 327246629 38460716 556785502 489502933 453633052 700090450 641780645 838788519 484925363 387319895 118887221 144955589 532034160 813580114 491598408 474554903 946563513 117107164 37018021 936877034 599757464 430944559 681998125 657281445 683453030 661017672 998576075 933563661 694304709 156118605 784613491 485255144 274583722 923325161 44089150 471175857 714183322 757381619 647296438 892237975 187126147 223023033 43464243 983037297 773613790 31270037 376544210 57377550 934775053 471623115 631006319 323848052 440529558 486987084 351202276 397000832 728502087 430468225 802241878 132957939 319958492 671530636 513277914 909358903 869946548 865749849 395500250 520212463 944902286 314471354 797954439 98205356 8378023 825683163 887653051 343853051 502277912 23015284 48254086 134033406 601971305 275696356 574017471 129720705 614842931 895062817 103667880 189370426 520513709 912357455 624455735 156034815 774237170 700466315 823723142 654517101 749007889 526196116 488848765 310819804 376687493 530007440 253610268 766432997 842418484 849430090 430121933 745970602 357712416 241711246 177199929 753827763 281424463 639359456 335499801 523130322 474232293 784886613 399279157 96820234 214332682 722143726 266648544 205960791 591598932 579430551 628136481 722302928 325543356 122987438 541253370 471412219 152584340 558110395 514274960 513152087 35994840 81459505 703235720 371312402 463045682 294889839 258493664 274999140 159353629 264020038 999141676 738591508 6629268 910808543 617356046 528866157 831036099 443117096 623638270 232198539 702717438 439515253 463703574 326095072 484807383 654639895 559901722 41076802 313982228 960281074 485867025 154246926 69960623 717992945 473252821 431812379 893366542 551824746 989496267 412469929 191052921 878410094 884617412 736820998 12132387 100635101 572499138 893003837 928665337 654189479 444618007 844562961 451359943 724144299 921297604 233150262 535232436 583271311 467248785 490069224 964745808 41132072 794335823 4187922 297227427 516153031 247488704 943080227 611498996 835879772 606167005 955868630 955532877 937327793 855594805 474556386 410365942 98246888 426285433 712595216 374466819 621377601 39013454 675970964 744284826 159790951 27530233 167003591 699379800 434157911 780347341 908878539 995423199 17285686 610065158 672819699 563214642 730003911 593411423 343420824 151138570 509644556 35392801 928342859 102484566 319127150 274526155 970446369 721188727 591068527 678770015 655565887 551353380 593590863 97872866 827931361 918092560 271815139 266887727 999524023 450941701 809679915 886403633 655989933 289708194 687439857 835836962 199259725 789177507 132852048 264048400 253409768 910535539 48270942 830134817 765621889 602297078 765983829 757562847 157955239 36195453 611718759 48710647 759740360 292169211 212925514 403397834 855108824 487796780 545663885 652095649 48708812 644114999 505106395 270811534 387406402 979672009 789131937 718109583 716535928 22968267 127475658 84283087 89217499 653611550 273457667 347923308 421563463 357707058 850098125 792058801 746369004 267987730 484641945 380398534 380338905 919525461 646160455 155805704 437904968 833747952 893450521 890587288 999285562 264219092 667533234 904992927 954751783 439187866 907025493 579828575 163344069 340760034 767337041 691669016 985963844 464846014 233153974 531594220 869675500 48128038 728204419 898112786 766913385 130671783 77184492 806746771 855661768 90238968 481000825 445279228 151002776 297897080 523194083 884289146 301329092 796838274 907840289 272977367 886562368 587455012 31351277 250748554 600595050 589213615 219950455 36187763 229042841 22322739 37442718 216819727 398877511 256573456 794640730 653358146 749975003 857914856 152647505 69129153 797143923 108651725 497191917 28329339 994912087 687874195 306047458 304848051 108424060 775165412 760561013 283922909 425098963 710383640 219268562 208027557 641185858 572260346 942656114 791589664 2336291 623831910 460507917 315907579 690442235 865681701 825208947 934758859 962712079 175075197 808462128 23207919 751264541 421987557 764449873 286768721 406202089 743567836 421995819 303994830 836529357 603229750 562269236 176582222 495296466 158465829 514062828 54309039 997413583 690355333 543018486 789489044 768591953 859140313 479618927 567717976 280528002 548355088 506571321 41208940 800054460 105664229 916350208 895660318 540368258 519746056 553804313 37441850 292204708 248837677 928386022 740786972 559919860 566359953 289257373 335371756 885917720 544019887 202344131 603198039 743680692 585408105 815948282 362064951 357725136 170183123 406930066 674016025 520561796 624196605 770772684 868961139 22025598 185001460 877192425 768621202 789285503 249323582 581561177 785070632 456256520 451520055 278452132 396965483 900180417 140449889 475435195 401079333 833215835 460780709 815719693 18322086 226884597 19032430 618526735 767805883 556547352 50769971 594361262 6131320 231253622 346310383 938856589 451409225 886186307 861984810 800465597 576210702 762670290 423681487 725254932 214445916 227001627 685320006 50417178 320749297 694471961 605748536 576226909 49298347 689049825 18049939 954884350 827298853 601685804 507667208 52172190 307853243 38203700 868400343 660565309 356685767 347581534 29223121 216557327 299424576 342504791 837627951 959790781 380648064 959968456 160034677 776339255 764077772 239117219 401247908 399118288 724037887 914890431 817827909 245488199 588532674 913244940 310433023 565055328 962711586 17543995 803333797 445890512 829148825 543866360 960404126 760044425 41317914 820029753 358014984 806073546 40843105 594988535 918307238 222148555 151808971 825247635 812080154 639731236 213719678 768247050 334464944 372516581 253913204 872176034 544248438 824777887 167277885 151568608 804282842 560992198 699052182 960837208 319006035 499572019 931579781 872089942 590933033 443204256 953314578 487362581 321656136 357556973 961183804 467103170 799804090 502721723 711183379 801427959 179911227 473945009 391312306 929267463 707534184 966860647 848076074 378025379 904769286 355356943 755427859 162338811 103064179 276878031 360754950 334467943 874929295 833309939 746578511 320444740 802624262 454940349 177920251 67595089 929814136 3080568 272724802 553828484 399498707 455054796 355765602 864007074 781258927 606442706 573963888 676493661 102771666 311127836 390047088 610996199 169706589 60456272 928473882 16938285 352397279 300279415 145252532 593573045 586298507 902243974 198985426 105544317 429924022 373071254 310863940 979056339 317593139 724259331 676767949 530355473 294769897 580877147 500729644 640010692 25659097 47615453 596539904 22452087 528872768 712674162 950869032 64826866 989157498 682253892 755517053 513214986 529901274 737344244 203964957 27867195 419251836 762289479 376864386 995677765 582996656 464953922 144199378 775858517 46465790 836704566 775681066 283589885 759352846 454013042 813022900 123711471 455129802 13894058 349389634 776933803 113563943 655654493 116070487 109277932 109786561 479987086 922709606 145093414 253918400 168041314 879179126 913277723 393522952 272258163 929157096 167827014 718587186 44722 304281205 575594611 707794317 563570902 873586610 437835206 626042452 27213135 145480043 517691347 407902692 437214036 491286630 650377602 878692049 797947762 542729298 967844879 885542213 26113544 525783782 749799038 433758139 975863056 585953593 137929583 308011958 108381145 876822761 899159176 519289636 502059309 771303681 621454443 470907075 922231095 739959277 186314918 689787758 8620682 784268347 119865441 827270164 291753255 160984933 822814056 55041295 511260557 342550614 131272823 424421369 19664731 154393065 831113667 85988975 255732577 587934426 87943642 857459115 221570082 36087467 242255718 744680029 21096339 850992315 703541714 948802873 373863958 283452907 278679605 707290660 838241814 393482507 196229990 503599749 220812640 559651885 39799039 599754531 926356642 651338174 962899661 742334668 805743119 533533012 605505588 965134774 301892239 843623157 973948573 497972228 66955735 683609071 918115466 476622491 884386810 868601396 526815426 727689576 473596016 716726643 567473962 910288913 8764262 76177066 313328840 578882088 577026441 376631147 840181002 42116710 144423546 451783603 544089696 610286561 727026072 177288612 538695243 53457366 204386533 601265080 894065788 652089760 536471317 980980732 883134226 816447138 221991930 708928638 828187428 666454104 325551735 103512174 571566567 851762714 591101508 105091530 391977595 400014579 376764334 350456982 551501835 322308986 869075507 585907939 175122643 190508491 124198934 69895584 718510929 805328878 527449825 907123277 906457677 487455062 25745443 586475627 180330460 912716246 846876073 101149386 365901236 811507701 551833256 67446775 808055695 350390097 15054189 714326559 676084241 521767136 539659277 173875231 267719149 894666639 301133163 292005653 794798041 315127250 994565499 577102400 495136191 345361255 513840336 164437640 689949516 326308131 813296327 728528021 209755717 349077201 474710588 937643317 258883265 273825314 122783209 428971183 533025151 901389398 944322528 461323665 407864651 958286882 652678457 848909001 551546171 261749340 52028936 777056084 153010373 268832455 164691155 194632895 459756562 807675058 526552970 861981180 224902375 509267071 990063685 481059429 660196576 373045614 666406690 891991462 341957838 52760596 959341584 301024958 599613069 650321981 316009918 871622371 799594648 66142297 452204368 133291171 751720568 524734772 912569144 297965076 918268771 934841078 658641965 417867027 730596758 51478685 538723029 712142249 177430227 545122686 369799519 144536813 44224414 966923550 161925126 491707254 22586689 740641966 777053446 248683751 992029731 812584616 423123662 692962254 401802535 210025133 335333363 678725825 477427244 901372825 567390779 844841538 399797373 898870938 231060488 970976596 620568293 923006808 301596993 955957152 307285096 547657426 47294624 182214852 981234265 938318873 237291125 504769240 802463765 871514761 46162329 544060897 131358729 283079764 483450233 368005241 332717623 378580492 851232391 426822745 774271244 112469504 877217539 843182516 31815524 44074665 973773393 197999404 769262017 60208124 105582690 495057968 176173484 733877414 521689351 776882450 927407733 221544611 183633681 603086984 614886989 281945539 961545270 361995318 275896866 370577706 256560262 859746445 470211442 76771697 675642190 569519155 833562807 504217215 872289613 184991972 799943669 137918028 863823078 640558829 23681644 453823419 214054124 480942476 642610705 49908904 827827690 117524022 480341780 277942596 197925083 53189664 163302299 932296169 114910841 690287850 920049245 113064024 309500483 331126043 395215950 296109683 198394870 488114144 282758590 819674001 276793952 808925315 359701257 366334419 908060087 183410998 337398250 7356796 98395230 130991535 176748359 320963019 650409846 806067196 350846651 10347885 165685928 178182924 300376287 973111654 521064394 244014221 235955281 518966967 215934438 427649316 510224116 605436077 174788343 702140406 64379401 21111426 11632245 165325683 181929232 739372898 96533262 602997306 589196109 20365880 486074655 291441501 793059794 79647498 835456143 530107606 683135351 291629299 938019513 528381359 869324379 97553303 39397246 826960819 815787358 652791346 848858921 121662111 799538157 284258300 613278469 264301951 925907595 440942444 729477725 86881367 885339797 590654957 122838509 491895457 987417811 78461752 843556181 195420066 749679288 786626613 446067590 398864783 115145403 347399582 885869626 46232937 421223233 242608009 742380118 645527511 991666375 965703480 572149480 458161561 12918082 661591186 443557930 216339438 788371199 917503495 835666082 639067556 913049096 368309196 752699301 122011951 601198181 978756869 571179732 120102705 940329594 65040209 968674384 564973049 132464100 795573319 170303456 800379276 58183287 253514988 390128827 143929881 859993089 1300404 887561875 914991309 718747126 945480418 7592041 426219433 742114291 962061476 732601161 969119415 103984160 482896995 776837174 179304272 539780227 567207109 995629062 383461673 106739258 882485183 901886205 560286146 249607726 755499800 296801312 657474455 477637081 340239738 210721884 383162812 71978456 174297643 166361134 150682465 805211227 552959435 61719330 413073258 824373652 549323255 884149543 726769671 211777724 151431152 763424881 839261793 32483759 202886776 502417834 955765298 459895521 739717240 976004914 771677824 615423467 518220982 253240162 983578619 533243341 879569188 359233737 434369723 49649892 317057794 149983886 893019605 627361790 431403432 876155477 146405767 58985008 567977576 864482191 289022288 307455137 160661829 42977262 287825274 156766482 248811154 766870638 849015473 712459244 264226451 922130719 807962581 114856475 473449449 633433143 505111871 431589050 666383352 693792261 520796861 896742818 145993612 216238492 794927157 778335040 515980657 203462812 445245582 156639411 708029890 681230525 435025977 912020744 925243602 335963900 463080544 366814087 428168485 693868425 755918555 73089961 451332077 583175188 555801794 598769425 951987780 172590315 408946492 367414677 508900583 381872533 410121401 768331104 44794697 913524157 667162783 892339459 114567774 401643945 412716414 134508778 630691076 118634943 558311373 274741353 618716036 577555496 231765936 749665285 41430538 303389021 653621609 262798900 324522241 597823163 965097563 730110432 728801148 462065042 820289586 661689640 665698466 661439994 825021444 917479946 312078878 267112578 204252823 513391091 509666960 555859338 657973310 816226739 836867255 231724652 639969003 340627410 987266806 481757940 15364988 151992041 726615864 159836762 559249950 901616150 599396719 813767428 528466513 170205393 196534931 399110781 929503072 924607329 345051996 573719978 814341324 159061805 481643286 362467764 585511845 842627202 319025485 502864175 287199342 824874701 105034601 58507747 381739689 891142698 707878801 586190881 267877754 638151771 670703762 524320261 583580446 134238378 341448824 219969077 834781801 884332457 961281135 838317410 641412480 568664831 300557707 712578089 186052064 27189206 851521678 984863050 319605345 10791202 568938426 730338836 59631739 498761747 216635741 11218204 690021056 842163066 632577865 175976361 132759792 760631866 389612027 648352284 696811205 850116590 199619523 485256099 255533432 941767276 856498849 806938023 3665524 368246614 748920725 970614206 752534547 644085177 607710613 151010698 662949452 627876774 373927580 845427146 960283584 719707708 592474782 500495042 217249324 468331199 401631932 43109709 185794609 54005663 146090586 719884689 479164512 20414446 925292751 396447509 536920966 223839973 120184921 697995613 232283662 799697236 423770756 448778511 607515146 304080619 75221900 326271639 719479476 514212053 521964037 464816600 301263665 557816566 971279402 610896660 340913216 663647665 406289276 736025763 47173462 799647356 784029512 46165256 693636420 74128682 204828802 695178363 37474653 125509153 199718678 166941117 333208620 716596356 128817274 961090613 583278230 275314380 699167641 973125835 505564434 216785185 48585191 879009159 234140334 448089307 197187847 56518718 348745267 775268074 397873594 968187780 240700378 533257964 555121036 162818797 202601703 786066418 91407324 672546702 650368617 716107001 90431046 123426010 333893217 429851310 793345106 856543610 764213300 990294666 721336588 757203266 179781866 49273958 979867882 689060231 672218314 751033629 596558463 191680324 438004228 746387395 558311384 886979125 242506356 388291854 935974182 458198734 183304998 900437208 372581983 910929086 725717789 377721941 511710365 161476711 267639966 548722450 596031298 974137390 875645906 957417541 547514586 155721749 566961486 678105483 288582842 336587041 123121088 650857546 513195441 150556551 228150133 296080506 924904018 902716663 58237886 119377553 949873209 913199891 58054670 675020438 329453456 395767353 360538836 687617758 829149520 856931443 778530897 165710367 882846022 43927700 419416957 764078818 500922270 281679438 99324237 487796210 311015099 40609718 797334571 994846128 924519100 163971674 561927788 348916204 299566913 508092059 979072456 588953003 796851085 606286970 996563520 262884981 44297507 454639245 978370180 139676654 945649037 980314132 371809645 259070699 546843058 873552823 668920828 740144435 187636432 817535263 750158337 567142296 939330150 761012987 237522367 256816723 586139235 377676109 30320099 346290455 966608743 695674677 569603667 20463813 371818714 377514095 46707212 773210881 873582622 614044412 221458312 577828942 380083686 271865640 244692270 943381114 886154197 805013388 88873674 19754706 259833427 214728313 336099531 220343877 479883853 457526902 955003251 773684809 283302426 250620270 645528728 444493395 361559565 150418447 239776088 64273235 901928150 734239222 591056068 977923922 469043032 607590281 495134631 367950837 842144359 691601692 365550468 315995894 458848758 419303466 923802567 186720778 465104872 339276316 626652264 936968837 608678449 480656301 314015319 355444175 637940032 491365744 343000225 321617116 407587591 382916506 625189519 333644376 840490332 397453792 215470209 30025433 922883794 646608075 321692881 733591826 295028140 382454602 962474303 511944858 470608758 860526233 789811941 531822627 433342741 659058451 227921764 239941357 590257865 809229991 418507218 983866542 913333095 495988298 562926971 954066061 484803105 361890550 259342728 839482637 73271852 499617097 261822187 47357450 798272117 443498642 916520914 924864114 844228619 873263192 429893441 300082555 264542357 728993571 840342806 86274214 544546694 155848443 782525010 59525878 516300097 520226977 860335282 17457094 441167960 651649155 263420651 656584454 737492625 266141598 781412874 464183534 570394017 986286173 962321146 659876469 712219017 90327292 424901455 29693019 10173617 841976895 413715557 712775385 517619747 796600919 993798524 909320453 53140936 901270757 142112766 941895988 313779962 376311167 382815670 375273478 37108859 820643192 273842365 632687130 374913120 863910680 735090269 605727333 514027929 421542603 615439355 121383839 995961393 470367486 196968791 578216967 886431290 5841626 507391204 681233783 39703858 134835547 914370392 815187362 529019057 474762414 130041904 520062054 255753040 111925904 667461494 451547008 141578533 194125365 952399803 113392188 613458350 889488049 506894905 149944787 694086211 695975088 366448262 758480077 754711261 656138243 256404655 427550005 832280410 829016855 40758160 625801791 35302680 753203146 869168931 116753143 835767200 265582081 308506372 235624597 194367826 492613636 109132707 440963726 673308244 859087017 591450036 916355907 443937590 995976517 493333260 212823236 241665609 325569705 919662117 649954569 226353462 557618194 24390318 395434894 893791612 393184185 151483618 250702460 998192631 463693354 493557122 312007841 883283371 699480586 249419352 654375425 792128626 991672800 172995345 459641969 960852053 642566598 124137237 707015744 468265027 129275025 403480415 797967623 117614489 857954078 762677918 467331270 325003503 704610272 703982066 760148416 633326644 725454483 518048375 185514306 823641299 355734954 993092534 177701565 373466246 812840175 258011596 901872345 653932017 737584427 892529370 636908556 132372517 531947190 644186149 863536406 691209919 228239141 641327170 332487003 816253534 419032597 12229651 740327988 403409893 32755040 624090301 136829469 539297179 337287076 415271509 169148194 102929973 654730636 467415349 932975735 407232064 272189524 478283070 814238498 2970053 90053013 778246563 924375573 876577411 73104191 473948768 995463277 760253682 461958489 412814585 115153221 899602649 449069018 550326781 770101974 21428605 367661854 106137454 834274004 796020174 713995787 55703846 422883555 625227378 704957087 628564837 555031717 274175076 983985522 984129357 888011148 206634899 998286589 583806116 867024701 273521091 97866825 484593306 290547395 593431289 857420881 296872583 463368417 645762411 562299997 420514039 154413193 295949320 949653337 330062446 808536237 799813612 268250382 595087295 386772116 547948631 89252230 450992728 458198145 577711537 652373930 621521477 313941106 842610582 598212950 739828105 382215399 929583215 636925282 102203255 407598539 859967745 488914158 834628026 397877074 130248401 388547669 810915407 597058160 778923303 496442670 99810322 73412688 903813598 861033059 709470986 400143574 729600327 40070959 52423677 564440297 840337489 691031251 275748246 19283035 801004472 529952124 213103573 303407976 182240255 538403280 507838255 109228453 377770072 568243950 301139899 896891637 683715839 539682097 68860920 230227461 596754298 176930779 682927607 837329727 614382186 275880225 309116440 626257653 310657657 864489952 974581442 718249630 94372188 850539260 120544664 116507688 827135721 308190127 894016423 965001096 342821846 83980410 846013666 329263570 584457366 21393631 554598673 48675127 743577886 765314185 525959223 587700531 494711098 588973138 413585240 991252575 160182323 858512329 582491437 19992445 660327240 877371688 707658927 640704943 296998739 255084684 960531368 191747462 703031271 305686137 421194712 756163475 897379339 545817311 486849633 904485250 650865707 464857841 73407158 303646162 208108484 482791369 31238397 551070957 269347380 205954714 553889493 879684789 392500070 904801509 653202442 411699828 579867261 164615437 383163860 430116894 541785336 451463522 195386257 237288559 286945536 34991280 622446507 410073939 571846508 482202913 477585409 190864575 440071288 882768543 956410170 339379906 741648124 930614858 956112944 13037261 762899616 525035455 654822533 899112228 424389767 392963004 278047057 610253773 850254339 972535510 872655624 306734117 949892313 808028206 732600011 195733547 871957279 815277653 247217280 864621383 350679498 334116618 392181562 171665711 375527896 893171053 92055099 87732091 745582887 331698465 898625412 465248173 382283570 763600539 895870113 969463564 277266873 608307807 57513625 607484327 980133576 982513057 932228179 717578040 31624270 4585028 825795176 113955941 112615874 832920082 122608882 42793781 674921289 594528329 638505892 812227894 922426505 138893131 448099070 29308906 954020514 517885958 160506125 534577244 211822215 66508612 740766549 743479653 893255998 501139484 816162671 896947227 388012075 673098437 651684115 74616534 465544979 293894484 104165275 918439600 929638504 543608610 581981982 288679443 150033494 309297845 533209309 445109734 957857136 51263003 613646612 645314077 577330236 424684865 406042491 314553713 287603753 457810508 209717371 115848762 342547894 183965480 644188365 591884057 758837175 929967689 226595721 56278769 944686426 103337188 216444181 740149736 598190863 55814560 453309919 271782883 805739373 70413404 827223448 993757189 565628210 856064427 629350368 948332505 703023496 362023523 983442843 621961180 465527328 853667345 357231224 321387690 927406744 856140340 320365372 415479012 589228802 443316647 141317395 363075708 581552379 434997436 76425212 734686998 317097129 65522623 451582520 324791043 165779047 454963291 904699196 468881276 831375755 543296406 992878252 572088574 752644897 33289176 505963119 597545960 396601365 923010926 683909771 298009731 851916023 678593809 256224270 640767986 370964388 641118296 505680559 562553049 86367659 25795956 915122040 903941980 794742497 627711304 698179075 112367725 924809729 138805746 25732989 14352436 835054941 248331537 769420711 34934248 836616568 413355213 117401075 529234897 316763500 843371514 433477758 908515999 974657511 299974346 897027610 38434718 294024992 134657570 422839616 497595124 493339853 641613306 830216709 837526813 22499118 140535063 259229084 602359002 584996692 25070144 712371071 831306996 858868599 541481120 644334197 646159474 925868873 986392973 223004311 266603476 898744397 856811945 430545431 232559441 598525518 205068479 266048217 660963317 768475207 449625947 869129095 438497076 762128862 151957964 932904682 629612803 456500423 901081686 658137140 704086018 861778490 261899107 92645414 498392231 494625561 23439855 716989366 916517395 172535734 462935343 898794187 873825818 397131444 723298045 882785100 951044640 962067542 522213291 386659210 815799013 592278448 37467037 401379353 428032697 68652771 676826949 593832750 99039827 458858731 684571353 87143470 270579574 308131491 491029033 253684937 108288904 82194773 886430628 656325385 356999301 711245490 517734196 259594206 334282796 198015729 979870811 287401908 320300331 198422329 370344457 660959308 771917162 541821921 279955041 963904912 296723880 804822517 83171068 573921835 796353998 848088839 864149177 309356095 443689588 444567067 186545685 950814218 717338376 516076429 907753210 399953401 82056286 99306404 561371778 206062106 310755030 98960585 288931537 273331310 933270957 388824397 102636042 260353132 892963891 962434263 576375054 500072159 423519805 451473805 846376810 224244430 572937988 412894308 298743313 952543097 772338611 244791060 719280797 942368583 167120428 268127875 543325611 509221563 940047859 877208702 245755929 40503812 627554194 457290800 20416313 83637912 692019230 795181619 113234499 22601901 151301662 665800657 389492362 247745925 168192512 982084610 343311597 641905 565299125 716809209 460701631 279996951 3057137 415476043 844828126 171142976 277563365 364094966 305452109 951480717 274012326 50413372 953431644 245214338 869842457 233848864 569651648 427698317 805746780 850653979 435689668 122398098 908655210 448714634 927393770 392152882 900796241 115013184 167833302 231165734 725262853 809891133 200094565 624785764 938064105 510352260 850772985 768850294 485113736 164975501 193970947 126084638 277715922 702372513 863337679 854547713 890113092 777626585 83783600 214018889 548230112 231112880 96576834 761592006 783066797 595009109 167839714 291311956 503562572 670653513 963471435 26362312 778308272 21761199 214464648 967645351 134224719 72063386 20672866 470365695 524948405 723168244 208345135 640200366 579473225 365409922 834196587 22486512 137503282 781659041 235062259 73297190 413453975 959740086 129778902 666903221 503156529 728341188 415197989 24466653 745221896 855375374 741168562 399446564 590684591 429270756 916654275 878070392 80389901 803767841 243969567 969450698 691684854 723674634 406942483 636888214 320743482 546725148 191875933 413272048 863058166 882602134 696874084 859707723 515087778 218628569 640914336 946467659 157041770 162863456 994705332 830458668 773254382 479221305 808681935 416849637 732341351 45475802 746949535 547552481 706381005 637952522 614172960 321887692 195755965 807463604 519038864 919659358 987159615 683614696 587203069 486595984 30568610 370638549 517023543 925384241 994447893 827686271 445016919 558739081 270107922 762125700 859602656 882721768 854079535 321455328 330987790 272125411 914476128 180931855 260567407 473857564 852228201 706718379 755649329 524365992 331641680 93376 132825102 232832509 483501073 5361312 12705930 751426130 508118683 788108215 56049935 481085680 23799632 649883635 855161006 966416148 24914170 943072539 152450846 277677995 996338221 11676632 288377745 878895100 803193460 428465617 485602449 956440810 390804529 502530953 593527008 768990969 361952083 250514576 100325971 129258554 507712785 785909169 51034964 904605530 763594116 872731720 791433183 966601133 767525373 163813833 500579402 913593388 554087651 343687385 112054719 865617810 946211866 976525914 743398016 860808113 594246477 427921940 967922847 358983769 992895422 547206352 611679640 114303239 628678762 21038471 773419558 468519365 644987073 492360605 25031689 192258154 81834254 268798047 576887917 321355796 273575319 166672830 540203734 473639369 92828540 787839790 856327365 592164670 522886299 452636167 163406865 181116498 353515394 144851942 20942333 452215512 106931321 724819605 165359298 810833373 177366135 222668857 191511397 621322279 989207423 238035890 820448720 875100048 174074830 476803381 794458089 38297297 884726726 362858460 561913713 922906094 3509690 51586486 442448232 167208132 62606269 397722690 142638686 257085110 797893861 725095430 411643441 232265476 941602642 13321455 508137407 930742180 159243788 686359307 911800026 366820215 612492829 315155893 882278134 251405262 195347883 763358163 435465538 323728956 320112242 312951141 816695702 628505697 708065814 964874220 78498282 361124587 988654359 545305967 170110910 836889000 673656611 644704329 93946019 132788264 186719732 307261133 164381633 670279593 623611002 183655199 593349039 559334667 170630103 805078903 427576425 887322879 110630910 874079637 106919447 611844687 13859859 736233961 299828012 695085994 955771681 674544 32218535 427063262 284861277 585181457 609346842 268463684 654755867 882071990 955530422 916653578 473547519 816105692 972454909 536351366 121556020 643801533 494152314 514097439 682939183 508060754 815952603 720080866 516715338 272402691 361239843 178983268 305739546 636852143 473672144 6147359 309423881 244784692 347732550 401278966 605285174 403611298 617958049 389448722 480314284 983275152 568355246 895456664 458644577 702819034 848528405 265885472 523869309 730996371 345440472 930162933 820635437 73928128 918601285 986999671 211788550 854375658 53597383 123845469 288948868 973253872 977993754 671865655 9084109 712606872 670298574 839789736 861091515 421471088 388202146 234296579 963479597 634093552 683799648 930844653 464428109 638571283 709562804 780442950 177377106 556877710 845336904 78593337 865802239 912752540 556196087 304187903 765389088 639375841 200165789 105625975 951639723 570976710 404412304 610342916 710103790 68184860 793311731 294766327 442489143 651341264 488260863 485139 625050645 459910968 725678301 925792420 379977221 692719296 158809608 947020312 648513793 36564473 659586962 926494424 812058894 680305026 76002990 635600834 194760453 331561897 767132526 375900358 368528525 940069520 248964870 773992896 959461987 236751429 353716465 162877701 110712669 589490095 106975772 62832981 632189465 901843107 292991142 633011879 746956063 193764841 67719709 530645840 936010928 868987709 122015738 75569457 728546635 657181915 207936880 176732093 925106501 496604255 502820514 240898781 43706215 87818486 969494067 400130559 758530673 43089209 460842363 457035897 133901092 857687456 820739645 562092746 830127452 338064437 545236639 493033526 410296297 698042717 427280814 867285482 819171468 28018394 361675623 256593379 609994013 488047710 972236621 815113367 42495621 413806856 45488480 371779516 706336462 820463958 393988204 931459682 652466508 314148017 827587014 464739246 817599572 729335440 520330503 365222415 46711166 562519404 555936950 519495417 809222747 583224121 809564231 660216804 954695610 346950734 633420898 766979680 58601181 147528617 569597994 852110399 124944844 543821732 884295370 228188979 974840692 186415093 117141504 173719266 441820534 455367233 990567941 825990875 352522391 980441385 428253312 371640607 624954642 973698564 391407925 405953514 611050370 267399732 747664972 405277024 41480836 222999074 624676134 597758491 154094452 675845852 631582035 76483095 925425343 185468135 488516724 688005232 65737271 713461151 130673336 208457710 616948429 241646291 688414164 41518856 525941431 345428006 100434612 127733328 501630110 852195723 504775006 297392198 707304025 784277382 394278269 928339666 609531163 884300053 265365969 332629900 499093672 91215510 160462816 791340986 616350473 641243874 216261821 794538417 19467360 596870896 785217797 791618427 206347308 597810492 938184553 71386872 872967864 329111199 984555620 312360823 924274010 317021489 469551680 222299402 526494569 368478803 33795257 87965326 816888839 301368065 372048003 159556751 962428479 174639461 701560037 520827766 269248711 726304660 233317124 233662578 474206597 179944644 91612465 36306010 8352126 417240995 106231673 336224403 146155900 782391945 27112559 870520951 679308679 110272697 714260904 812482557 445146888 199410311 915740852 329736695 870039032 334422747 987251760 666460827 456862280 454580937 776105641 21973480 714299325 41563138 718280847 452236342 819997250 785642122 23684388 419542582 128497095 264936442 970869561 784199769 553951160 101458815 982628637 24650638 933829469 834014545 223048442 993795482 607671114 648912329 896267953 371695267 110900325 31226796 380760142 680062335 860985335 644618683 411088262 650865087 674275 757869131 213967843 729752727 662923222 690242507 546929522 897980189 969132536 12509521 111958948 486663821 791267868 973481514 828866615 592220617 944947597 730820798 726737405 215134332 127741418 43388441 279015211 574653258 711966530 495998996 378391812 275958452 455564587 880540109 175747588 816723643 332677026 50012183 443199186 81409784 299345 115167944 414496842 215741793 642457392 418050435 588818463 127266662 327719341 946953124 613717905 834287359 805055078 985473734 212050697 419948932 903771708 120751595 700135400 439114315 440576982 220029045 295872707 771750271 421443925 685457278 930002065 271528832 37665120 972734978 94704495 861123506 309876112 32388977 122429456 310892021 781392007 754615669 486647070 76864403 49783609 380346814 466210121 625095566 747790908 30693252 189931085 46765832 474317612 226904222 486946531 263734551 376267645 382870267 694504021 93517471 315168611 775196277 953080881 134394790 331691791 64951568 203601095 644992877 439220295 353816096 543539838 154857292 56594969 326597418 289651645 298417771 113743419 543451331 14152145 372310034 926534468 234176937 732252336 764129089 884460729 152472460 35962702 550183095 361654068 862494412 855762387 511216758 402260948 332786650 363847076 343544339 675586095 250841685 966253657 875687887 263170470 37844092 553213441 136380421 699376651 205233371 74225275 720763029 928643092 676686672 597056948 39088037 690295896 986742742 416096250 72426561 316871796 258782043 798422631 553130166 193335314 841509572 769727820 176796415 237387743 70205756 658889702 81549113 158984434 461815231 808253212 663701598 769591746 476273742 870871357 490233205 159521807 142153502 769130205 538766391 929934957 735409542 96743845 808254145 65390205 172955269 360039238 65948173 310765741 616492983 565292575 902992555 137144940 319200477 526296861 739407255 522009234 995082983 163998300 156731565 860862465 762498927 316655304 806967235 591003933 937587093 244515379 419753288 423238892 469208282 942064876 862258788 134373319 145171302 251011609 883956320 352517667 161569690 189318544 901794223 296745572 914812440 607983029 460619374 179515790 811459384 61316279 149649435 225717813 146386466 213839330 432571409 904471529 786672784 447068763 104198078 581366760 909332773 776506389 869338586 120834259 395592595 559782378 131046519 693593023 412484838 625945381 420044472 204870104 263787219 908418050 210903240 491880464 771275298 823210920 469764493 873015090 475929822 383173415 799114582 734303640 180634493 544023509 597649747 42505039 336941888 927365823 3878945 801270015 643179315 420828123 599579209 635427061 37847795 435116986 478428603 796556232 987809469 334040059 450323073 725024838 112247825 831573184 71542716 717382538 17676408 703677681 286998101 297932375 589300160 416829706 62365507 73700766 452748025 508183201 625364899 562472830 270253578 839571444 621140388 553964032 231053906 274992311 751260547 121151118 826486687 672067233 710213694 825558423 746598688 403652362 240379266 221254988 858762850 707394194 629699155 910145037 684065632 108276502 462478654 988339972 710257256 473043612 183134914 462026836 556799087 210366013 910780654 899949032 465873911 608230321 204107191 16246431 253897143 661364955 119624404 31945713 321438653 807099884 136421067 18846054 412836536 803779541 529882948 369594425 511750356 473909761 392011586 89256866 433480139 371713420 716823837 609237855 818757273 210329117 3814739 813952299 584957310 157709072 10417433 132457137 871706749 543454723 563524231 49964566 9855210 523985807 333681058 559000161 21266823 989478232 960234683 383458612 420848285 135410623 991618860 121092477 267421475 823544226 269934563 575919596 202945718 822509516 272389796 865932122 163926343 629770131 219791641 932825483 258489919 460533173 617154604 302247692 940860001 827930254 934157483 146829687 853862409 674529276 588772613 564222290 451679176 793513360 84342184 579356473 403381519 813505096 101618033 802042168 833462171 344758046 560060705 750257403 873508015 360046737 485549575 291497305 51233321 435601714 41181544 591631082 510038307 103503569 100030610 384386149 917321611 98432184 403519654 877866642 683349403 762235801 263539749 322123412 967182044 664121782 830434747 867992797 82587972 908778394 407047229 780827526 788778372 198636587 692014704 862932333 236340495 155791248 532432120 969993108 927679337 950451324 357313891 696318646 741544438 263594861 733270295 515573339 62147114 269011651 103522724 529366009 570142702 892303544 934539960 785171399 142935373 59046481 986654436 495672809 232574848 46915915 226730365 320115669 545923413 499826242 922069238 274835560 96376476 444529806 127480590 262047515 657253118 47261184 577283102 15099067 130149321 321586411 60602095 516529360 281897689 161445282 806672996 823161176 60453221 566057314 96038651 616916407 16167196 240597944 11882635 212749373 788397737 856061016 848873478 749733100 519968772 817761795 240234439 352230847 794317529 356833629 602370459 746178275 848231809 520532047 175571800 807605136 910909413 390258521 708448785 989687612 363596417 699512447 377159528 401720219 604410054 119207156 128027647 254400046 710868471 119349552 131873650 204591926 121788938 281322925 136787371 60375785 956181087 251610881 739822219 178143788 231484890 108717757 149738672 550479058 359419853 490462633 248604289 247687240 54555490 396705717 763519280 446395400 849287612 857150694 547755450 17299519 552774806 718421226 28762730 61028711 70401438 265382491 249680726 933187431 861089155 923097331 419010311 882714972 905750769 471094617 313886715 629478595 413189007 253919309 896976510 425193679 478110029 747455555 840002330 73367375 384572285 616853229 823997012 48866977 290578936 535362626 758512650 939958865 285657140 90945599 929004215 361797976 818090462 680513786 887455779 917273680 619523174 301346588 503198580 608538545 301394294 732851646 15447472 216186033 261950762 236980748 428196872 937244701 225137056 817130218 704653099 980974489 432667737 79425285 864252869 387378488 996427967 64241900 82400262 538247194 396620159 407234844 645986581 930499209 108594600 379368684 908910392 795517063 299024249 272852626 535659812 211159190 531351197 326519385 969933801 35591935 970800484 20794772 479563696 363738078 732011420 650539874 59413706 613831357 461954933 507764686 2671062 432943419 761646924 325128176 864185400 732398913 728287924 873070609 799324840 420245268 627698535 354248220 330875756 703607574 240672816 790011885 516705951 794565305 764249700 133431980 913963708 687914738 480811166 744405431 436950264 408917575 499038771 260142499 222205378 350936074 831231941 899246727 31296655 222885407 423957839 207383825 995246157 28573515 246613127 999566219 743834382 245139381 685465909 327784138 398822243 160809521 913044765 386004432 141013153 496259675 519659606 215107586 427275618 225522331 207127430 401018082 423867156 319382557 756669042 231205793 491385779 162599837 14112563 260647701 599530255 961778882 796197854 82219000 85297914 604078481 293338703 165833466 344755535 173859985 107726847 391859991 45808405 856345674 608581967 306261779 458131980 540907071 225231721 662497915 213426323 16002600 323403758 500213005 231674696 420990775 791934472 4573442 108790366 350169590 313022948 993892519 385248100 502838000 504763389 604869864 784225311 34064917 385844211 189184766 797197563 473236226 198416727 71411900 507653376 269810870 960509346 729044462 156088002 12462542 182934490 137275990 40050471 560207401 814498790 194330219 218819951 890698372 65673361 831347844 671546088 97775954 71427554 763170897 849018252 56761342 98520573 653274772 368466549 736165989 354715841 192589895 457491608 253961668 639344743 591707060 760033548 343340542 494504946 728075202 211194493 132490328 130712222 14229236 572491489 157540236 852538066 71689815 821127696 825822545 97238618 357405665 9535858 384388929 633394640 449945542 57581787 148136877 566577727 43112947 965929340 994615003 581803829 675267776 496392157 681749493 797775385 322297394 995273125 696131430 588194155 459450081 646163821 835963846 780518575 134307582 923866032 942208491 961902137 916986315 727700350 135698317 18889029 806548916 374396312 256921052 626667135 403274164 814412886 506696416 42592581 949438442 841867057 991515772 67146911 727789435 560940291 133166195 867441462 480555615 996680626 695090807 114361050 594582334 445886960 910733629 682472066 402375433 529434556 406031844 877623127 618933120 974775269 57439955 163634244 400845865 265308650 32220054 518925444 24358358 640330372 5479660 390151459 357967896 876559067 366753240 714284504 671466739 900543267 740976272 549133883 266663649 60364343 827169945 734811010 135922049 661226470 247547135 83954612 724265598 120747579 902736990 544577152 613321446 280709462 817314272 133440143 350965718 690444135 538737833 502293121 395570342 572847080 357795971 965209678 244645402 912933717 375282411 868635031 961889657 533926576 261647739 587260011 713514664 718769817 753986890 262073796 475355657 716268009 44437352 155054795 468046366 478550128 988551731 572827387 226971976 928855145 374477786 397634259 975225024 633736866 25516545 273809468 688793410 738150803 333124655 538473104 81007355 44310403 677838174 529506924 884786370 191626383 982700278 166507472 478503004 460177522 881983335 623617841 314669035 508095666 845397319 61504149 385187772 182791171 752011746 731650612 136379357 996856271 687277048 412975273 540454916 377240407 433899125 361794901 577610027 250762768 510599626 676192316 616847626 591553099 780393225 525269537 322958422 481460152 790610314 212109705 75780428 968057945 106153836 43967773 296875697 558000731 369914669 32692554 104528425 1117086 373841157 619551383 348878440 511552718 39616645 605626815 758619145 128098258 141467874 115736989 778643387 446227763 617784603 298274724 634423703 378000034 551321542 564367051 599109918 666461339 186948436 807496521 544074630 438329387 119309872 471392882 589012164 242414829 428231668 718961106 363737640 779215839 715029812 289139148 530159327 282777350 698349754 202587339 537855058 247225579 767430241 986794410 439685374 377863496 93584737 26433309 437867313 398001723 839755484 202964058 129999039 274142821 602382845 736737970 409602921 48885327 145491096 969982238 110988921 229959343 526782115 610358183 886547413 76936309 990608125 293638607 965706159 340616904 296165368 71547413 607411235 421549199 391985501 434288851 818810939 774220166 885129819 830696166 535819209 424515341 583134549 603612988 643779214 279840522 930777831 487007342 89649020 297028120 764640373 143975790 509914876 146320517 389629464 303131917 906509914 940747181 636420174 436283228 186549583 971236127 538384888 742126755 951733745 539496193 824243859 602816086 597252584 740885708 4830823 57371725 325963339 979642622 442704615 142126245 59996514 1968160 862949990 74346931 605583385 257371826 820799230 993934054 940609718 732100208 885136304 543496629 478636373 516214156 34931842 314380080 955618279 563841375 422617971 594333420 235872518 374855652 868041105 619051943 747174928 745684216 117630008 278921589 462136331 841243963 25837612 676726121 388511156 357560041 925354871 848426509 193625173 377087525 179555176 747708948 803552831 930711016 605638569 859441783 582212373 720610703 245351328 710906579 7679776 95619962 995692122 415745410 96609025 935085057 567858665 325682264 171874109 53623875 812261413 148261601 725065775 641947839 863185909 879751590 16866382 124068394 865574696 18585039 652471763 801543353 220652724 423462153 243969268 213490416 578454882 422501502 550109720 452526496 247548518 294122296 672575503 343591902 903192270 97111955 898797034 635690210 295450181 626796969 451865834 350179324 321356620 746768226 918247494 929271031 17035000 605425812 673212851 25641286 790103471 561197376 669953840 77096405 460282596 525530042 200670331 693986204 833429084 31742765 568208721 784258251 509943039 963149904 256189182 826774590 547143660 476454837 389833153 34751207 640569027 703783013 527823343 93290587 549490866 135185662 333451697 195020093 960117373 407400348 931567373 67993065 252782280 274595972 576407242 609751358 933332150 82026861 406708713 869907663 270847316 735056348 806175617 897894465 883963440 388790570 663125315 381758734 943626805 817394780 91649012 325449180 607458831 867604917 219217375 174015277 795123334 136167275 464852109 651302190 794401694 835026253 891196616 981599488 784743498 925199157 836941208 904476778 871287453 153486090 524129668 411314259 857908198 736641219 661502079 257845238 613416944 595272854 832808957 35552397 424962618 148968277 330857980 941487890 781456786 48562631 368664528 681728954 377191518 64611981 354989890 60475287 396723931 656742944 929708347 626938556 322105079 876323940 272735892 908388669 674633981 579384251 970598021 966272195 492927817 935013953 89004833 337873823 142051111 519862006 436176315 790198738 972623622 642109909 686287243 829558692 284686088 439094336 638964847 127282263 929845962 986123143 615189856 432583449 997220375 47628514 397745560 685496994 621636788 359120947 376120356 814026564 622520018 894313220 373967714 472111463 851027673 955844947 816604936 693575911 595171 434487786 642205660 460166757 625597419 814267189 218922491 956913794 810777467 967675284 464421187 533999159 308051001 38198983 419406040 491745791 737413151 618787737 317692120 222419892 69207042 167980807 571069772 143567843 765997253 796114192 950940453 242260625 386698204 622100344 942578510 384991292 890977278 949520312 502061960 315579220 443928480 158456688 942667578 756542480 925092757 449770734 963390277 811688893 114337856 669695430 355204937 743281182 790575839 530979908 126907225 333531954 256545321 910491940 397936386 670334164 946061630 484997668 971703072 434108627 702418561 373639260 537524900 418838767 292605095 521974063 782736908 286875347 955524681 874174016 940943180 274731564 772128484 616271945 453921020 819036803 656774896 798089821 720955410 857619747 129652479 289489490 264230499 461687190 714490212 76522942 440530411 908600134 949421531 962193648 72174681 209779597 52443668 731792278 588490422 976838357 248929657 107994871 23881885 424647041 411045748 919366492 952695526 966769512 111260859 253507978 347930389 483153162 476587396 584510364 326657348 793477415 163256620 550146579 236900705 736778343 587810800 532838596 534750736 33548780 637906754 287497164 540240550 951771023 118647348 579798785 956966099 35594295 148866719 105810248 733447709 793536709 533317423 656431900 758716541 9631103 226708452 256157764 878229711 509471821 511213463 253101808 933981797 766446575 392993090 915957236 693873273 301858014 744340926 848262232 171600176 440058596 284894622 718866400 685472277 229713729 640290711 72743896 895802715 752295870 989850818 685824389 942446551 786736088 144586205 798821411 272448146 971311433 542571734 125187557 303101566 514073880 410443179 185522218 863781762 130804454 730029245 454148240 145107256 409127099 552175244 52589590 450354767 417093857 159266563 113339609 373780132 584883000 835042638 222806075 691067984 737401013 270481962 71613691 318178934 874233683 863721835 415337347 210447614 267471437 601418761 864992738 695140030 949864068 958297306 546864786 383520491 120119086 714248395 859424281 949314030 692728562 845551399 900444702 266494958 333107858 154621826 222018012 288418957 864954957 344577981 140068060 179746150 415625676 585008411 535972989 806730076 554548114 597860042 995196658 394642625 290356058 47944168 12743051 341735099 216415871 207107680 531597372 319525395 338703898 233157223 658557128 257309179 379798547 515498436 145175576 693703959 26458840 183288171 497860882 775562397 161900145 723551309 380511475 609897975 200734896 224420991 911656019 681281605 757590576 691699942 109587087 448903634 234187918 227809524 53139211 168485376 983259653 201133361 164849533 191737645 924518308 886805457 983991495 452059196 497056515 95606634 873037364 917395140 31674715 232732512 944237971 610107705 913883789 620925220 860782402 452863715 455672477 612857504 365618993 514380987 73915771 359954900 446844533 477987304 554062202 716883578 33042725 909506872 708453528 301164878 949146423 415165772 764376540 119023684 132133832 808210889 1649070 214546093 668668276 552718733 974500451 61533425 157998009 748045191 208917642 60376344 836715507 327524925 929932289 519608674 737900254 38797135 520423537 216262066 1557676 65601127 195408016 818741795 396270283 205925780 760722155 73933336 178751721 487315659 241030212 578214969 436285521 97911041 497107366 651112524 69735944 56545786 604659946 132230766 440365415 890711256 862530309 574973029 656009593 731884170 463862437 916054737 757752392 574400918 429065566 862240304 256615846 571148100 781760002 501440868 267490228 680537901 721211009 401005963 83338624 542446150 8573601 870304394 935816103 972381222 666563687 594307172 109913169 254806265 195256791 900044583 894409542 160260731 86559639 237525990 980777723 622636762 116826725 527264172 68328397 780601395 428692318 744915409 5975231 625573278 459685935 21509841 120491299 611444332 756029472 249990141 784814775 794656608 546589863 47770959 797676800 924001985 116912355 336367904 120812488 233355967 498717777 646001553 601395240 592528452 243130715 808715763 859868133 440685856 967770891 710137233 588834628 508202157 635922993 431038584 806146600 713608413 157106210 885263327 160538709 6848657 940582066 465730399 51381032 400602206 515312248 620834433 788553270 454475286 899076775 113575780 153180520 454222319 362013326 87156654 872032216 949788512 926745085 613340966 12978265 424947431 768863885 896205332 221380063 637475213 699624696 875624494 574159706 684536249 430582640 75239947 374969109 343382574 462689374 775476909 248771109 208492793 31858767 190715693 60801702 545977120 672160609 583353319 617157435 763051983 386250570 680451880 635309797 110311685 187863360 14869196 508075721 967074608 2985964 407022415 205327728 685949714 666536583 927213021 713099704 495650790 176861592 367106042 529314866 51758764 425545123 545228219 254086422 338441936 374788321 83052636 763300666 982351645 42390240 849626085 9733012 231085431 146786844 927380684 992277118 562498473 211088146 743281811 111302378 860506781 135534312 316958066 286359670 282560782 20756027 199886983 461774693 632403582 483515801 678393761 84122177 772323361 229259016 60995541 992059115 94601077 207745791 970796834 243513205 465346122 305130373 295846315 818381101 4973477 518842107 672259817 322789618 85564080 60914211 732636995 681570667 464769383 367743741 440476374 254446062 187735047 228518132 251830368 661986525 690058222 349152191 249258546 367939896 364708787 745473003 463559407 851734120 800749371 933181898 668910522 478513466 940277851 1194325 82459941 264451041 143090922 94802233 318659767 716329376 705198828 648340686 781582075 540704189 469716497 442893042 188196438 979012572 742120206 369924845 71339479 650409484 166366607 351483094 301657900 302759650 493982556 595195291 846436196 315685921 373406594 410238310 517981906 614393557 643027362 972472092 710127924 940733259 157339130 506615985 457959179 794450169 23020442 345326093 910678539 254235332 349192367 138995937 151278972 567228616 66313379 427825459 928530226 865868015 495267741 498209178 66946289 445168512 541816043 633117201 51142209 871347528 502607182 639516465 236439337 570849063 23543623 253109810 217629244 524583057 839541531 866934157 181298449 622487753 430343606 155557789 60237904 430714813 31244695 584253336 698818538 102060359 244734426 784285461 680005623 862506390 911984677 798334627 338802347 372482039 853438122 247461232 813530201 540160658 399951196 60117051 280436564 398614633 683961726 533641212 41607539 580572621 948544882 257889787 783750351 416600177 434268406 844104120 842825382 405006909 250251746 508575292 301879066 665326396 944768993 749859254 506034550 579428350 331479073 196122542 112051437 379512529 998474567 565936016 460992939 275259132 316925949 724982056 504085611 723213028 506102061 336506917 256960883 336456876 37247363 60086936 131586181 294116498 553192619 316524997 247230610 151684295 576577250 155700647 646733945 239128433 143526201 347820971 993138035 331960070 722200218 863798756 375795060 531929344 953750982 38693508 29289298 245812029 481810422 211120499 778134369 26190707 512329151 347583613 535128400 34053716 869885232 287304699 239282974 238782937 300824244 84416597 749980691 196206395 635334795 555674744 932241504 295828967 710833508 385094589 679226519 535042434 347607060 515892133 472238685 442686845 634999264 971498686 971968032 321591140 71136269 494214743 406134850 417730773 766901430 514677789 228848642 63731176 928820879 917122206 973710654 110844624 830799999 723759200 246889258 491008409 437879710 805437081 364718192 901036794 504601231 234199626 534887031 614299276 434800487 163039599 474361567 179463099 949034152 188253898 44341535 914423607 38486446 917745541 307514984 518232458 694338125 924645327 954563331 134946447 538852155 394528197 667619995 759271014 189302827 486022591 191563350 462135097 213828814 648556279 905300175 102320714 703286719 25696694 862747944 164180483 780597206 874413126 123063344 395049165 973977608 171106974 655717440 310448653 435042833 433316582 439451557 530892922 262422943 312277229 155168236 753756176 791367199 430470863 516236000 796544329 672985319 448552816 706406439 795580726 473631123 56222920 692858044 624389219 276662432 654682884 805530874 56360819 779729037 244805415 920743366 45936992 300160226 973437879 605722767 66111751 668602735 296811555 239822700 342965213 757542208 152545560 20106191 947532767 167917891 635520502 480590551 115097367 707873730 328787617 81520390 192443216 779376040 198004588 179071111 551635226 994325 171538518 745991697 943010006 189995227 418344625 950538199 800241198 886968966 20636079 586215046 180036504 15827484 1893175 217054322 975549304 324811750 357216817 242204847 97341468 436336943 384367419 769312321 559339672 834860491 504391382 755564916 42971340 583013980 905467004 895722470 558262048 635453930 760577898 412407886 3314835 154195843 158925117 600219221 122759163 990033481 578961043 669260575 42969640 895512292 127966568 111745058 307356466 68060389 903180456 163144353 233907196 640807928 573852131 746939183 999403862 577567721 181992576 959025774 598791778 859087382 247735395 651334190 523290757 67457632 20941610 925108797 752843082 710811587 648140581 283461626 898385879 546068557 247712285 522593043 894312367 693027831 35605678 875457670 563941702 429981035 851650552 477879643 88824635 132849372 809217303 488996867 425304388 483201396 125094369 55728414 513330303 50462177 979539370 868244034 332170713 987297123 303649176 987111365 864240229 401585553 438945126 543855135 510761679 688674637 835543773 339404628 299741103 71081594 89781230 768380083 321576666 920411019 823796585 757984031 576594441 47826678 384125565 313821625 347398693 964502638 367589811 945493032 49172371 367694801 397671528 733910883 147309275 662280793 49208654 193001403 629131080 817308790 151284550 555851153 544224390 837926040 139964345 696033423 663016651 980575741 212020598 205554710 854056001 939135103 516308587 459929035 705885184 211537926 464292834 550029206 570072199 73526097 335413 395078641 711232495 807407095 628792120 319387450 950573006 251609309 276948044 293613413 574585649 874089576 654279874 95776450 567508847 868945202 321064410 181009977 9895078 669402577 854748935 891539534 73840837 956750898 61767255 39687245 170646877 826740766 453150024 902308454 610107819 435548309 634212832 416419946 938680905 313648619 933129955 726315499 246955871 985751382 642962143 595575635 782173816 795575165 826211421 832820131 955218274 482673198 906302905 713297524 127073659 746475335 413992867 174430052 247027262 683779826 567657276 601595752 805063379 728278154 989484977 871399855 894161749 562317311 237823457 811302604 763077014 682650248 918018714 492258165 303001171 856181662 496570490 143239722 923666019 805138436 656615163 634869420 673481156 939516526 594260398 986083385 975010793 158578385 460424061 516015048 461461834 481747656 85290846 21867157 944436862 917524848 490361174 376984589 558677674 794269941 835634483 543310187 242518237 437129885 533057703 102957493 57679548 946115911 213689894 267146242 981603160 189346181 678828825 88808225 850507307 731533144 464608499 119875021 355941467 833852483 693860910 173857163 490254705 164290330 534626920 777708636 923143432 441150484 127006874 477937804 974102441 874288604 646003436 686397360 138229041 978280915 718566210 253402968 469651362 541802592 743925703 491712437 93415755 122157721 538834418 307125636 566100558 613816878 134013058 716364223 317595433 10405760 881033733 596562187 164405308 468253059 177348507 636979376 477718621 153617078 8635482 160292912 978924705 97659469 215140129 183851726 637388674 988182021 344630427 518739081 503735604 465783520 98073327 900388668 934584776 150713742 845320865 398849669 499374248 47971004 542895106 526429327 122119426 339071694 618563044 336455906 906376076 524308429 294547023 493609069 62478633 753446716 214436358 23282 194689256 38280467 815808726 738041140 350845407 367796989 149411421 719030639 596405780 153710306 187998377 434111944 474418962 249863044 854774457 476873635 914695348 360590054 455851712 612939115 870294122 514318733 625895048 806837994 91026045 815260035 73993522 828758692 135242203 388158441 717095130 9859517 2769758 157999429 302455343 701706906 427740551 508727676 203322903 580467063 355894612 981674884 808527946 188309023 348928557 70601571 931541098 369684652 908322398 485435567 600384935 516123868 100940300 664194611 22499298 99214074 858421179 560094091 599885589 653661512 2981544 219892523 71739767 563140186 247692524 507192083 143905376 141411689 419323237 189411616 42343529 271827242 757473245 333489880 337853493 380982596 358239921 892740232 1582986 129258420 807255877 863960901 561516862 605039199 852175214 377168543 852982623 91724964 19765619 758011224 923539527 155001615 969197141 70576388 360521952 54639768 768813023 716529195 467748555 339766746 110683924 341542358 116371821 242086131 892481590 858713019 525378788 653783496 917958284 700990149 583905264 534840149 296102875 4280578 729487519 560154119 692725803 972005398 383652897 940796796 792926337 430453478 641384227 509144817 442156241 444321139 152789492 632419387 985139940 395141613 246934386 887331297 267778182 773350013 517350288 675288387 157537601 58967924 520541125 896645056 572905137 78100816 156657638 320459948 581906196 537411261 856423247 450062891 481941111 70190141 220478631 583190740 878224753 993181317 798815966 829106621 85796309 167177630 879913559 893919060 344517743 804555698 786567340 844385743 959658605 658987016 915768382 438120605 392225721 958500621 227129080 78433183 813484526 370366786 227583435 100313896 280882467 412559511 719627715 269264407 712968723 891626184 647775891 788977945 40158598 269746874 352900643 453535201 273864961 154914003 65691366 959767522 280846496 39437922 312615762 77256073 526579490 329129541 766561090 502773109 607522810 601492215 247056853 324383473 820101281 781993885 104856835 455443191 618296438 389679194 608732503 923702807 935233200 102149582 375667493 77305218 472550989 278343591 959508429 926639013 758762112 190444595 770163226 69767161 734910661 55594016 498478526 355008200 378426797 18113269 67621572 182476898 989613089 783764221 838332809 954307944 769037803 777290322 754333575 166707234 840353243 741220934 668358650 569370005 413428009 467908763 58136874 387779738 778344641 258813900 755213534 109399405 130743387 727014892 553178797 473842960 234504841 322357509 222703764 732971997 969279384 722257832 146010956 946880383 840580757 349666604 145819271 720992635 913687845 221543225 464357244 951068332 55164494 296090416 703156024 928887343 357924660 81430841 832545943 228169579 987198605 174839629 762105920 38346978 748677434 443693498 203626482 77549213 699581774 761728890 396980182 623130160 910886234 751306948 555500019 751269780 757209540 517682611 866921848 290262247 488796026 910419054 984835696 505870707 162917836 555812299 675410138 802793907 800241907 371079562 540058009 326630183 8032407 929342190 485966743 247110467 68275607 248625602 529738538 126352008 767110062 935756472 483517653 256556766 125855353 314882013 331343996 271286231 199429039 644318497 981324405 258756684 308660176 388418868 524032146 257057636 661874554 307273480 291948637 786636043 643382674 638300743 40050816 540989735 302828313 1867051 48959865 76109789 433326222 228771527 282066775 67815193 285653054 673960010 450172491 942658509 595786087 265290626 75817901 9623493 957160931 885403490 196284191 987387060 315508440 596838447 459573193 829328066 407097011 478013923 671062421 176909843 158279355 385214703 324167682 617669813 379065959 474799103 738647350 792057703 474713294 891371461 368776918 340109311 68590458 874127978 676014156 325273041 273903888 339803503 801313883 704117333 757882520 158614084 524328214 213219690 475743086 279217646 806335633 506996959 322752931 627809061 218548357 94404662 827808219 690769233 243094447 660792269 57321880 756835561 343043425 838792928 816052176 161160952 473788980 603418223 106069670 271982180 509570963 38591515 652082781 858671131 919457240 779540180 920257693 53927761 239970336 438337694 937622019 232666597 314419187 8378070 838833241 615277704 343727363 655161577 741137204 411335045 623510922 464325590 312754401 140891878 476901793 122501681 554530044 125412672 364223107 373019402 601314792 274939774 889962459 391491327 575828688 560606976 571465756 293565368 175776120 60568882 312914457 317523306 697490735 131011004 624620740 108900209 730938046 551427092 771348260 611941707 688999322 173885864 626971047 980253481 395837777 996312695 743657932 574677780 633790855 985046187 688952267 31292434 404297382 765258117 434770992 983146062 188208461 199523864 548403180 590165385 514047402 828213742 200183967 489193902 254178606 406836046 768638531 731784778 347384896 368492683 160587050 701496684 880431390 402423576 658054206 447263973 48398383 972607559 617104303 916460638 433475539 21283186 229786147 15952967 851115918 55981787 764075699 443364679 962647634 267815613 460896716 138084134 786518273 562719036 703865254 935181071 874450331 29875169 103998537 946504968 710972378 50445128 137543621 819451247 46777736 916122717 48765523 828427089 417127324 65269541 159202725 115482554 259116969 24036527 278514680 211131100 519255043 693547697 995146838 91714631 450853044 933671337 155653950 113875363 215015045 51549792 779481986 718751738 105025789 497839622 445676020 507335649 606541180 618435654 245518976 641038700 415289019 396216113 451159872 397462259 57090907 641802363 119429893 698447778 821941701 472774288 643119478 419199576 868444897 719064328 587572161 927858366 770044539 358522184 167200646 45971545 622279031 879282654 941287584 799020799 930964112 422057209 121055846 181091909 2879709 664989870 470858228 234142650 246747668 679961755 899804469 775731185 256112626 65602521 758411209 402753768 41315153 517945556 951560360 412622586 567326428 316579626 824373500 445219849 848944640 470919018 206256659 687395048 926428717 418610802 123769952 262429025 294557118 510420316 388568830 9787481 133265225 550647051 569262395 885201511 491231665 800101153 543644040 531369265 77744832 926831598 670800031 199538156 813405459 924421994 583328679 603510102 722631193 586057099 103604400 743480072 956792889 893240431 44597790 863512316 62786018 455538292 469570082 156287518 25322727 919625463 632869693 317826753 148250929 101594783 856366564 233838693 814363423 627004434 145077031 200515045 186162873 616459132 360711463 600004098 443164029 12108585 518959637 247713319 412784515 591635540 87481433 583604159 646472464 161118894 157487781 284912699 454205093 593448652 472126716 152571621 442875320 47553937 244792704 979813925 906313409 507558718 813067980 439396134 894772955 713292673 749225369 634121432 421161821 113572226 389969109 25706318 644832027 148852165 265291874 486389716 488439729 471992986 219323603 525642073 482800753 272817772 362491943 366657434 407207738 490500304 86143036 461880828 528027195 704269688 594215812 130001998 548795980 805870380 230585960 367167910 577961005 164369401 910910080 889612568 263227833 29802239 223355387 976983355 360169131 30505859 557493817 785894355 465757015 425541759 377505788 745274512 214049725 77696653 70055576 870798369 171605536 278407331 60077419 17254020 508992766 618527180 108450102 359096017 112720071 253510394 132515433 174705077 313964629 610627071 807625423 757131104 663392795 689637946 846861672 749260839 332996325 894228130 407865351 835324624 624307431 999062813 256071056 648906607 440669061 416384459 560116384 804046558 940504027 981727065 581719895 65711324 310741975 75530810 207104021 965896088 684276258 548152171 264776474 410353877 693164479 475298546 977312337 205287199 687854710 531500886 650887299 786070076 501556378 621606703 475698912 506436152 403843644 832498193 158402069 852207507 266361508 627159011 695284704 878217454 645105226 237887371 905485253 477235699 963051200 989640398 918749273 411714724 827978462 51500576 103435054 398242396 155099030 12327198 108845215 939403338 311701922 328966112 25480818 475375153 165317339 87253928 986875991 537884254 395621851 599048644 697149509 860780082 309337838 299402367 498482330 628700036 848277316 686511815 443814500 493752722 58171660 562900121 410720328 751496443 705418638 524047032 877727171 109510227 979899194 252916781 170423720 476606715 630916164 654289375 889806254 126420947 541389605 32636660 279802152 101722185 28239222 448448929 898122721 757395878 870204490 862779167 559802877 921037836 400869927 239379461 165197694 750430932 492338262 908925134 686234190 470152474 588994180 311676073 478260214 627352938 316729330 767903645 289977811 412331474 146153015 764570672 95117946 547084514 916705312 228289640 287884130 228469055 79085997 404762188 434407626 136332267 730895644 721834790 429597392 645038608 314713686 61296846 664166821 927423413 616142692 783178826 234644217 723612973 927870685 344344833 164732692 196627786 413780813 922363371 645157418 937957687 805888878 654984135 69137740 100788143 522158055 596879800 230274135 378823322 298222879 176493733 87492497 107946176 84628566 612059883 765663845 588240140 143141157 610760310 513333800 23581758 394343449 185099068 435337301 887672322 743890226 423143912 425305049 354168111 993005454 493907937 752739830 35046565 949023661 326432373 797131076 380715405 652896049 59676183 916756778 567619190 864857443 488035201 426236413 21519843 409505968 742748342 404023072 850320193 577857806 12045947 569035771 683457738 769503902 335341744 560338598 94569112 581219918 184104055 756660623 527704397 649324776 781657500 27343717 17775991 937575283 12145422 754229287 567372528 9652669 413053174 763135655 132472849 645073963 611328911 520158434 794796778 738637208 159040597 155685356 299323982 705231900 690415789 334772793 177134215 170765312 34763920 288488293 584701703 32186665 623703670 296218356 955419967 361036785 234175523 262195710 63034191 255323768 716820472 525441975 207403438 824093963 155530218 18698301 872436140 608206895 137782572 101524611 801003220 434961301 837425050 742454576 947570808 457661267 409749230 272655365 992508112 888830218 2278053 733335030 687298261 646177253 730569434 347199085 197563675 290107199 377706117 241205444 363864431 892569110 538090520 527484909 585206579 981197034 662165166 798721146 30036007 730875666 120085521 319817139 704944572 54813539 248570603 260021815 913339871 435611584 8293903 449209806 961876446 183811962 924953294 765402190 336873840 800442596 137617364 153372128 661501782 282516275 359454946 355064389 290803747 640636095 555174888 230994309 226710113 666448574 325779018 480259630 417129231 207377983 429281234 57665447 957243612 620408529 624970318 73530302 223419761 703742008 463655428 386381647 738033083 708180637 865534352 350531293 552452136 550538211 622962933 858618058 952685515 358943200 201646850 373535780 828704761 357958301 666004179 631378359 528378208 174862401 461971952 753117131 630097812 728733075 604631958 708767000 49676909 297596022 870958135 693933023 19032424 97625233 182482743 369654238 918568575 648362772 115118499 848090321 346170386 693475426 546752847 564645427 743913547 290790214 82419338 539171346 861683356 722546866 552928425 850875744 918232 156736577 32075278 170331274 190681163 602310424 515739749 424002013 114345388 913914713 413445101 525131208 178720041 712567250 991836191 544978445 538526939 590448621 715886732 919412933 927513354 653863073 863643029 904688400 630755692 891809733 965285109 674393092 523219324 807331547 620195476 160754960 716366535 833447726 396274281 478801679 163716340 160485246 871437123 430001481 115619718 627417198 77611238 658518785 100193714 569864666 963868730 853880879 418336498 265636192 808990196 616566979 839566353 867052106 97613094 42114270 282504091 148475189 663212821 905076500 951003348 904357503 712323035 242885659 835840676 680704501 522791948 662618755 450210011 672510567 129839112 919367022 122552533 854046329 169948485 281623884 864764255 350519819 560093753 711596033 242553529 275222878 550727367 251753707 514289580 691858076 268000398 188812689 959661829 648460355 761941716 131576279 50654616 198954474 759823917 603668885 751942683 620915640 256462440 355710144 567503483 184960413 77346985 373637758 578597341 772729606 689732951 823282742 126576193 276977241 605886036 516633030 924723666 57670769 603118501 737819615 209263610 474096892 638294098 554286068 202793455 668989723 233418901 956231795 961482896 379979776 10456953 390531956 950568685 964986813 29615501 995083329 918110560 421946448 586359919 274816453 913337636 805211655 74829230 707059162 50019633 163994867 487698313 696793494 510291428 99260325 387255969 594624169 740349626 158691788 926602945 672614390 950520081 608953118 388892445 866587186 350465469 423855637 302407867 453162764 921030762 738933522 530504513 438975460 801745683 567873606 315527885 669204968 565771354 239793523 46698858 178541840 30233996 79126043 805610729 202588068 714034498 821061147 423395194 981887155 439079331 570988859 966892084 385745422 155270467 347722020 101015047 18666661 572571273 309404052 764515766 29888498 393341675 241224707 319908118 897282371 470771550 898653792 53022272 754695086 211484071 831987856 652118242 912252234 248089680 542292224 891349232 215031516 40032548 842821131 926781168 855914161 641945723 905734345 657091242 105694315 257729481 652818922 393877834 160233899 10057190 62113313 879302015 306333138 529757552 794698849 458306546 475554062 273900515 644074528 773253213 188587946 776673882 875310578 966834775 491830703 574638743 972329660 304799133 450959020 495899871 962636454 678422100 650980650 293634697 547634436 668495048 224054013 54480437 922335648 619579827 327385690 446725452 693324405 879162026 747813393 538352862 384873875 621949699 349812953 521636676 271890790 727913728 937433172 826317135 949533842 575840796 140151060 52011887 299765580 713886968 368691066 520496099 191843701 479264661 926497758 984721277 973716667 290622013 466955029 978035615 190465358 968450578 950977578 654533154 27224985 633258013 795745092 913969463 905524686 34311424 841781181 430008493 813201965 468703802 685529583 316114708 645532466 42205807 976776909 844214476 335792152 214725996 260662378 448870383 16932595 574982369 407073431 888671005 198663984 779071826 153481858 785613009 671626389 183442097 120707439 974686311 157675893 809150322 800066635 597958294 727699793 204076414 236451189 441492015 61414603 387867971 426017882 494382345 177068279 790556663 974691508 339172018 187084538 355538266 657160170 420213397 55851271 262900002 193835937 700440011 795069638 354312629 835887054 425742732 407667954 733564768 831846530 543251686 462964229 795051064 342531314 850552290 354803940 297023081 599932189 262647154 112850718 541233785 383293421 111237303 989965776 301531217 29103686 111921360 654350032 434249056 317720985 506037369 158871632 545044574 717196027 400953418 408578232 528657673 329210521 964956426 40235860 712011014 360623084 596580713 909858364 185419392 710941552 588007442 783523450 508480166 98290744 63574027 792955471 652507394 356770910 98608112 996969241 86567793 979209613 808224992 774000134 131222078 695751764 370930325 869841454 790938427 666132403 361224494 154687759 333563751 531969101 787870101 687119402 612838242 247906673 403655499 272821888 193888070 270231561 321575870 390675729 65665747 646280202 92642737 829765169 698639144 960988924 178004168 8950037 818942640 555741462 705452559 286974084 563838563 214373943 593933010 335834749 328910884 732524440 651338042 333208410 260750652 833913361 758035546 945749673 548870477 83114364 836464652 832994343 484256787 169742710 115391615 668677315 91670320 895828013 769471410 301247977 164211834 135209853 663733876 317265328 161019018 974956883 215840587 587714187 499632681 235109945 497149544 862842970 416249110 588267139 932255539 828831984 346247259 937477802 339522249 73618057 501981826 218911779 301706802 533384683 145152997 164224835 410446997 126575188 343736930 425127173 963044581 774316689 755120062 748611602 304455628 975403568 377831794 819387121 979738137 159875784 567979407 311966435 558600652 384112172 641928673 94279460 150306475 41398803 718330928 4700339 841245549 499094083 538286797 553995061 883995395 417706408 233939962 951968906 760875846 594521298 881635646 996644086 104091706 581507948 611076176 906676558 559872263 467539005 871895715 567347556 12297869 223670999 8492826 454908086 410773399 601578815 407143592 919620822 997513858 819728638 21834560 621167993 577470163 810758453 387875568 668851070 549222992 480246295 747097916 10681169 890377536 110206778 490437130 631202037 817019722 153515660 807018025 390451027 813114205 531735434 505086128 57217754 840209729 242570398 917322529 970301338 416162737 725252846 55333083 52340491 234089967 488245894 298885377 680683458 690332970 573513100 830405843 778841332 539577990 400060543 617874455 66031401 749471297 467602496 614796296 662565532 333379276 383769222 809524185 46025670 75722201 212299860 100316651 96538424 76109345 493478018 785098454 827551004 88547571 65661041 617307742 35888498 930437891 617381411 673968095 828783507 341299310 249791048 149885028 113526474 558003587 393123749 66131156 365494493 8204855 244795003 720093730 896644971 45931212 173958160 176379638 83409066 150801501 972562636 362539787 728971786 516899788 455929089 854732226 891822126 779875844 319088504 735303340 65842950 72870068 745956723 312597824 640738144 999676899 838099406 234044493 244609322 230463939 609086292 295584611 96528321 751602462 841989758 841866372 936819276 38992804 844261187 756235457 300884358 67020673 66261878 577789875 227600698 675826363 551730837 972016860 658286768 458612374 815986231 391461237 808217907 140857110 463657607 891767222 216379318 321472254 406800871 212641767 918659153 796397897 358601384 83987741 223710443 345948407 984496946 474794584 658756015 709978068 711284211 226216001 448145876 575427321 856220295 74803004 35172157 991231131 372409176 67572596 474236882 69285965 733212107 953601154 116686595 599761757 97154413 976428360 154859945 11283405 478959136 90067676 304357349 565898294 679820883 335731320 94001229 689807736 806518899 652601047 166568687 28016269 647921536 722466526 426931499 326411595 841957903 54032991 795011572 204674248 653476410 772167098 930610932 807438402 618686165 227025426 257527691 753290224 675105164 210027698 227911117 270551515 619055312 924862707 80073869 94792852 10751176 95628272 361164319 617253546 823358294 413971593 815300812 82534586 21536373 992070864 465528983 940668056 748173702 823294935 755994110 420800397 989795235 897271684 586460132 117593580 349966434 631654911 425513306 784344499 75661499 310590193 896921769 316166682 43346144 940816907 369488172 162116940 479585090 241488922 596467554 7205782 888318814 399880402 241741940 365747195 233256248 992859104 367349578 739943881 546948250 712121418 747338622 253562288 945015306 462066457 903460390 972484349 668675998 354687830 810080958 299987013 175470099 397653258 255545812 768437968 452776511 771782895 996054163 276331070 142405530 267159198 784859010 780311609 594806767 591739402 412509325 69699401 542649295 678424730 950425750 802582087 784033706 558970631 318957861 771761230 879916511 810847301 523504222 336698091 869503187 277623951 190762384 223825331 874890170 43642037 319281198 256398214 989419474 327608223 959311865 160087291 697662686 420800800 758843138 262437376 896734360 351304580 522046414 526162618 596594030 800686127 829007752 397310987 392135646 96889152 24314003 249378676 178396143 64613593 918058685 158832881 414845143 774282089 170114288 18780184 588041438 761246510 65797123 458963595 290909812 479443254 186196382 492897922 823046719 320547553 543960522 600096535 697650733 327774482 149535381 756509470 608865653 456837814 810142031 512957240 431999056 450427870 106299883 919097887 78725243 262104125 409296892 731672308 472574967 614180935 375425609 526988250 538080268 117059236 696653305 140772635 77922933 928775213 74307945 329608520 150980713 692283030 921960756 838839405 461800974 928977503 895708076 48231831 620182865 205465171 991472176 947559952 798599545 659141520 909939052 242933024 663724186 870332577 733408175 614216973 259140399 33128736 101519190 561992909 67428280 507054403 341059492 996722928 953047029 161438723 499253338 316112606 486679514 237221273 877584419 224283266 111778617 16550977 495370446 234310971 681856689 457066008 10118737 673147821 12825090 373947118 352095975 430071272 806665578 989684282 977135502 451275413 441537021 855787401 750030883 710433972 450671611 495469134 956566561 327704320 564915308 243149512 95993770 120338514 739422956 683307375 380171144 484815045 185232965 94913570 372573397 106330732 405183614 800778964 234045491 516504345 702843132 681218745 365984219 994339300 138291540 886152881 221761054 256967456 205997488 645732773 955564694 630276484 665529933 415168278 1957914 98686146 337768844 969292327 204928983 715376181 206066212 388020877 806601952 30016666 971737704 931886921 360368658 550162410 774142672 908864054 649660642 124383243 637500727 609265238 266357473 989293552 363889779 240316270 663087615 617767666 337056292 819124912 55803718 42841838 857245900 392049422 904041425 201393914 534699191 393464453 733576263 828374550 435062259 105588049 323102476 961456434 36197702 993605823 435526015 869368836 10358204 828806837 89200909 751141900 789776354 712165706 844512401 948003362 86992950 381586607 483578042 892173340 238506628 868600983 777445772 306337968 174857381 518060426 634796363 664999562 19409704 927241074 945626944 272654267 11781891 592998821 303022036 364531573 72462640 114786043 833469449 104636181 197020952 526347808 705173140 50163947 820329256 75075224 695311229 799884240 60676471 919003001 390743818 391077576 284950515 701505940 633130205 126522160 955917761 321686605 198799395 662411147 53252489 7388944 888280522 460964120 894962434 869756754 856327654 797019080 627599749 676150074 136924623 448406671 630798040 730907927 384211395 646168518 571581552 389925185 822348417 378687137 848945002 622276065 678808976 425383498 92674951 815846975 321438097 478802903 579401805 230620554 713557041 635456543 179640191 587053377 532204250 886574586 479168922 478929581 642497512 1902848 15907362 764939273 775967622 420672130 198516878 845704968 117825166 902734514 760443933 773051035 546525927 108559286 438993492 183715197 917113617 362189766 902652581 105734308 813226159 918340420 152587748 932572611 624887578 760788797 243364407 139793175 209915171 979814890 674543901 531147887 831656579 709644734 774069577 431433693 824889743 19507902 891675863 611674980 659696410 775687232 325466161 920308490 318918752 418845519 269544591 792172954 634267846 300912086 774828009 12242733 335061353 844709165 997575065 155006889 546212166 576443613 641391785 33635549 959138017 402210390 678627652 251110183 287986394 968446255 31602701 528821922 665743772 904147281 144952603 507268049 989194570 801381061 243834926 694699388 285385236 835287110 409225312 239603854 10282344 698818266 937547887 915874467 63731097 234307231 159412420 976715898 636335581 275139424 618770956 433327855 819676681 602762570 214555295 774683798 916062568 258051137 89916446 523222387 720825386 270087197 232719189 962839822 766160705 631994573 978919104 503639503 900184316 736984057 348650324 691700655 574452538 729694898 669030155 217018085 563827619 15109243 206522953 792178375 674746367 284288292 883847787 152217464 462540893 479806458 691194856 65208400 740875136 249059655 715169023 740309851 345922257 439597923 859877700 778902791 647355450 475828793 767299111 774723099 311608461 448594661 929206829 624198472 325995600 692335357 263868778 748378562 726624091 885155805 773040622 428593567 14504416 808110680 411567908 830578756 634882578 534329525 674487783 653597604 853009475 254123486 572739162 186829323 403327141 66671829 551396472 607593422 622950991 571184364 45972754 675409009 626744178 657405178 727575655 865621931 194556877 645216124 388401203 776997782 583479895 363250810 593285609 32054869 32698464 438728511 339496992 27515742 996388626 676415274 929655951 248110170 519898231 770124030 719896357 850573656 667849108 767715376 982934533 915059409 750994762 43911012 277432842 993551728 778635917 439650159 295285798 169170716 28209562 62242288 985352328 926173604 286267019 774976572 8703288 500097076 351345928 976461418 594654172 492961368 587468205 365962003 843591002 791625167 651568291 397954380 435052494 578506626 732646655 717803343 886819249 879177732 657639777 291267071 867689416 160946153 261246620 912770373 207442105 589682127 291982224 569280725 629094991 449940863 531544107 215774496 704101137 957763101 992402841 352530185 258942379 560824030 408421102 54546182 16379973 851250397 363092204 907235342 429833361 320506250 797709539 228646962 826606403 85930402 780225093 444493954 7701280 561016732 633510938 940492572 261902685 494143502 367474162 802858167 626360928 479388664 451644677 842817204 182510008 775288133 553445035 645694141 844180671 398439530 154668696 354950579 45369547 446627583 152870505 368266688 632334883 385347435 482333330 57790074 490805135 703988083 256365263 593770848 349841199 939314643 996279589 363547830 651111150 335351165 342103080 14943641 228895952 113437878 573928178 258841172 907217043 939531180 153670439 52294012 271395037 738167272 795845221 514727835 190364834 73413850 598040710 599016365 286181687 44574919 409678881 215918294 128629827 44767652 503591567 385312989 545941805 54828199 860339741 776964455 261766398 109159683 45954214 327330785 31323358 383804004 924861138 15067320 674812590 392343616 935243169 844690079 302963415 389278764 141138705 982018816 522705178 693959297 42118021 680731905 1815245 401630802 218576727 384356396 308776132 548953418 516375442 271870925 275668884 725397660 165191957 704985353 7949176 566691994 300455904 536239493 820668200 528524917 383205785 979042968 512995633 785452594 516819966 78222659 988466532 502615022 907421220 866219916 76237740 442761413 400850865 641890966 362394444 328674010 373031885 936695159 266702636 872674662 746512975 476972511 625357688 500768001 262018525 794154326 746337150 973707482 694608490 278552051 155434511 236129209 889442252 113653225 563271160 756941253 211949162 474642915 56813677 603385504 541265929 890407970 603284719 814970074 72148016 411488117 267119521 258464066 290634821 283003338 640230303 896680035 15417602 344825984 902243507 298559280 814754918 683791030 755603196 697617758 281767316 840802509 315291220 874860643 312837599 759630946 688327394 240736539 683643601 372784876 610560559 953300952 925468244 746376897 118885938 299675535 266794740 284816305 697016256 275792893 709489415 167363532 233740900 60652493 287560370 488444977 560374808 670211060 666056369 815523294 389200539 558339472 387496000 709636833 395542093 560645326 348822210 495846363 896176849 855990932 593682431 803678149 349633586 501944203 947844858 942798188 351817387 587676245 447687949 87963436 148449779 644426539 144244255 135585188 718600862 438243529 595168113 363703850 152586457 265898244 853243624 122106851 702086786 621601804 432097944 512806852 451077380 820316655 927009858 206139292 372545624 698542870 430507811 203856251 451188607 589870592 637013022 931874507 373259328 843652162 350510699 788510225 603622056 385435512 573308346 612275269 272388289 354779818 637804035 52298054 990595440 639167049 125460322 101098031 38953611 976711336 920784879 855193737 37090006 399694454 726232983 401099004 917292699 112610165 462568546 882998854 516820626 357028139 917798751 499724730 240273284 3940095 10214584 47313039 840460877 418844473 53999669 579601410 546514381 154042053 826931258 144308829 384959722 569232370 116081363 621193194 165318920 552099838 339149369 668975169 92417685 873652016 451634881 631395485 293525362 615605171 219556671 361598688 914878365 508233127 994295538 415232150 394074287 239234520 122807437 88318497 783176937 699702232 310002563 955784782 433270486 814152 159664893 613897737 406121869 803666211 39790855 664011432 632480020 217693961 743573655 302188714 352159674 928955762 939296079 149542405 134891157 136466410 976554023 719043983 750012086 253835368 858325778 278140657 781816413 535256941 406355051 179601316 236520145 358564052 215414941 154607207 582121809 884885014 546071579 522796847 631572821 154142777 182542827 691659469 244088491 566440785 690011161 453175223 425679566 299700960 473550793 213789720 730477106 513892417 68386256 686063043 440778995 977433305 396241792 603163477 786114503 881697676 221172143 870072764 116662423 638935272 937585629 443612648 641052334 385569598 132337769 802390324 331364994 351152054 245670884 749262464 595065605 900955362 827205043 265827356 207015454 217194859 185120723 71683336 485803092 561065848 255831897 312445370 592038337 167688867 836576659 591536331 336019333 182564724 731465132 518600021 727877938 402641925 8883937 563461471 211446362 435305046 614447884 400455584 429947416 689435685 736019005 817006590 879111401 839026483 437736698 370533617 963041035 544938382 899202266 276439506 10867266 983815934 608181300 309012533 811209908 360840831 984151538 883939819 409964314 194981808 133910290 125044122 481693890 259330656 506307060 204300852 273124019 517744181 169874674 224417174 442352841 604035756 818382524 907959508 845962650 299410133 364392830 288185878 888395117 453780120 277182019 148676416 625334338 853181231 867583960 361852610 37510693 654964002 370659419 842466140 685926093 75860413 624557415 118999740 449964113 353954571 333711087 266535636 275645831 645180274 744158675 480158584 72732156 527414517 539986719 538323770 168707127 249422935 724327893 225439024 371445307 765275125 996702798 234391212 692427391 209799686 991531017 877978178 933893440 63775121 232578401 468545308 506844720 625940990 929759375 780778196 297028457 602085990 72290359 771077937 709633018 898388679 573953371 202662201 786939275 251512569 772320167 508492062 204035141 207700571 563540203 499036777 453655700 504690950 147460885 309280385 452710847 844568399 105876295 8262845 395864058 660913240 84348259 699183265 525253841 28885718 294796087 24095256 76340000 410475093 883020744 190923689 264988370 505774934 331528113 762444150 720464830 710443599 200917846 587293191 60953870 473450749 638525527 988498747 735865147 524475941 593992698 388752026 992280286 950520118 163108911 867113965 285419723 850226538 240220330 31357759 875659056 786766299 345787139 578145526 427787909 655691536 532118341 346333635 112794519 898581546 888207462 306526744 295320263 461282799 821877141 780691939 137306315 52585145 767082445 346597810 211326358 98438510 532160367 931380314 819562478 97836226 167363789 104745853 344816035 57829687 483465159 817824356 490247119 705654284 908745665 643364861 821612450 700325380 661484121 231089411 597113017 588119688 757906770 739212739 114765533 422965364 841888626 906203237 580828232 663747450 61081948 610922621 515125318 932310416 187912022 6377994 104024843 928933463 501637930 601633999 465135034 939789111 515224621 254974282 317970036 635437704 192074968 570499891 948121420 888997847 400630218 589905571 686301566 150287706 880715950 647596180 718784296 236859975 142459611 74032523 10806591 884140298 589759264 575789763 819024534 263690232 527480596 986307046 636890279 106738933 43228010 509739254 403111783 192607326 439271365 595523625 188841988 274031735 542574401 156507517 43601848 371529279 167609575 368730492 261755559 17093077 936782874 81680771 414955900 740395935 718852205 441836242 307313304 244991255 245257569 230700503 474584236 579368071 770517039 296235918 138370179 402549103 728642058 234743451 150739101 238822268 406468438 938353347 481542332 544327117 437917836 448025507 776710483 542623515 853678296 278731516 31382460 484636840 163286204 691374779 741191607 69725207 835874413 20906820 507672988 874033057 833400659 297059633 48708073 667028345 201070590 989412353 537710827 265758778 67455717 944254933 548882879 712269495 780035787 454624104 760653556 237942721 927805343 431918461 605434479 115244525 505132827 268363441 916804989 718022039 521716878 891009001 352269898 438422469 432905218 633161250 433253483 658328574 790964177 205523791 805874387 375835422 63388153 90097821 341892034 202966157 290583753 944318922 791784384 942929984 123295916 88785013 828146066 914030977 649095276 435766070 511005460 290497538 667110502 942142698 277961698 336048078 956146521 176794442 674198229 750013300 56275882 752404851 800885528 954201576 590355151 449477327 21649698 781580605 786127006 510008649 721803708 190315549 353705056 535182512 361361336 642872349 708236385 804231158 99367082 458995778 332319546 182057405 625319604 523394128 543017677 469297495 457339111 45724711 91757061 498804697 311588735 357397423 68722747 880640184 220858744 5603216 700912791 503799184 506476123 711617929 928145814 809061484 522520803 215969558 738491479 701228848 700258721 854115723 572366635 464794569 127139204 544379323 996314134 915375250 907164049 423794571 683703922 365810444 413488851 514453685 286765420 692500978 157655521 856482984 533320887 34765270 114317743 298647383 20310528 59664125 268651696 134002733 256408281 449477921 873892141 919724949 107960871 239895059 223508961 232877296 104016256 116596613 712914101 856357232 608857713 123378889 190395806 631376958 980613629 302552131 957805835 111935474 225546001 557278321 947782080 785539450 534578050 272092662 621900865 53973733 144552318 133236436 508032653 526147826 363726907 775157616 380869896 571571519 12009758 702573063 338356118 137403825 465422809 646702790 668607070 295797500 727089431 732828723 969541417 32001270 308090695 741326300 48059078 410672852 122003590 26614849 667430090 420315225 71149740 499126405 988129715 372593882 1580483 716965897 847473354 700610842 449572657 719668964 57243970 786550479 587645845 568847101 513843188 344658502 370765569 583623126 731238630 930670001 705271551 260113075 581252863 166353358 904356668 806924358 931428837 919727499 503134985 257987399 497380543 580767623 604084389 381122433 145972885 983129891 973093665 333793099 444038463 673713398 710397366 896047780 743335271 291905247 726907066 251054958 67459332 284745117 823676391 927908512 954827032 562944653 889417145 907460918 331417424 755107344 848192099 507232918 943245343 748237267 971337289 485369951 108618531 244068906 614606696 592680146 647949187 93919686 520045780 824382732 114134935 320808593 617140755 290199618 600542452 877768960 252997040 673328271 756700913 768382841 246896553 122715066 732410177 626080107 471656991 177663759 429944848 778434915 606467675 857151550 234135477 290064036 681929386 848477796 909352927 916128635 217287191 224692833 573530126 719444051 251539935 772391790 274565638 318782140 90278432 784154390 735277899 716710128 766257898 832451754 808083122 561152651 596312539 516709557 137558832 488471868 475025239 196703028 509645977 966086022 400844637 815117224 344074498 993186259 499157163 493659909 159274900 893952276 512648046 244576355 276250440 203154107 456069038 347816839 488536640 33206339 13443262 676771947 701636699 349397040 417678612 547723095 589685649 172682894 711403070 156597439 807168955 562744882 442374349 826729396 57208342 543566639 388141906 866929814 560070447 778220053 695257322 673779889 225754105 856553399 836766403 826106290 997002143 299049034 520356754 870938991 409625225 178020595 77041386 55746120 988377789 269479937 88052130 806170421 61426675 984392491 41519517 268233657 334178400 119406959 969916542 380878561 543869964 967501314 754769549 529536266 982175454 440285134 788244158 81482653 589320855 800532101 971929693 331121292 243481835 765124189 147010151 201844479 376789929 369134806 240357538 4888188 95841767 834121315 590492374 964724520 30395071 675405593 761331359 163044094 49311190 122415072 316001798 589230036 993362998 853922468 278627056 784749616 777229867 10006009 647459755 476819648 391064513 81509966 962070075 960792605 442416464 150103069 917592088 876769989 34025545 7859612 166048213 313004233 712138429 951806710 726532920 422816619 643998391 418117652 675178464 348703693 966892687 875232360 197026707 570774726 644158594 922558611 269313923 287185679 799189433 618205230 216992985 926002094 551011175 614312037 941388358 838423978 206693077 162427101 913547860 399306165 116652990 479690115 178002963 211884152 272993761 298320020 187831397 525499519 866231562 228825896 761080717 322473874 131810761 670913094 547350442 298488650 547121555 751423562 163500362 577962396 198173678 7937483 998424597 144503498 506710379 422625453 965175367 511173272 954156650 793910950 303538727 425854843 465466210 457011364 47947816 559965789 676689612 443793115 278440991 430450340 12164032 834139737 660112585 862146866 690347216 687106391 295181944 139219444 613786237 963509430 515667529 971612245 918111612 561706650 679748847 775488621 743209223 394152427 360397258 152457382 358855930 89830649 114781057 289818826 687451288 89566821 898863327 573972638 24729222 997744364 115766828 611773769 225555707 923605138 470498223 116957416 127813268 423111694 804669723 253612057 221199279 737397185 265587891 364382958 254678481 158488471 5957700 138621286 980746708 85424551 996325775 518652733 597478582 692876656 836827792 574454179 386270746 217340270 667939939 718464827 340473807 653682858 717200459 175840142 329087096 822920241 860676697 211103858 714029663 546706771 314714459 318862724 469309648 779413114 775942187 863357593 828968676 416576426 882183357 301174628 187461320 433338858 767043776 678333050 939974242 478458134 995289174 719417299 6528080 666035890 727947547 787149245 102057804 971636077 86739058 123621074 631974781 347216294 250609867 743511660 396310450 778941204 880110461 217167698 496647495 850463382 893802841 551725863 720978066 801714945 544589089 261770006 756368290 880330915 29502066 734669698 774860944 839232195 73820613 479279900 707275471 882288445 932803344 874281874 306439771 722131927 114751942 683809018 544380129 644403695 132989751 2568304 618036087 362784222 151310038 977487365 420573686 582951212 261947921 543689620 404272355 791338759 461861177 541540924 650358066 48372490 764122873 549412335 85549927 17314290 644107802 836270608 52482480 503062130 8346412 101019424 92415620 680361941 34363134 624229404 406849916 904365847 594092431 845519659 363987084 680607892 644964819 766809729 540999855 929542786 500000457 912756127 65130490 358079993 613309950 953885197 28716453 503407536 824407812 875138009 786097827 827354303 491352776 331766111 580277196 109047493 365364545 432488578 809435334 43686180 426844524 727382944 54402836 158023457 191379417 798225534 508811628 83339616 232419672 103564852 439725646 915682311 781659037 503104598 492291943 579810516 875712429 245372500 447890785 162721817 533086899 744369223 325381249 789547159 216290393 97563034 789421596 602955010 644623099 634276453 12581823 67167492 716481374 154443955 495652600 790377737 287361777 127604210 141891473 480539936 956119981 380644536 552225901 717414712 550840886 179098151 402955541 785685769 514972244 599390965 44056850 78368134 250897958 434814213 325841513 555276567 386602626 73659443 907344095 488253938 290581463 826968594 902160509 367580992 823730990 548127481 340232271 272892800 595559070 722826090 616082148 547854165 448498734 595560353 506903996 642608002 329061452 888674748 17939257 971547277 384193688 736739013 898518742 516705843 717246238 543144952 644009125 879482825 106980073 635653610 649965258 474872820 900200841 921386237 501171875 537810469 847990495 505016056 183377005 383622334 9239308 952998513 167466611 426608982 526654351 967209681 764707383 163205085 738083145 776485200 552546247 930204853 166330745 857534890 994641009 589834935 294310067 179511764 608209473 327757389 633145651 626775297 184208500 457518168 29135786 894342413 90512925 834747467 249488703 994314923 682305278 742729849 487089231 844583396 856809027 886183782 823067199 498687498 132780784 780669552 555189494 370478131 938321449 154836105 764632521 884614371 267687130 180615693 442263632 904852144 12512781 651817386 687222379 401586944 722555557 994936655 347155467 739359914 178448175 212858834 638874668 617603806 84989443 481830437 974181795 803506482 403494921 971786382 263740508 569737107 481371885 194709214 177565855 621095417 943258188 190384820 418757985 800093608 441092200 812281411 148836500 397211470 864164859 437238088 861668701 774603760 741856928 786774037 934592001 518937665 265633643 992279365 851429175 352445325 838020792 400872398 389344940 816238853 407847934 833389499 612211548 8290536 595242576 7185556 580616026 894166539 309933130 67406234 877026357 346634636 328041995 240517110 968325232 143557467 219757874 275504396 190816763 427684378 843176850 642083834 590662185 828119642 770168304 978472107 732239671 530090813 642110314 501198826 930171377 145715961 207333769 337375503 440382716 450489470 211813399 548081514 646266751 909575652 883808521 99877549 88575614 352222218 29405059 939237384 506810568 976138364 425989293 376577644 516408352 533559181 579959175 643661648 191907082 813468443 456385128 684059240 19506028 487207933 347321667 187705095 300097388 50100302 462920154 104512275 927494385 590835001 196128705 495489649 848839751 543218914 886179589 319847349 931540442 459495924 89433748 92466619 952616291 300317405 115110040 875506316 439202053 535324042 643947028 300915510 410110765 274885659 981769607 656024224 292261997 623925799 590440008 862206803 549838605 474485798 821433112 251980239 726739191 588255078 781654748 782304731 742136422 727886434 494025778 966480045 448319237 354091628 931091532 924303349 186694433 79383088 498895817 277251164 996593820 253350501 36256487 497638303 893158367 603062266 701419163 729583363 221685448 593495973 843927427 697757720 72380549 726693775 628630278 831824313 288962568 992798546 878607657 257784040 167352022 801656140 424800104 353284768 876955475 925650588 772683634 327971607 288578993 654405888 144192591 725668493 235947125 339599721 64984153 453456748 709806230 521446587 333849421 153870843 393116981 538753692 986879115 439354889 620616720 431559688 782664183 252385511 291349858 182685303 712851912 791502041 906795872 136829612 255127563 227498326 890367784 118226317 397732697 951998861 108540495 234085724 977237390 64304288 459955870 403849270 763202268 692016489 565929361 668282346 599867268 717486916 454914912 536456262 935734689 462068617 997957955 558916041 38760586 144548171 810254446 564426653 144794806 380877926 398727091 768622664 865246444 417928104 683528834 244147161 167235238 649517243 517597850 643859491 461354902 285858304 31175290 797078177 984690780 538173539 507757965 511547125 165266589 569471716 764903401 486857981 42247171 361152938 675333392 550819797 439649999 154510907 380787157 622407864 807417841 900348383 218476031 660916326 109117800 407325982 832506764 527675842 433232593 901867572 764838376 604561178 272321697 841881883 858593145 871324910 466581727 473556549 855771530 791930281 982566980 192961530 180070818 684559617 853784486 249474998 230375946 262681720 671472205 228288076 135717116 797088563 740226624 961167538 534135659 313370947 455221825 932940286 687605294 849227308 564506864 884004895 397096103 595627526 915517058 75504894 600719439 234315256 957361284 656027431 905621679 664712716 600291172 478820939 961819624 609044756 271806405 667017427 460232120 899768187 267804081 52679829 312181900 628093720 331765652 619525165 190420055 452252876 973823958 429712183 704925683 721374431 836465725 226426769 550837235 354726256 143169612 788700199 496351377 379604980 827746624 348956309 407833931 251090699 377169850 797049457 259270447 722012202 745373723 192420522 328685941 710427880 381960398 717430294 243509719 959680606 292965019 907341341 21280112 461277008 343901820 766649609 813483769 555928071 173604704 629541841 445929685 398367648 857045371 946175594 931178863 399400689 572785585 125551169 270381659 563268889 32844819 824845049 225465039 224595357 997856212 832104865 565331375 350768790 596682672 28329192 765915707 153192864 387170169 185595821 293623688 679710729 693721859 207173262 229095014 345577513 404954316 344640048 140351101 626889500 387388816 196179993 567743598 775535603 485197051 288045229 480243968 700224134 244488306 846399537 627278567 39687567 951434691 472514838 908951059 62502363 182092019 611781473 242865149 650614001 568378368 52000384 155412830 96564035 807080617 244091380 465802354 66408520 135811802 270663766 350705278 297251485 33128454 347706182 652532568 609201122 797581952 538953977 145698156 887891416 953954923 176677987 584019427 271258679 332346070 267447185 496875036 503879222 1347174 283192181 817475179 678167719 498794415 262756120 873716706 752698870 45950846 573319867 692694600 3637889 143538477 289558288 342545831 205605114 162287134 543111573 376905131 838232464 592859817 783159157 8952417 621068827 362824679 885065010 398677559 108061705 499394563 271894612 214032603 879653978 979847416 112857296 929747758 445905987 919362241 356503250 611052731 52748141 237512833 925992827 221586594 692577827 453383840 807840570 608467080 595721691 222200413 631418247 970208629 821960010 258574332 993536923 656653506 513687332 394803261 909010418 199780392 331716208 407712420 614545742 263852947 852134684 543741273 749471959 609899834 387995738 484136284 216778020 394320494 142526615 621991079 30485988 551208836 416254517 649295506 201364307 625689512 400594453 426806616 222893753 245237479 541861034 722363858 769538122 713392355 835672573 744756923 986017868 403254684 660283896 615056778 942484440 196425275 541556239 902507273 82981605 346612612 403383038 602412559 582718387 122613815 808617664 189522929 25538263 266899063 429940116 174761926 175649883 162871775 435965155 883455906 543112150 422502878 183165269 412419742 855665855 634229392 468832098 787678411 841468419 971159321 264581849 626518797 555095580 372904848 242603390 3062358 155464010 955208704 751266618 89392034 688294592 359280484 486590468 881809215 347221469 993620925 491962630 211418275 946280859 39628403 42154873 104702585 207393758 303882681 812249815 562796062 653764554 232597061 926839749 539904123 724331430 341748848 531011200 192488972 833442367 202072832 591584450 195528490 689699270 397256675 814318813 307449519 830061348 241878726 915162663 280431799 970103887 123797922 506321060 440395466 616386392 964246481 460603742 832687396 325928492 773083429 433197099 958348418 690755453 300853700 492707630 247946126 848227777 986110953 814797583 709235786 483257701 216321949 915620719 342356889 802692619 970507445 248508604 145996544 571647582 237778663 750644406 218032070 492132263 927100322 229877451 934380466 120170031 790022570 840761169 339322172 507528475 875978689 2285260 206495219 154456358 616694836 601088036 496204141 370565496 643511192 146332018 220819231 670579199 431838643 656636703 520139649 556426007 540824147 801221161 970469518 351728457 271388729 699197244 156747014 386216457 13398888 965974931 847105731 64533865 974526802 400600630 815529791 908653653 28550605 565689933 208099847 363424895 532715934 649761840 166760875 332731602 972422574 531286840 110498585 19437905 547666966 21294527 988767992 875358996 143862041 248624075 366832791 759639852 300252804 604462379 982572225 470471325 463410756 152026902 260040395 193056250 624074345 764214151 528706085 95998078 976022036 232470908 302703478 782250664 296850819 312988146 652324686 901295263 981194585 571116981 66343419 817409559 552986392 482516528 773485330 678945836 147418108 601726287 538630030 960843802 242097788 110173968 326241592 757893014 49573592 825369775 82653823 742785832 953011404 413047607 588412605 373071305 741560918 864400564 453180378 247745203 910131228 114675016 676130025 994154518 632867863 631831792 645458923 961333475 175883476 600430628 734162047 293803377 646099216 295262601 672241797 472334385 564095533 955904086 761031331 302950544 956870584 531896924 63528877 619386687 781312878 239965100 64975072 301581083 627710346 295330894 104571283 941583479 913408375 369885637 338586452 149067711 780163891 496157570 273507926 180352078 760343840 646448181 23856896 107230239 609404157 772572207 912839455 805427749 796937868 272253570 233901824 118182941 203556914 176612136 678864390 545977487 996402501 51695819 983514446 331173891 69191514 158922275 40611336 243032751 815877265 55710007 436753749 422099839 747126180 774334242 101135465 119069307 470872752 290994997 350384117 428173878 529452790 153633867 525641838 366408767 652004314 117531852 324324769 108837952 304714557 254152277 498135598 855090671 407492843 864105321 382516013 826235997 88725806 435909825 759985205 402175236 782708471 547868943 200129127 695180429 568700352 537545786 643623039 764533159 704603751 882817431 95338213 834209559 336175571 91937512 287142836 854961959 182418049 359059049 107527503 400178708 714286245 874974693 507123743 159711697 323145612 498368580 159522195 912603644 47102813 696720754 330697826 119865397 682439310 970119046 284761330 170241642 776592692 30771373 168232721 283780992 304559815 892439769 228293652 854611665 52309660 26458522 173093423 839332651 89186141 805771126 631393984 255687510 742209784 63697994 814195771 872087198 18879911 299944062 932265587 628394193 32929997 768726538 798982740 780570577 45655794 245004646 486596446 804291864 958915001 822528928 200601378 4077943 910135658 689959893 914386165 883892802 4498267 729981163 387107410 119446894 720960838 166290814 942219751 670391543 748358558 869748267 639866568 70720903 177140230 873673017 146282812 484739422 363332964 920155525 92510418 439319953 744102565 321404536 547328750 698627328 621493871 386022623 855810389 481032375 677054720 142352055 666386086 275044857 12730653 731057741 365482570 157072461 115066903 349295634 240752329 150338319 123550422 479626926 997303352 707444939 370866225 820663034 912243945 433321858 456836611 881930004 381977366 359475485 705639677 785241778 745341058 121561173 587039725 348820329 990471879 618518301 40644839 637002521 213105281 980967749 317999012 872055698 169950751 199578411 3830853 999827908 751502099 214023019 800562356 608410798 219522958 893671111 6332238 898263940 51529548 348490801 81516324 758056670 526699913 500994530 719271586 772337875 401071672 249628644 30858400 819524695 841611083 378358438 719617287 781452841 502344120 9380977 86818915 285363689 915093397 111262626 876264507 190598339 354556118 292476544 279561277 398101259 458795881 544329518 294678935 115600589 51235957 615845719 182092039 771754289 300418600 471691170 649111196 428277154 273285973 477907589 748080738 451559808 652336410 15432499 605173506 649699613 343144761 823342016 22813486 957829437 187336405 479215865 27935372 463945696 792998089 424847562 349358779 537335795 92008100 871940989 691526197 6839549 928947176 492931678 547961404 839461287 536781248 450264023 885807846 619049055 97102497 828655434 194635567 798489966 237811754 342037078 928685323 73922383 685704271 767946924 742423636 246214991 423475619 472034149 289469252 271326818 730018181 664089386 869807871 755514812 438245790 368807878 219330178 388703438 49698420 755431536 392758067 208412893 587520314 691764680 34490678 452798659 190466540 897997896 611627811 369566491 585469711 187353041 222674502 693763936 917509661 903524662 719457189 527352226 227940951 900598907 754306765 411392424 729119660 448184488 402532615 863043013 140682664 564814488 800573838 55127974 534897258 493109243 426698911 283664159 867498557 84819138 730569367 529692553 115905855 142766228 709228916 800054239 163435243 782101988 241019306 727080884 695771300 421297570 607894955 369373707 282739881 760051661 809010241 356731828 842006749 245933027 301639994 570729017 332836752 791228280 246761257 887064246 137847495 565039683 924530588 531624144 708270557 434131332 788779294 436771349 553882399 760110229 269078242 987169080 740285692 818211556 399068345 922255318 36785065 874050885 658705541 433943847 627804121 791798535 8913280 977654236 436717366 549743336 851857097 224027416 842812957 8814199 790156663 871425314 461860298 396190587 403123239 361979823 156333283 893379929 193013520 786024488 733400600 67041684 736927587 267187227 264975030 2799318 135480618 756268954 645327407 796777746 830287241 992534819 298026637 266675696 614005874 909489168 2953963 290420822 589455398 60077157 432387017 121110295 579466497 863158992 303524956 43406825 125063352 743379232 931567602 885806803 283597984 75464219 490125771 565076727 654771887 345663965 699747686 498993469 393837664 180586768 429883205 50134923 415062740 483123101 999463525 502407500 936519404 486855478 401078757 996547611 759297728 917773458 947213201 506851920 16814754 47971386 818457693 631274421 843990430 669297546 112739756 729687594 804551589 151396204 91722893 20649387 955999448 695256899 444753613 802172000 458697658 692756979 210297245 194371002 564857006 213924632 578830638 940922222 612040208 18344353 985467473 70947847 832322103 299798930 903609138 501964517 646035836 554356595 752611190 592810789 869035427 77830096 745382813 140509254 630593922 322519674 951727178 251951850 398062657 262717686 588281326 59695252 999232575 507408667 548683815 616365255 961771616 806144535 413619374 953431337 653727917 729443455 719060720 461105370 366420940 412000209 299803730 344357062 472117295 333386306 716513186 106343160 837351942 344484972 36620514 920155960 662899975 793854377 918440167 186630593 300486639 659708194 798441694 416694160 71871853 547390478 29879339 487181480 390443994 588457489 898559124 427814104 125030234 438779862 746608209 629228664 487260438 442968262 391553867 372589993 738030345 444011775 298192125 850957531 599672362 701301635 874380735 413829215 88001481 51590371 73226410 788367833 15693542 31934558 540065136 140190689 614827557 419235068 981437481 454104578 299249900 742743034 137477234 422836500 182387166 978188111 800574751 172033981 625322518 625325590 575775592 927446752 954253741 567957435 796813753 68006278 174475764 398128022 731626732 761641283 833145023 441733597 139755731 220611793 295319286 791944557 452815722 834759040 746434840 394135976 55207787 686688569 999019499 921917662 413097345 527705797 159525555 452281580 552741190 845791585 471633294 981848835 210419010 324723466 301883143 896432234 89507543 519676879 356281998 503179130 143541582 117435885 855194477 540639668 481332697 665431272 401598884 875145895 918242216 22880536 983267465 432343981 684494956 939859065 19410076 862599010 782987852 314074896 299521022 351746437 389946529 827910388 655226674 218326064 63517558 459075662 395582215 610254274 835343117 423338214 373295565 653143166 49233932 552378452 130044030 429172183 3929778 581335269 944654260 982968224 839816581 163809198 843203908 810395215 173133629 67919130 107564031 980244356 816640457 300867344 375401320 208497052 417270490 620387846 716674168 726886445 477549917 224545658 154177528 480343834 662242952 31115205 294321117 884226298 515034970 330059580 400357379 379297071 512827219 771614343 290042595 127621422 480803646 575523013 240600460 53907359 710585604 789808437 943488604 394738165 86832000 347344179 944944687 244513499 92344281 256179915 581425159 193904114 533145690 836497133 186933639 787521178 708130678 478280192 335747562 63946434 259596943 8413452 369249593 361899043 506101129 135539761 794859344 21875146 171399152 297585491 23348919 939535251 58386131 632437505 350930969 167996776 698480909 88712163 360562652 409167982 658809610 319806000 890800165 117966423 608950430 689175927 866246266 48004656 179256022 57587465 794647419 198354934 408292346 557439408 718946141 574984252 838148732 702261206 426519986 557671816 175141890 446693979 501897653 441687854 134018153 891619857 243522657 374098573 726750955 686173876 250085909 211223403 584971957 434450583 774816897 137368716 640907223 407243666 720767266 222751220 30452629 156593028 462041082 871369693 172439501 799713607 725220384 97661965 256280385 574939125 699757812 504609927 178204100 845288719 75291347 302873352 706441194 978992390 398324964 486721103 332697561 7872136 120982043 302437880 989038478 796172572 62535467 594794844 951498431 7034636 63353124 585351787 552731493 657291458 175315452 345127990 1629533 713777407 121699812 221826624 811485480 509133540 12597588 643455706 513104362 467506668 228179770 175306663 492921251 551559148 284314753 103242341 514795916 23382392 949349032 272404294 782811210 757281623 254589944 642132965 311070180 254279545 842662256 390514485 976773454 64174841 146773659 261566196 159057877 812972144 314298032 278192098 487778328 392536592 992756057 372186865 933082095 76846611 921080807 802233904 981639531 227679258 291068775 340229017 794849678 189391523 21714755 623364924 534805652 672581933 480732009 908898869 616589607 879582599 156099791 540355042 658472401 114954444 664583766 822235784 624844842 593799 425771206 348212093 760689909 635097196 280588891 488226717 309705685 527978053 690506457 139561226 573655753 47893285 144104172 171450501 738384488 491780098 580466075 378893565 770639999 475266537 706962970 628384280 539014085 870753140 468597104 115355199 556663766 150504711 295866125 142619142 499381767 604037031 612571933 896153616 380188977 936754133 896948242 76080443 277267732 597745554 674506851 345295580 410874558 733557686 581351590 668551621 381959065 574579069 14280039 212584552 892322652 584900084 536344820 209603905 898326942 40609191 612896843 518432760 173436243 180725595 844047717 792024126 462399535 731742080 598392002 186054986 39548074 559769791 859557441 388400372 621551451 515856560 376500974 717628582 958312271 783430423 2230501 210456521 956919924 456976531 246661699 482250499 15232455 299173148 679523099 728153802 834567991 264664604 848069696 285418948 483410471 360215506 919557248 967356323 713543784 207677600 107729686 557274994 861600186 188549335 477312136 452797846 19247331 871206071 566947692 977609731 175933171 562000645 408163081 939145684 597188342 880867676 859228642 80101401 275128903 559927169 215506900 624000856 630423492 845824927 712416402 274616448 60126198 524901660 974502843 668968206 36172271 343844349 456106094 348189418 658029825 538366485 312760264 619634772 16031761 381369684 310668110 60871813 353824986 508202339 518658851 480356118 276730330 467396990 331104898 614996241 530634588 459493844 821227122 185474460 680961858 12819168 373345689 483900758 661086953 527049921 888917084 783707115 342334649 512484212 719144359 592945220 209224881 644423973 995482814 879552594 292474222 712679738 486095148 727525331 790111796 697193365 736905489 186612868 207539238 717883544 918773812 610854515 760468327 109939440 129354582 706695560 985970482 93922492 379837248 576400837 879479438 630851876 32516936 849457709 431358781 47696125 105404070 817833723 300267949 13179827 403479857 865647188 377531447 661788863 564361013 236010019 671761023 32645657 389631417 459639056 670474086 154769848 755732678 76186821 281214834 149883826 916212574 525824695 619910176 113814897 778639327 453114256 593873173 671954614 306795374 881193930 20197146 656444216 502625127 156795895 939894062 201964789 475719272 840372295 969213986 638472171 838683410 291461008 57309505 155537887 701664161 959352320 536530313 859430217 438391728 551932474 896360949 145811486 361461703 346271721 517354599 173179169 579176515 50592959 22432751 23733515 720486860 674066494 826905506 473598655 113356372 243385703 406863822 125441347 538924694 950444185 538152324 852092437 706552851 981536624 901981145 127026936 215206051 531057949 186580279 131776947 965568847 181041057 612282394 2610827 7474169 150380238 450652001 994677939 510767922 283886073 30595333 269506261 97518993 568048595 499167585 79964872 203255861 376148432 804755096 178534587 709285089 125981798 435030492 222501229 218262984 568509323 630922071 538311884 18497803 240108672 222742825 520359502 319564881 623350316 682515115 849259096 434713238 980098593 168391094 505893061 333186589 407410761 829343521 933328961 401225035 978473532 390102451 76509116 100655111 164250997 965023574 695761885 395304694 576939983 783966417 125022739 800240999 964752031 282422714 34139585 553683799 62491436 59549353 106027288 956809796 196005758 315240046 937298746 10980234 819055615 14524268 206618756 627353851 513826196 590193673 730729191 971514104 41737220 695409005 919478427 732182126 629649989 230580291 500736038 987863652 515447276 596038178 496649099 890847033 98208781 700686279 531485970 620259830 505306972 263652842 374648183 379295335 853897734 360416981 313665145 977666216 540069435 165688133 624453795 112715798 273562920 769896974 47910272 472361007 404033256 877022367 37115139 484041357 627404812 445897813 20518178 100467059 810899832 109750338 985705391 604814870 379694682 507330176 250536812 851011677 931220092 933310189 455954993 247670572 288358993 290864097 839892327 545549775 58873076 433447303 527878484 405313288 803312677 559304951 837046085 293274788 526264898 391050095 589445639 567406356 906798611 734607706 337890223 738044603 143392515 736088718 588069056 991112067 601333764 947453960 594853385 131228361 312251762 120738921 177213922 315372956 501755525 957701978 330081796 342245333 410739165 815925928 793036355 464394378 850077811 220990502 659432395 627890327 2207060 890125032 412441742 52000194 707268112 367981743 341884798 328169831 968459500 293009249 193171959 144854614 275561120 526471434 747885570 376157587 115830457 709414011 462950893 847767010 60466157 132679130 340877016 778580634 47012092 988870867 107330243 810152062 692707129 996458094 475165475 449964498 210868540 831205246 626682466 602071708 250068179 48164307 92581112 767786524 897415197 185301143 458701096 535314661 289448683 79917468 382763728 613226272 454530723 101808008 410916252 637726120 97881039 873875595 45884113 172478231 242657469 736443200 864622562 673306193 315388236 530949389 177555871 706181968 245637569 154545419 296211722 671667215 893644504 403411408 491672758 413201955 719004749 682262492 390923751 966549401 697030759 970639638 41728519 766034575 956659741 588589020 870408862 556076476 709213017 388670304 986825959 736583758 245230764 182077020 302810541 374512600 128570319 486445368 21819774 97326655 544496228 52830534 890289193 855869911 738100588 81398408 681748510 285551258 52612653 846633516 920456080 711692900 293224988 448882618 836118693 576289961 924110161 728643280 576326490 9793343 801077620 746890887 388990214 423487368 786265295 582346594 936873011 848766344 906969031 80211934 323680681 217700775 566363487 487640354 214876552 982098044 835598 34033231 85364363 134407310 147962062 908428149 778730123 636418120 409735596 864036842 710860011 889994191 156076668 237744873 979405436 331236202 551440201 684279339 900082448 836875269 137991831 909892551 507035626 345630504 89171372 756464230 846353688 298606592 84480536 466473710 988334775 486210607 416200720 372501216 478404781 817252680 917815244 339415985 494104171 138838098 648636631 405645888 412210106 965303138 579885504 591249101 127432522 308101918 356842543 892325765 826869 312938196 535616028 281684246 343352381 442136394 119578050 199286992 634904213 855126073 769002093 713140574 747188191 388055433 664239068 915540222 288298683 327943551 145936295 745172369 241824648 273812175 92840739 208146294 794431001 105328980 132141899 673123471 424047435 44859602 696948018 370126269 68334791 246152494 380331645 39754608 681522194 621042616 338461395 580753433 691201490 444153252 41247317 290861442 338693637 181612705 786937961 182703166 602245972 776408448 49893592 575211453 541980348 461427115 727763007 775248560 278526502 665772951 23913918 52641447 371352417 141418222 21157702 568938440 560660566 662270591 230107553 42509886 468187916 447838872 916125994 295986843 384802649 520703167 341190398 824305082 695294200 390624892 850494681 800524050 678825107 117015002 774609712 145288620 865115814 123436598 367408549 799311794 230517884 977744677 931248081 702632354 240892938 309870906 40741702 931011601 856015199 878005371 574230501 192018701 987016071 729767422 485469400 37080334 74088642 125607796 571599203 460448076 710427344 719043644 758124624 599310724 426059980 474346060 423588666 89404407 2994111 538820299 310450392 419118144 324734120 90491895 221971213 547871013 4193300 69729834 448520635 197298608 663587684 918584041 398522410 538109548 841964393 740376576 297794522 898567629 461461863 523673999 727421643 778315960 634397672 464894691 603617754 712459335 466853139 204150891 507121230 117813094 960959819 344133992 751320456 957025344 56672512 611749495 376676427 286191863 743259105 763568414 890879625 306563247 927651969 525754288 762272042 492677368 303221421 777550951 900625623 69478318 456915689 953501542 57040624 929689753 731988052 120611654 885960339 778531565 136148466 12142808 128576462 916164518 905992661 765759635 492558619 370022394 494363688 434975404 879567370 567900511 873571929 778609364 125706370 206465088 415360375 509450229 826582355 400389307 82462786 486126023 4317422 917943196 350029311 272563071 953874969 644341309 102102085 772651350 339311578 45020707 753573061 205717808 304433808 52328713 914343157 709342320 582463635 249846981 282003293 125528554 567156761 168525194 881758573 715663509 600860125 942150919 250685308 496827487 753743105 251646166 92591549 649980918 788476128 97282456 425748146 786914184 415290739 933155936 420105411 866017667 84013035 945640043 721697908 707989605 467662375 168117784 728663807 291448812 813499971 400210807 828559792 953049572 973356877 912263967 146715126 573930675 707554201 962069293 107213638 7155588 253071419 235732840 531360345 654970306 471574744 396427133 974041231 385891107 77296696 257936862 838123290 573096833 130859527 989990159 76893897 537205942 788160262 325846764 533331458 930222490 650263433 459270649 4354240 305644888 873309495 132401945 361532444 560950816 379270665 535610134 349812063 535492311 500320812 410289042 903002958 151493992 828175561 87666933 722902564 482424513 398774932 622103111 656414511 619218735 486938035 938733965 857593701 199074605 784652166 726359030 60700602 645185842 896225874 216882513 405917678 564819340 202954437 581989676 678151088 404154068 838055691 928219071 880535861 552895607 356400055 548508404 389439930 305117343 402931602 470238753 767227734 713293003 264936873 861346239 643809314 469999757 241601642 301363749 981856855 509235684 185010332 999528122 167918526 206745080 63449973 133963891 791888449 120412845 678625326 563637674 262099323 763384372 534245168 931706939 234375595 292817067 689566046 590778587 898891256 535448160 344194723 808325450 735429745 475766400 390872200 694617150 370189034 378876812 973979221 712967731 423990296 74043974 984135061 381653406 280243605 901621426 117397338 978416471 470953321 93889277 993737371 858952951 112117968 713891869 811377258 238770845 144769680 570107350 55990386 404539532 220715543 552839782 703338919 616767233 294364139 666644272 863518451 891327460 71578634 284154037 920020399 536287521 899470742 465525598 713696413 185923251 136018495 472302290 531568338 232421473 934078190 829050228 198525369 68653823 845736644 972154077 481693996 439402439 38690888 446136055 644864620 104355771 99425062 992008417 544401439 191389724 256221239 728943220 656759573 150218378 257425956 709219379 297582681 836628658 282323181 915701214 255597065 536734427 303188947 9961736 638355673 169700237 621583051 845340047 78838194 755904715 404092352 962816975 86822177 38925556 550318973 115339897 341710252 652069202 52223627 547373850 696290351 512888297 863600503 43854346 734487700 638117857 862739399 334187410 213039684 643022944 450268586 968305547 942255216 874202376 67837090 548156925 729803632 560962980 30389183 20829146 926016797 322777005 738329898 397393661 761571479 609428565 110414233 928260112 234008251 879303934 16825513 423714 828375895 700526617 394310335 791027677 507260640 69539169 467579394 988785471 927378936 170761300 315493674 429675521 220501599 247643421 209231967 270937130 522491569 632431188 764012813 396597534 369234733 647819800 607697771 465905795 237269211 498420759 537586551 346612145 694581461 441454753 753061356 684381398 922486427 295771610 233624437 705625557 641366435 727651802 191745756 847033963 619917633 301508815 106394407 473661200 293547977 119572110 75734796 745547934 692200760 363457393 725065666 831556211 595559287 87538215 396385239 778313955 255510109 17892315 197352920 647650894 507602755 758206002 784634213 71566411 239624132 136007814 386237768 192348325 257370150 405275150 870561305 13429902 974832247 385533391 579638271 164495576 263817591 187793996 60482419 167096924 736114691 348220937 729102489 812138635 760549164 145034748 739836363 395451549 944096733 723666045 754314639 930878551 307216898 713815502 649493130 71015265 715714847 380535869 379946487 130703677 52831379 834805183 458138433 458483965 24992100 201822241 442161953 76921633 227969781 501368998 223889470 253176246 567032645 791663248 815925629 88652346 591088253 95913233 63892422 249192991 307651541 935204595 122478507 491967765 50673281 468151599 198932703 575737750 57950383 30561009 237812066 555325791 791760796 751776937 279439291 892546234 419396676 226939327 723718656 519653516 77997608 6693224 911921324 628074332 917060028 630837004 534316559 777114033 619991205 43448837 956575720 678861042 624741631 485431411 142199180 81846084 715520432 25063611 59278245 458729278 590107798 351917963 952643542 30764764 555693050 616569865 544852041 72097755 839098623 188192228 112888715 333658818 916454964 311843743 99501422 310681177 113612626 896831167 586606212 529247716 402746759 305207931 898887562 329962513 158269800 206386740 410225361 660666728 179655386 201622451 272801817 584769738 262256618 52530031 881781674 242280598 569115027 291787404 915068105 70732798 90416200 403597036 616631772 890040797 34567331 441886345 571261560 17741513 574032073 825404951 323937167 616329091 772136855 642308130 934057667 696324519 55729227 434826098 84065515 136286237 980506077 140761100 19199873 90416302 53183514 63696344 671041079 30640956 972262211 117307615 392915761 287780147 420148586 308675505 815375289 869928599 393202147 315461359 730294211 408997902 36164859 990530656 502092718 945837386 694980491 768596265 220259860 47352967 184033179 83491241 681378460 691358331 423046654 33282747 917607759 843843064 149905613 416323790 173011864 497466016 497964598 126147837 451217163 505394096 346096566 513888692 398778607 321487372 262948390 336416171 549075232 793018839 90438114 390583705 561316496 600327331 233649848 227437222 912530671 509797359 108682745 642311927 862677986 530826370 569507660 91622976 948918945 58520954 286483773 68414113 89268656 735266393 291523243 673378809 641115738 987891635 166888331 282779591 448983473 557508828 611977706 877934837 453067769 717531905 330681267 357393891 820289092 655982516 428869250 567958320 718008940 13434878 401459112 657969543 63279926 538676214 476774528 641594866 548255616 990102438 163913445 179088809 931365910 370902503 605928469 52202110 800253013 885940920 668324870 835967769 101673907 89096456 249006021 335506662 182291333 478607364 296112352 237721539 38647498 350316963 638097209 194891085 612903428 115915963 579222203 91840252 62845180 559718554 41560788 579428742 768855688 619161542 528807211 721133207 347391191 508587545 222395916 730211895 632492780 683753696 234778281 169161862 181577749 620671749 546843456 182327794 97144531 837280207 345819696 89169147 74178257 71883936 218735936 190978726 445786410 158944390 863406986 952792607 860189310 631579615 769415921 219953191 841751094 688211999 400217356 44608957 903647916 686110829 766303100 611861161 527925690 809665942 548245149 982318203 242234186 702678315 750358809 362612688 427860671 893297266 8259031 339122421 334546697 189011143 307319956 975574763 268712925 538079701 715453226 40819500 529996375 827966191 461178710 533656440 173935175 190954734 145105609 640311857 164415150 886564736 952818254 403496278 451892639 239511263 924506146 508778949 118408411 357850718 754267610 865891626 432169776 777269043 403621100 194804195 6040703 767433341 927887735 827314872 138725344 292039956 380650680 754724807 455066687 196134422 350649473 967930695 233976083 976600342 131083411 541098418 73203198 693765894 999459895 605266177 437796566 405221179 141487181 409071420 108332810 339005425 161209000 105213208 226611974 769434510 878672680 546394080 723146037 216186525 626515414 145068455 983585137 579792418 692972454 610428770 525015651 776447958 250304376 520700004 829818975 678829307 783445678 216812198 626076669 591492100 924790796 848862558 603657317 956254436 532440147 67806958 600183930 901729435 145497653 662830461 319116200 259192559 312074462 638850993 647626006 608646 742110013 953581668 789128319 142525456 341988315 615737761 898894096 845857224 814519389 50281853 588175562 778953265 446283899 831377220 573591669 850798193 521946568 436896208 807589897 827058679 850761051 111016378 277514145 332779559 727177732 251450144 452164990 684152328 463154460 642310858 366387507 141989986 433818535 382548008 893831175 680195473 84832435 449314386 2625347 872595523 656796607 75532841 3680638 412941657 231647484 429712981 334376413 173122676 140089877 634672802 972162985 787643307 943294858 165714522 619047693 398663053 365624827 428098881 569683487 405484251 653216278 172223738 494434977 341937327 727414658 780526211 580960725 474073316 374201915 10953298 660339667 417878041 283366896 839622876 252664642 746438974 582417825 306891658 628351072 150753649 699161485 487927968 281133354 308891274 276193690 943027444 302482234 46125674 842417195 172493400 618311139 746214818 972735458 169468431 792581443 146506635 262221071 18111150 133199429 519446137 764051917 439957386 990576510 982653353 174549805 210352793 184061795 295859693 809218913 591638497 370096532 263783731 133549197 137907426 922309843 380477281 764951546 424203665 469408593 650517637 485787013 917703127 675401941 946192260 927557655 619217683 29964040 497169840 562285892 511388837 784706914 61062448 79074536 539857860 697453574 460981345 828378199 348936485 239230549 463551235 519012317 382153386 242544331 799316033 247004076 751358806 443080834 561014996 415903408 356982108 537027505 483796458 299074398 604663401 588016738 458883676 865413350 462585081 372032507 230825910 610834337 760833244 628211059 602632273 919598830 804250807 431717155 936696112 849599803 51071044 468273334 651197445 999015855 751894776 611002141 486930334 16976456 263364529 651550225 751516202 201255440 162343411 836094459 724409734 871117707 234903076 681441746 739441822 178370754 703816668 579087886 364821055 456487396 718157295 90006549 175810148 199647393 699998479 459613130 948477689 149720880 947658970 119738215 156383856 282686163 253582521 144661658 685602406 311169346 747143359 81345386 454595970 616396300 305328862 681107653 781784127 668607368 618996463 481879313 208179445 432428770 710920220 839411152 965796288 905790224 700189725 637563925 19449430 227144228 21132326 425534262 617391770 707367851 696876692 857242906 123747572 851965584 315826721 287118531 607971691 577840914 13047050 16193645 265900867 569085878 132091308 749011086 332926031 257376247 240263113 602666759 683819537 947425646 407373913 146722110 21219735 912537600 878316874 509493138 665972549 60015642 57770107 399080925 584987851 446210767 87625003 408283359 710550677 483748574 17826932 81925081 972614741 271256628 62619650 871375404 648294246 274297557 921377779 293322788 893397154 904041884 667983909 130520148 138387979 370962289 950711668 820844121 813978002 801749548 109540910 725748691 491601310 957224445 459493876 739844526 594426687 373998955 520631089 48070625 133432079 555082094 860774116 556072703 497026752 419884964 531573944 134987243 817786376 851889153 89426811 796053277 128780755 405214265 322044344 184589768 256321610 218833616 606232827 536092183 231377515 870852190 754879888 29713153 892997877 266036100 875350248 906774520 606712931 369698506 261773457 703613997 636730847 566942968 264875572 488937966 938499241 419943301 398367351 681565728 762590941 325974447 674277197 748528070 456106023 16160178 330378639 688556496 689319492 672972163 424769620 669135254 764446047 762470072 276897034 604832458 915620059 47396342 540793954 108224666 372751761 22321863 486865015 515176215 660286047 223540281 914705258 822331044 69509932 679556486 263225291 121384767 287651644 941915736 724908489 341347338 874493658 200150464 910505311 220137142 328127914 297092888 484499376 606533580 480388039 118918336 160366497 602691930 49994798 620419399 745877120 946781631 627865121 217310307 407337639 26748171 261008754 915792453 704324293 105904698 337322903 272722310 272451471 638071436 772894573 241982759 383587840 24488881 129680473 245766 910218293 10070873 277378086 396803134 942822678 197960689 946165034 814361717 960992825 485258900 446518675 34319512 920136733 795369489 297758323 925379308 69194585 783241265 952515851 891599230 756093644 613400052 855603305 17121 307884395 994549911 253306964 916930817 630915066 530818466 500235880 597265484 308693115 129939150 437980196 7364067 472921662 315592179 488705127 747242478 170666667 989885316 413520585 681223207 399398645 961499366 700779479 58189754 993232831 92327804 590930917 88289321 970376243 317490616 5430519 597894334 100791593 590499300 618569116 729053822 240927750 571979063 446756713 519629232 457126566 626640405 824904389 603644014 741727778 684890695 446918225 237609041 348711151 42859448 624300283 36169834 334129512 512711349 213245883 934844562 598761804 546204998 118781494 177441872 111553900 797787514 690129028 486530997 754468909 692570975 480848885 900712392 551598969 260752962 32607952 999385316 660841159 276352720 439593108 997124062 555000075 288060544 839731836 751891397 158684015 870461840 976363924 941190415 948756767 957520102 626537614 90625191 387559820 691851511 530375332 224363442 807927079 742296610 498041602 540939933 372408247 938791782 203908086 946143262 734941847 24954266 8561340 888475017 858064663 265476533 834423055 641296300 709331717 621917923 751937924 805954449 355016256 466118501 247794375 771945151 438031565 364496249 84807446 310390460 815282844 714576998 955116423 723773810 72526443 722392726 546635989 331838573 274605083 260115667 857562025 806403854 349487948 722430675 350952644 971900748 33630203 660002496 223098212 704109835 594327624 870312724 310786023 537160883 566581828 996286351 682465800 780056037 335006342 350271952 860116498 791062358 498597208 295706697 697447726 126206507 401853567 782144655 82538017 162876084 723842411 304018911 598896129 655725885 185642527 20707678 642242533 628103099 632691849 979169224 87041630 12160923 562190257 174684047 329303248 417073667 46881867 88835214 662247063 74392673 718017629 106291816 235587058 195052574 698920622 942227313 953282469 114047258 203549402 918359564 665121850 642388743 868868756 965269616 268052376 50799133 527779831 798177359 482088439 434389964 898847061 296158818 278442841 997038415 183684650 561868500 77390138 963360940 592538172 766279606 69605382 107241709 432827138 410230300 82932261 408079421 603804245 841618565 754319081 442168811 151567003 343436972 458772644 774173820 487562444 974633326 509026494 331025080 67091332 849120727 298775135 753122855 981883185 883290697 919918528 256406810 699906997 58405851 277501722 974084168 128065727 933158979 910053874 994668746 972427985 146529700 473999440 802120989 386546417 887038327 224419932 582369146 357185944 421759029 126312269 699975633 166957881 425884724 958199980 375920079 938283910 50013032 614520811 15965231 289815140 280007692 267191898 268541907 616511802 577682050 667036057 167834486 184197026 421634330 858760147 42804467 858608096 114588670 911055233 623285950 456991814 547760436 936556110 516392910 655153259 111181524 98802349 526605764 878324172 962454877 198593693 203803567 749443748 821928630 228740126 898979187 816933092 397468 764724646 458274852 793291369 674038371 94159749 511910571 197380589 939350926 51214731 215298285 51954184 475439916 257070437 253340779 974473649 824182258 869890057 8779596 75971601 567041300 464212209 86296967 836391177 349686676 405821394 322771220 465213929 524616913 968595888 825526870 813375184 882009752 592423908 13972939 662478231 480109719 112093060 552683948 776338243 395088947 192862746 745245564 126067185 347844462 4779054 433070377 394317434 741081927 414298993 87627295 228260667 927679841 379487067 581706483 207517422 168944272 742806178 524492933 127138714 380299360 301940138 507318606 856315548 750940747 195541285 653771586 841500461 605153933 694996148 307513610 723610557 708158394 114503152 174829433 177999762 561541945 193906569 105547641 346583668 891728742 585372811 454983755 650737121 270876709 824993187 438677657 625656741 898734911 856923449 661188673 634992099 898867757 894854430 453810338 567973630 738265148 195535367 18369326 695986269 771837878 484053206 880352125 267487263 901382818 303781874 583720181 304836487 436820870 741787352 726037028 817122725 125972408 720293489 161143177 873181721 836114871 187537522 993839828 676161599 124041680 807989130 304954058 609248718 403770186 399143254 189159577 677477703 330175734 30449641 368436264 44696019 172453640 322560376 824508408 829999737 55869958 979304244 273751909 364705083 161976638 411843810 403577604 508985625 639065993 590358973 690701858 925338237 852502365 217580943 708966380 636733703 467528503 215736242 213577837 444297464 487341805 544429744 106147632 310614187 511999378 656436264 278812257 6821492 6534271 372695884 365391392 23049578 344239933 123079504 120490365 241804454 55359041 821057477 12597888 594676266 245477289 718058344 29719485 380561180 900435294 321059144 51164012 931918125 394553059 556049950 98702930 187662290 874903700 889747726 154820594 230013482 658672494 44152844 72821853 476103941 462809590 146000404 985785174 685531511 246448291 73617099 684108022 955309913 269863148 928945154 600900142 738242637 340721203 101373755 432423027 580845609 689860963 176226421 108759698 704917964 129524365 511793161 37077270 311367238 947646742 389139851 739907172 394113852 846621057 138576873 729677691 800338992 513738214 55865065 268345885 168791563 757600809 596554624 183698228 58380101 641824129 110350251 831321850 838116225 240318741 25173007 412982465 971705364 34346981 674544446 279306339 365734759 352543390 769870245 339658353 39541125 63104380 87674179 12386194 12976249 733193536 217597203 554267491 470153247 452581053 273587251 379843541 749686747 481803022 377520208 441790534 450166091 548549260 309471352 834537989 46076997 215105481 825820816 82059805 694155047 723968226 268134873 586311129 856459072 496473049 794976304 829606458 224582394 617083802 180556192 679050687 241047532 639816407 724467903 97365578 720864573 16041256 31549477 534490018 627031853 479336407 605395844 270144197 546708727 105251597 391103234 525211110 288980150 833702518 961855144 562412710 139761687 999357098 671649620 364263703 258592218 605884590 770742463 117800423 810362150 685719848 578314279 215320581 922344293 448703682 838469774 787190550 31627118 440398363 943970069 127068183 33426532 630252240 67021921 355583622 615782515 689694535 389049165 522387292 279326857 209485193 556524548 133724995 808172192 545960613 912567726 118723809 319824927 916509739 135168710 334070913 960456583 151061038 171294066 591121135 201311147 450869761 823138525 190022021 432942400 23473503 335537619 159750469 710031012 556143771 473858722 191837798 401089876 476046839 613431494 179222059 337310023 358946407 29424244 638227580 453471717 609856036 988274496 458864089 260990341 426995975 129595219 394887157 273200965 148889957 338470054 899206722 98638586 235891716 381979913 905217917 309200223 522189390 985976466 196068099 835028931 468547557 630717796 822043419 816178122 244143181 631752389 86795071 114489373 602025254 289273037 500241402 882817718 135116975 174038603 384680840 369328336 949538702 332399239 43189338 365140522 490596979 731137251 604978042 496151374 118775161 578541663 228097292 465891979 486409863 126943769 217609691 742787628 707939215 174936083 247261874 523411949 441572496 938677010 432360076 372967151 138108400 192897406 586974039 162172315 351863040 850030656 534785593 121697789 748020400 933204472 784741185 437410489 178131105 602847257 66274333 692229937 878070523 369822444 957159886 645868548 954523549 969784924 974277484 413726358 545956956 269951785 425381866 848672865 525627627 30617438 158951966 79132587 609875797 621392230 239797418 484430997 520465712 707914932 751180543 576556532 658189687 929676228 589252455 926139315 157873508 513862425 80207304 863490934 987284600 656573489 679837999 252543550 554234477 618114495 984668569 727162419 400017448 782369496 102953067 821150723 786613111 685883284 186111678 535564937 954972837 828790244 221551408 227830982 561627157 829972218 74793593 453389386 679993949 621972882 88563212 199713536 339130871 35977929 818277093 15976632 89755466 235892581 816651443 460280807 395721148 497356830 428703284 939499726 893275260 108409381 558294489 388056073 209744084 262332003 689699008 379317190 331423402 516986380 220370947 174374786 353687230 589235829 55365984 302006147 285374196 234872789 196214062 788659068 122331745 581989090 550042547 238512278 514248639 238248004 976691434 865770936 762652365 390447409 4230592 340428396 73948455 172249521 705531667 543673627 320684666 6966900 793154862 354325535 697535966 422485421 306204911 893050824 909974971 137646148 627060113 884783001 458207871 527809252 660727772 815672781 737404406 184130695 11098971 625271226 955960009 638637008 886021173 751536914 342940420 899167661 291610078 150871414 284960632 243120213 572309992 214533519 678899673 838990533 480238221 25776948 807409365 381421628 548550230 763625864 180024188 368650682 591147673 515540893 292020978 851009368 647023484 151808069 341084292 921043880 206773249 83321909 959831991 744123122 748722519 60601709 314411586 17709024 730903186 596233052 527950589 195630384 638905905 115020725 425718270 332040645 3044213 140222892 804649123 661467571 364574264 809134882 381574587 846368633 125505003 925412753 208725429 173579698 551967506 177840686 957032518 559054630 823475621 643318143 433672451 53069449 927759196 287896657 592098037 201367549 245126068 623874691 637423540 623425558 29906450 319837270 584197168 432112364 952780500 858609371 272059050 351850005 472312492 88047018 829483777 587447793 662520286 847678287 358858894 703801536 129536965 430854149 789866152 716120900 622554238 152456236 441233794 818383255 531808201 618650976 188777719 638691189 918609117 757907643 527626389 419330326 977795954 131729247 778744826 965800229 464287326 327252037 372244141 416325975 554584780 122759823 174623840 722983030 760222556 556757531 632134434 812218077 285425766 304469645 473990304 496691967 851076270 838711729 347885164 435797272 47600800 274417885 984049244 609652243 665838981 430950132 470166018 1412090 973803123 557010917 579391611 560840958 154002916 667088502 478706305 750644252 384618960 230314256 248817339 125472726 490890332 369587117 847885844 85122411 497033129 541851366 339841436 623304045 159106827 600457668 243102536 272093418 929760209 700296571 326048970 176654174 642980778 855000288 688254920 530297474 932799855 884456874 478068201 909019406 574053576 16728365 592792523 301622536 776366266 73215658 121952099 913831806 4437160 283910472 284677574 966575650 866819144 69704319 645416936 250432536 971520579 553379789 726124179 300305677 107441685 402674931 806745480 50959686 133053762 242826683 227437294 697380799 923524795 454872324 377781574 449884512 280695197 568204165 165567945 515469628 839431972 979394065 669404100 815579945 389245976 127907483 500745571 166051622 909884430 619780276 763582269 463801240 971997582 617916469 170074417 421014058 419850464 575442102 528831845 546860626 216952514 922221344 219773389 391281033 692409602 257989333 272944935 532462762 784878392 420424769 246128605 884833144 726665469 338976202 14729016 188574682 118088934 700374714 76206281 346374472 500655513 14591235 944819281 514044583 983121013 498882120 682306330 429304248 843204493 705597896 152672664 361206472 218406282 732952798 924961501 51158977 388408892 541730943 923909535 167594182 593170932 896674421 207660511 177622240 227076198 719221659 499017938 335982159 585922797 851496851 608177539 613529224 841288228 539596753 625736551 279505852 793638223 574720010 491537527 705246565 294253308 10021690 558486072 139354016 209083593 276359165 815889732 405898984 130723020 893930924 680431633 419797 611484551 548896242 193760713 434789505 695885932 197794927 654061084 50963306 795765092 60807523 403721014 599758853 719791425 285833502 455375995 58318096 436445950 553491030 406181822 217110048 805350563 370149409 553961701 575281947 443464111 438934337 981050958 389403765 871733300 371517482 393394529 130780621 568218590 860953008 2088055 995905846 471105867 187269205 854523741 16283116 119423362 174023445 85959438 863338738 878656626 500689948 688156771 797691762 209926757 976617095 125683436 610727436 458750152 932763616 270984396 232219437 478716620 465990952 45197734 596626905 419015144 145753244 613830998 431412619 240533668 184401414 913460940 450289937 351605125 828726644 667334167 785286318 124456251 596903591 790948350 672505890 252715190 794122644 391350848 933040598 632320712 37010336 611847798 729685550 819291056 659708419 137068918 885657584 876826832 688203942 852222971 707580541 842285708 427732219 377624155 459350940 609233436 155608912 17691640 281910067 239067014 787646423 471765425 939184881 119975219 511473488 47244080 192386360 438841223 833023425 975627890 20587499 42532672 364693969 441247606 528145538 27952147 35768788 82306977 455517412 612901678 466831453 686737194 631260443 991883870 390511667 882387831 723016460 912960275 513872133 397115969 438367013 991235728 841538270 124339087 814099218 964904781 768642693 120668326 579321369 558717938 110207958 840328537 668418944 981151702 157332903 929964913 789434267 237840613 542408458 832830578 78293491 77162263 502331630 750672745 775669434 139648965 864794707 279628327 238239645 176935817 634367333 798777103 746790489 689550652 762794736 688885014 40570940 818385697 35498188 848475218 173699342 49016840 274818812 421032566 288906947 848482793 86062215 329746102 671476938 47229309 510447762 395992552 270667138 460382811 923659451 328340233 286165390 77859202 784946340 360940313 485037435 520673734 293219422 852902381 160338073 743191966 401135991 37817627 403008896 880925702 434287258 679895156 740890493 801617999 986403672 659011390 892378023 878310606 270727074 780680251 504222440 722892086 354115101 362674923 359948132 991128436 397786092 628060404 611501072 510311619 100025016 724753539 417258317 400135694 560618339 559100010 771218811 674401026 916554927 592722649 15091361 419381401 608814608 387423778 641687558 174845656 207607472 884679009 996053256 931543564 264241930 47671087 221967731 464913133 314428423 694221742 952878622 6351078 52287907 349775253 973489691 860196403 664050613 868546071 110282574 629313453 992362780 423436648 360454292 879458793 407339468 575171827 643180274 101721447 959893424 976296281 288347507 878062656 625304930 141539414 378472627 339882878 323490730 236254413 214891907 535536738 352428689 248820852 564341259 832165040 624039401 168246715 799008453 208177958 89668399 124003634 484535376 721006272 453380448 921553916 617925195 432141247 714333689 914408926 763527277 842852126 654566172 282887335 861069523 221801139 584775057 866953154 336349961 624120746 948540791 339358631 442015960 404747659 398582167 991237257 616668969 74988451 402576753 105208768 338940440 249179318 794738350 389511195 988519240 552754374 93246681 177162500 810106404 36512110 419426251 159712548 333820757 184814924 83834477 615340190 562310020 726045691 545977501 819971025 137345332 94925919 488294059 613504171 280652926 352903328 335247934 755763799 996019495 732599840 692770948 871036256 782334206 785380721 288058529 794767330 476851645 995884313 894640711 917142405 495782132 4679288 508978083 678450880 811485834 126749480 576547656 912846544 672604845 188439093 871888132 715657785 213337677 879777109 979240902 522594235 386812287 993436998 268856131 742482479 99175920 335581083 863918446 517141535 674515116 133890607 903623898 508087012 376780259 395395295 258126270 275676086 650334017 359199425 676114334 874134326 474624230 392072455 889839360 574212948 290723367 885178682 649862452 43899592 147016320 700529730 968231242 954095586 322583213 955037819 197640053 245248204 248285743 615644226 249495548 450267630 52121481 804785303 599753835 358061401 841199884 695281424 173529388 860380670 266637939 270628809 776648691 247288595 913063056 289027690 332664153 603375168 407675324 228092744 953753513 751193757 748892219 427526099 148081747 929833631 122709954 627577585 815280586 969956259 491377943 615839971 884767954 158424501 33359807 356704382 137580474 893350113 892064023 315180017 453860185 508260243 733371522 744343086 181200518 669614686 759909805 490193648 891830196 81452428 794091789 978284861 195214154 542771519 895016767 705098288 730915616 169419401 184343487 432994681 932671366 461149356 365737277 840696229 624803909 297098661 572475275 851657350 501684939 62311108 109281413 244466230 878033334 204668002 776180662 861739291 139740712 267776139 215512189 117938960 506131587 654227391 215417789 491640897 760704450 771623459 585713905 595506635 147821121 32430045 483943234 133409168 529617084 951069394 330917575 575638439 492155393 869089688 402732324 902606569 99960280 612236055 369844782 12069762 640714523 48068900 384151063 832811705 432387804 12455378 621667071 615718148 460524038 122934300 853694231 804001220 201969451 764678072 864204859 708412458 839383721 51326493 482545199 406677188 127417022 276370951 193222141 458434502 82317297 826570978 403279081 390647995 418809871 314981543 489458029 481730170 1294714 337637732 661249836 309480603 115545287 66215824 648294165 775527015 89659325 474003610 346851179 254226539 392339867 263209518 918154786 843675511 517321755 873408407 817540764 903071314 920857693 558402830 619744490 141642905 640451497 303638563 330959460 202318612 794189189 243935914 464604047 192454088 442975382 614211185 707333608 930867909 887251235 430122791 880357674 575468351 359283697 841849004 670979621 561652891 703886451 635816945 911488530 796871101 467221730 867058129 366447032 607015146 670497138 235852947 315929772 166782797 619915410 300631823 503578889 589749067 362278802 514312102 878081612 346346992 722505681 274671704 659504995 9237022 115004331 681511467 436126395 452761050 382184360 172888396 288906581 88563501 253679050 823542637 262147133 597916349 419114231 258275746 256850660 899584557 272907949 897104338 750486104 748979954 974260794 916203876 648122136 680251426 505586939 734618382 326322764 821163018 136344124 315414605 323394058 502290796 544973305 435781935 623088270 595499137 493157437 896422124 155284165 275919384 166435121 920738789 370303235 805339344 298629202 780075755 323588608 286285965 200324297 665173016 547932553 393321075 206830428 336341929 192679635 706048491 449135914 230973125 203406566 342613062 310298274 991830345 819703667 674707113 962325493 728384858 145331030 965568305 314675641 622302268 958189857 453593608 882077705 376249752 216191086 108959630 692551128 95887618 717663988 6276509 114992609 640374994 392210724 917963571 19252782 769006792 144946882 759671665 441862363 391020307 802553260 121854250 360082375 240177384 970436426 695871327 419264065 68730996 490350459 133181272 318573520 481832178 744832590 840620927 854869495 549740110 824018873 780595385 45093758 377102147 811896238 81732140 574128056 857825602 903983548 531586287 462118225 329339668 684086677 538929479 427608074 766368051 389781511 86534448 448570129 249220499 987056188 947499269 485869258 952363663 579232807 495220993 851527947 286133796 719434163 966038007 99724840 911994959 842281843 869757559 76574488 15802871 683056884 523680234 842939026 279488667 305339706 621626858 7830222 203118412 464325341 832019077 784179920 445979487 282313475 488959117 853993965 876152800 304394039 266935095 468452390 30963103 607009837 306730173 784318483 960893390 988856001 788697222 328528963 113313721 133877255 789862712 864284592 77486547 547549247 418576634 261106046 491027553 639582013 904179789 173920056 302005621 445181612 327810567 573401726 365344392 454705233 158135065 801107911 786743130 864536866 6479692 362602541 45739808 875454386 900134717 563414457 329580094 949196089 880094020 582580953 897789242 150793850 422835704 738301471 195116406 788060196 503799621 750098903 383700279 471606242 772547682 600531746 492704293 477354969 495106048 822442439 788911672 381511100 510225513 347758451 39250359 458485421 273574946 267659448 452967411 854620038 67982187 444031107 329602903 15649000 852721270 751811231 537849517 909417169 233166478 514739467 159612533 286384495 911144258 857050070 303415855 484417061 280069268 666352053 384947441 817547371 990302824 780679984 709393322 40289137 783112395 263192990 530409286 431134862 87029963 369618065 217314880 172853181 382978516 697657142 556941003 699908521 812053485 55869636 671279446 766869770 348925604 303938869 654794402 541931314 841809833 769062437 420937489 839440982 781525638 780592763 51590984 96559149 898555898 765535193 380783456 867143235 277544153 390837557 775040194 75074741 572162569 835313638 572669324 857650414 241057617 265196199 884351177 686969839 380351804 90149385 905152959 503812187 396472966 535540639 498226153 339418115 118115802 466038860 28609725 207048102 340386686 566124585 247842198 361146047 96418480 519146257 78709463 619567297 24788634 559076526 6167865 11393019 197696631 947655692 988929763 139163916 643517210 17653489 164018619 816241698 650178064 680604841 374168572 14445486 863266374 629306712 61651927 49671859 816869427 528241223 326090202 191914762 739675559 220197598 326926989 848470882 723669616 775105259 788015611 860971071 869775824 416113311 207101608 683583778 271045110 13382485 662410279 684605411 79215860 253974167 908611939 341242006 43664233 279521691 121254520 27681376 753741490 700788135 574173089 794901815 902521887 74284867 226551032 324242558 734471016 246687819 313893115 408409844 530137050 244641897 137037581 817752491 632943904 316715792 536989427 450152637 359991135 952438869 967162841 532090263 365256890 48786780 560509786 437088922 788501649 999104977 343745056 573755529 578374977 505149841 612156010 234172666 360679944 4486840 616353386 483248788 722575814 714462546 260870365 775580720 957583273 762679246 774041039 454734870 949738929 304330748 972445253 435950029 156186296 192974220 282660915 177069312 465538333 109960753 527668178 543899891 544692229 722929771 153175268 781023660 669921250 181713297 162774168 982329954 563447568 448297129 401052490 174250231 454645942 799679418 371201382 589683140 976803917 460979880 476427330 308985932 262194020 13489709 291103178 438115385 669643887 329009944 952208002 146102278 250284154 76749576 485278977 674635534 167255875 48717376 934215350 828906120 232779899 104627350 417174117 43800548 969534574 802637852 67457067 7721137 186093323 671402544 244137061 646316442 732923420 494933858 658954362 614895779 138773656 394466612 523974964 724890978 652313365 363511669 950656730 690541216 989489782 678821403 583363933 301203086 933057182 592860031 428362345 293342645 133081027 336118080 216996641 704337724 265310269 751716431 109243449 33455571 356368778 699162193 18596839 778853569 439420175 740178931 592297794 110223937 986772432 190885378 388174584 991399097 283398629 111985522 261763152 793110742 80533557 550255038 4238081 495094717 597412526 51821933 430118023 768342204 348821461 777338759 777615067 107940405 501129831 1151063 465572862 723376420 139644274 960324119 428760028 679397150 322205397 427627984 789710773 595813152 119659077 619225935 920871948 41365082 371574448 376309569 619562864 223940015 803042310 383301380 723327733 253925780 61243254 307251820 844555617 568988336 309872774 962650792 663975372 145452491 555562663 149118240 85078041 370345244 395246467 242626141 592102947 542145258 8886924 356999679 389032340 524169615 581177548 653315283 857869601 763847843 139303901 176151591 90503252 597814353 448062631 95342156 808157095 196540992 97359592 756478139 392007239 815411698 163870468 284088397 330966494 670223738 219923515 857451214 630434502 322292208 962883943 389553854 660959081 897358921 804258327 442694925 75400213 480676226 171547606 252287064 268276372 672178817 56128014 634899731 859463297 830256968 713449796 521773054 800543914 654187631 121664005 973456115 186029876 254797490 385239149 221168243 421656301 271750816 278020761 280405729 556607196 335897077 512364819 769105284 179154185 544654807 486508299 29205848 232924238 860784773 523423754 612184749 69771250 405842784 259836320 115549969 785383687 36695637 464955075 352796019 532138938 681054699 14432434 529386678 687057658 936341379 28061678 891425013 183701964 147206066 960230918 365709173 399890300 732557902 377355447