10000 100 88761474 359738617 956342320 538982628 1026937266 786338729 978572952 490367112 379887166 613604553 1038158938 809477878 644213201 474981959 369350607 820645470 141687062 206764852 962676118 227180884 875281470 831688263 724100883 894283087 949970303 771818584 190116075 712580395 549654416 248041189 250145161 1017994151 1069085741 982423184 540108701 723756520 621392537 129119646 654762136 787557877 954934807 982270586 956991281 759426361 8080496 732932656 837302755 295864068 167984240 371841779 865436012 271596298 20229225 230784664 244424527 266954722 728533167 490194200 304491603 1021517192 200383002 210255634 78071555 42844124 808762503 254232647 61985324 770980129 605005143 440664604 208487265 939080830 235387374 587750939 734757242 932944000 864745013 81148018 382259985 1010014615 624026393 260768370 715775236 263388309 318709002 1035926801 356397302 551907634 144697981 318833513 622816206 363965578 296346218 572417335 32597046 89590684 98443982 995774814 211937565 447792589 1030166315 45404257 665292853 510766948 756666115 774295276 658805878 694717452 716432481 736311371 700761241 1052602709 421425744 815243505 398262686 238139699 1017879393 766148851 206458183 509740158 928555049 796753546 627075227 520408432 755729857 598395029 1004995172 589892137 265636932 122126613 69301680 58351406 338703701 1025783727 366286932 679141862 222370455 201880621 479533412 1019898652 823546930 83316989 805105596 123730304 82325333 292464049 334551163 768451622 827978926 698696061 551675267 511679750 1052212980 852211132 336075770 586990458 959930718 88977515 128492235 438585027 1027218985 454059692 324010278 443570307 730557717 632393541 337046780 1010102084 94245352 214723871 484256132 199235824 835863274 338815431 244315577 607837528 665821032 707805168 409176794 816165038 69809714 500053487 538487528 392033802 98245661 1024256062 305676075 196678120 827069057 455582713 441812654 140971176 489471419 1054003556 55530686 833799437 647490476 947809891 1066131311 532624063 223439416 546478337 423435799 281753801 940076489 1035119082 178173905 57542683 546637770 318529264 1043759611 953848329 674901292 373659018 924028600 521964234 333761764 241210704 554683247 593132539 812316266 425192064 151957322 739469082 516722748 447762556 1027471800 996276235 141925977 296299594 357859564 960120725 997824711 393975571 584355932 631909862 785895949 94042276 155834178 857351435 783805881 66269680 1049159454 143407993 816670428 1059870604 854737458 735843975 267626121 115833906 565148165 335512818 833792602 335481663 150167009 591896919 289028843 919122740 171686229 161318076 876950108 760438841 848339635 247826696 121098963 564643477 717478291 77470599 559983864 269057335 263173454 559882087 825759351 355772465 846898052 31088701 279031938 614544183 13907606 331093120 19463757 650124324 355845165 667578381 272927632 1060949366 790827954 740607650 597009160 993724621 325688531 243678819 757470454 664494448 341890564 109187671 128650654 255182536 36311804 130508012 985889737 555589346 49410868 475832943 657852228 1054929137 321675371 652571541 456628063 851779530 769269029 215793654 245590382 235680871 482632487 148455564 121648972 791722085 817795581 617259576 620686803 807968902 568782196 473643069 372863845 1017268015 400845856 646921923 871693927 273086186 438834647 692333909 102759360 486114534 674165300 305305956 802293086 420969330 968689429 432842946 59730097 901207174 656631582 761107495 1065598255 1021985850 964317236 21805488 834996942 402363212 585521666 190398299 76873869 1034979743 517190775 618481036 849197803 143124663 976975430 353151371 590584430 888862269 64912229 53893123 781527582 129734273 612914063 285290372 170628615 469300979 525222082 481358595 482914747 429410473 969950657 727698517 988352205 326830813 209208467 994369207 183771991 230516076 985181442 1039165769 293142645 737350488 324025117 982219151 628332743 124542278 411452854 404401647 210245363 762356737 812358885 264013877 1061504033 92601077 1025308803 115920913 358809214 530895541 486471344 296813976 436453306 713536373 318843470 486695871 133477258 299796369 383596932 14807780 770465318 76936708 223808572 984591173 986403531 588303601 679250596 258353030 836500026 359595038 803531697 366602031 118679863 164208500 821072791 687317291 592332555 443816321 386728530 34121291 278348803 473644534 737071649 988730305 241180655 346393641 1070941702 946148773 231063716 406157716 969566279 1011054964 365844603 279202900 266451184 532140172 262839503 724043179 662236238 898491057 989138051 783309951 494319989 342438027 166872697 975521752 915257532 151504422 634449948 715790694 930697788 813768048 451488727 702294008 624835668 981995710 754851739 605194758 762120744 329866568 326896477 647913512 912181789 931739048 498724758 638168989 393688158 724100192 1060619202 744148165 962881883 522354257 65027298 793793959 509362244 971580740 742892537 245578860 308422034 168548964 837631122 977756642 58755455 544399554 863583033 11026426 34463370 312422352 150883325 82682955 686335988 619541991 3713269 490338956 767236165 483633857 13582520 417703710 423149511 992096767 412249315 784888192 660556553 507710885 800897175 326074072 263573854 209297561 624080632 929324145 898511707 639926567 314796463 761928247 4426077 1073503104 963032937 952038717 461152769 626156598 360706646 56070712 526880938 38951618 454749866 1009240065 553569279 910367742 439232800 492370455 709221482 230999212 182123890 445612826 445225626 621831149 28011746 925642577 782433793 842743242 198440117 76007205 825359191 930258351 863204530 137636260 316863253 490649834 735159719 171964159 715862011 885104945 631414756 191941389 504001931 569919257 188903870 596117446 826941067 771165344 620152334 125939656 1069435783 19883940 623942319 936530133 470032717 95065193 483034884 380141138 407050095 827152407 390697584 640539594 913102532 940888890 521935579 784643945 8202215 643425345 702204724 223032450 146370999 588126719 747053545 693601802 300992470 436090413 399443824 326875419 532482346 235913189 1011414210 193040241 784502366 327329321 380905947 783247856 351168610 842101338 71070780 235062044 163000039 802130625 515212649 745945503 375381732 36406538 14637419 624700103 775112980 695044291 849423694 973200645 784765045 844579298 1028490660 153991792 138066123 545612605 669140225 740399936 225985819 11319567 457462397 1031282771 745727536 585026425 780488757 122068395 241678617 1019515135 455074250 425465070 538908073 870494471 423068384 125943780 36334838 265770590 601615777 263858941 556054491 345608626 625283383 679665609 905213302 79514649 185964629 923934590 772290986 195873161 43679663 765078901 999967646 267303773 487177342 293939629 233722940 761488087 465859325 700021575 831560883 394576792 613694702 349457160 412802294 598140457 502169622 124718554 183245370 993471094 858903741 845061963 1047663996 905882190 15137839 284060684 392251897 475999204 687826749 522529908 276429748 294954065 253250748 939863803 189027827 636832272 1018744837 466170559 139794882 288405376 764458868 505795074 126475375 345054565 62567145 1015708842 273274380 87754088 603697738 476054208 566640625 1047274642 973196287 826912497 188433207 1002225109 614839156 191131920 741242686 459150468 170540955 226957458 481194023 140340950 343671143 193142545 1033231707 216016998 359754322 274957002 818427906 208065718 319455960 212676894 963772813 638218663 1001566458 748650773 72094253 1052781058 41815740 376651222 400029529 865413107 594235559 278610224 748675661 871561097 262323272 268770837 762979973 64616760 28782255 777509657 533121094 640083030 971322097 137608439 867113749 785373601 575908006 57975052 1013346365 1025836471 458390123 1030744027 275404110 504386461 798778465 557019015 297984664 374714169 815155885 633904732 507550132 349394904 982392822 880016711 666883068 214024873 553475050 921756249 879116559 938577216 46498233 230075208 115569998 17858579 108279448 775325678 783255649 367272192 1048537152 689722567 5260210 562845126 898073452 411829623 898785520 784504455 580368991 912629570 902584462 840708173 90430299 444679059 102842434 1011226497 713733931 552782454 565950854 340314741 399841178 944172318 974254106 969327580 544589306 398721119 522365056 255556941 558408094 497860404 263741055 742195652 622118496 360359227 832992161 398168096 818594588 639883572 839478709 708955558 935616562 676767622 227165518 405997692 940013064 616303802 10044481 604834351 1048662918 976769021 531854379 950630958 323695769 740765090 396139752 729305164 233294001 413143455 363221789 650565442 293783874 380953099 401086128 1006288683 825466950 1018157478 629604683 500449287 1010507450 240513617 787481820 44944440 843236124 321281937 370883096 783995656 530583540 345643281 516505331 642323233 563180104 73725213 113648937 134348051 310261798 179491624 103280825 254158289 507156254 1013667398 931997284 1037224244 1044562629 963620786 677407283 792517751 503092019 853244234 286535150 301281465 653867909 423763982 895938470 170239359 892538973 854875813 748685356 1003678512 860806749 440027096 298879383 1025103255 517656752 597123349 471150018 812858980 881813377 738774253 517100747 116455338 76545665 256148886 838308758 712986210 782787429 100476778 37704264 270769383 110066790 740117350 158137036 843017593 539328192 789148076 781006673 852143290 62174515 601979905 238567626 630975540 171103877 96286800 718257517 43955409 561900542 468777765 79638325 1927521 949897194 139020851 448557664 351811863 335940635 1028462286 302402545 585900557 164839524 477988978 111544367 147784635 638286111 1016485690 61909284 483475844 920554920 399193706 595797279 247264554 15228640 571264742 402928947 842314068 460107179 121817528 451326902 821613583 882540914 294709901 98896578 622848330 1036656290 932461113 319140535 459021657 1069452586 312721711 81248439 1027194739 384020225 1024479754 917800233 593450036 395372190 409330695 352369207 265041948 440782207 1000865160 1030275664 270193165 804092579 160870034 119830182 129979857 1042045199 787127120 859112880 575084178 55643724 144152206 78045610 765127008 53768423 839535679 13582096 473733039 450367217 996768759 395125543 797467094 1023034493 131449714 864748149 166957457 373285412 330037515 847015747 693083264 427451268 582915654 90036258 151377573 870561212 379531847 951539299 744076522 694226418 752192600 618335389 279584665 415322061 623191655 103028012 128898274 670794747 264957829 1027080364 968481625 410246829 62750312 927360130 267846773 53859862 1022254058 1044969811 112033554 1027131632 579362184 826493322 662436336 597472503 892375012 612528087 731731505 267156843 625389892 702440875 103082463 878461330 287521809 16310717 373412452 537576244 727253336 796706440 24860432 725671198 150328140 23109834 905173911 196118943 398442434 824391174 346481296 280459534 1014553267 940450563 61546487 127612994 421238974 108366411 678468524 130836248 991771043 603378350 167863282 656834289 833405641 934868412 457232369 371992881 200477113 950918734 757977652 609101249 1062456993 97605374 153115435 740540814 900425427 644384938 856279978 665836808 59864899 843286773 330790760 748585636 110509836 570128582 185448321 277286234 730165739 120828615 709758197 891969320 480518850 752519655 374461223 1018275725 401686039 526850008 298648158 636631567 761631890 488283026 797868615 279639221 624227715 776038350 750619762 700692109 235657562 628121996 857513680 1066395175 860920877 130518670 55049788 1040910360 996558901 489698267 116705519 320660857 770043985 681411644 187963658 987054694 568695425 139353794 581908239 867083391 338967149 1040751934 803921000 449685866 630930396 526349000 394528223 809594191 18652477 770529849 443831845 54624602 708221473 395809969 407668811 108130877 857695679 516896785 964260428 203284139 453571951 718032258 25204609 712777182 341662511 1070825452 155372331 133068306 855748641 527522432 557409005 255681288 43388683 280893231 465074510 199191684 78814933 278625584 1059995708 774999247 388705551 703876990 543384452 935175989 38557801 905890648 616102747 259329672 790416185 75118271 745246424 1039506332 94209528 737181435 617686647 298144713 856340933 32827159 43642520 731127660 404271841 996427360 605022718 847089766 523686705 883381994 458667089 809875612 986520767 569316363 548230300 362483829 192957497 662120669 749379535 643231071 778830705 432402113 981576510 230328394 862454747 636058583 842944289 447943723 994441490 565952903 990263570 605545594 1041191764 69286651 895061650 350790581 961163777 88517538 491986820 546281947 104193567 652504495 350595247 522322674 403363033 612028567 371238465 295630210 574382588 194381719 225130055 237885719 649546361 1007396908 466029366 341929154 740460262 272349337 17952357 158784920 471862780 760172133 775934609 479489330 160050970 997833946 1067611736 319432748 515275969 104387462 522360510 1016278183 867387158 76819646 243642794 261357766 210380388 157125654 430495850 761002292 1065227671 460344555 818123307 241315741 55352513 905044186 715771522 378112304 627805081 814865989 788916198 291491108 676152311 264871637 144586292 375016240 161223769 1025371634 529772842 353997329 813507170 660260685 463413996 162051592 63956309 181937495 777382530 414984025 678211742 565731272 90525271 334665933 661081674 1009130009 617963195 638875185 1011657098 9912841 692611170 659811029 191039796 336305692 842692324 428767246 1072486978 709651479 876701499 210312116 308546129 1043140486 860686920 708183717 918483490 835440694 619206478 720364352 850055197 382707899 980856437 834251754 466735817 514467051 326511432 276992397 1041675093 853004385 398395192 878998036 701980691 891041019 969116695 970972912 707376887 667478365 550475421 690107286 589254685 1039544172 994617575 440581119 402872384 331915987 955223283 25226022 429587267 246216577 756942629 596124046 476339884 630900777 419961029 833389497 920202276 290747585 503075454 237822130 128789497 614764804 396506849 946940036 67956636 211903216 507227360 558691009 769559587 954855752 820314707 658248956 839148744 736633363 131432055 983910735 781747560 856647963 245007466 706307286 556862725 119375471 107005360 378674738 1025255492 341431521 271221937 263545863 698588143 718645385 521594680 403719038 675962741 380452160 312301814 291266243 588007269 541439270 953187837 280753032 581058551 881764125 949728581 452686209 750491523 893467980 604351275 147955942 172284168 824304541 846101485 320788724 899823270 71140926 584017455 120473196 821232676 539779108 100470137 586367507 72401259 1011800451 820366518 424490800 604878089 772929111 382802103 1044683281 1056380591 690607327 195162798 457993862 882133427 668384285 772991668 729865828 862332815 992098903 972763715 1072160771 1059576416 52450201 42647228 196242625 521029480 254656560 344685538 410732413 872974732 640826160 10522205 579293981 922778583 920641776 227124793 486832392 521655285 804363657 308142436 508239788 804015289 7154522 953138740 874426618 802480280 1071817095 661298654 535507173 102929451 1051366005 332748544 990340071 23154864 1042922063 1024448536 49481083 93638282 286080388 229857802 228200100 578588605 596375367 640983710 630230117 299002483 732452878 253908736 240420423 495461242 23942164 325279294 814707926 772544707 523297239 41571277 777177124 8682468 164759707 448989701 526089796 85073047 553352933 464788640 894454224 621888313 392124672 1905472 134367332 827693900 318523259 543691750 162220321 946843126 895051177 1020896635 590324523 82275455 197662751 802095691 945724459 58706647 665090874 134314628 338747086 292973069 513008023 180446907 1023902020 851595993 851796633 507259496 821107650 810827796 590543079 464995942 165900032 509081914 601895147 164854644 167647931 175226095 1041950548 1053424822 265118773 302037879 414848916 716091956 847514800 543072572 677362275 162564954 105002998 354267468 129446970 1045913974 139453140 306966488 934695897 331704894 861890971 850353334 131850434 670415431 1003265694 671694304 645020091 1040144271 870314166 22378995 416056144 944888820 403186113 419955377 461989455 989308858 52497694 726716288 718200394 903128074 179240499 341370857 848205848 384210285 52401896 914521625 650502228 612826709 739001897 145430883 62398941 1067815316 74960487 208294076 909538388 235910371 118381592 743478589 735656610 212570973 241544243 36244645 189092207 163135489 557826741 87653333 342314412 118646835 650555678 545210706 683068170 74126907 47115508 821387206 997575296 831620037 437696063 734894207 703570121 145652832 1049005580 750097902 1002075363 277008383 57818347 739517993 183783058 111859067 970254704 491423082 344470747 836599054 345358005 888387727 812211337 472478426 885334742 388298648 836036267 892981600 501087604 766289963 798142228 479355913 302255668 643065875 875834074 332495265 373773117 421472189 374691544 418301655 517930941 378164410 953890348 679237822 594379364 499946559 859168953 669390671 457251815 991366568 564011430 934467556 562988414 232047857 492348893 767721407 28813159 921339195 485603981 932034177 730259297 788028237 1015159720 610937011 258955057 76947473 770331238 398809665 584149793 43488019 286696385 593987834 204742780 1045038341 876351223 162701073 931900435 229872190 1008425994 669136287 309528764 634809654 876362307 139274015 812752333 552384779 120843947 480457200 389576101 749466623 517902993 539896535 853574692 545452536 749036039 571654010 842038573 1004201727 431495781 932071654 181746475 207028673 525592772 372846089 631747978 1007949329 117270660 373642809 854230841 132765540 314847686 482290604 646612271 497558356 226621427 768355837 475981027 576412701 52082739 653071534 610693842 545739555 549156855 557547936 923588861 510378858 1025217392 1001112477 291960168 474111005 146643989 223062222 963788956 981261064 640436001 1065574725 710460453 134821661 708668435 274002293 682336533 948820723 72356652 1016870069 1051207296 44887874 244257781 307261376 544536574 641742184 103596982 717222712 945964077 446525927 732378111 215305758 455772972 617866981 184942883 928321628 607319328 367779499 739946680 320707899 969521331 824788519 717234201 224792045 963056015 977819498 924648164 436282373 200165096 734057514 1038152061 496651258 569065968 352571456 948144009 1073229735 399815776 549162027 629838451 641390798 38489846 51273612 683888618 354149264 576292849 265925544 327433313 992985335 28635543 955780586 351236494 589564269 922362032 880552542 305140971 235003713 301146888 183674422 649909816 896131369 802293232 228768329 211058167 903425211 930344126 885851535 746589167 551907571 1033779016 636381094 374662570 931041456 289552493 570026833 556668151 204428599 800783501 463388915 867538536 224047278 554409996 898058520 878393301 931106978 1009006035 680898285 563840728 796246146 320650702 304550595 305909582 78601250 125283183 710067344 495692252 460870200 107084842 573148782 732174952 1060566754 754015735 704024346 766099100 480945695 342287827 528458870 1040780390 607057489 107828799 608331271 683319418 334920386 425260479 465088375 461315279 709826076 879261020 295025429 1042454302 1071799535 1006921507 134663248 851089255 166791214 637486244 770828864 1038526059 77100978 903153012 1027123741 386952243 84755638 552453547 16157126 548068999 870343770 450460775 62937659 141852536 792418848 160514631 635746851 263433175 354581106 565913585 464330823 997915067 900971802 719690892 329053717 753247999 761765832 734618694 78660126 559486913 659560591 1049108175 614425240 449144037 123246696 216980957 102389725 803437200 1015520686 884231078 520920810 74925741 993908385 330883433 920329184 697202539 527717347 1011297765 1017484423 633326013 922700542 290696160 92551878 627959769 869099740 180168866 852117293 319018938 103134285 562805367 4498283 389511582 518717573 607307569 981148888 21468808 433713051 852335267 485414636 389971647 264701195 593759527 408507846 237975629 283363380 237386265 15808678 712523137 117044955 28231258 614763635 134204270 1068287910 524400334 157146678 175685738 515554466 521000670 322852253 899517071 943457726 1013722871 316956537 762619453 316896078 169773833 1000761408 512568470 305920137 781357321 30746252 239137281 149634571 136177519 553448858 317928616 854770772 960588728 169983948 877779705 401315399 484964581 973306152 865321513 357206955 581221882 928623062 1002118316 278731693 318252161 957941926 970154175 298565468 998885125 883795335 489834206 89646124 57472919 339715089 1068947534 647884404 660395596 351176188 906694037 303320048 503412668 219579815 132316412 1066014272 606739333 445415571 272275732 610977126 823292614 954200549 94043950 1039757900 312374949 1066990823 710235617 60041532 832327370 142215047 616872840 15944806 1040533473 1036149974 1066353858 409503326 54286875 275222410 300124912 757124251 609009582 375059581 264030907 895578617 2988880 281529644 35492491 885672248 1040199360 441616953 659751185 513169275 21897534 1029393898 993366974 534288073 105698830 842659495 661030217 297781391 639226617 92420480 462502956 332650524 50247371 641813668 229361960 238472484 481116118 473833963 573896125 467979838 209871469 641315150 1014391475 485700455 700739434 3068777 918828692 819144828 367282858 294824960 45866032 411983811 817639819 60105847 830755095 17355875 886116725 1063155288 604996642 893394151 999386702 340870609 593085419 948751807 697653508 105598003 547863888 148990911 48231943 65213045 499714548 151580318 656217036 78298031 1029131966 317313912 904188235 258793375 989227608 834977613 452318337 678294823 194229169 74658176 41652463 665701580 631687291 128534104 894115354 925145913 829483950 137660803 488775177 956699579 557708291 1027528846 820622282 369038018 832817786 176706926 150211054 863459430 297892053 716040442 457074952 298767072 864045083 23418222 531521073 312572172 64253717 364828906 475328903 654554350 184242388 878993393 430763178 633658922 884755241 970606570 1054519613 162382986 11081004 79573410 367828843 398609020 442346934 269018057 941329503 763236242 431938023 894156145 571099339 924429056 725398432 385038482 805615458 231077409 537937930 847576200 37876574 1038935794 645776909 450953363 153192187 896793238 705838298 444743254 963621370 435859408 468052578 1035760729 681558047 119116172 584653276 83687559 286322611 883216727 869864003 1057725104 1045129219 82309601 303666389 189536008 557957087 988479874 928770966 66656422 210801691 414114995 606603211 275336198 415149586 627978385 403910783 525107592 813447710 467572061 838418690 149741551 82054689 7297279 943912805 426682083 700121087 529031550 153178879 51315055 430885921 869126025 852460266 946301059 580422644 878455025 869590151 782800243 968539240 185242413 591303158 132088951 939676786 850042325 15171743 624035625 1044736907 1028037927 766750636 555771658 25456686 40113285 198174348 834934781 1059745374 893530357 116622194 856816330 424371741 588895136 77650387 420917148 451293686 425536596 1013096684 171702403 606305652 872080386 940503610 562211827 1050004393 328816447 1006983168 415708996 427396520 1004101831 393178053 452997424 771049739 429241334 478151890 1048411224 190434925 824461134 11925176 656964031 190971889 882102004 622321609 281365325 779167674 32327474 108496794 20096589 534208113 158568182 363908488 581481967 571179458 467931730 937994031 100175303 586300127 548799738 785329908 214903885 940971259 878324938 685621885 1005718875 49226704 779828285 966275379 897731762 1025325595 272579830 969669319 456677493 749383706 444860987 265264554 413774764 5028373 203676533 533099924 360925378 329371346 137420466 601532926 265145351 460463646 607675171 746728615 506146352 972035915 511808414 146622483 437755602 989396909 1011728668 374619655 841555690 944937245 269991228 974910991 609198936 636377206 668222655 3193848 538298207 103132186 590576138 607850070 282988327 100553326 836562856 28081407 271104572 23478361 968114885 738203534 1070343692 796235721 622282163 788229089 205176940 917483054 421280361 921572508 381749780 692134653 332668159 552753060 130328862 692028975 847969844 858477732 151391115 887918272 537161192 1023787915 668932542 452092208 717288866 528106252 528775423 379938309 54010635 1028273949 188898809 340013126 572433009 323041145 12775229 490173442 379611461 947129886 306624445 743509191 1017442461 109266383 954935633 705598508 453869490 702040211 652554038 282495048 703858275 434474548 29708426 960004664 15665073 963304129 79028945 238091420 759993410 514657548 179981427 694266394 810996958 62913837 15783739 391896026 630138100 515762941 13767386 64387081 284441878 571276444 309315426 234094679 356281721 614223084 381024203 75638904 303622262 841288212 430568562 171375782 712252683 57451518 212663701 569546782 850665819 511609560 683210200 587230111 116895018 519306647 950052035 357831662 156738658 640477295 190056769 902611028 136753552 865489756 236600355 577939742 204664936 618979485 248832667 783848988 251832381 509106996 641773762 532378915 420910730 452613479 171146258 276856972 137054572 618583874 131948012 1044018610 1031014949 895655186 638084627 1015143287 870406042 1030612459 794320175 295426240 1046180054 363975204 613128012 985078517 772108165 384455126 381343321 405589122 545026682 438051680 697744553 29268824 907499561 551051750 1034702708 47828844 807897390 628532173 44108119 1054142775 926470852 324806976 829848784 1026490421 156160335 657857198 784598723 500480358 271149779 926635850 352325880 895053264 528570746 594432906 649618587 289138939 457819665 769230761 684952762 606398323 99611276 986967589 617957579 438738250 916124798 960205378 320376611 352210068 929791906 851127941 756293504 273804265 196919381 67492665 664249728 770825446 509855257 1025068269 353200935 706294444 401604115 696034035 800660317 934021215 485113230 8537571 200873070 75098024 873815158 1032115735 847628936 628768564 346972126 539666989 581974593 722495794 481080443 346217864 1017506574 491274713 788625702 65466063 329974221 538496481 970414430 200994412 677503804 1067610373 617871299 539737358 184739455 611300487 659908764 290576935 631379870 800398763 112540755 1041089135 778996229 1066505275 1015486963 722198111 32520963 458053890 81226161 54591671 625476683 127601745 342691680 2979065 812850806 47694973 923415803 974790123 545731454 692663391 363373855 542843929 301236548 23093714 616412558 428749904 583306252 804744249 981025198 198856229 1021075708 345236214 218313991 221291116 137980064 228764660 415213001 999162305 87247209 616462878 780894020 1027037955 247257641 585618406 704429165 687589843 77702297 214739391 262484576 376780058 499644372 117669027 324070105 373816704 577735385 575378574 105025209 308296694 242462476 265340673 763093127 372641837 461804213 1030180224 1072973548 1057750812 863507328 432909332 215934774 338452862 175022332 15509449 166285271 120414801 556642076 269897009 159036131 472747352 793786553 575112928 418590869 974679451 898454030 879150062 116339146 585087970 938724154 830779000 293786244 331455805 539943617 656175647 1014815849 226914687 130156555 558961287 262623554 79573438 709602788 791826905 1023706492 973463253 1069755643 251176770 789727914 977436642 1052456547 38159730 1057434113 115552456 111138325 174567710 320089819 639778990 838239596 211052415 614744372 457400446 278973863 506172624 782012464 114483559 169278058 955833043 60591251 787055451 665705534 393226061 205353799 795366290 114531084 955292293 760309722 305863430 860887206 235044297 371564286 261577972 696640319 211274218 918690055 909960545 11548653 743292347 505900144 1001678739 1025840430 178979990 9445463 881994900 177593696 929066198 632395516 884199859 508266824 679947870 1056639045 394303234 23751308 384123153 634752061 808074713 53509689 36193112 31733137 569145169 322293566 489255071 390347794 541876938 61663470 573253592 1019983670 391748709 866179458 253329910 978151574 1005443979 557368469 164362355 248649329 65872228 603162022 742529995 518092328 109344609 250405529 954685951 179840704 74137011 991383095 919590163 747682659 404982225 964803241 905562512 1054758367 238589174 764673025 999163139 713871654 629160609 256916146 371190908 1027898316 928646931 361920019 434803472 128311948 133125588 139466463 85352535 596323012 1047724079 987369912 200394478 575372532 90446769 773495199 221809398 586448707 315213998 450191998 776968340 277798906 410292412 602403742 528804463 140406790 474010934 814385713 139493429 673205626 945049018 781192138 462841110 72031755 56497836 1017383136 333563463 105961875 551014321 1015861071 396990849 853222543 960842292 224988374 93279103 403716769 443828196 771031449 681324164 600729870 1069271348 113459873 344260818 569317696 37579738 478284888 703144756 579169093 824498512 708453646 43050869 136208463 300402006 596463478 95297255 1040258354 142998638 519490857 605958365 376311018 667419231 671969570 1017594161 283183890 696467635 968966720 674916031 139427437 248726841 547106248 774959591 157776737 677449859 84036064 546358031 282216055 110982249 493987861 541569311 829648605 302252676 146946006 158236676 581400804 190483124 275134711 126379821 914692226 871442843 313114159 297805841 941554641 501245728 351485849 254686375 834545038 608986348 1040301367 588441068 455694234 195173616 942666091 555205217 803114365 165294045 1001493372 697422986 760710878 917849003 14002711 767529329 960979468 603943443 440626635 470437665 802834041 500025109 926694283 876825387 435691322 314593138 232625968 65552675 193062280 608188210 761085429 174002468 697432897 515995680 944425210 87619144 415110504 436279370 114319297 611306801 324351648 21461122 821197492 648571524 664811957 61125343 13514141 493945192 505572372 741738812 215757356 428022284 131610702 576742327 976161397 1056970782 880402585 303226676 649220975 28692820 280447311 1007119320 996945781 156873703 746345325 771881870 649883849 1036844306 690833173 588202117 1050496013 995721112 266980877 197622704 182622920 787774012 264994365 1049353029 930819559 444366406 606336052 264792383 783167545 16377349 583073188 305269212 459151602 987683655 841602018 1057557023 323431977 843640291 668952167 106315343 692000602 121485872 245151057 120434806 662110180 468590475 345455587 804085475 834062732 150243029 566061825 108759721 262426361 966146290 368620469 411735582 519878198 805389643 795582893 332821340 769184563 831387724 414451130 107193027 1021975107 452944359 522760274 113426805 700261023 482438160 286931983 72132569 16234722 522912063 68446254 1063622681 949551500 247284466 52134673 700120227 305998720 274845736 619668669 780351148 626406021 497916902 172554589 583105704 292762056 153080757 68836285 494913748 410797656 710923810 567410640 940922796 552763817 847296829 664137003 912275061 540273682 675275035 747080071 386621876 749999951 205661781 553808707 197751733 944029952 626625670 1020980191 429384454 844072232 885000401 362828418 553537785 303603886 307943512 484126325 240085029 150881247 821552838 105892262 837110501 481817834 177161414 372923174 6689240 697827939 881077898 395428268 989944415 214599105 467870277 977784336 1068557603 915797472 698549937 428252624 24659084 614025600 249848202 703890830 681843530 68102596 959487504 267324303 453864144 1007432883 784196489 500232766 743764437 532533178 313097149 975950503 908434129 145492521 289163641 772622077 410450566 419008433 875122444 456959253 566648436 631384813 516768973 444254440 526281571 146495446 846053267 29519637 361941981 464905804 444360507 310943580 536932017 429599892 13810982 268248869 969921906 693127637 703984312 1028170743 770831094 265451674 961859546 63839745 794958296 175763795 495397241 23802516 426179318 288906452 613443589 1052102310 399422451 14309076 941366771 222296401 926117302 759562351 29470267 232009298 490244841 465248933 927040219 515360907 684516987 622092505 247878482 837418114 979771934 326483 455342885 191095520 608601290 861610430 270098526 660050674 45771064 809457066 781150728 141774123 1012317288 343104779 416810676 773698976 708480028 345195704 250659575 850894474 676341082 240481005 314568682 299688648 227197678 46746058 877975977 379703387 203967462 949606866 103484884 836051688 972005908 105489516 963064337 943754809 7536784 75034214 571992712 149412028 894331443 673030765 594890853 457573890 442869789 80397206 69367897 898896194 103438383 921497560 711657754 184694740 869534610 906588815 8839647 33280950 1000895790 251651835 14012645 577095178 858990644 105605823 706861548 736063894 898459285 574611555 467700923 335594819 328695688 491438546 443575192 748541598 742243848 3441372 995713488 839093338 750053203 610206645 965593653 20535500 951929197 503747444 833291675 910132334 987781531 243368598 104309082 844204124 481420008 511657336 736333263 170195162 655246500 541730528 499803355 472350668 173949151 436603509 967786595 247686973 248732402 938557250 71409870 916141017 749225463 648307256 358245258 617369458 207872844 357585065 742082951 489505662 789860629 536980173 735120826 881820568 1049856183 568256064 1056050075 385763323 96865629 795308162 614495656 905869322 282634870 951411062 608443360 516859083 897794612 331169252 703840841 950539111 54963215 780978679 179111786 721344427 464462657 697068479 815356626 733937290 848414024 431857072 793346959 898615449 911122535 855437602 1073493687 638710930 537874980 440410319 634830307 69278162 738637259 534229848 975809967 772936410 968008426 564997568 548383803 804550610 337329108 361027055 600721325 30419201 571591710 993822000 953310381 770271574 1047607077 923601587 741706984 519833827 945813125 331849228 903497101 377528156 999073955 756605363 894260691 182933148 544321317 29816194 369399153 769312033 613604724 770742586 463543076 444651659 180139841 223469310 372048685 733532193 591871741 92106198 1046332880 979027788 1012159583 941708333 970005974 58347545 974070499 491186772 122683148 916725179 384639045 93242621 319560898 740310791 200186634 74823616 853770317 53405943 551311607 43116441 178007941 676024616 613041559 936570216 405136199 57284700 219525306 230852720 668749300 238765304 2530545 700866777 818115057 308792710 53354003 526047791 415828005 265401141 329828283 173602272 554169982 181873748 660253639 288507329 973100653 42884827 345237723 254996106 1071614821 252259042 577652956 650197589 515729759 663880999 17690485 1000127267 517532505 284057997 702453909 354450775 417135058 865938839 668624623 679463481 303972688 437738225 130040441 185137780 14358747 386955752 811452141 207837337 947714175 330589165 583483980 953291674 1037434830 99317270 580698966 57721168 56724571 244734877 105396242 410349813 227008576 1070590047 792501325 393203114 1054398617 187466590 708294675 898289906 206484487 402465087 931196471 130647349 428796206 25808589 992582353 894130238 1025936695 1028967284 357433786 294059454 751815246 693908423 575917330 512680391 296511013 39238650 589929403 927935314 76109936 32897641 227090396 567168697 840724839 623100431 70733150 158052413 658935879 440798479 926914674 555865729 89319889 394032943 742081545 767864077 506781385 417220696 780845147 943871693 952885881 113250072 664443233 669159567 1025569068 65981216 522188123 75998088 145036979 602974150 593077067 552495056 712377571 155698820 424819063 753653473 127547924 732862839 891110379 800042524 658618276 106581473 437748468 704979269 654821490 775538344 589904294 546315522 389076835 271951572 318999639 235772255 1055577569 393374741 744681250 1033337933 143569495 999037242 843785318 215845918 366960310 920252603 273533764 376336906 1011410676 615300912 717422117 65916078 690067335 126858712 386826545 140300936 770356206 931714323 1004470488 39158908 881769769 945153768 426434637 105672786 463620156 934283648 968103942 281936694 983786671 864766377 147203134 549743670 238719761 139709780 351699827 967839432 209406833 657526296 925189353 233702721 555783139 876880812 586884900 284439391 299017985 216538737 522995314 831678656 174172775 905048550 632707935 1009914728 285734198 837840689 740297022 622363199 581527186 1064095645 331103399 983775121 924142628 1059770134 31791604 1066027916 759453849 40261295 541195203 757063366 530065953 18298652 83886455 495918260 538894577 942568249 52080055 505400884 483247553 802593410 580195565 695237636 734363726 699741080 12360647 163291464 1066524121 925480642 409552314 588672520 56993703 931928169 842765178 632101296 526420351 1047585691 1021342084 671663503 617285679 568550537 223098517 692809560 576161799 816571146 117355055 997258148 543318877 277540118 742542107 361734253 87167239 75215179 376024546 236410772 557308644 452192619 370346834 1024606557 592290899 69326043 996534016 107220718 888684730 271467302 106132928 202067156 1051089408 360525432 1054247982 140494205 334489364 1055614500 892738857 273937343 131609188 34556191 708921426 1035142479 688648295 1031409795 529627282 23358795 639657491 1056418316 264901265 497452721 433528679 835494558 249115456 139773669 1062942179 888676541 305528400 891453488 243279627 426962707 555875512 132002875 342760 141563630 753437491 783283864 970095239 295504575 287332543 609804089 591050359 559997085 1005024543 443944183 557456719 521936064 1042837338 196950029 985162278 862587910 64357435 910087322 616887065 912273009 875486415 1034175778 920272841 97333671 972676330 896638222 119377883 58358640 868745634 323351335 782100854 996820028 204885969 152552479 898762696 840581531 975786648 125461768 664723841 448880835 688957911 668567003 269401942 898666765 153495734 1052460019 505012863 368287352 128812063 369052815 824130361 281975845 791941441 253759315 216739654 314662617 802231310 762413256 905015400 509871998 258383294 140635351 898622186 847945122 31456074 632871250 105878551 411154934 695350258 1004075116 673464512 441499857 1054742456 469609275 480832442 553135275 564944355 75338813 191104094 984836258 275829629 453556688 235379976 154647288 151558613 250132665 615330200 401850259 282883325 591496862 303693300 441512572 622602828 559072396 536601732 301058656 319090398 850534770 187393204 485745426 941319695 596888739 401285494 741226503 711929860 218265688 237533118 561114841 148473891 656731180 498672900 365539781 859829141 58337182 714997189 129702444 718110667 790467731 21050369 830778134 440045814 1023625681 850931134 123722666 101302413 943185285 419490693 499102135 616909771 1042597821 54820576 932244527 524489263 13325551 169087202 1014676902 954442746 822585457 195950751 387847895 533684404 282087167 272064943 995524895 624534952 762634552 369197743 343476481 497093731 31438368 96953281 462698656 688732473 13936032 250361095 363962952 592361920 120707842 734016811 974387942 1010955091 909064053 230336474 7881867 940253584 899630223 834591812 391481581 391898331 506312390 475579295 35496934 665575641 195100662 1040127905 528129522 998238965 387477982 1062375689 395417269 178604254 961441955 895364630 843235187 980647687 349615435 1037437198 359032215 235613989 677421123 56147640 722373933 1050216117 686988250 699327715 801774440 999472500 70258371 571117789 685707548 318186469 177495703 659123708 42947908 26231247 28672593 573629465 374640510 724665532 511943888 900845072 421859978 989363835 663312217 858210370 833607375 730641310 1059705874 915758867 916260054 929036797 367251592 720029036 349179852 820832049 76505130 910195513 497475588 49958682 245229260 236485612 1027050868 416731738 207330085 866077944 412330547 782007512 1026496849 401319000 335912193 158266429 30934351 675159814 22219711 398145146 1051803012 37848964 905663986 964290624 636296502 273296470 158768965 812331911 702271250 227985029 997779972 945534472 388214695 848293918 36585890 123797442 386383849 151497393 8320307 907649401 430122927 679179731 608887282 267406130 674056244 441480604 749555133 190315193 523591322 639150378 406573460 705575451 283457123 97366300 994399262 22736428 255978486 34940439 1041404964 709801219 510148384 914128709 52937492 436655225 248608144 1035765969 897593215 568801453 1066290522 100199020 1054113691 400556674 143392629 217857483 634682306 648750624 214979133 75412775 342583537 101456239 884653041 509628860 100627274 454038175 273028406 15444554 497952914 5166755 558259090 588595607 613515956 908728241 229180402 280751339 805110332 990700484 968285477 384256658 800905437 195896090 173113951 403392606 609756139 189441718 255155639 138623522 1028667106 334382815 355973801 295075896 526415325 783028639 545876116 540392956 314392608 870451525 250867005 381362255 425061006 326595300 572245835 711668757 756238900 85767377 834617545 661933239 639192764 546227497 99996071 489683618 151235835 500344905 426840632 845091270 1026201956 1031307092 62832054 561004567 719262354 416851633 193184954 481834000 28031938 442000521 549482436 448320299 647350102 497264461 1057886649 173801578 173797715 938660911 937544287 792130257 666339812 675751332 617175267 633773034 698060757 799807976 28114517 263560768 964025113 293106042 789475366 672486372 896292676 998882716 474569392 1067607275 245419538 378240724 433353646 553905645 258851294 1043321710 327130304 487175816 162060332 561296888 850728425 1055848411 752931872 182569924 683196432 681030412 77472004 281625449 552103810 382900162 514157766 763740994 452775535 228162220 422728311 1069377518 759648104 743234552 423367885 849302222 787754983 704282076 682944674 237291659 172591815 966265617 1019629427 793960333 921172680 373804371 605422050 678772356 470306061 932377571 486795829 157608675 448775070 766405125 333950677 264415072 3958758 632864129 156585167 1060790902 537226549 368710950 542720598 566342884 373072703 304461635 347785534 802680875 836761755 127377452 423305603 549862675 117673285 563521723 500558785 585189926 689493276 362003660 1040094137 1002801715 220777061 392733120 384158418 278594253 337096775 899337468 95654549 374614730 1021601101 496487015 231462704 703256773 1055278567 133739246 655006197 279298460 202317545 213922563 872950744 542377714 992751626 530227482 542439412 261051821 438451814 874456108 649846278 771462266 674346749 168651316 1065458928 75866693 943022386 563113652 916868408 497394881 987767117 394055985 706898822 899475174 822168313 697351090 808022826 313968493 96437190 582310213 627509396 92911446 282998184 792517755 591672282 288639075 16290166 421762535 505457461 1000360858 767893868 743479970 731393412 96567239 307489706 47512266 817851591 198529016 793683123 958990334 946178214 228794879 356119023 175385572 827562216 515716340 380812329 348343972 344770556 1052676016 582095377 89083242 864976243 428670802 113908411 750420200 781097092 798467518 426121246 995251153 314522247 639113241 202209686 625764703 545988986 1062374735 631176803 789140430 970429055 987012238 613738536 559176415 943936604 498371528 155401581 631329366 728218105 584429108 135830557 172949628 1058487526 321016525 601693192 786863262 161458131 97501905 804405602 408563083 34066710 144625732 982810435 759590938 508618024 806909035 521783845 439430562 431309096 265322065 3258985 499882625 585817431 446910790 707215057 1026593942 845137818 721007450 488496903 539261382 142487035 855976934 1062440469 357895802 334002472 352383492 929074412 1050440735 1069283059 594733842 779574494 624635813 701469904 157923636 983777827 908050433 16001626 448780750 822793815 639616172 188077007 207148046 539863802 1044100129 337140879 341964640 841382895 266248803 47888800 848472567 921235966 287086452 414651437 543999819 377681234 552924639 387998723 695963286 727486460 865005871 235051539 731160918 75030638 645796981 302373619 1058542030 263363584 1023367367 449497436 120521092 738206062 70765499 153936045 705515460 598874968 528041456 360734567 825219100 246559425 1014903174 634700207 295616735 482660753 799727777 204688336 472635810 130479379 944632810 752788662 363956673 770805880 752832781 211026035 928435931 337051474 256026940 113957566 382356306 266504217 151228330 737395055 914744524 437972649 261726225 129642244 1041068725 148838082 816100653 256046368 439221435 837465735 103788351 929871622 87984464 886085888 317639307 856781858 929201195 759165080 109053403 423862913 1053000904 222247328 699242745 865098068 1071127779 527543498 849935160 876514161 497030913 827539886 21920236 344969682 165952743 628736329 56975085 452904467 1031339552 768960633 14526233 159411448 410693244 770677378 269633743 868462822 714232972 86877068 839354996 1030941797 590383143 17599266 380430578 7275684 701587688 929396404 152636980 454464501 507114669 145300502 63985579 645964876 12150297 170148864 754904268 348027333 40502035 406674572 985294224 924413211 1030779718 280206267 1061421298 743986737 355989151 887206384 491187061 922289805 1052357586 872090739 605459868 997610456 817239765 491694064 334666351 646001248 1006255970 981758709 172144125 994598806 194674553 299712631 366595028 162634896 221669853 276187726 859078027 211744904 20476050 478495668 817451320 808102747 856888165 261815242 989358074 1072332811 428121700 417304595 283985009 1026412349 517240930 123285239 540746049 490473915 286490997 1009084994 158488467 798642932 979272055 79370658 206165396 742665079 555394696 489540908 467969267 703671164 808915850 443076568 454000999 1012059483 124616355 1014118912 8486695 978536467 864149439 682234853 588923249 743995844 243314444 202016810 774160643 578839093 134394748 627582551 1033216677 853880143 359227719 934294872 575348125 534367648 169822310 606803451 240022073 640329433 400200473 750466422 689008713 861882448 920327265 505122782 196119970 66631551 908748423 572768945 624102556 699517571 870029715 973254477 113881749 968856222 1028452822 545434998 403574380 588371637 392476257 340250068 860180231 747675091 785747851 168832114 698231245 459262372 811300207 116642625 795922733 18596091 150613612 581250195 813660949 840706637 239295907 833586593 204961659 598849075 244261244 398041349 971986648 845642219 155271714 29579584 354853032 272783832 252211202 140956469 298392043 453116926 169480784 974635180 409639847 442464903 779756930 224703185 176847204 642559553 305310163 993361075 785414062 892840221 765043137 17540549 89084567 306694321 59678863 189033567 63165490 1000147127 834365636 122968126 970226457 680746380 684890795 504159488 491860201 939499186 215184081 366447785 1047892160 108036431 1027840137 486038049 606453189 745513643 91651179 1003350964 271600033 616538806 885376721 789511569 730704638 446582399 517527129 705614923 446743567 536992446 64867942 16301915 964032776 198913612 550450590 991144859 218785 5651621 665822317 218056140 241813656 420966509 533562241 989146386 557080620 25044456 771807821 587838835 764848802 853751168 82423174 795556443 632297412 450465347 1026878889 815857947 617181277 695165026 366441843 533637989 60021950 124409779 475011174 149862866 342719292 881583664 1021985099 488087132 127633071 231677558 989339819 750378725 932154613 1000971847 286813012 165627822 488879469 139036937 963717338 309046752 735909757 500765253 502600212 576537095 371794189 750426152 815759259 772567697 966888713 969592325 733309007 74112596 860416483 346126033 973533137 960812805 466235406 902770597 120423689 931165122 733866116 85936704 936153250 995963785 132342593 131512194 164770697 884322239 895843781 921993715 481629554 289300138 907606422 1030871098 565691220 784623094 213672636 511813542 874847720 896564532 691537476 64046760 429086765 436461654 1021245630 868691798 706774502 136041013 917318846 801458666 548944410 879570700 663296351 979748674 323794324 386469626 243560635 96340830 320578913 228161667 219735668 161327076 887976277 631317264 57312814 30238367 22157958 247449962 344496658 340780028 216443342 887917635 313270605 530725259 948973133 45737134 326555279 821803140 431901670 194193057 741688973 579712064 178969021 503255930 371127935 566451388 580391104 1037958263 982719139 494971161 370493979 111768893 660430008 476434974 1060687297 901060178 720482948 990600373 233091306 477089699 414139470 306459754 537150607 983649022 891151204 90035695 30217200 11263641 170922135 945719707 369095439 969609098 595825338 776515046 639900979 508929100 849190183 257331694 449799014 234571585 456099385 389898229 467528439 839235882 659787219 728504289 414710776 127505328 600749016 424384955 948854720 301243359 609132208 1014972464 849170283 883893414 799838666 220433171 241857109 905609560 338424852 370203097 201649315 686032942 599221893 320255516 877034938 1066443971 405170836 927018520 286404294 92371606 528062654 454344497 227938613 30349196 270264068 315707499 1049234745 24032875 86081386 749649137 309313609 158208352 579348089 388034191 701623200 825574522 24752574 789874743 394687165 616972332 76025417 909189248 149776865 251481039 334518062 823594018 372192404 735057950 30997512 765606011 981480481 42983864 378632049 824645133 878577173 136618914 81073547 246715134 231789252 693393858 101272186 626304407 212380612 1023169381 511383784 105473734 180517488 508827066 161745024 55590044 910327398 791596628 241609843 618665167 970546185 37180844 995047926 141176632 218118912 758432157 181677761 647624790 742028470 54953958 798394258 26473418 961958616 925315244 144737960 993474265 61529561 627742965 1034324553 324858606 945372017 113165614 55046973 236458005 982359322 170640294 122428240 32921472 599637650 391323408 82238419 238923270 736687196 951214341 15967260 959471263 970476095 769500288 775528450 910718185 459289029 633780321 967437921 343615399 631062717 553013738 1050535836 343429948 1027112889 1003605829 588936214 652706868 111265937 550865403 470708920 313364924 1045771486 584825214 429010799 52873253 957947008 1062528417 455666090 1047143269 205267993 143485211 738093792 59251094 500751247 938148872 120139016 281900405 487681166 674168423 602542367 301809892 575953156 934435485 703341990 915914600 932792739 313071600 226721057 806746283 144796771 627148045 334369946 405426940 993551101 914629251 1066781211 1057111498 796115312 693278022 608953143 562359341 670243968 669591853 596484994 127082333 438315058 897409908 281146133 172523833 644769362 681551162 1031279883 37326529 949708013 226156036 766275078 498438812 267259095 806440504 872536747 520466323 796426279 243423651 906466849 44890900 911673526 860219892 410431638 229124016 535697059 929915199 326145467 61751197 741199569 753245307 784540483 91320117 802138471 817104388 639913831 383442805 211198032 624539673 896819045 223420542 294743481 342830943 217951741 636658712 55990934 975834460 766870003 64538666 206052637 911698685 763032719 374763844 349259593 658488081 592799776 658027797 61359448 734313676 1001852532 285644021 638348365 228785733 884899682 490817628 399471 330297080 40918849 178493289 78306248 1008435781 452826478 996328796 911686823 514941422 721490633 191761180 787645471 924037277 834644024 246292914 271490181 385965148 90696996 927390924 466059254 9568539 1062286839 601085243 868333263 679009070 272603812 363668341 44951091 541084108 1017023775 254028308 199585416 680518033 12976096 432238677 600480250 728141564 489987172 881790106 269277943 509561074 181799340 709369577 266476210 216912698 390021821 262560618 206378912 178229503 686718238 698164461 811127805 224225105 730537821 999929697 693834824 799616931 606685066 1036182110 255028675 450804303 763716026 993645468 881550580 427090190 474271366 408514938 521542695 289024384 188291465 16172408 668045802 630880170 261930982 1050736317 54914959 30953587 357828287 920736915 834889645 189967398 590242239 293269733 396764319 1002526963 119728529 111823560 1033127684 594963821 714400358 359041263 951907389 329108238 244404852 564249653 991524082 813543599 806201458 981852695 195912590 733371664 338424348 146308919 650537662 646037846 1014309557 613968347 104600566 1005831048 52390272 343845995 296789484 859443473 524785734 855549943 919507739 433946945 288856531 1025851054 697104449 100665292 916584569 146345576 208218850 10303305 115537036 578566942 11425731 399233972 926952164 342444396 514830703 419132653 120310622 334792982 369798837 859158838 880762715 407768960 904321320 23005113 398401599 413057588 490089374 1014391552 677076467 843673952 317915313 366136187 686486884 925532757 107254082 963031550 997250818 601532938 928613105 939391552 496606530 1038727063 107710117 427691358 217854748 438496954 759039754 388562005 324602509 181138005 515827470 1037447819 987423511 904052461 258297956 943470663 710221884 325137709 628265474 19334452 696758279 326775906 288591522 1036051170 224035203 752567548 222083908 1070194501 203459393 317379347 112045482 803131188 970351062 336197856 762329818 532013291 744644187 533977407 746038688 73318026 131355883 895289908 167927050 411287700 849861417 964005731 802605802 648622193 838901432 887547030 461845080 996973292 770624448 984750139 917446189 1069986485 497582960 911635940 389275528 994656992 466805366 571031749 663034957 1046491492 582522761 620527161 920448417 881922462 814811616 429576253 830279280 515720907 331157432 1003085812 16095720 895334033 520500433 1059575841 341596667 851905399 98701553 223276976 278111712 90605416 548318816 739279918 679923858 705029684 418676843 196854859 493528911 772100111 1034316258 1029073503 654311451 430070801 1063310234 283182819 63985723 36807348 346706667 462969588 829326010 73719897 104063026 640697043 213411559 646195139 588684624 51916904 437604053 582296729 488188969 213464506 901203418 422964713 216536359 196452216 735676177 714959008 509459893 86744947 956431320 975059475 616296132 821135138 843008595 398772857 384756553 400101917 359429094 313972590 869045948 434946210 23790527 863245938 240626587 481411603 376098122 504883048 33063397 560426870 1042430650 479467288 247817632 54941172 470985607 284766637 498859347 499241307 633889515 263054648 755286156 449230491 588744292 565441579 607321692 687607372 375499829 786970590 276952022 436461351 214923748 272675597 152662676 683116681 378786493 168604760 994645810 661531892 657233486 775358658 516722640 372583565 497184489 646200883 302510740 555069342 885370918 651261430 508077094 106152213 460473694 123094844 604589618 615282948 885895217 115749271 791340522 831862559 8886017 892084095 859488898 394325314 723149684 82770128 800015282 1008335336 101183734 105792842 1009289271 780440244 673106741 151248656 1018278994 1033977580 901151907 648295722 1040140359 910713337 284191991 886939140 967804639 160224745 838356908 532134380 42691559 452728301 658711169 735372695 415576751 920451291 1037155320 548453532 641297547 812710828 292317655 450997240 581871446 674339839 82255785 106402953 538256362 974537365 576730430 10321299 1053334697 332152275 595440935 588601150 164404216 855460932 565361467 893340949 990896830 193771284 779739925 116500616 665542377 366410901 328779411 849363820 337687017 83036862 996052056 127273590 815613748 619874727 15107659 473501635 1027078848 555791887 676519959 139078995 372264844 843205590 1058069929 119715721 674313751 886407299 605628853 32948141 210756327 659885503 942421041 34924139 227128580 275958743 907452631 186957393 310914170 224156735 854410663 493370964 878604507 133719050 105888099 536593484 965175226 354932338 447246866 857057139 980048689 990269270 627700606 709188330 764948572 522780087 122785206 783622196 470494683 484318779 346532749 157895097 1030246996 57607594 92123417 360648005 1010645743 1012906867 233794100 443573894 574822873 430711848 509708542 239896977 748469442 202095614 197440601 157022 135701343 19882318 533833323 697710151 895919592 704818966 290216736 711501965 359541658 686450553 608292518 695470804 494367030 671411771 843729903 529240226 863395712 392975174 449268531 161391843 843772353 326331687 455336043 49532007 368847942 853967762 253082071 124655715 268280543 1028491738 417115768 499755244 57380705 153741690 830626967 702267264 692910117 37051535 555374652 651518333 483485318 396744795 520219064 159353511 261369191 308938691 438328348 176123814 635060138 325834194 690478015 412242053 986781370 969738292 584311996 852548405 215099650 824961468 506020210 720117256 295694451 668894430 448305410 259066423 849740035 758574646 282791380 1040549468 826027816 935239423 703851539 497684728 853722721 326918045 548497452 16249583 897798062 942555668 155839827 811794951 733210642 126725262 29391870 477819756 15836952 864941016 169810024 941997615 98964812 211518950 79481103 988188098 77836989 937272395 511190326 186238078 1021742466 225816258 519795556 271879709 139847730 515833256 553211875 755466816 650211434 613239935 846205763 570218218 845415755 359740524 484921556 391652100 1008897529 603109050 363857199 259502295 265019421 617961301 371612846 18079893 542619236 492193616 468695535 427662032 472463102 963354464 289096789 652399361 692849183 705178206 486737542 713529858 163053698 727007177 457841902 319668372 663603681 855191105 1029633083 514722267 156646270 106051085 303568864 628977117 776414878 951718807 907514002 195652614 310329096 297998826 738808526 465202599 457609610 461069627 484588880 147961970 726665844 413723997 2238365 418148608 519539739 588030027 739377275 924822860 813995352 832760994 235371636 769431349 73889799 115332132 178082902 153886463 494542728 116547127 100438965 552811986 960620353 906240611 337082216 187680826 338460953 511173336 283630600 909725862 366210047 522893030 548682868 721557993 624491105 565429634 407650384 928389564 621373621 950276040 222943873 1837881 400196596 633785204 240089011 999526753 745463834 140561767 55262419 328690072 837787304 863011880 901043605 802795044 875676962 737182304 13488880 673851570 1072931729 252909917 702650780 514897104 253610753 545588113 545677467 36647540 486740996 11378448 651837357 943786099 580891950 183384085 566775258 798865163 987425175 467755901 289624045 441711194 784607068 1067215178 814282483 269384933 701949470 133054242 1046523584 407968274 372733313 178262734 761035882 481931438 552887215 129295547 1008168139 54592871 642118610 933900924 896996099 813217107 97461405 28717382 418092789 835500135 517752516 436902003 716100549 264467457 883172224 135429119 738362976 138206559 981906188 347223822 997592052 816983078 139453226 545908324 488648820 7904476 913501599 573698795 719490326 50217838 575553203 209529905 749270740 839544235 443247538 481948392 413727982 939464134 851229037 283997028 1000437606 437839064 14561977 102363168 152839555 179160411 5721839 1048190010 330161231 594380209 517417067 264439282 758301976 128092827 813318925 962859310 789785587 779162051 201548475 583401977 713055796 353797170 253915613 25990912 11901176 422303962 179238879 668185620 590940059 987858702 384540595 980622507 1008357954 121997572 264621644 255573598 1043479634 712830554 957597988 859343724 493146871 705166990 181759159 418309430 786377631 117468037 628519686 782079681 827961980 140121093 772393493 478011191 1029015813 757356091 311425645 721554534 492729461 113635894 909090203 286827840 239688779 994180201 92071087 711435353 662100168 796090413 850603710 361775724 722424180 424735293 435793760 980275415 1044818842 975835960 228664626 945071130 161155271 15360547 174301269 1012207196 18093391 341049060 329636078 1064790502 344123080 88497352 934712740 754889637 130214541 687383806 1007559205 816330156 855204924 457025817 831477153 753582512 718732344 683763090 818293069 423066507 282353192 558404676 1042931426 137966522 192243575 301289198 375011099 370528735 646407634 662716853 576895035 1051447103 459433388 947809695 334988420 466862404 19337405 933034777 699875521 195163132 620895359 233053298 459934397 1050809497 174639280 485883998 776175562 773614575 324693459 693097588 824103739 978364666 278928303 746969007 549680362 817609557 974047182 260668657 874596275 978402755 247630847 216243579 278128630 834695338 493090004 989412215 639533593 565363859 878960677 1044927599 867285252 722171052 977136523 598229971 862166180 321302854 767062758 579581302 783855721 974936663 237084376 121546769 987529671 956123641 731153223 86474687 484855480 672444136 523488735 822454399 370523193 220690184 728564878 590563510 404102344 833898974 70833158 31753130 557565677 557060882 1062694462 862440456 12942254 257629427 747960562 946128479 52124953 643185395 369527838 773700515 101741758 1024132135 676118663 950967211 891341362 895229384 47205938 357404595 766708109 40113588 805616363 344628442 190331372 381144302 94902463 1016059557 470418417 983986713 755094658 325099898 1013876798 175672321 321033290 287048998 470992382 481432595 19375602 976883544 699404636 273686752 477461913 567068196 661199369 50897054 251348000 331295361 654934458 797811623 393475503 655903435 776536744 868890360 27332657 943220033 50832911 1059245747 110252499 186161800 529533615 683098269 350095241 361607207 248953678 765447841 15100809 830857993 817501492 389005643 487953357 927484414 641908397 154440270 975401110 1069008953 635678091 942974719 256760548 244322259 934854049 129112791 178139903 614970439 432625481 275192308 153685745 976112885 205858271 243846041 927758601 552478624 96984644 939969706 418266713 243993327 261395804 986266161 968936761 247662831 165324432 586402780 92251075 498000271 401812045 690224764 137416277 704640291 882900098 682610311 375617042 1061308130 776852262 1038647959 493977440 404459368 189981872 207226345 465385579 411918132 372252318 755585759 16095137 808472875 298904559 78966142 911313460 611929364 365431720 34958833 248730268 49666586 311785298 69114628 528840466 999162189 1038178682 675124394 1069432854 583286817 649958449 10030712 828163818 468978413 837277578 844241447 822809620 731176813 1040599070 1002734102 779931104 829744960 803812747 583283653 749663964 184494699 650862832 182532699 170474586 494391765 412177267 866404641 826103025 138213833 369706171 516969989 809955068 1057330295 925667702 513917976 971714330 203775091 794640853 202448401 224018092 986142516 161980427 621732040 109931098 691136406 218324690 314922427 377999503 50688088 143609830 400194956 597106680 595232415 131541639 648841856 294905353 531051634 789570043 529918722 840887672 951601980 1062669322 925361182 484650176 909526605 49665921 74529799 802669727 675495257 564007599 926413970 930778777 299591415 481116651 909972920 1058421619 991144739 862537228 628885528 150864312 727565757 792924911 342556530 785374263 197327112 404059637 339146029 699553923 824660011 275016834 906605267 43545970 243855795 429787776 826731664 712741278 255787536 6058201 835382198 983820775 423466515 815846400 237848891 484386800 927937911 840438377 637450297 466059421 727346517 207215372 671768685 453042843 681538221 321184743 9816249 930591960 905434340 447000697 798970275 262448391 941080641 330197064 119554004 868779549 600658031 268385627 290182809 1043349207 406942462 780198592 516883045 326092850 557111778 797250311 1024496461 178732017 558136818 822683334 343050122 1036022554 606450027 317930259 781116923 28193913 417940074 55863309 612051105 112161564 876129653 849741651 889599777 545922261 983097331 806193803 49901893 919697595 849808047 765059549 995608955 488609194 1062929497 746779253 597552980 324716734 575159301 292232453 268634631 770882524 635026347 547345472 28902124 639667241 798309029 576111456 757751809 304609425 979091507 787514529 674967144 93757505 950457850 590931908 9207015 428069165 516606593 1017301133 968189543 483518092 355795891 495842629 864693365 745224023 313418081 964830520 945283524 864425165 513322941 695402296 858039465 333568242 992979423 670806041 233990558 906495243 935955523 899911987 939251135 26046499 722941769 622550755 334899536 1028457865 358736308 259882762 240171573 397448016 718101292 814602125 460586617 384379086 93839036 721138899 503523016 825361694 5928276 882884682 891013364 219190686 944105544 716932834 848566899 697599089 929481679 238882704 960379616 781735678 115534214 670695885 52694646 620600431 691745514 351493140 265005208 385068084 1015587809 982727271 980665932 405927037 79703346 586034379 945117371 909695171 502234889 16981448 1055072178 278175808 377383796 486164714 302699556 421196913 829380840 677822786 980607654 1009479579 278774972 981764069 599569906 820984644 117495212 880423532 583209317 832192182 317193816 228139379 601619328 464117120 3977155 127584027 18167915 941999604 851680213 182746503 7918701 736087978 408618970 717516130 977878645 263383547 54210304 296911960 658764437 818190983 741684444 361986968 383759489 952437680 485861349 871460441 227400212 1043213084 37950456 910426194 184100300 1015175223 641508562 1043076160 944157001 881828527 312301722 968102500 1045817298 883792118 452477524 1066417922 67047632 150873795 251386991 324968675 341207632 330072977 347138872 300513236 753423237 221131039 716730212 90260261 872089412 746785262 311306379 564418603 382822023 930373575 583640999 678922430 266687211 987081266 22704537 902650300 355211570 717571328 97137060 872335748 777317313 719929026 58555376 940648059 856190242 1052030799 1005658120 99841419 824822404 564284994 956205917 1019013279 991356470 125280633 253180865 720430376 501584432 75815831 126337516 180099739 1067965066 501404291 850777083 640985329 631791618 28653032 576778219 597415717 581714555 661245363 199462435 966482362 758258552 402180248 309519336 193472818 498305189 505551500 962278886 765552792 350504527 515074892 1044724397 290348023 166746599 415241429 460524850 425881313 12504195 233386474 838971210 374983401 674297181 311966866 472226866 714866217 543282258 104873111 661646090 381137341 686226532 866027016 923402582 766111814 923668024 419104696 234411387 823458920 874660505 409446844 22659400 361281356 598017267 268418033 312796266 784144158 831757785 438891636 837555959 64302480 681995647 902987304 672951268 194854486 277624385 380999475 691717006 281798056 875689754 496418689 245886517 1044500163 268162605 948107072 962420349 323582568 671685440 722570594 472902636 1071060316 108214844 1051033119 772580718 684318438 562884015 447242608 71087060 338272084 706928970 80800149 346115152 1030336118 29125731 157184399 536294138 296094241 416996468 190454695 68406607 333839533 892915610 1020854245 908575917 693719928 537632535 1060563610 620542168 228238689 1011014097 727427799 53903992 787392846 80137936 33157363 966002073 847551654 851093443 63716617 19731497 548682199 196842364 836263288 632512637 960511698 404783216 900627809 800260045 798262154 20670264 833045292 919764147 252289145 395715859 958824196 470874544 119416090 20342369 819620182 738812840 532536944 265986345 385446230 690959457 360459646 1060937620 864426874 1041286407 500755917 458168944 814477309 395718827 326888425 243229614 442497373 658622143 175631332 401875173 132240093 225381788 210321361 701404620 716916484 731174140 1029107274 795508419 127925788 511858816 649128171 1000045387 378354868 547484204 751981269 519112842 185250335 339205350 715118380 636849097 74077939 899778298 904335257 1063972085 637983627 899183769 195132105 177062177 394700421 997012053 607191788 223741185 756605764 256661415 799216695 313845617 934748270 746330473 971883362 819241964 1030028911 1000107100 925959211 928738582 426765813 887568292 939061201 94824243 78642803 712054599 91757465 152089261 96844958 979840690 634322764 590120594 157130995 693275443 138734519 939973395 577572398 609523327 428609835 610706439 846454740 728340782 169467 470653798 968493227 598199611 1072577792 804658126 261472572 293535877 129965080 1016433409 44189272 989415248 609247906 1758308 554182544 838516420 489074692 414151554 683222460 109174637 951056934 716508807 531636597 551935930 679805940 789225670 338893210 68757118 497640415 692466996 85047759 937971058 80190045 100217067 837155065 456700848 712521829 552480167 324126660 508207162 125474292 862643276 994332445 620262513 888805514 711796574 489963192 284520094 147491245 619703687 1046719371 873528429 430636389 438627349 236879441 712056172 730056895 666419577 637104649 484070801 61278283 135540682 840147572 719761330 621983389 815195968 22555290 1028509706 883675855 400351417 1035588421 2004666 92509950 603605047 209047941 84136518 219496136 12515168 374609194 226525716 1065639381 502464508 937830221 1026828529 333399627 362432123 432511176 873836427 811597656 976333933 819855545 280483576 1051151276 217107208 647564035 445004590 671301628 470269349 691181261 336061832 967403904 149027907 602760449 890990408 821724278 912541187 525817550 221983759 801227421 523115434 159890471 230429798 410198458 332974626 643871298 1007437881 309187095 557221113 667750937 200458583 909716735 513085664 772009708 567418355 566803267 603717166 801285309 1021750054 884558777 678097755 177501907 159807339 881858999 136152965 990658104 459306273 419365788 852045038 1023911994 264252684 2117960 31239036 334398702 399016149 179833502 918629176 988947880 716766597 544562697 555339471 1028541316 539508238 472913653 755228180 914892257 843668931 539763793 425033852 984604897 673675994 307539732 367036321 647906282 669599985 8437941 162548160 406282280 823014279 749828529 21531706 245911305 1051791486 22042633 82443799 849936575 298181279 762482113 382517886 112958145 593112086 689366882 425954110 1063970378 1054265586 560284280 496780104 59526872 71076262 217093141 421382451 343961775 308864395 670433101 76102071 510605140 424729948 412842936 565791282 814582803 340063672 993037300 704820007 492311673 741306788 376538144 611691193 47677658 30643462 935518305 605712180 987556556 537949995 930196321 775184773 860046250 371025218 620229835 142585789 774918930 969725150 456611792 796168082 710165863 298509944 1018991013 881068254 858278480 668825579 402565122 72929309 422560567 52709111 866000805 353874163 305660364 173646782 44384973 1017088164 26842751 236041033 13137856 785043611 678768393 989512196 916858694 598423780 1039566052 874292798 638038827 634245810 798219214 354005675 505380032 142265049 155947082 476920034 935951195 99726420 99104287 1034820575 969695954 95380161 121456343 466350721 622418436 178705632 912777281 726710797 688537937 159952664 202314479 1017157801 1067682077 654165490 10862777 775565282 836016209 501790875 614861624 116719399 62243545 229022566 550982220 943937099 147410983 810463816 512180887 141613063 540774831 955399003 399569919 618892406 421759337 433834332 265689136 475792280 1052876882 852536877 856045848 20187087 213970155 659584339 525862761 866148453 192186808 483618425 344799514 334373892 337443778 554485739 208762855 482712379 1025583382 942258460 991551436 627651328 777281348 319929632 925240718 200572713 489908705 765812018 167787826 127782130 824457477 352258864 672888964 586499450 263690190 364219418 288707985 505716806 283701979 303493783 412435757 959505853 458960594 7055728 357364078 641122729 681447130 288853523 980954159 598664636 829041441 1031248657 394030479 1051458569 31553367 1021518496 4776559 1025026439 902879538 606771482 496470775 805085330 485412584 725217148 623634706 766952298 119252408 460652008 974339821 876730033 950157410 637238819 887479676 863060977 108522921 568759832 335807221 1060367380 444157656 847868499 333072722 701532650 531680826 363884679 790504660 103457958 378512801 434330120 118452859 301863521 288617697 1017327186 867571343 136317590 396552273 816479616 1009232666 448874661 873295696 204395222 918634091 363544145 655196862 522104631 292135316 679663169 65633151 828642223 30590701 419776130 885946620 690035691 498610320 491516675 655677346 418621628 455077595 503767064 528496481 909253273 949530353 549696760 914100782 925735962 226318648 438849087 1012949633 426900605 36683740 674521197 95181271 268638756 811523403 880912996 524986161 429972756 725689015 1048885230 718327188 1057243512 802772632 231453749 582781575 958427676 1026655015 205442121 112643224 1063351027 346125540 140452254 802273751 1039129489 570837265 529157259 214615641 871047602 202050612 271904460 105339574 967832497 744712345 875550208 186157708 789717778 806085837 585379372 75062010 295804665 529314341 999801911 843946278 988249776 255265589 396810348 795132088 111483941 929505881 617251067 498496092 555335273 885137455 659856504 983923267 1027331122 813150747 611406938 457107107 855326298 813770946 879112061 276311602 92580446 266479248 1020507297 863200943 293371104 518544946 317955304 431590234 591481894 728457500 98211420 830526327 892103320 822935044 280401511 98965711 366018886 829960037 890190937 724782638 909949536 883071485 1023820774 320472550 540441531 822877008 630753189 150472778 343814483 469657635 819729298 370342452 286238660 567065345 541083533 232461185 1063286479 102011577 382732761 36431248 178191323 738066654 594446749 529052102 502555761 108660806 857379175 828493836 180603071 813960075 724330916 240002383 384488983 761449357 731171625 743516671 855574893 283440622 958456237 488046737 412318172 262390677 263642700 842439677 275886881 927147820 479566342 158398016 551493662 246451106 546883645 15685339 601589081 509878954 980629819 327592275 90114938 547275577 418622634 485942191 698178001 430757900 356627482 103218429 994230478 404938272 891266431 426374094 565671047 488698680 355048881 1052501173 526079797 747664474 991269610 537178316 399135671 90483794 267646794 894678062 1041844237 31199790 40790870 958663806 722927583 532518848 285737077 77229918 462175988 815466527 1012992882 331682041 377314235 839939623 560989950 836541051 996534725 234994420 1002898986 226701459 947778632 48235627 265500401 889588216 687229087 870642609 1025111212 983274976 456741061 559041458 947579548 10793610 1059945949 146255771 779109988 770405302 1014022829 757821792 223246987 165935400 815537693 126873656 931336446 15553833 360953277 516917020 500632973 277873414 259194941 136383307 28041322 465530255 594739187 256072392 524118189 655754648 360910168 113277659 1071777490 1025304700 786379147 2868876 877248313 981669525 742133965 744631595 918482085 40057285 336160003 600572107 895779518 444791792 883853367 379278530 75128975 797928831 181440279 621472811 949400328 23165919 260830069 530561124 686614397 926709761 783732421 795502480 428355110 470559959 623060130 641991446 227478685 44533213 115064137 923803168 25264227 302990733 761630749 368874525 226079067 967658474 234896929 12670784 795587660 228027638 937663617 786353919 1030053220 181032764 981749514 702629524 1070506672 57674311 869167789 228453247 866782885 857431337 107567104 812964866 886293146 990319861 938855868 865027492 272664908 106662725 927923008 991990703 1044543832 375973044 180996877 245804466 79800261 921261925 645260616 556353023 25389687 440467835 710654524 24754222 476392125 499077023 146709717 846428056 564119492 903672701 341568805 725323229 67373345 41642567 917132003 1065527647 121610571 187175728 236619751 801258436 303513631 593090034 878195375 561817720 682308955 917526858 747163869 1065386793 246817571 1026967926 965358007 36003401 298565759 396406462 473301158 529279375 999959514 328094696 966778808 601956470 740904324 398900418 693342750 832129213 471550513 947760283 731494062 699695333 116131193 864992458 129110626 1006378679 1026700374 348193575 303622870 524557755 517832617 33900685 448917710 833248706 1031222965 800411486 56441519 13955420 644125090 1020668415 1033064193 976682083 354616315 928391511 826752755 55222895 227221297 139373396 181850327 970360159 504268054 138506598 827865761 472536022 167340642 995813122 618458221 425650107 464628018 900886561 78637814 160953528 519562116 663197631 1033222687 239290045 52770236 293983836 537843566 441979002 627996962 553740414 512935052 580405736 52500065 876098861 869638599 902799041 333834250 110347381 822335632 1024683267 201239823 82232807 872732157 604197745 109513544 162309913 96064840 688410642 397779442 21805602 540883534 362213040 119188523 911731743 488963089 510363482 836711287 96963504 197041974 734956771 352866878 994156411 794116231 164752224 1068729931 357813416 627715955 9467566 760812367 834063716 872126601 342878442 134968668 562952031 1069563905 778039543 313910122 631525965 711543859 739889403 996073942 313605737 417407006 409013474 359032030 496347885 562939362 188983514 1002832678 261872795 579725638 844724181 458438710 582468663 1073373747 17005067 620410617 97084682 170250039 145542005 671435840 148360033 199114755 957063763 341102909 827724556 11202541 140500390 614772233 912358880 856363119 62006199 818703390 620698166 45884326 118952078 670718173 744552809 317843156 502002812 855226377 304150107 547048670 186065554 1047430730 243502065 10586319 961269543 756468652 280476563 103295059 323288662 839515677 722830253 281787965 67568254 318403571 660629040 48438530 522422976 309651043 50593553 532685115 821248388 35521547 324446921 300780582 920189685 1022825321 299515092 426798630 1065579392 161097057 276284978 570892607 858332761 612030395 365259753 23843739 63702006 841394082 557862273 496017928 91762834 428299303 395443079 987972215 780317355 102584508 382500362 847953534 1070279044 306497466 850160417 279428567 352019364 427076827 416812387 446030047 482741589 847044545 488675949 1026108184 959082278 298278509 767621472 586284456 128859242 328665032 798759264 846733783 295989687 776728093 42096662 880829333 610747239 211597725 762017839 574995441 295541786 266083034 851027931 465603491 393620274 976604493 209295182 98690436 820708182 15739345 279093059 282355984 234834160 111888677 1029011316 641543403 872476847 1033909869 756743459 1065040217 96931333 837071281 858294676 602378948 871608746 1000702557 530438289 253121594 355620887 426465727 734166757 1058200044 645425164 844613005 239661281 715488176 860176651 6795868 931993818 529454976 635591131 581991978 903314857 147434489 1067740933 396466901 26671401 483082973 958873946 524730529 833027773 868445074 177464427 92450999 395014599 98141601 467344656 341018528 62065714 292723511 486068194 772939726 834098409 694848423 103972800 263193619 479798878 727238118 5725262 989458984 990299396 500011789 889315441 148172071 596968917 915763419 114557141 595681298 419857613 150240304 834497127 685330506 1048865645 468315028 322162907 881926168 870532921 678336942 444189991 309780776 434270266 1068867533 551209990 414332681 1047101308 426541154 703335543 704989614 818664849 167436675 197996091 537708528 1040527629 549443434 1063800922 494795273 352146696 777535221 414203806 141124635 314818463 853026852 652391703 746125479 919826547 873386141 1019716757 87055126 1062256424 1002810923 552606513 808333876 759874023 1040156987 637054405 124390064 821642205 658089821 717617007 595020189 1040174010 313198025 46606354 96481012 128561715 679748568 104243925 718006287 623822977 607214983 173517986 75084336 502173407 43406839 28846760 474254584 498367247 408089071 74412250 494959856 284446422 268427865 6201454 127557124 688717435 275791553 292656734 140199427 143075149 183578585 31386090 1042642720 391452186 831138296 845445908 573858420 1058266552 356235158 713822499 450771578 256507264 742446033 283805984 903026065 161912782 5199083 190616668 173875326 373733506 81094346 122291945 60874983 535604098 356259190 702821916 316344281 407429942 455567263 677832465 161797186 607285002 481528085 139939111 472909176 803996144 850888014 130357376 193519025 727910619 654676452 764023938 936719496 778981701 984049939 25810521 445979007 84721578 337818687 754023282 685901431 598382091 364250732 41482242 498180666 56314476 463169221 782366077 739250929 639528278 574974742 267862303 426205358 52109398 346055249 927943270 1069017060 451222652 39063309 269070742 937319401 867748061 1040314882 810509876 735107451 1035755793 595862670 290739595 283085113 524331957 103858995 798304555 167006757 687882474 118876183 320542053 835918888 845111509 322778499 1068939216 224010894 497900061 166293605 222528967 633493126 73498736 181906126 669469416 182178212 190821118 746552948 944879510 1028937823 523498236 441538352 872185720 15821970 408160803 452480385 359270392 382922751 123846958 1050218760 1013524166 531814087 694625888 890528522 911306834 640018932 68772859 205627633 776148565 282663407 706062026 372530892 90920521 1020616970 656774296 930714058 322893804 1069331960 343659191 492358339 230513601 302681680 351542394 470974639 430971279 559313166 961931707 891448108 49000160 177084689 210806102 92073213 478985602 1010673566 134247339 466685573 154851850 13133531 799574304 919111760 728230477 816585813 376967325 726031755 1032754149 214035323 176628239 849774215 309738162 8013856 693717222 553724730 1030524758 203585789 471472790 57109950 579644855 387951149 1004592409 639845584 788056961 707956656 502087019 49997394 958396066 297113576 132814349 393003465 150463436 668741151 204293508 586287839 138628342 116657407 234067159 222188515 449699803 598090008 765898260 880654404 514636922 255097693 488153803 597169946 343901077 565859239 465961616 812539293 800093490 208509745 454394238 35316140 246521629 333422363 177712815 1060326471 457317219 842644199 205961925 604443669 313056984 562043647 281562725 14583775 905353106 231771949 464122038 540895506 575183724 799272225 799276519 354391618 285435525 235569902 584691110 826131874 1452478 686987661 454502825 591908748 37480767 190875481 840152105 1026099456 926296819 95802002 28270177 575057436 739521799 267051994 406114068 499113129 594369647 332744891 345512197 548216462 94528353 526485023 716743037 677545051 958326743 1054472918 262018760 212619199 580477457 1058951700 230454967 907128338 223392530 401311216 19801376 1007911628 994984735 1041789414 1006342746 728613388 497430595 500430165 307556802 877976338 884346061 1021879810 248774713 12006085 409284047 83497619 247356067 847162926 677677473 902272277 104948841 164547835 611362397 1063794039 750173687 860083197 747542625 76422157 283134783 1043629994 692981967 80024590 355158581 989001372 470383632 783556118 334330193 17388560 388116557 442143397 732417553 494756456 508013557 726848669 860175220 688745898 783344698 454038472 374966399 108221950 794764180 723656528 425965243 144779828 157186108 1064257605 101513397 17125947 671363762 544920603 1063663741 902154667 556790840 631242537 1043148328 289340 93015380 122982187 889751119 303777357 415886418 426407361 482908301 635442014 837344191 759792365 682077701 316810390 57692399 473376665 579524569 212464959 196151929 965822479 792712628 150651716 755482294 755965567 985664577 236042682 773397061 889433469 208505778 686140244 571821706 278577792 55911994 191388909 955592746 303695972 980260499 314826754 935126417 421669353 349615737 899546421 414786924 887948338 840713516 441790156 331515183 781084998 175193586 356723503 242931600 993325714 854965907 251330414 881629962 375907173 166821340 310950328 938342491 71932787 186044956 62170085 958255367 1003886931 197314474 1027542510 392584658 958663937 524044125 388180079 689659210 933460573 586337554 349597484 467259963 341666730 851553834 998712201 1019859513 406205456 86896649 274683664 685532186 707576346 799321752 1052837359 621604472 697860664 314544836 646627703 513914419 812372286 780228861 307358367 325741805 1030946531 513140664 363363454 570412941 110288963 1049916909 324626133 33936573 856486494 909918618 732526723 610921324 1035570327 767120958 311941646 1000589645 1062118197 702538590 236820513 737462613 546937317 275620612 477019657 598301249 885138999 340545595 37126198 458620174 998949405 164474260 14546624 1041912702 193932911 586062756 885286880 970997402 612730217 328580996 461742706 932908331 696180011 500414800 37152890 998849088 52656696 102951592 463956380 762428331 704123383 799493426 1050627490 149250179 412818741 544233750 203575034 897630115 637844130 766933888 1034806582 120141354 130457936 270245154 460881802 642643450 1011655479 535640239 447926097 539534393 488488883 962658657 600351368 519866323 421086724 148380020 10440274 173590517 381224909 1058887849 852797810 257079955 1045535637 765731524 839063252 281920228 743518026 181161486 301768709 1068777441 192932537 505256403 286203829 456919753 389997079 344667365 239172668 421823903 97196155 1018254360 664039955 905460138 444207713 722884804 4386391 759825909 536639529 107644742 788691273 435641805 177981590 1003081087 339816657 1046976326 41687888 452401492 409588470 885868982 366768994 446840620 303978599 123943992 324215228 77820021 343613173 816768042 202618802 171721247 626598935 62911407 1042909564 5948191 461885285 1014003758 649806004 64266989 622021917 933398737 1011384027 95086599 897579169 327517447 283840468 1061664364 470570743 936436483 479669351 247440930 32678216 100961851 794545343 991013296 279306081 833476073 195005164 543556773 1184309 10546061 677713250 72307215 215969369 859730281 461975929 302652164 380511879 347019524 738250219 1052605725 643450396 858214824 203203929 364437750 473406362 2328292 1002893510 750207151 106312486 413986570 314780186 1965678 515825930 898886066 854580896 926599899 833903668 62123573 579080584 277257123 737405110 607291955 240365158 904114677 284463684 348155918 873008050 954151176 422049465 1070994796 879459654 921617555 943169683 888627641 228194019 632543059 189428082 150072482 1028603564 121166217 792632477 505203868 186593193 103913337 1055732093 345666907 985140293 977084396 963196447 580232795 639754448 337951407 272617911 344222043 1073640959 840560402 498599704 895885532 1036637031 469342826 51609404 520365734 706368005 663361167 785146818 842201668 517979833 79491166 181913963 923762563 665062598 837496377 317008540 624970999 197924948 404399746 312373728 339249783 13990127 255452707 199529571 326328219 77063173 174073609 85343351 716567109 528850795 739366565 1061815315 38794517 250282968 41528426 345096015 861586931 388861801 732909649 1043814122 1073355913 1041106972 569577816 50311876 865880263 753282645 804236286 225129572 725057885 988413788 217686217 703709555 93209156 526845916 558865089 759619134 996948790 201770598 844752370 43505721 535186993 789159404 921368046 566952055 144481784 495769670 327121992 767751730 502803602 633714865 1048448794 983073097 325913033 155524683 209182592 1004698813 129536428 523548312 610664475 451891508 220347150 513294336 468597647 889716598 431748612 277732430 1000307461 28293874 530618987 713945907 724614313 551785530 221701728 279585985 96836141 291156867 896339142 1070550000 371908421 247866150 536728515 537039133 991342633 403745313 28033859 1050971270 862535702 497006231 478471028 816806095 309172173 395466828 136350536 485946752 471395346 67160874 568409846 778623364 155714607 222237118 623976058 776836524 872755311 404365244 734454800 109553450 734154915 974689399 367096509 735189527 832301728 398198122 445281478 805575661 479744190 717215922 1070959159 1011686925 636016731 811052945 991987550 863438906 489103446 1064558828 961725261 1009154844 77096852 117179341 253621851 857252543 359363455 873794019 289220771 90577169 737642114 5990909 347484291 851564648 469821071 673569427 387531039 934690297 754119577 147135549 247400668 535436386 1042566681 650433594 587980774 6151713 320179597 472545003 212600490 430651418 129107701 783532628 500757596 575040533 747479893 236636322 848442738 951917374 187156021 978455199 149215783 1039640739 304563236 298263104 19264761 393751481 698378545 128023832 104114475 429585112 793677680 33597154 498813252 433395131 450446715 541107195 543982990 687314945 168821998 691493861 440871576 896277422 892270826 561124293 315748277 360096682 186209427 159086822 1029592443 964060737 899529106 68500276 289903684 102870945 95727252 612218818 171219632 382424160 130131401 615199557 273914913 664777715 1070633830 59679894 144650046 669272888 232264739 190025524 219806833 876205805 972596157 1067380159 219282537 953779766 683500405 869248126 358532760 1004027163 928641168 155104218 10612662 258205448 1072515797 360645345 260503612 738449739 96488210 815716805 688081642 853231002 159689111 727970906 43436866 400899210 93852858 764368027 814412810 876101657 306239313 1008508197 506627534 4482597 837717819 662797242 774653276 907250419 92107735 569091008 43993670 462033833 678440075 1032116415 763190627 883278035 892778303 313526503 146892623 499060962 828956383 239761288 917597926 231191208 571064796 669742999 169650125 9111518 130377900 2274864 379425001 149993375 53668933 649893135 685155046 188207338 554839206 150869269 649465521 523926819 244225871 132534473 397609982 447529618 897351108 913114836 353351619 56415971 10058766 1070019716 571933371 695370149 131034938 899727435 744435685 699436747 611318743 107000893 872866562 397562158 762848380 459835541 469253914 271463688 466513984 525565488 572953847 859038331 377692480 741706000 1070571945 107868168 655489821 568281819 834362624 1063232792 362649980 605592922 679106581 900222071 758503044 15019258 547957698 1027544788 672350563 1052877646 590149413 683019586 64464073 317022603 762637857 863605690 1037081963 1065437962 29030365 336591767 926138497 436248522 524442947 911746584 23220809 961046252 580454274 500020961 304483458 200763701 232181389 801363579 536147185 380025743 953997209 631768271 640435168 438950280 697697187 658799535 290773658 567103442 339340776 217588045 325143024 966325953 59112043 167873218 535750839 210549968 688190578 1052118665 277019208 719585564 357121289 851830529 818865407 945126888 405899646 930768111 854390972 38650647 153465315 838349305 195151205 1043808437 928386960 226304812 916160866 800383343 33516446 362912630 582221855 920859926 413564269 949452333 103594126 110766880 593164575 829075847 452090787 44719398 318123546 440480032 47938262 102689127 425473418 647737463 334020260 293395780 163197148 93572464 210021645 553824194 549984324 740119252 801374231 719997963 889690425 122063564 161811531 94776301 251888884 376938858 458274611 908329562 697454324 766678817 794394082 638252518 437459837 533971784 368773996 33221452 548363796 282158746 157146985 1070587882 546998276 804933049 969933943 215929920 5392093 439944102 34494133 607536757 836686576 609391691 58481224 216022226 588303828 220520177 711467481 2023492 365179108 401012938 441140501 934258398 538856382 241901417 34072365 604606037 349131461 727563077 405425492 178120323 324042144 746943033 1059652931 202845157 2405817 218188295 296065976 312177180 622482623 663476944 380232434 671669872 965276453 12128670 501860663 876098120 311510689 959906523 67452750 591259059 996118702 672025815 516140806 866505187 896113930 484411973 290947501 750218156 548327480 170448062 144619161 1018400266 200852990 394155837 526289315 1058395288 756711400 466710689 713599399 718439961 20030404 1068197423 762773254 681152243 350636581 124790285 908919332 286493615 883547360 94280136 563814890 321086331 83297682 890112207 131676740 36074152 43330584 993069814 275356324 204719404 718406933 307464948 779689086 408707360 197701743 467392740 85871050 216703299 1016817618 445205704 865670021 1034198902 1035517228 347535617 160766000 34156351 18311471 513273049 593918543 865167430 444148178 209323770 776685291 334479578 397029584 218552308 346876945 458340461 12558888 729748666 308068177 782111251 5841564 973052197 819500096 1035378440 870348338 599685744 730260214 162928935 600321718 659204539 1006075537 321981812 600795701 953099912 237329328 813127314 456925571 206553409 481617656 198256461 891324086 132836784 892660627 163751186 949580713 504898949 610109868 390566514 151677051 266984147 173128948 538446243 241408525 390888083 383677216 753190655 90148999 960823072 767111785 697828227 935384531 3412666 851660811 328785745 479540257 504644100 1044821702 268721198 544506977 918077061 960052576 703883269 364907724 303051050 561483041 951842658 216231772 912399554 906762325 774385656 345253967 714166401 191373518 213918492 571612329 542730878 128536159 100964423 560380078 110127669 114644322 11626391 765795948 57037573 656190771 117072975 824927279 379969203 1025136307 483383123 769712906 603078630 806531782 1041861037 762746197 621409448 1043654869 83648267 430507305 67414252 685268301 940769342 1014876902 496314626 146847774 11965884 679713710 726098980 173669180 154636831 152397800 364936941 301639970 52464804 445942206 788624861 136575818 360098733 179340191 346279895 230631606 855220031 10505917 974938274 409091178 409086853 224737680 452467563 915110896 849527627 67851857 354415937 1004690899 757674628 971471232 722851736 360321060 672946373 785991774 775234247 101715704 379417543 495671156 284508298 172608231 84343273 867195147 556058241 620257167 120456363 843439025 707700911 324426255 245517108 903059642 1062665211 692522893 686599373 648762045 771442866 362480560 634407780 287851539 399764739 239722279 629782026 636493147 892505986 615904800 252715894 573740025 1061429670 32267985 777337983 535363730 38695499 182622195 981694118 236391826 401657905 750436162 71302794 285898150 157695099 285104127 199864945 177885762 432155952 971121006 1071262918 174651932 942858173 109378903 581197461 639725487 440417138 523167369 424983057 968417209 1041024000 160659283 565374223 263139261 345218050 621641737 813673352 827235458 334239601 249900421 934709787 518645907 830856749 780844963 348940424 807312061 74063483 702042052 653257782 471157908 259936130 22161229 222956207 700319981 868156365 342369829 222209055 135608933 176507852 229751098 548023768 241215961 667101267 926015740 740584656 611290348 71568665 915720159 490553377 316384389 267318074 829515998 817953672 994601806 738425782 428361203 552817127 950195254 224076272 553889440 1003769796 660805872 111869487 381163114 559736264 365598833 985634849 711293784 700416832 472237430 918767955 418536568 866828447 487105787 880160698 11681883 444865018 764665029 74788909 497142676 346896778 632312282 544606440 765945660 968970798 408016644 629765131 1020491633 819235303 867593041 911759897 429957586 112718938 161810582 90674297 825500677 741481809 1068433895 123027449 328972850 474456890 661746208 219750214 537924997 712368550 1053833824 105221493 422830768 955427788 406524041 726040701 559145062 384800516 720149953 262249402 514196961 114840908 187116788 473420396 126630237 747708358 175761743 830609974 382703259 599339320 1073360070 836087200 669336927 1038766219 948690575 866115221 992731122 687237964 253288869 464025829 573303201 1026244654 752292679 525481156 332911931 865048966 830921078 785955145 684432279 69539790 61915514 127020785 1066361356 740690978 149466718 774857241 148025592 474473158 101455727 284751239 1001372218 251239838 662918849 303277282 837562295 111468212 830408618 968759093 741714392 871039671 406582597 277856625 1046781450 65751926 4036848 565893352 599582013 377199208 647309518 625694162 992596582 476887847 823932486 308741579 729962750 499793393 649419906 428781139 801555328 672752166 261029617 115097421 190970351 613978317 1029707718 205723009 644405325 377612047 1001035383 869387546 299406629 21450937 670715454 972039208 870037506 920007358 841249947 262204703 469999605 232105395 76001232 79597911 1066179092 1072119890 340735332 440476554 496895989 803598840 430831777 1014432345 193467959 405138726 807495958 625740487 688227066 548839940 514867477 646109884 1014690914 497141977 137225270 469345155 926277400 891944084 57953746 99126348 565214408 772531527 464097161 186819755 801919652 633270950 947773373 592635672 1024837599 783558284 778713108 692013933 822365235 379023223 921797626 352905579 188190300 344724231 283303708 510143285 398115483 527607939 143942639 116592595 188905780 740533075 673712679 206994864 124552433 330493319 264901952 43656477 117600668 564892239 904860409 375485132 842402440 173471873 261614035 925307477 451178761 150220055 546109334 696385716 550748919 637484462 866205645 23211721 1039454512 627942152 989080133 72463319 983688723 485342090 405524882 867405830 165649413 841536958 213574026 1057488610 228377584 16927442 303793608 505731545 49437631 701901080 437577771 326929088 375493859 129822341 922042196 375164495 538471121 247878450 735505707 623478432 137152898 306062301 618442074 1067769268 316621809 854174825 393565137 153581550 349854369 893858393 177675072 317027990 259183125 1070661465 117703584 237832791 887527765 20478902 797491371 648500674 346013808 1051449569 20527199 76865481 795836148 168938480 1001787775 923964996 869419640 541808669 828920338 106324080 573537554 796109125 1069780450 770687339 420940769 86015594 797287678 1057589945 159665541 614442033 1022726712 715628226 320557218 87752549 136694184 870826833 141181537 947201906 758196008 172131351 455763183 944476395 75361494 197764390 813569532 494225412 184209812 795387255 489809212 1034107672 845258635 388419940 167492329 834671909 427188900 174286126 1069354560 70363211 742762254 404275064 465579008 118909009 745031611 555361226 737742062 310900000 557796578 173477136 860339283 718845254 808835711 387354648 364072572 248905844 486649550 725274135 749659961 772233728 836939988 897611557 56021087 116210532 266505942 29121724 984719430 759361213 655650016 857707581 368111692 943552845 383099712 645146988 783131472 415995386 906890504 1012785391 288177208 399982540 57665167 194677458 10372203 1015204978 1035320304 994272518 593052248 443225790 602236809 84446685 388022253 132659493 495886462 527926927 761356576 1011505216 185276724 271992249 259066474 370965838 1035873750 642046425 181507911 157515951 408232660 473701331 91005111 903840874 386429791 579989871 433509312 625573544 1071132654 299048921 462346218 831771703 986803387 82325023 54347201 321585928 306757703 458446775 49589591 389504178 454971858 594546422 41004224 1037684972 83589092 750063514 56268435 7096342 311649991 32637249 763373680 1069878705 971271946 194062831 52253044 443730659 745884672 433500300 1024821447 721293557 127402559 388001636 255374351 774566868 749227553 572937893 343842297 288732307 21733958 272260837 592084151 672529382 397489680 394857369 161941629 196846761 1054024742 559447455 831332867 542316119 984881394 71833013 756844807 58765204 614633763 647145215 719266504 581157028 863381547 139180421 302698635 957715953 735049410 899800243 113006106 912822921 945488225 555518424 373149760 212523677 705574600 635311783 188824398 648154628 543719033 836941753 706906521 101716662 431150906 406852360 355060218 166752081 725681559 191324789 415653452 481768855 565269086 1063298628 533938674 177470701 153803041 873588635 265609294 1068494046 496985783 662178566 221903691 778917782 587851708 803975926 664445396 497706088 632317708 1046393405 771339867 519916105 576855116 144510612 721683795 754424402 381258337 462197526 156265398 828643906 962145783 359559874 530451840 864562938 439303163 136051452 622369841 778229503 716369953 55072269 227847503 250361083 774237023 113434014 231776482 442018364 299082352 481525057 129275895 1012171059 760372306 467379432 513047326 1028073463 717242569 299354988 862621931 546437824 386430682 358482184 153068665 718184044 438129488 8262107 281230306 269740797 389846842 316848233 500162248 170911257 892255851 1007673370 40529103 384552328 243555833 228751290 329319456 508211642 165253823 362009592 363657192 13213759 437518299 544547303 271603415 228580941 648174896 598960512 175571362 553530173 465475045 265527326 800674177 709870350 581760740 179784448 458641074 444233953 33189212 299282890 219739892 974881147 633230656 75964677 91591693 667801030 266000325 372685978 164307524 1046697296 809163240 682418779 279103207 589918410 622131942 239836283 367908551 1009181835 589767362 877634576 390687927 240976651 100442306 890139544 943460369 67604328 136829426 305686897 242641712 450537444 596019104 387447392 370348535 977649765 427886046 584053771 232151113 833760500 591933956 446648191 997144718 516045886 169335083 69079979 397789749 999514646 661993139 125749218 585943085 352121329 225444542 432830045 553690986 684681577 383914162 254623415 1036565862 739658427 531561915 354580591 423949981 961939272 620982086 348448105 1004477712 651131416 228057479 1023997038 850177731 79262290 434996725 888968104 330089535 59231685 1016082889 906498854 705070865 36184930 441834626 237901662 172865609 71400896 849129060 172596134 247351035 276014487 797908724 139527354 998176450 916159557 509682557 831832889 182457912 1041032781 261090703 486442535 563922303 1003931090 522336635 424869229 723078331 285377824 619359448 527346773 497255062 282341668 214222080 747326478