1500 1500 433116020 46011514 534570843 413470910 345209590 203422477 819973003 206378018 294531932 584221093 376720762 789538315 750654111 653199008 900593594 657544985 800520016 445162594 76711909 122013750 885068243 120734714 816644082 992221498 346952993 448107109 990997559 301670430 497779610 126751432 288715126 930895629 25279297 823285968 196882890 370488886 879224796 16855892 576866903 173756727 601076984 953587664 963295041 204247447 459303023 716404987 861792431 112339390 14083932 938504339 234353139 899152175 911755405 903513573 891373672 111224749 351620681 734887583 412895179 849400290 714155366 701610304 632812270 739434662 377412623 829695160 109923547 109153770 699067403 539306801 282910496 152660739 345410816 98721889 356908185 657230191 667643227 71216967 769569580 681727158 9721305 856439071 580879332 773993061 759952643 324769356 885217810 964089675 912173290 150629340 666006317 478845007 852239643 151334938 70796020 82168617 981030097 33235918 191322386 532613852 572542718 326749233 685274590 770469885 425471121 42182774 427700075 93114347 113399740 49786007 627357857 975637396 906225077 60753540 749630457 518694071 385522895 487364618 335300097 150212536 637993957 1306413 629057542 342749951 152641351 699853561 424918567 986187799 733089478 468757304 518801650 158148547 795506536 56592591 928618432 73494009 98775364 208834858 19124707 64691455 258620864 646482563 40328851 17362292 707236103 642475659 388572714 92758997 129840276 723872811 95487885 767834232 725179223 724545426 110584182 730336925 424398987 388019100 716524724 10004816 856776403 87842725 168153363 504799290 144435316 96771794 578293298 95727031 305606651 597418005 160418486 416743867 243900567 200747336 434106158 951136669 843222994 822678872 896412018 825579621 399068034 991899902 445930204 124247256 568961679 409030737 707100533 993360665 797049836 276141608 3365481 506342590 363984332 24035195 11141879 360935999 120806988 441951529 456663030 278929990 39369533 617081515 695673856 135786451 817828850 129780014 86923120 513568195 804975237 835851489 191664167 56559622 680267742 637594370 33323229 101745772 46625106 740423761 95106437 696191293 16565368 950988269 55050234 233066052 975023463 66192112 594002050 948346802 360659992 50665079 227276791 400029524 667746593 922950647 535815975 338091794 905247012 475255446 704176340 562738600 163623286 895840506 619298221 696407379 533434875 652621449 798153150 432576332 245561562 745775938 128767624 262126929 549280558 183817857 495192980 376820372 102526321 89195030 325167173 463186312 992376460 404960316 715732188 512639405 180427314 104064514 850731198 85674325 579319959 407423890 500929276 595459596 303264395 972743848 291866974 689215622 477881648 90020123 121791953 723443209 688312413 103075929 985570138 237592970 286893785 333279469 614413342 241936457 274990850 792096866 705122769 119883662 197057181 273371308 632523066 377484494 377435821 335770615 315675170 956755779 743194504 669120797 404731726 46458899 641864644 696598699 588190872 119746292 639135173 709982824 695705852 179963937 813058752 533792341 417556907 952468889 867071810 884486600 194405345 994579011 676583465 752044465 114462672 726156998 25415772 746985737 103641491 402851592 82756352 271833013 212123722 678467207 940953809 616855447 577442457 435334805 165970497 165633328 407597448 657622022 728132504 103303299 837585958 393707607 489611992 107659216 346176495 209200153 992145815 393098192 203779163 521245632 145142656 170758187 247402629 23074780 917743923 203560471 425926371 853016626 327909835 490566445 384000185 121379996 107421891 961442641 556714800 125908740 127075969 816828599 783530761 707724824 772648249 473633070 101432430 262260240 581292286 300125277 471460392 573438100 693223468 527755907 94683731 838366123 698514093 194602711 861440902 468774367 250679534 139883625 174307345 578589368 630450069 558307529 699969363 590388311 519750169 109200514 568813402 499342489 926029112 204860514 59583664 698677361 678493584 161016094 813453952 259785869 461141370 137430696 685740320 6881189 665186602 632940403 845247311 363700694 827543113 559204565 832475060 78222646 551604541 6782404 509328366 34570961 417606284 209297728 624959271 937356453 318498242 46289025 289215293 97043705 251149538 348798957 795721065 929643121 362331402 461691369 41945341 823472771 599122064 727685661 830353959 264308665 360626063 528117621 480525710 40685527 939838537 165517121 971424525 491443077 24815877 480752890 526014037 442422160 542566969 3489660 232294964 861065210 49778684 521510257 958108915 300928221 722825565 606346331 83087694 85156966 68037699 125033034 761146088 519676114 852718694 444016398 783984778 65861108 972134018 117026839 106546635 764488907 282543960 77971159 108448335 307359836 411240400 634462372 749781995 953807368 490468383 982076959 667388930 540247066 356103567 478014196 693691638 78929131 936876878 776779331 16602448 857430929 901812365 777748535 377107042 754531058 221764932 13608172 820392166 46415301 130635010 779455152 810904207 413178969 709942662 919352542 720538804 121183061 406331265 322837151 927506780 896799647 304914109 447412061 289563064 661017675 777942608 983254701 592463157 714819486 612550384 609065604 424766766 514362748 386814138 801873807 121410157 461095421 667998330 794318674 507510721 798633340 573773825 170931280 64328660 136232838 942800173 637383816 109932250 201647789 960220966 37439030 98447435 117651426 337367442 240526850 778669100 115310050 76297902 223648608 682645887 688848285 832714211 107412652 55727384 72044700 761802810 29653893 533140120 282317492 823972566 40650840 80950831 250262743 64098471 997795842 386495580 6898643 635179657 496427830 61062783 447916974 386383211 12026569 565568399 723750652 252553418 196753850 691577053 181367672 420402457 226739291 870215956 253116667 186668294 778459692 325161366 800987456 808113584 858301485 83304947 632086149 751468677 16772129 882348891 668083499 14567970 121360823 527498494 502263979 617788652 588561276 950180952 4171862 600587845 368265703 580438865 853141262 565019552 124532270 34508933 985422009 351271560 757241241 91055027 390456206 388217284 416216393 191443661 196330867 127034229 127264959 680933367 731019257 144037087 415798610 399102756 11121408 537159432 926601249 365901738 154948083 367678876 168599042 11636296 968266720 536864744 592075160 673924334 101884295 716607429 560949618 87306303 67878989 170707210 30877682 310851546 558924493 447094074 502295206 755255359 426644654 629560164 288705078 157663911 626113602 704503687 409283018 637235009 241663118 188400618 3136747 249127552 556079493 24252140 260763847 524346213 561116883 852839006 50786898 663001177 569446435 611736515 602823832 489841775 782443725 633701513 800693320 341368217 933311938 155504877 949139928 359956591 637581392 237845005 370136853 263694993 942348691 779419870 753446353 36528160 967820487 609099451 285655711 523899980 633351590 546419557 900762544 194468472 251774914 951549441 709986001 821221348 563285955 165326184 163579474 198246031 799027696 816789145 539614248 584855985 972294021 341270527 944812575 462391764 579115531 167465780 726086756 373980573 946885649 332049461 263025084 914706136 941148911 548680794 291122467 574500501 947616702 44401362 621485324 199391615 995950802 331471324 873129315 411753108 496797507 36708788 609999139 148341554 706014285 2129738 733197538 530824657 343400264 530526465 993216421 922515794 697992244 571819528 149012718 497394244 903868988 412037801 264616731 845017899 813234946 555739197 272034751 760851647 600140558 893520074 812759613 448607711 77507750 685888927 860360819 426821608 575114067 470359957 575163162 133644703 472489694 160877051 664469359 815889957 543919867 657685779 590922102 94428462 82021659 592451171 591822706 985890646 4488971 856439436 683424896 670240268 264694985 955459646 283608266 864835542 701496072 96367878 165959605 631520173 634773157 26320423 58341780 62403575 349196731 486021293 196048277 821686424 646898344 860517635 490092732 43334562 370719766 933531185 137763024 452741424 525982355 729585729 438632069 382987677 586025164 122056965 53227944 850720148 930032962 189352561 568072042 484045385 285720438 734031646 115565557 920493594 612868420 26423689 982897168 962065150 512444981 31461796 636267925 11859676 891979431 126360656 55194238 262699196 912408192 192957261 715440619 290906898 922542989 6589039 673894574 361084504 981162355 579638869 64321004 763711669 768991429 484909397 100273405 907228218 71457394 68355314 680238164 684325813 94779002 515651683 646390962 459740334 547113479 135175238 471600010 439092909 114052245 379310599 554308456 26460436 572267859 122265426 317367333 347327199 128854464 843778258 560928054 110016819 275933478 625249057 726244839 44924906 110158453 826518243 804669475 34132198 894873556 484907638 718458010 989652557 559321 217365323 301909243 400189151 352540560 773509252 839282059 466592804 5336202 246106866 493053239 577604060 368372291 662936923 777447610 497226754 506715180 338375663 459759924 782648657 816141072 38521114 680089914 778815876 865039357 337275741 812948074 759912912 822183378 531406083 602081821 675259050 748771406 903991063 75448200 101311965 530016666 767246610 420421121 535352867 13353475 913474359 965473278 234242117 428927634 742920887 731468871 935642813 933812901 43745146 570807822 749953972 82266260 103414087 381286200 947305616 440689827 194234273 559734879 115389557 578156707 14333051 643164958 179444464 770840465 571129510 133272781 153373482 190892471 553693901 688726348 56762298 319684611 506715977 291004414 748612244 102153215 22473284 536771409 35966116 918734782 107579230 638436439 1001041 63509668 19722638 800823008 356715847 66473262 213074238 472105403 644629969 79923641 115270360 824074432 850764105 538916221 957347212 4137587 729808692 511041112 545380286 786570989 830725723 52096263 77575402 431854318 154249477 952565038 968625726 42731944 871299819 928721307 681168383 724817211 992230975 700891020 378156570 201463173 767364282 443747159 673568575 264510602 523670799 641355286 88585033 374434904 32787859 45932245 231088842 762596550 409489708 776469127 549167538 92731782 828565389 479259291 524586100 835331218 431824328 345728177 878063161 155640498 274449484 559231543 732974060 119196810 112638915 111130629 320659982 732519548 407394140 846744908 997030149 931064938 340616545 85615181 158016193 373404403 984063777 389105034 136000952 246069837 165574161 537684841 191317970 846655901 16944132 715904069 681987118 301284811 61632246 412566631 456925309 188598081 971798173 42415720 160311242 936953439 6062701 480971223 669472986 413456840 180232482 519019486 344521777 520849026 457151019 502537970 894253429 293731147 891643003 30254380 539800983 909733515 420455573 731118953 756389416 437399704 299539373 290892885 738684514 213687970 703459515 48126174 254802402 527774040 90541894 415113643 317243830 96604594 896084865 986716816 510061433 76317346 358252653 707099561 449682724 815403671 62153882 343936152 109134818 953796885 226706883 501452152 716046751 647162455 85087456 324952518 937078510 384626829 615845403 528279376 450831150 171821269 576405549 705633552 552111660 519463794 120747194 869355490 616068387 869348411 708588657 978646171 798182108 66841309 685745732 247864831 882244980 747899613 444317334 843896149 554212849 671024217 345348300 122775952 170703023 430435756 447728469 107781533 667578936 63573871 488577260 118410085 87911492 64982808 824043636 640023151 436962954 797307182 361894992 53031340 666655592 70483648 884193863 317354051 137324957 422455946 565218882 872086288 22871910 9536215 568498788 577084759 533076783 913847087 699860710 556296158 196799194 105530 516594042 864378129 63679401 5171301 835304566 4107244 922670460 511864553 496646746 359633413 309171734 858541738 265181105 828343677 929025385 1891319 145697728 918866693 424347264 563432961 643469332 447219173 425485527 64484471 24303931 958562310 978331558 576680992 367374819 27647103 576786522 883968860 744541584 492982274 889140160 579846149 349605869 664326971 91710701 846252614 23960384 253398787 704794351 141657840 81742463 486336088 143549158 79956542 257719132 567896421 643389502 753704816 15115593 68875029 818189286 891935876 879953690 649037195 321133219 99844860 676684298 750436092 983813719 273742233 95934717 725470230 853588381 445540585 389797200 797815433 291793199 266273935 903730571 849103901 260448126 837989386 187956340 403997283 917945927 445675472 824410055 413851781 51896639 692042000 335243161 870085924 436494227 67713202 519123119 757627445 167558061 48323768 360579889 3888131 322066000 456514605 729358360 28170732 902055190 119155559 678502516 46364740 237945846 582233087 895468640 498393971 272738824 83424980 754907606 43201102 381616803 579317660 457052882 433513441 123876011 644812394 303599364 560370237 712525595 675238834 170514034 732600007 723562601 531093922 736488137 898144952 987608526 465846496 926315683 889663715 437518407 457334551 936028454 527980604 39567637 684013446 26374574 164822812 767438425 633798531 208023913 1571579 65632543 665076795 435085019 189508553 162405540 738684382 749878790 874931135 266439568 920392823 460047493 990002168 451486744 196535630 740663472 291611621 514898477 519495506 33791688 952416883 976830056 969820141 332913838 868914044 506349938 211804764 33736855 126304714 845603294 241760768 127876292 911235836 759353914 562961310 100744389 921759453 154162044 850623178 649206939 420601611 623532352 109254432 263120130 75019095 158306413 3783601 219147067 673204889 523279107 252938754 478138124 352625514 75275247 811051961 221539558 581625184 22856724 107792764 707929898 868460018 349553531 835806189 632212205 108907444 398767499 732956593 883183249 552929542 436096122 532390187 973531152 59628473 494160970 89167633 987163919 652467382 92951234 58827338 325672271 468746692 311766091 803810394 821372205 387041337 467378706 42911762 968666521 490235430 3220878 676596418 211211799 352774408 364918958 843424003 314198204 763686456 428896948 49897804 169132349 717509421 582287990 995179852 629654246 76448960 84347485 469334516 581432693 29815070 528161853 907104963 498561761 839927944 563431708 319933965 226969280 30810414 215362079 48152152 373562195 218582956 724748569 437290345 423873715 89667527 133230699 738071918 705870334 562127646 787969721 727519035 132153419 222774063 722698886 761807664 151739374 659562722 231142179 733172066 689377791 759304032 492793381 187939551 451748327 908741440 360389868 678717606 792068205 575751946 726869758 18146751 646851253 304134678 455437095 70724967 246318556 588667794 661313237 804705242 3311791 301799309 532224276 135465209 524573371 107439513 897272872 528829096 767002235 128415051 114517514 308896377 740235434 607310894 496835928 44500112 368568685 857225795 723217717 160636890 285494092 302603826 178783640 932345344 459254856 634220735 855586662 705573411 75404880 516899898 362795004 78716670 818699207 895019279 214181879 195788929 854975144 111454750 724618025 474493730 92386152 839135538 783390106 685137937 298962783 132742385 729638048 667531467 989968179 305372117 680684708 127978622 607975942 859468348 912840317 67230797 346205434 768426979 625320560 421610313 137843228 988115563 500326982 809058786 735651194 714508860 4847715 443142689 678479962 581982091 917636418 770866113 273633980 701026523 308520402 425113114 833768908 38158449 92644580 676253438 343530565 625845640 656748412 804022859 337830339 569588728 723770007 684035772 190532058 201606918 958162436 180891638 42238833 311005769 989950423 777890026 25514629 847314489 73549066 556510942 281812931 991185483 179893406 555446910 544728357 488413807 980560023 231013616 526572256 925720955 907267054 722619172 404082946 416531817 526642030 741913284 986120544 102928389 278465407 29168954 304535306 236627842 210060591 346774138 547633610 52527365 124664163 425664590 899841854 50729580 982175531 181654784 41915062 14585289 589618046 586643419 502999095 422694420 817657034 29571350 200931726 577440439 604706874 605014671 993972255 131348903 346927954 832609151 86793643 625393360 714294456 391328949 714537553 924355046 738103086 114687515 976882410 715283601 540352104 729240615 766013180 375043987 910895399 807928242 389629275 353029796 247088012 892628369 775724215 917261397 774716071 976655941 347218188 231939296 581670611 193706794 215804550 781114917 26315944 302598193 259024628 593126751 693927141 973562181 369998148 432030226 88249695 199396910 147313826 481118150 928637524 765843358 856162136 692049274 426287951 98307762 45079069 673375962 843452483 820803284 443153710 470684905 649975576 790371897 702624200 84162538 984078691 918428749 865277454 862910986 221026941 124302082 456037737 914954081 97864262 826035884 199500659 38630308 25432793 199330836 519748457 806586669 965174193 228426945 498635942 243978495 179251058 396231363 917354456 22703540 69550998 213024518 493388444 719526573 3396414 48528995 803689110 987475104 966957744 668966564 702902442 40501036 645784997 11456530 955455117 596165610 837492413 7472127 634795917 715441558 59319314 7060725 374544578 24493507 88004021 873180519 120988353 267255079 121928233 38342809 289958618 191479230 103883678 635863414 911005802 107280091 684392408 714694912 947271547 651350151 236177827 650173988 691851187 881962823 661630517 499822655 330644784 351639281 359811133 965440700 919597190 419130446 825017776 294141767 296140304 913021797 19838638 417128657 180276875 141766870 307987817 322751844 333246100 411871494 958615257 96768253 519151584 643007665 811463164 318939482 146874167 900157342 969113469 691241705 634636516 483260337 43580711 965281299 687415970 403391843 783238350 607013159 822522289 608256126 753671278 118662592 373794274 773509915 535791248 554071148 767793136 843779064 876822991 101039235 108166909 687954600 50323840 627318493 183478616 861787003 946257974 330352782 614460697 767887795 21594487 249097212 103664483 65175197 66894863 791080452 321083392 850133212 250609963 143605680 310905689 4281240 114784623 684699962 630307506 650575871 91287461 250616993 346871286 968110452 204172580 455038195 508581403 254496419 934873039 692060018 116283421 733647364 22412799 583260469 354051510 896523637 832357681 457715993 814215186 899252543 101312796 135298577 601902106 204439110 131420608 912807795 61236701 246205230 597507756 691544206 749297452 688795217 942161199 96168738 509422020 146333778 403723284 18003422 253346548 191112674 562579791 222146320 924760037 437508941 805406789 278811547 186548930 490280821 589043891 764115 242049715 690356686 988579043 843951820 894795796 972516002 756759614 956032496 71237583 206783722 500093054 820535035 748095290 294770604 769220124 110033661 293620733 25459759 128037082 546967280 216572432 543133224 769113599 141332468 980642164 427036739 272660366 167191093 917317559 861704256 20471559 159367273 404577294 861566953 3319093 151889441 834082954 612595058 107921936 905320537 671895131 460531341 578371923 419990420 607818296 347592046 530024080 901439028 373051804 510577513 300922659 589624235 53710736 922552610 583473054 886869252 349589348 856133420 54060344 119423259 717837675 927048255 278790531 122414968 788615207 134625975 126820760 475214513 599737385 87259048 233051401 271632515 547790388 811423323 544139287 8125036 11531720 74163366 909564063 237099875 437257231 63003074 826724109 343484318 985555683 262713514 82869921 187661382 118846933 136930265 307084640 689200960 916494871 438391523 664132279 557626429 573017497 790953039 32840941 25271233 878212086 118408693 296903748 278518825 782348367 841043034 286643860 793880086 767722751 48724275 30979960 57496333 111727348 710220420 253497003 949799382 972933934 336366923 137460763 944297218 325813539 297061755 633498177 242308409 735453277 150146808 799934838 160987125 941099846 685292130 186258358 819311931 656217175 335678457 97830755 438565541 29237842 236990967 84961979 796960592 285715241 968458290 706973277 397442588 531195062 960470279 199758321 356645347 296837201 189735435 300942564 622650740 486797189 786957093 717475500 74766817 937103900 369926689 88270294 878203745 55218819 274528651 550032027 563952345 610207107 500379133 2517885 639444948 737370099 939996215 288921891 23085339 908454505 995895167 273044278 292165918 808881797 472802598 648811264 105718998 662538033 949753827 580886089 1851573 589227271 150877940 76618390 526331170 520804629 17405035 257051266 428539799 291933685 659599644 992492143 754657143 12495129 847526379 246618442 749865227 787522594 535540332 625466918 548493450 383951851 751027547 840659367 45349999 76346497 341986982 3585348 738884529 144257160 584471436 593252453 733484431 735349376 522387194 112331952 108670356 539792228 369383218 537210154 831725912 28982861 529702296 438899406 41477989 229745026 685517847 643859568 17267619 73574531 121842837 418277420 457526381 872870383 111453138 502876379 949216879 453440119 506461727 540617759 597697279 943449514 133870212 183698061 531315241 508773757 296030012 639985596 48565985 665413229 177195749 732808248 546912442 559414396 171707654 440906782 789159422 857225500 937282701 658943392 930800030 59125537 77220812 240842762 784512272 41190301 596235493 586245502 347146772 102697219 979379613 944844050 898663084 965766176 128542110 429978325 474539932 277088473 69963920 375622268 942501702 99676021 108430516 341930495 659090416 132654521 635353628 300766189 989880020 572636329 959709581 773196402 484278217 889446744 866555515 121306840 930637044 462791007 560068694 130300167 418004577 539448306 75144216 169184013 357730833 56202677 599162337 832270764 185807502 521642608 60409384 128309203 473834980 168839899 322756049 132925396 301494419 958109676 286207936 143890790 383262356 245917516 769603543 720056925 135364259 636159058 841363764 918517655 951466416 253948809 48817821 221987345 793397114 976478389 391171357 3644298 885197417 990333693 835915062 71004918 364492652 896324445 51830472 838327632 917680695 227102872 823769379 71691465 37728900 109977314 215582254 273507607 208411182 985185797 993564531 196291792 473861206 687444647 967325798 277843973 941393455 868659971 499831317 587306921 697654711 891002673 590951218 435368479 733852717 279382631 358889749 98345369 28223427 263236572 789189352 945904121 490339444 465475082 17595585 380584695 427968747 85694191 654092301 488896280 70879987 647656832 685188072 397257544 187617830 505030221 675101516 129011284 373690191 27449185 716318204 71344901 918451857 159785774 359229732 652304574 439168404 718119480 603166294 467391831 981356051 244871997 413295951 324211846 562863430 283407888 704796540 990832176 369102078 358888841 332244808 292498416 859062024 17432879 689755959 46679853 374979451 217373826 28207488 748669642 244823010 744525692 672530894 15791219 904311465 31760625 668095792 195996220 602396456 123778437 663388050 583752507 221166785 76684001 907964352 784030214 212608240 465277244 627378741 581710317 824166084 959623548 874208732 535744459 829572778 416481042 582424311 204552229 633854867 610631798 805738222 731194229 207673841 330785467 746985447 964501657 215062444 267597590 160497877 817458899 391376026 823885926 253727757 612542810 753086278 14208461 249089375 965694517 479485704 876468115 399921185 156168139 836091663 274129916 691912597 518180792 690610957 126853259 722733020 176982176 737485056 380987593 908176404 797675249 711773060 507678202 762176905 926835503 775275791 775191133 744294401 19168168 451593411 998022158 631710977 57196040 12230618 880800351 22890557 344232673 609784817 275328093 500400811 298392831 549458009 192313407 816573623 92585317 319166665 391822994 122083844 909168072 772810587 30260247 706843320 484583646 390454800 321536577 263935500 165730590 96727709 8229900 184898757 400837471 858768409 669126085 458033511 723515378 402442787 333440419 67748050 12227604 608768511 420665212 310620434 10742871 612978618 127194056 103328188 784661634 371533402 225412031 693829706 144343988 108188630 253189377 481443985 498643429 427242305 745379484 516890371 376486366 606125735 701789127 777323836 317410496 223431564 235357346 40925873 625874350 568797764 961190275 638101953 30082627 234371838 801238739 40825497 847350456 780949146 144153684 484528441 152482547 222082067 30874498 149342886 330270696 284063875 630786870 681430476 711306179 376166353 198320846 87792544 982292088 752626325 717632732 152218935 976057888 952990077 45661159 601932237 374304193 6851433 92550542 404386819 93739623 893789280 445212315 941090078 527254777 441882351 278134870 679737324 663964417 309009368 829080209 994235112 593073242 312383431 528181939 156895772 688549783 726502785 97204668 523358222 331645461 814837399 675577156 307703348 620343827 721238315 762151936 847164371 580606099 854702477 104067541 674345721 601008108 549279856 467952150 128262885 991162206 746087020 660516560 507642974 55096387 342113120 354394437 500685980 654496550 882576375 510098103 195562685 461595511 607302770 571437258 793240971 274656520 99530766 100944318 747516699 820769080 715612606 594681069 253891530 422831434 698748610 780753603 23839542 100544817 101222104 4618778 944223374 847309123 517651689 451866347 754921861 712281160 806260783 108124192 219294062 541353509 618222295 414856746 2949020 78041416 986294003 796189990 205214288 85824768 749650660 952730986 759110199 317779617 399928406 865518081 740611050 98677015 646271683 616966943 51738183 747493786 474102072 995961556 447319261 991753760 300344254 54757473 556551272 959121388 15398017 775845333 500474897 633620311 43218430 355940268 564178078 29512432 4646609 769392365 967853552 754297268 722123350 579480102 72076884 122051756 297514534 665204286 73245122 943786216 282171228 977499657 543796354 756273300 825977564 843631966 600543411 126321818 898389438 9611034 937959557 913787454 785456366 290950805 399924116 828674795 646891072 964102194 710703579 651537681 586010910 531073482 258351300 160650612 110553583 182944536 135218719 260584469 848148821 60980192 56887036 130320048 38479848 600683389 739109699 864457412 296831706 192169462 843295581 47737496 201780495 633771489 961524949 987236861 924722294 213965417 668428007 571613365 30583962 379131585 75667397 616594871 910205066 334018697 777245482 873275001 516963232 912464200 133859469 365112052 973444392 43262856 347948451 864440591 643946245 939574502 581414354 940777950 131743963 277226286 988515445 186040809 910997775 802556746 25794021 835720068 869038514 694222028 259849784 899622475 925869964 335517181 368733697 688591382 669535877 998495531 414382734 39015460 763476082 400758554 404127511 589436825 444021409 604592313 453877416 87967653 544166814 35291769 881261955 528427128 165034407 722293751 566984289 76032181 377366848 592778309 764268600 98921713 139516688 24118383 998544187 65386652 212151915 219794236 606494385 734204143 70806118 20877118 773219602 834282199 421635671 29863464 423719024 865657079 634455777 730112791 806141084 31138942 617920911 539919390 559566070 782955317 114729492 126550358 858987497 344612692 571845018 475772448 443534404 563878058 352407183 294594943 481781061 564559097 514389178 88275445 151279592 585195295 109152562 924499193 271993845 383304584 954362657 695712868 101478014 588818433 278342010 760135449 619957374 896262921 152571190 32039795 679218237 267300682 11106504 390722086 611913373 435467874 866494533 55447776 999345931 71418067 202559070 481126991 635977164 716948247 421918787 787256755 154659893 383587700 564272299 426653738 766892283 518634955 974882957 720886648 959969739 253224967 481022097 432443465 2004239 633593286 464483259 681222475 753410319 328106115 924460912 217840043 763573988 643471797 125804171 762919918 714889863 328363240 96563260 203383378 45311487 518482046 990640132 52487731 902069745 407428783 331657820 521478379 926063737 306540777 94881378 738549828 412282095 575903474 170993292 414286333 62013112 487992902 95508807 815423430 816099016 872486071 33263473 579673003 515957867 11583995 195109272 83364081 339947234 144188883 286747459 237775072 662670928 129903942 290262803 417257024 537332724 621920622 791251754 315912813 780977750 886133132 54462640 193259844 314552957 77972283 607546176 376566068 565965184 555571335 44505850 382064200 280573757 930285674 814253554 796531623 941869668 9362826 879895703 281816901 6068060 19159513 519591973 668738988 149063455 662371127 938512363 686396178 136808100 729764117 2308990 917785850 468413600 56771629 111045693 782966556 134743911 571108221 12048976 553225447 979195907 56554825 935289646 259769663 986840498 602059551 908817637 781226517 463938728 641229691 63043417 470006788 660389204 435151741 138745775 809452658 97522867 929774489 495848835 86847319 512054957 350674177 4633168 980468556 259962157 968195212 763435112 247222420 391819784 775484087 800447866 371015690 684555263 588253863 483301704 523912112 190313413 392119340 305138628 654252141 33349031 220698396 124258928 546254586 508366489 115521054 355707243 458405707 897811894 704072429 545253025 409866851 54746605 549886192 242851758 314708762 370597756 6286869 561931181 762417539 634287307 214895398 133433229 171358921 803149260 469251284 695271032 993462672 861370624 409659 500231164 747236006 73624407 477006443 146006943 581990895 445043848 501714185 40396601 195372094 58302965 438165978 605238944 113049570 988052169 848090701 280274683 211166276 706893922 842205863 973583815 193697580 57101260 959533395 365056501 712766871 428784678 60327532 558745894 142671653 913253543 58977058 742424010 839394301 388499852 888430952 273901547 686060052 242661488 166814499 881432145 300964453 604980476 339187440 414014022 445548997 39794492 694288704 656715272 746688413 389010918 630299086 792902345 298628529 442348832 10475197 11395399 871133510 70802728 422657644 866321514 836572622 334151053 608745524 528483274 722650905 349692827 802384820 261227308 592354315 969199319 142659452 893318767 574179794 481846891 159849140 19728790 521641382 854137843 528960414 120846147 95665112 11775851 913748491 246809992 454124683 924223687 110721742 177774544 847542766 533379385 44096057 536631740 867530438 505357932 65115013 442697694 855050759 720016185 703925001 447405073 689215503 846584452 193240191 115911648 180947694 353089330 988156790 555105427 59743524 517117203 675951573 155408635 528893053 442216415 402218626 983017735 218956453 512940367 13308630 919015571 46319751 57404687 308163662 766366540 562762618 225795026 209064233 270329728 945811210 912989233 717734800 487543064 612090036 910974990 603454712 645554081 116580671 444127853 200659508 176324194 961245055 729127432 331732828 342654459 23860199 586467805 178188546 242816651 99408171 191497175 14348573 998244274 101418213 322512234 617127165 664180831 548307260 826191398 934510558 494118469 591696982 504761710 981661533 56303370 268253051 437632596 701857450 384833722 881760448 755033309 561157915 695521854 484160741 745407095 890692664 508020939 331874899 68881209 603353941 283799422 112894736 617702514 134560047 214312948 940214747 751687211 731010130 488522006 430394960 518037040 835156827 874608294 22798749 669334711 930911663 143568151 106967306 485285464 380918224 841244105 92835125 942076139 389282310 576995865 539999585 132491325 937533155 871874483 53888886 540887095 8190256 166783621 11105960 142750302 233612920 951320707 746953865 964623050 292359064 29865176 482660089 127515890 904473469 357975189 796850600 687901483 354059691 756334257 25703299 734977915 450094713 118538423 529570405 691893374 548050639 69569989 824384699 485583793 793960823 878273584 878987239 802151079 45057204 890093199 797417732 131186475 841413905 396887948 95809524 133772968 279269476 430985964 113805210 36259296 788961152 763172161 724160779 143020843 372022770 602380429 730515109 822117482 720918851 260085513 366527208 121485841 182171853 190911906 607069633 976132675 69185489 338573223 630800105 966759044 228666421 280734189 97945518 922596677 677622136 46271394 908885997 956891611 477257357 22691206 993150907 118734861 638379718 569828037 114272055 10402487 24724817 844787163 685036321 745643667 957389027 51563528 867129507 139560879 94991785 326715491 115693553 16693625 665288713 599010010 983452668 746471486 879744198 933914537 669068162 409882685 832702282 430470510 219290648 162475991 305678067 64957906 281210851 944057785 634785942 247999257 954460271 659510758 92786419 492012943 257670776 902691797 543576470 977316634 42252675 638568254 156548476 10462579 655261878 821837188 461988940 491230897 420825025 341733137 277661786 89893187 751615822 110364067 372880048 970906469 125356409 678558115 35864374 406567259 622615899 523166667 654566515 429592521 35193776 599869285 921605464 145380903 355077433 317698285 122697536 249846459 808782891 279246011 112825390 316561120 953599550 574814329 807792017 374424575 916547466 937970154 316834113 520679639 900850572 689714160 344102459 26206981 220788626 232483184 285290591 843404524 608166202 939857106 125513397 643359977 392242742 899635212 788740879 747320175 69849848 763954766 997166633 878632738 43200776 109992022 195193858 849316677 537322703 855502226 76257603 306386520 793472379 393091715 827066158 546839302 935322227 23684968 573046282 156110852 108684503 858336873 852031728 716850704 650710330 977545124 212727032 895469423 729696687 1467910 495305949 799546534 617939027 344988934 678179272 513656154 307497307 725889481 362972830 844820009 581391706 439230433 151206528 227380436 684838499 830789037 774219737 620160725 854474004 199782371 628787929 963158506 910635595 480819656 532525561 413862276 310881131 745252592 309331698 40577817 599236853 804637647 692640702 217175879 2142932 223336325 730832032 309640238 949225805 946321214 154460247 383133862 238067998 158183126 610514297 922906496 988972163 237250386 395583573 695962518 289549108 24371501 511637376 200184702 357707508 44162936 614046977 668588638 789415528 775895026 561682806 241168732 433049024 106839859 458344611 435191955 330176184 41692994 744832193 279401988 988014207 899292439 662535850 78598556 57475564 125566498 1505052 898964078 215333235 397088624 594926596 504882342 273976476 106563971 705067043 631683983 3243258 171630371 152788972 645175137 947525397 714471777 886343869 233090772 821311635 197204831 668282727 4004170 238897824 413114919 283406158 79428383 164923709 798458359 158026938 74915624 924024856 12048341 973879702 139358091 409136964 421322649 496756784 683113439 380402971 54340179 167313773 236162580 225970549 320102744 881337717 26012297 34574520 767681585 259103069 708402507 964886415 927385795 712406676 56300590 193017065 848329185 135728972 210457125 646787543 146272262 285372748 423328751 158320602 111768801 415203193 419973918 385607801 911959976 103087356 766010771 966300154 122917481 2173351 44787055 443020224 736027419 70799351 330111096 356225355 182418771 38513602 173628121 962320917 603436629 229928710 7854333 304282166 218174034 218311457 951069708 216962647 503684205 226914810 375283248 467969357 494634354 795257165 853577158 259110682 750860873 472104280 77927187 873778353 326793982 122714241 169314928 62821400 46029944 499426023 419046754 80965066 390455976 592674874 43285983 993892605 675119936 51140315 150691122 893293969 269451772 101760829 110256615 625652328 181191991 338056214 93621684 675826344 985829731 947198841 934937025 589206955 271819473 12864212 315501659 598613454 988094804 484816586 661434854 34124747 984242609 932997959 115089813 374698584 378189185 10892147 221107540 53309120 62032461 371798661 799119440 184000584 326075842 761892406 809652911 359784184 99948619 755790947 35610527 938294701 555506139 823063904 527501655 827325611 688444467 843003313 425939065 529055622 180336251 939890270 415696721 164578859 872888228 383302885 391793794 103593764 394195031 612901334 156902883 308743843 837216346 956022322 345260779 15808539 570431079 7430041 375592722 522896050 763220987 263719601 461190750 318727126 86783504 841208757 146052736 627744322 536728421 424508152 9316295 717064671 216914773 425013015 881643529 89803001 808315899 125953675 45913116 55027281 738855008 202815999 363771124 428587705 11354672 709031902 444396244 581785751 716461942 819988965 104681800 332199281 83708565 418388901 650926406 23008420 112114009 649495493 503269093 648842430 926519997 512585388 365907100 143434769 937598402 100066981 85754121 745914301 226020655 131667237 800941581 817392014 186999587 17229056 245979718 198354258 578777309 690375961 632656360 147755603 362881278 589854511 479954883 446589842 8243412 130881288 322114614 120357420 632893132 825383706 621716201 411929480 337969093 987623301 555364249 128083847 940206633 493634721 873998147 18743639 625301957 527456079 836135652 812301543 397201487 82115369 863172153 975978795 625007682 495828512 123734397 987888959 85683023 603689279 286995152 946442786 587086918 609109765 919316557 72496402 287009823 393549110 484425881 624978915 233688762 892306481 753062761 173895394 385941202 479577259 192639032 863759510 859549690 28774683 528577405 256751176 963406403 391749557 85246322 440930436 740094420 208980719 281335746 678293794 665186349 420847250 477252931 104789619 29957014 249085840 177286020 169483188 642634949 514228252 794462103 876323710 406534733 400041215 50219103 644992286 732134826 95374486 508751795 591684515 976665520 37329199 700952042 792588274 281595107 786198363 86035062 21689527 995179081 367370807 552499672 512881782 788218056 29752603 617671400 670691422 278838442 794957419 840174609 921473390 161702022 487153063 650313451 568236754 739710630 553048905 65745391 471845455 648423390 574497186 916046321 477605261 464342736 616998362 270193534 598454195 255713076 356228595 472660073 103408509 576115754 25159744 616290290 216850161 54912346 233961689 887541582 186267139 881435459 580232543 960256880 43137480 919901957 610570330 463890586 659612586 16135586 529635976 983974392 664558975 104133161 900020712 142164235 420992249 369535425 264874121 19446443 625248501 473619067 344622867 728657009 49734820 369782610 197463650 266584981 277211308 431425338 6642914 315994798 165377148 439391808 276251678 208514627 359293765 739338359 672405212 871422702 755473945 54557540 855397094 272549271 11207052 607934157 267229858 432199300 829985934 532103978 304162094 307750786 5723044 648784960 36407794 907974216 871083922 86387795 27075548 811581 517813132 33718461 316806378 683190279 473110269 593058055 744221257 684920385 184912766 269142821 556343086 940386710 323700360 264256531 212935980 334907411 724707040 480165837 767106711 554692973 864786166 923785156 862443758 723025562 425086468 751367903 630999777 296170389 837755697 658075324 296981969 208085180 544310136 613788346 743791810 17420404 59362753 488013066 554857140 244275518 757155886 111200226 37178579 80856245 227973108 250114558 268280008 952680147 582796747 35386718 359889471 447582912 811688225 74849580 23124825 236774692 678733834 654124601 385461432 369005882 164716276 682443400 577091061 709026412 148748098 173399222 578963167 60627202 661412288 133820307 304902719 271084525 97536884 342081297 204457122 178026343 444712206 472737129 983222842 27508952 360640198 195628664 327608216 24844774 270478244 350733040 261619466 949212077 4857641 647080897 170734311 22090268 182040649 747825371 583633031 183305098 921224593 15112550 243932299 435153232 1449208 548835017 558754108 98986091 743432665 763211229 129528785 188144870 88464709 112751626 68170174 301621258 160896642 395778389 326466032 431374885 746511428 588085497 233103313 603885420 87682745 403837623 625975688 122239745 4179346 62125070 305544842 777920290 77237619 549477140 65589873 78686826 98312156 624343980 30189268 694261172 240071561 159718053 882406042 328536269 124986030 950576215 630157527 285882671 198870955 956623558 569773907 945382382 397225406 802877220 549267802 337424502 59231194 27759841 459664247 63410539 89884910 765209088 693847180 167122529 314686228 759437052 245809354 265514735 383781032 275998622 959775907 623852592 288233026 694698300 804905212 413219055 497790866 287579090 551618078 696661820 96718999 121391984 494560553 493944404 776785555 43828354 831368906 836016749 924104546 143549504 751943639 13989456 908758591 298307171 33628336 75961170 57744222 131954041 341475905 294041605 407952662 153768163 917894196 696185687 700982814 575315760 961921094 51290031 862894849 513539171 747951850 959613848 487447506 95028754 306074603 264233061 138857108 137443508 952766161 915478005 133509363 557226151 781983812 42267954 855533321 815612147 118229123 913277543 947566188 312221379 59835499 208035201 465989541 977729695 756737240 19488706 405561806 718658333 70778736 268456654 84713855 818730585 80586853 572161360 913759339 386661456 688910772 905132798 376621315 641676932 673127154 510130678 51419435 455110966 552398631 906952755 123239464 523144105 672746649 923322003 835365484 732582148 131357204 153871376 562828194 740610795 173360082 968389999 311785479 244138817 89363004 396499333 62869402 169949857 821177044 829145092 556611312 510087816 586794241 933232626 4281099 112437746 443363303 55700533 567548711 848278285 962653288 543304527 371422390 487916288 466626529 59304225 220498435 450500084 213175600 783326628 43627230 386535681 604232978 355412708 630674498 693595982 751912040 546060251 863545838 425605436 227721694 420157149 935693251 814515934 205906126 792490701 926953679 649269429 848191234 347018742 350064065 663360873 890323268 721486454 3793512 209466148 780790678 224291947 512482584 993966278 860134926 556109813 233018310 464367904 911522521 863692807 10480237 515950912 409753057 874026074 941556347 637474750 146699574 729765949 304507035 352605699 522256650 83977066 1875127 222964235 283512159 204455544 738841459 26351778 925941997 742634970 235817925 559249027 966926916 748300508 405731656 679578194 156926673 638749965 143946097 68449193 354959124 6942685 584400104 764712180 880968758 378472803 254703282 27668331 108238751 411726668 380274029 483011752 495703733 234665508 705975986 779215891 439121051 297333796 805567668 217579399 39968766 893901945 629344777 859412033 494718804 35076432 538990226 651645476 526342749 535452674 720094668 881301872 542395358 157011124 498530403 275880467 535483926 605750036 303548797 496239028 17476704 536339178 979250780 365696788 771004685 537743117 144912679 62642087 835076913 802996698 132737837 875045678 549414994 762082614 586974062 44133798 649675397 125964288 695779273 28534497 513933313 268390293 909836368 908845023 277917768 260883123 184725489 813401693 866633158 340790638 162157072 736626213 877129815 141407851 102323001 500650851 679150968 99752031 563292937 366744232 755265080 696030773 94306261 304680074 310629738 681280322 201330223 960305135 659760961 897109495 988839631 26210626 18016139 751192351 935055648 295933906 12075473 119781136 961851950 731224982 313088125 124009022 320367547 190217939 117933224 422690547 690868789 797084191 374958929 106678077 16344774 130224008 655225202 110651034 287420433 965854939 791931356 488750655 926160073 451692316 238376502 767516056 477902941 256392640 518708406 265474940 404842898 383300230 237772428 366694847 967041563 550860552 343220220 287409109 741078491 461153444 562616007 284463631 110753986 937574935 243658060 127098760 67798943 898883261 237749793 207735727 864738199 29681148 696486382 643414624 333889816 934862883 263447031 811792756 43771874 782155436 77267696 448614771 17972017 167556475 815309618 985013579 718417026 11046189 124939040 312011868 472199632 687555046 596475499 582953618 477646333 840133558 710052377 397961627 591533170 947802169 605697353 308787720 977483317 302183734 952202343 163889484 89562968 68165725 975682239 133334842 850321160 905466286 581949612 720809528 73022760 249775581 558339459 643956138 260821770 683278498 955968005 733021401 223349895 404959855 315975018 700996227 97609764 26027394 98957853 689142933 826345915 557171558 997930653 656345583 859355291 802649347 820235066 948918259 870815072 648433656 82253100 573652583 406416294 516719063 294462111 331955405 766494644 852801569 975911542 27316413 388596418 931879547 760337813 464462664 189355753 928829183 17975243 286965517 807372928 116933095 976108449 633718842 526621004 974039101 142580776 238492647 629204800 962815841 39927257 500019871 611249497 122180356 73672453 17665790 491415770 220650915 202137546 257910413 925968835 178049088 137743177 167081604 962444986 898080990 631544268 151800738 679426524 649519510 438766254 486799451 618968956 267391055 973034645 145589960 93946507 115615420 384082606 723151306 78431261 424009862 75687528 542197109 398706569 1876333 412379250 890122338 222527247 614516795 549103 1012434 645082234 138292279 168094037 607527219 888889620 799638304 611844309 568316143 449157813 50610562 907631946 68126769 170517968 880666590 66233080 264464475 848798361 302832037 987615780 779745973 726841898 63303308 174459433 978064818 65179640 586838682 720703507 140223238 53871829 721252609 141235671 698954062 712061240 309329708 158997633 600950859 108968011 770841941 21783354 410642176 673968854 929415299 331285296 844486822 662598240 397518375 108951296 363912952 700350411 949083427 143658925 279708660 12386734 318118357 110289829 930082725 757473391 830993335 70305963 811345219 404762296 211541633 362815632 116823535 520871340 374329616 570290745 482355703 145171556 592074098 892997878 671656762 374005748 224283173 368659935 889120339 474317899 330127582 253033291 27184661 131727360 249208567 306893320 144114094 567326923 417183148 926713170 177316665 100692834 997019132 988661883 505455129 61077117 203993867 622278663 434464808 578323482 45085760 916820510 576011390 637159857 809818387 100184503 863681957 886617911 321360789 752802295 360935809 651488370 858351937 388120469 783215729 107560503 547530140 779846174 527403778 964713287 559075696 704720442 65406121 408611179 545898677 423377601 469688295 749892543 45656264 904153103 180732376 90742023 673489964 609260117 580418231 335824703 709444619 296616539 222442613 30805407 49418834 435894774 534810128 760287122 824015242 170542209 867847625 224061734 802904734 247767754 41291372 361980429 952488195 106697492 770591608 498386871 382591445 92796254 100795765 280764060 849465708 134044493 224022434 522955672 743304609 804440664 858780374 305265580 101057203 933739338 188587338 2992388 369634111 723397466 615795861 46165705 746456026 336159837 270227438 549360759 583927590 311518809 763857540 536415785 270732653 386965499 887319007 653324097 479761752 988114772 934088156 181743812 122159264 10626941 704699483 717980224 815067604 415996208 23245803 768641158 202251897 211833141 624149897 571886008 787746958 92462110 470568064 534202983 428621946 740795501 936080093 12549536 904830661 699937632 401481672 28079665 86903130 288800678 681403761 419181234 129431801 468008268 600925045 104107416 478635208 158140879 822087640 146219164 426653438 697849794 767376673 628905334 909682934 244042922 53307693 549946243 336505031 523875756 84149225 765126976 117187608 872745670 777676511 22018269 425199653 31674534 50097933 364619135 320475212 584018046 783800368 302423364 52026313 237241764 406530780 383177873 247898994 81134771 381913388 674552431 778984564 149290060 303457764 541183850 393332981 356765457 91130092 729838011 880641212 27795669 347481339 997828820 753057690 125157849 872363440 178257342 9348735 922461372 542876476 329823946 358995769 179193195 632247309 263538434 268951310 891294440 646716306 516850303 972429210 28629693 191402733 603930126 30436104 347376849 997630327 276285437 704142305 941276770 6123447 437299868 821588790 206121137 287645039 574646479 183795338 12524830 605420173 193144072 934986202 813000 522968017 146498322 180006195 7731677 410036755 448957504 899026117 56753060 965807807 723971678 937899104 9726891 180418155 820851560 357103739 30564833 97136996 913762395 971841603 955776794 203578615 793430392 161897931 491223653 220593223 345693268 503748483 826013395 538837339 291251036 826826394 914321707 437749357 859348940 922053383 847786112 160822796 673595851 757055523 126630602 250083881 547470979 988873844 283018387 220838890 198493935 313583220 317975885 112256329 285424822 126269030 315834943 931371565 288166960 659574948 4481139 486376579 15839782 830494533 25213917 307090817 509837279 792051975 597356525 221702570 566621710 297658988 382525365 92733912 54714511 361672318 342817792 454701841 350546162 625836179 675540730 549040096 939419398 846032966 513812776 77360571 972301995 829647719 8732135 112985307 341739018 13213274 599361885 357578799 696224158 477092154 664669615 58577788 269144128 114542491 280280358 835765837 412201479 662805722 928499749 319432341 24478040 123833892 774134181 227540553 602186422 302191262 629097000 394122171 740579 142909775 471482741 973042573 825073845 332731228 86027879 166812862 198460853 685389764 524391660 747201362 14998269 41577626 805779150 284142396 156120117 938575859 972424585 568321595 453897932 753440685 887753935 330892323 877274576 514404467 558432875 331977350 669112080 40046226 726099520 669852658 182956001 50098613 642895230 8029845 382829840 581439461 27359059 433807044 119345576 404267070 181008405 134343844 445844696 839303906 418486239 454481164 777879764 243427175 22802758 84294048 996867859 763073044 415186370 726658787 129993862 973619245 58636136 799105941 13665470 784735655 321474950 49137822 834834267 964370179 909684019 70180458 398325991 937043077 503987501 517671566 193826498 537512258 652015409 639671193 376816163 70501648 94152356 7212279 166445174 969471465 91506326 163313033 585060860 506692695 889971819 567571073 332828291 801124306 219193365 199010113 438376312 540668314 100664286 125726931 357554845 10348304 195907388 755880835 799907732 552411241 273552401 993734230 89923498 925567809 485921774 319256012 848585808 432590482 326468290 15030982 254578298 270490967 30860366 839639158 777183662 773348536 259726582 962528304 574472841 478919947 14054768 12849152 19588260 114719054 138576082 377143104 125067357 186999822 133023939 924975089 739411062 259092691 771225670 681850911 37176851 257147443 1106922 738279011 689737924 180091564 605826344 944316222 450582530 636686709 636471731 80282543 262551596 896198312 42810847 837024436 227634610 56865614 702389939 247222870 171584667 693482373 476882325 149168376 732998546 462422615 74143464 324925959 721515305 697885485 6776869 611208508 955032927 7883790 349487518 497287203 40491705 955313861 294119776 491074235 444516921 783107858 571356777 707068516 531822521 614167623 396609303 759457131 523549589 951515593 6680000 695134255 497514317 336078676 844302630 230512862 798501291 770962445 555438820 372532947 321364281 414732040 983741454 128913560 275132182 185745323 626200762 315623886 141059183 772836889 806698120 438092455 555944746 378054897 997677322 87767266 844738871 246802976 699740748 368288459 198318569 558937099 915939066 695832885 895015775 612758047 778862099 693517065 236236844 186817270 66050011 557601124 601549310 902307817 686514683 876681491 88053139 165231796 192305376 81628674 938068684 999003496 372237480 346529781 229574744 369914802 286813399 74313614 616717777 986554146 295118425 667552697 545491245 63573842 215901934 293023371 676331888 994764032 986540435 912568731 181581301 905106797 470169855 783130610 659930965 9200889 512328452 747984104 174432685 704633828 682129129 112501368 556153675 54366608 459031149 638244770 276797761 745844547 565074735 893515538 584915044 860193159 413584586 130406288 923767000 629486519 275946010 452615240 624250550 115002796 365183970 658348203 20109593 687870176 293995164 532556909 697071065 806323616 133057364 871503749 363473795 815186492 984005116 919627469 869553100 295552616 410388590 146350860 893913514 975463324 892382749 478828558 688172835 158483687 461751197 464456186 787970205 737697207 917071425 264737107 852700002 134771747 923085309 725325946 822641922 217080472 110399207 519712986 23404087 243456570 243733086 239394233 58643062 80254554 11538053 780712513 375807169 421926642 779579724 122237035 397389966 524478825 601065592 85562800 682962511 915333140 402535337 470932715 505546698 319606762 735669821 210763052 454378508 511271481 936088997 129536781 728351953 46488203 649249767 604272391 142461125 892982852 843666624 201104186 973237405 855204676 981816698 201560926 129647670 613912773 323797960 527037635 138391597 777379903 465116786 821354107 692713042 867652122 144803174 50776092 39775235 732989346 261539143 346670094 244260827 50144491 476206875 825129131 96632694 125456641 281917873 91610170 870955844 125584496 292714355 696709601 833305524 127047404 750786878 962953193 740960176 74584837 342507179 731868125 704481091 660140316 405738583 249710484 380308789 550541756 300486575 420084024 136047454 562025717 766754117 380308280 612170208 95477343 57953762 561319253 73450335 339871634 652929422 944406179 317972482 945643776 493632131 3794357 925207531 96935360 966747549 518684058 24036548 161771079 250552182 728517638 821911394 656290765 978228121 54736534 59348872 278714696 474820557 195396325 840740412 94091026 428220956 305426971 189568368 486174717 866746223 263018703 826046351 519675644 59941233 144018832 317835771 406089715 147813188 95559653 503025074 967077088 614243711 527061621 128848166 864795892 255579258 803275911 373603008 86323730 858012444 285468232 365038425 185349353 480864556 58295189 131956730 909085512 363722159 321525097 247776580 82984734 437060151 73822930 602660377 497001383 70358113 773012500 903091097 218171300 868572152 258632522 37764739 482815862 785694142 19129256 200128106 41273399 822405166 426247465 127597129 532933962 711715696 345151905 570799666 45096604 255963445 702756395 954182115 619685604 24281491 54475046 702670337 313857994 128297976 157847065 810859376 198656088 930859564 566466825 269343740 651948068 825099346 307108478 134763929 463309840 326237734 187408386 357099590 1159251 613655851 337213070 534093212 177887898 682364975 104892877 222984501 938328419 660165623 29682967 410530374 536963466 84158013 965717062 850821459 212455988 123564127 514197186 263628427 906940042 80664010 532972166 411404461 758279708 840080644 398684742 74105899 166318377 586093127 431205488 167477627 52265329 768418558 554087191 230153227 303299884 511496419 453137727 94144654 171662042 482820694 504675028 708625507 566978706 322908441 411963317 631951045 298988919 926160502 895579471 58445313 859340864 428551637 469849773 470136923 121148632 868534514 544242821 287467008 307143993 975448308 307460986 359409321 743866865 861548176 442078899 47166748 373044595 895216626 141311402 397222988 230553671 498502781 105848494 650048728 821411221 370328162 281999772 120400140 296488663 30095594 31361804 8345878 458647230 501211576 478482800 579795861 369746090 22725620 719779220 676890082 998173928 27240206 888815754 594557144 888788381 330894653 494240244 114349327 78627630 488067997 511572314 161697652 839087129 469937159 811746379 513014701 840265320 93746150 485931192 989270335 123841743 517292995 997616212 435005325 18504571 476099012 867317537 240767012 351340983 587096757 917657093 202031262 466853314 658989198 796588406 208158046 989883850 143345001 322507373 921027831 483929349 686596038 82725482 323016477 9049549 894471860 836031177 849314868 840734361 174478721 691101554 817092456 691771715 688717766 104614132 710276285 17333129 971931668 951043296 368674111 411544776 721216740 570705373 878398089 232722290 219810130 86556135 75122491 215671482 261579859 996150322 699600830 948175896 78875803 22617306 957225444 825864015 711164834 659056664 519114727 885643554 202674569 188723534 429931621 891392334 145854017 140207905 761241814 117785685 943767553 129915925 381846812 517500644 553137649 112761253 750222933 625464130 51833739 825345424 841135611 165929949 674012097 540736440 114105844 605404251 415870097 923847640 283784617 979551282 435420655 802899344 717711188 638095223 844139229 147642808 382003909 989993246 140367064 143245722 960295282 936650968 125677998 194658445 306667964 531331998 307419697 56890896 9312479 211769787 734752671 850448089 377699735 261281119 243700880 344321931 866685370 659570976 120685922 150469986 491638610 556106576 805885681 209349797 46718150 650024910 209508956 281238410 492534507 349876019 277000484 452829788 139043339 255194833 647488232 445711302 786526831 807424281 355118549 795839309 19194067 89871220 498803750 396893802 203668690 742504629 741215732 70354059 254591957 861901653 73340397 746230566 270524580 879226077 955580362 169759081 381767338 17605669 450997491 874301844 367481687 727997974 179647983 506525025 983192806 827136215 952236326 622235988 487076847 159871227 270591649 506270913 102258798 769395398 755681066 305927487 511900026 349413149 376281546 766491982 63831153 449621942 365238899 334355732 181364370 173335612 504114813 563131708 190941280 955112303 437433551 558422967 535626628 617081534 917464343 518819433 296734100 722217021 141055421 783810946 882088247 264163421 142598210 984347044 33558818 898279276 290274530 397975195 100208776 519072427 16983529 164039929 968694368 382222427 498395660 2575090 555558039 855026824 565706797 746499318 662655478 3140347 157438636 198282105 472738232 74902979 569617890 621988683 797119999 563189662 258315980 531724597 827353082 400914190 516071640 860911899 151709817 658862521 111403445 251918592 177934948 128386973 415958520 999145667 510609400 766870532 1720756 66167438 621897355 567427552 812666755 137069185 423084251 970105391 335351289 748338834 897524721 904969178 370327517 547161071 320675191 628643496 78885667 148028272 882074037 447473658 861456522 33783853 106336178 972859967 138218797 136787477 101246939 406693668 135933144 611856338 173564199 137653899 530540127 647977906 557597803 195723234 785047090 833198405 18344976 120398378 581537238 915869696 877883908 804381106 463030766 51075450 285540954 394432784 199103722 167614990 841906441 60560243 53915195 948242618 885936561 44650343 85030095 987183500 451344010 73479590 451556189 624908209 63649840 982096316 125402466 473763994 30335901 910449555 306962398 48680876 883364284 741015988 964550571 613764543 545397093 280097688 664839993 830938046 674530471 863943714 851069388 516436911 777020308 904984582 317195880 515473221 949634924 254742326 355173072 253495285 180738267 806729260 878403493 244388107 641341927 3805958 718152100 671677827 766771864 877630850 720358702 650136148 618646837 537425624 116417042 16560281 817523311 781257034 700014679 492053781 497717099 551084066 861007043 127253759 308584999 30719275 642726979 110736274 285461600 997900050 364231558 466199867 657145661 95151403 563104325 151003940 951473712 133772776 822681766 718245576 11403625 395556820 220898075 482566813 932982443 337315116 499127094 603022106 118572150 51658124 95075886 468805600 602742189 808599281 596059358 763843539 839318555 238786336 874579812 124780154 89202737 91327721