5000 823
947413902 788108990 505826356 239431198 940668679 269049942 585237952 932007415 833627427 344658837 655482626 964943217 190696082 867454257 977659866 776012018 234771643 871405477 596525348 568264473 824968614 740780908 863038130 544148526 235483099 461237483 552220215 319225447 302602958 670503151 542228162 47736980 182534813 306830592 721660391 364129462 820583228 589010187 625931970 656525536 997087810 119913187 807198058 334885553 253764123 693432544 763943031 660042604 130427372 611358044 626444520 550624017 920863906 669962377 276737695 558692923 426485121 234280901 338723668 602259393 535158524 849390177 13320908 483504120 889980102 66264819 975411538 842634582 152346535 203654091 287297264 326422598 775075152 9458435 438505603 997043610 459307144 894255253 185375566 113277939 444754316 404280237 627188148 173806597 915479999 35522725 519045976 6325745 243511407 902547484 919713631 85739467 10162401 163453309 538328815 538089149 44648508 623049110 788373023 818408598 398554112 356174363 773067389 238796613 595351535 126261855 239443916 184184841 43730157 894901571 672847419 560047944 828845197 1174557 435362946 87793466 430545848 561719946 850829955 915749420 986770099 573783152 790040694 94610769 254030175 73329730 789611273 40817563 718620664 901959444 800616344 403745660 778682900 868752621 323337006 428048080 75384871 564432054 231446209 928247014 909260119 194268076 267848296 650973862 50378141 33341298 466630642 57197644 580261982 508866234 360740573 802480168 73838487 500121948 765459151 568456764 950174908 959960730 920604502 99532066 58159011 985542984 524891300 465744620 307111479 62135996 236152668 596191424 940366005 406753210 303514918 128010404 240068428 420724964 875898985 580245967 490454064 775086322 957024621 884890082 617213995 828886657 303682352 680054695 936896691 599862728 213832247 846315725 730981288 299065094 340380867 485264240 532313663 336501312 299098936 178402595 444702636 828231334 804499590 483576806 933724542 659852559 849344944 120528981 118692585 600543839 269000705 931586035 486120823 7991497 796281934 821097696 182356579 352024035 452223113 796622989 378518521 217291229 62164124 469770219 315328063 587939669 404474310 260614128 121317756 578229520 872309765 382110140 557855052 689732943 326495985 827420647 4789985 962563729 842080795 527889312 230155986 573345300 18576586 457939314 306924597 990436371 396782947 493475257 620397675 492325185 357016218 648524217 282302454 95879705 632251820 874544951 576316314 566808054 930994777 731967609 834208571 436111865 686547786 436412191 891692613 758465409 130584601 587296833 989493446 864486652 132013361 165598195 990215830 130748480 513404449 577367046 906748657 692309598 270224483 734355132 643456315 688244516 418530977 722070147 787497772 529686057 788662588 959977759 922714158 272891693 748254747 651529220 922804450 445233779 655228949 997222560 28171969 553663609 15107218 489115728 362729019 83761168 719960068 699388964 153852727 195961154 546267084 956222314 548137029 455092674 729462478 691429996 261693418 163815349 115060291 936348810 956328098 422759844 132414812 975492024 793905338 240347588 156027493 155384167 11074670 669433826 701859596 711514856 248242344 290762473 423503455 328766393 510683384 289675267 640012275 56743657 450901490 742203156 109209771 863252121 305181584 865461206 961460545 884193173 317376077 708977190 422671812 865464712 119643615 811820567 226920218 394405976 275819491 471777839 251178096 842796658 339174722 417965802 183483133 276203231 871439065 665705428 663380097 411304890 364866842 74408550 82071118 668042451 762503381 50602254 338254638 212025536 405335232 731199211 169681859 581533688 907110014 789024691 686361893 378470486 45957047 909133039 485450639 583152563 177457873 382072662 617610524 56772887 91400833 464326618 143300104 942698221 740254130 966617846 78122574 546305667 834559343 653247312 587012523 272824218 981717566 835796817 606272659 413671949 825059023 246516714 651048073 360018183 694902570 597955302 709558196 833720092 972698469 59821535 535949684 175596235 860652270 582006389 112355125 775535758 422263890 77272504 811400282 717352722 384832639 154433011 5721341 460652730 144628224 824422195 58034076 783723421 138099983 956526430 824643264 709759695 763459826 640686998 638104348 138914526 761586419 199084285 642645740 113106485 815365589 320627528 210943836 838051107 311061188 22345129 590926579 274920184 272527544 970795177 709844748 998094095 861346942 98793635 91545221 207282651 857368395 5283074 147129990 192344018 158727785 431552496 547257880 405049177 857892295 321589052 813565341 968793957 971996986 439240780 228655514 158107619 585671462 50973352 869586876 407128185 617608516 802884097 561875437 828630112 526890311 581633614 891139707 943643375 617827959 913277959 548692196 860071734 692263501 650439485 518942540 423516527 490948467 836809824 899563586 70151871 367751319 986937544 178788921 927029369 488929680 918198688 661600088 494666837 198291433 580434184 514208749 516447823 943284059 526897188 698468805 269803366 391583398 174059710 863318678 316669070 896248299 667068681 368740130 201018423 132554219 645434349 926745970 614251742 80387530 457416208 955479356 88001794 677345415 17135841 190555099 627990739 592679980 123679481 343895901 451205979 106758777 250804103 635580280 27389152 358765792 776578509 131251280 840220451 163664714 487764884 384917402 540357407 621940035 900799967 732807578 638759524 869639862 572605763 271958993 20750987 14573904 692729253 145216115 545562131 779886815 802755684 92434008 176997488 59786259 529865889 284767692 17465421 155722001 905157760 92901360 979761831 769927754 161116061 752526292 983393025 890805313 720975186 889216943 790183885 472887360 335227377 786818864 128394238 731528464 444272895 794763497 943404922 271366692 741944876 501114592 718893394 170779903 48198279 69890315 781735923 396657713 420507504 245041620 892761404 604864939 620725719 168127052 268593558 33343163 398467280 892043076 767560102 889174927 176744361 488283645 80751218 476661099 418925354 939237974 222164517 518814159 625804047 562955153 809346319 806718483 89528467 679730217 327254185 361737626 792555046 474638013 407963709 709348619 8934027 73508168 214638965 264242081 554338573 197726553 406368126 806839133 840269708 847946937 782293552 826299576 551243296 445839842 553861613 772905955 718665793 838959007 596972367 229907039 116716070 180495537 835033164 669167257 847146732 317501605 282785740 847213 144294859 61884004 562225744 825433748 797079622 294594884 504973008 231348462 753156893 343896995 103196569 475218653 701966474 730779198 336957983 912122511 953048213 679115477 556544939 1966104 30104687 448843099 109826090 356374946 13412514 838611751 695789099 726604956 307545381 158439724 970685802 565698974 247430268 178376723 855308640 36268615 551229825 156594867 727250083 386614442 43231817 671232531 250544475 284238871 968038098 789866059 710666985 630816759 608745843 61965661 101360512 343839415 258787635 790417376 609119705 965622861 324639004 572895232 860437356 950555784 196449484 950972175 230253758 214051383 681875493 586218581 205179529 194535390 318165585 5217186 429007005 552253790 589159302 516445580 843385354 738374221 165070908 753191883 751805326 72350529 397852016 4769663 462402206 35672613 856405205 30196280 946752986 620295857 240068273 652267531 464688430 604270529 868396440 754640842 109955759 925234194 240540891 729082018 788266441 420180039 826574025 487270627 939016872 818380480 588360817 767143889 243904212 120267826 631267048 669462441 772522882 601416768 489870348 707186469 689229828 736470309 490856873 919387828 952200041 625738220 257457557 779516261 536610325 610452031 447485099 723228765 625954431 533547666 370749508 862381115 898994117 338814667 315238081 429131611 364488043 325386058 284304857 362501720 962788122 575202678 790748771 808859231 295293727 61702623 696742931 811162273 417445283 17967122 413151829 638873976 437805424 195688191 57283583 194653103 93357475 686312765 824842564 430095529 323379631 678433810 968059061 219877555 89544405 809308909 170539700 265906699 210076111 451983085 938144372 122754043 987924822 943192418 503818846 599191249 763522178 116702092 413172590 191649726 356014457 652914774 576802972 508269518 639661813 904879918 939331454 934194369 283204738 320955908 752546332 395261090 205867866 502105855 846155690 638062859 502173414 765711554 195033811 124265504 189643300 41723756 972883216 507501636 578493125 932588317 87928582 977703475 833848061 883533218 189663806 631394020 967036794 183763407 510399162 466776727 707987349 491952147 732488828 579930975 272258882 914249175 477981486 751451396 45625671 364882940 580179858 313245942 79353389 446013110 759403089 183155995 288698444 501753839 263790564 807850500 440527855 193799381 997014498 495870267 197858325 900109240 556880975 549613139 65653459 650805624 534205593 846379102 435112102 666864380 225776089 736880175 877929330 308223084 982049755 515444418 412159207 957850123 168948913 82223691 386288257 454575340 859101346 855142838 48220297 385539401 295418385 754504451 187308193 852605976 403439466 757090525 40644044 838949108 137619783 220028586 41502787 917353932 266860021 930818264 974643712 344900347 378896587 607401265 477935277 602222678 146057861 964397258 638111851 738665290 814212038 768242692 725587336 928904033 364433932 274329781 112080548 485543273 103102501 95442166 205271666 784882643 322819337 252222555 92625452 727470247 678784281 515449925 727390875 922187266 320429859 171008989 986909246 436604256 638926196 863420140 627279052 240815845 170555319 28760400 856278066 226787981 227728975 597344335 439708729 590020008 71394631 489095366 15752194 292127883 456846648 230587235 956759135 775712510 68250666 985058966 214803752 379822726 945271468 413391058 473517927 625716438 49792027 361118541 952271222 976867305 133449613 957738215 582836846 253135874 563448363 804025078 477791661 929557822 622389132 231274230 529412279 567274272 288502716 326770203 323306905 389646978 801456671 138620134 488543526 721604518 985630917 942425749 526219199 55033777 726782213 167602583 427068445 888718768 504905996 299652981 264374889 418997656 192403643 145925400 271615881 201308267 882007711 557640228 693096145 876898285 40793560 968000959 42350155 984375463 987531689 817105979 687166407 166360745 312015287 713377030 754910664 642281326 584464405 303027108 448179098 766423152 171201260 401320252 495564347 72837205 546076299 3075785 759494673 869830188 735827944 159358832 261213112 84984293 709636864 948883319 320221111 597463125 885043638 269025172 546043562 163259918 962104083 688737604 569034515 615739251 14045165 616966510 850888751 637419781 178444566 827094523 774798329 106985267 156161410 28143145 247505537 756795214 142542805 696830630 360289215 789399053 326996986 910944379 935134911 827390077 538540697 862113568 767411431 41253574 786968377 173821102 177356969 114621395 284903213 772530990 104807382 193331647 22912212 40369901 955044665 378268540 524280376 413007211 780623019 50874904 690303770 862380742 771911588 139578658 995967993 986752746 575378073 66693955 788350753 13963946 823582119 412074273 535769208 766985710 242735054 926478644 780562687 968718086 140089957 287287122 778155350 815244021 943873406 344918878 276505480 475795641 165502868 874934012 177626497 710699962 308450552 974969870 378355078 156159682 954497587 766850707 424731700 305321526 990514060 183031330 241924947 275306839 631402397 826260452 242153307 72938515 40733692 934635200 651699187 521878864 389535309 498943646 836440069 793239711 533295494 498998257 211839390 740992878 729579678 370435280 377510618 914960916 306490457 338293334 190353357 776808092 268398442 226302582 363159510 344000384 950316289 777769273 716536217 329146154 412949458 647015888 629812819 480243399 193698711 655922250 205390243 334862580 266823141 519463458 276921545 482316659 246194708 366300786 899612387 16366187 161936962 994980611 782559195 853790572 110213007 923567814 499559056 240945935 599486636 348988813 570032297 61521190 571565610 562399453 69337063 667085962 327852679 807664313 492280103 611902928 182219062 526884673 559205111 677623591 893540050 192793242 904283358 820602515 100665242 120546245 554298006 990001323 555166888 844761965 924357935 638178318 103654196 54767508 230602351 826831723 980047031 249686681 290339356 211193319 689133322 699498113 286925672 568017046 866624495 969442849 685479303 348988894 424980697 23470661 323575098 557739956 684992489 107622460 519750859 29535430 913059781 755560677 227082432 85513913 118712054 975247196 204272861 239017818 288507306 702608046 319681202 485911388 280396657 680132349 830976836 853975052 684474477 905359628 52307506 482227698 335221094 370665720 100627221 279009026 501554851 163433716 30292296 499505347 534124970 4170435 628017003 526334969 709207312 636415084 73236372 828135373 312398706 384149607 661250302 765537429 46858775 877588100 628213657 579596281 241714440 850893022 108236455 913211522 944060828 688517103 180412446 430963045 256578592 312387467 211822096 179603960 591507004 669282089 483834190 276946890 418579526 795482468 273974564 885975705 196162258 303749005 387244008 210590568 988285729 990417182 704496684 778759817 589063597 681623508 485062392 1764899 918444534 200930313 370052999 914744592 676538925 73446484 558432001 141741126 949837167 507734809 994802001 592613625 677599538 533576666 779598337 428131662 863591946 845330785 757215446 451442567 623014 829627826 634633924 541999166 803669588 313745281 595335248 89504744 257079621 861531283 901342893 984324679 729905112 718245649 866892925 406969984 442510873 767214263 522075358 506756184 5092172 10108587 133434416 54394240 374870946 926330926 724982864 336158757 114202284 176631936 817871894 921947063 101639138 898468195 496209509 112943651 366748751 784870985 237913477 214225300 304109053 872099638 716539744 902508674 844094983 977489019 814615453 121230023 341004709 364366115 770671251 121164524 583313933 513873312 287858093 521836973 740066563 289018718 93917967 171829333 472676394 148177229 670074923 822484106 861710767 716187316 287743968 161752883 554380572 674213372 516769346 449356479 109539192 794149730 579946816 728533339 186069876 829566713 690635749 361611574 883479764 562962469 211815457 62492508 785269803 291038685 680951911 657435035 457068306 969734505 304999323 12949078 835873353 16824356 66516025 387583014 695230113 913455886 77629696 838688476 497323924 452211672 94937792 24555716 758698341 585238456 72589762 665435626 437390723 731083717 952729124 713149234 5904032 135845483 344943690 49780879 600596457 38883929 932397139 180548653 528841889 543167106 919600130 425571762 579676203 392723722 543099805 182761557 960637248 331018980 305360285 119267723 139309436 576091113 306797029 811660478 511225698 480562804 408744 834203557 319989981 408924541 566888207 902794235 506771426 334527158 520118691 623126356 399573479 349424216 230823514 949610552 539182608 375634752 568388403 734891015 311112978 527189514 235274894 493782804 512257918 736387074 800247804 169394528 282907945 619246329 961204101 933856862 611544494 833134880 875046639 541492207 593039938 474415183 530036576 611692940 870436168 968826744 51322496 809497728 543722887 698405979 532781626 486682811 814243394 577253900 288045307 47182080 403661558 473881744 454198082 944747017 137584555 274100345 534404344 542691512 861293661 631094344 461544508 256085582 289805055 537439286 857997449 247609811 553465295 863010704 191640428 769671438 556375270 338000443 242329035 117925572 125432095 278355815 949692272 593003787 609870107 457964681 131591418 611432149 512793118 687233890 381419739 976897388 735310856 448071736 835209203 60426639 222104551 861884074 913396476 455152255 14300845 192846283 762782426 584595201 584575208 872292491 58133968 555531481 60903253 990499523 135666055 706151806 863318921 820253679 276394742 98511556 43701175 89949706 918517392 783952154 979651935 424555664 773821457 609322029 291813875 728814762 686475457 456219241 146518503 207493710 591973953 467477570 295778725 475371887 562378918 716542897 148021308 403874441 224755321 220491535 123707390 72823799 440050782 963618321 997391193 802554711 201499219 548444067 194599471 246976927 987098925 840683366 805313594 158017806 621966669 875642057 226703815 772732460 582146373 112657067 865474669 618281207 824053001 8634365 554394889 680248097 446870791 598216813 959202646 944211800 828039722 87937847 380827036 799829777 729612465 633542591 682530804 310090685 188034677 53220233 544618375 436117814 136961871 475813246 605669622 279856255 544490782 405636194 940304930 732894984 947962520 474063347 754925490 401053757 322367328 603211306 224150929 613772900 994545763 59992169 236559272 837994081 551407143 229795041 684871179 949424346 220571694 466399143 247430581 993664252 172222833 51886697 286798456 401994468 487225332 570009334 898435589 502602768 619656988 89767537 452816858 911251030 129626940 10611482 469496082 736022053 778579209 334576969 982786407 144967426 890608890 790236070 278676346 909859972 143728003 73339110 991855776 857643772 253217127 64724737 664043409 22944861 919581029 529673266 500891005 496564111 610568932 131715953 663871200 443792973 850101908 386987096 41935254 94799052 7512099 528261632 514086242 464090222 154039611 844269740 769108890 955239270 244167771 52625252 515486503 136884306 83272161 618138173 558970315 288433133 92064944 898821588 813562470 103717449 748098469 436569189 835590356 675634444 569099328 186017584 364659467 316231658 776054959 709146514 576614303 910914315 876452749 140742627 492265793 177527841 245010711 663730867 542048979 996064543 108937321 225792934 321167838 397046141 237489556 566971226 457977822 995624704 638495048 142703668 1135849 487665424 263673318 210949203 203743506 252528280 328938384 93333109 329417694 680470423 398660866 29809982 956760381 221874726 499617046 883570808 883609934 440282780 359123519 236320531 132966602 12932170 157028024 741001957 361545841 987068002 402707072 251790289 26994571 200198323 757366868 133269345 668883508 742001829 38123837 999668896 801366102 641748892 911456882 984071895 647648678 908907773 701292107 108601223 602373526 669765037 529125950 402194484 576631349 701204712 760435619 404719317 810148681 176768590 26419031 16335079 452277167 576955884 222322339 839297 269802095 453682593 462434328 462732279 194206879 652100082 775732166 314180725 949641246 682520050 947407715 229604211 683420176 841101530 33306486 891140314 881175832 574172694 999753235 141742098 75712744 141042001 708614651 344855651 320510314 45082866 168804328 374324655 3142760 599861593 378622199 434431437 164836259 500022446 131082852 54107165 532194329 822876935 628638862 839272161 631082344 32351974 950571101 267065992 325136145 448975572 730281385 220515352 164430295 779861441 550785670 944579335 692035214 754089368 138899873 360929572 195158642 115854853 197663621 474672645 727611792 220654509 322629239 319571532 499164394 550997342 104629826 17620306 175741844 840241336 618939789 3126422 944444156 897135237 272849756 461016058 433679211 780625851 434066132 701472402 848644505 763260339 976118745 119452212 235972990 370223147 405545145 283220106 486163278 364698633 922076031 786688968 19828072 701576366 541438981 667429721 669107181 338067814 948728828 627021500 852213880 570995612 980213747 274030852 519511108 479849913 69249741 700208663 677763059 643941555 427725632 343626957 70019568 6400577 961163150 922382951 629440336 127126187 83780568 172962403 592258505 158058666 48764934 732816053 121481102 644464285 751158273 349491382 850580546 284479221 612794540 610056149 60074205 275872899 989132481 763804473 444786684 740588545 99737562 863483985 774041049 661029968 181395500 692570460 59391677 468138626 771878568 592831580 852369558 598351504 545581160 869518554 679188386 106111219 822159691 166201452 127204669 212236057 714898231 224119665 129605896 751894912 179834571 856667379 342032012 303215117 793466154 307266041 349645893 880779852 497534859 728485955 619555827 12402997 996757687 335314848 655699551 883679289 141356564 980338884 278709953 463096157 630411600 720421224 816877286 274438641 100773475 124699974 593046890 284292961 932119584 811694854 18260536 106264583 520515351 778113538 939791131 244101710 485885481 893952949 358414915 853663496 138772083 744759356 584168606 710431987 21947090 227069683 593083944 778600172 799605744 910430139 433118073 59485439 74752891 177246413 447200914 995553944 983154654 674448110 274388663 106028487 151273100 945419699 851895662 524736204 849111031 971656512 474736646 885173649 920571201 394939348 759645297 369721496 245406144 382674290 844679261 530249079 594182012 964033656 627225957 312280764 128387336 773899121 262349965 415522208 497075863 523004832 410658081 186888644 222564642 892430808 927426603 571100080 490023301 50939419 985185680 412110229 206009891 281941351 368788786 12291081 884323867 688769532 620271205 850648339 955494863 205448391 539691572 985079509 519452937 119136258 324088320 756372146 47487747 745813072 810434418 746198519 974646167 190726081 824974177 946540584 415018536 784937064 899806453 93180674 485514973 552382107 122264575 301108472 587813291 64713474 949065957 492392598 118153469 880334587 936589047 966813441 961245373 223493567 947274935 390001960 264647460 242139723 196860644 705331952 999908154 611429523 714728157 358761673 530973781 744143842 277009506 562785007 946270874 740341341 850694711 736421005 589495802 881947290 172013190 22608261 574583340 883803419 149941752 846457377 261213059 444447986 536071778 587785877 500969557 968491066 972295167 327706087 503710276 963531792 49926908 523970082 859371767 622608411 353162100 726823317 156479684 478795242 543675797 791327992 919263376 666080794 28934631 386265956 231722154 253286675 552837907 879982039 631533081 774229651 639018060 889971461 199613848 503782305 133294435 405760330 696077746 785311976 812151558 407840439 42666119 142448287 265033979 437063221 532131426 735197182 164716568 109883145 881356942 524048570 746047165 694322348 981459109 625935243 206125019 909565034 510224334 721375070 830712902 223451363 340299837 699846932 3409719 410090560 865979323 505912147 26870659 218778800 490732500 185502092 306300167 389483246 663437709 225050322 795368172 156531728 200079096 16620093 683909529 865490541 711829670 325500399 858502213 25595222 163161836 361232408 948223155 917184407 399215721 967167263 561395389 82114413 506350254 727920238 728844468 743362657 664965692 897788821 690194978 138261812 756865593 442128674 920349714 195565409 576840791 853506504 699603718 267610791 93421687 383581540 418915220 390970719 481623768 949785113 889366611 992368035 32673710 24404125 189309137 769045457 793770503 844803603 217927231 993311497 374581343 616956685 879839 756066003 216426198 389800210 643187560 649841945 963952764 906219833 912612321 373610420 992100672 249929217 578273193 294454610 655961193 24302361 318747495 712906843 125706927 826084123 94162445 123993809 174002908 910885463 447740278 267289453 586967813 22973674 791965606 36484421 633584399 51422859 667476185 388606710 409838571 447901166 491130915 312583329 164161932 965348402 227777701 444614019 736350251 480134056 964240949 592331683 189233965 327446859 780651088 67380397 443016486 343531082 293373914 875370019 964069521 323542951 599166354 589352927 660994728 213598800 401531046 315216922 200694321 137419786 843477443 423852099 449358523 761621876 413408052 76871360 140420135 735402800 922136320 161516139 465934681 844268587 22527431 403776822 522189986 784711422 687898868 508782467 423371193 577321666 170773070 792365848 682167793 744436330 435043081 90173153 789704838 641614487 942111862 382822227 476795103 247277947 140377172 360667709 968176415 521275722 702340335 834166572 147827016 703694846 580629141 172957185 944654888 711387882 656280549 861416801 394545053 681464080 269520866 824661745 724456651 37075340 759626998 710373760 558409873 142405363 2338033 885669261 434915584 856079307 98275900 603983580 276162138 885295132 137145774 714256285 447044664 348529992 183203721 826343960 496172155 568622569 670757561 929077189 39034438 64207832 899503523 991584154 432278167 157328611 976942311 162671457 591265442 296399844 747793560 518865702 134729695 195880164 222541492 184064808 252397361 877384583 172207939 868677060 925322070 460635228 140339391 375345037 882096609 246009767 868569027 346586770 806930777 833213681 880009523 775029016 986530248 417381931 625047882 718112288 226607191 405531167 31138377 840921634 806808083 358096884 219130996 573982263 1280274 396217626 367512639 708001083 387584196 898566085 102757368 603960040 204315906 908007546 292970765 185106725 946954249 423012946 339053810 910405592 439026039 725543453 214853497 408166717 715676941 57090360 392848070 711075838 171259081 392608951 730730448 422968887 888903880 48884411 828933138 153968987 24796748 596425649 32017598 90066563 193522078 868200475 446324513 112151946 315192606 537404180 341906344 487833216 143446775 836934567 319300594 343282023 378313800 691495501 473438749 22127462 992477146 204409443 250613258 253642775 640664870 409329444 531702805 919067302 107466592 44016603 374450643 894465063 163273394 499111036 948594690 724297283 565063827 987034035 750252286 19537723 908380733 243525453 543994847 735029455 524241906 818442768 165194663 150009688 247293338 157303844 94770824 130658276 906284440 708511680 628238792 558715921 115256211 810204487 882954767 392414876 476916402 837092306 514637749 506755945 189712563 266918373 829141933 346093734 420047078 433099964 174570977 606136846 899630154 320719483 774092221 744219378 82533514 873155226 197856664 884932221 956774790 455370748 226737563 395329138 464352199 686525963 262242940 870705196 394797695 145714604 22373451 244496223 374190826 804250360 367273509 519293369 834445101 449280306 695778848 386899243 311733005 382559270 147030025 644275342 988512958 431990915 640659133 740964704 978509352 300258311 713613947 375459508 525880350 830033978 861651299 77244454 461700103 464622912 671030666 561301454 540816335 41966056 911686263 946375755 878350489 536056490 2383349 353728555 276158822 601071925 708840836 371448697 373784298 728648402 412659373 265990262 446221559 44932843 329681317 347955018 139223568 964333551 201246654 549030402 304011756 876254659 470458458 835515482 662671274 51288498 338124764 253348564 172176045 728811774 488355241 177134750 684434539 406393767 962704168 512844558 514134188 873505148 766815052 882413143 680348536 495547850 429091428 395863383 88934712 948475755 943856434 267846466 168242463 884313160 359383616 408688767 734575873 624787512 568823686 946538206 89345542 316608725 755564044 67600323 676285317 388492978 666954997 341418910 322929080 50138837 270756805 489160477 341711263 494717644 756171231 947540802 118562979 104461294 727213702 720348075 918889231 89350311 132632943 546019468 40205828 380367246 894227943 537297939 953697939 407028303 166268324 950717383 259534486 335208884 649567509 270234650 770007199 976140904 553633311 155020574 713401184 365878699 834987410 583452242 838161240 502550317 197018498 933866559 481383838 459949440 431277250 561187229 148030723 243359747 753882571 662725286 89533576 892547389 751974187 707241094 828362179 835902080 161731038 60712740 735385445 684088779 729815948 577189285 151858271 300058543 479507342 273830445 149863545 760975606 376541341 440380597 966300127 927932268 285290943 848155868 461230138 217066021 28173384 472839019 854590597 238270883 321090414 833110528 936083807 367981078 226709050 517156655 194389319 203360892 5171430 198894813 70389087 417025740 596164767 809639252 799154774 8092422 152857720 782860286 777775603 319171113 250169137 85664273 84950797 26627992 381186596 572220447 552637408 811411073 626498171 418378563 273661341 826501547 329434801 960316471 683402257 359614863 32013796 182746987 289145304 94393446 553536063 847540088 142019924 790971694 568011293 75738552 546720616 959299149 492653408 21179628 388314374 758248063 447021745 905285118 102407418 255712156 657424235 307784465 567158679 948632464 487015880 59626154 980821689 54164706 822425111 463606675 183117360 831628414 702455619 834580229 862851253 187777827 670060746 102955128 824486370 691383020 769241529 480438636 889040719 786246533 936553104 219113363 548518650 489665555 821833961 765089230 724583016 208631660 237014355 836693757 315455329 630358573 733835015 685765619 516868256 424618279 129779784 769648075 725527806 713518239 723835797 844747621 589589425 761733499 423782972 68630255 258393980 484989301 277322114 519863297 448844390 724947861 864264189 834085065 364496798 829707363 925537934 492621151 628381917 486292345 157388522 319410627 849905503 737453413 376801805 347037405 214448833 166524022 41879099 56897641 499765015 662639343 454668699 978718775 410793799 311102078 240164441 422291443 459756478 263227289 903563096 642917914 777077737 935649331 541120036 191415443 289526820 605477358 349546663 171725403 281764645 297161613 537055310 180628627 676496783 151281273 365019311 319833865 953219949 341062277 735081758 214763649 728466931 182549473 227693010 604576191 285869706 616595142 522255398 699185342 149334411 578973730 134880591 377143875 361205228 395220207 408739642 631526582 667918059 934026790 889526882 197031651 744214586 567974692 782757273 329227463 471030028 538564818 230739176 634915539 84214999 25279713 513930095 329482240 654201416 525812455 198454315 91350251 17337081 541228979 734186920 979532202 321011266 808234932 487229539 459922175 560544186 222161404 786386955 955008291 592180942 458035626 926215141 215768842 427265867 596813084 908214244 721660847 892105843 936330892 452510245 499706820 179404492 199587139 281231061 127564332 129412703 948944110 84068141 560672947 576342935 931644527 418184652 350132161 279245409 527466793 56288677 54325736 299238723 835975004 744660792 657654209 236767406 884812064 303473055 509171957 939498439 674224069 545252202 173138731 114727995 3599640 435264337 588681871 831147469 278390338 615754837 660398827 844559358 70217214 649695740 698419457 307214900 239935896 193625962 843620768 206794341 571564665 774019494 27037884 935705130 857345033 866121288 826293165 935016488 188515913 637605220 627254241 46849358 337867600 996340922 667249112 467615241 323182218 757481597 929173295 324756718 439448886 954566645 123042278 738526368 98337098 523334819 987175948 580581723 24508180 607119847 484578939 194886090 347231874 749746396 990004953 897020044 447852374 373688079 237895620 180277577 564973019 351053001 937460312 816363557 634883380 298490519 474790923 787321955 150565285 350161393 955907800 662054878 733847572 524093050 60677234 985598284 634324036 530984690 212250737 698093088 539746035 198764713 502634067 340567264 327190586 275959966 192029931 665514342 786497655 18023296 843318064 623173207 468216904 815224395 858744116 422011483 56451028 125484129 320074341 66052375 985003453 448675644 342120220 449745339 362573525 568288998 599082610 855022807 613477692 604223111 235188653 241851223 883604358 484514805 726224381 173115520 835914539 562546378 945707069 880770255 8341503 625852755 588573498 337008565 988227275 657869397 209295215 383941075 356629090 83990766 44362173 293793068 827616299 862537966 438821741 254511687 562152446 839227170 573601074 937529573 631315934 496901686 114772462 343963537 518647220 33326687 155674232 447941336 220634724 346488117 745408316 432433088 520797354 870186317 104284422 516765934 184963711 163173403 81366732 704256677 558613472 801798415 367588026 53660710 446157098 836409095 246451901 116892049 589281721 894936610 448862039 655232595 862040136 871050208 657487588 812518135 343873823 765822480 273541828 391301438 990591971 524835416 603123557 480283840 229506510 332152226 59413713 636036147 226989459 117467456 937643789 678869144 486538368 342547860 324343765 427119042 761906447 867072339 553380969 512111925 211207329 578977465 854646574 233729178 421410918 982289735 71973815 543188222 267958253 603030384 956803862 235025831 103924348 503229145 968506464 208583234 364204838 703955600 701421781 274163366 261925256 53982531 42739110 616489482 659537487 616234429 270619529 627119086 661208752 462016677 860568924 600986948 244384211 48597813 996125697 359781194 971596563 984649577 628680402 754385929 167292111 550863815 810215880 119693455 456575540 278409184 119771901 543434855 67382599 896886867 522863377 863122299 110124451 995187465 358857386 304535255 521762372 701100833 368711211 863779438 642850746 201173745 581539405 244000279 525811337 824385760 690533140 791287932 178716642 509091900 633908756 658457487 656571473 730777082 974886419 866238119 480692592 263261714 179147454 186789807 183209467 522605831 87925172 858812928 932431158 766184425 98551316 364454302 399186355 369432599 534886655 517825907 758472795 415932480 555456083 988216352 860445284 320625342 341298480 62040202 53960565 64023313 997646522 304963279 782317574 39140130 855079377 937079463 191264479 620361270 686056136 649856636 166596519 971511709 12944491 664098364 194568879 218378595 697826703 753684941 203211917 442792951 377243269 551579499 491712274 419640608 995301152 870301124 997445996 774105058 636947660 554263604 182129824 310372738 68879152 810342423 584664815 850494199 381695297 915167541 147568392 521549521 466175259 177000539 871074791 253186517 196993580 313934344 665255785 760203790 476061707 917005194 696307719 755333339 797106431 698678578 631596384 373461089 996758676 460628096 209229635 16344284 907999102 416859691 522489760 459787407 497683437 531478305 628624196 889936701 361500033 449580979 362048153 602192235 832305645 625000461 508912190 337918041 231883948 689494688 183304284 733741225 492755497 764898868 383071058 515677737 631731933 804642573 269077856 464617380 205380671 614285157 311095261 429599037 838840994 212869765 884408186 903348463 858589783 597318981 259998391 709939391 40518576 212542184 869810662 467837730 106435747 843137368 51417714 301507518 551082507 333720716 784642625 133912405 476415271 793104162 382173674 911205508 449928446 307234645 530882454 794147906 232877904 985118701 50895414 201198740 651432 526843770 762110090 183988716 986839203 890550857 236802129 972983986 666729404 251862391 87827937 581400398 411610256 119608542 3018384 296215551 310658155 804706237 474543935 468021123 612443237 836034240 729567515 542631448 11845616 571959002 216501991 706524898 807224186 559723105 698660152 925902383 610087553 527632346 807737172 169966727 538325434 937213720 51719940 476477579 789979257 510914884 324586877 789954459 870047193 988088617 390280734 117472806 34750435 457847377 448365176 258049196 121411135 256954782 548023587 168198944 865695719 539724766 578723082 35408118 218659943 760509331 317269693 833623909 556288692 441447524 820145129 966702699 892797228 304014710 5464996 460418017 248189312 456851457 726003251 916975917 193056786 299594099 983688782 425142743 801080209 380249077 669801756 330773959 967008734 374583069 840491444 373628658 411355325 257910641 994580485 396039260 683844121 851118916 884426911 818262190 751957399 498716516 937912598 748914971 824351369 948805149 365493243 331050320 636242982 304171294 710973538 909662133 325027209 120390289 694690133 412999766 340528724 947130323 94861125 834514305 192622846 161768125 438548524 318266979 449480254 470153238 870572010 755841265 305905966 542342436 496746378 328828313 132721487 424138297 603142521 329855699 389302081 354264155 364816037 694844217 435453950 527840160 768452164 386972269 441263627 339976299 46524923 489206797 724443525 321318175 242417493 73686025 798730355 821263242 541573453 495302251 827662008 89950186 594153244 56036261 467310958 941992053 307891205 480436760 804595294 922992466 897505478 954408625 847611183 732924283 474106968 569889973 802152489 778168349 758156780 912701182 418140626 15316873 809519312 986429821 799778402 560696757 212817600 846942821 497562955 97873117 107074544 364407435 675184377 284899333 169435652 318840034 46441428 252895334 682554818 185964754 683690091 203910790 24553717 747151971 484208256 188131005 263185000 179366123 369118837 430240974 616086125 386425896 61970787 628692284 621374337 770309219 382136498 664248917 628295596 661071533 767742287 173176989 143838124 56865351 68104291 747322181 716997024 226921062 662633195 684418596 914122291 551213394 339892837 973747404 959242228 674346643 419453838 393988670 586326572 500626067 921809010 18855040 358498752 256977284 218733519 584541357 146442713 403351007 68770049 682385802 493511653 521290789 360733998 991671706 477687695 45048665 73529601 394688209 570044686 704195133 2980726 184390022 506728434 581779638 29487754 932325592 694071136 680176887 934324308 11138015 120913699 390082673 556107284 617723493 949413850 631117345 203343489 246375610 586592872 60766485 341529461 301601860 194232745 936270458 581614927 102009470 555055790 429586283 889656505 596273990 777696346 979892639 160793930 552376401 67068144 424158889 668732677 120349403 262458728 560299016 574865782 984294902 172558208 104531019 430049245 520539721 263021815 501997954 387505130 88110097 642836356 909083894 947988304 879808368 159019578 694751894 513872172 240935917 31422145 557456220 675204117 871005354 644128920 487418459 311791625 879017685 550533954 723325654 302036320 930084829 592770967 443904944 965235693 710934040 993767652 615346185 690400853 181458960 121162395 45652550 578495692 868055604 678262578 502562798 544189311 164004605 836317002 524884910 245011727 638592585 12488889 215680567 816365061 627806256 478494215 159013469 141647045 589236696 400915474 699347179 969304802 887073967 77253729 106603755 792721939 387649647 43650881 731212902 815322214 563344356 109270618 813018574 688045198 305380089 534641154 375085296 898633836 33901327 980246999 272439692 806502624 472734093 515968008 701465535 58955693 205210259 410066102 615280368 565422750 898090922 244392758 960143584 513019210 387733232 808347798 898347340 465001830 219140890 125788073 900223326 730483306 979101324 543166012 206348935 287403103 265005976 137036545 556818249 603487149 724329788 347157658 922091243 129298441 110436259 302136526 795645154 127566517 664791539 635066194 895325410 467919464 842977431 457271981 120000562 956162621 54511391 853066693 198464733 936889917 73195193 825625635 711895209 531712988 857336455 533950842 301784044 302726452 547270940 737930638 483489267 835287123 107382018 523840474 936622300 240377938 94049827 339437018 72134746 593969707 213261504 82420441 76587039 918439579 845741885 667129971 61457386 551170543 779027006 443145427 640736264 600784901 15850073 598401431 892107364 659543343 838644516 830908878 403610030 691950167 310476139 622778289 335718401 221322385 380155172 447947952 457567407 220153608 998697383 708772358 350837545 527591004 6172898 938318521 772112550 992763014 830140024 216565758 568992698 186148927 648355010 703257697 29879121 967675717 272037876 326484119 417782291 980661257 456389324 812146321 849427754 339181837 612228178 455091356 300914553 953455627 301553839 178306924 107681021 336288343 518393932 875003283 661045522 699769152 42801858 723416241 211233131 957354488 935333661 318189161 503037278 206842365 562995990 294705217 239601486 237968233 460997717 109173906 197532216 709646643 99795277 803422810 534713710 399308761 120557225 214345474 13755273 49223589 690831080 138226963 663360147 655814388 384013696 578292667 950958939 633900406 551399385 692143479 400136028 149461437 507868814 925548639 302304941 133820053 822373086 174012980 698795173 693537086 217858714 460924754 550952917 733576753 330362099 663039653 916174956 627310167 167620901 152559682 603370440 540950368 961647217 589260901 663344973 568133812 629246421 617068345 207623030 315622158 333073587 997597016 662003268 962973957 343340010 834423711 882432581 818221111 5356312 127977363 161019172 485703767 678869097 300056609 846978843 2854193 332083526 747636872 736626130 317300497 301779874 23791460 880772500 941914226 346733114 930641582 673293792 87797304 950504607 951842676 671374762 960262338 835866126 689207728 919844499 339746032 467078615 513499251 524202582 847309839 251776522 417576148 361164619 661247152 892537685 185737861 164002363 752292756 206624366 242803730 239360529 513406211 380739850 609642618 677422754 428156502 126985325 573471323 989508012 674975836 137334234 628856787 361864472 502436979 433995021 651080362 691488897 328396963 170044049 626341155 876090917 293136329 705211871 932935870 185467697 501128640 518970694 971086342 628701880 605634982 21468770 13753643 657093876 225780903 47918851 344325150 82573019 317268139 927192000 710658194 973343966 369478408 790646634 23577020 43117644 322247128 500804332 566780537 239958469 420597382 913764901 572980775 570408907 996170984 407915076 53960617 339696004 238560344 586877239 222532610 3176967 166388748 292490551 962145415 194924031 667172085 857879832 43328111 744577623 615814154 377732754 145855106 130120179 303334843 919448869 821888414 63049260 397972624 256720049 712171691 582809521 908661272 773703577 47131478 650269429 661167416 47721140 968602790 791644331 627842985 424539401 917591361 677492706 397191058 932263644 982412577 889283497 490419072 662589034 62568421 745131154 695707237 519676122 941476699 440884461 307336776 617067718 604886233 605630973 426749595 194660748 249853544 119196870 937627276 856800387 184294503 308453486 71412279 394737748 376538634 421941277 976083119 389495490 83599657 852546720 755598844 84037118 75774477 578980508 928525383 843349039 355396609 639285721 728208274 878445295 373573943 956133088 924699462 244323803 358221988 736425285 486436697 937490472 225061408 333840995 20966187 307610313 405284600 217449537 676415564 511081580 925532480 721647927 996710799 781469549 800487066 630435589 774081618 369864741 988935157 504139876 949933004 156392931 475746557 458590639 763449811 646465090 654031523 865385356 98306581 883607667 437766989 873989343 521456320 575098490 542074261 899030349 200526966 78226650 202071824 39074490 782985716 383330133 709921954 643919617 663421928 289490948 595670827 220242311 16831993 576421434 848347163 782207695 41433783 828047524 957063891 886678991 293552871 674845727 900550237 848977532 41482017 108015094 663417570 756929852 679288548 798955241 473827451 72930867 95949751 525728081 8529842 212551547 66059689 717900906 469884886 657243864 77623203 96711367 50848466 389162236 139846832 669026878 263570077 119430415 663550975 653323455 137175342 122507276 180256125 150263825 827550277 869541162 182449126 724162531 153262161 507365247 970975326 525545927 317968374 480117429 861099571 203847743 567305566 631116957 951039806 191372593 616489032 646876259 436288431 411257336 807291285 798151100 25967760 236823914 684403248 869265285 514111359 531904864 384307394 73116075 509665616 532670471 798851219 33552743 764228384 36312902 843584661 912202274 17126537 600949779 691674867 195379318 487346448 113555933 602925287 189190072 512717912 139896319 1779281 810091161 98183530 877722444 261187724 931609375 542179240 663460343 61894547 599647092 559436581 932546442 747033267 812280096 885381763 949940901 585023129 578156268 713180137 984359442 152893784 628347114 295296854 212062066 265620917 784493136 843376750 2477146 29795400 347600876 827116166 698584142 824354457 450979004 41258416 755548551 302405191 397574265 320624843 596210048 631629497 393320970 96154285 12885702 223049996 20523995 887270244 298802830 588122224 819437845 305773433 46657681 746659837 973856817 281603844 666465040 639307780 241297465 83531635 192156578 890751153 826926775 594014681 515308864 668525362 55703506 312425677 486107429 270667815 431056518 67240844 587132172 354470069 58010595 85057467 174156127 741950304 287439195 324904897 326574905 646815120 678362119 514877598 204782044 205094484 944623677 31974164 619994930 339998712 585475524 350007522 143843316 254801393 537127348 253551071 826209892 162686633 73977206 121671643 439991066 831613633 321629211 479075384 186373122 411510653 937676840 120015645 333391576 408996301 629942475 957774086 409357513 180578304 752656670 837609959 316667681 306356897 331016992 959580598 69571350 795906038 348494398 637028793 810630405 767898848 596251702 649426500 960870876 886727123 443395287 649531307 556207510 477791801 160261785 602091921 404400860 472579128 10217151 853335503 362088465 949701954 766446156 252766307 883349318 126769854 572594762 438537854 80209624 575247020 222611821 888533712 885307464 231174300 259782658 637867650 119333198 203436014 660909152 562147157 5141787 634858768 246037070 424172324 595833622 405664335 523122 447230709 520128329 695982394 954963734 321883323 47878033 463405924 134826454 772533604 872242051 935896562 962457202 953194486 415842328 176968814 17119713 612598050 707247367 99013095 3700099 698353489 321888467 781972624 750431640 187883573 31868155 804930838 797518433 127295840 747746236 80413106 419150210 522804808 694340872 29486322 247843328 909642475 745392966 607487714 629011788 87486229 711146751 575264263 543888028 537838454 121904094 124392519 166033533 266645015 751364559 486911044 731829113 587523480 496275412 393251603 964006978 254189980 26738938 39532658 734393868 805565930 361044314 397588788 896454084 612975002 650370627 685437659 484302661 288010082 366510885 38942480 467729190 29870548 326402707 774992879 987448826 996949952 587820048 897213750 655563213 156186343 115854632 50750653 873876532 871118066 16094518 118982872 388339542 104435354 792124577 437166949 751679294 290183416 672060843 362407614 285469016 889253174 499261716 76085816 809274582 518453262 344428838 271523791 467426299 869713395 965014036 495293905 873755401 854514433 601133273 744024123 549936923 336848559 696366900 416950047 892012856 264833718 50868617 23616217 570770163 94680350 107006961 954633982 566943874 203799189 802995809 779551300 404549045 89465589 720687835 437439705 299108945 423232840 508978714 761334775 682360684 176742479 70167232 836561714 226238716 724625728 536093563 583739279 951143821 162539725 562470830 48292157 214351137 985272424 927707696 603957803 717115268 364227540 477289883 622048710 697710814 390077333 285005740 503854619 4690913 768558809 740746196 869457070 554496358 645722171 96302519 178417580 540858977 767713933 277874032 5463138 383621866 159218889 389427835 816177839 148402095 77563537 98403428 665811744 201866495 478925727 818351398 770392958 565638270 412933527 817744717 77016511 481493578 566960764 275504874 524301278 820348153 713749816 318325489 13888408 367006543 472994705 776556767 330641086 283523560 257130449 939630227 630402799 29055824 778115654 143219183 833921377 727561698 822323233 154433944 67636362 435989901 593690710 200016843 20240928 521707712 156654454 939803100 50246938 247685985 933795773 276909619 370319062 400923459 306233944 51586070 503462185 515767126 95853406 174010333 919906228 187967497 712531012 697359050 202433938 229557715 950805037 571877431 78790201 802583673 161818713 891070803 646337761 3897064 672251320 403109599 478736028 967987720 938873639 464229214 722129783 609956797 905796576 468520180 90806461 954202839 469348636 927519527 805547883 481529782 241603287 993094509 930247292 69294274 758210721 992375419 833336742 925197913 217510796 809562260 524765248 86149369 167020296 859273523 392731755 676193670 526369314 604112479 95198077 159512418 949087728 719160216 618777813 863220418 657901829 401114259 449237710 705183828 769783856 719642760 434422577 744305963 533330998 690817301 906223968 819034416 450719371 482558656 27265299 594458327 903507462 383964332 339998307 249472919 594506009 347124445 891365096 557519938 718713021 985413832 533804111 173570790 671215851 623995578 780272482 908367075 330312309 687789959 524250614 197542905 811479175 809719921 889668127 979925653 698868147 494141227 50772466 871880060 782626653 255464130 424514761 620062317 848444304 501703463 468526000 915022668 748152523 638135880 343737465 442169347 149866360 840563809 433623427 653098754 501765465 201036946 662533125 509083125 331928625 896187778 121744449 296547962 999908492 827702984 405027122 389654050 811408120 862151450 909664926 45806142 213075786 779720957 805957632 927336409 989110831 930281433 119784454 261411922 95791675 543617171 242363297 669888413 135886602 826738352 2615215 235100694 824276056 140359208 882047029 353679275 3846572 44576275 12557370 472394619 526325592 509695977 564245029 299398247 243286966 507231683 394772507 727267637 250800984 669002631 485858635 935798234 966823078 218445534 713313186 399698840 12493219 503166075 939652968 620882343 149275075 176308305 14231167 404095684 923311029 371791193 595493830 254810254 588082724 864946982 782467098 369521667 205555862 663608648 572551696 435314809 109146367 648755463 883189173 949437918 543054846 910768592 991144258 859508255 834553783 358296704 919207697 39042013 934139270 437846961 536959383 276036166 825052075 186104527 814981472 652706710 12420492 788255029 298875602 205876255 673124520 818184026 451442315 948393002 20733382 787747409 711012413 85337972 900164398 262753097 259532529 114650351 360127832 277393802 810961295 69755974 260616997 192079182 650633212 787330544 571934185 170253866 815285051 938416061