5000
885398324 424380923 69322770 73895963 361246111 166868972 134521841 261144870 325605557 810114709 6119143 666277975 747591857 142017951 173842549 404748298 691086476 677210502 219087178 693325797 395586589 771588483 681859377 436738871 982789847 767481524 162541238 33150882 264464904 235147221 101343375 993551874 732616597 135810644 205234138 912802134 867703181 176401079 170707201 235204714 815983710 790878873 683210190 635051922 230290316 889046302 127585954 673440699 722258076 731108402 510243018 1511957 170208263 641714442 410090801 850799069 950399910 612705331 424501996 217496685 642083502 172894110 615147844 917490467 411639114 781720659 901563549 385219102 532831966 871338444 797478646 335239507 869763011 860101031 559636626 813256549 804705387 352481792 746753337 595114001 724350404 900857449 620561277 365182235 931509171 796672545 507144682 369081079 276360829 145936616 820873582 661658284 609892301 153591210 446123952 90954452 61781046 2990465 589121455 959709793 367612771 279608924 587261124 -1115118 166190781 860216972 700695371 48029836 257933081 89208447 647954745 660017484 511795153 51415399 946319769 110076857 151327165 793726463 524312508 330393944 965371333 850487217 706956985 590474537 758334140 94040681 585905294 452938879 964333613 656251114 74944582 67844311 421042880 208045180 900469648 928557627 671935097 113085681 198954704 311642542 805060909 229610843 499331608 952825204 669257291 530199274 436153975 389379561 862349346 903189033 449948244 842063498 538977557 983308639 106593639 284003467 721293454 399945586 908432207 260094622 522785780 888462312 98821385 593947525 537100896 452611844 898211160 431225190 558064215 968117471 157373294 428903795 648020784 543291332 65444429 98368057 482314126 897642546 90018592 906606248 311997389 908376737 72438941 83601606 723321710 -4363070 644227993 185835541 302803494 880167680 -3871480 881051199 708721258 40338541 92373394 338681662 311519104 285673513 402135833 990811744 234167816 304578177 712742957 202904113 697687579 97024313 534306399 -2587294 211892867 776413326 325992367 839815481 352700165 393850778 798105978 253146284 23300202 8266808 663371952 813252119 508389798 668337842 287908261 278993477 31975092 807988732 41611789 383884709 820556326 537187628 878972549 114350981 296400267 261623935 58996624 986259043 104435421 392151131 233113575 381133562 340955722 567781336 258437475 728916318 847235403 475902192 692145813 138160776 660704503 698939616 808896094 24573027 160673255 492270105 300377804 727179155 259050506 209272824 195699599 211381654 565322834 728838775 245805080 680103831 417157580 864025821 308490435 184855023 749924082 893754100 809755478 254836761 399576076 930214947 739542999 869624445 522898151 313232752 849273046 962069617 12471363 731938501 803744032 379830416 436817731 287053517 602168076 5124550 717433008 867224235 627118630 684050261 994776131 315754584 594600275 582909093 979986993 460428823 379378696 171122892 264063666 469057431 193937452 769487096 166304438 212204476 269840623 573028812 244656668 90344817 467852666 454573137 347022774 332832685 121132809 645531063 588577403 960210526 909718805 721094137 853459120 862626175 -2890665 566531327 321625423 989699421 552458833 366483760 867971136 448626511 610120171 71302318 73518998 692697805 193077736 731724779 166599652 303633136 386393073 745734823 284346286 686617590 835771754 931213351 204349803 567524531 252396506 125755123 695521456 18340126 731963206 390994809 669052210 547303595 803063850 462104235 298232127 397533368 804981530 941301118 436771302 794752990 531304937 107357096 281767679 539667685 839330116 178362525 932001452 37536496 690241533 299953986 839217492 360328600 340276400 147886298 938678041 8925532 308507689 408080398 878698124 236368347 329565395 187379556 639362572 197770950 121158623 1752248 347031645 134249682 636578110 12366766 622528920 474654112 751191793 825114786 434699737 861108916 844547990 995207653 286270783 831695081 689699515 113418463 20098661 104062452 853719873 997020188 729803903 723334594 303984851 101834147 620496728 320869068 422411684 10150235 510763344 16453970 227879872 253166038 438365601 244167982 313390510 18748685 841382633 794150884 463631652 798081014 236002459 788737460 143853867 209653153 475528063 334787302 562792973 129953415 183807285 333667203 289397952 862472314 298770555 884586561 587251905 254220907 991224074 919575854 559233188 44014394 161812908 492178644 30521250 943000471 825518414 129781478 833274987 404316409 904545057 77465613 889963159 174097697 889757182 524794505 -2040260 230603325 509687567 547622574 603295365 928491257 382416856 370209949 676650857 148031420 151005103 173793149 853129612 658083996 551602564 994056543 207486138 925505942 242216518 822907115 857488915 857301754 173940451 863661818 602882848 710945595 525455938 885553595 332934498 103126220 274081031 781511214 529158932 458733634 652367039 620841085 442144259 512637981 902468984 809800785 576150469 195186648 500923072 96846506 589258908 576167022 232062692 442964997 879071028 213764287 968469550 219548998 728635972 615147527 734182349 189238039 709875667 321236239 841471170 303628968 682789228 454707818 830466804 431150655 955218402 217872670 708516744 903445416 635048330 460021792 518928115 946358171 302678035 600083051 405981117 28154115 220524062 492902069 324046495 758619147 335630830 898920832 713269104 204637889 498211236 172494461 88474461 538543909 638067307 912512421 543732048 684880974 137030578 527137671 427882311 908794880 890443310 113232160 68943880 761459036 65065917 489233845 417316490 248724411 226352004 233607156 562886145 724664101 153576982 520512417 456231767 875644935 391626456 720121693 987704109 30202058 243744326 996693538 714921275 444511005 64638818 395317584 305074045 638352300 390861048 903345739 241710457 248262040 572016769 334687943 626936231 405785959 546635651 467245153 538961653 696139501 760627382 791991895 34749008 801114265 747226076 530677196 625875531 822514346 508022709 368373061 101959706 570925567 714510467 535297644 171593712 104714465 104536095 124999550 96417811 755207897 334884143 372870477 798731399 403600690 948903727 325656220 199790705 220124876 898637703 840160278 615528034 371903444 203523256 119676053 354323474 514089788 502378466 610848153 794801982 188290333 923007437 2469294 611149153 814825565 976831586 96419339 819888043 582250068 466432317 5263918 266544258 839902943 722312158 149489747 702282376 559909085 366807414 55695584 623472555 858731001 42680041 679464662 558479774 756043497 924656452 189295681 729416830 381691448 116724188 476281395 452463961 994941926 226127478 639768097 417507242 190414988 217802465 222734385 889068810 699251335 275251674 973277649 974418561 799995947 367772065 842384756 453336410 739476989 319324422 550323881 895135346 846850051 362935498 124201948 158325862 876463623 748466188 868545127 794843680 952528215 66577421 260151875 299377719 663983719 977624514 111120192 872089784 93443696 382400355 356676282 83334942 157962547 318320758 88647355 251877585 558289420 610863891 433992616 352183889 585117843 253809056 832614209 525300016 804413092 199558531 723252434 581504686 592675567 81058791 168327224 986895935 472193345 978205647 802524483 183931916 259412131 476859357 432454295 43513871 520706130 580591247 912794839 428947957 667545466 9904037 712901755 592885617 217545160 318804651 518436089 538439812 284444259 975883448 976243599 358090950 536085944 946002443 505865414 794236979 292202676 153269127 861324719 916523982 86643453 395832837 140566332 705528331 682634516 542195917 41736626 950565267 568231162 888833570 802042802 325553701 243311758 884795070 315565217 495117636 729720189 60444321 330694029 471211244 941326264 364009118 363759073 568792623 586249206 554988706 229388265 817994362 857281123 529019434 343505482 939968633 15417698 941552613 94932594 638159042 149947809 986266708 928780085 477804973 660064352 428052049 197464364 338016492 908529409 223694468 648041288 788158825 1132029 821415028 104450297 654947052 423358911 435224462 573439273 300411163 705307736 685014397 366123653 247157630 391942673 178347745 127145833 504879733 256400149 249133590 387694883 560075870 568375548 972109277 475304751 776212184 444355544 721139819 809578338 175424254 71436656 853192031 254704041 992927170 654861038 423514105 42458875 541119489 652517740 779683918 251300437 643169719 587321359 666321838 488604180 175327783 100295456 135545689 700273185 683780436 309398449 95741043 183687075 475552067 909341182 238889314 255484428 418079209 123074113 482388608 136961230 473986486 782941711 127044992 830430998 566706556 60236737 759134014 284621424 689099335 777782625 691329721 938792906 19164012 399015847 163894441 75647436 946912864 585603878 455894119 143363870 18417632 205063697 585030606 723539123 655328830 163629896 355615361 117913154 856459752 962686278 29181071 531703146 353036542 453898034 84932780 962471557 551472839 12458636 596520605 768443220 851976893 370964071 593240854 858849005 42438525 425097013 888419052 955462344 30247491 442153381 622025118 525913771 888193203 195277616 958967735 68951427 713507508 260806289 904439569 837731292 232779935 899411467 541551499 648280468 669058846 823261671 733637459 982235548 32191463 634511899 132336720 35563872 609565102 556185766 668559163 59889816 949321003 164258830 945738120 360582574 809604602 753494859 891917709 241720127 227092715 294944466 744603533 48118297 529183791 973112357 473316187 -4697580 271311989 648385496 296841309 532073051 482885837 422486885 653031571 150164524 454522384 567786577 214843296 304863941 746275474 880039543 214160634 903075346 596044203 270528652 209039414 252937331 934698279 501168739 975162046 546000285 248761656 678859625 583980601 227908325 354508863 105916297 224098778 922242891 372816398 909530477 911558262 98302011 634371419 250139819 291219846 662578430 23927471 736342599 624023139 516410390 961902730 685461383 551973700 117760005 316469422 174634811 371303444 29652348 409725341 400059262 23311431 152089512 198114340 567633927 932372166 342054754 246577958 321062387 104592158 152839903 486927931 8715124 834575618 846774284 236650467 87259839 600077052 931456063 344381458 613821792 23371111 28303124 998084722 152968326 927160202 209323604 359708554 343380415 436527460 365967596 515740201 135596821 689919141 635499084 80960148 345683880 930889434 183891585 629133301 147900595 904776316 669983254 580594243 409016854 4376553 34789294 369232731 579976053 766518953 348377016 111661949 775552190 919756556 931397513 266305555 208870126 308500695 824144134 262847301 193171000 651624767 101096403 368926993 563883599 80825326 441129504 732667392 663292859 333010336 73734167 189558095 138281436 644021584 385134700 480886800 753396226 277449260 885525312 -1223532 602929940 901231654 744850252 271290914 446850963 482896869 366993415 300001755 363855471 986419178 380972426 380244907 569036467 495905634 19465488 304128777 131546581 547163999 611486107 17510082 163341246 710680368 689937628 933731261 13518578 276052474 796902766 612342940 908341065 776627889 590398003 207541827 325958243 80948581 858351308 734377255 894605711 949246610 681419571 566214789 989976280 758393800 773784584 418802938 771579186 313434206 382801446 501286065 835471013 719455267 277508973 199746536 276722660 622896273 544828744 224673370 525840023 175966915 775914301 574384608 388290983 460395561 69933926 33870422 42515915 56754945 338010351 834715808 938514834 38443115 79343763 69244076 724208508 355819636 813632344 924203732 231798095 252854297 547311402 903835501 933659441 556643436 567950493 791321180 786038527 84711615 889954598 355528094 543673046 -660508 402038695 246409230 342113831 378828683 975450146 402120138 485262472 55587641 75126367 439401267 321964784 969936804 491966305 230491009 330944860 639844290 28917227 800115340 855426448 807429683 849567215 608372591 616086800 39288963 806686705 728908856 40015893 212309506 260819784 166334211 864928972 800388040 142672273 481141441 446146922 821000937 127022984 915443211 395221684 88129418 730213415 795803656 929776956 609044606 121909745 814755652 280718830 62035999 973566406 702008262 450595229 43388472 815658177 951085954 927081208 544891729 530515302 65814468 119689145 728326058 293689520 711916236 298711739 508792978 611132080 327654411 357931658 816319780 125167327 20648310 213987801 549531714 331034663 116437887 584190362 271779372 235094470 219572339 246412233 752183681 191595195 349199701 563300146 974825272 912656045 139834781 806694448 802473910 975370446 880113825 797040745 948568075 240417047 666750413 993987250 400997595 321577622 854630759 745057551 814697353 320163582 357721718 618335235 387399647 174804892 302903670 689507544 199421884 191397874 555950660 571071342 212868492 406248625 121959913 722414367 474990605 313766147 693716779 335112619 250840681 35569478 53125215 686117842 73048160 24509993 363755641 373231270 698959112 770923234 756771608 894060081 280308700 668639171 411537611 904904935 622710788 316420464 395312066 307979430 388179413 603788760 762162933 953787652 211591916 996307030 916298285 540162816 849867584 986797176 616144043 155286704 797386029 331385942 165208556 791672704 828929784 980631011 917129621 681900945 172636014 377409229 973279165 205393953 866378104 798214641 416912745 727464751 88773467 893174679 861733814 948615756 911571958 257054791 282586173 18911918 218826206 619973245 470782604 671488666 976262219 768110015 276923862 107858614 703350592 121233738 626520865 491219939 967978394 6212245 772497973 433825791 522682898 638832144 87105089 481045792 954387293 524927650 493294508 433429410 315918182 983249106 478141294 777489094 476187344 855062967 434779197 612443341 376075468 619141365 65163189 858488902 288357853 138418744 409662637 668726662 297438520 -3508664 676874792 93252030 536118741 551094110 324390918 548780194 969001634 407760858 796886235 901914517 208633135 752715848 985944851 612446377 245415888 431173296 306186792 381865055 705901059 860191738 170256299 387921269 838483105 378995592 182348397 265017069 530315166 807378718 503716157 849003999 688784436 191434739 766632235 243683028 8986974 817480187 414714720 584609877 274303794 467769696 532968814 442820658 826278337 746552512 855555620 326623042 201950922 674148446 312752275 872216083 751796482 77022093 170533243 254851226 680725224 108179285 325064316 238624089 494177196 986874708 836168629 986716501 48311476 162767631 782978874 493744303 683034809 452521056 -4477580 164321701 619437618 503008310 190760145 458372613 99715729 215603933 763506481 832148149 313021994 292220039 928341185 198323690 566449820 231762377 148260414 149654737 815616500 17591644 260317413 553843120 545029514 67286657 210533033 790820605 995438176 587909382 727847638 442884571 395206418 107916710 280096271 297505467 975338179 180818076 822431769 406643466 501840641 595301226 319443410 581229360 791931138 971893018 720818438 440351650 420429883 297649756 290552714 266909565 376107736 990752692 944369569 588621952 521475908 447161120 63919101 494161268 446408556 777978346 702777230 884686610 479402085 126585486 883975382 157195071 439483593 869247041 264592245 663431981 223840072 956438321 172600450 108772803 867569272 125109767 966714566 403466808 531354385 432148934 27740685 100226829 350013359 692944834 689499229 670948306 428449242 280384924 279539004 953168749 491768470 523044307 507670469 826451942 700803233 11438600 147200103 988287449 718034144 438914335 33025838 355743483 389524450 878881124 382798656 625424168 955473432 507734139 397282322 265172349 970266180 233548287 401406342 354333726 788334476 54776954 253035822 860870665 592974208 32338030 11460594 807879130 350988474 157827874 177011019 757409070 920585368 906272004 618858252 572373882 313973149 174559410 624719073 945633571 113861174 786540711 525319127 799952912 480190601 441500214 210955166 271246498 789945198 432741295 391620168 808405077 825861564 646718159 456633780 130576728 746494868 263131027 356949872 849535827 968524169 831978331 977009478 599133037 781699439 616538062 310778209 67353606 73436301 652560317 791626102 721684242 669114875 660534369 968121719 378716980 664076137 412561425 397225710 583852852 135957920 311009727 885590471 918498541 57068195 492073428 936254548 625056038 529769818 660501084 154800601 404898463 990526723 765551374 763784534 510111859 9812155 45048464 146396202 566070452 156946535 349243500 662383091 176046711 232374927 811801865 984140423 550174364 66113937 343014426 585708841 876546086 112554576 871910503 520154747 419495248 896336142 -1739543 523070968 323921527 615773568 8212667 450875881 30489341 865623752 94156444 304027632 787999694 799570046 601028532 297615798 352055701 719907868 229604358 737065017 435623481 464059633 156623408 165538909 281443086 112835217 230102071 297238654 819633478 201852304 576727659 899822498 810603291 683072022 293017128 213587430 160525299 573469450 381883953 705824235 954069984 227040139 570948603 344665563 87186127 573666474 39926824 322284275 912551197 882776434 593521777 983965156 790273108 375886738 385136218 810933203 574752099 511695683 968760787 112913784 889958962 230560238 91333805 314357414 333173546 614314438 535833957 508481692 427389268 602323244 949457089 794132145 202039410 720964176 167102623 776593390 695181761 248687791 499466585 201894602 567639944 421489219 619438670 932133393 459638514 597347760 404503167 975489703 515122901 839670706 270700646 609188312 319881349 609489442 968835492 389823052 151580755 739407626 20127898 858004490 169838239 286166918 76730541 95268204 553528648 542702677 752127198 970753055 332928689 942862473 264800235 857344440 314234927 673469977 748808337 353664127 477996719 136746778 263035883 974440647 323635931 70078045 229563105 216909786 699792584 670154456 370649963 310420653 283337848 7666702 40034275 250574607 251659195 3554743 386478770 152114506 811833300 316749888 199593393 536350900 369403304 509576056 850704661 990581277 746600624 733417435 230838832 789237442 352281815 858346724 625915959 249532731 883623777 396950093 801998216 825614963 897520865 12598573 798551610 838282355 169003702 830923341 614936889 597884428 632801376 346470787 284754033 972887873 972436614 778850509 280738476 214423407 966549188 959964038 756695697 677039104 674179862 26537304 320777361 906888433 18252584 417187784 550897597 808352345 212579358 676537436 60767412 648141656 491814598 869547947 788196167 110947633 396880191 615421561 926768364 432554387 791959677 843353818 721847274 495896732 497739278 364652585 800234381 381661271 95844345 908620201 913994772 690435353 216174725 460165375 413779464 130329891 64873674 524327687 337801446 755127957 830164632 746066950 562810260 87702 328357786 290816407 860095711 165771946 995505205 162841661 375546285 598245827 914830460 899547892 857010373 462845654 149436259 295183374 232525730 728303173 479330643 194479130 252458888 176605465 589896432 670968392 656556054 905325004 63870963 957977988 332768533 468664436 252820270 173658822 726381534 492941393 92288270 321682504 699631908 734955729 695371932 911549771 364447447 607054100 544959472 534368537 286185229 882143512 391307255 378661650 26018764 271215490 886827279 484944996 15150636 395198852 914954050 282859937 747110181 253434931 277729435 45625262 631846196 189184170 686291672 985447297 489125266 699245103 104630392 302203498 292809344 307973996 424432356 365403289 322791434 45717955 817211699 132413931 39220761 89008905 66045411 771921165 547553048 29593313 414603911 423771206 220823900 242965347 512348739 144651304 456090015 724618877 888979571 490773944 685928574 727259810 314566681 497559627 452332185 204309087 871621757 660331048 483552684 245973713 192067734 954510134 133830964 111048216 281269964 710990569 587463851 811625256 443636224 742567829 230682491 681525388 390081266 386097091 557618676 629191088 49308704 670258887 472564341 303265570 258169826 495550203 381266651 790263195 687394294 868458480 707663177 901858435 287660017 430898438 678944593 906520000 585655916 810294261 12212451 976097154 761717044 942455559 927269139 673014413 357466980 350109113 4148648 93657022 922174336 257580032 544900544 449115490 720961717 997189933 755981463 387961011 200575369 846708042 960414778 416755699 55261117 209799252 447535965 396622058 540275876 872679416 93494310 984409510 752323344 791418138 777706962 965790711 82728927 716544474 893621086 856676347 731322358 886931171 166258274 554603238 354838634 467950713 323640146 268884430 510718175 438042720 665823058 917193175 649326168 461261125 718968087 912061970 777614118 351702303 405973379 596035868 2048753 50051826 724662660 476743409 532763564 876844135 381025812 960185535 151446546 872172537 851744755 967725380 563947034 929838523 181744372 731764742 778608066 372117299 359145958 920579477 980429500 200350511 725462103 478154055 951665744 828748953 804602379 338953050 845357553 372996744 697254565 912029597 386995788 399402597 530068054 853577526 988348703 56952932 367609642 613267598 92055514 697234998 39918093 969071000 847940294 357029602 642821414 883677247 233004315 881486978 914773709 400075805 925157663 563818488 392684315 68057898 1080844 303963959 368811858 91321110 576235773 584757191 347696238 172991321 91489095 350446489 674427511 613223967 42330005 610058077 688451306 74342922 645802813 929671572 965436477 373560123 849325946 730642468 207593234 244191363 814048038 84333385 530011017 791613832 984299285 484234699 456621955 293876247 913461758 879863926 856693377 756786680 614843019 151865436 151751348 727518726 353197325 127918166 168251704 432222330 890402472 805488819 694883370 305176631 40174345 114336368 315525968 690542487 141889930 592887852 261590950 410518974 625252245 963795826 413253813 198823520 369521570 407319253 83841494 676013104 873814704 734202539 41392652 809767454 478561950 373577057 71858602 917995882 762061035 244985582 755653558 49798831 721814577 410881736 319557238 595686622 662815091 873989606 425010638 147882378 194270076 739175708 577637179 7420429 427155724 420889754 576757282 663232191 137752707 530990307 954351410 351296883 229321170 425444658 29241004 196056961 911371162 482733766 894867901 368019011 310428907 360105900 502364347 422877518 990408604 969134330 433979459 352211863 185608834 130234545 696946363 58719972 375717342 138347961 388898095 971830465 576613664 910084286 232963569 634159577 878438861 688018586 292624741 582817534 984151283 134774461 132654733 573275392 819529974 700552941 919943532 898337188 221552978 211953019 606225685 170049098 106540151 720337169 810841438 66742752 389146441 261578753 261599030 442550061 34953750 452221064 364778770 488076521 209816937 654963354 5131674 145769301 599250669 164651584 425505908 938662856 885329751 857050723 25435082 809769315 896907070 309743449 555160447 369401633 529594333 718179497 42907123 218710122 43379821 220862448 268266127 236202431 235127911 815010285 769213316 746394957 53805652 832398300 718165448 911604377 905576697 977772094 710564172 525613345 979723537 979168375 310106565 523875979 898253906 768722861 515119499 854292428 66943474 720359002 296438586 226431220 526858245 607824224 841503558 673523393 468858127 234617186 910042477 279509465 599512773 411898257 49669825 308697443 86094690 544721510 859650826 2355249 114734572 704776328 639018614 386135411 461252474 344857562 324486941 620041782 687436108 646610925 464632198 450937024 72767148 624206764 206357630 844194866 341737326 991563389 409246802 105423462 277776964 944742768 639258590 100599085 687590923 340894539 870958538 387523527 286434282 338465427 973418129 948295489 482187190 620693034 586246428 391406886 524283680 311705797 326296061 581238348 145827130 397833399 950895498 49133894 985473847 699440635 760520667 784172287 863074635 880337913 231489467 32074179 754179414 996545192 115017596 137882494 704431522 483024542 643131286 422933644 333343520 309692862 20239010 286763833 32008020 448559518 877477030 169824861 176697117 721143908 937348928 854523665 898006005 485649740 92675044 126684777 233882236 128742480 751394353 576235420 686494565 650800345 646906844 867716676 86547590 506264786 791815175 827997867 879078642 829399953 971996851 170454379 400948386 861062570 20198850 249007130 893858366 995645304 656987845 279137723 377544938 938643313 633305482 299249734 476474823 123767035 488094616 666759407 682535300 957630241 190351524 832878725 344797085 798590437 741409336 694273152 137274701 11224939 42032496 102887630 451645128 82046912 660593293 911666886 822194082 841575343 618820729 871225912 301947255 508557566 74518879 381917695 69304819 236849904 341766364 170381602 456820639 744710010 915189827 779446533 561800326 101535010 940480235 593896470 501064420 557456545 984669839 30417792 49155687 218314743 483113364 951715865 595576520 529392643 887621696 367645580 211733305 862667060 68759593 574117424 741957839 901494729 369170780 273393033 887649499 765980075 44358990 844815597 51548221 43219776 484390532 35715405 346197079 882504503 786915983 270939805 49251226 756336532 660394380 939325516 340015515 538622321 632544301 33003699 679287307 327551225 410080451 645363958 926338955 696858237 779608365 793921513 641848496 162005747 362464368 444309589 382349526 871380772 319619272 519306168 817344207 664297072 652977999 824064610 953786140 430306806 290812710 995770428 115025482 379288953 321327754 203872136 116302079 727497018 513550262 582192949 314332759 596482191 676510050 343958005 887760007 439787685 870844562 625409195 750195234 363466632 481944641 775499106 486650612 483311992 634431458 180433539 834883176 998801389 254890909 438681381 -2500069 478037311 536901128 844334959 934557768 404022677 526554007 226968383 142674483 194894382 797587583 209943468 675236672 3436351 823360307 365689010 321677897 28306337 775826626 120259762 314610772 761322436 579886546 924683935 600245928 165988256 923612618 518307620 966985112 479105197 298276523 14601403 933598064 469064957 795553078 548152296 623201470 19054165 106803751 9109378 748925880 446788949 140751345 783632953 114635245 305603431 782276429 979400367 54563978 662903094 762398848 58364686 55210475 962085515 763224477 792780810 896616614 836133742 321842797 666397519 584909882 590880127 137333519 675418135 472311795 839022456 38923858 30058056 576410039 273692803 295167487 535451746 255472042 746779304 901268017 914009332 566935262 887878952 563880970 835408941 820736888 952026020 456872774 266883670 746419178 124406678 980482247 434936110 678908809 73414662 145148517 52918844 851064711 173406310 584020672 694473729 451756980 861721413 -723339 8275313 302222530 780837423 42591859 43395483 874595263 833891773 763931391 491044332 588948275 391444861 983799831 859648438 186471197 779533591 107577186 56392314 708284044 457695869 216473942 907729922 633083946 54157629 838610002 874632102 342876944 494419852 62706928 385538513 733578850 627623981 489601880 585220326 165953489 976061351 829435477 763793493 434066612 400536086 396277342 143908192 785611342 212731080 681516922 599845941 561898536 578925081 685836653 590512001 755590393 790092326 634593377 974049342 411595395 624516242 781297833 677452919 874502470 498384710 406364053 330679579 825833205 262506786 235140658 346957848 300844889 857601695 253485010 110367050 925641026 490791761 845245244 813500907 259008958 365899598 811745040 171342950 134666262 809531719 944488489 652318913 625344132 463984279 898061783 56585331 306030343 459581624 884103716 978670889 587826464 950505291 294735278 37290854 754335862 567798883 172326515 379370782 241463228 859544095 136413199 481594287 725912663 363110024 895447989 170364376 35157624 540291883 4090315 286626958 811184728 960714678 718894322 115266704 788955848 594182669 911342066 708802564 198070343 485067600 829807652 790882133 818721826 770292388 913491112 535094113 127032887 806242834 214629956 803639621 566831622 574259465 3014715 125968143 577322846 622209283 557511081 804210795 51898529 414427104 809495800 552412570 7715284 483186759 281488184 916781301 256647358 55012775 512007645 356889427 250684475 300963626 366366301 246270695 501208702 915183595 572561219 721139194 994416422 496756949 350338137 565251414 363768783 210203539 461182735 746234166 248042098 617136528 722373778 600770971 946942196 342189474 297796047 351137512 834417177 20011272 158147551 319125454 195322361 45877576 778794061 55655162 960382682 823997030 473069716 736514427 244489999 67881873 186615721 998507782 699755503 435408534 339594143 225256285 856469827 852095431 737183548 325458248 380022540 728220918 630692013 629292862 785368980 994960155 161876800 637789386 973857264 269093286 462701422 126642948 991876446 787448460 809760600 175650707 196821770 115672423 135702991 697868544 818788576 986464999 812104296 352769952 49878982 506314867 857855598 75921365 779551195 926908675 666885594 107164710 481548712 979913523 325338648 795805907 12198010 823026253 404394699 771721459 603640909 361854284 76050167 132320209 753286227 959806860 273606425 675064245 123871699 911803484 74061210 550294445 521540272 908949607 514251602 895883892 569817916 255103587 777058742 275759934 723089062 598958962 985641880 197475488 678997180 150065135 230610459 864653850 444814970 992745130 657993178 526769038 552721324 11649430 672539918 67230890 821923491 945378062 399658192 236867457 66186006 198286567 957136502 51388926 121233958 983589586 792549541 425419357 716010202 879871788 813692479 234088813 -1078838 434439477 52079196 242368575 89623618 101759989 885399717 395662537 799640740 453541825 487995503 366068118 254324510 867228177 274957610 522587792 380423297 660100789 693195378 30816502 758042005 895051676 485509444 803639072 942573441 969831037 709143597 626173486 553201780 970808356 839642665 801736456 940006263 24053574 552392095 735659698 108216994 437568160 418955628 146573027 919337527 438094333 407973153 571590931 220777190 91920989 452452213 145113458 783987649 509306060 122728785 327366451 299076333 538233964 330889899 345446741 504925324 370836138 336027862 885810272 134198109 651701185 637197882 285338988 4140715 213908325 385294057 524713913 158274385 908695891 707443665 731665720 856859539 102816896 113378843 799995718 450073538 564809065 569523747 871252152 422134508 169231653 935514822 993256249 999762503 444404172 669637657 901673073 867259261 212499397 826114777 910477957 331928596 803536002 634280202 188407776 499683124 506346294 322121255 559941423 379530365 877437104 626057593 732802554 543788357 532765819 403204465 339094007 990507172 30524584 411922270 364291156 155805532 881034658 918254453 199228499 730509096 7224727 373334387 62763956 393502448 34039785 195201494 761610457 39034845 362829566 -287691 601525754 884942863 193057578 459165749 109478047 370580536 293320871 927035128 46406165 430741813 479079583 359423877 844223405 860469706 710935836 261987492 94538456 921235451 185243375 693736732 97161263 603103023 711237168 832591368 820196727 269665651 537597809 641329249 802829941 190098315 976103696 275027813 721124101 514223887 302294883 720847517 86807107 203055878 693075158 707572132 224150230 351511532 441561060 831137992 47971777 55725803 684595603 704220994 373081396 536911165 478569492 300056329 965405812 41289143 980540493 526114282 509149304 941554010 735374488 952977095 622303975 953676011 898806900 924378894 62517890 728669590 121836927 47145465 979768579 47314557 559008003 867322868 688645828 534731889 50322453 819689527 338899365 174564226 902452975 126116143 753584226 445886685 882884273 506447277 121844437 336280520 396227987 430019371 519789372 533062626 973999784 875098939 229935174 367244236 -415150 830903615 282201341 888951578 131163520 959830752 589335309 875610248 375674034 634480592 349164177 194473874 548418009 94844923 209846959 165784537 499985112 457437535 670661560 568290961 184928478 970986374 525593403 553303755 649230700 731317409 692946380 549199544 819256842 165058480 551845703 241100602 610396689 621241385 757782480 49240600 640351960 923187404 404497366 382301242 972681818 459432147 509549105 958453290 66532140 799582333 322402374 529846559 919840790 257663160 949991271 68961975 940451789 142040451 289799396 178402024 626101693 284012632 819748768 247318780 957029962 880859633 299408132 964469732 215858204 516671621 13379376 374027749 188356260 425990008 662683228 84767574 533807813 169938269 167908656 564532510 651995438 567631740 361108913 443117169 169781943 668553461 13790191 342736088 820051963 38965654 17950292 958687630 855476213 505157392 199332805 530281429 611899603 670984920 403435887 145116916 598285426 617055382 321003528 255352291 798540909 266291336 873318625 22483279 887022209 298789767 822236049 607447254 830502641 501036849 987997577 285664717 979902312 753369303 588472587 547303787 630892546 681041848 218741160 948146620 463307831 524919953 132415984 92935452 536895685 395784686 925381774 472901272 572716756 681679965 872666469 569459643 332384979 514234900 909671356 271935093 247651773 164822700 662679557 666822481 430455422 362884154 584504004 366119348 368702680 973311779 583096003 621690528 622353075 176305583 932901053 233472160 918976128 935068480 203613673 798893484 370414917 468354232 206136232 889363989 146506560 497005877 180601202 529127019 142274704 491196343 105536209 924957964 386009064 336482460 440329868 347878 800932822 617646340 557645651 101333734 586021175 424448672 10309347 37761888 27256475 628022462 242993280 964190209 426546963 354089345 30404697 342372088 935491408 760080534 188485958 395242745 632121210 230997306 681757827 544421109 426296512 568921491 766466249 558743953 210032258 762029172 669555067 358021131 55010524 766972015 718166106 689925509 561711876 366191714 150085827 722411626 568042294 459911014 48662656 697846650 10502579 156455795 559384161 878898133 216942635 280676890 371877854 696933883 335218535 957415922 268057986 206955456 496233145 99117732 839558711 200986253 974058208 554746742 277648586 771231309 432175568 333221228 539649705 867551534 648876787 477438369 535580197 295809917 67798146 269913573 14947361 164591844 408770055 795970462 204255703 389987983 592858543 251765210 563879233 395520954 728017705 940961131 802110254 415680531 249673311 914433288 179294112 452114187 75645505 296183825 492367746 808156479 139386810 660385726 669981187 50090853 616440299 777413013 343662586 911299900 177235123 2409672 741019035 302745342 309613362 832702815 533344408 407764320 827786248 571108498 888493063 93367417 754096048 230754098 745246101 25854660 174104341 102140678 168516808 52025 734478064 337746169 449519138 534753729 345076802 188270701 892046846 799761445 614156952 699517823 979261624 46002845 426209546 176733187 741581028 379255637 960504313 728310710 528496961 194497208 559251531 549188376 99255512 986892718 181432159 650960704 448456935 460603555 484864329 307316383 431507186 186840462 149064645 678422178 188452719 980933849 381497426 351091456 906585101 958982127 835029665 195488675 982256463 271549577 153497995 429287291 308938433 551009237 832527470 332618365 261170930 139062124 507000391 845950439 610463551 440572100 763528228 996861449 457786374 591667044 521133803 324872352 195593866 905294448 486183564 3960523 874596693 797672981 84981852 246171826 561326206 116449294 342920864 121740785 693137791 68236925 545617570 215678301 297235652 202091308 976476571 970967756 731204417 801422909 349012113 77937499 519880305 43075342 618771016 718469653 106912250 773961457 979181931 552898883 554945155 985566544 256231628 351331184 199617214 722483271 84967854 397991460 375404260 221489139 734266674 981774525 438803319 895276445 680660301 12569280 629904010 777974393 972161629 52833429 717683670 246562333 126902780 425902523 901378659 844621605 715072767 316764599 947342952 262709651 393162250 188182015 50085984 664186788 310860336 505161862 114058703 102105333 729513497 272849949 177523597 945944168 99852545 962364823 269511576 749688894 49241387 59004101 48685281 765669176 885093788 293977970 282451384 121877403 291996461 103521424 514977836 296440484 969689790 860632676 453036261 905229508 833489397 383515277 331100927 151788008 289003763 833850976 64467981 784493036 558329654 530147191 185240279 480711190 698974890 575059084 222484008 429073429 781369180 737400456 940621705 42633746 624844201 461613648 109591018 755332848 725957363 869073005 351901729 270607017 636720786 525776296 120334343 893325302 360082281 655017970 329123188 317922750 49515068 79286712 97933602 -3722678 855931780 697105642 655681041 241146424 505341516 731916595 51306214 284176585 571035207 985251506 603077913 291310839 597546275 549495325 459704550 758854842 715543134 290502339 476547205 407505593 554681854 332817001 823809960 536394080 71361952 985256701 944217835 719917845 24902867 368123241 913897822 161435658 409319933 369371727 419465302 649667313 19628615 466915622 75503368 42274995 659540488 782411679 199511202 48773839 911218985 422533996 201238007 717842701 58066177 522492898 555583720 129216241 852802539 709755662 950006791 619790361 563583709 848664642 584154688 504492228 885743540 185149180 46651475 766203295 337521459 325229680 189140213 492000106 24055706 588715055 797649941 994130846 218727356 888444557 283422012 365912160 399169410 34696299 453114256 890495595 168543586 633207610 990847635 866455526 867954600 759585267 281542559 95764831 378836544 457233733 785973678 660260911 619025413 404138914 359509868 989707149 633493950 213969866 415771457 324266287 663101400 123517827 38486239 708569261 303241942 328459955 109999385 585686336 801125825 218037238 134929290 939001927 174733554 595289535 71157923 640063811 543279272 613822573 764949063 406640102 742639775 934329297 138145469 979646871 141373392 214543384 246497874 106110158 927988977 828138185 490061680 355253657 220500695 778159341 626555598 694564273 185599596 534873379 639073041 109710030 166026705 7531413 75714260 873154387 118090654 626898897 691208907 94656541 88235120 98148847 153613341 936461061 284996171 625316501 393905005 774536812 376199110 482962552 835494706 550270569 771552856 703099059 462394452 144508786 263152242 837611402 316799170 356103287 920524529 347473644 722978589 224591509 299569830 104949507 803420112 59059176 229325266 355004633 113124610 437885410 572363440 597684606 753940038 371872119 736416017 541662062 666291773 703134940 191827117 411956553 6269598 467536966 472555520 796183853 584108941 578773232 826118492 154453942 752607853 22660789 165294699 421703450 493257135 121035492 79684675 518206823 46682472 196302352 983450949 13385868 965743677 472150921 831392325 601697354 977998505 852482396 592162356 145177401 124119424 61232257 765061040 542745530 527308704 371404705 170541868 436515217 810383190 850747319 46787320 516869275 122362132 451934836 359694980 475037900 84903797 361771796 263852870 64070191 455885840 779810845 212308302 173280400 432687860 975867687 672974110 294997965 459561624 569262806 269404308 34665286 651507624 409281992 135896931 369830564 194398885 802116285 758065971 763738224 17351276 114880116 725518423 779275765 350412568 15353783 545273123 532694412 963877092 815028426 548189677 310386153 608799219 731862559 527746036 253161337 807645356 229432629 495759602 845593472 858913612 416679432 817166349 70679026 564040621 984576795 546539420 444626508 926775661 92353338 322789959 113999056 759274936 4365038 192324785 714962605 674814302 978038255 678992520 362685740 310701207 602540542 245320175 646783738 2671431 995240185 797532570 874509124 276923886 686392470 802804302 493465471 270174002 470542500 137261870 21595275 856784965 755967235 466754313 102374436 702417385 333251741 990537984 149518630 327240269 413476663 368158322 667467854 16956941 826853435 978592324 91301239 696134177 355053416 108068559 616419320 278901052 313915803 710083939 432242027 410543811 195998463 354978287 726316292 367111485 415466520 762793746 778202385 890898058 278936748 751827898 221642057 570028064 539585191 258589769 275610017 194684403 698560297 799626923 389277045 898841482 511180815 603139223 852938232 136611369 196674367 312980554 876131283 141580432 498430792 171954950 322092804 53236756 607591099 294521070 372258464 186368177 546974900 304015170 156294954 936163186 110556388 7077057 863919551 949952684 803964814 469323011 172790026 114643482 830989943 653217526 107587687 967488523 879775827 128296741 98063424 153301404 73517019 228333769 239281419 571591798 539354332 318696331 159754015 76929639 258547024 694326669 769137271 869885718 895441507 132026162 831744885 166116640 473038024 946840324 678857357 165669709 567316808 183720971 693927142 949306004 422634847 955071277 233588702 374728049 847988302 244963395 711047133 683515345 252308883 128117719 897685394 869465344 88440390 470831760 588868222 910843012 64408109 24247271 946025551 600036175 23522055 215894486 651966675 242285515 700751653 17636775 552928392 363192285 91215747 350472473 784715756 156008345 796500854 373020834 969583128 707867738 541951318 89098989 242445749 616505709 642611985 446812360 915223591 283607124 963241186 126163719 142424493 975096711 389112272 178914994 929452885 149527660 937190932 975001564 44605177 314354844 589621089 733990692 845501335 134492456 241129126 822899956 550882223 310143139 164742521 722781530 259683560 592002575 741727669 202138572 909904247 278746412 914530161 707656456 237970696 214065050 626560781 689334527 956304330 337100995 303771948 98184949 892862933 141052546 883851533 20894425 864280359 416754709 825589986 781205877 784703219 659168166 843946606 581864801 54239912 298275157 229689046 754563779 768579829 282934366 591112239 25517058 292591710 173021395 68834420 605240335 300482943 369137532 73712245 130613613 727609896 495783343 554711527 556692476 96557441 495875193 567915481 587478558 955029571 657861676 444925434 681451666 417486693 785380341 494775840 417114561 247963538 106416773 813345421 781660873 972397662 200676012 935335476 691384861 385270243 437640738 731217082 942350638 900763834 853336690 281292295 623526822 922955583 369903694 586468753 804231108 466540059 346860293 239305154 41707894 444950059 171200705 241645245 449304167 633103602 322706931 61403452 133764675 68185333 880133382 572477746 608993115 467622603 846503439 124181102 432967384 13188102 781691240 327155778 74821882 159195085 433801058 589438148 589053985 811985183 928606748 617123676 236994467 14844907 266643321 870456527 265611264 855024533 497192156 504212461 389484217 379668268 420959643 470027028 191942922 293441498 451017966 753408446 886303425 654805610 528750768 758077326 799667126 124587160 758090586 206494364 529248790 407928513 134003153 490119460 197815219 364632335 30677814 903206056 93528065 825639209 706018358 689487304 481989689 466160301 648772871 869091887 339395763 605873380 787359028 187268643 204302257 783839035 584832083 264360391 563549677 855580337 679633594 78955752 157227235 959670028 310450173 334051289 206036959 977780144 376741739 42946472 785913468 417059422 343638786 624861086 494358935 128906893 823361003 959661817 82082074 790683635 269983774 735799634 437183603 672691410 114541433 475932269 315273086 416794987 38873731 781537291 104576019 139299183 520365214 642897044 551678649 970333617 916710106 629127781 854079628 758104791 126335252 37873509 833504095 296013278 679747081 597270934 758176081 544455958 252533501 169425467 70877315 177283629 663784349 629715294 260956430 -940620 473282211 27540320 284549416 376243283 920027514 346827289 27799265 292864805 723241259 798306443 522532225 807999406 477262101 262089542 839806759 327208740 98316837 550531413 192347812 426278222 983896942 668692487 320911998 228278473 348182855 3031573 691105483 81704407 139928571 213743735 711288845 63089971 909152073 912085030 134884802 731264103 362361151 365462909 291042174 851294718 625626671 366750926 135400378 123902727 133323127 976812374 990609338 772126525 35023130 237861498 898218319 417649740 54879738 113720104 106113337 371590338 364800292 834094393 120964657 405298067 148073462 568810668 557318320 262149740 307368275 841792365 719195201 837687356 110847602 858463295 559699993 773010402 145943797 495757145 635515993 831825219 957897634 371838977 652432126 773099977 741255002 969126933 132783262 132028039 740445953 509965162 749668672 399253849 735570659 18499870 351401746 859137328 90295537 519681950 779377735 -4742092 17028626 677231615 684999879 -1600284 911931727 574818445 256417494 785304105 409558389 616188429 749871352 695863637 889674201 928667066 889458040 889738929 751765356 660032561 712134144 847069399 385300952 270353099 944115324 360012116 510695140 820707470 676653532 766570076 939943718 115132385 974544230 67525334 690897568 649401629 89715758 882035759 430640145 83793327 781089123 823491081 170127167 957399034 488797713 188006698 980265959 434453010 663632633 877406277 507827774 765700716 74346227 575799581 998465481 52674985 531820291 370688700 369489949 689852408 846069885 991841694 829867442 740965412 171039921 599517731 122904700 867543171 969582928 58455833 480370837 298986029 189250854 146064221 848871568 207581297 468039139 701157631 691984979 891879496 127129983 75310400 556107622 187597653 668204377 174971116 3301281 356074787 156316926 792772627 622554708 538691186 358877748 507337435 493618889 457760173 658657225 432758467 158634910 462779615 533698901 568370199 393619699 884894498 615754854 353715780 281081544 426178695 417917333 353134632 654313237 886670218 106419577 333863550 28364375 173383283 917571473 445388367 729029103 485085531 403292473 875267426 398544365 830415479 501560070 621747159 169687123 104341193 527742290 53027958 956828484 663416441 270177212 694103975 337703137 198872439 262318835 863903565 648457591 553325089 289628401 399751540 523699239 469904988 33087231 1514187 515061378 172159933 419591230 559037444 658986138 774217556 268250239 478658174 448178163 423850122 626196173 977333105 253117597 466850949 349097306 412740389 869806121 796185296 488849202 231806532 682293135 648890722 544145781 309749136 811228073 195326058 308278433 243596636 900552002 347244807 191485966 611713184 463390495 811638693 382059478 223961280 258429198 640440218 898005549 864797381 724269095 18760497 524485648 921595101 752128322 9085854 454550474 941305042 844903329 174357713 626816061 843599752 816523147 590558378 89560957 786060321 522521101 455129275 7502602 760795431 963260610 546213951 81071063 52396844 796978409 980653966 770563139 464163446 16376154 426869852 699680406 490676081 895830684 269594182 715024893 57944188 404834794 341961013 388078693 94983159 248192665 323662411 157795581 56497792 809043013 252240937 759699902 243443458 884287199 744483506 568891654 462360127 851317446 577233552 305278308 319630777 174851882 378326964 421694000 735931940 109988655 556544268 243746281 632147774 391748233 220363437 843009954 718660613 385154515 68265389 776352128 618386146 661328421 813336447 754638642 430267008 960092454 592916306 262245154 628882915 102644492 462862144 53411895 86344594 147790901 975355572 802951145 170349828 243395251 390803189 819312498 692038965 545218898 84719798 933912082 600702371 701955778 36847638 376899532 264895498 277135290 418313606 790560937 811067904 50530218 943171761 243970012 697892555 170165078 351327395 672882427 758470026 651796629 899811164 81477925 814872781 71286657 558358310 55352612 33547523 666027344 545226967 922369300 166158087 114710934 664356177 189789352 856445774 596909500 720019427 881211199 625202667 574163963 337965638 489447604 273768666 332011686 149435815 718410781 829632968 192924360 249484232 253815676 241355755 609861282 695328356 898185577 483519783 465163482 450968152 543754451 593211933 160485739 266929557 373148125 913512727 354798026 561670493 964619563 426035777 999763098 746569469 864706143 103772128 934220729 687764481 36870414 499909524 202830369 214790165 33706300 219550607 557353515 271104938 558219145 958942955 830340632 341695876 144956576 77268813 382522461 902464760 493446182 30775196 329110229 654075015 992338527 651945895 519442686 869886596 524061566 77339317 567461066 679271949 279986281 417857750 383056742 629009513 968517904 32965505 264802267 110340340 621301103 968854575 717889964 36279796 828727030 583577667 678850160 376339632 485515851 32673785 449555218 350198152 514998719 169432690 325970836 439601544 -1043621 673174605 951260719 437007537 303181512 260240407 -931586 741855475 -220012 479307976 743972726 979905917 777860078 643958520 268739490 372101254 10147065 340949736 789774318 3619438 328301523 772095150 914556727 376533856 664540945 860363123 699436602 389485423 118346164 247950754 461374207 394502174 68288687 675569990 784430132 131242647 299724905 237746092 762771849 768606103 190246417 535413946 323403696 252505610 25212181 815475402 99944342 599274467 361758474 945360463 897474457 948699157 518330304 843675683 607070606 740746364 926118852 333781892 734510959 866318030 781562277 794593675 147895090 375060171 148426332 359322784 210911120 370882230 557972821 159085906 446526096 717455454 158521312 370850509 60026243 744848103 474045393 864970631 481448566 327456677 150055759 419555449 -161422 999300455 137693682 900093978 139815281 616665446 635137250 260116061 368024125 272389036 621129324 37648778 580176787 516456481 937210462 499665819 438642049 211689078 774664649 293239553