6164
117525387 612293758 610685752 921757508 428096825 656135894 880759085 147136473 997197291 165419658 868558201 891000360 387048717 655423584 644545026 646948041 284829649 625811943 777863091 520700784 264335155 864222248 54259936 424512052 97106576 747637999 363847550 343442127 557836882 724582300 941864643 675362268 336876058 552550394 449636128 617489234 61202639 330395212 764625706 58399929 348331222 633183907 801916640 735379938 141123842 298978017 234844331 278469842 924789960 12707421 799170626 41641466 729446020 705946913 466153517 679068948 453584911 830001066 22511074 863938145 407099718 816892068 391816764 743975775 221958813 841452891 213981360 283161451 24364455 978607065 194077731 372695676 464307323 995994370 108075613 605431165 294972387 195436295 883901006 72278698 60660068 535587983 113920163 790106087 94051248 580073679 469175034 547636158 262591096 344202460 264090654 669690813 13610879 655907418 266182939 235569692 497360308 480164298 518731142 521724762 458771363 712808873 894420437 923078685 708803242 855012402 381026201 856291980 50448696 117443559 928570677 111108763 505547893 42490839 753731202 599599140 622564517 75422587 147235298 885155613 419625046 263842303 407362777 433235925 919749720 673545716 668805616 269626380 153710013 40053109 791351141 464997727 752861981 538287930 240592764 314181575 245816683 621618964 170473554 148781730 591578874 99044231 112406845 97126767 994051421 866138046 696725906 469132290 941560632 696477555 206804254 213702030 960319858 614167030 499454306 732585929 287712745 20776273 2212308 293939110 60829381 646079801 758936836 813691362 36884082 999529599 127872936 282700764 473664915 150862841 283998845 65243788 102423423 396405689 14886906 96474844 115060086 711612812 565607133 909137070 260606718 772411386 122839099 73442927 239094767 474809756 806028856 526807512 495586028 660757515 820746621 556415408 306837315 432199808 370106769 343721396 431729407 350496056 478938511 905394321 501358897 762937356 823154460 603782319 11859396 838041366 700257162 126919482 402170529 118380646 36056551 662777246 743308383 11412001 588736525 982403150 338738108 247281732 361727013 834324135 908039246 34989985 390739542 67392913 467189792 613362663 411114308 898919198 963858718 890052819 656829870 465217614 505506526 332500682 68999933 517365921 170542047 621773446 644285402 572712575 592670444 532858304 88006172 335978826 396786656 676742696 170898327 735524763 924024427 532625339 422365249 684580025 567615323 813104791 751972937 34805115 278983805 15603596 786240664 242842522 905656414 295586886 560576488 263679291 628087567 482092772 781045212 798629613 103866217 277846965 223858539 549053012 810705269 164381062 885031838 60008276 841123758 55930164 648049391 617664536 441071855 70414639 154760912 8687177 736035781 906733848 43492291 15019585 922337444 682249307 110378459 680510209 977836192 670954946 944189500 605923758 153047717 725234711 257069722 109430285 3081675 333444612 658483297 666303295 497825673 396031486 578827923 191465782 304478001 226877313 809130318 745549855 149808303 963891229 606753384 885844084 723141429 502762026 900863668 645478872 185011332 11242126 178505432 15363875 534713423 122694931 621287632 687761139 700445993 730873705 649707776 556044020 64318316 160707424 74863666 562143989 556738909 653691588 753609770 713733261 880568900 415256439 311799468 30377203 231664020 918552851 768737638 954805448 421314876 522117657 452800671 458842560 385876135 631306102 474206434 920589557 606517385 95494066 460867048 306963377 678884122 110574823 863007396 743202438 271282246 937871062 157862778 680537506 444079001 763988899 394270766 177164253 31761690 706070233 60057807 263425709 477139435 828795444 70747508 898454311 350913100 376064530 209813222 736789234 7370631 684019655 509895143 466404367 632030072 970762190 773367744 310914194 81337012 488891491 906632983 205135609 279278904 64495760 885673114 723357905 681001010 132460231 900522157 712762699 691046816 960579963 976188407 168186250 641891758 899452266 919156912 992804857 275516795 128970133 582110443 135403778 812989788 92005585 601808144 297536211 915284126 227692239 608450404 849137489 569100082 367599738 54273097 848378985 284611849 792462562 424253241 965612859 777439144 177291749 678375557 468485959 990388063 507080316 489188561 632279820 259048933 408345472 477601029 534565728 389831957 912227823 522485857 55338096 856749759 124294000 352874306 772033884 204502591 961324710 473687724 773602672 181440799 380477172 474498008 466052648 25456085 751267601 431665506 802895228 928559349 962557414 123897539 771463764 322154081 613086099 256259935 581203014 21431570 733860963 115768741 263779878 498605137 490770949 319117973 355354895 467581300 671992279 979905130 672083890 485833340 453592853 298202913 667274138 834070024 625217273 133326785 859526108 376484873 417508642 514937688 157560573 380066056 638835226 929024336 702220136 251921324 37800623 135939501 125869245 771661585 104224593 389649123 122783074 594995541 708767095 478137968 62576841 233275725 310559450 587177082 719109064 764152302 885379995 386383202 450738678 363113619 372226338 162781137 739598491 789734980 677718824 749675415 22317387 169070401 531216103 724537522 420991724 569016725 860477023 399377321 193194661 964701615 789026443 315977734 412213508 350309889 794115702 474790348 583585614 104675151 61967429 155211029 721343804 799863775 541594230 24598833 15493745 913820568 39896322 755092235 556071899 717615145 357284002 578389285 886685546 888500104 155443158 160193621 457516828 15920180 559570941 650711488 833138147 201113735 966689222 97868006 403939976 613321275 572658353 987525589 570512777 487142133 142736617 144372932 139522260 536847199 21488117 155016004 303184118 61384438 762624591 859256016 778999582 119908592 290161652 518201479 8408695 445604809 530911452 318441874 314041341 90482392 821669713 147179487 144112479 640875286 97563844 548052454 106712912 670222196 388094394 677225688 9880680 383347362 674114972 1919291 772710912 695603088 156935295 75895029 756987525 919559885 787667396 388503458 891984828 77829047 906704937 752909874 375950208 290132740 71351747 689991548 233131483 745537811 689687386 377243961 386413097 787251229 777812766 493126008 309989776 18423511 22868048 319870455 401770873 696983019 321789746 26998136 245102458 331241392 102893165 2089982 103317628 743076912 390593439 995302455 673422311 149814727 748212328 49372518 439947466 672080426 591880417 673078949 270134588 281567802 902839261 656547684 68819030 680652027 2190044 231325157 699075537 25058091 551195611 953362761 574557461 725501708 980360897 819659918 56743099 935770413 674266251 160060726 531363676 64859689 7879532 57302338 67190768 756091859 106674855 359654585 280688636 551071623 32733533 550823224 832639424 788089146 59887259 753974805 321257524 62077302 985299961 20333060 939651744 389011924 826212173 366725556 114513631 806573069 38901825 23773082 594859833 713168075 36350159 126223508 630544116 44229691 183525846 550251235 800321549 142717052 909905819 933526537 693788675 795155704 336866112 378944450 583244849 396753370 985435607 904502372 311347024 823251919 777351783 103515119 64780194 456080307 322757027 31810177 115169727 361658851 55583258 710029559 927343278 91933416 836253067 410403745 136163106 872295264 960654979 789001007 15012315 870560797 722527543 561317341 518232852 59393654 792778143 101477700 308663375 778213749 858496423 472526750 453982019 488364558 576041869 518762213 944444864 898798895 550572389 59614591 112974097 606155646 622160501 40317374 550605413 310929919 303237470 686768519 183225182 263892448 328285877 50753849 986969597 50813419 464587541 505202448 962723424 257365683 459196500 123903150 888095783 170209274 596429900 342077802 511090183 24988120 860840014 308051399 776303366 263928754 220182341 889277462 870084399 842342841 782111188 273206163 153272760 85348657 959974681 189014293 201757457 140776909 239768141 41243405 44106679 704355682 546445852 6830102 814237716 858158703 983249604 702333499 28367977 432195855 896927652 391974511 457183974 610284017 700025909 86003691 874212770 920208249 975281152 596813520 762551090 609908691 870019682 768340201 547773700 682510715 957354493 602047508 823287623 49638986 643290912 867394302 753994667 42253115 726740755 420748734 900411818 709990358 123082232 781296146 142186212 872526235 173270656 451886537 482810251 873296565 537890227 209539372 646021165 365687731 806352891 261088606 828112773 676372573 29428806 228402824 211399639 986783299 830450331 34687261 36422284 473741242 902081562 642933302 515994357 481338669 63682035 268922526 43845378 39280619 50218671 38547942 764323205 76005678 490434478 99649808 949302242 880841057 309189179 447839759 99045139 115542070 708928364 927157911 644430994 738357170 155560735 855830632 577656820 986011065 890517892 466595455 312268659 645115806 962045108 680779367 126454474 878243494 949701892 22816203 770040464 999920562 61364144 534363669 75926239 551798622 634013476 877744833 285156030 943202654 178100943 384201168 911261075 887029306 311359078 555692068 477902827 319436164 264039051 55559646 157963581 7073295 374671452 470232239 652189100 189232911 3527957 631159925 67476405 953229848 653976127 837516868 805666761 715340271 224396888 734109351 119655244 710926715 464370535 404811273 506645721 642471477 789012440 417906795 529500783 952887869 826115215 7403609 272324033 90154265 915479607 430287613 97227559 142667410 753036203 601933010 331900321 756564159 85609286 251893077 709794006 739585413 89409944 367977118 307442035 166323184 102086468 279613630 877249898 566457003 684424902 236411970 61444831 325953693 654318765 590945613 131357913 332950331 450865574 403681945 423104595 218861532 686485909 372848506 214045293 439522111 974781515 545945613 48602621 60390801 797838689 758396626 652492565 739764985 126373743 959934599 758604520 80976563 92064580 488370769 499949917 776489481 724782739 561394747 954959525 231617855 4856712 86317437 564568185 455722285 342515734 987672779 527100168 29001642 213037636 741145460 321040105 187819151 139607425 369642725 100726303 937446113 128039351 753218867 529727449 106929445 565669817 140848320 40422359 657734396 629219089 540372275 286740228 354001827 101767022 241699752 585619681 106623733 180533540 2704217 414862369 523049273 990376995 941962536 552050915 55930983 535624347 873091019 243750133 675231771 95250095 344476435 465194236 75805797 97695301 994921684 35251594 515881469 135770004 75673952 173615864 617505444 468562579 460356091 971507270 422845952 554572194 409643302 381986036 735105733 412347518 796848404 258155006 255240864 591327291 662722272 311171846 126951637 388329642 407438330 654699760 483579736 751914764 119893995 559385533 702126416 967332030 594637126 70524236 955618385 670311077 244140099 573123828 138873655 557012541 397147449 414235958 111584734 659307102 796221993 846690467 71654619 445586748 957361824 179411835 36914038 620084095 343100032 16382027 8413736 750538362 523598138 344509823 354969477 643492132 903895355 57095893 463340513 498532480 127620128 418958898 21359909 224276579 844599077 12749915 781289119 94262878 426985873 745390205 753569979 75724217 444597023 677740950 521310965 401958846 857152784 410741354 874559292 52769167 279639732 735489379 803307528 803237869 79999201 158277005 299246352 983894556 67889249 762586865 334943387 48025728 34062114 208819647 124818658 878661190 221569562 906107777 972924067 501071786 504014333 726494046 576796002 948611355 256751347 98106966 203086552 113904130 508848320 77645843 19189648 788488051 813135221 822497176 444242272 745650773 980774180 743488623 582061680 901179780 506075487 917005067 949205507 540137600 125824713 74024165 271315142 199910626 832648293 244239208 700982411 189178977 823249605 130294765 137790331 80000951 228401730 340876882 46421432 589766401 271039076 65611080 230770804 84174296 888108255 675013075 682341420 721398786 418501697 264403100 475094917 777093536 33924518 276816775 169747487 12265582 203357291 441062628 64692560 36005583 685301836 765674970 77700911 361067792 895969734 215491241 441068743 976887816 408884474 340006526 566654216 679923549 405617605 797425019 616614196 146242211 324954445 298955616 720157348 743456142 415875067 195252264 373066029 449799584 472069039 542813515 314581517 675426329 983876143 379274076 563948264 521694330 144949046 641649174 882762121 893435131 709656767 176347215 722839298 118541240 516353741 142009866 798464789 921971345 939434884 267595336 920729908 116905681 566550951 640887255 860361822 982426017 688655871 85944202 284741952 13241261 628757716 599323469 688667589 612633858 978597544 105132204 134328187 976062941 599297730 869606660 722014424 308954496 45953874 297370073 280012087 562307614 439379938 78476875 336795311 231331174 198588563 110041570 348236854 765139513 750928824 61115027 600081882 292101046 147059228 737340185 305342306 775816943 189180005 994009895 240967153 20293901 951658450 227811691 996356841 550956179 97418350 570887616 712427026 143372224 868257689 992439113 558196189 160153978 923432339 747507851 391485151 122020901 857549420 739722004 739676766 460994596 800837030 192274999 753095641 947896257 929615183 58437947 723713200 118795188 904964193 964680352 139089088 856622642 45008394 987962280 260095173 142426744 411366248 972522198 138315319 132140288 817477662 549027859 292294265 740910001 296535710 683779416 715447253 6601481 423501419 455124018 467596076 76854801 647399016 220691717 24751057 429530551 131646015 600980608 548325738 36610207 418177311 539931177 745749200 463185705 527893456 5844372 605612448 939259703 830882922 596444118 71399990 500876935 145471976 216210607 94303287 294524037 899990022 809750540 301125518 176007792 117390909 768721593 252862592 764789925 989413309 277613649 46836827 121059323 878594256 595162564 10185881 149287919 135093740 755935081 612473623 515503547 614295804 70602422 307279602 297695077 667046539 231195943 798572012 812518514 447406549 892875298 107042551 199912922 555142189 260684420 375920714 672533098 29406012 628783305 289839374 871335673 906396953 336676200 844911347 637507561 931838763 855097228 786795479 919448854 463548660 251785453 287468752 930360815 322387874 447264705 80572244 989434412 678460648 879144255 654469277 978383548 624535904 614028179 178296470 32194445 874712598 554217183 704727542 904118610 35516839 994566915 627970634 941913792 331243114 472881980 431937704 115598228 180495559 71249534 887563433 496560570 323034986 27548536 426921385 645422859 474813241 507493628 487373622 5790240 239154234 141842898 984173787 716206489 755871077 14986608 748400933 483100026 569203790 453128474 239734987 604720629 300211740 867705620 399150772 631454853 193103952 683604827 599569432 373599510 754854360 487132864 870160080 930405697 514681400 149597816 428344907 989494640 509607795 915718528 995284879 748762028 57561425 831975017 317484868 665948853 846961625 65885801 1565231 268681766 371530626 241300217 873402394 671742366 109005837 125069517 155713570 302109788 808674343 755283002 528225649 416045054 94932217 250902080 198967102 609613616 400499895 627312008 451624607 910107689 543030535 299425837 511386068 453108312 131400854 828870936 971573516 830878830 747273088 973138746 99560595 118803713 214438963 825479341 790546078 175961151 950548857 946259648 478070938 611739552 554059001 6296586 880300957 648991217 109715018 79268059 111121185 510214912 706580066 562745791 272838953 102126953 714687980 636741372 407751616 698605185 318128659 379325131 529484014 65401746 204980229 481560960 36721811 419419191 307040300 827267888 595380341 110105509 626043887 925967630 574361412 32619239 784780567 454662368 681610456 894495584 386446778 792731640 257226848 93026844 207993782 530065800 47670148 922681761 19323523 455421763 621286945 337452182 687263245 3287310 402853927 892243473 484848270 439575737 164179015 644404921 119359977 759559355 754510429 597920215 538043336 181388192 630539454 322823903 636050560 312149909 69835838 22497337 104881548 327062685 968040532 165391681 857128484 868227031 88073442 876452007 176165145 561876738 66420540 863428390 565164048 469274466 755671862 902528669 761366555 919850877 546933589 880726531 531926583 153960370 331163097 69969919 335348561 961702550 245310173 823915472 126368810 315146010 698929161 83766709 642208695 519486044 249158390 351853530 387713075 337231831 80821888 563878219 899108568 147242427 279822960 316788967 469033245 35494822 71833987 230399799 807862050 618767576 963642681 192304984 625244297 294805777 114791254 960592857 109024679 212617778 637024681 235393488 527763788 335953841 319160197 22488834 855439884 568318586 226858715 95669310 905550416 307680603 512063881 657175335 307439381 791886840 826480654 776472625 679898013 898314640 6872423 340276414 369598567 823031455 532581398 994842863 117837232 499889003 807952072 79378262 712506781 444976752 314771749 92786920 633446944 633931945 115275753 341403179 202250530 342134467 437072489 960317297 502331421 949136369 470008984 809770802 593539560 296489637 586243426 273437573 47320628 445632201 613713986 416919195 121180007 998811735 411762057 91533590 498700738 72230480 170911851 63723870 517207231 485683600 156510789 3170526 119615544 271786541 344573705 174382426 466437359 781646193 134699722 968768780 583298913 604708705 778539581 29354824 753714693 217299358 302792396 801035321 515447910 769022734 217954515 636627917 767834468 482232923 728161506 119051557 554463403 899073357 182775426 71670633 384756956 339286214 74841159 356888851 463589106 271931215 531271276 930026465 53577407 665970998 898795244 489392671 123196054 529851176 518747494 876910747 599666885 674056242 530462419 115114795 443078975 748416933 751742711 63429794 83166207 332420568 34997703 637629609 231493924 217773128 561816594 468767231 409575694 489174104 825656082 873164799 761105318 356927357 803191263 667199076 875414706 554502858 9108098 998610760 936870385 527855591 728037858 536537270 54428184 111016628 504168416 497507158 859433560 108427478 413453304 942599766 440848045 448451006 432745727 672341969 666224133 994562320 141109199 75799826 483736423 819281632 801480977 97358092 28725341 457188591 764557167 904140046 11691449 773665264 755267157 801078185 154037206 335821366 190131806 208465390 446837993 694300221 705972547 158787904 802727698 119425850 101387670 243575743 420393207 386649748 768434063 86617340 381212067 762059613 14933517 717464841 581341245 668930845 814822932 610066585 126119436 579380098 366722982 990327236 205561713 121990139 791405420 359598918 457811504 981537226 568064307 904649497 528353798 126553206 63437400 331081496 98495407 17341421 427173590 518888614 256507520 195607652 458022305 637719586 957667264 325472173 207700778 391524860 994403018 22523709 854107796 120522453 454420158 220830778 963366040 659981870 195337268 607287811 19580788 653148771 441341388 587645094 410314619 969695186 714198299 326268371 153293033 812693706 196126143 580466622 184098671 452633663 776074273 642120975 942869600 586257888 967593147 150570378 830299100 961996164 25610438 684406895 935034968 480030596 757754024 750917359 140012465 953091291 358205170 12109604 458756414 799546557 599754698 869071032 621758094 166469348 47855754 775051126 831679405 96498249 355517747 15778075 549131911 984108371 657899049 344517862 422882611 478008548 495088239 253181710 292521063 520698677 790104956 80072383 729272 547858980 830989741 993258088 353466622 41711262 5367692 812223035 841257819 457638741 533810419 315532264 624108088 581666172 90583390 308303845 678164420 298617488 324081919 79812682 282725859 834497320 424330544 705608469 312505867 771935134 811306530 605026929 145150162 601411485 685099311 145879433 1786816 368605404 991653873 355253438 410316665 997021564 19992824 104090835 307176656 553803242 419623099 931284743 135469414 510206488 92104939 666150185 808823975 416186858 598479219 944066185 103200529 22809762 502191005 415706395 647261247 313497534 873249675 792411409 767425371 410865338 790807193 769212186 779470741 782461065 976981975 189787405 631998980 996974799 293878240 939175635 550778040 713501338 722976730 538763805 76224177 815081668 57430342 737564503 83784877 655909560 681630688 186985405 531235673 36338044 455208151 31013271 349835578 328457826 823424679 117260948 739323163 614231872 738989485 371310255 249209288 568487812 561097659 733724620 565462610 707492250 525416606 968757001 273509939 100909687 360037158 349734115 915991355 417467499 87298618 852292583 925893410 621445657 39277988 309645434 657783700 347002490 340658704 860135629 675460315 164083383 829912928 267299829 630831606 421418765 638610083 880040893 989906576 52224094 466281864 407885537 759716343 991698470 376642537 33226282 92608156 736679694 235476748 861115862 6663544 175291717 713408445 932556953 649253725 605202784 94718738 159553777 952205273 435377442 19689405 480181940 599460824 849602333 599998120 82808781 123537449 91124555 962849673 113444024 143348648 281647889 521329560 755581342 273346358 750488448 641323975 218470865 339684494 876800723 79586727 346348037 904608791 645511523 131421342 553862516 103230658 226140079 713416292 55435930 661517520 585622048 388134221 113494695 287740732 988132341 196303475 411278180 79256895 11669500 524722203 75121894 293317388 898568114 830703235 419180097 649056562 324543562 637650961 988741055 53860636 717237687 187605443 958469426 215265561 171543136 364848293 318496218 397683215 78264584 226448500 911717086 516402984 614582720 25211781 804143715 455231412 74031607 215421895 387004658 85701106 592660449 314642903 231534845 491228563 145346138 650714941 992801476 322406051 140882254 834058882 376266686 858119940 21664324 334736111 73385501 45723812 699584404 244398070 443407026 630365339 470846569 207640463 146768322 85429289 85368595 803428389 393177052 159400202 18850283 632698062 97617659 464027083 947340964 181668856 955255645 945203453 832383796 800573472 267609503 973266049 634632353 643876188 683902341 508813029 831128651 609804193 554536840 383229406 854202262 850460217 13594744 177565183 58100679 12879418 115510823 143469274 668824158 508687874 155385827 540190792 141385935 253003485 4217874 941243251 434672340 811989871 886446703 119572488 612563342 6572558 945354888 99712047 502965097 481773580 461041427 334093747 91577772 15578266 717323152 798296386 718554834 583434248 975861568 776655512 448830017 91372390 772641137 117654174 452576615 928026963 510361317 446478902 33546800 514579190 240238504 468219139 179085412 126685206 440307978 791648754 985774115 385662866 743877152 488739212 867436445 204918578 675349310 811530569 73013195 245188814 462343306 791568028 828623061 290721225 420739891 129969429 234609966 45897380 100139954 539702932 973924342 610501270 986181833 7471141 977596811 78936688 328206632 156682223 58138246 768514609 800847328 43912360 6693826 544724479 385167923 874130271 602159408 60517233 538177191 675172602 305706046 853036848 319256981 986845458 143758072 592513223 116814886 230884389 638410602 69471191 770587320 612334944 532488812 609285505 472322436 510085622 688222192 800529067 519284196 746360437 569043676 320131523 642789149 575737501 717372353 27957071 302384123 319531760 88474303 693077665 847220713 246696700 546114512 18994045 86058509 542388935 611507268 55389746 625789675 249917869 124860936 248893347 714769164 657349747 858178851 187091600 19951721 398917394 987620666 539235916 997794183 409180693 711883791 640583331 837434546 429256143 521056753 139818668 601304255 462047408 685412685 448524967 708744107 84043548 467519012 794802616 626432483 79026279 850192361 104738509 181460499 827569649 353631855 896229663 337435747 64327057 935837614 357387467 463244451 775974631 749139735 313554985 37671676 461023525 954138315 875106221 742796019 327711419 867441240 344100273 789758826 552853924 645141592 351019285 636897472 112660603 145821900 115846306 44203233 848530612 220584814 78180083 528616612 574216669 826926097 866052359 638543725 762763710 75956177 954304527 391254693 825095911 267859511 428926368 138635787 74514177 304032588 881431806 402225596 23990179 78048430 44500773 576844103 723190021 395520057 66257926 688366975 393858308 34620583 585086559 94905272 255205396 663266642 623521883 681938416 342709090 489574241 172998493 105472800 565530418 127303019 349243844 243142680 247678882 778170211 381778467 322193058 82202798 263210272 576935005 106192976 341258701 621435778 535553430 64448722 16955834 454327707 605332048 410814142 488948289 190418607 505719413 744153685 706201600 129241295 278608452 48910689 471331888 451606944 6899840 889378657 578909963 356143683 132521336 826588844 134313893 514299802 1298253 69033042 630026425 578233258 27742370 971285126 52185387 415812151 888250199 69141220 870139858 346098598 332471713 211604498 536517204 838191125 955758182 95235155 819948772 86882986 144145844 143797011 538489929 3562035 33175667 117399891 359705718 18213354 796505086 346535962 385029508 650319691 268085356 15055932 81069300 148344077 838857409 133254686 416672579 579623959 202395905 139328788 925722557 534867618 350933286 314756112 225575094 159207819 409991267 898040217 246090804 554137110 41837227 784580733 557699144 927529245 754496975 769921213 798258951 403518413 116457175 183288458 53838103 237058882 50860741 134907402 237919310 889718150 268162087 654591888 469342108 323074343 793920676 247581016 857941960 144853961 562337128 936033406 304061779 972328394 834073622 550152583 378981855 728427201 187249667 936680998 508472797 941746641 559118563 159248099 345265053 528092089 342536556 251619507 765150970 393397297 386526908 3070279 135631798 507205346 510178518 604973905 830279689 304099193 852554921 540738000 301469505 267408400 476771405 605531284 239736793 163361379 8200218 618718647 744304931 195449884 407915996 105294079 137196524 967034558 264542178 334977929 347642998 607078733 586597435 112793967 852992381 825640695 968380597 988624178 332846040 331075467 446114435 15642080 635174659 151185707 556380080 936644164 418594106 33151484 394691799 658330898 49029214 255408368 129565896 793334144 450858251 389998243 898628223 440571126 209549153 15686752 628065406 557192150 622765484 67179193 522502469 328274217 892819887 343399417 316898394 78182278 674474883 763012828 93824358 162165894 914198534 650204437 98810057 185308991 535872272 346018207 843639888 584901486 601426574 825722135 230751981 904801176 215720378 981896555 197888653 425269530 997583306 825954059 982461679 472865142 893133251 357480499 801139358 785953137 700879916 118037751 864135414 375354798 733566931 957959771 537520691 500281816 460680559 488847099 685590807 996552831 687381657 381747046 433970668 141324582 59985533 664722648 46125757 275705910 499135555 244014410 553491791 496718860 69968468 388469821 969584001 815618070 745950320 623239710 454087558 446830235 593793813 170739323 674701384 179877095 128699094 64738427 680158910 441896004 553585525 218266068 438448834 93483534 452529466 872419501 234808115 512514998 389658501 280933872 788220907 888794055 377464633 194229049 238029266 299949452 582698869 60129619 115567521 328649188 683369328 569655078 627995774 129679492 740394400 302697158 309556586 721609845 367435584 989715496 16022201 773537460 60497915 454471034 867020993 513027380 179406887 101829108 25542377 421581739 235279331 666279635 162892145 612743963 860508683 400921410 912693414 295723904 313567380 28260934 624373091 996936708 450432363 104885217 126616199 43343114 407582374 288689137 617469311 627534309 130920984 633491511 401071768 191418898 87962544 120609113 556962630 119885782 222438220 435021358 541467520 457717550 101300993 704359664 70461512 814326027 957797426 835671277 110049930 271364805 716448562 586939373 120817864 19397276 691824589 99950415 62740389 951923314 388639551 680209699 579457622 519560534 166217561 833045741 563495783 106696457 953654853 120458412 226582238 28609424 555479770 620566110 486326973 509297114 177442125 409304836 176139492 135239550 97492464 138705774 259120707 813941025 578161498 379938570 833338300 122502438 332405336 896078689 74425751 721044886 428804739 506399724 93121771 595022300 339445464 656617554 701718756 145616669 629592317 780817345 174226092 37588438 401383454 660553065 546885551 578825579 922374252 575541395 566581480 19866716 714247168 825702186 833807740 144925017 58157108 519662392 267427454 390562443 268257432 341853204 111607329 697062170 848252927 57245451 144600821 40214742 566379356 698835928 185831410 195971673 479653273 360057502 233560110 733553078 873126918 632962013 164895008 795501169 208503407 731476488 667884236 775266926 557178673 354208328 920191942 615335780 873870719 187619395 5898223 142128150 381988950 970021903 691706671 82758228 879783705 836307492 122972969 446163061 387659771 161320731 494651085 867313043 521378232 728211194 453382473 247021501 213689558 618277480 42522669 422192964 349753967 562923257 49976241 759448992 917131584 970168182 227301123 791002302 10303928 85715697 785646803 392292877 55737599 477353473 475051104 788037656 166177316 598024073 86717068 553837087 759344803 581368152 273666481 133239386 162095697 727048953 380260886 375785255 197842785 275299906 797978218 547596751 838223162 847954459 159562094 607871097 670638992 386863217 251389750 680942920 472578913 37036552 73235796 380832864 366906377 548286900 168870519 533083692 998827324 255587586 939437130 610688478 836955737 65619963 743927863 999051433 792668915 976705100 227353039 990511699 104521357 25331257 390624802 942744519 725802067 550186895 403131967 248957410 937050111 654521717 929900329 262145376 691558268 3136125 642978239 58464644 403939376 811848757 444064688 255283051 919952694 236018169 865971528 609424782 301638131 462415742 460992566 94307046 439120841 688345605 937335096 543642197 566193213 180476249 338903067 144511631 583179496 742035034 393469040 372745958 249073102 323369369 634891333 940631369 179021845 277869571 851612365 435477572 942234679 148193404 690760622 862187372 384211572 556732149 324128505 685849703 19147890 785121071 632673100 310785082 473466675 422524547 706943630 39659887 455517148 45846697 36687869 38696643 640398082 430156908 411442600 889471183 753526276 46333933 682618903 785064472 176719855 386747619 220542043 118954534 387457374 911302664 833658257 771668946 320551164 10303114 310035000 192215405 795424184 795224451 355516838 121407210 70265349 62460468 13583448 525782496 960823516 50271316 564479138 453737949 480428223 828438090 195725483 86470851 727288374 878344385 871535322 904008228 117608356 92077365 875479113 505065729 855896380 561653722 129251026 28963896 571956835 291802377 73695652 219897370 87026827 429212490 341304579 157292176 491672957 354888026 683074671 305012824 405159341 100070161 758750772 885587563 928508250 954476254 972058413 508312975 685336990 843593735 264837554 802945345 788187451 140316667 160527426 496600182 554486740 142294803 378080429 978959926 434097180 451776081 198857295 521124006 880988570 540161873 530932533 225177878 895049898 66523556 530190701 152725590 166593716 288941472 38313152 947618317 95934077 10371565 455931291 781271066 706481651 720768844 436732763 347185453 713601862 597260188 696301986 120604953 739554990 74382415 99564878 26168521 526158495 150938524 547292527 259663416 543616748 78225059 484841293 291182997 144748614 15031993 443908586 163858681 156489816 482221738 111476997 252423892 345109654 419924639 33694957 904107656 993209835 470427719 103809460 559328048 920204258 800111445 679933001 512275600 874493859 632014230 538444120 253168705 635469106 85736646 512832120 179085853 16478057 997673412 470268850 13743022 865221756 914177435 30118055 21711571 248915524 994111403 274135462 446541529 266552394 160346771 350649184 259762228 630774489 454458643 819090275 403495099 107086440 351539627 915770698 981580298 836070209 454214817 87265355 471539314 392467815 452613826 503141518 261462223 302803590 973410367 127721596 168025345 740104154 10356002 42253268 841536029 4467405 316388729 288077558 271019798 476735499 491243093 383298377 960026340 945701736 54905003 363521438 52788175 406444630 131808487 886884824 95031190 586023303 826666530 566570503 831007469 279280356 69712020 92469691 582083945 895638739 72707639 602625641 488259244 83063640 644878908 182311624 87531044 961267637 470389181 211067193 290519487 961632274 594365569 103062178 759850361 649270572 466583615 665154887 908231553 598392101 404556062 3262742 36931756 83738944 422349596 867939224 363019299 344577967 812925267 797619595 92733057 738149257 400245235 580992300 821212896 45124143 763303924 761260292 858908131 86209456 824843836 1943969 900358081 271725757 105006147 512724793 920996328 424106113 30396031 681744232 22498214 434952093 685006973 911946321 518691036 107356568 632401896 734226686 304450886 297843514 531846280 397183943 35992770 784607866 978176242 709722018 682248360 593996517 323498661 393672842 532722325 148342496 395616811 433080405 420068252 353139309 945805198 193580931 777245421 976201228 875325162 652259986 263669672 412848486 564206306 634877059 372721405 49124554 369103744 677172291 346968067 753466375 74356233 382960837 538074241 905048826 92682854 72838952 351561695 268697866 466511794 884284019 417040361 862128604 169880775 689624965 67784264 968202324 883205895 845029684 796919904 611047409 497289670 60589575 876412246 914012327 547982986 101650003 963136880 917086729 778822293 310104947 523069456 705694877 545582135 61143696 463260054 490781340 133982647 667338100 759479205 453010792 404138470 29035917 167655747 574019245 718660881 235440010 394737920 454383128 80469694 191657823 65430536 430275715 104763750 794359133 344288041 652746735 896009135 159941273 422349815 527347779 470046219 945419270 85559007 15628353 859079317 548819061 358926044 845578316 68673512 118405248 151105459 472811982 147441164 318761206 46831226 866102045 554201215 294085497 173001524 634670908 485743320 90948411 64946622 443023421 885307543 261751015 95770155 781316678 421692287 370636321 161180808 744254857 168571943 246739815 612399561 880167611 795558875 971325604 578262278 864232386 89730851 729367737 189560719 89688366 48128942 88908296 808306762 602330156 382993793 981308285 89517416 868737112 72256695 6980389 164276884 957564238 121247755 112563390 591397267 542940041 483199710 752578074 139711249 504288004 999317888 752110809 384455615 647393114 723436412 962717892 364141852 665683614 544601980 553702570 607888332 592730921 642610866 416195093 47577429 25604658 250019730 137094844 746858121 322276424 996591584 911135004 132357013 117839339 23698393 576270631 513295731 359414454 181365057 653006980 863702458 33199296 405117788 100674424 680592410 981070552 915908667 897250613 499270517 460510647 303469534 107158848 905757919 946080399 375870293 953335347 824201408 625890022 942946542 423575880 948166445 792054478 187227235 933039810 909893816 63441979 509310440 275705898 275372785 690675496 928712877 139075242 723874792 186347017 92266017 256983553 167417568 8174683 6750517 666688084 321201681 310220050 626363284 79475952 108816801 2233576 32811298 933018208 628123597 828274192 209110440 428806393 472845021 248854026 214362554 235255188 312296005 723672994 510961085 587668789 266864841 439673962 579260382 843255984 626020978 524042750 100239536 645954897 384733784 106990052 165159332 705935465 269726454 791522615 785411416 378543254 793756190 670739065 164077813 274396138 351529608 373188252 555718883 824374628 622042278 770081436 59629815 786854634 346270781 423107252 227039774 613135622 862781213 806300155 308907957 341318542 182859256 261663845 987273438 567593039 221170248 4949121 126044855 490896701 796471736 911456270 869439954 442744277 434711687 33517767 717140415 638757646 259222370 125375649 315648626 881264647 895457084 227794792 520635632 241727865 650902043 747675405 707379838 366199607 406491911 16287794 707518148 589351166 277951638 547307937 156944205 499121886 552257058 282989059 990018586 201245145 46961681 711974892 643989421 334189719 745492658 213646187 972947364 4715027 339021835 288595989 738496026 234478919 516390781 111648009 328723135 19809175 859323414 36102972 386008782 265815324 52390765 93526929 855166490 182858755 493351218 864627046 534496992 898124627 132456 377031929 99369771 47094136 89006820 743359191 381283854 687015829 957005378 206747570 544247208 148543564 495343558 135259585 383022482 864250690 246907593 711745616 884059865 106231006 600364939 270068646 224562682 505272056 216111926 79729171 688130810 561979495 796872568 75144153 460104121 797005023 452176081 411990243 844099159 541182901 7865786 77899364 80715081 964871163 284646933 624962288 113414726 632506843 760221872 348953560 496757532 7129465 913215527 233333748 113360470 513580466 503402393 190439503 18852521 572030671 122685025 559499682 134010165 919557592 634643834 446630638 716562615 86819914 858620880 413178125 480519166 866486665 343593840 561234247 683874179 628240773 38712886 649805257 113263967 798934758 998758816 610021498 806064222 764490694 843355246 771941043 130587511 199273990 962380546 1956383 771304660 85065570 561456064 757831177 857139514 48616249 204461814 426218480 987952515 63082693 839396604 320988032 782085710 35506795 882222278 465959888 663747567 920935164 115765144 777011533 572386273 967040311 239549383 230966846 584047357 935420980 2907888 714634867 134694969 817804785 716591250 758515981 755386707 130563665 368863509 465042572 179179914 573325322 891261051 19648780 488924366 583174006 340636811 123526427 618680800 75375441 589486315 134944719 996310604 557767810 911956251 421213228 377324473 4021985 652180073 961371829 939442964 507604312 528523047 926654285 177925449 245114296 537686617 933312155 375677961 906550125 250871078 407374226 332391798 142132128 427023005 673832515 725306133 767659815 797358942 196503284 843035255 239361608 331448002 691862210 797129417 95920605 113075437 26970241 99942589 765255509 840858421 891901905 125376173 369381468 671072541 303301621 467012115 61275509 89130127 842690075 967825633 340001204 102580652 152733782 482133331 529603656 826566296 59955815 297263471 476441589 256459098 140298725 715803196 587907100 684677287 365448965 683827704 797752723 392419205 636286644 415524584 85793978 528188548 540900756 455175445 51777440 844202376 922187559 113052948 933332502 617393986 80878580 125850057 719974637 86128713 607983387 102094645 765211361 520455553 399358115 241652949 776914650 392173191 957456145 217338101 76850477 175421461 753682156 727119552 567840665 389968800 995160487 653634642 770673699 388577594 961326438 822451139 85296321 736030349 935504086 18628822 205940686 868899018 144478878 925915322 955027730 604978616 28009966 572755442 125434168 279884432 814408391 754865169 524573975 624380887 824719622 453940803 799802347 578401777 33576706 220159363 820886928 28737192 726310357 591560627 417314785 687636794 266528117 502611105 276183494 202032202 373756278 482124179 70931219 370751507 260555853 878475301 828246474 141082170 303747094 806196993 420966602 118155484 413578514 945540576 595052722 238298135 251997730 247371420 669216263 285574436 320047135 490103191 314311627 46357491 934180169 584142764 586510636 200708285 86753868 862694130 255256838 313026498 344818308 178704409 536294356 605374160 57179709 364540830 746456330 213443154 23254174 19939283 184114990 436832687 817996210 779167711 675130821 69993939 879055483 196863436 355568374 199102617 686966626 522396353 97976459 473663146 106539116 684487094 674371430 45809335 547181223 929628267 211352184 744515883 108332675 747646540 202406394 18028735 112187369 948862723 83988241 135441542 821318357 268103230 424790581 639314566 47270940 99921401 561824857 778842774 149301188 917393230 977945390 836267813 292305934 75921848 162447310 398845049 612925294 836818739 297170736 12622868 618963358 508522919 757138750 579812384 256169458 959545144 450357471 220873178 760924218 534345711 208831072 582242575 802448940 633621652 74073492 702236231 586059404 635898348 333595357 735360592 405807930 164057098 424144756 698113863 92495298 586592066 949475264 705420591 275927156 246645999 718043458 747406865 755168917 475182208 179735601 863854727 287243703 630093071 84727904 48167920 16955133 146075327 482926846 671920424 632213330 557000338 226673006 70789086 45415037 560268362 806149677 303739318 724325460 82810784 1853181 816820757 521919201 803844796 522241347 797846357 50490794 92801156 397769573 658176062 567983363 577505173 374547140 855227065 60114595 311791396 755911337 77069727 457866722 238838182 748990150 90080052 648354871 975663156 13385489 693769908 388447869 819535165 997509225 112773328 754862300 851878757 929594084 276781501 508239904 304351782 927144209 411247049 397152938 324913781 69423111 817652652 902418954 296486602 525396069 962533548 608277997 281307405 892119627 66144719 372661938 493626128 8741122 21016809 321805635 22126610 567303068 710253504 694178126 417328644 823026831 301556777 121723753 605137267 578338277 629963656 762005400 357998837 41210705 11674689 682912618 963150167 829327341 437847923 259636768 354723409 252897822 867914765 488547165 145017448 786575835 861209102 491159928 647833308 882225910 812965562 522476269 302045329 523219065 69170746 719373973 198762248 370727522 841097725 656415866 801582151 471061380 418421265 159580987 364788436 430095954 695009956 327938602 111939646 132857878 440091722 466663054 238272052 160522838 955210218 235805851 947098672 668935671 726965778 447448331 403677933 392447692 822440951 705723261 915666756 891611696 425097233 966945355 114855569 118711309 623361220 916437719 589772689 894298837 928535058 954561124 176911142 623545013 135016078 288850787 608919243 575107799 755513840 699707646 735630636 563240409 935513496 535245659 84692431 514995626 835210341 488370363 907443317 657651291 194093624 675626424 401779338 471707208 495088131 369151258 590418517 118449350 138105329 32707557 865264538 66640386 987268680 42175679 542701750 974801109 331026465 4137344 402425259 939056656 703844989 138055894 354813416 491874837 525817904 439505847 6870462 213544596 927876209 766830130 871195886 121969832 294972905 125491575 446193392 790061035 494642833 36611908 761026737 632748161 69319464 478807626 551904898 909104495 520983305 94606647 883905604 704526121 98743991 138847214 643582777 802588979 129419460 998396192 146980167 655237363 290418390 6366980 868781959 218294599 773197109 592494196 192780782 920686366 570502123 638974173 563263752 65144955 528102432 176806840 550409467 597421895 655614466 102314364 359042742 29114122 49437362 95464697 733640242 697704 234311910 229739370 803286683 363731369 80651914 950266849 18968732 371070303 956633829 740267042 589364901 582347289 185277589 634662035 355550006 755779711 126152559 918813758 673441017 654254991 95620597 76366835 104193237 751235062 31197550 463235978 780349183 80634912 558700674 366505777 81332615 793012584 596245146 737135649 156743952 676897059 539918850 28229035 47967362 349069030 621012428 489848614 783932670 806290017 124510648 139482676 414586079 250663207 58296433 940543448 904918197 6433381 16910282 9111433 610184795 900624184 324863763 243050329 833775447 883564436 609556105 767624413 676577019 205801251 357276414 685837323 882698309 897195263 714066357 783182022 98780644 187595137 273030636 882713313 993885153 250057635 874712340 260987583 500720841 785525124 54047382 258155389 791958505 70957664 119783174 254659651 824098199 444646936 497709979 657873645 180727723 107266084 278014409 857304742 165583686 635290822 395658416 48281994 385002436 109724772 683980368 483783079 149836260 957011003 219012744 143721412 59584989 93725083 257225347 560305830 731766559 311272728 670977570 376241415 234746743 790760743 630901065 58844941 87924030 128611043 569234937 268651753 88393478 847249346 978472846 253977163 335056519 374131261 154775509 720058955 336372384 838755876 56358385 486208644 648283230 275371128 482446407 707868218 221612563 592188105 120690399 953379121 903460833 791667969 182136887 990723927 434945063 813037951 902085220 522869093 941648993 323836508 644037197 30042471 23602205 622510042 136535985 358658724 849157654 291311493 78717678 38046389 130067368 135076062 524255032 778350597 262963542 859217791 338735167 484576104 451405895 459425565 290471576 207383079 251093533 472608462 50623358 686038596 138162764 952708577 61424040 79811756 276545084 705461236 962370578 300147289 180487629 98906563 658806012 29645282 242734407 590040041 67691670 372801775 725116102 444463054 3668723 988079643 156197196 342403889 325172098 607603090 801829454 468160025 667502521 905439338 940768486 718125878 443994285 78931249 670834454 505418324 11259357 799895889 63395911 826146286 100043177 96399891 777569200 611365540 126045172 20303607 53921932 46253194 245621733 779038034 343232599 101806807 619634028 499429794 444210696 797322478 959549235 98556501 265482502 627051755 3995838 58767340 197693984 300506475 990214940 868528437 805924798 853990648 520940678 721837061 532653286 473500206 818236951 162738837 84865746 796798475 35558795 138787677 695568020 281180527 770342062 38800618 382987334 242492442 390746763 679714381 39814919 202812349 778270881 157813772 829864104 634783070 69097463 27558087 935289544 59312403 748602876 593730694 913303050 122059905 168084106 298472687 595560110 986321056 461211524 532942207 783119530 496770318 524246236 331203901 777950845 147104649 222520870 13454530 389597090 613267632 693168910 281928360 816079981 323956142 292258484 498460436 811255563 361355946 378534874 599061459 420668348 979654101 45308504 186487750 101714005 213392609 484960436 697274115 199713664 946171959 82732673 835349546 295458629 606978908 166553446 73409473 754083557 389074316 939380354 143680646 854858299 485065615 278125358 523454631 809021756 570383841 21915066 472793670 931739786 252966292 71855128 204924486 85136744 117163631 243928587 186850749 330556239 728889022 736641215 382786255 527577333 819373887 218135800 823035961 426352795 237205597 748961785 32952703 626279912 540858490 29149700 333654563 25924104 307275057 857109193 687462211 730175249 731540611 160255880 514431387 984506902 84627360 719355872 69643645 201790990 963284458 109010745 384863581 544689831 845651959 767649835 924783515 517542198 985785634 600335827 943894992 75507582 201813963 976847694 701787494 742672452 5997393 35442056 768596555 165788802 745067600 308575117 895964050 476608210 468830997 262911788 313631463 553458356 982267659 235791460 607765697 798068468 197318556 992629277 195274651 42970515 760279111 120058165 413029064 598581096 572910344 209440407 674088678 774724306 38804452 228392523 517396758 44801844 116350930 138509664 63106997 861418529 447084781 811587399 190543091 768432129 74499186 356690905 174406836 909283197 592482364 782172532 559868016 789800920 774801809 755142666 685287786 387597271 727717183 98316849 838694719 153143878 160273607 365299748 927868183 199078058 593692270 297781292 96396253 562559551 436290956 159503250 276494431 735892088 971090648 467037521 504324216 898106185 823728426 678731051 807389381 268727141 313419934 219773749 911044412 88221742 974916414 448848549 328335365 555149948 399681749 19546435 708293825 559955355 384846182 488678360 759033412 978538451 786459651 855429665 393614353 75266958 14932914 670108783 811159045 838539913 137146304 167999612 589162449 813391081 846730662 249068182 934634573 12666948 468841930 845678985 100888689 296274695 147043885 281740405 851424643 546725634 301286839 412234819 106680988 686133020 900913178 865714400 517187822 539889181 573660416 910802174 615156138 441109681 433427309 426315183 132165945 423089964 594314794 721328393 88997396 293561808 970396574 23631968 306228755 439238503 721827304 259633795 735513198 868871189 393890552 439454192 415596822 695177390 704205362 374794161 233826762 457634892 93024912 603530935 997524072 666685327 366849461 612680209 107795007 800276769 891511743 239960951 223366732 338342889 961289344 312364127 631904696 784202269 188512446 790649802 75957124 910339750 50283596 811470321 779210938 296690499 103440864 47324111 991867889 807646225 422118271 78211002 117797468 515143183 681741936 115321539 34344861 48591396 580518100 142139868 701384516 472029842 234617170 924751247 810372730 48422865 89631725 294793777 832625134 278144171 85443578 908582257 41000272 988243526 572568929 820211209 137450376 676009792 720051671 129318264 336172368 142169941 60045617 453969836 509829475 594303905 421807726 544174336 495411652 2325825 538830555 196796168 326872019 773447724 974063766 137244748 821870589 63695491 284554877 654495722 194356013 222514806 415594330 235356284 63274683 988163258 908083844 200725059 516689401 628135514 182559674 852861768 622821806 95121643 159347955 985167633 689425547 581155681 381858320 184837198 435997857 920688874 234149717 762869875 694136597 208213483 752630975 368523537 124425325 37185851 23019258 171297689 112217008 291129939 406653972 28008043 279293196 167254167 228733101 795982596 795389680 263809126 501360716 270727837 358930768 513225022 108411821 48356314 94380702 490270140 85709864 382894911 410959013 319859580 145764785 957611962 528073062 898395759 326135498 505014738 788097961 201671108 676312426 752831321 492801046 82966397 780839363 624610594 102736915 9572463 273109541 898126594 125897940 774470256 21370783 484828708 140211630 129782603 533185021 87108683 620052743 618894884 470003593 883528107 938754464 615768378 841140068 319343877 366680488 19791918 824358615 7294801 73979377 353187392 760126121 566780422 288670141 393481835 43907367 391407055 255570649 317016908 142050001 381468588 91487163 163420783 866297295 84215144 145719737 251998668 171323827 765772479 870893551 641327419 501816938 662164366 109612148 195473357 834024595 476292636 215265274 510899561 336103788 289244650 864086952 96229908 708541424 152757092 342228094 752448790 544164147 597798742 69465697 686214147 979267329 13469212 702151281 845564624 97684355 847871017 97563291 269008181 466159848 820973193 910335600 967976785 335653911 19947747 163450141 22194857 348756734 231231767 533094417 684860521 520476416 397181368 633606780 81534191 402454812 975834873 833982981 946618958 426149966 903448677 485349456 405417295 769434240 40017088 103498270 867118595 887888104 53577912 988643127 354047951 727067456 751495078 174541087 62721366 623959177 337991228 84916222 972715910 569222994 470526990 510092783 942215761 867708358 996215914 23749952 122679521 824567139 857732932 69298478 250717104 613697960 407164285 508650750 235648552 447181372 612149019 102767146 187585827 518243282 943926624 541633778 245310738 695421702 716174864 160548455 171897230 906682443 97981029 144613139 328421788 568508018 507222273 270637549 288732727 355954539 146903852 411412247 180521677 4636783 333227076 283755132 470851094 592907712 792405882 706499645 40089083 257071252 661783142 80191262 775314534 458226118 621825039 20625271 6164171 190516254 33690077 178061400 97198697 131671105 175190890 278136836 552695475 682413163 548774384 693944553 38367701 695678235 105356800 71405729 552831369 291100227 355160860 876198815 884007939 83093 435214811 776613373 257154345 96997953 856804634 32468878 407740422 331146024 905610500 413904592 374178630 939300576 591965991 323893678 923488033 767156880 602030513 328699859 302086394 3321249 22644411 192970446 698999483 980517562 264376174 104347204 124134141 472053386 980546018 860658431 472136478 268277180 489788155 729290822 217791484 199109141 761759699 625531905 530255164 519886550 39436496 904433793 311703478 631402486 80843822 87707862 251075718 682874335 416407720 553162111 686195583 291568482 746132557 237711417 124602396 10508730 342058620 101252888 335078467 175120989 961911318 807214945 443398169 451699472 536505766 661189652 650808612 150781817 139237909 33580128 670668366 178674404 790530272 982371843 662593242 871374094 70079704 913668959 554248428 339003775 466831069 92960362 483088609 65479977 330671778 607691004 75988707 672730398 708943891 263583525 700367738 523371560 70798469 143765906 975071031 459820587 657471910 478395995 610602403 796709818 364492474 133787120 827900573 155022745 968675315 490493814 26396838 891271370 256679124 433161617 82791497 723510193 526121978 565880105 788990169 856793756 26087460 717495227 382040505 735031350 981078752 82408242 110919261 904393572 78690500 85990291 364214158 588678761 416902637 827332912 237904930 781395110 961120032 65805502 788934207 782311698 408815668 667847396 673583067 665494791 101009013 756374563 241521335 479647342 174771019 883027856 188957449 200858478 453039434 423514305 935889827 286634537 358438899 46809087 191028109 289645750 985315730 407758618 878324510 254734718 235091530 968745791 888646180 48727913 887067644 677580386 831039610 148399663 197944133 357139028 813894454 151469497 966029943 907932140 631116839 140800961 790959995 672590639 341659439 96515781 96104944 130065617 383150317 454543842 29391056 574178425 744189591 867223137 981937043 475030452 121957854 69544924 296292594 863120385 118272836 183360237 393217122 801828797 331759900 591161255 11484176 998170705 742630751 977514118 906102844 226263941 970831431 549579191 898854580 165007221 646094971 994959523 295072837 29245287 302019716 176980244 455940064 898725658 44203380 290393458 226272461 18677586 212454733 522565054 881797970 183243920 705925290 127531444 985072716 890201541 718692698 849073243 888372245 461323448 679103713 646991441 687587389 649935143 49086983 438958320 814942363 547698305 286434194 962531551 429459943 588453909 139511795 885400006 339695918 36231526 28309815 565968378 54909111 240764547 88533431 789223433 424008466 646975072 916754876 261597533 537176613 635447573 110670776 278065209 949287372 642290840 777573001 489391112 144742334 826659983 928349431 959684696 226874639 214783624 774732598 656334582 655753884 914244392 394250939 995449801 950475918 422560754 561418178 857901380 515841652 502467960 647124812 939850118 149443032 416396039 53964002 539135996 51843611 17151129 817201204 853647335 659441968 447290557 343038446 804184301 126466891 123904229 616385348 353341530 338687852 243634298 9676111 994441736 10395041 403927049 842407888 960870958 679004154 256342418 671288690 194845806 758810377 170929853 987212275 908253408 587325892 41176276 299905755 491685854 910843757 117106959 345333188 422802076 416913867 540887986 79502729 543380757 664792214 695888076 896722286 3480065 939522373 906398396 850438152 949917414 162841797 545362392 763304723 841845950 801704809 287109764 889208107 560515185 458039617 876420381 321284945 45365508 770113009 621190699 537051361 533473117 590814009 734900901 956275192 7727875 275788886 35777920 403624984 940581099 584182348 300347269 796577515 376221072 59262017 499532019 178654837 74620165 44894410 941959560 916466114 699115570 81585675 658190573 112147106 539625291 387127305 433432050 584990798 9756665 907139101 974558511 543229781 350469461 709459411 499504973 210713688 837764648 387799244 614338671 630862098 971981591 914685939 279955964 348202663 826464307 779487982 526857499 901084471 676898743 321333410 670066937 228530664 402919085 328257509 340677770 942544375 715384813 774109819 380051525 725141478 533765271 207126387 120887610 884234732 916585797 620392582 94948419 606866796 8191826 709287089 237728893 832689768 476489379 517684856 33408782 155470038 149689190 560266281 56554508 679104284 734116042 726621444 907634948 137035126 907395304 248312717 932095853 475296469 874938887 164663729 52954298 408704158 371790115 173841907 145455241 140892263 794234489 240403659 747759058 654942666 802207099 838004302 340148785 131212829 208205509 373557567 286682866 357894698 933823847 343237374 36998982 520456240 922375169 797150281 510007718 829770473 45462997 294619922 157583293 772918235 459283650 210537590 34138744 683590116 384379496 179593984 824482378 31130336 419997642 424757787 686073001 74721092 115278440 26221786 205933921 323483948 252295704 492616786 681378646 38635902 835854159 570893979 559092141 610745680 220560611 69099858 293032504 118539959 363719779 450615796 891458193 675519780 661153385 925596937 359109895 45532880 105190920 36108624 76663216 377704914 313382762 615252568 452426005 428661201 493990705 658359925 752145149 746286408 150976711 286040146 784922309 839347221 856934124 344014450 450092900 77494734 265630659 743125403 48551044 629350438 46257550 940009236 157386569 707410934 865606172 516496464 752943814 823313444 405121439 682123381 201018357 718504201 297375948 653444361 147165401 791366653 164320638 899310549 390169412 315297348 37867046 175091721 7160920 894801169 371622522 457253820 824812254 637253180 52895574 873363297 119119969 99153124 665888885 276506538 806564057 384011408 793003001 412024222 207324851 50640791 94147602 260859559 769144991 244039902 914303920 916310392 887922906 78624557 668137292 278092317 246438256 706004338 305700389 253599175 453321858 677322910 563369346 130650464 314576090 616264920 856530112 433696058 567934395 522418996 710202595 227014803 906430404 355721947 639039025 966271606 406362738 585702978 227131165 28024080 682259231 993951436 944334471 570182136 925092344 464988115 700790805 24046951 23508804 6491193 277646125 329347013 683814103 841015471 459997476 850906544 309796742 169043940 137118953 877731136 691462935 847321548 104745938 450409690 55559846 596301314 269197648 314438935 34520644 496328812 342463015 716779874 342796599 139313837 139478362 267888942 604301951 840269166 291935892 480327106 699276710 422098368 809674119 235607164 115630190 122187946 86513707 425426931 291231885 223632660 155674418 982694820 923470559 112936708 285620861 979030404 561754373 554818508 145985691 596275016 903663671 488448705 165571242 246460269 627762541 157565955 366865562 84580844 997835120 658801453 564907949 549628181 80899821 374582067 785235345 49046362 496770013 871749051 474473293 788001897 947898062 482664062 623213068 871368620 595600769 761350281 702915376 9871494 168685140 848901066 606146509 72348811 189866122 624234102 171325431 817628662 781800056 538190993 902209505 632151527 49508797 467117454 181779708 130408617 694215872 967015052 31971331 43502236 691280454 506444623 831504133 491694868 989108684 307233552 215579839 437225805 68583832 918495214 447097298 89785324 619912631 905760158 162134134 809778752 529994260 333459564 479923766 164310667 871650556 382133270 796462194 921159353 701767075 978241901 904084321 395982947 797773304 936055651 439485182 341570109 295016625 123505666 833264976 136641661 283255570 48844815 426383817 204355753 819856380 873481114 294141076 292285363 631757623 456275209 954580466 14268234 642251125 434504231 178578901 366418032 669153853 975041094 140093736 370920927 805799346 44178057 619420225 456089001 832750059 58905407 797659109 980283036 34927424 483440437 116924696 318182993 384801603 395824864 522538746 57174334 121822329 816679821 201976048 753579951 125471382 156556514 767848185 767722506 443577096 946427085 134140537 112730948 921468178 126750625 336168227 579783875 23445033 955588451 35872875 856195091 867010209 686048335 688994478 901937633 22005123 658435525 72636977 406806725 54260388 447692074 316497411 176082716 116888247 518473458 929662667 242359628 675029971 550027203 862598485 118607067 496454287 849255373 83854366 270438816 976005997 420022592 850222690 999451029 228127395 738611916 708162472 95137603 424660250 397156949 849591587 446665373 55592474 922228564 705988449 962369213 222436989 22485859 138451929 339325235 540959317 920630947 581684862 68505639 323174501 296799698 39629057 819628787 146055071 123483423 942583954 122061067 396022366 645322995 974028448 624149760 383934910 682190919 571803715 661111511 931864219 421395301 107776883 839973044 196140216 666281684 802342257 418577205 688767542 793310537 757902439 82243210 566457835 192103653 3265201 889632335 488903350 42894257 561777473 487474772 18894031 356877778 462052191 267432749 2200772 436080638 891582508 238652033 970787908 315902574 899763543 902652126 737297875 860056778 595141522 785954442 526338461 250000130 57047998 67622354 43310666 814950437 2381916 462284852 859570441 5647116 204433538 200990142 48541372 618727362 688464914 67435403 975605139 150517104 187384503 977805910 439114093 78967010 68974294 409902000 247385936 968737836 165070477 984683810 828794613 760211998 623154603 207649425 10212127 680202601 127788131 906039144