989 551573932 713056640 165431616 813550674 201812788 226816560 61086818 827660320 936381486 973713308 588612816 684710194 248548765 298363133 114269551 383909978 687925502 913964331 153367321 542594919 338722311 605698570 133558095 858106723 491682214 498191310 109384521 203124380 211241914 520470418 659566333 985218418 650921407 888888343 649867101 786430827 441932547 924156915 690384439 957346731 349023059 555571949 577247092 926619571 984164235 990180952 173148927 575159936 402720554 590577035 576413343 771456485 962580746 969022836 630730093 649949077 870708338 978036285 532104856 925314498 779224647 913172560 932982756 944975949 232113463 681315055 506412922 795346942 259852268 313186996 736353540 794696708 286553511 979482527 188644483 497426488 330620406 500244699 819095144 940816674 145185725 450145662 665732087 779953944 687487179 897693863 545260650 972620913 452517783 473331925 325415369 888992125 841683935 965949810 576293310 723816842 537211461 980821240 419499332 499116518 728848852 841080075 17107194 65568140 771268699 794052346 123024991 804083775 726394412 882669411 122908974 661348429 501103090 566939712 952349816 976219240 67819949 395003355 649889723 854221372 139771073 685406093 115890415 289977232 370798509 900673917 68944314 744399816 767047355 880756288 280755921 318258127 462362935 613437772 723835548 870546271 507206137 957228397 82420205 623864409 761559719 969898156 594673197 651561040 185585993 305565971 388141612 915662554 302104478 719088005 483702994 702738610 35162993 174799789 164780192 936360030 121882836 739443505 904083911 987369967 228586698 333281122 153135671 485866433 682593968 845056631 356431269 756827630 844298036 875188307 838138069 930044953 365751961 829205320 451397866 867379624 434003912 806607815 303468465 975377313 233617189 336481286 466965293 994732465 78423328 634414798 420714572 967249087 560806144 689397273 96389700 153743259 115495231 750267842 495331821 793018628 911438711 966171890 804468371 953904416 591332756 873624710 980080755 994542593 696223978 796710935 280007037 560685101 327534332 851988699 59335317 115361943 736939167 965877349 895397039 936964881 90652044 112925977 936911926 959530136 198607461 943014114 94919607 234277728 49938259 836544989 85976839 205741506 623967002 989212797 615392103 907285062 333046230 722786185 614658819 968909533 623539222 642875967 377273982 416384786 348352226 498844986 708520457 819200340 403492446 692982479 402016496 464216892 680491827 823472836 130691319 514000711 763004474 927762811 911632686 970348215 141292088 739903419 702965107 991171329 733254084 809092386 260127624 627909764 63555953 912821991 723783619 780759043 486419567 549109076 251258855 531710264 254353335 520282521 972087265 988681656 281440630 765921471 731838298 991653360 391328285 902026052 436996820 995134632 231058879 514606360 87525474 450383661 558380550 916614880 545262396 603714850 885618585 964134005 865442594 935502751 791822538 858653611 744450505 863801017 767282007 856347208 119154435 565210829 856272999 903120332 770518027 961174502 750439017 785815019 623413431 988726763 126068552 855517513 21055293 677995083 199873130 253880931 780851498 784048147 936029235 966930893 84063480 771657434 870525596 878786598 826395625 934790630 123226289 503196709 199044144 238592088 890296448 893099867 578884186 861661562 205848284 923544319 713745329 765853274 718020266 867900698 756364951 793001999 570835482 775040671 885515579 906427324 709826220 798853150 829487106 980846845 521304459 753941672 120524314 765947528 386332784 539673127 518411433 788205228 530841537 994600508 954921011 969967610 442151955 736959483 732453803 890027699 114482008 804305614 865235966 890139115 41064388 531851637 655550252 872976718 978067361 994504363 87821581 510580744 611375549 779200502 980337298 997833386 430935988 550388367 459337568 669674922 72070962 995258984 925795709 947185434 719072509 795120178 72564910 235347576 706432338 732390065 397793735 557074517 837806842 900043028 995107193 995379223 633557803 995358220 778847006 948291815 887008971 996265602 514420272 601582408 492872634 781588168 523116880 728880499 391898676 960635268 422624784 768566545 637352946 851404077 330022781 847477427 703688290 798566072 829235503 995043650 539002159 772723745 297167200 999151597 490348532 922271961 818759331 897023074 369602029 420917589 700085961 767826870 709502562 742762283 877988972 974313774 548499878 936829595 253732266 699140354 438113967 851777898 667622091 916024820 322440895 603784465 484960986 551035873 845556783 978389466 522114943 683342741 920253720 951572923 910168290 983243303 99970263 357607201 821094265 885853052 628752458 702781094 86545712 885777650 204313998 576154606 373627401 377940995 642076242 784821634 918148746 948077992 181052027 481151646 897933016 960624317 800977664 849595507 334439437 446447052 372174767 476637328 865530014 917633471 231531334 925930532 935404331 963517355 849386912 867666869 526848545 792351046 242811139 333156137 388413063 520679343 817897852 968751046 561146203 753817179 223747484 632636361 622501706 807316153 898088757 905198075 964610042 995892519 279310650 673915968 609178577 869307376 148075175 835783632 51481428 940624961 765200603 821512085 96812692 531870508 48787416 500525949 210168022 440061974 165170901 558053707 923954381 997889371 841137853 968633547 64581706 338552201 731630176 814981571 15042297 730959247 987472728 990228107 211625937 237204249 117679275 494663467 113243962 159536098 865738065 892748027 838906473 870040329 957778969 994223700 782752532 866380641 235316592 848221707 188234797 247306057 257941312 423926143 414866122 969601477 564950543 857544279 431412590 784791852 705757489 851913517 668620045 908327660 228402280 673142127 335405652 571777106 622883442 697795826 636301218 902773672 199672736 526224327 59771300 220909621 359389079 643241175 136890160 209205151 680504712 970692121 888203096 889845546 988599759 992147751 979169769 994801677 190504784 754113809 169582645 553176217 194346107 883124974 586788983 898847865 269766241 679148128 156692066 924708633 420674140 743807369 750658808 785586482 201562518 514737336 886040906 930371786 562552941 869621731 46538517 303034612 469133684 830632950 639327900 842397376 246981031 573773042 296338541 989711317 837119697 861159770 242024528 442346259 543892121 579297108 989126999 997508256 994633384 994829199 828318918 920913983 676722623 900514277 484372722 919415049 738324631 764394569 426338540 968294054 701417034 949174109 383996525 676797067 87181479 302918204 507840238 541316131 492369147 616213690 587739691 886726192 217310644 558845837 124107763 748254794 421224165 959269888 356029987 580788371 151078557 871737364 61342593 104439469 967907546 988196478 825655747 972722840 785701401 865220522 844596705 954202840 292842567 845518725 680587177 925795471 78233111 648496978 282024187 460880831 351394498 354705307 688855604 769254264 58712722 242367745 392228772 821723861 511248806 530683646 448791832 725802139 886435061 919923117 108498577 360111329 804766166 982393547 945165929 978330262 230406159 824652542 934291796 944810272 437217756 813656564 291550880 462185043 766882967 964353964 92661703 132913545 92695108 513297455 85722282 320277034 798993357 817810192 756814028 957716495 924889124 927065463 324715239 891878848 174136307 482670459 951686990 989605980 816220292 988611658 559598704 753114805 485161466 499923599 986069692 996991997 55828136 182699198 62657856 446928204 576380950 872307431 118444565 218190219 622801351 794620132 600488203 810407366 713118548 748707168 506168920 641244806 810718805 818408068 10691229 515893545 698009928 838820020 494731530 618441017 511045308 924879012 784120205 955424793 715475444 824599183 866773964 910723672 861693309 926926787 123404514 343149168 877273960 950044204 596845896 795495970 518254444 760946445 813979084 955378226 422248481 917936326 636248902 689658445 521432292 975662418 654447251 657143436 322757857 725883502 355551703 819612533 208074847 923033274 866895731 925807840 522706356 931486343 342046406 344606963 855172490 875363736 771489409 996601183 688088308 979924456 519607778 562488743 939066117 959865485 376925688 961059995 186945819 448135501 866124353 961079959 293859494 611717069 457596658 868848702 806607745 872734302 904334259 969930381 270202854 652011915 420891239 957689671 104061414 754814534 892873702 971592023 874452534 963138555 872773183 910887603 15375619 465027725 708420328 928753894 655262211 778610426 733618569 756841155 627714945 902367967 357991186 620593728 580660242 855694926 334473497 733925118 877100470 896485048 502547856 804351845 471931408 875798592 281659392 466635563 861430429 985972035 249546350 420428108 488445486 679613166 690131550 907684478 605844595 800355888 155167582 897644307 214599483 910132905 947645666 996667493 586828060 852335659 79568739 822048813 938630401 995980595 832223886 984621907 849232417 952522548 239784478 657303809 186808086 687457074 570076874 881344386 72481639 800923567 43838100 698683463 192696359 849339408 369967870 700820243 624687155 952681602 477442675 495876347 322432223 579843029 681155165 896604604 809326395 919608839 248461362 590801193 84619371 253245023 520369762 695560336 315073009 534944032 209395732 804839649 131100457 808871295 696880879 960135418 394446503 507418156 120302521 701834225 940314556 960841263 666027675 678646400 96308031 871769814 680295998 787653166 88751700 666876639 669856858 918801440 763097484 894630808 329681777 702763039 663356327 907776604 800975884 846737355 292950948 761396537 30896855 573332510 59712747 391105333 267481216 765587143 289897836 345496556 689048064 907201579 623797174 759527480 393867417 412604072 972543410 995036320 71094600 230444801 27732867 53878621 280707176 600240465 728870969 767629380 426122347 447379266 593552208 654598932 12717354 871958352 904455302 947600013 749005304 961619179 236769422 265078904 248190553 977976136 55782525 97327795 522076186 898141994 723042601 818452695 207475695 872819347 880576746 955900697 625200133 919255556 874294784 917120614 215806135 965724155 205571661 298260466 970090789 981390374 732169568 743551630 32830288 568306082 467407365 643662145 82398610 84765439 802884304 830031502 814456423 903669593 881640677 997154717 205425300 233009584 666096147 828561112 863283381 961930707 725009138 780635870 806719545 820698847 836607518 856450904 495438507 997966783 633826876 803385423 977938678 982219123 992609166 999079092 84824653 719416293 236678783 868379751 942974748 984085409 998664448 999689222 665647594 883112678 175164714 689688942 444730535 626341583 596349360 906279987 950591446 983942586 549368676 616099440 928131365 937405898 371633452 790525568 193457014 598093098 810642096 892073595 457784684 613460154 796872967 958836965 435633961 844503152 839482557 853310163 21308777 214124959 117529150 600079449 686004539 852412525 421680905 831185350 880620448 916550320 333122294 573597140 613790425 805289002 776739442 925252719 322560492 756425555 36789121 290957256 276597085 616705038 705948770 842371335 16843056 434436598 231339652 805857531 86527063 361438507 958092138 961010260 520481962 672582073 912552192 968919958 276983728 381794552 907737955 954328369 366022064 999240869 434920410 565752228 92765904 676559045 259736333 985835041 702087904 739944790 154600996 274210306 279379648 932237736 958360114 972780396 626808265 666508197 595860911 923891578 672015963 685531135 331020827 677308940 676464136 728082432 654124979 702686578 686851495 744457620 739444074 967310406 417078382 663285148 847465768 895456271 115223109 575153064 595018444 956905267 640142850 927087905 907861467 920534176 793833447 801981400 76222699 613968794 320132280 666007603 748706779 765933702 527085109 833897917 525668396 996058346 317756056 662966771 340381573 892125367 831525880 960237283 533039580 587788692 533656163 601259669 176707710 785715064 869482822 983106834 422990807 979913898 330280327 572182407 908774369 955011941 620408900 672352455 338686841 724410494 820814456 855023517 697163511 746950801 581989288 878230555 393646934 616531167 954359965 977118626 56731013 336934383 923050382 925694104 469621252 697812563 112723165 403640765 516110235 646532481 958227123 965002699 192883185 615087798 224964669 404207228 735139055 981162571 312693128 572347723 290283808 671666438 793234562 987120120 982337273 983673250 589230241 764621264 436050266 654339299 380180957 493118478 378045972 491095840 319410222 532483835 93967356 445232381 522568588 988154960 137158219 284833657 535434869 886698660 334391704 616300748 887593095 934704908 985788637 989736301 744772067 826120025 161426596 183436413 981079787 996570978 156871818 327764814 78482680 488447676 730239186 966824833 527009928 672498248 750389511 958889229 423645565 760177153 938790353 968287124 527502281 783395283 589316155 907268504 987151969 996194282 396307005 534875993 406987196 853595930 859981588 932356862 891955026 973555374 739973299 849992917 454974578 487343699 794293015 971819700 838207936 925027863 908531067 910965927 448723733 634626828 762974976 912616764 996018507 997129994 260976476 774980755 571111197 935826326 958670644 995572359 185632800 707605601 167382083 650290204 152451045 156570120 354781152 374362781 747666965 888307349 934683618 990973247 80476960 927433251 648715948 758230190 500616194 874614813 518279441 752151090 80373638 149195165 45106588 367145171 583732006 605705878 674194690 739500828 527180826 804016908 470959235 753570349 245310768 614136370 150213035 311943572 642372252 931719980 188025713 288571047 405361203 534588440 98824014 877533002 138597054 448266419 272814544 914181165 368543417 927162627 874332680 888636617 523685384 861410441 226453239 950339370 647587988 678554334 636717021 843844099 272187044 883776238 178524465 997663269 139927918 683226105 312883477 428063110 539068640 641949249 819802257 820588803 142459828 483965573 67447532 951338458 656020142 803446098 190525366 733609251 136842941 878486718 929607939 998194204 161580114 356756535 887356201 991972517 862090298 942191887 42985850 165676427 279209974 411302469 502966805 908317607 698738529 988756987 242008796 692006926 24474383 117703602 248249247 319527001 838912253 884934578 747944137 801070721 558277577 698114494 86301598 96993802 43963273 571289021 676520287 743369329 579015465 829419582 424122685 631245565 768686324 879012223 756128701 953398001 395558627 425786026 828778161 967395992 992151038 992444082 161994403 838916592 635308271 985530707 870400963 962381188 313937406 343211934 430613344 704625153 272877584 282730322 719846188 925663101 663844787 708400976 842848995 995026984 329615584 554469493 371329692 390078279 863402499 912399621 74503378 707131417 352735450 943095695 978756182 983640603 87116481 383778951 721564124 749521429 84220441 486539178 93571931 688063869 289796913 336025099 900456743 963730931 615869630 826141682 411944632 635779166 147903291 913760173 305573200 457883285 500509307 528625393 317700190 556194464 887415671 962393825 195550509 747724959 586369231 757775665 277389436 702660101 332229888 470093430 149345745 763909597 832219672 978100404 683117004 717538310 305552559 392227752 729091763 970809416 147137051 453726597 265276720 832719363 172695752 784729163 751271062 783957495 446799961 975250088 646299158 973324278 512766720 530577833 310822392 402300661 643137237 810584290 365397246 502044578 606266009 922527959 740798526 914031261 637294658 939871437 308412777 853395329 994878149 999796327 481102290 763709005 629128848 876263381 413352210 531875064 330420813 883248904 229837757 901888825 656787273 966625065 972185524 991459354 312300990 762384041 283018144 885368461 467449528 572373345 965719342 997493003 565007731 916034951 139796012 341002436 382662990 888365960 576085616 917606173 649838365 928435923 338487146 708961060 408176241 484011138 508505098 548997253 395066063 803740521 700431437 940107231 148428841 561725559 847911547 972801851 955373462 959355443 851576508 953190988 67213814 749501508 327409560 401785857 841546778 925842185 98104635 189834480 616081608 665104272 518551776 857473066 88986007 910420843 364753193 524154488 480593635 947685184 266990658 477849288 172805971 358376971 389712997 402053368 111447751 267583525 724793371 919389489 480689066 973978208 720604369 756632124 808099431 892061812 15189282 929584891 833053951 865953071 282720912 423249012 759632841 950961598 767513685 779208199 753914007 830570209 792052521 818093518 981565877 988247706 616974849 889237299 260443875 906208174 242520987 596361838 497389849 945701268 967210161 988385440 774346481 951355252 790982879 980961124 484699857 821722759 757568666 946787871 747708431 875432090 317723925 645414761 889157887 894470712 453679979 717681777 169146544 176626373 617888870 799384554 355251047 359338098 11271151 618569482 369214357 795271219 831528541 850483076 140955562 183032691 104818091 995137136 231790752 335040187 294397397 539228702 379104712 794460729 698201539 896482978 598745272 967453940 37234108 785899967 445763571 883096672 487859194 522893288 312632465 589960241 62347699 379991721 824349709 941657698 647122667 951459981 469710980 987974847 884828061 975703202 599715269 786355230 256410579 667266561 289655588 362075593 468130396 813390273 443730049 942613148 320437912 579688794 589021810 631510208 604559800 780628447 676744581 860812760 733351496 761222797 977293305 982189475 691875228 706179787 102321813 729958925 388385238 843917029 767612599 926983449 108292867 963308641 352027949 805555565 140036437 815191343 452567422 762211664 648883195 959984784 467778098 578611788 132229593 574615342 390925435 875552288 209597881 897445637 432579951 549266418 37285209 457452807 715474096 850143814 513449944 867303508 711020044 970517566 514982763 876428388 89588037 258279009 27049193 631754288 809228455 877339619 860768834 947502527 759358553 888614553 56723419 268742115 953032245 962437093 561761822 997072320 503562150 850589139 184819006 849108948 299877581 370739620 831145683 914411325 726683103 766772376 282005260 993517247 308242763 974424775 804482419 929785276 189456924 760662301 215697015 711365775 995907842 998361222 197475304 951503228 377393667 862331570 382869720 688499484 354348531 891208379 110283701 534323932 269327326 553383698 256530466 686893858 764356034 891759538 659994213 888086850 308938327 967403102 486262768 922711525 756541892 796603682 203783065 449991709 686200222 738659443 597554437 820682912 388274354 959653251 808644446 938832619 457401779 512229003 910277013 966871185 852952702 990106298 102426451 445182162 769953086 979551316 110495530 727584316 539980931 922954584 298312714 850423406 619868405 942100032 331292004 411580981 458942653 902550310 450915776 501170863 278159776 811161348 822293997 945079331 179537689 746433338 691824650 784978792 687252441 845628108 333138750 459056637 414559364 778938079 73012924 608831388 860293295 930068183 319964287 647678114 425076284 950002547 37097231 132764889 429306103 830609786 719104384 885669321 358595175 785447117 989167261 995292050 672263595 826931960 728765857 758234083 790820281 833437691 733261510 748352166 674354458 942633954 954780306 996265929 902531984 971260348 14249753 864045182 622366534 715802187 538855375 860416591 701085514 734941631 739016504 748163743 658233869 891485294 739282451 878723328 793433216 968890725 353256864 632957150 158076303 706946106 362041426 670101383 576461316 875662804 433238823 952159948 575856730 728122453 788540836 987654959 155279137 496961262 900356964 970944810 980789128 993416551 641295333 907055166 777694224 858057384 553474935 767173674 620999143 658218404 233062349 629741785 960056757 978017961 467049773 605910409 702751625 788484545 757506080 824663204 403078866 818677833 196429208 644216658 603887568 919936849 149093391 453541440 569000851 637313790 109565242 619745955 682390471 712272967 263566676 485457644 420937297 553302500 574964383 669859052 962728952 964688709 635107711 703415787 902879121 936764445 536540959 770199762 243797961 466993487 220043258 668227387 967231591 989693483 173255445 940905313 654838459 766680468 482873219 797326018 98140827 635632466 680854283 821950312 139538354 959462154 651017002 664563302 150980297 228511859 312167044 801554299 420513458 946479168 404199509 417291879 209708961 211897534 411472880 712410036 807989410 877042568 389257850 556788323 559969798 608090998 989376337 994342038 490131817 789398555 424835947 903001347 934996053 995931610 63448024 545524448 161365828 450720263 425270561 749366339 240736753 924671836 646003813 674637236 502401530 795047936 589978570 755715978 139574774 902246592 240464782 841285824 412622932 820737922 719565218 922842206 299599489 462654628 740508210 823626919 410815273 689589834 163998235 768312784 521439034 587285398 755587783 932045559 357993545 755069911 496453136 582478035 960399271 979392130 97137868 855982360 187911467 367273135 92037954 682670859 25390805 759866779 893809960 999277706 845293364 932027704 181833732 257813461 156802208 970102161 487193020 899849147 488519462 547129564 606341792 939915952 162732106 352275693 674028567 692751634 285106209 612194697 208342882 441651061 873126742 906389118 578617918 976051346 750452460 784736199 492999219 523694191 531549081 947473083 824432301 939193359 278677165 960558866 679868129 919957556 259731228 811248055 40347615 217733051 66686456 223575012 943635678 985118897 982556282 984741653 46979759 903850604 535203918 746185669 994598528 999984567 881055185 936668459 792351148 983180782 920651965 964421482 700879201 780644000 410475866 488697373 822633053 860414697 718562907 911481987 385442515 544604447 241508605 331821042 189612988 691614972 866375216 992920129 762654201 858314502 735945714 791138365 681818728 824881720 825285023 875642114 537236193 642742098 342378257 560033107 793098378 804673700 784400055 846060180 845481298 915592081 97660706 433857351 875268767 990137405 113076032 848884187 254126728 598387383 310460005 413402485 424764151 557744878 712321751 815539689 777379862 805596876 410133940 456164989 498853892 648857113 165848638 436420664 559791982 575188465 353359526 879766021 894826215 922334422 431843698 766683145 823897570 879619462 330808585 805017857 20450043 297397470 319413043 382221001 899688950 991157706 812658553 846813692 930416535 997304267 499261806 544236733 330572463 991789961 868032727 869754079 236292423 931309628 80297562 331680932 470354238 798927870 351625678 696280938 714385402 932668861 863052609 870545852 830576077 891012392 489844106 802594044 412362203 700141668 779267639 838059690 572808700 943147261 716455988 717760378 323346238 983964210 794462261 907226692 351995877 438693331 322793264 625249616 864107809 920224250 824480042 916347444 33952195 771422220 427592707 522489340 605614079 844566508 355519097 780451285 960088789 996266967 408085870 536949726 123979493 859141057 644644213 670820056 109803998 269214864 403711158 600080729 366711621 882229196 370785436 599902288 736670432 926064969 870599786 905168781 357024872 585872980 673593869 749133237 32949116 40642252 505926336 616939335 687602141 928605548 863293330 993023280 837617515 870856307 175471921 462671260 686287604 777852117 940077403 964567751 339640700 545387453 988183978 989721054 965241404 978250324 607482976 926057849 225061104 485238124 302275010 312646816 176003155 763494437 798701198 836290922 838635464 916934671 433273909 455069508 979880947 985675056 78796345 906262632 111944310 593283439 209933087 290916241 982723783 990814980 36847986 568704854 472791580 854961948 72658195 99178404 351420428 752128770 514323025 681450346 725967982 892574658 221932614 292072765 852434455 955055474 645163246 645739390 987857714 992817277 78977853 700136641 143025761 875346604 491747254 801735335 292974490 989373142 311913819 799877221 596818559 832285097 66395191 316461265 296252701 321653320 158433593 605819449 960611798 994921451 848944493 892234956 991910853 993280527 530399177 681346670 40642149 527367292 698643794 925735888 887994136 952655437 635247116 936521793 321220826 735785695 846119909 947762285 718822518 930639575 812387868 865833997 424793866 714906308 528333899 595887695 728866780 951151652 799015755 831686806 497401856 802669692 65397738 550698414 371050255 820977674 803357810 963469300 917168741 974285229 113834615 761608498 105883369 176861669 881508415 943469488 293917350 566899050 50625264 583627934 720573117 852210114 154111440 583203277 866130215 945242062 581476192 743324826 640935866 979978188 319608613 476561362 535631857 585634918 363937515 753834029 852043000 969204457 313089005 788099906 852926081 904175679 217983718 331121177 380969951 436796244 235192044 301230575 187257056 535701072 991560095 995975046 569719555 602365636 913028200 972010218 935525316 945269421 704750449 768456791 269755777 615976919 214502014 543783301 642144180 991068712 926489618 958660645 603174881 844491524 460328984 653240725 466852621 569932951 266976651 319885816 556421683 694001063 884466779 914456154 624843623 900330897 832638010 863648916 957616855 987431638 342788816 906732332 385120549 617363764 549369279 895069335 287952516 473025713 361050921 889701621 668770417 956404445 834770009 982722063 42145307 533830745 342421514 834743875 701300553 945820822 504716865 600506098 108731577 881356342 869081574 954427082 639006892 947187359 888099548 970171324 646205774 998199202 579818458 948704842 913063160 969907338 376815715 780030471 361559607 415445641 837953038 945008686 407987467 464241709 695505069 712140873 553966018 895587102 136887453 772047745 930242338 980738907 572785464 897754545 264769132 332788766 578547470 657641586 908525542 918827444 529832521 979964797 778729282 888362174 898468226 985638099 35702616 69353264 470092524 486606044 718825593 839484568 450929202 918933777 974515541 987638212 428564836 960396436 901062534 902654057 599525259 953288628 319828354 898609088 405910477 931438532 163962842 206204496 816845025 924103493 96591449 142861109 940218009 951404439 482219744 733014970 74381285 431470249 338704485 404167040 394655622 921977030 425955077 877529566 551688240 900400533 457780434 532645851 802154135 991346169 570674001 895324475 428513227 717589843 162574797 886300050 704167678 905763378 907669104 949678215 410902395 665715421 88076775 582211923 572467267 634372723 269156662 377958150 859767739 889301233 488577601 820470618 406602473 434259249 281063293 626048462 509257225 892261819 944974736 980400647 285708006 779701953 789374939 789559015 302414268 942909691 433277417 679186269 414317382 457659643 916022208 929780203 26230890 642423814 633554292 691260257 614283653 708832289 953847672 966171423 807612340 876005258 293285732 973621656 28298020 608811666 474678217 690110003 914840159 963732141 178456914 409313238 30957278 399426944 790067359 925772533 331309605 652939435 633820253 899041921 106135590 874575678 706381867 990566406 930247972 976465853 222496953 341313580 912125258 981122804 461127295 851732390 671154906 700140446 143134697 504678952 757788179 786309889 662288067 692943809 114556286 685449520 179293883 277135628 269957994 818328910 311244814 975674824 104140924 990216253 352526153 664139232 619919131 873182655 589335218 980898247 560193821 592032831 63349239 929249629 383277933 870852672 40743125 386079768 652499599 797040292 123621542 390215412 171460129 821152110 713904193 767839189 234505046 527815546 664451962 890145440 176110254 198805103 100685133 352213728 327977536 434361768 182236046 630847968 730948545 889903163 528798534 639615290 264183837 581867080 210918618 655956068 436743867 765300540 376634720 999632105 663596302 670330096 583481956 978242012 809937670 888065012 148261453 754681884 714095618 836571942 924575505 964455151 623732137 923705607 89228829 633343102 785756279 911604216 640422211 702065428 630041337 727311441 227085194 654422966 125725847 486246260 957284489 990674692 299631108 315437722 525377634 902865836 746473491 944177355 13074304 834294646 826280626 987274606 249525250 281547275 824727917 852638880 538690249 782040975 657981053 703376361 825250653 880899526 80768271 823249309 356662077 747521471 711359284 799235747 985988671 988296005 703790276 831069094 353586210 428364820 503188272 709883263 879903097 941452590 396532993 437427151 972631809 992876916 793451043 923628323 685951879 824590115 877450137 935619893 363390332 710656007 916453171 930335200 636784789 859364984 200230704 736243667 79806354 875519955 123845518 488520885 906267688 917410917 718863725 727554777 975354568 975870367 354759161 636294322 23315154 502773909 143916481 498849685 171589997 497901283 726988546 759836874 144883519 342063174 306073676 781531778 929990092 933698418 317602780 965127687 629516239 902593026 940246510 999572734 206080520 495782270 755192302 866891570 195856454 672957169 194039584 582524168 939395645 982167531 459850841 768475255 152752070 812310734 883845416 931662636 498072722 537832230 509457579 701745428 432079764 871227071 985359868 992548412 708941161 758243844 443449383 665325924 260977998 728497925 313295790 610664359 699417040 937816927 131614698 356835387 612934483 862153631 792959112 862973796 202486364 664370682 279112366 995096369 598107206 631796929 842031783 912831861 70537896 376352745 305605643 545539402 822444883 883043084 942507461 987650828 523326367 940170382 945799642 961973944 922876280 975909604 170931300 532069385 712262914 896825315 788016486 802649679 309846452 521099064 17611009 708579077 470676811 982810729 15399998 187848492 97540895 248470733 684364831 701812521 966471220 991549701 107812297 815974284 39943340 181883811 750273991 843227700 375835819 590757223 165465505 821716253 834463612 934565945 991748119 998757412 108019377 545286470 936209008 991126897 535066241 968575828 946949240 985220473 292085334 910886538 547897347 887204097 473165777 703755422 673438767 786078410 86051216 501257237 126074431 616165006 544375427 661494288 266005956 781786923 200081257 527573242 795544040 908261765 259194161 731879050 375189796 623683970 756103895 815635831 375633261 627641354 349584407 446361132 74860968 311564984 923748725 984718591 365445533 824183126 504635232 701795948 406273205 930966539 497170193 985709839 441421029 820455264 250243348 498826827 554462001 736112005 901464308 970244261 987163380 988570301 580381483 768087655 974391136 996439971 123984278 959930175 970902256 971981697 508262283 917580630 30414697 528150812 981798382 999293889 64761925 883672783 147605051 708388341 745116941 825539048 45579092 71610817 482573625 681459046 853416129 889561908 636608991 703872673 495581733 819930902 529093294 625918240 518002804 995830152 254179180 917846502 916766908 994624357 641758262 856010241 580559817 975354527 522835727 649059488 775311800 906290980 659632408 690853815 966638915 992129727 498028955 534176653 880081382 896711422 135089902 154021668 700884636 970184289 142375049 925834249 223545651 552087641 266402668 768655293 33769900 917716395 204502808 844104844 779363921 977219738 910749655 912117229 67696596 644379220 516769849 563320148 189917211 205324200 768251020 924304871 138740017 239621864 835189752 842985580 662379660 990169024 625541191 656158665 451124977 961007804 873359799 880530685 940123439 944264078 444898629 617402090 148625482 613061182 888306671 935887587 237263606 878716730 27869183 595358707 597958616 708660538 999581017 999810238 716518461 788652514 263777526 589781986 205135035 599077014 615964225 725318894 936381968 999411076 241538542 650302507 308562334 925982130 585225382 816387240 799497540 972061541 805973560 915927556 302735920 621534551 410824194 458842849 940350981 960072675 327214847 489462971 376185808 545698271 725610518 758303383 347495507 453005054 399462333 432819043 992667786 992772320 897075220 935822930 96948840 507808156 819702247 969166491 780264286 880534909 723485603 732693358 824494469 832374738 310208871 425599921 418939190 504142295 74153516 721650026 439212511 506209412 845897994 885681566 564124823 619489121 686082928 699917280 218851507 297345590 112340949 642441080 343078252 873140168 996446140 999671320 283300064 836698216 974435937 978644071 720363641 977611011 781673675 865316889 902864579 989174597 809577611 954985068 70717547 77127938 684810721 707622478 723097212 818145437 191800825 458158441 666797359 815075699 525790937 705591598 145093493 650370330 793591245 919506177 346179392 846714272 185541831 271889590 689743558 782308078 747932580 922131184 312409042 714715133 654985148 919553753 583195894 953888321 16808608 178319407 910400394 968988759 421221557 435622190 282013785 680955935 926512117 999000707 476736830 907994039 951285123 980605209 302432927 990131273 707737361 775512238 52980608 473911552 768490713 909721464 123750352 140170305 153045170 507757833 254447222 962161901 391111202 454763381 175794297 521826195 463703407 740941019 337995424 946401686 693197593 774186404 338384579 544841499 187665130 967498578 723776299 758376703 568192176 653239684 758950352 776182504 325134774 369764117 290634881 419512495 294377706 881885593 184144821 212392852 979183884 981316467 301591311 858455890 395033280 832918578 25079429 178631395 88246684 691377161 978166129 987780420 480949866 554394871 713738442 808042713 137669033 909079244 675979627 825079040 149675757 787968352 582461207 986839487 55730538 464423662 913462965 913578719 706797302 984706005 585034147 628987771 66601424 763970876 686186007 908766761 593541672 983272435 617222667 967073078 492829605 757840372 45809629 104266412 620907944 734354178 822257560 977592087 537411964 974635522 678004794 695499572 63395173 834044186 386187734 982753829 784549793 857762101 863209643 986119398 429697821 642805317 184790673 281572193 149057098 755332672 308675465 885332377 708688042 968938224 660854839 796244855 247121042 894523339 826789705 881940203 87083545 608645543 339814455 658617287 771746348 874754367 530861550 726544821 889031209 892811995 754292336 845935826 116689649 617548707 251621030 975752044 828400560 947179291 466208786 623082514 37528335 457154621 665858472 865677274 997127952 998096101 443246327 749859683 233384948 577425431 571828022 879415234 165151236 767280804 12422087 481594372 622953191 940204691 535747433 712770385 191886182 631534847 265111182 832616051 383011482 414578370 597600087 986090137 647352863 740088363 743637678 798408657 877695397 916851891 241982162 648445092 673952151 824132728 227775530 705491365 388630730 756879237 92337727 755982988 488045826 783803037 709652195 710517651 973763064 976363568 467111996 558733804 90494654 353968371 617797842 695116711 420699722 819433906 920809892 964435443 693994936 750925339 483710673 843316112 92216670 162330173 246997214 869267677 55528292 661585682 91976154 946807711 25325480 518482019 703618635 759774806 777344580 964445496 237305205 291463560 601226878 629155553 57729794 96539679 274991664 500008335 981055749 992364106 991490600 998033578 519233241 725497024 536744219 915574641 272571111 283974724 765659045 981053806 504260262 877884799 873847844 999894275 497663275 750911675 535729714 900356505 249192380 750054620 971556078 995405988 334639607 335340723 975841073 997132309 386701533 907452745 498740799 850516193 501568328 963513515 228072290 601255174 423337239 839502832 597817816 774676737 783677845 943204934 857476788 916559233 927095851 949855888 159972308 462196404 421599945 562579588 121604623 566034454 707681435 829436402 92197439 441653009 859914797 972176749 634284991 681473490 962422358 996741391 637020844 938312123 189307398 734699039 452643042 455284413 778182775 915858343 260645991 300022220 985737448 990720077 768357818 846770972 268980534 566706831 704070397 903649441 914453844 978875584 466558544 611489518 878505353 959201761 668492721 804766234 133499489 962249938 105644499 344081458 286245930 686799005 174741686 913662483 45045008 581278680 746732264 970344685 773539887 870634261 948674508 961614765 750951893 984407358 555275546 930449900 693293445 863643372 580481039 706013325 308996019 442709099 229904744 358997234 343373550 904598216 946979339 990401332 747514043 807587908 917381574 940943932 99832780 724861536 217416378 243397543 776790073 930958277 458390076 585557616 30904007 377137242 890507510 973299614 869522552 922540940 214791548 744796683 774113121 914943956 671572024 916967899 386440679 575423079 126424431 674471556 847028179 978557065 293207879 429404224 804317016 930712802 867128294 924364634 867592130 879949471 998402813 998895675 903267050 997590148 882709224 932676981 350068022 433270656 678684159 786636101 141575050 402848419 319869343 619053447 298013212 864524657 140880048 462563192 634586999 996019261 64113384 274720502 158731931 586751508 386967778 732044896 763878242 891155878 655848349 758117394 864036311 878384953 627296617 675863100 340210175 727810716 581477245 989948436 179963315 640115699 389135756 985531447 285865807 621474428 90968034 581658637 296945498 982727206 461016788 812458392 746990913 873012140 963208517 995445579 459139515 749614065 412553286 804732608 963254151 964908324 444875817 449181123 346914435 525892044 445508232 498174690 468353609 800305964 976823839 982757856 299493617 933003712 73286396 118760317 994400587 997128658 925060686 965181996 500825931 603568068 539058732 934306461 307760681 875267436 682179460 735021634 577926106 918620611 886634388 890169515 418900179 690252947 836304688 912943794 34503793 526424561 412936939 477414367 945899286 953777132 217032564 497581057 603160029 613545346 373377664 552616699 929201812 931271529 964553684 990134448 647844667 738933768 492790552 729590259 868812456 896678205 170887222 397922248 401290257 974632342 370252790 656190921 300839967 754547985 639743473 831814570 222728389 942891887 580357768 959513453 194789742 754944114 218867009 909569830 260643678 512456810 658761144 938999496 545759541 758804281 874683798 932233885 986207546 995983498 103508512 226314613 312080136 913476175 970480937 978282089 727506701 882983066 603740459 888814132 687204131 698090008 750869884 875773459 718453787 972855328 359091223 457060641 192073464 367040193 652345580 753325957 357528758 738969680 798000283 862871965 81817025 259827469 504230731 526440806 427597173 632209215 514876944 981131089 773267962 859685800 292254557 839986612 718900339 982730952 835827463 988981381 717682949 995394783 351359522 691826109 873233620 895978531 910001142 927659529 577163658 779702034 115689265 626485945 326419382 505222359 992159788 998831512 558380227 832995425 346123444 409411358 307745301 791128768 740950058 922605948 381605831 518482197 347996998 382982343 250619483 929299740 927400090 940138127 672854832 682264569 240525103 740348300 102089851 205195661 207596013 872914595 341175735 594463394 166031372 919038755 917544886 927793195 438708127 943778122 636054676 986669083 647724212 887356215 645774291 886502715 497730530 980644739 745166728 751025279 147655932 631161939 965342326 967950306 271956430 747790972 971390179 993872483 627986204 946424645 606379297 848920843 822468926 991740266 911937438 980101067 474242494 600301472 450905263 502048006 839332970 994955589 494406636 836510597 191647237 556255247 475743298 807623028 606719592 761669663 881985017 894910899 412858153 468791354 885864708 919677763 103423154 916377227 372201816 379326930 443201011 762863427 147621194 331634484 956539501 998491374