20000
514610669 310332153 801651396 356557991 678514978 494034437 594127343 379033978 115343136 900452788 986190395 881373862 550771371 761236504 376454187 819884107 565073485 322483592 534022548 300216338 497688544 242455362 84038751 447666115 177527257 491440285 382712109 41578133 888795897 755959422 774582940 817344630 272278263 477593938 940100898 308378491 627163201 287452395 780724362 219644116 110807536 71620120 62281354 649617767 926072368 677545694 639744876 801935610 705429221 342123881 163743212 74355557 741923136 289622424 654392311 955600996 964949788 259553453 481177514 934648195 397274369 473245641 670250188 185888133 100021399 544525566 149478750 965086719 391694839 88206759 757615971 465632082 667773647 235716568 285592093 323097422 133257679 242485644 307470460 650839904 287468868 833165123 282314351 629749806 730873994 300247453 627130435 391906510 363101272 17363255 885000241 787887053 221398034 137587068 446135751 137319935 104997026 310324207 446969517 373335984 198254188 410266678 122976649 311978945 889153202 509616779 780329654 92465593 33720881 728246651 382404580 883971568 359594121 593993788 335884779 242450480 379719234 655958199 608883231 123957892 393234137 576337482 137656385 307546380 917467347 536950104 902573344 739775379 748235639 654063394 718282803 400257169 308914055 13380096 293898268 55059623 605626714 398060451 636301262 653449992 935727882 844942431 984805696 505763621 874271835 207135296 828865997 274860538 623752954 661362356 12670481 229103364 858206846 955863662 853069078 60096967 719843674 296429260 205386967 142933801 441988732 358900319 318319763 628347141 625216271 849488197 581744026 186666231 673099473 519387448 413339732 869057238 15880413 557175107 564331673 18913135 826418244 426507576 634792995 74471086 957053763 143257699 482354247 938763343 797743434 177154775 338917315 149079762 595468027 829180220 417722002 293619297 447493057 30873176 766594700 279725077 868840424 492163587 110999205 615315877 492143804 167212676 425921064 903169343 447529311 179744138 170282047 816492155 516477566 1435197 755096229 398675062 308811554 663247388 772734121 131861852 792813574 941109364 532223086 287473079 191292951 428251058 343970535 700155353 180584218 835063548 928640769 342027770 875172462 523217409 237431284 264525809 606104987 207824915 147297023 743954141 523123700 800277371 411650867 766203169 276097751 74278101 985230518 195292121 382891760 457168457 360906135 470749364 280417994 793043989 730052779 317387003 253925183 370581224 64764451 102923719 690147871 71284042 641596155 433901039 347358204 234652221 111761740 369797515 287673153 41609271 883987733 364124554 929031509 25568674 785641073 855248271 778625858 14284990 153164389 606331774 350987569 648221209 965037957 952491757 115561655 128827920 361517782 48545229 693365431 856088373 306680102 745010327 757206072 608968649 305646832 326461457 397074106 198993052 818203571 163753770 664209818 425952539 579158560 201522072 534750778 657682834 723257722 866593594 866632013 528352920 552807030 779192327 361671297 220195812 440221981 904222930 875063342 960744176 431431541 506007826 232836242 43691014 618730949 511242829 83627498 912692314 507427049 426854285 207297345 925691551 805185139 548160100 169857000 467468744 718842419 890609284 202145276 821111627 906925525 541157761 179996422 460253002 479552251 32255116 991363136 293181015 381375703 726153203 450692738 526522929 162287722 833186040 116417039 955951869 41599010 741463648 55815193 39748085 876911071 87098963 788756726 748469224 671729012 528174551 347432731 551179097 267354017 185863485 297194067 834915246 663914767 5861502 259610337 355347449 877770598 913633258 889436063 169583979 514835480 361281732 27361011 350819752 213803003 663548875 461682207 207557220 901514138 800267040 28364977 489567804 723172484 959789014 419179588 494455103 949429288 444322322 619706718 320937903 704149000 758669532 9668592 49579696 961045858 221396940 500977754 628170571 554494637 729774786 107070472 832672620 198107846 728322783 976045348 497409653 217348370 386422826 872568510 984007833 853251638 4953827 281311512 56042812 419870840 959494290 332834999 171785819 106474439 213901462 932707850 860705710 366690281 323742595 865209017 404369501 888962115 763107740 33847077 617060362 45947497 163649757 573931532 688992366 354311411 428059577 85402050 509482325 596079482 154633170 315421989 909671243 956600463 869906429 138095322 755991575 923327309 513365673 195744317 992940394 511812791 148142498 713610896 606744956 625742852 153066918 123075469 51037621 758135479 497675232 886111175 319091 722378848 388045712 108059535 387209634 850980505 818366294 843359284 746969076 289502756 55627859 565291650 670170368 147464222 381108391 78833177 996946567 878697090 115739121 23887040 128530370 583708222 386894242 246258000 158574259 621225598 978155695 654246118 55579560 863768394 563604181 425631985 76435216 827954983 732128032 683239427 328727884 516194775 449019493 592111996 279453547 718497869 646585207 229288560 951929828 445080854 437146942 751641690 215144510 281352406 423521652 265906792 484388810 58529728 963086095 68757819 134183377 638583375 601294453 410930081 114879055 362966796 263053992 855562869 604288311 105768751 28138937 239323719 742449525 444345409 852145019 561018684 632044230 353196513 779594415 34656577 248007861 826947189 926224421 402287103 634063667 342914172 712314531 807069766 156935331 43974900 640807170 215858040 664914253 806564328 523160123 819597834 908616296 751110310 174753711 262084893 567610065 864248218 596332406 515831940 747749786 646916509 199192580 271920604 760529285 582714638 649464512 452223892 231856089 499793333 847433293 177661576 468840452 659588683 852402506 889033736 888149264 884023052 667519994 955113397 352216874 736113582 18124648 496137532 990085410 757750253 982510171 575603645 556743732 659196513 813149153 276997141 569997403 938713233 945053220 135477577 580651451 839735174 660564736 379799066 797453130 686544603 568184545 370765735 785061207 340997668 866209210 896866948 542773564 476942346 109892314 35041869 754331569 186654149 206603226 993921019 680258036 138404032 491756166 237812402 155754130 587444719 745769039 375710205 995483798 812282027 178683551 497031282 186100403 582166396 976278033 120194771 556589361 936700419 693211208 288265241 686902470 566028049 779725972 775627189 518273528 185910267 937910527 184472371 361404568 959274871 207701282 86918904 904590549 619899515 69111897 163328766 933448041 71346768 969587721 542493570 248759768 421898122 517220789 751020892 349524880 213099768 977610647 796366796 414742671 669106775 785984874 228981649 166823795 442187489 32738339 955017291 529051404 401796430 56747331 600046351 881160316 303767436 927808498 665351617 204018576 7326305 388580980 639125039 721263689 117665044 405371230 958186016 863617380 987630538 492485399 294573693 585752424 733281938 963912382 422488515 908478210 486466729 690303228 659600419 97457019 444500274 325484072 353159878 81869205 550397475 330484656 864227079 549799210 822472146 962202855 172903357 911803217 481546927 779019382 383953779 640410755 764822064 573823597 625506746 702302926 991475839 859045868 243101620 104960650 114915934 137484460 443365707 536483897 205770009 986334079 621663551 613667361 235457702 676529310 209130007 797572792 627317258 637205641 827765125 408700770 45833813 526280223 134289950 911751725 876734342 269117461 669972296 135726132 293831892 781928491 818052296 154232836 781241818 91217859 4570866 774334501 313309749 677809995 924637899 690188934 810498028 711495379 449188113 930741628 710675749 862812949 872714640 163073224 712424896 948278556 207404852 293518393 303338338 132545257 957324464 714465606 118281151 808020532 559652643 997253785 764267484 973603004 939248476 886291214 240477762 998403611 854789200 11413716 247952903 239756233 881812036 902651037 267172818 840578937 172336832 821198782 216321867 485372210 125519931 110807419 807336323 354600703 962791806 628776315 292876012 316419423 326352888 634823996 502648140 123880812 539626856 349900626 563687618 629572025 760966986 125323102 558835586 395759292 357884452 289272464 526201221 456291494 773008741 283715408 816256550 546252413 204911696 56718412 199246434 642364584 387806456 984039984 200655609 695514975 986564125 486193073 355717016 19817646 347792920 201916948 666162829 137076931 853678445 492366463 311340172 47542613 879520947 53691727 297874529 482154040 955689762 827072984 69265486 52118151 544295376 703621908 915886169 375912488 994521536 60203763 319033648 397574529 709267098 332165884 605722319 809919157 225646070 47695750 792741639 145858037 33423379 867306630 340199921 633946714 465846651 78709078 77317288 900299214 242939040 399189887 686827743 478332955 379050332 444277223 213642128 924742295 382641132 887958770 603954516 40267511 186891295 896489700 645802607 217393718 748081651 494916461 996507160 103812475 543748833 293958949 618700126 43183485 249524605 426339988 191165816 218748024 803378169 974748294 393743116 873414913 623709910 904822340 585350620 820285391 889910005 654869509 388460123 61176074 402087647 224450615 832442896 646961669 38249031 359350319 732138439 126045148 619509512 630925472 212506900 28975831 791789016 838662257 645708089 917613463 993934965 470182912 733515171 792470535 865700561 453749926 918911834 656078796 341655717 902284071 108310021 624366863 522776215 777849975 34408673 911230941 133934891 597913219 521472876 451198459 880455719 14511050 36361385 980153903 86795655 826070830 637367495 17953824 702881649 491574965 120608833 46669188 462539794 152917661 61264312 901321136 922371074 317166828 990935295 576952663 749066497 204937852 924850050 74653023 63767109 463905374 803683591 462150966 156582616 158786059 18010404 326950935 528717939 317245943 293027484 737376622 910421902 667536582 684188793 535622632 556220800 159698209 879979052 421200928 755462606 449385005 487964721 684876178 130392594 498452151 187867324 370862006 8695175 823034927 451264941 963912314 455626108 9125521 551294777 759079453 498975704 164984928 598761842 676594821 205320361 191847099 988560166 452776360 353940990 618163005 514745692 809038981 643468749 595306450 116957167 891852555 479610568 288078601 664146356 358525613 693749498 971748792 361253705 118876051 234931396 436763159 715340745 4367527 628013285 969329097 564091638 290518907 519348210 587603700 432220151 650802029 517880136 122837409 357125961 385744616 341229326 398539562 615179195 817606326 847088597 356986295 554313347 933801588 980399270 485781538 476677802 197758691 916888041 92186984 970252830 641799516 969050001 177166867 203586775 42495206 174608029 928652286 667341808 815319623 657947522 943598209 35441955 470798759 698301654 611924984 168127003 794241463 280567054 182521096 773950876 977250346 839530965 547803979 337108632 289372039 284790853 800938904 718890215 124396377 350395269 614437045 988153355 801916593 520483858 683241045 151705140 221768856 78624264 164247029 952187287 599801702 196004641 31533857 44249185 865726968 539260390 472350559 470078901 116607938 130451452 922916316 873673745 461308423 582094174 749229583 17310993 552590130 420432716 926113022 414062926 61682211 577482542 131617134 958865215 802679242 648541828 562437496 525953772 648706516 779249157 40257145 912438287 279675805 862464932 186269137 848439655 164891357 800875525 593852813 613681312 87927590 389160332 533974227 743418444 927993420 380016250 442854502 945129770 525946611 897289929 746737520 833496972 265206026 495601507 339756078 514327290 543434523 930629819 929401946 261991923 483626553 705004435 153632746 409300687 715902539 878502387 53249063 482087636 309085484 347012907 42148379 334649316 916364746 559590305 695004348 265698653 582886631 336316190 278779405 965543028 569021452 251529379 360202312 943816506 833338230 326536333 826240049 345932196 526943085 826140276 854456097 609431747 825857013 864550026 500837582 392029195 260435939 952300358 654276010 210729522 127384246 108502105 237271830 987429168 823074392 324515313 167214982 945862627 72001021 929929728 993411511 247099912 968709401 131476555 270901042 197755999 174509217 599305265 241929424 664791193 313616182 500192745 505716458 585932901 979001007 220624541 959084740 464084001 585431935 185571220 7600775 456896464 410814270 879253982 98287924 464663544 217033070 156362363 473600393 865239510 321691807 71063002 429161987 310803889 76913258 514758633 626145777 622467009 858632482 261426094 793104711 585079125 76512680 452543812 306932691 776735079 439511705 191769538 873803843 157079540 931632893 531231602 455099995 812153317 455878687 752141072 93153684 165414802 168391009 943513936 786088859 550145514 522936474 65505517 847967885 830624900 203617273 163067160 858007768 628541622 227453892 172551372 679539283 772714472 146765434 785881340 691216985 205354247 578276072 348082125 928579561 341667438 414839771 631191280 785283333 849384604 264196058 450148308 226888653 90460863 62279991 83169586 256600703 718423988 968114577 606196516 782147064 620286988 667955873 207692655 131548261 331200677 162991400 250738416 516514493 254976482 152129847 248633143 452196014 253413275 847715322 64179856 529380826 225341725 565919758 170366895 477283650 196444032 545140521 289261859 734611944 602903262 253259731 228791562 456811327 776120679 490386961 33686976 960690383 648144482 331593449 606980340 801746903 659447302 209120914 715131190 3339977 915737177 388851546 499517164 135365582 311391828 754420759 963667173 144790750 339339318 907466599 806086046 721261552 784186959 968286434 74790252 627121173 780054357 145915671 239051324 969407750 322898275 489251242 243055794 816100000 47522796 875892127 976243982 499525015 346479794 66168246 739477206 389463136 477386474 237382607 267744373 35518422 121765037 614546038 445132877 80104873 928299329 548838083 501429357 308671231 742848770 693811446 143387065 670878425 633026063 896254154 538057816 934307591 696579060 995119141 409148530 910155433 253389782 899140079 536699319 859127157 804043151 386077174 456943131 117482493 233121916 475484223 822999888 174699741 167072030 531084689 795389130 532155219 304307622 33736669 676481948 140047019 560740489 395456025 274008581 962611719 375922265 532275813 515184463 445654574 304318956 356086999 594717587 124518084 305504649 493166234 775874061 399418084 382119651 125133161 984600446 454512411 532818740 229193192 906356320 705504417 636183097 217533890 946389172 691815749 648542689 857238168 460810643 84667332 116440153 672863649 802833943 212502913 554575831 938898094 208002776 191329679 137933804 809895529 468629293 959972235 183264285 807171597 715605588 403031834 667920198 696629134 484981409 43117591 883142396 656434280 28557419 252075038 308544402 918944525 643785303 959979637 947392051 117272445 46557206 329180691 616831654 237778739 851417486 874010426 623831143 344408686 300923364 189286166 777140392 987368600 896358724 722887221 473213085 2036792 770291848 215931483 132136218 34537855 618466104 922963471 976645142 249224210 131678743 449737458 378870975 823782174 382488095 121008998 338327862 221501125 709744759 691030841 197553241 192059860 909931847 677318684 276999929 33386238 984820780 101801327 526310312 629286409 801445621 604402503 163280815 277188834 68930004 599272629 476885258 433121368 413814443 765161182 398615537 973323223 966061492 816113299 898824668 378318768 237332163 579297616 438744394 994130652 200241037 657411260 903225357 788150882 107143002 7280312 653278122 274188525 174039809 817912008 857817970 411225093 959461870 370288998 905166151 700231146 703017962 890564410 620146410 575576097 20650418 174567824 981551079 902777256 187111076 645945597 841921397 790716410 575800946 907787177 902570409 889086711 542962308 754536292 585379206 29637429 671810046 350499269 587800344 879059011 751487910 208548668 870759114 536495849 317081745 779570008 330952399 75755638 585448644 173783596 450546060 359487789 707307555 450222998 3620795 638930117 607326874 492934034 332187452 248120583 720944462 472215626 607908133 95414797 20359595 957109766 169363609 291708593 632753132 325773876 99968912 514763378 582962277 395621692 177035801 993751419 151781983 865369297 673370320 146411124 53462169 259745942 80357044 507562100 132440300 799673210 200346425 838391523 594468492 363531898 865969183 868930068 690780279 149392878 513160777 432380502 515841941 745204912 804145160 106134882 882766517 334400615 788961163 146082286 580581199 826738065 67772740 290371670 615980775 442230670 136548980 71102000 480258654 290219124 254035865 96557011 951482169 654681019 94355133 250947095 383133100 674972524 894823653 567251178 138460790 587897406 721657430 14984929 475136197 588121105 624017046 148255770 308531296 910069292 394877366 838316154 634206324 704869885 924326747 772972480 437783091 897158342 298459146 79096829 439796221 613657875 487398383 774002556 600448297 556234502 911948655 249596744 258139229 192268311 359734263 589278406 590817020 572291233 598337811 3928532 545763429 764984925 142531457 833383887 262230342 564801900 338863014 310308771 820085291 238484383 880682252 29298076 145845898 166393484 814736774 18084239 157145327 102360153 276567868 138931002 209950637 624996582 725624884 582249766 71218834 602872715 560033372 386246790 766551100 164011463 246022841 387624963 635486199 152787603 534157553 326873599 215054557 764742695 942364668 825744545 540231117 738435724 904090954 535663548 364601961 185077105 517080500 447534813 93381499 926852854 976323934 267101080 754281506 23308741 567171858 441060238 824799714 511768383 769472191 630312748 372190809 391289840 332120508 647768826 269900495 553558110 889698555 906985282 577392880 855254023 802203867 706450051 674499989 92757826 170956278 272974472 65595368 155806470 863246006 522865861 225377534 219592749 423800726 484227635 524202754 927755017 983726899 661858378 264593958 825639693 333361535 22736858 104989467 799597181 590041816 77600742 338453453 899269240 147234337 353333955 314680971 532446778 761939091 679003294 335771445 577045073 292764708 43324004 952062264 42487464 574241085 202256500 881417368 448112114 892951999 112628649 381684437 915266899 934177343 5474078 78924801 149258729 420788974 201733356 339114263 204617954 399222592 979919733 508651875 978384238 454685586 42180105 717492953 401561003 261540780 256052161 393447229 551029340 571194700 775484796 323859809 435936705 374630263 468668230 989119536 440308260 168972740 224449814 955618331 754155224 442790236 861509484 448351784 88998312 973005921 253047195 161849308 613543836 293568164 352298884 823335393 47225919 289137202 439962595 178092679 774103704 848734644 876113540 927382127 776650033 936058897 831948609 859142846 694354972 282060916 440854679 80397092 58467783 907938724 905272075 230171596 294923005 846502079 316914207 611427763 310602173 897439102 988718875 940415451 190787919 828409987 712334926 482535926 182990714 695358266 57147285 766787636 118755245 134349757 611428767 392600545 257832888 381067924 905440623 763444810 689013051 167480455 384966669 975041324 186171035 667922325 701645605 185552602 441934714 397773679 742562938 964190475 287338339 555014781 958137499 672843689 618789664 447140046 651717394 689633897 104598943 366729920 688944590 605332797 78007779 552821003 78956842 108664920 679647113 677983413 713444487 694511589 974419173 932692815 966760263 511062786 416389528 87361674 545269976 510222342 889559437 675121641 277838097 471198532 245395806 978751106 775130837 290187419 303506737 68156139 827293594 149075479 78937632 669926595 218232421 603988267 114626660 100775256 748965447 834162891 526659833 231678842 971598969 264803301 416708546 921496426 45973167 419226679 714323751 591736420 556987770 938596644 675655280 511695761 622138358 863125419 518930818 834782936 972786212 584827861 297751705 674687612 975362688 496897246 964405140 294835626 24262470 836039859 877979905 23396900 325105936 754336316 875009065 593926058 616242162 644968659 12011834 263046420 924068046 837628119 609518393 468624336 219157454 169416527 895649764 632774333 245531106 952174554 976719929 107878737 140122105 771041782 854064822 799497548 850815514 978901679 164153923 925679802 620913793 358493635 825049711 187904889 938873434 155533917 203666371 758911784 504907775 114954307 113143872 783888274 957983707 915985182 882905214 470394927 269168872 708846174 232213482 550225736 519832087 52492208 193271006 415957766 955089945 982289167 989679076 25866521 392420684 426130080 942342342 275614527 49668867 435367868 922990772 222851713 53249735 985193480 229446843 88272706 463454420 863717921 35316234 55591967 293473712 358413757 970953555 694140136 39538498 642231951 564348876 503623308 447322502 509488057 238227524 154527252 632196650 676589750 441208652 365123278 721098506 967943211 514157956 313599594 266409716 134953373 667984536 715433164 805455022 175990265 745374596 55424736 437559707 332165521 939397132 176875332 373865376 12929834 970736535 71334143 953050211 308640511 488456465 36063211 910736240 621244610 495884422 188903619 354053588 127141150 291998286 991448550 779331121 643510690 570710037 719599334 581332113 246105607 84934332 381811733 669068204 199506763 108941284 792995206 749058538 708018043 630631800 24044333 335022363 224380313 364006581 436020403 699425752 874525904 343981124 651012516 414357849 599340388 326596987 912040757 809960175 885501752 939282093 560553304 741625329 734909944 194670883 848923970 18231762 276457188 64363680 822613254 380713133 707065767 355547738 363240226 614158655 604307462 714232332 200076298 437002130 622736971 889481708 814251296 236985887 726000500 928366999 341160776 807485425 750435602 417155121 995854485 849614984 840130244 258182895 746038638 143749780 460539759 719809691 735554193 202434662 165757535 660620366 379146803 980342025 187999499 832730500 376529949 108994169 868317402 882203761 360850819 105286777 768253832 304170963 237301719 927267099 596729564 224677162 269887854 417665126 582756702 992372304 619601555 384625265 444667278 712261951 575291258 528087529 559030748 704814797 409947711 705219865 953809355 18876851 66198220 798913683 63949155 464895362 261496533 296430092 865433619 751845505 279971273 865800432 708805789 361491929 144815528 124287736 435440269 547012842 503016233 648569659 74250540 899631936 371739420 112174503 284736517 269630494 904090219 880540126 40979877 994137923 466193640 913239664 494985456 309088973 765910668 523436014 509577990 867688791 60082862 707688496 824632423 884425625 342417440 922054103 8596156 64789158 423102213 636389379 127142614 751438884 10153271 515085718 926487410 359843510 526292032 745524243 28808377 218711584 165715432 735153002 432828942 642569856 398406990 85523805 31541886 475899686 971918155 745456276 566252862 505620927 344648070 756905725 544177477 547278127 384440058 417543208 136405420 939961238 104536149 370669794 319677722 776736289 882731736 984983796 233374043 117472745 766865883 776118744 211869864 439219284 997474679 302146516 451382179 636243858 101768421 572769782 452945411 155186632 486892877 253747888 718080527 942499879 620951036 939460530 463487820 176771874 430239422 384678481 719872221 403115565 289336171 128022119 937515177 169629874 154103817 884784667 228687137 354526090 324473358 31637347 484748013 541090577 851558332 873744397 763015361 13128602 960983147 321691205 469877200 344276306 554969514 959349279 263161985 784478331 254477860 567850551 598324518 268727959 293577596 569503838 203400435 221917218 344185031 141418914 717334569 907003787 781524654 292212976 577238170 335774054 409868852 864978095 193176256 508468795 521681767 30925531 910084944 501437891 470215434 662343964 445239597 763410661 1749 773565070 869493858 22822442 167960939 970633638 878844214 356906905 853770199 25553950 16636266 675225629 446581892 794587034 933546436 309235507 924259949 147086633 868403089 985787415 485239135 933488245 634896671 800042441 292884577 832073644 686724106 648278207 49963568 935995175 883008775 68307705 871228430 949175713 454838843 333378031 937837188 423121938 512004598 773621368 498221295 420862313 859092079 536971173 751294240 292606647 101145721 398143563 747053914 985809717 826899359 308084489 74061112 575189333 749503411 156575185 968383787 936420011 315464192 961170735 601524752 361246441 368357977 685570741 950434646 911740126 887907258 565956342 468369020 372276909 715005126 152975213 382010517 607841209 116465892 435835126 113889398 637919978 987542022 283255467 846714711 764680461 961327586 356987160 962510234 455261628 413717120 396514052 651843048 333404522 917859541 446933372 674124715 646995555 554566821 996181614 948143734 823050877 114472615 274869076 27114645 661289754 27473101 987484995 558513900 653970842 875153752 732226848 936429806 969756202 558821752 639818395 707318523 26360851 595386309 542440604 752091183 575513331 523405096 679175100 95352273 588980722 708933572 486070288 258591025 653943804 159661647 555920067 852701933 211391160 31671186 980883975 929792906 456413198 279363965 843683527 949727269 125748333 402386746 662697261 119523928 56705927 321036919 332171764 607619291 111192611 294650180 939935661 946767547 268108100 775901839 412583750 356315923 499425199 453516336 473974073 984395804 87494052 821369794 301343522 32036044 500232568 860773254 829785052 4359346 205203531 483652331 359655102 395773241 466080280 232600423 931123694 243748820 748776404 662466440 623884539 425206743 47421261 384158668 500903617 373768834 412259501 276121051 376415588 101046353 362991162 294719292 709720597 286712224 997041293 933819383 371585779 918851559 587367175 782411194 279269677 455526807 667964293 694755450 824092254 288716796 278390655 665180982 256551730 965905193 570703588 342150993 284805923 829602623 998994563 617107118 875906739 594950563 768761029 750214496 439606623 794438812 657769393 434472818 660372202 643120508 571383397 996173638 786977587 931141365 749481748 907384511 274284531 122660338 835790779 912036743 996614560 587421109 62057326 265983893 536773477 224563491 737770313 791982195 713519072 137501871 977850571 966687679 961086875 881362667 930398228 965889225 35130095 187118082 710993994 79213107 807541563 359628775 39079913 98100595 710123380 551999194 128790249 357219245 206104215 646791444 687768638 727009 359686234 152106933 81083347 896959569 772819201 508722827 804666256 155002516 743227775 664099669 931876859 550629645 339227321 338952268 953019573 20972883 892519867 159739846 537144160 274403365 100977580 914254433 469860084 994414622 920253703 139640310 137198068 890115259 860340587 675515267 452325282 438156243 868425793 81659877 325120746 765327532 970358212 946129044 818619003 311388802 333759236 572032400 7578378 18678497 689031714 164356110 213275739 183493627 240720728 833668559 112524388 69620899 352915923 534755419 410377595 680769880 160349977 802524683 517619348 457739185 105724116 641274293 969014868 84266705 12974326 403641933 100252528 923274529 77890365 559088628 84271223 16684121 849430537 689866396 770705315 959290391 8667378 764551282 497902046 188089149 206672280 259689886 614369164 51106792 137311005 360418729 484207841 119969442 192893715 896081280 433134337 804347919 862035800 936176637 936271493 112026958 643137807 895860802 866212944 972545604 468622209 519496953 528083989 114292788 286593942 600425321 702559504 831012570 460275178 957782271 698742509 951460345 3672154 51431043 404696768 391358593 498496838 805973734 645840755 615228902 633231109 872876577 68990189 944874757 957578262 163166810 843901258 896837807 898958015 462542464 770060377 382775448 769277266 547587167 660472264 972635606 47456985 505711036 855927100 281126009 647888212 29358934 666635087 13992484 556296811 65581506 230724779 712907246 90735551 258394245 497445649 758272161 209033720 178253094 114170703 753222255 108778502 569147790 967938076 846395907 706789280 413602751 739169032 538400667 856140420 773630805 277365120 132276868 529058745 778013779 711488260 707053914 831467566 524101977 883768071 984055527 172253968 139388717 786204682 390173125 940155285 884432124 149201728 666267859 782897893 565353414 339106050 624846573 433510589 948181665 483599156 539295232 881085681 170816624 3726623 352847569 835349345 111839634 262649663 765819873 750777078 292105427 863304255 20695714 864520602 547976039 804212893 229231262 111310263 479355092 756085878 726815881 729679190 445195227 805376958 561377986 339053192 381108005 839372993 210870751 936700210 213274026 531285292 984012581 604689422 773560788 957219758 728214847 157387362 802784120 980733282 69115792 557164128 408021813 343130396 754788367 280784226 646959877 595937259 256652835 448145564 934754048 690412346 251758821 957666576 544940905 951044401 188337211 906824124 798544645 71842790 275745282 522355990 285880354 198746881 277906912 505888927 217069409 500290258 473380222 658936313 307083633 146809984 920153346 853015835 864741132 878309672 604449413 157539467 767814003 234325027 973652222 432082819 258879538 946692627 259291831 198808414 325980957 317323119 882113894 405192710 50168065 306164409 413136102 518191916 735756656 598547139 254002480 349498198 582550186 920023359 695232137 307687567 670431039 454034358 787516359 952069501 768800090 48342254 628036262 190340770 329214124 890016946 822214764 513559606 518845143 369011673 720660097 321064330 538141858 304513736 330293470 734385980 927727073 400933891 48678897 511492376 363718645 513282900 268651299 838980646 652520680 708753635 418862708 942655258 850211280 540414151 582252019 884418748 137320175 669696856 132060652 206193355 688384061 97965006 301137361 593253364 698036466 542994869 26439151 22279669 560874372 743840361 608894431 122144717 823239558 851726712 150762053 358755067 851458910 650185474 514460994 578618100 942280160 641106559 539246490 516423979 69467786 897066457 872961476 870694220 355446802 850675924 381837346 656422145 426785819 38702722 944241833 837763521 128681872 386883564 289833327 965440917 682552598 581043348 136916115 947699786 804183709 282212430 852816553 968692454 760716157 832131078 475796976 729418945 318450931 103502553 789198946 671784449 830962585 827309256 186245891 558110510 5551341 549103368 604676422 922374273 590865109 951358470 194086068 905484948 964201833 19443147 205262279 764772023 634037384 473494415 58029603 273512654 650281523 144149331 858038224 529926416 335856728 196941398 988204823 296945673 347262418 848357873 271108995 206906286 687708599 966885050 899991809 642929411 462744158 853566904 896812413 705348283 734065274 597248712 781266901 252233271 419367958 682816355 472992833 611764114 65635400 419342558 946921234 709421613 182597123 899625604 516268612 17978992 37882040 726871503 847885065 97102743 505132542 986173059 176451574 726661635 17785840 379429885 747095809 187231175 172512714 297608332 119886947 529425897 282006434 74791717 840554027 330240545 199713262 939383057 671727921 283054098 496051202 395336920 134886298 4254385 357906603 666932719 956244343 35799833 512017854 980510769 801088153 720339656 273958463 280326405 63280059 416515744 20482393 96239196 480470173 814556029 225984018 944174677 399899818 804053591 50747743 621454098 388909321 870039122 950751717 440299829 960442924 270874665 577342883 865360704 59879702 192002182 152392704 532505813 477589138 985368208 406022180 839985719 227919402 275398230 63322781 99849125 529074235 740205372 336620043 378510449 655692711 442764282 32453961 448136179 731462490 721643615 876044532 465998555 782180785 542078306 776054233 773133838 168224046 840552498 258706484 319088354 305971567 226915581 329729465 948602107 720829454 103732725 380427051 811996360 342649729 269950462 520904212 154077207 632493217 18444852 343528399 697854930 752494988 229769262 251365485 28945520 180685210 228974252 328247359 859978887 490571084 867869796 968463143 882127431 163926527 102061273 629949449 189762360 577895058 202943953 228116533 106805784 462819629 779935919 782199366 187563917 974361416 921863384 74897213 454479012 346074549 59581855 702201726 391281108 897608640 344670224 671291718 956301309 721909187 633044887 999590350 241488913 900330648 824139089 346743227 85441658 909057937 940937173 978496632 630518125 417533104 860351615 17277523 525803539 191790106 564967679 879258125 646590297 860790243 219087792 305710629 804400991 410401269 630731544 113658331 486902762 416395912 283807219 337418998 372761296 625051654 87822036 137398196 352508474 745815340 279887070 66446888 670123446 291435018 98559074 702824537 433036843 228051843 308063915 129492409 849996860 693409005 128611780 891276636 39165093 741270888 571339487 613866680 708647374 30217279 422932737 919092421 467224070 367556152 333495609 243061529 641212469 898997472 596676102 986790089 239553744 313448403 973350507 726440244 1470447 393012546 36229587 148843422 585665470 576029209 569063374 542320731 451658332 548729923 719740326 902158126 260185548 76768541 898063857 427683865 313167518 749680860 313731634 316649556 845591900 497573884 550114408 672682081 235006275 251749061 345521111 665205303 311067871 182560447 751109760 971344229 599666139 116506416 962078234 325234979 527566541 14720714 271687138 588526912 542417401 617413312 420057864 51474663 216639871 757272053 944039120 385377002 603553621 358776216 131507526 111975278 368295745 423271086 650223190 276204553 170948522 217950360 406164501 304868459 254023994 632124751 990605568 954966284 96092329 352957099 259935164 15611178 999194907 309709205 901440349 34092478 898101707 812686771 665410911 898489334 954958158 119355765 356843835 784419081 28325392 411195668 499150647 938542510 900571602 440821401 331258948 603573638 352125672 694163747 860739198 292560041 211665497 612034703 223012447 335365107 753677502 934724816 804018875 355790941 26510502 706678293 868352629 396783262 3714094 68960801 698103544 637436784 280125680 39212190 240520478 788888991 449887004 908765001 363952200 610784254 67410704 199352167 44811586 749340693 435631662 19644330 73017272 324504726 260391171 473042184 781721921 637168597 218125210 863229201 957380295 689247019 635675928 952990931 592708112 350789160 465766901 685866800 920180692 910238831 778453729 257594975 463008940 898634755 55801189 189795075 169740736 931582437 88225258 719254988 886565464 892921412 753054090 618623622 118527001 56843887 778413471 719440309 89195327 815001604 216360649 541578019 494901302 811209232 787509823 623723251 72869261 520391800 552512629 161938722 53235640 634805818 596578963 123627130 587706740 399017844 973271415 456354434 361747551 809847269 492009462 620720061 708441425 961456860 412812094 198296096 609661612 72471097 815661568 29209027 844332237 133373073 125271283 331636571 318970437 672806618 80912276 372732016 686427181 254035691 275165683 695115296 595153130 818312908 342218201 348172028 523277376 84424666 289952410 839544164 172601844 912915430 185443760 202440152 831499231 957501103 930492830 677187684 828933739 12775253 7701453 458924499 505818358 156470593 869731262 411859413 835409437 545140909 591688071 549161793 988156590 481362515 972006651 277767208 773566517 53312784 784261362 745492731 346083675 457792158 110418262 785830946 505219656 332387254 168653911 657107335 995402151 572065027 94572184 828679241 868384513 109686181 678556947 234161516 516735340 988673027 130888282 951393879 293978062 964458248 950331354 952069734 522858878 147509490 324962474 360595122 492038807 159582856 417611969 440796082 121878023 791537106 826816556 120958497 390570026 818820245 797467074 775363330 126286332 38288939 482421869 110675569 83133356 228535079 557778677 101903655 238214258 562888772 216959257 524100123 976219719 565533923 75788028 114744855 862704360 783987132 86382578 140061214 206106462 347233214 955657136 443448207 708020514 716413859 604579294 25200601 831566967 63598165 547346579 995714313 495940325 83209636 855043357 106883244 842730234 681745280 732692749 427838636 976907396 806976840 868268333 939659048 602039610 493510419 971526244 646075031 963553076 990183867 883639940 790545861 76934153 830385454 507001186 664709948 450866513 763614866 275105903 419382116 781747449 643644017 135933229 983472686 559864895 990071274 519033047 340927197 17534887 6295969 482777352 644735939 707072907 421966774 334152636 115860476 417777114 277732493 64458531 619865982 347391442 316554485 233590703 763442046 644821102 685534008 619991684 995929716 480675539 464052318 228142706 824169617 30774925 419580025 569965365 909954072 314507605 679986178 89662874 180780671 715463187 318281602 999525838 793041807 882501546 262220525 851097962 571310583 56178286 888768535 564083666 349924924 410260482 477588385 516235934 169302572 665203144 600766240 392676632 729696769 689334103 130066739 417916241 647009862 467768774 737929063 902209226 270674165 376066726 780373494 227844409 135250557 631065223 472543052 995167229 451768642 581855003 438430400 241064464 179577350 487158225 20372012 55337680 948015725 404042327 212675381 490824849 249446538 775366825 621036232 718761323 339962026 160315302 289104432 196974200 534029318 103354852 481411236 580204376 111540682 918301921 709875097 854800013 685006789 189832964 981992449 226855080 576426128 539043860 601016696 360881565 934047815 924527654 339224826 657370755 802263463 911103242 207184576 543031746 196135650 33316049 779252167 549738870 251329217 381091355 704293526 254817574 760283233 68075217 579739238 439801782 722259382 128098954 918795034 477563242 931817533 795024219 340194764 427640599 616283426 226690500 318241591 382127595 665202876 668105461 316218383 806344401 136756415 894054238 159671727 624050025 535733505 586541004 81902057 918218629 466745831 966869609 993986711 358410663 336839598 858077683 187004350 201749886 565330487 314818571 249025912 128020986 781250732 554469584 261661181 979149421 979255676 82003575 257395704 246013487 122226893 945508119 639113664 852503193 842211089 921009031 390291056 749842797 528205895 646658469 973930220 757408223 886788468 718112446 377336250 764156860 222526552 154324407 4676342 544982905 34278766 700380393 176112849 240469982 897555406 652634554 428835392 694354949 961018229 300712494 322696057 160098117 343293676 681268645 311123865 250113976 662632587 262870172 89273254 982175112 517762215 586166694 607201580 857302713 582762604 742206354 871437919 425316651 933850816 694577983 625890226 104481976 272037692 712513123 548845180 271478592 123882398 385212041 695904154 871149768 97531955 795946399 520235553 590049896 142915673 679440794 455469393 115611235 206367706 496211246 857070618 981429302 79882942 549536424 867076863 274704769 993550257 232618399 606123595 553512310 876462437 666453984 919841773 139628485 474368592 280599602 675015605 429067064 759708957 411647266 485021301 890884217 85281890 384108126 741838625 546913720 51972257 262115274 501533935 720198742 780994830 855818700 204795884 701995371 950780654 142472367 680930185 40329385 284599001 72955451 195940045 780033111 669431688 159684821 602866280 723445504 159719556 132686304 264394295 131951821 993857551 909246648 945605668 934988242 274397307 304037194 847946992 181390919 81213106 157979038 340269914 759196019 549628789 667847667 343212254 551856586 717187769 49788191 977350534 62716813 85047537 723261083 761711356 600353631 379124900 279800566 402173938 618675964 279612252 298213068 334533836 144152626 792070006 865268087 864899331 365007931 43546926 192730590 256081489 739002278 299317653 10073029 801342019 707903150 22736274 964108113 905268548 757772458 764834153 299313243 592404221 42819591 757848105 141454366 588705542 913346747 458163110 349861287 417364861 807321956 113316266 43560694 968645105 549377586 204088766 302939757 798992356 59691365 952782082 28316004 917790287 44467532 336580324 360305205 441009004 702360757 666049610 153982170 16070184 12225388 133333959 419472567 329531663 248396829 99041885 690247297 383841881 605176757 462022047 515439276 239537007 40075264 991498431 209660940 829763966 66848582 736503966 448450234 547403759 806746154 302271282 542010305 625488205 290851060 955928735 698157361 319041571 447579265 454198713 729063903 132848617 496575669 408942729 487207509 238147517 832337787 809017070 719506972 765378834 493300363 622922879 793793950 810127384 581331298 123425908 354306781 440547425 192193556 976640845 89383532 767041727 734148444 541965952 695284990 119776319 867496171 411984500 144922679 394630785 70686734 647495969 141924368 629651953 186310087 954611324 150828650 614040869 723254310 769564616 238337755 138035558 761313650 537749407 671935463 159324723 731504417 926080637 7010048 678996540 185623998 943034448 266248579 61575885 577404748 245402770 356773434 211406740 974203194 171737594 799287124 264483382 78537303 36084037 266061672 844732622 456698917 369676073 385434444 31832060 476292592 348996535 370730372 232059522 264698091 389829501 935472068 883354982 653430092 734980150 755231276 523963186 512143708 809040144 980955108 613694554 876249202 666656701 145445033 336421015 211897351 791048843 950635131 894337097 70574371 852050289 812032154 585518012 893428954 567873824 394117881 499486216 870223471 286379049 810127795 359154489 943826807 940640898 310529657 42522558 943747967 435238838 753810976 337825845 850422779 519055827 418095609 865946155 821471677 260416003 46538419 736835639 976731877 96596110 678184293 181858822 758912173 138836008 811999799 730352915 826179127 784905756 998967837 330921455 745194898 996257218 990696208 991835695 992733119 394260939 759017163 923904619 858756413 873291131 644611011 540165066 631383865 744171127 630776509 468107912 139490916 969250136 90175017 712345168 735827335 636153827 372812754 541956139 599370010 928530312 341834147 109441353 187564341 827517800 391604043 919817636 313475137 908673235 282359050 99416463 802143844 878627843 319497826 78673723 949184662 342978945 453100188 595456398 692766090 519060280 95500643 348666551 206474249 475990644 383800017 939258861 462591804 559705858 132943251 363051239 45420039 9423560 434721346 381561461 880317063 552898254 651205214 175888651 567504741 766027272 470136987 763960044 582138098 860933389 599896174 818626726 287584352 75913989 148723849 874996974 836841760 924090464 954619987 592262670 183050604 311148111 325034840 485885837 706902623 649113342 447472981 996181250 201368560 121593800 260133936 323142904 722189225 398077662 664485571 864024914 31643282 92392218 389435009 118474365 859031007 807819130 966292786 573027938 545624554 908355567 502296806 145810152 62654846 717897224 574501517 88861317 351498883 186125530 356996638 170180273 436150 278177879 656219479 850418183 487232494 521582148 610774880 392091344 869968426 747643509 504937241 989902562 180605646 44995533 814859724 219631995 851648929 611707782 589102025 116662662 848765556 515082214 441462429 905864173 187601126 149645310 332854255 573021054 221376877 327181620 605624807 694777161 833207811 233417216 806070257 46356424 193425921 736448466 478719041 656558134 648875809 937935889 940492794 602186251 651674314 227722135 739721611 951173119 520076056 335883318 319200929 946441112 245587831 754947814 635920158 863626451 592665991 29185567 277712130 452512130 747171980 645551969 631645287 250558837 855246418 253367085 881024659 356621066 190827846 344605349 786542805 121429480 663285773 316680564 69622998 13665124 263580501 771924954 794742899 611314204 237619004 446721907 456471862 106903714 956639609 332059612 873493445 291842478 818617453 3826789 417802094 645363684 594283725 512400405 67719925 804810160 157835225 849553007 612290888 781199905 929937935 284012235 538121598 950718545 113529196 275191666 397040073 783903397 704375463 311807216 223053203 645701602 339994007 251979478 305795687 249313880 476774547 480547896 249029956 573010593 468183634 678467466 406564435 498365866 565958930 981891494 873984324 18233321 982949654 652755937 90228919 940519543 924173617 946433701 391848352 772479988 683695968 425255759 894896715 880073615 964450378 266736382 437210959 993685120 831771784 540198977 560663203 231541898 348207986 761415712 679631141 973328692 739313871 60733070 951072494 552581954 742728153 811984438 956195198 64932414 941990707 794551140 904089266 593375637 166903219 346054845 72565081 353941427 833961660 573077394 691458869 144396895 479326207 467332362 521882346 296144330 600609144 442866655 764224727 679289830 561288056 417808753 370221516 964923503 489692119 500511731 126059756 857007992 241820773 250918887 609616487 530511510 538951468 60547897 595768936 136848427 334914174 427473055 789749463 87423189 868658050 739518822 622713308 564595597 279516251 551591947 323477961 587712605 908313054 545849593 309768623 832449010 161369041 994132033 65688247 130700611 345950714 336046394 214324568 189574494 466960072 714961049 664499391 396021797 900120847 350583114 868268774 175309524 768111039 775520821 195811543 616196497 222796283 224741025 282640337 657055672 257315779 566720027 81332275 593739281 29400281 810585670 662872889 445677020 598150952 317410585 928022614 752071526 191786925 827142487 661223157 916127227 869031619 592730688 850104317 446025260 706072466 874037047 102406858 662787650 699238122 641191843 61388969 128673479 778314433 111974151 864253629 218200450 482841239 115071690 668812122 121633091 358107183 444255604 923885152 695253551 420536207 130065580 304966952 725570584 739078082 227527044 551611 736969291 250848147 59962153 25266794 989658266 512100729 286490209 906914971 742765238 23372712 279193517 148246802 62871529 524083254 531987222 695747243 649507071 362942496 812485499 916979305 602810750 207626470 500901757 935294208 225660007 347699308 709194576 736194931 673762653 197246403 790466112 357358749 118483196 778190682 324007721 275127878 237144736 967319547 477869233 419191720 80940244 79181726 435770357 152713426 271603098 893157746 589614990 625212487 220230726 324669669 100080388 104083885 269873655 676372238 507972015 746126620 164393141 367249002 960907719 512866493 781988159 805633534 810101102 250579799 209025379 22260302 553320432 661870799 377679376 162224243 962518553 963579379 27320892 203615555 869776094 542653221 915405456 856440462 358801853 655304500 308715625 952470313 542841847 825948493 53750272 315744320 771114092 25201914 355285641 934232212 26880400 798354300 445358883 871686409 580404057 151262220 120284643 241270591 605433284 688311632 770264000 276831650 845917617 316191964 374765022 637644696 369082972 247629629 115283333 752244542 809496326 71004278 491220450 641864301 857917751 804196945 694651866 795551797 404499173 753995075 474301855 471817987 567265687 533276466 834418037 563968983 209248890 426650950 339781662 443329650 345937372 952556340 314908300 434366786 168431634 579396745 14638530 143532468 958643095 663258140 182546521 967177753 703794801 680397409 763679004 724660257 638811426 689271873 199835815 142116632 760330445 27422364 768076384 392477707 193822693 349651781 413309413 685516627 743242889 775640295 447186849 737730508 942206470 995038518 614074188 910025594 120638152 672312480 647984355 140040185 141905785 765097349 946069726 19938711 702611987 405673045 550114307 744606671 787540463 405779965 211419533 74653189 160158020 881449585 941930204 673579888 132938527 330257845 509133069 79977613 930224188 145752554 515690683 335677940 768181677 646772859 566104921 654990820 722893318 692851684 158041044 466777289 273634211 512593474 280219639 151725781 802476932 1310966 653594857 879518666 584179533 641427819 179146709 999543734 109920030 329206163 703526097 583348789 439762552 443866157 562736303 32292347 905758742 487719148 832447988 937846337 86472104 4256654 355204801 211591203 757391079 639118088 713630980 667568196 518221888 217499819 311783728 459656611 583503336 514248326 706342302 546151135 688443201 177142350 604610278 542045067 631200728 450512126 51872056 965807374 898172446 723386663 634796390 744738223 204860898 616881612 790560571 419616934 8268260 778239582 69091759 988239530 5207906 479126372 303553777 369318313 178348394 861096030 482165312 65505551 249076589 37426360 825438489 962553029 880853680 576066384 694022348 414237876 107575425 627884561 294414437 437385938 413116023 862637035 708265295 657757529 866065096 78666570 204984002 373448652 216976774 255581912 932591475 59816747 993984573 924662960 458900035 273995707 386581079 117452991 338116473 548602658 839612655 308665384 896845564 694097629 368548806 418378828 938472755 13479180 866143521 329100828 423318025 838075877 599078559 539843982 427373016 825339691 327662584 642431925 879486759 303317477 453653232 989612069 344985559 915532898 974633302 406123285 803014095 956597710 38729429 848129108 714760338 768506019 374043960 786652246 587468035 773651122 761438552 851213442 464993947 581199426 900247406 548847422 985055841 871127295 536542187 314012288 445283564 765461390 758575248 417223539 788694732 207089654 693353951 488848393 95489253 382417219 461856609 59460216 582249145 889773868 799881594 88101937 91381499 24972614 146191539 976613865 775623326 324305690 823393360 200567582 807073255 781095016 718135828 215379005 145759534 571668061 376806058 896967961 581420211 462241607 524169424 62577974 274034736 430040142 668469661 539133089 369201234 138052954 373440449 748465439 767358465 698098061 247379650 69608250 808801314 71327059 857407065 850296663 567112851 178599183 399743815 972617040 512415525 494824192 243392784 362186989 153069775 489537620 680389902 219209102 537131892 748653556 286621981 878933745 942579462 302377737 598783043 181262688 240596282 31502672 721998800 83532055 673738944 566272204 291675634 332299283 430648007 445018768 171125966 18057095 135487888 336391139 663583767 406134544 549418600 346926402 706487762 885403366 914205770 177362726 550199288 737159382 934456856 698990565 280752527 860815427 325046301 137326173 530549709 245787160 363468915 233222686 744693950 944161433 844881730 458865395 623630511 163440550 863602444 772957507 217074748 642286726 435616894 321715796 205423598 677128338 114546982 95680815 235934432 241428863 98067445 304473716 148261521 718119730 263305497 459537705 146282065 608666142 117162041 453067552 132951349 658154659 4898906 346034959 996217413 244606457 447492474 831298049 899730315 595156304 89239175 347484557 624399352 786906588 867848399 377944355 301422505 402760049 273357007 818387411 756398522 276284185 441083064 814361541 26125276 475300530 137028017 756389603 23963873 692661718 881251786 354510847 777085213 93316270 299277508 705053718 146194189 256236174 959787853 867776330 411569219 339074809 729794888 782262962 343549072 924876380 527919969 154179222 385603767 695302760 547415298 200192823 57804145 207785152 543713172 50559251 1034020 446582697 756107578 301983738 165887812 581246867 47352460 571243076 209856851 727020737 785588548 997353717 821371594 219520478 233433353 783952836 948705090 588478111 969485574 825718819 928018216 603789758 503102328 785392407 597606181 566204639 236663076 21598695 866804797 454731221 443383985 938014376 724727083 334494041 755428081 112913244 667447461 130973245 409090493 344595594 434442159 402352381 209837598 499786496 964330278 234111135 886722443 44224126 173111866 90565743 73988740 792834235 358313044 763503733 41963466 894966487 848224966 377050197 414884540 939427096 61698296 336715598 475614927 591449884 210649568 211984813 599115157 401764596 300270772 679120045 6702463 92476567 210928554 52237708 176413363 870795246 708263636 476198738 195680326 82449242 445225391 633119201 434262319 485441421 726518817 503058908 131761625 315501183 735619284 998156782 389817265 839891141 909081339 643957100 625794674 265496500 365740880 62603536 441328838 143195887 386688378 694882260 919220899 885420301 209099405 846479284 55496322 425110640 388466938 366694266 824025759 436236365 411983409 767269770 327335057 247024150 476006608 793839051 638883132 953578417 754421221 135445521 144810977 91370544 386197762 951516765 630726542 219775103 40352390 728770386 927221141 535350766 330091103 216736362 668769637 42311265 823207227 535849271 430837470 810889647 841857056 745090637 961721647 263236749 964757341 528903616 578985142 652629413 888514011 437022547 110169066 242552986 932317634 227688242 555835391 857827691 454878029 492801226 230044742 312345465 274438336 891957091 344241139 461242349 776638283 53122268 366760142 559809032 625961126 40536138 829010087 976669513 391850344 101242873 397938384 874380953 541886745 277840712 193643120 376566245 993218121 324361796 972155903 399594803 206675791 953094186 625223164 6340040 522096729 569452065 400961691 89396864 349909009 693324179 463073723 267247718 918111588 806197995 523803263 299742983 123952005 694678565 330512320 859808770 165687989 915325151 159146992 403842325 642846032 760722239 435822616 156669827 301091268 322082404 423202906 817678247 962012461 674597910 614881760 215178046 799466788 207379 694750735 20204706 40047924 706293721 630216087 608314304 454894721 347847133 434550319 814114771 96144950 165553794 858289110 882040969 661542514 527247366 161835352 885952958 364899299 440509112 489506376 620686704 153502299 305305796 906022430 960724621 269399938 240928286 430511085 519887437 430894867 232560229 502579206 502341388 958326051 548627051 733301176 742887104 486504006 6841378 254506415 579621059 227793424 733619585 560068669 570859121 486657838 43825571 982649347 638917608 857135589 91868553 822229949 91826972 702455810 765459448 28655132 231051984 269018333 499976704 347889846 791899894 703802409 431565628 822043118 513983059 564786046 697051299 937897411 670932813 377188948 69449342 143154054 550204051 318963320 274402964 77062148 16579413 29946010 756620084 435933271 565534784 151678743 481409785 108120064 845207528 528614530 896995081 638813066 265945340 561056159 64525185 394239686 204555099 593213443 544356801 998678459 622207780 789446332 39427208 899352425 688137154 15925608 597496638 154154873 393201050 740108667 131086141 624430004 918289345 677498850 709996198 592541681 970816882 473886794 794725941 460476043 981839466 664587760 592563931 358482377 264983392 156087023 648077502 580868829 854551596 627954807 178114874 877516085 519076519 407666389 11398271 970656411 63635529 353351760 482939501 716469570 684929517 835246337 138270828 445124612 106438523 549362954 489905057 744799452 653872409 564684421 304448301 498145489 892038996 259796038 947462490 527264784 677364303 572351848 228178714 235844816 263599536 887277568 390769611 531655476 368350581 454771481 89961477 834178877 133669437 61117856 933441571 522697436 20633373 838030499 606840706 134651150 540766095 889226113 908383000 301287981 358678901 330072066 855024066 719515382 361902078 984208826 1134316 192007977 310261488 699955035 905577025 148561828 137338315 585620256 810789405 50240802 396724772 40561779 967505190 32002345 350402345 529392683 481898066 440791502 118754173 826933272 107308471 797413485 120168316 964949868 788739256 412170197 539121069 10957666 274811113 251120151 505347959 990126873 781896080 296136815 547601541 176526802 548324359 184765971 951664683 737526276 439232964 839466953 247246741 850120249 3967176 720544450 828347381 843092366 245170955 299962287 330829452 332768272 20602804 354942148 818294797 720792902 588196800 22855689 720658302 605942030 277229603 75625902 326506804 733127807 52614682 406570110 251670289 767231317 561028131 57637132 747262593 668669828 116774319 263863950 609028754 829945517 932532431 782434902 104727177 661216958 166174461 156599559 549144066 985153336 796581442 33587593 714409035 103747560 166059922 89645891 821644707 97441272 520033697 568513984 858532475 845776539 620190405 705567662 951330459 916074454 703388775 463639962 185904984 915567079 179565036 168995994 919580122 503508171 553510596 117189304 908539902 879006514 484515808 946185564 301694778 693243975 951933576 837162822 127749866 126316383 691753616 705497478 728604269 673510072 180400087 799175407 438411035 437665236 130022491 995530692 41990747 809572342 715819491 720934923 704819290 476296757 11455891 150412091 686407582 925407748 212266070 584157636 102388913 513946510 498138630 415498752 290766994 713168995 857624681 324055912 575896316 103692058 591319012 18036398 304865346 544819007 242518673 354594504 398007505 560748508 149835193 978387719 452640332 102738760 969234640 951000474 172447472 114976462 917799299 523474575 62796852 296332576 311970427 676551343 153585684 264146774 896719687 47223882 801648063 417834990 219518214 71459201 908463066 20901272 823837272 596299598 718398492 693729295 153867104 760167327 773919385 784217148 903284048 752040259 137322211 178987987 328379734 16643676 820586647 922307010 763268314 527263157 50867098 278555538 675138779 151641251 655664320 931173724 706161753 862228975 915046170 972167302 563046376 273947753 897960711 278275726 519349825 52126707 397235169 929727285 299595416 279019620 960960362 349198908 93740147 423325589 849878540 283393162 662945446 592801837 772072449 972485958 150906901 858834438 948097782 894592212 251808033 644773907 80967538 326195657 362650332 270153689 991676887 917952376 51623843 15229222 341552903 429846573 554533772 696199156 916030813 847904271 20212602 217091677 562845405 843697566 386438131 792967810 409997632 649025443 934543036 471240564 701161224 809664412 506903279 628789140 927598738 359588691 505748599 581337616 439698717 384230591 340701773 677648111 412536668 456679406 901632810 483926998 426994021 581909161 426655345 366967126 327256722 872419901 897453531 348350569 705923388 287070677 43815902 18613564 467829395 951954785 676079716 812835398 641296007 804083220 789550677 617767586 916049896 354802401 296183197 732405581 153245433 244969547 576051279 650567610 291936628 118388291 618447133 764437600 734757210 714337432 76794996 918358536 634277019 717225970 59186691 70048204 698151467 647947175 58115071 388238538 883510680 190360114 511321500 569254072 134622748 515248886 272208386 43069187 611175553 557163885 267040493 833182148 907362988 87313203 479293366 442351677 932049048 66654790 935954738 898961224 165397208 662593442 103798448 760846219 470151847 148690085 527756921 157933547 699718181 670333611 862108748 440000942 172312103 796483688 298307540 133783400 464509778 486490606 97683667 77967626 20628307 126294541 893007422 99689425 290919540 760537691 63833395 393345047 198064880 32691428 387790538 64277740 300616605 611671455 221899639 28092032 137289446 695501600 902768610 189888676 969284284 551073272 388650259 131882466 36997288 615529672 315582512 416048785 906553512 944001549 580546419 828804530 223273324 9186862 857599204 206635930 835050330 316582257 836034445 687255745 202089195 55378536 624177961 828018404 487272516 820956773 52213730 30356977 36570518 6554725 769974059 513097229 585291690 957637846 741271470 859427709 285811942 636478398 280414039 669437863 659964177 982911642 189896795 9812035 29247662 304788410 960109017 476049449 103099320 10441099 704218076 482701893 199784694 263962133 718434745 539860980 438415030 600292558 421771224 389443065 398261301 670519466 656963158 503888330 945509352 678125994 860270242 878414511 891723600 6390463 721841671 868924403 680358932 737553642 534737083 80857008 744841230 254253941 88239383 494829794 197979841 600210648 910820471 547727592 908253012 797367506 930413578 713875901 209225246 76791915 740075334 880907986 186085676 569527785 329728563 126094522 172408959 730270580 446691974 621106305 594714168 822376737 966267137 360200740 799474030 16280157 990224187 276038733 890470846 379564745 709732174 815815609 622999385 305700934 520499311 496931464 692535643 553905633 410576181 872028392 567419850 861749419 754181981 331966747 678529741 868354924 181745504 439627756 89773563 130566764 586812205 483619322 317277516 138063568 495214104 330729130 408073592 835992513 670899009 540849716 193725069 285890688 801096183 995229410 283854270 192613243 429646313 9274495 116829172 828155710 632113034 883759125 460690356 530665092 918968261 550209408 133325222 448345063 726038897 53010089 723277909 604463228 234225898 594280402 429299507 169774889 336500370 267975201 881571293 509822250 178907174 703290653 888714922 616575858 18990006 569137612 832654991 572661996 222500035 741204405 742605477 489092517 868249897 227680707 899653012 245397031 76309562 360375294 552080135 92609408 617211260 205693473 862545424 440714783 557610826 567783988 192057583 287889996 318598203 710127810 274560767 805918107 17614891 505269989 452469415 303132716 119259681 118184054 382731521 137514686 70724946 508576904 740525028 59509426 126050740 661856266 888782475 663627810 604139939 296121324 467449921 640375040 562931700 790291175 690376899 520592976 69911398 544311112 746748773 268961596 606956652 379258581 862715708 763162895 724306024 858286485 917230031 830232461 490773164 691081240 512688845 69332972 541592338 935298087 931866439 370071862 116543159 380383568 486201102 748429935 602679596 791686447 440592848 179927381 845276846 958566699 848934759 661382453 496178620 697036329 311872742 611249336 261642525 905371290 981123790 756573375 52528818 43299747 757506650 589763753 201057996 330121280 931091245 948833389 805619726 333139471 705198247 90624941 608725890 389159113 724148102 857881 567204629 437496661 69235073 94416633 91456836 854864815 765227695 205620489 549399862 56501870 532256811 739239331 394599932 869748052 944400324 950173837 666856665 57840822 109329967 579671032 54296976 62987507 154588231 700521759 626825338 112752530 530139377 436279560 356116337 328270832 83438556 380904031 430439250 89753615 849796423 245708377 15954952 909386275 176146624 922329575 806457809 453450795 221262601 168861864 910634619 987550280 81175076 611448540 539600338 441662417 785633165 809748450 615475502 709952791 789906056 565216807 404251510 344203035 702391097 384009752 208853563 422089694 622962219 752066492 166538519 184130213 27737760 336831783 323350833 467054421 32495975 608208095 206166657 141703106 98120010 312836885 923651698 959162472 225364343 125352091 730318643 897106929 91670449 827360360 595364851 609290232 200529925 591437050 523963308 546384889 269173113 588229153 598276202 416240878 467207206 946023435 334527138 627021141 252325929 52549553 275673715 413776176 873803488 845244929 7840377 162051221 275207030 589103834 625342147 749756990 733024332 72245730 233308669 680692816 240570018 848993037 407503999 316477927 970817485 471702269 453504715 833486500 979596893 454630225 107102041 105398221 644615662 859348055 833908618 24669933 494879857 152627155 778425502 145315479 675583010 653523339 177119707 201612371 993374647 836915030 913722854 584422686 544047146 135635917 916694231 498575338 694178909 913412448 743445100 209157155 354803503 157467341 925490250 65222771 222000123 797968685 710217705 11813902 977743395 420705064 213727066 46822836 710676145 716704388 402158312 896160532 574466175 652369999 825063531 794955895 17579716 504952996 714503500 474807244 199914153 765728084 497561472 708436769 74967778 506806844 215668803 190912230 514120311 691568764 596893038 154907572 419543272 93183301 774945946 342903311 689455078 81557409 286030731 985188976 47708129 852475091 637819782 938121409 51594576 306677313 264015602 464811164 217575139 998507450 569936434 18634860 682027145 521503122 175085753 179211715 657012933 421650194 843282470 344591218 338975089 636921469 718498055 186798355 712179469 616758323 664228186 893039746 287728459 421701306 6657220 623701432 336540954 991420347 593612546 656730478 928754554 129495869 420115771 667884032 677337951 707588350 890218342 864098248 137627422 594280321 271320047 58449194 226291275 920015770 374224902 49963591 696351745 379628571 116650576 909673917 476562488 916574084 286547583 973147247 650953612 318171271 389376044 622483711 32729195 499155494 962448100 548270055 13853460 752236889 123483112 709749018 594233767 516846442 627765771 998271277 510078155 30404721 595442729 879955142 41723786 296253481 700584533 980409203 328327699 983965416 65669901 35464352 253565219 702013318 499516266 784523852 856960714 845728928 380229148 434171419 957916719 128642889 539350377 892515379 347588703 997233889 83865996 268790621 16655050 663622874 770338129 20378973 834737575 793526692 57458666 539530786 942144062 362425063 590100169 516669793 989747141 753564653 590449038 673576832 334463988 432026059 811339866 950409685 522827645 587437207 451930670 632394928 243513605 685474851 818095645 251938033 17693225 120181456 150146052 185615355 206283399 437101243 405471475 24114794 922891465 626621169 853428627 312852531 916811054 126209918 254185107 429360961 15960915 665646057 538777675 942824562 456810463 36568044 130526726 747548790 716923594 794611387 838037497 605099444 532287500 680778312 904040495 435750010 894566783 630224755 650947471 235906817 574148670 940941978 153295441 601600535 76631650 229809384 667945332 317103434 269132522 503667144 905429488 920019873 927211832 526320202 628116295 195186891 426327025 180236492 877005655 493328577 330327169 464513126 56200857 808328689 706325464 584465637 256375330 506915534 201696503 822912010 239732723 576365600 140821319 671537671 125489726 333588360 607066652 473187623 609868555 818513690 541710408 340662056 234827651 496926455 366892459 573590473 623536724 733844417 649048544 966036695 354271918 727178698 956793619 747866334 632052258 730638908 52947211 663481003 458008068 380172611 333986308 180466716 33888856 215778994 415929334 803022542 347261580 185405150 760057957 480858814 291919915 752767279 557414133 626952293 461319544 590618207 459201174 50730764 359802134 641304352 343833569 630183330 871101672 871215380 61972821 645244489 341171925 17847514 973653653 890388814 521591303 402487396 634910885 428253568 124975984 366177849 913144406 72218471 693575860 88603696 164439512 480310794 357724760 249788496 883203073 36285756 924719977 513216453 566188575 413048682 413059897 248261337 104574901 139559431 190689233 480263039 638400397 226436048 471480490 68512829 739503259 842433063 141323104 490818158 896975521 822991023 240822876 436144386 460396112 636509230 843432894 503011356 903894718 240674623 562439071 634568299 223999411 817552671 985104237 716605652 318387939 199383027 157563978 557892609 492676134 634123738 32482666 851413014 313107840 210655350 312477582 571973915 542266290 740783414 320922706 330214223 822487511 579203361 716517301 131309432 939417458 436541428 146062813 852138543 844154422 898801608 705440846 269905827 596383356 19345082 393392258 555569211 303479140 983348764 880286380 322149763 677608870 916800518 573342889 586671165 4141974 311576854 622926598 837428784 161613402 132993987 972093116 390671068 561218243 268733966 751095158 648766927 294564457 615580329 412048618 744842513 201546351 63114747 849336596 383563993 810769155 308574421 91605207 821220366 188551868 190151652 687746673 506414238 290473068 113621746 325255656 229475940 917424175 639515750 234138456 973275227 453528061 243973341 249169028 122479334 694819246 629280555 518762154 360378977 611351744 105551747 153495240 374862399 762280942 209694151 661363409 948752249 42164221 620326302 778278946 377045205 1391807 946402330 773655981 511125015 738013993 13809498 432247395 108668918 885284215 29376813 831974384 784570401 45166369 158270384 846584014 970258320 570773969 492031387 118974705 456601107 819648616 315926425 192563366 33704573 864619920 816675908 704600887 584489067 451358166 356855936 897199181 561873263 997247421 822383303 35510920 747562646 617257131 285046351 449999137 796933990 975346831 374453280 172627985 577017661 664228272 969615697 653469124 574773279 813242136 532646264 102458816 986670166 557684956 947463820 521707382 292708337 986717824 755803325 302209211 58320850 577178755 574061546 748898847 876249255 509370756 57094541 151155523 692033096 780487052 121132300 594926402 715050977 760879461 488923340 479457828 507820607 513706561 73894773 366901809 352476328 356937685 186115772 728700262 708655824 35218569 187879084 952116085 311116606 525576399 619904798 918818423 334767262 47306028 386719709 965210577 850173107 232119799 228812836 96109225 103986826 498819779 288194085 137592505 578041431 246678885 866268378 955088453 194342291 313704399 728435618 442845600 702142198 965407398 243512973 73389059 715710196 381266036 912517303 633361690 29431308 57923100 756756804 79039096 929746408 435988378 365964400 152466147 852420072 771654107 42701084 100982979 943377093 754080212 660253349 784164845 788676227 457514803 768785571 698994442 825015846 172644609 228475108 782551184 342984130 776629595 786992666 851483463 2976927 619838585 723578811 659090045 486554543 603326984 620029203 646288598 190168408 840015293 477228818 979459961 542074417 287774193 867981520 182630560 637227692 158331945 220883239 505637210 169268833 639062201 596617860 211288718 24226489 157735774 65711461 95529152 333265427 159706416 87476402 454455945 549356176 905780803 574253391 151395391 897360767 1914388 958534408 275713717 394192982 545877329 707034098 567613556 341023998 956428952 784537031 667407497 403545708 778941887 903849481 791679210 224423994 108189389 114413155 874266870 261392717 336152684 800415262 316040447 987122667 156231222 830007693 540167861 169870281 318765323 565600546 292737448 658191303 82444916 783953035 234076924 424107242 223477381 485905362 251177462 369398936 121717191 641920069 534698640 174661176 807827753 763251509 9131980 656642733 754457048 146937935 401031112 810934563 283218103 480990895 327394372 742321982 128648929 893979980 20707122 715774130 602063575 434157333 184379917 976374710 669608674 692973584 169442405 649571849 988416462 194969959 802686169 312200953 606512134 48214880 392905067 752125122 263035696 699932612 197153493 18658006 231163799 381786119 211981082 292207938 271547102 842740412 52654462 68023007 696426659 27991564 695610572 273094674 445094840 65361292 847115209 183402649 502499632 46211673 704580587 738072994 605285877 309625620 928706112 540608711 42269050 269490083 506905075 84183840 392882731 441507971 937985413 472113178 682224704 78004978 326516813 497268958 110455518 52088171 172821264 22279651 975835071 468383587 987105310 923171443 822315433 209660543 834046411 701801319 473759460 48325349 189489097 280470826 167084444 114480545 669967361 596241618 917471971 813023303 400824839 645357651 597109778 738889423 860302562 993839896 430941859 211782681 857203921 796340347 156610819 55406605 6895258 690104103 139356002 662957436 772257822 13382630 716098846 439235068 545936449 250361351 505802574 55131615 680588391 366341485 487668380 424899382 224905174 238540187 605093586 242980945 790321950 866631818 542801888 909352250 103030146 688747242 11255608 33636896 598780104 895318766 474525762 519563823 687554879 99467951 854406343 562643841 77452319 549522468 137688868 610672877 210654830 412612759 15061299 337410519 589577563 139881704 206075252 848016553 162962197 754177953 315340556 186202202 602326188 704030012 491276949 500559086 183696172 549647759 118336022 249680603 433973205 664346673 439351734 398499255 43744205 284329273 982189180 167156172 457169227 321543325 354971785 273259780 411038228 24805894 603128739 400607532 323949281 875625449 844382472 693587277 841684649 55333795 496491087 2746658 825139318 674022499 891455213 570690907 409232597 522503052 869459859 844879316 820711156 358903400 281860734 854940380 289763033 469967455 72485996 369087584 45732844 82406813 560684199 712111071 82538614 173043795 458986252 684299574 417136692 957043145 386147630 542074531 89254625 23070992 702983260 645217207 313272511 305061874 991589304 915909998 471859599 897734406 827653117 379699541 153914188 90897811 440465352 291885967 650392141 206644615 416546154 405424466 445353517 413553712 901380465 52218712 160196692 756944486 582626931 529652193 853697949 892033134 742291596 509237422 430985788 58058931 546052975 661681458 572102858 400619178 288197492 864543712 948626364 54412190 674324135 370296747 670817898 726699724 565881740 641718480 188123504 83913325 250162448 94423791 317426377 230611841 172639904 649825812 907041543 155459555 540689536 284561611 362637791 995010918 889419653 604721488 268456527 535677758 957921299 855893701 245220692 987562710 746982858 751848916 310748776 402928482 92145228 842751698 189751085 26825303 976963923 977945406 128564832 972080609 930536558 952889119 892839679 475429177 297709078 125725971 850284860 202417374 321070957 294397614 299705830 137223068 136966280 353824749 135758892 10621587 558759564 603368607 29613102 214611379 699487257 651448913 865038971 614288398 546305895 149715131 427873236 434102495 885965645 850820225 792517511 442238558 593941786 690826845 234864916 129671012 573938132 880697645 809573017 280376627 67524533 79950948 816154698 641835400 3414640 13397643 492484805 74690375 327123624 637539553 24742827 462418438 407100751 168461407 118831106 115621497 957481042 605619236 540054791 674542138 665853153 9493933 54538315 368699475 953486377 892703355 763967708 894083519 844759078 546889697 492841823 106808289 61782751 976902163 289088749 760782150 162732693 216390741 731950168 50658002 337423712 712990766 689137170 522943097 225508400 970676419 463074584 593624266 360349660 463091508 672407654 334908460 319265332 274986427 353910235 793339379 377189833 463469889 569791734 962059529 957057847 388994853 620190745 453829850 704559556 468048409 804585852 364953900 587575332 406876163 612072971 216645642 170529122 289707643 48807924 207324100 860008506 574329575 853995349 169323457 890728773 334854965 793738466 108273181 460987915 694604782 120566845 998093233 330709907 444661398 28210336 1595927 662317961 928129311 258496689 105931598 887681373 244331903 706063522 565082104 75017680 88977704 85788003 330069668 677483451 428871192 448025166 161945713 167476698 375221100 590710762 627097434 265904260 294055697 925834097 707459305 903900982 439385478 924043115 180599958 994474566 139696981 60898135 695419491 737780851 731692653 160279467 351030030 874933162 138011475 628214569 473496476 435461504 782755358 560016744 786643953 993130723 9191217 75877779 9478881 637444980 930940848 540451629 556821633 971050227 324490515 274324525 375085813 344647191 36810901 968464978 315503093 975006144 520359189 600873363 199580735 659324106 801478932 379772039 512464799 476818357 212215962 549295345 883598723 565814677 122467584 150564543 604475081 7706169 32497680 638715013 773940591 840345612 56022072 674777038 323580411 512688768 407118604 192122703 914572407 652011094 543084348 737758242 847686846 482293762 36077458 779243978 45207829 371890166 486842421 203873218 699328711 412842799 3489603 850339453 180704526 466419313 146369781 603835304 578790436 992564684 575735483 921130496 683433720 370618404 480085059 795991812 941112265 990958828 951822103 975555195 793210466 280866515 774726435 142169342 189601325 420891956 477306783 391703004 982356863 130847815 500145485 606308985 162097525 606764567 145887836 256981341 187428266 631419605 287036307 382844829 991639703 812764719 244449035 758079747 78394522 875578011 179815892 889411860 386914708 78758074 389961132 864115380 20139726 818949660 33480100 441788861 624562091 28312641 79408020 681799097 458858243 912613954 134631924 130991305 832955777 94476779 366064105 259174340 784782240 364794995 562817532 318920496 323412233 738079294 823958091 485172491 336883713 298893969 992097627 700689118 519408096 265810089 653078588 145216256 8944678 484734801 23466337 62093468 773511984 270459432 826151846 891780020 139875264 58986148 793031209 480065103 168735936 110100098 768165556 54356596 121456258 148993390 251546767 556130805 179899590 385080720 890800693 893837233 109302788 750986897 22476882 513952723 95048420 113881179 584589738 510428477 592800872 417397765 551954527 94722298 776274349 78170391 292525120 822181472 133160026 812288978 973436497 41917624 728457501 875660348 304457681 961996550 736960881 694714654 857400373 235903901 187450548 339963179 989285470 317011100 921754311 813627142 155166309 995525953 102516770 418701992 594172456 620702141 455594973 810663943 207682408 924188024 860343883 30164381 403227012 249088391 884773685 737743717 172984176 798687935 974332020 993400581 123809090 614117002 598846123 153045889 640830513 415086189 86877538 87191788 446698059 53860187 595358660 199763525 196427042 390006256 854686882 39478378 1650441 921428056 409970322 446993245 191919040 134072169 295023595 732201481 383128463 283362315 43692836 907881484 159529293 549149466 960450959 106983815 90798003 738325214 280969306 720023828 553964117 984930338 238243718 332832243 85828841 770667875 357443714 730819016 176468491 432238758 805966135 910584936 683795740 397026900 966593185 441348360 859841477 968760353 556678690 128485847 839893529 54858063 523363011 758395083 300266741 394559420 721367814 613237858 703133589 655220672 560135570 868193308 700057826 220589970 457939488 257457817 573840628 829645914 247280368 98095311 415618159 315740895 701936060 760328909 724359798 702130188 484874366 956502559 78548453 649478057 337067755 951117332 503663327 169072649 55283970 215586152 567688716 215412256 747878855 6838335 47478716 909133295 406990795 870774142 356964811 765026304 859041063 670113185 164858520 244408473 686338234 76442173 89970484 653562517 258125000 355770403 222780237 957896070 756755882 301145783 523907743 932259276 795610310 838634812 916256796 448490362 731137226 523634287 520597266 453601609 794247569 272512831 532371421 289210725 17505834 847494330 577943564 463716545 449794905 448596291 151295891 269164782 450918535 18650738 930686833 132948068 798396019 421213576 886128633 36555363 839652521 150690785 213074243 371757560 458619647 478858377 496475267 433727101 355548031 312117821 709291365 878744699 813021612 523566886 313917421 181096918 931079426 392979480 896403791 399924834 343229046 8339265 137339144 196938947 176728427 109582425 295364068 582851559 788952373 928589830 607085431 642243510 554390352 782707448 739103330 714614762 104801072 278812527 713803463 655170965 500994428 718108947 36048529 70888729 379491849 54211465 170669955 615060300 698904925 671134329 73168601 484024562 116437857 630093709 50147985 656275966 933925426 230457819 119164300 243731344 544548792 396239715 448515245 992744279 281684065 964855954 651712128 104517390 849379306 617084915 705335879 404489744 420808481 131736637 261527189 138680650 115390312 59948706 123636826 984261522 854501488 354765686 900807939 636132034 111695336 866374852 330627510 287422150 38375948 569332072 875229623 641885584 115174631 985384808 443669549 656323189 557740039 36001840 420291041 641221177 71961462 310536751 811204134 426458406 59546219 334929179 124626516 285624064 772766608 689752064 45516745 806505135 681858679 897373658 600698172 612006445 728183018 555403879 921760367 94373584 997379723 284802763 389715329 122126969 197259575 950480111 675253764 342878021 55117867 420709353 44167056 774393977 345741426 591337759 202887406 45590122 58762425 731503925 571324173 230760456 499763291 795308613 39376036 181168052 620688358 437637753 483110462 57634536 686677797 144777437 95723644 354033045 471842750 421500655 122671543 177437295 400375443 404545767 404080172 791710563 409371459 775250284 753798717 864966140 231490372 896894513 431762258 139959876 903024046 900193566 720889479 657118532 763760949 305942300 369304649 322840985 184975077 526501829 130274449 963511365 764862553 220910304 101788455 741244243 946914756 498817002 97166232 542422921 518725627 212372373 906746345 688902999 743529680 463404846 695355979 319751932 809260641 50705105 477125138 276903080 131022993 294269555 534172373 307873479 745458883 912512999 105810179 18030677 987202264 470482642 594616373 83514953 177247526 755438905 573213863 401072329 97306112 718935965 287829118 907838193 964017738 222412212 540933143 773919477 287020515 889070650 882817784 966111198 376018657 857772987 746350068 43832729 731974932 25660287 932951064 790058883 46200419 805782960 402375814 538767261 277571793 314302964 733204325 490391109 528950303 259526446 67034246 809615078 541874563 416810453 364339810 667953421 78931907 711841214 720887323 175691570 843063465 555265210 832031255 850744097 250850015 874571193 497764062 523930033 851830321 36554091 144571135 356663738 829254603 785708205 556980711 279193014 343393987 287679190 645639028 365678551 963067226 875051736 360713848 266933041 984434612 571419807 714132689 450771506 314020115 431029018 602780817 646476329 578194437 236191857 672710170 972660916 967327436 846781216 859774649 694247229 95546607 9000072 862355331 909700092 670585063 985852456 175906816 332179715 188069721 917133526 708944413 98438446 2702368 679526482 90352014 7196907 931997822 147283257 858727177 978770558 166811446 394317673 439427551 358953508 955623826 709720089 890629033 526623725 804601178 863050197 313850853 427705142 118369522 394796748 982340764 805760278 435263278 640059477 466248084 382288761 529197384 478553740 733756883 524339675 682820632 142476898 429316201 940977500 448837340 104001336 794061903 683111189 937022777 696948538 453353869 467601517 950861418 700582482 5489522 974920954 902842704 69381688 243858076 601200748 135688494 703856182 659677107 231561446 933532622 829963591 855137501 492830231 233346276 658387859 181503244 158730444 391344160 389866903 225578196 498733348 637842762 924070689 982281329 255843495 388249776 659987524 458056880 223097165 205543833 426459004 476602542 868315076 553974473 162473590 164057611 778912152 969741114 471877332 866719880 953241414 732911794 465871559 920829970 471402319 580863473 98527833 727785705 958836458 447693822 364555709 280246439 827922358 79734861 377932942 70181794 202864306 315636804 649615123 51915214 536914784 511996568 528581817 272590710 842499911 702439426 682536561 312173387 528619139 267417897 457986447 381013164 82206275 347789568 6356729 68613614 237319948 467593793 771428128 234305629 867715670 478845758 663363639 591096549 661432759 610585832 299462291 642815533 597496977 615107886 786247457 357367959 971974405 232069480 959181175 364937409 569236746 197778994 803576260 577458791 411415369 947547655 948522508 395568818 357985175 186906872 974828160 360105439 550879098 158582911 439893598 212726995 262054850 535037051 682668775 228183103 572069599 108697761 221163713 256259821 73981187 408299008 159448940 339729684 691493619 106652421 590815054 942905982 317563524 358840368 100313465 936912215 533741471 230901971 591820837 460237561 86580650 169749045 659252452 140855031 303288209 756103156 499423619 343905464 161039607 703412971 47164097 927951211 63361523 72802099 946500898 976023550 967086697 149414403 125341269 977695530 48276022 660157335 698422397 907707245 539733147 914718988 616398859 769861638 701346160 239872658 448831265 875824530 662770477 790984413 702929430 993614471 112491754 749721854 178048801 744065714 535767803 757938767 849231263 211872803 672717612 891841245 869604376 723035363 8835251 115845110 931247584 362013385 288246382 33885668 20104158 992230878 794431177 446841270 744529730 940530240 379254439 377042545 242716356 703526141 787640730 293207434 18304254 584093737 39915026 252374675 856408294 354530647 669123767 491978256 94245809 337552772 891830418 159779983 928761484 841509324 780148396 663050369 742138005 340884764 892358586 234612381 878280891 130276839 966768088 218192399 700374632 137704880 516832287 188272342 512053114 662877624 499613929 27363111 323732717 964517256 163765965 911579231 437590092 425856464 401635463 25339780 686613367 980905191 156121398 861302646 284107882 466975630 414798765 186551583 605802489 496716642 402414922 851603885 513021582 593621540 886349311 835572066 973507593 364152862 511648672 532680550 953889709 629397466 301283505 981944750 358294963 109545934 884991230 414959491 571844954 673336371 686198805 335821885 951750331 841667002 11724789 16476986 305895166 89687082 850091504 233117101 267256433 134780081 924697794 542293697 434234346 525199010 641330966 67278604 493750848 546666416 718831205 262025239 642135590 45159190 225841800 434547388 61906548 188886828 830954316 599353348 921209793 791617567 783041288 953367972 131230129 166202987 849723567 900850042 103525212 364402864 48495218 739928209 699047841 804367660 576328378 160800578 71800507 655420773 84774923 743849160 468378660 616769555 157684810 724102101 819177835 332068145 993907429 399872430 234726921 806046396 371332960 428992175 562327029 45464681 144538872 14810194 267148570 556913488 279589144 867322333 846704400 981203630 224763529 269027389 362910360 718685035 277421050 378167384 319563476 621842479 185991534 36212990 422885054 837907082 610579069 244831778 666054806 252717027 721087511 260508365 37805847 979371396 773397092 573151485 970807840 182055955 222681941 364455692 158728202 890644349 329173135 357754309 305780323 201076144 553986355 958238267 351950102 699099168 756254266 106745867 780578765 585522977 648675469 621393583 874288319 3604673 814801630 753947763 142883804 3785393 75365445 792815486 299218857 434152106 834625347 150700711 407432305 696882012 111961079 166098142 142103043 412522169 702783747 497894853 392658460 619371294 282626331 306307064 570751253 163367540 79147331 634569408 270851584 898666095 139927238 29251051 586464368 417070309 318668968 499002914 360449806 823994032 829886925 209999903 250777939 301759546 237156910 149266324 405449116 403617427 945223096 264360751 722670707 115677167 482562547 478814338 305626731 812463379 387058844 554529158 921601187 76730747 922381861 25507463 677181032 358954475 791598669 831761512 382601307 313872871 957513882 585716224 34875076 740712937 945262165 338656754 568375373 20645825 476032128 130446965 113059541 727181706 883787786 688125107 232572689 781019247 306196744 39651903 597546915 981851594 164671614 582404077 761644473 821315341 9687594 123739245 593285600 11474094 665587459 856740186 601665758 528901502 188769388 188511071 889481316 706280516 661207491 978090363 694492511 768268261 833462675 726937965 265579623 45594636 936515288 916593922 910704163 129761525 431329355 903041186 860941261 764072389 836434040 606327207 478030176 32157619 47950451 887853027 243915363 379011789 39465206 152396441 864807608 291382852 70095753 674369088 147963172 284057841 708367605 133530025 853474009 520185917 94121956 764344707 850144175 839386987 583202388 366477055 295689267 41964574 24134756 89633043 906761509 282457066 469635578 804832603 219832144 269533398 234855174 65804258 811618575 627638513 35700771 391473966 927394270 535080761 943564739 457305805 114301346 492646917 216543625 872918678 950216044 756109285 415980966 973224924 545579254 910950747 816397807 716211669 112473894 130959443 240108197 101812904 792361366 598720780 119579128 479676382 548491989 747918419 49848998 435179565 436638281 376626361 548175980 650745048 78839559 342951657 252764382 491232531 553534651 4522786 707968427 794543895 544488108 906475960 455648991 433689208 44227285 31462892 67135671 867528873 678104359 131952904 246504074 400700382 621895771 940572688 413104096 256472689 849187218 487650379 968916803 646908349 396435249 944881452 445424685 396188420 526541712 24665329 162645296 183224039 868771076 906082691 648488220 387549499 373805875 913572165 670263014 305546150 830767683 700514916 821453102 584010561 705535689 743948645 716432488 547381516 977259450 564115981 971473485 882865162 313176404 640445211 979846942 902297262 503327651 756290694 939740369 379376310 590486277 19719671 296049789 888951615 430299703 220248034 737229563 801755423 264388277 703454881 638609604 929747404 115680570 437618861 997116386 723633153 268840609 295156151 571290306 866483857 141414663 127680750 378001355 670589654 161181417 708951054 795326636 502428990 25260553 791890152 886637685 422725236 903763823 720775118 52034093 662740583 536232693 27570539 929354104 500888131 347800948 675499030 717717405 918470821 41957887 961465625 692377136 293542131 534920016 567982940 512749528 344840201 342088416 636157519 704357170 203276885 423580185 367934000 124422870 788656328 545064469 95380225 318782093 107346757 154125419 178300099 604906864 370353996 988489592 324743301 378103048 152122508 482791098 544474319 926090971 609919013 187157948 257558926 557948394 334922729 553392816 357354227 797938348 663970207 518165902 897705841 869643050 666126422 551117439 110394439 866144108 389282525 349663580 555284328 81552669 112959599 798744383 553477757 654771201 136819342 335747217 278304055 516695257 217431643 679276001 544352934 697551627 203551884 497800882 833601422 383087353 154270902 915924250 81264260 290598891 778151939 467178249 472624721 939949073 782773215 936982300 629266792 734836244 613863722 430600991 989396032 55448208 303325126 188159073 648979143 61774932 106227316 599152351 860589871 741071333 632797373 135866135 296804503 712481720 761872352 762136093 514175376 630213216 571734740 501241291 600831275 317733616 937913599 503830808 999937001 627354391 457223819 486552928 520418681 483439699 181926198 180219785 65278775 969156961 30709407 743672394 939245742 292859533 561987773 990428428 704081826 192595882 876457163 720947083 113894729 788351700 649882213 894776554 689452360 667838380 918526495 450662776 722847404 951818093 101755210 693046859 666708388 752087173 638978331 715707232 813317356 874427395 952024535 605137269 109631456 35733106 642566963 899513376 250426230 28449805 57804060 999312825 223936397 556186964 166724487 431409993 969776934 460298460 789085260 123276975 243077533 49153369 622068204 394367908 46854351 25438166 182883774 343169918 780717933 651101400 756529287 356149748 455767977 352963296 898312164 831091007 273878048 404417738 687851083 562678075 782643927 597531112 360190403 933455341 641299205 1112253 319700305 167458283 3429140 113671481 892248419 994468728 970821072 167166684 216248666 722609585 847602013 184605088 11043321 622685202 507313719 681053325 5426357 530391716 243203241 36757963 734083558 62273981 583944062 681841461 920754256 402635990 645083905 684296763 329242212 642045232 659532869 176713587 998233404 713319631 248301382 699289414 25689282 993847979 680015093 565445320 162830453 31149952 873301320 666149617 800094654 879282948 175876762 281586414 20505143 765446055 181304912 9115914 899129627 38131806 338166964 427696428 812734919 46500806 560630141 83558615 350766648 563781710 183958416 357615322 992157498 796589222 785255766 844703525 648747603 260923569 205095538 285139005 783404554 48071248 205377208 584025508 354421948 273275462 659324497 667150709 390879234 691655982 999769319 161452303 616443879 699616457 993349306 957514658 77550421 294555183 271903807 856138865 66163296 919634357 460923829 345100991 929281725 829907267 984424006 112226562 58129312 133274174 678323868 166283574 944917814 868014439 876148684 295377077 201171702 929526195 168205011 504204105 752851808 717208259 107687957 706019190 888030871 237998181 630881002 816793011 255170332 672003985 762218895 748456149 491348826 839572840 504746829 226589233 747304661 794539731 514351520 240530898 707400623 469777033 622433173 829375804 136498049 452134047 440496316 616479190 192959532 879642273 151202446 386486061 99567036 459655229 945420305 258898352 228161424 890248853 303874669 683688746 900353739 10873280 377583252 562787697 524422065 521882719 683778926 870792318 603395498 945540024 53832103 608997162 550057997 740059336 179721534 703565477 95826304 538048166 260326059 850138229 842613056 299185091 416284642 197531936 857102242 161036612 836354525 134060836 279772084 301742742 505927207 154384765 376663317 44428535 605307984 657360716 728191475 748196589 133404296 48245313 799068921 828642713 241079138 99257365 931744809 446563862 271570861 728372157 798429924 334635484 74807044 732071712 683808098 394779197 752686537 993683475 999827686 838086145 726657883 718864726 692572803 42988453 357909325 327043297 365498492 722810912 32341764 482449008 464157536 941470928 287859988 809476192 980668539 235258390 472750961 590572592 862150520 592964748 974830977 541677110 93898641 218869668 954568826 977895130 934893804 194840445 882563444 285264204 251347095 361606717 584600420 288682156 60403156 85530510 777702182 307310334 235036961 208691088 108999486 632246141 367183382 299206674 81077695 769161068 646024932 241003882 186500100 134528132 631469339 573121381 700412928 150675439 622677380 874272955 502770124 474186599 510716143 85320900 173300725 898255791 598258415 459863627 771760641 238332961 740244083 992612230 76398045 26586294 237533438 19653800 876167248 138615001 83870974 446884487 37692608 330120760 985722737 688932420 785616078 132286090 300950896 758701351 825966637 177303880 706622258 222055528 505726182 486513094 51211741 571403311 263917320 483495208 38904741 462124315 840196225 476674364 500773336 859724675 987217284 214508225 155607864 141143890 406686256 547595576 907457170 652252169 184147277 2505259 806376761 36612890 800624458 914882561 732995011 556444590 140979896 923571933 735528810 312749851 963496813 155568706 701531605 965496064 524829692 223602565 361345441 790958859 656561566 892959036 193848166 839999989 149768824 490845798 283020809 652910533 780550844 49242372 195981262 284351382 152986312 231098403 205937731 485242743 55148232 353813699 263300675 899215562 215078358 628580847 79435531 272893615 333440456 953971922 906440044 976840551 230458876 654344950 70347970 507874280 242182258 978269290 138171138 67417853 504660176 442426825 338511574 108508403 544156655 915190608 884788298 921709932 155525376 668241340 225255862 175955557 202287450 404123089 60171451 358416261 420198566 818305620 714984809 86253968 201042693 362860612 361403016 443311517 160802990 140195444 774604117 941153166 270905880 322940763 856554286 139111788 424975063 161654600 954221711 146549829 167470152 267616985 774352781 595902699 957883642 482706326 989056547 878786145 792476090 876027006 650151915 477153517 836577731 354442413 485037478 125644581 113852758 488144675 93839464 939679067 373509495 616791277 4941829 236011126 896689118 647908184 302262572 450081838 516173180 732350778 611839039 740297618 361102468 472669549 392360189 942347420 341426371 84536622 830443605 381616731 811165572 638895694 331337584 807814378 881088843 418175447 797308866 702146709 168543197 3970282 763535173 704338615 19034125 12929659 519687118 561958285 544072355 937747559 928784803 120579299 626706187 957997261 79660370 45210736 941702164 283388474 609637766 838164504 161597243 318522382 182699689 115255556 387855000 450291239 116149711 925212565 159036371 88632290 40361281 686501677 246884503 885703254 576325463 758165089 573467630 444260413 826958213 148490245 864140772 175012338 202904912 886899887 654531270 138839971 770359720 611381768 868204152 198101697 295255237 755235045 319163730 843982007 486282849 57048789 659503762 622835807 920547165 845406772 101299636 256560515 975310122 565329194 781085870 48795054 486192119 731764558 462026961 847103206 337160134 825729288 382653784 986922164 376805614 51174662 225967667 39207433 435836313 369419133 518046599 624238079 723227948 878264251 810911034 321068459 892584451 596703781 642128771 320821193 417610258 843457642 79298134 514141445 231469389 809284045 997889358 278059804 765040876 322930683 881934562 529136025 49771583 654513362 39403933 827594881 997312251 176694097 281661757 652277736 328191011 11911079 6899502 989803074 223884206 842711510 903802824 630170655 684293753 938857238 339672563 693888209 504315745 473889467 820697607 197911633 334089770 486444593 608924379 451013064 863257978 655030791 135759644 86596828 428189011 372028222 564646244 950042271 702504736 470185497 706945262 658201876 917280647 700397381 142245518 751557648 286186420 683731767 933583718 742764089 69022625 94467443 450217315 298883830 115721226 708397480 612445584 841329225 667202318 602245888 356480891 880458253 440970089 106492733 211723902 975642002 388913202 100794587 270654061 258101628 301811702 451106646 723324243 170095081 290785293 359786107 898504854 244199566 117031072 764820458 199196326 793902978 588012968 566180785 83574365 822969360 869251456 87261892 357438468 863707011 564543480 98735810 69738987 508336434 36456279 337130276 778967537 21801327 242049465 133756934 430653530 923576555 2955342 82166489 869436248 760949903 823698663 164803603 270472344 413504670 602391194 940635055 62883645 767628941 69312016 203854840 208052393 746643344 901716507 646353671 743768352 161755916 526177583 964225885 893737 370427288 397980787 921934223 573823560 605219396 155892674 558553610 541163973 501979452 809164904 23189330 558102874 23907959 699711631 323233808 231681721 267508584 478812328 21824110 952074343 266641003 492255071 262240719 397205763 443542361 444251705 977895098 703058783 725950859 557537151 711193059 246232998 966285899 707829741 782697241 563063890 29579091 873955168 398925901 620134977 570774590 165043903 976583117 497569404 633776843 76359985 832926850 282098720 460063514 501425056 60795029 821278182 851759820 505371655 312465218 317066045 639804098 714043608 550491330 847076595 829378195 159556494 144652685 654703366 921504712 170222848 957950384 601587108 609589361 942713313 239324650 492538084 989314462 984530233 953004490 36529902 550186101 844332715 531266467 25159981 28068898 661973012 388276944 501821140 104658144 327617403 499765281 859153507 559127641 448237761 819852954 755206752 326528314 370379422 949849715 635264974 14252595 8867474 369617369 798183793 25445487 180851932 777606592 77669019 485439060 577607001 594027712 607351723 869915145 737288757 73627198 761889049 69944503 459742581 643926647 749394315 318438348 755593283 34514838 447116858 562546446 279623819 900207579 519662934 947020638 904578448 468043644 482396671 630952527 860439553 146783182 263274714 79953231 267990525 791415835 28998946 253086515 770634958 587753428 67124481 777214828 497215292 308908229 132894115 829673829 660741734 866005469 349763666 839228005 23053590 962279538 571621758 390633764 176168205 118698125 788230964 623260063 27226764 683398599 576166991 539292654 88999986 522503250 869887798 179854075 957054507 25452837 930290647 991878595 853112438 466647828 931326510 733375236 648118037 713259735 777900724 25176680 403058879 299948617 63324352 832287271 311719317 456282318 345307781 445017452 747165169 213025939 994283977 153124048 786076288 916926923 965519871 618249219 610901115 561290065 310719856 555724483 113843464 696925616 451129787 231744246 3580915 275166479 642542579 390812532 281194940 404686880 392455231 953098925 855612140 356375446 604003681 942720377 625709920 525529365 132154144 802450968 804180568 768693455 500342393 786122597 671770912 28379242 166950207 723595900 338370574 7164218 303295114 429033710 457178278 412507489 950702474 17037212 11842571 258129360 598976758 694393148 767222744 757096223 114718681 762368652 641299983 983330089 631714190 269994375 518543986 199403044 645804164 483110296 185245709 75007094 367750151 283199610 868574505 447644380 858511523 585003635 708542622 304052877 440654684 43362729 14617927 116830056 175790691 935394690 721781243 196707681 918170712 295495275 584328270 873621924 688069238 100411517 362658334 576340946 878939260 906261376 959082857 951623614 235089236 49322987 320883898 449119764 264466928 476738478 87152940 243841890 337006985 324239126 866534675 45570886 7969033 784703687 814023966 108420529 775099550 589120001 609604869 27815702 454525264 136466686 592268426 733670181 546655887 29683237 961446863 334844341 624785888 484115505 489905733 161335876 28704766 197032122 56742051 910484324 309503166 726622346 560909971 43506235 989791046 587630454 511195714 268694752 390706066 912211795 661658085 789251000 77516656 66014827 635528933 90915140 797788828 957634407 863963273 843307680 717214682 114734330 124947906 527539789 281875653 313538876 299297929 650606600 290678342 949140074 202093489 365081363 22635624 798229942 196528483 467578247 275111762 633606506 987213049 28487081 853865082 21546538 680308586 602179298 546141059 334355613 775703865 34411638 141794996 509733872 336518969 824792816 645137088 86180251 279526597 257298073 405087162 546386622 97004525 826860320 600836257 773491574 718828591 431373893 393379654 792216205 349827897 814621482 395435298 265533505 478799297 724941986 99266309 708270624 89629158 505639797 679172759 338148821 672324100 513477430 210238907 594418453 54530649 557020708 777992799 43674427 242634839 622149763 993914898 480938593 856920636 752114130 545237217 520409797 796492452 73488250 881021174 377233144 274970341 832122484 884850556 844445542 388893869 273868019 941840596 788065173 198505409 433219030 643310773 873897523 864633976 28412240 795487467 647984906 28154951 394595080 73006390 627605204 685002364 94431402 947494489 811924285 674279540 594724192 961178043 780505387 3129947 780126048 695039135 355659996 261004842 372630925 657439757 332799212 570235670 20569490 196140111 397970504 819099955 287990544 772354455 956325789 809131671 864329649 315004697 29425838 196915313 242123322 943361750 26939675 497156705 239241903 604825097 593895185 463616561 15413819 424000998 488714124 369515960 862292570 76842808 528892156 26105582 202772807 892466750 860183385 340130043 143731497 600167272 966825671 271990093 426729679 338598361 193547458 14248159 648525097 775860518 121978086 759755988 880204734 613204701 242397711 146700365 905978432 544288425 950840407 861648630 411947307 8995873 589614649 374232237 850980015 767041749 402768872 780061733 338561425 214324637 657436013 512416117 523367447 334326663 267168910 45583225 879379074 657479545 360122615 702866277 966066722 200920792 525108280 827351275 602114236 280429153 235001383 133956491 819057475 694457684 72949638 286074353 444970113 868787198 330697798 374274256 108764386 138242131 746476492 361661863 715452732 968964502 640955192 101801417 947831726 936738027 492610773 437185259 323493478 274252541 753112067 508575810 526206812 212346237 599763130 172042738 565487759 911573061 848544456 949899740 41968083 605662069 977097422 630904380 533447253 373256953 266719756 134398951 690257889 852677945 210484160 657627967 149730630 689640187 530181301 144032825 988780271 946548239 60166163 426715793 384800746 922948575 146176541 458201905 637430151 791416469 560538747 607868236 504873946 541876527 388052787 677891624 847468724 151710683 292082337 807847687 500545129 211537652 545617693 572425950 929640381 785969942 686117101 868822766 331921619 156805061 424277363 226752752 46690205 301833890 440087672 894545967 599307946 967502219 764591660 545294757 923036907 565142620 225781626 43587375 132236735 805974392 611368679 416547699 76077025 498725766 318862656 215365913 844412410 375717316 464217580 169592000 879454386 811611072 565044287 901774646 317493384 384614009 245435646 163306395 42649110 201801196 387946034 547547190 797312475 688649877 188663887 470579555 852836095 431668267 686502996 449991037 192647140 177056568 325947150 801199480 914276763 238296756 693118544 277578238 444989934 465063274 781079695 130543374 960438456 522144331 581944897 792814909 49318796 214822622 188774529 397502436 835161120 461577058 624637312 283164785 96362092 139898897 991546408 55981190 680041102 258515421 602035192 734811575 487607397 699471161 970792137 181732665 489042594 49149543 675855776 973845350 739903097 488342657 753539199 991447252 88799514 405856590 821965807 505821073 734460031 187772416 659652407 981980021 120520576 391416278 276660293 532940331 574862851 54610822 418991171 877037381 763965835 746457096 276487311 424958173 863777239 884729684 159452596 271835527 181061736 667818135 204378393 881001497 731373088 536885671 45615558 731201532 68263237 464808438 28152247 205665568 484694809 591743790 954775064 403709194 975906809 728031299 84046927 825058796 594549808 336874593 360893294 195267289 288357028 237245472 754418285 146136334 292670657 325228617 351424759 321079153 999469613 213872518 74043831 571600804 563040668 423765019 988640199 108927027 292317983 135293856 496837964 297488858 788707795 782205600 917577624 508609727 402303892 277878473 387193337 349077234 786223969 684301232 840567817 524582002 358043887 53343195 752028391 448906561 899349225 280539410 896039430 795732951 590995954 917677850 952763037 461730754 84467707 214132524 790121074 336853217 730217468 526141613 491229131 729797596 747273634 889325769 806495115 338904811 423530118 861769502 613820164 32230495 677154633 633398992 699824950 328613567 809529932 279381539 653147523 282155943 379160154 745603832 135267840 183757165 721273394 92060957 780379730 277792777 313464643 764499442 560835910 214908464 500512590 495261592 909732746 552044611 842422185 412534679 79541546 339818263 815732405 358240257 832415094 873112368 458282353 690548706 341815447 628305895 31776666 734615037 706657831 791894557 727009618 780187680 629112122 282521034 429613379 353144647 193660169 430231355 786148900 753285460 84070233 860043657 515088404 516331549 584104952 867752808 440532435 661643109 239877399 384522013 584407269 201421759 577284975 249477517 436846710 798799322 580244519 603423576 277060691 535020341 828727531 51414744 176932977 204924828 32951841 549841243 481250707 906808671 267110949 91810339 768296087 695440204 436137241 488239146 911168980 870925701 992780538 451530674 238900583 98095543 70380758 140180741 336245313 289923506 65291054 563851385 964290972 919953178 249960604 358143290 371574077 393673139 972195586 98850226 486288076 123801245 238388469 354249593 315442932 281575789 806794725 221241276 440593338 212770307 411955637 62515644 660131627 432920835 755690882 361715921 140815385 439580101 227446105 396597207 51199321 950919275 502867934 497554497 621633765 222196333 148062907 149544540 783516320 873856722 508736653 266370196 958826362 964357856 743713385 958435525 858305010 664179036 481046484 431129720 979624340 415936291 638721406 232107018 811271835 514289572 53910500 464164899 949447098 311005340 42724247 262289990 392623303 467770917 333170024 770766637 459427300 163369950 760123781 809122991 309528491 351141347 297336957 720380401 68317792 208325905 353045586 467821803 480692083 326409141 364113804 235463812 67034831 740683811 488345374 723851559 836898151 383381161 375700490 804829812 563882346 795419932 829682994 927525688 964330920 982720270 406627210 459685876 513224088 650036502 239479670 832465971 43747192 952961780 594916903 493305335 812845165 594161909 779940302 350461705 85463696 638109475 919681072 845730601 400887209 504716057 5193408 31835124 178893471 378361162 566666127 973062194 885101209 964533477 517196471 584236930 882474457 995375382 941120907 471891522 370181459 13368507 905141598 377253489 227923084 553243999 28430871 339288501 456988482 710172129 997471894 888697135 695688453 618942916 673309108 130581258 956617888 141946843 161652365 938415555 65257875 33153734 464187394 421351704 732673246 273124060 872048764 199750495 81304532 660011782 857792228 75225566 763890878 179554287 649836535 789945444 516412652 326251355 84601855 661149907 607721556 10923772 5172575 506629668 302575645 433616965 775676144 391902869 530919271 62788657 821840389 381328962 987589218 552732955 713013716 780662812 114231853 275484216 99797059 393494178 570482439 185628018 533099081 753332665 454063361 953035861 862911456 70539459 917703449 432627050 783562961 490738312 595995915 271946003 780010186 809403548 113543732 757401184 661442388 276770632 532428645 745854507 824050875 29266363 733610298 623975483 324058390 673405795 13656920 667857397 430030529 53944707 596657459 924380305 863316631 512503579 959020236 622976075 557387193 483186500 750282563 435757389 436424264 698279280 641507997 43034725 285986234 579458652 898644865 785243301 345083535 587685487 648399594 935562580 416519035 340002290 128629050 857418655 995314076 740794898 180368860 520370088 199208874 919177500 573095166 152253586 352812160 211956718 905034640 489148234 667420404 303916408 15911664 276889268 908955912 662410919 575303331 245362306 108305439 13143568 831586912 776216888 761820620 115249493 399415288 561079251 796591678 856901954 873663900 707762256 19137753 875660131 838162330 877177443 370380116 925364833 871565572 617139246 270300723 368859820 301047195 269153682 854404640 482655705 754453731 823349474 163472674 110224255 498421215 29951864 747694056 713912459 788354148 387968306 462695690 380962538 408411874 627774325 641571146 6465168 572348852 428391962 849315474 602725001 611969518 227729399 733627313 641119251 3776647 602060043 719044932 384840365 86573984 150631750 538253442 855335997 130296181 758747271 31238738 388570694 929327653 639140509 813443700 884147264 230834210 556884184 594663931 112239459 143078527 418123211 820321694 86500385 301969545 638318450 926492207 959659707 789111950 876996653 727274438 872085656 868154019 441758201 252793266 743665552 272470911 673795860 725777208 487990978 286965236 26082990 133679880 952377107 172162082 558715803 995925973 623434996 179631517 777489317 583089767 529827017 3090083 403532813 813444888 366176268 519517148 273015170 97424892 608326076 479328424 709308558 268439929 478930264 495795647 732012394 306958704 634604559 819952334 74573568 32148736 388055352 57080142 586140897 293864085 87132319 725901092 21512243 583541765 717838997 215773648 391219603 747530654 201632957 985138902 346522862 865211077 253875132 781040732 874893696 212134763 687903579 737378705 202908442 216975988 489233504 540266397 27854936 468398700 163082279 740855169 392855479 825622957 257014712 439422850 654282891 161766744 284790059 940412376 128001760 51709080 358198267 843980608 79301463 486838337 695679131 456813026 74539054 458642473 541450884 597311246 590499068 662997014 902703142 75458881 93432327 419458351 321467808 710384638 866590314 931378347 525641265 471853848 963719207 278350710 799539217 792598454 86774944 268763493 933649800 428292229 747568939 227414405 508255634 176802498 250698397 395359397 857766957 645648467 277234930 506276292 217364834 458335930 116027893 980449181 755945444 710643190 2331423 75345265 992162440 431345371 793080021 6978204 974232935 651607826 237433586 320752730 492276618 533454468 238274861 667234300 479701326 387327630 623857187 123116015 415996490 369141080 778645059 658190145 44979937 355982052 426044332 52751187 326578264 438304585 72741092 816146991 62099838 283396381 967489760 98840753 55335508 424691833 234805256 108897040 490486152 524814279 348381980 31707383 838878917 819438126 643206207 348760376 825784814 614202416 867210443 662162545 915514574 302646705 736052869 502714688 520422523 590017949 866667374 535505216 808721288 586789455 237269494 346969566 101996408 508458344 403758541 437455237 366943103 285080455 701924798 138974163 868194020 22986463 939262441 211309969 496143957 389923525 330206723 25110021 955239968 588585508 362331217 919928445 17841335 764144455 577727216 937962929 750615936 522469867 403677988 744490731 656016994 34389296 14195147 853846831 574244796 653671358 878720685 713181316 594647439 51935668 68918533 430132461 951873141 27037319 562693750 300716948 212133988 258283049 879899128 219421679 278943974 591862318 917183990 931739862 170857371 715262373 76239021 210283794 875883549 684120228 727543745 307765938 219714136 766518522 239235599 892761940 509531888 577425544 477035080 92336601 665976432 831413478 273259052 37304175 283037707 678359148 655568350 977782581 634894842 619086552 11695180 511480845 564464577 510860052 464348382 903909505 681967578 404205480 239680315 365268114 86516336 861653330 618788797 117107725 368735935 395234941 664978237 84496529 742673709 353817284 481648369 247137826 245468105 164184121 819682213 309654733 334786350 342031651 225441814 602370153 15386342 729645696 877369361 78216663 488401583 103675712 558105658 114901820 170388657 67280072 601440187 765922332 752599470 820939122 529951823 930077581 414841941 904168514 200259505 989616782 748807241 715431066 530870693 185176910 890550521 789352437 808601759 744026135 976743710 194911674 275669099 368879143 384465300 643469602 743007681 554061797 689678864 505471572 793499485 955768566 539196463 714847919 798574070 640810967 361622326 939681800 303966479 546360960 885700803 237419989 315833832 836046944 142108545 316190304 98202507 189881701 9529292 363696384 742172068 212712877 825135832 633002626 205795157 208710341 299369096 322290348 483905889 47610689 713317869 186006812 155781416 111177623 982152451 883576142 586979447 864752721 913809317 694533163 38700063 879279198 121740384 738686997 329849166 284780159 533158759 787085778 276148424 512723056 967544387 470703039 988496223 235926482 103828360 773591480 363218581 861346848 797677299 327853530 729645739 959005859 466074600 716804102 852578814 162731922 493834418 529893106 100770987 275584171 514773040 943398833 27623422 905427294 508365149 479555212 676283563 398761700 421450615 374215166 482308942 124400912 288661872 253243504 718753442 512374023 245205021 723722097 208288962 844183068 679877170 647254488 433798369 239094927 412346448 171352913 633329862 536607537 898066815 691074473 644472918 788811957 775043972 894393505 790807272 635403547 459987612 107899921 618241395 739331866 91383434 401213676 695109150 656032055 828732541 176459028 217321136 563735372 874282896 25978248 102377007 303449807 532620222 160331369 958786890 439254300 697452393 615250399 436162936 265942730 5708629 752950416 578948412 992342445 957035120 237883843 931563661 699592558 542147941 691528911 994107823 98234171 353228281 965345407 606011275 887662795 669480809 260835396 398975409 440865857 847856631 80033077 552687104 818894521 329693685 361192195 394998349 469218932 246692208 220281501 895540975 624531309 834477001 393125431 578471956 476204781 484687741 399121973 933946689 155185360 228430661 256544501 709774803 591457299 490065865 367566284 225476889 61383440 152739852 715338500 409098787 174652254 735359212 767973175 638316887 983142608 83557906 188077078 408488173 146930019 643775046 34446682 352808411 5306151 505812622 387704678 608796560 768613967 470620444 18077886 571098163 58969442 855349751 529881979 417837434 6552280 253916832 471439503 543705481 229537932 657296798 578039675 381078755 803667915 646179723 237595372 478532329 442659105 939457027 291562951 585894593 751925410 633623273 148259334 847480020 51456896 93860522 188352637 572182000 116539404 844659865 962153573 615549253 259055653 192223692 247607120 678713849 997725407 585495035 382703546 212445423 654650104 740854383 99088113 748543498 161322236 957359218 935986458 642808197 113523032 398933935 923389462 368574716 997113540 97007390 463956533 100661269 487394433 270743956 342879907 841112339 573675259 153557845 395127316 421318957 842118208 828640895 100422934 821052314 382450653 327474012 955178523 988249558 646496653 460221710 160485813 407205222 20700693 914606920 266493538 305248794 957891601 863043810 276628100 356887476 870614455 122019634 660554745 237395332 492092612 324724239 584804811 30657025 766532246 939787326 842622159 724380170 814685271 142697131 973101609 608329654 736286816 802299388 101949109 344530044 438076592 332156325 186267055 635641675 184518036 782936092 660858370 211173754 833255146 959263447 717224399 387179930 629743206 148888927 151359342 536698468 633158462 797315405 438127007 56872880 587609957 327383396 193799996 101917108 221630502 114339744 470884811 962783595 130366729 860446884 386958601 402319205 117143907 416035399 659803624 85640312 850570362 292231313 307492957 438847153 654550353 776141432 609755297 24554215 368304398 991866961 237560988 69527145 4645635 584228182 284696557 936004235 868000189 322029834 294102547 700195035 65430237 59878611 195029830 257818767 826601981 723746988 524666794 942050000 891144148 253666918 176404390 261955825 886305978 814621230 452987792 986433252 608624529 198132579 666333950 80976230 815605123 57893054 14055194 925256711 192493683 146291146 985052662 990523648 584273882 970643195 480902321 566155103 59679950 444037798 390002079 321711012 545152254 399753164 421227126 955076309 778872861 186172874 336083058 595257174 121334426 70412056 169874424 317097882 231778955 115833905 745268141 956315726 133022204 905191909 97694495 787793928 443979918 266215502 750459793 828470776 168825669 366087922 834771812 428182078 489708266 657417494 257397600 230658039 285425987 218663256 273079795 352361543 505278319 819643876 569473180 456258827 381464693 913206441 17612337 937461525 808452987 122373493 181062093 705271066 345257607 903044112 62281670 968545501 575111857 772623076 770454033 575202172 247225932 169426879 858999285 68495217 954739404 359561071 973478256 751426077 279178759 712539174 377187864 139706454 513826905 594156722 489119409 871346737 101234192 912541763 177360015 942743415 501584793 603219112 7945751 564170167 911696400 280111774 535299785 202872594 464991157 810400060 714554469 931935750 475138956 830775519 65671785 498513503 154203187 558061477 772245965 360208148 242289977 960551600 651627727 606992616 276127705 600818372 853710134 167494576 178550734 508351916 306092060 508469293 317725386 884891019 976089654 601667756 675886731 728447922 868862459 758168627 166951662 637406512 104730080 860518831 346614482 818241245 428325917 125733330 969302518 457571884 71457486 367642062 627469974 497079929 744767991 145132434 998357536 291128493 751358308 170184207 771931747 925768123 385252946 888859436 255068030 451991980 9525728 523207644 759452012 75085026 65885913 729036437 358748805 913356821 571373191 760520387 668141842 908589856 155251919 791145586 158011220 464903550 600324104 992981416 214417845 224875127 921811492 502554837 788173173 899914513 646764224 31735636 744040276 412100142 747307857 630678948 574593574 555008173 847951451 398336023 535384753 419643194 184884353 729176755 74957767 615587238 967276977 239709565 785721003 43813720 54548282 866783819 271094938 661307734 153673077 839112165 725659626 811035157 81838046 816006184 973399484 607112336 356795295 150921225 857110093 574964505 694099421 57528714 21686724 119853440 954435709 880445829 542766428 217017354 826072480 148989247 725504202 293745756 10746537 643715266 727136262 3290310 254343963 433207213 707560759 302270642 463797079 931437045 759264309 347625554 491850297 203956041 288439965 978624427 501612735 789891364 970068649 755011475 864635808 203031470 518592057 864228092 107339166 127885215 932508527 264321678 16651773 93288294 227493527 760105439 777970842 460563366 318585839 798192550 542030246 80186921 475426604 890730639 741572659 854942563 486315770 519619635 415992423 919308064 572470964 124263122 641947692 63350261 262379667 526426940 382862050 284842768 950377516 204985960 756077567 805722463 533967997 922402160 957316137 498670098 114978631 527251888 22747697 605446476 977143156 911232089 658933726 128167076 27716898 395201921 381228352 54283948 66810001 743175737 827194665 49889621 248397119 24474308 809532290 549066600 563349213 593113905 949207152 23750461 871002734 742505289 321357214 845800018 812756277 800230226 676046505 80380060 860074375 72276780 797555660 431387236 980785727 235677433 123502041 279681722 751298154 574325283 511483102 697961485 226349963 833904438 31184619 920616124 88913190 110899764 39033976 518792645 990779103 634377318 103197174 583784009 449618194 521610547 905911779 372687979 261580576 1273315 398933072 721798098 617691071 15040222 813612891 471319841 443527648 635839055 895705210 972446286 899689940 751505268 331080758 649837284 572234238 647861 473522821 295440275 176416820 497908803 784588482 973876595 369020773 499044426 311664728 481484436 408921152 925798124 922499631 908166703 400752300 205559938 68156337 998228953 717609310 580133135 938882223 781839933 325847946 379218771 422994848 354387519 687550267 844242752 365772070 589838159 157125961 382023154 636441549 771620132 953354595 196561823 694132492 698144717 699145392 278910219 437149978 233861061 292155568 731781898 186147679 736609087 488902640 834525930 639059326 416790044 642827093 233325266 664546820 265368950 500338167 616261767 269846581 97140851 67671731 802445062 521209400 676713317 947185036 174510972 616390480 806839528 14992042 600169872 653279297 183191699 107437679 688581910 194431843 946085127 236791952 872490910 329789501 774047996 948387417 686389081 817344053 927576420 589240313 72854423 215374958 751857308 104147966 99709749 304871955 271750303 207955883 489105736 379265001 689149262 67943165 588913148 68957779 948301363 529933403 331698665 759253368 455001522 998984431 658579856 129446267 689803236 152411501 518191976 302235558 804310021 560361570 372301653 920828261 682614841 417977569 522061507 185915339 669115423 390015763 278048610 584395400 985612776 106863611 807337210 761217401 923550156 305140847 20989759 177099893 915599422 977052540 128020297 990813399 566869579 139469603 585650793 828041550 168348542 883622334 664516911 774910721 97169652 449248811 852230203 840084904 624224937 239858571 910091230 190717462 537822510 288573714 414218466 427897834 358912320 198598689 827787004 665748078 928444096 729534118 348746068 254319932 274825327 949700486 923238517 365037095 884450155 751115460 216234291 313925722 323749307 493928143 992958079 524484473 576086993 983330076 337914039 739670128 684876109 128999780 490279435 527562627 211155879 660776200 52523143 604116562 913062513 80006123 71373665 955799531 80071022 589982898 22668625 597074768 123729991 166502700 864883459 7445348 841138874 829440423 423944705 955475816 690108194 264657101 847569381 55153124 555978439 82197294 285726749 829138734 689066674 608193976 32589017 403536622 388493342 358182102 937129669 818700936 494793643 641849645 605652380 943651642 75169631 462660083 369917712 230712634 40357000 567718433 272646065 128375169 652833450 361983136 760502395 323198061 163349014 532423991 527954770 840165653 145770610 283501238 75088587 722778414 763121454 555725407 478236138 431351896 521149720 23599549 971528207 953635597 137460523 417243270 394319303 390236410 711894865 497213350 912704485 201939125 98354054 588509559 292642069 451817307 869296802 883863075 438156153 367506955 630480427 900028509 557070422 5774227 825781549 926869545 543568430 430043947 827994276 958343782 253696050 282058989 989638593 231982028 853373502 961859291 888175179 487345571 487192861 899828406 811614235 555943338 562237911 617802888 447724716 91924050 439219091 972467651 479407404 505058018 413135352 835911931 833929766 108359381 964175326 514438890 213040219 400610304 839909163 510050893 59953455 949811326 412887325 486458987 795490173 54206741 287814456 112297204 965955138 364270611 102046337 890074241 868943945 958838068 488090797 364837912 282330583 665865108 710579567 831716964 968327834 339685376 620107781 202261536 430931589 275350418 110280856 964473929 468145386 580452127 854746717 218037334 654018066 240036922 437257741 641475744 816548113 180255729 594863939 365409987 163482589 944479243 97679110 438028549 434751955 228393688 676533692 237430448 356901275 367943403 416504090 790497451 414536757 695812945 847973896 246920097 935433358 807592536 443556446 312486578 284048035 505309465 291553184 857509201 722897023 661755723 740035481 673650561 719987748 383108470 265249379 808020569 223812749 438262117 547274929 228207697 877293244 345912927 77914832 31508709 857103167 677007718 542956941 521147504 59788721 429597059 719400913 643640190 144634550 947915103 635798158 77227927 271168625 106658684 703772294 993533337 54781602 480896239 752232660 872821815 577653704 343277733 240888029 885907535 902815076 463380277 620791867 982924074 220549172 712185563 246275772 743846939 476066738 340999480 738466510 484924355 534813010 881547870 979531158 838932169 332921335 661878499 753845798 687622906 767113580 47301909 49141927 909579882 161495621 964088746 478858124 312081435 81515485 176577062 626177692 288569979 769726059 512906097 541701344 22853485 892499604 931756467 114220739 124323059 251132433 693765115 190964623 420732811 649504021 817412698 414583259 423341343 301808201 628620978 902319690 521415611 675627367 73306602 200517980 281652866 792959169 984531184 155720 373587008 847302902 760256626 711401621 552137478 951728195 770558455 581803688 108201799 35779155 245604820 784373420 140270415 530363835 196151364 784729051 543324825 909395638 227919411 62447141 868886158 529440659 722279619 471629032 320414997 213345557 478389499 939939275 135042524 657741020 570903879 781343654 307551010 88574506 760096885 996767949 471016655 519400259 324677195 447380860 968204913 38289761 482191543 461818191 879086750 237596607 825529467 719247924 85321998 459203493 630470425 615287972 124743755 498414739 988275056 977820603 903205241 860143273 192970417 22551000 245386371 915764662 540301522 253108956 255091794 924684157 407143908 898505391 480598264 345148138 984925426 122836620 665153079 173610559 472266137 77496217 353709663 458866246 230819897 317681089 422165209 642706808 743497752 161377402 127207617 197592050 578726418 673012978 593002810 91835453 67387237 802071261 850058953 52093298 36845938 234934934 178688995 181303649 139403149 928590595 357867949 311978897 272281061 504802504 692327522 58879514 32334886 118712907 821813806 336637889 741656351 280151570 943997235 162414513 377417636 172527907 536606651 825716461 619039081 693363719 650600672 276387827 421439894 994840642 124042549 909684958 224425568 768957714 936980575 46167906 140933529 541420477 127782062 286687633 425476686 78330398 542800674 747236199 460627425 414630678 82254800 631495104 964692926 27779972 309670600 796003504 841112240 23797139 73286706 950508864 907825105 325728896 372203495 985676362 208457367 598750124 600473336 360341523 188683158 529087338 594666484 832275054 392747972 428262345 326200193 963366820 341207144 405685136 674170928 315188656 352028612 173029344 237019989 927256664 630087805 96717983 426035742 418488477 525544735 545412404 186583515 754615338 281182307 521458486 688883355 633988714 971831829 976935718 26107223 297867462 576402474 660949024 945327661 217183963 262419706 453989140 491646900 285762621 73929467 733595824 544548878 55245531 827076758 134375810 554995193 724971131 403211849 796740993 205322349 755511726 575668699 385917014 416358878 743777352 42607165 521370803 289649924 954994774 694537166 528413484 469625323 443130617 610916989 195435692 797619710 101529483 68768370 608589961 94533972 92953451 792840677 853695504 426668927 88203438 644697647 729986496 122317618 252569069 493049835 230484194 748727905 897032047 413162983 378788833 463681621 386777741 429748608 520596098 13351289 493138534 954512753 411993339 102263916 243784569 300406926 425882349 138125365 235498081 878516238 85597575 824527257 498838964 45211097 98725828 507864307 25881385 339774435 46566686 682324039 391622373 816372089 847797616 371670183 579121726 801719447 942653117 164523130 143523610 28403464 19796422 2050049 186271613 214246184 630083911 220777268 92882196 820828033 129563736 902053867 526274752 975903445 159145937 828849101 537735909 293696279 433261161 583425612 870691310 787677750 927762686 596024537 123702561 416626638 706974334 386456013 317619236 112444355 55114561 373479682 894876479 705773708 900713491 646511426 483372475 103845391 794905192 434285007 185168808 349943339 2280733 508285921 921120353 962759956 301209560 435471030 673233200 815717734 689675472 285033317 563448190 771422954 635675414 305589141 552258978 991550652 127615049 496960381 162682827 644587842 303795574 762355541 736242069 497790771 992954207 776602091 757694233 982111310 133935656 107879357 148233846 542948397 770369291 29177626 937016555 763274207 622688369 929749143 565640557 23257350 139843173 846241052 477193810 315394663 677969238 797880659 155812633 305340009 697260040 829588480 732392193 350934533 929461327 990722134 692941074 37957201 358451977 238540052 7985904 511701274 823087200 138232435 57735744 99054285 132748572 102253902 86832991 189597365 169793675 50033315 360200688 455264652 64813292 470156260 655217834 115080786 64085957 85005136 607150143 874502513 469290994 525700161 844500660 927035347 792733620 764660465 738891050 372663547 373866228 362643214 786884241 64022065 405298414 447803586 650231875 405909542 822469151 313811980 130299260 190715034 804593086 41877863 965585858 482443396 81977395 86948702 4352623 834616002 77787364 778898249 47648537 102384768 915562002 570284470 23289565 43430272 714230904 659243395 544021181 56366754 559973020 390036637 256434789 899849857 169033815 513640022 710359764 998166818 792751350 828545912 51887817 436815608 317302618 490549525 193810622 49776695 435053659 134577927 159687233 589070088 774870121 629494235 298409511 205136613 233246999 591552973 33927127 878388454 415086832 199031474 723111227 449082686 14934744 683550178 605243143 953943553 780954281 657266382 512580540 206460062 527129419 46107373 535811388 780762159 906715102 787934586 165644582 826374761 96561771 790709008 54552337 440784051 260979973 40857269 461806240 602350251 313974544 307253155 378601300 728671866 260851317 297731196 314978946 330402396 809489397 362898302 624639002 959427625 634159139 550866227 823903780 857412715 805485384 205636789 451210674 198153943 809901134 809870898 791564994 878253345 207521523 688835654 520390964 632047647 13991275 132556537 295674772 701865346 359340846 546805010 412622520 593518222 499414017 875373643 695364882 724950048 907533465 444440659 919406406 632099158 566568688 490930149 953359004 816580208 675705914 667209900 601878259 776206290 142806170 949758457 364534156 390547130 532697930 621233876 327973822 988182142 840468862 983501812 261976199 957056207 248455491 826707965 346074770 222496615 850573037 978234024 214387325 332950351 128071000 314810933 859006720 246731089 257079422 512866074 44566382 546553006 595086987 382318886 505051613 992880346 455340263 761768012 155895425 362013075 933511408 265443672 918509172 282600440 977963772 670304220 613551603 162490652 611541751 209767613 506751765 137908592 899332245 545226051 811004399 23777949 253956423 991115226 5089513 755060127 379174342 588459038 976519871 203795352 982812319 476402270 437184605 222645802 281029782 836122305 402214776 304930366 848451770 319972764 260099363 838260361 469837959 712778261 534640369 648776038 795683269 987840540 898822594 138299485 65649664 949373119 475231367 535728357 179774796 287079447 400344434 123672426 828612965 356637521 227628481 102169813 665001864 402527734 459875628 129330718 385497077 587184494 55518835 43623103 739835624 747335658 790116562 825288199 183546988 698257742 554777120 677000550 31401695 451536286 682064919 133438597 589171411 175620124 911628640 61617601 463435671 505575424 770051152 806605056 342917621 470331226 730852733 589508717 687580654 579274853 944588697 351044976 856954766 757911086 597738304 489435463 487121981 517154393 276419583 218332320 315607784 519153032 200160019 17644728 905547693 611363988 758864407 671998029 249050095 635037822 82953497 714513258 251003035 689859375 578709319 150974813 849480020 339465421 945708317 840005113 638433892 39160510 464494303 719938250 860663761 916358953 336590152 969263339 114692353 51452048 442945239 808847039 161131582 852545443 83478091 241738111 583410395 930101629 565334232 277175344 159435181 320143370 147275673 487936320 258803147 908666021 950449818 501401230 703120806 444046410 394223422 306666675 262014474 200898185 805428611 269492895 509460773 627287502 228911499 727812186 861661467 448485125 733684796 107121820 376482575 329777358 2147807 358035993 833883708 681785407 270426038 40549270 736466626 607232095 113464785 549731420 190297921 646519862 719990961 510000620 120565717 850041 627839996 603385524 340111356 66352788 3664720 335074677 871588835 972789261 565972269 764644921 60822836 667516273 807384065 53541072 300199367 347200896 107440845 652112189 447685030 515223885 927105420 381092736 881462346 883245475 356528118 264345506 396745291 119800367 377374138 253672338 564509022 436313480 70160723 123481515 1252096 757926357 611376649 26867432 300770769 733970527 84146669 461859884 579226169 109887292 157399757 735654372 797194067 879856961 154610551 959268762 161941723 508949960 993928727 161414380 563445801 593260922 962760927 163398468 334980014 23372880 510572412 472305059 561945076 745727093 563361736 336405793 324295805 593568774 481823252 743749177 665874462 724446805 938098181 473454904 412182534 344732430 446361429 282856669 677521283 626482063 821201144 459572230 44434037 240964836 127920378 927289514 936197561 886098589 409674439 440390092 118704692 423818904 295800428 36238891 485385405 656975671 866895133 425996482 319370875 224321604 948798331 674249302 953730971 797637814 719581806 384148470 743555816 786731393 164447838 266799802 409017 557349837 304179722 930839910 483186547 472890362 144832359 646153657 688294419 928932224 822624618 803428798 517633198 470409697 466330422 657226384 215672651 928897996 117877550 974223839 262086661 663375388 389049912 102232328 155129263 696910508 311452493 976551148 989721522 668129860 132904407 93927905 595359057 832064856 582695156 331654045 270629237 695224462 922328062 387636346 242907475 463359813 959095755 449942038 976570542 190371521 616898512 76182783 127453767 88638033 501172886 930386008 836601043 683522905 640501316 5046949 131115906 834244660 474686719 544025289 163734677 602157156 742371005 653973522 428461631 50901228 633424962 302686008 759242244 780354840 3957402 68145384 104218936 582287825 669527658 145727117 641033456 194314647 856391726 6703049 804584924 602830795 89757553 646991764 443715847 46760885 575772975 704955059 792241306 596374975 794044499 143545129 27907947 480017687 781716707 53873322 327527491 753926521 643591999 118543566 383583041 545473175 478466554 2781475 790322064 145255740 685979216 447529535 121646515 915909848 259581678 82034697 725628048 572453031 594868523 266480455 593786123 190675248 735124226 894793985 289638633 280075659 311867330 116204967 756732752 243866677 440849096 220886707 206556338 41487561 376978528 205905515 773364066 378581612 330221435 320647834 851303475 699695732 410058981 757450140 241124783 754032789 764350793 370174873 764258177 14589429 955514030 147849726 130033488 251549946 763614987 444927573 730656813 871788647 326381558 752256279 294446928 969530458 532120789 589405412 791706187 64187010 316470677 114404762 909846414 651287055 492914812 58009429 423508996 799805041 325647775 259597062 533457578 520768955 763377140 339456729 448416421 309301767 704470163 749657247 27843774 714292761 923717127 177901195 59307836 391504664 377287570 285244782 682008825 533946252 975081178 958460472 605168909 605161914 269792723 334086757 590384674 571509550 460246402 749892621 977687490 280381148 366842075 996689434 845782640 171211085 581633664 271329754 534749062 453876015 454006304 360411282 709049387 185966930 1194609 133418824 123812145 988704242 701436516 443334433 897778478 114798182 546382695 143586716 741929271 670680325 282814361 519383426 811099328 378074130 374638154 443613235 624626894 459519575 198906771 282471814 306219083 54166670 617602995 105380396 54398869 953467421 886142809 989560532 658889281 558949412 165760180 307323205 505167869 735837117 266782149 63748471 9894551 579175761 947282941 750761293 533215588 512201110 104724771 166883206 817137095 111884823 424383090 83907963 796975363 207551970 781703960 857928602 923477802 907396455 318294826 318047361 599301656 725902772 838562723 18627794 179260249 85596924 965000489 251896257 10306420 858877453 866846540 868134807 395578076 209690852 769530327 969907482 639251093 57572613 852725475 153565156 225059248 285717475 740719440 669961509 129977985 776511846 235238309 819171613 470464669 251224653 751268950 684585226 721642139 807042991 451785041 374528086 10396929 330815584 366905219 865903785 642287528 56858886 822348893 802571122 352790392 168379030 186260782 661417904 813356375 219444805 348523781 805120658 794122109 1459129 719541404 358589741 413903735 683595714 776818918 58899879 447168595 110961196 129705738 594243749 387882414 443054610 281049088 562714051 814798575 280921764 90029171 164133830 9379376 779837657 169798727 912716315 171130239 652697934 298737612 326191132 56729683 368299198 162075520 106793104 485556305 749749434 605863812 479111176 738610080 32098427 688816315 969707685 998483702 450274303 871616284 45882456 855058234 203487647 210615364 543750395 137485177 385131352 566573681 998310093 784885347 458116305 275065161 15632290 943271814 29928866 261593192 93737534 381440080 104891323 39546306 639055210 957369144 826418780 617333345 290879688 716172193 199140171 731348506 205794875 466711438 367240964 298780885 268785719 342431751 308007728 561487630 55194234 155885283 565968369 312179748 649066984 696086144 532687532 685429288 395655935 686589542 478234492 960288105 110161741 219325062 233815188 838193125 413261449 402530123 912020685 484041941 460820457 328071877 118880484 485503796 717331252 417163666 416013018 66083338 991444970 916459208 174766230 567058249 829587209 518450357 51332418 19754485 591908805 411042355 993791539 61249131 341194231 743979655 38310510 995290320 265593198 645252603 117307419 516209517 540499645 784458172 848857685 134145875 620616647 746902425 850345709 861163749 172271350 313030707 660706427 265037153 343755440 115230042 682579998 749371902 596436556 816305492 405448959 323705982 865827357 457473827 933336058 350700410 175592311 789184249 384453120 929221976 481459371 592918625 400864734 442926198 687122272 357913974 821346798 872368672 704496303 408396920 798518270 237800774 979798434 328250732 206835035 128775828 866021748 782676040 469810056 996469993 144225914 415564794 265339484 15409776 773565036 879160390 41286364 902065828 348855368 335393282 906269224 305425093 451597005 251402863 362403818 763927213 656159904 375758695 360675296 713638416 241962062 310988474 362481801 186819638 117436731 678357823 915127006 207923860 669458670 531280781 607375844 22406194 981992618 213573764 416415511 673454581 654752404 4694931 688655494 842005100 517422608 492835132 493881363 572267344 181716894 759470113 981455227 900963319 699355092 388574576 363092534 480786091 664110170 436463570 145611146 837736197 628213689 834995424 289133631 47246489 322913495 461405548 601987381 54860832 649683531 411072078 799317432 151871271 547355725 715824392 534221711 335017832 102856304 333291268 538529458 813944587 870734703 58165310 447005217 491120023 852133178 83140801 809747670 851473514 56397500 165789695 199852117 827212690 849021792 116421121 117408911 627492434 250844244 899827688 988274972 938717667 220703958 909224910 427734767 29673566 16158679 856465070 141570874 213053813 10055679 82269829 318717742 235768091 119560935 133098502 964353090 37450205 76035168 268185099 147428583 165784849 939501499 515902884 358857121 586561288 822186950 690972970 449340197 777885209 285083918 209690540 855355329 450208569 348456188 910334758 203494242 585591678 618429527 696354874 331215823 182239790 331749675 780055557 777323872 974551601 333250456 149242558 969913320 516930113 139609676 808327252 819813958 294742519 122299952 170369753 68290750 536936215 659278298 90073199 735018824 707432958 725313854 483796743 319363931 752973374 607370245 672576596 450021117 12908758 768957702 951394205 331271209 941171869 157325338 23038304 154888007 632806477 574778858 383732658 860965643 921905854 561037337 48344914 321132525 50043470 106802363 317558263 396779887 1074014 865338685 378027218 412008575 697533911 291237672 762511728 768780712 102461416 664518275 394168739 222665230 911226952 34782437 228245928 232633802 395463780 109153225 647275239 957778719 600300011 543975975 377924745 331310125 639165464 913823337 149876604 534231598 289897037 943487499 718880202 489133411 628224814 739685762 324663086 31666983 133072639 271274626 745228690 558580190 259884109 597347613 500876909 254385185 540852173 653341429 579957418 162801853 738852740 686866922 358816832 743210017 551980954 177557156 196272783 431070556 932905596 801526489 633481907 785492313 56091494 109455616 788140734 651068823 819254106 291318286 206278721 924871451 827019922 351317514 717196896 163732667 200237656 283212000 709882977 39784816 854473453 119050019 829613279 107865596 250798342 913821419 507197321 397007479 697280795 568287274 600163863 210942793 808474771 988610263 338615101 721552688 131851046 912364499 168091742 200311247 474795635 600539547 605741434 456056441 201338527 348454166 607623124 426774366 105800155 514130909 790041980 207620687 743488445 828966854 490142891 546808038 466772333 981560393 670865317 833703461 182054225 348201575 889257274 375909309 394730603 528096167 879073266 613569238 859832953 668143904 125613264 644035689 522218618 703193150 969827393 31196054 843837125 344123791 215312418 672602684 335449634 11243958 527415573 611687894 633891939 750174668 605104340 89229215 831793667 807182074 486090385 417613382 840873760 51727881 552200321 638102121 524043781 710607718 742255142 45035288 806165184 983416782 174715533 591695764 219066177 239579787 805471951 783908554 769305209 304145887 646969208 303092714 815638768 368008727 837411354 595540645 600710451 455526103 25516812 525411695 422389850 746820273 704778756 599248717 302583868 690538961 740017874 916209508 217897609 207142173 597276577 540891458 173194436 259706261 200928850 836478309 491045314 689849886 300450322 880067399 129315052 744513638 917058323 512831887 180193585 467213132 241576186 738055581 683615782 806967792 329698873 796385406 415061525 9188428 174368512 301439152 707300036 764944970 375889808 464033453 162219057 123094285 353395664 606684282 61208382 426361963 930308993 625362109 964793627 104789996 692643718 904652755 678007689 288364947 810546021 309174350 47866883 298730045 344134576 94305854 222664132 111273334 534473369 684667397 913889675 165246277 420924528 637339063 292745543 371783091 791446431 518970369 993356012 462889411 57798370 881316634 304971395 243928853 466850110 353120347 259534142 948131868 56638064 697195040 1492782 941429436 726848746 163155461 154571152 923349757 41961942 753310869 548650531 509471007 97751801 117076222 791639669 864817899 973507818 907317986 108902600 819544775 985373202 543398012 722704852 768494633 910986912 259174607 448964805 876218794 506838847 767690794 455567328 637888676 846851583 169588348 837491966 754064001 663059970 408776111 484502450 259652815 904128783 691691828 658589525 277592439 83143769 393640855 28303461 362034929 142251409 484262557 300595933 474327744 612025659 961542353 74845907 714556859 357099873 376814982 865976271 209173977 34215718 547288932 595186404 768478507 374861480 871913909 898284186 91799504 344435447 76298972 834428496 463660906 397888067 305677458 656327746 562856727 731136967 893647829 401906413 187144408 183485991 971874052 435988418 128475278 578397218 121668479 212432970 142425997 280576734 156661502 625213296 398104585 745471074 423293950 316382074 776094434 668942108 586542229 115521899 149251045 442882560 454950526 509007021 576746604 336066561 890140128 855039032 39811495 732833090 192772592 267575696 340766525 166250193 528894145 618600260 544681338 531471830 169021800 211614749 334931155 188976131 521268473 392655916 922661659 194150078 818172290 321809347 369126042 112992192 999976318 138367585 8709241 567270733 78063742 715311735 295576130 200016277 903676967 345228177 905317761 855619531 74970060 873372147 995562434 616185040 518041181 576761994 185386995 588881614 211950448 492938652 862818032 626745536 525741782 988420813 912563964 876220708 532622038 519890941 579652767 818735633 335754095 522766553 881152496 799505823 472612627 711106333 29595774 748641939 337353321 465906673 214336776 376147094 284881474 777558413 552986902 129070149 484119570 709603220 972422708 278799990 537443692 639069031 277901880 705756045 238199973 648979579 860903280 775453275 728245139 194403435 419898451 499556770 349702968 944547156 149546101 681003064 286205040 437521570 919546310 997435310 409653558 765696891 152006429 138433478 127090937 691861642 637309116 433683559 122515321 577693424 447645875 536647535 329167182 991809036 329459111 316377275 315039456 283233750 250881608 776303880 616944308 586505616 970429191 255544225 808120404 38775946 431308048 46649149 26021479 209325506 263414882 284395566 63650618 363489224 738576225 651270840 806259469 78961683 260870114 704696694 981299965 882071666 813969045 368901558 800355079 903603979 354544225 568099934 854111050 201379962 563883569 481844576 644748002 168578406 797316760 226176644 886985541 868015015 792375337 921221465 168888039 641670748 418450322 989257661 989409218 766106220 725539866 108722131 674290602 203039772 734583424 77532940 615413682 805687638 693169213 882606861 123147959 911236594 620044199 222671972 183667773 226149231 12009090 581832315 702667270 157206961 782171239 261408187 480826201 674052565 863192499 90767054 972123099 735602481 123773671 72986854 829200302 370146586 124655579 823725822 715884738 274575599 322182366 601619715 983906120 695813978 359282758 257086252 443750004 345822690 389026717 670569746 729949521 323239098 63860604 3978147 801720338 100821832 28702385 914749943 210607583 831803582 193939757 947862983 392275640 553443834 390340050 122090204 591359697 141180991 259272228 909179508 828597932 914393924 890386510 244929513 156638718 638326890 327940901 241101152 634429 430893514 503028380 73287613 734821582 969677975 149179247 855968216 292600249 39599719 667192733 948222920 820952396 739685126 469491041 16403118 581879665 69455637 844354273 805578856 745383200 984501323 829896807 509035250 53577074 551280737 620120344 326336024 338247424 479760523 390670157 229219664 990776311 479700581 496664995 528880945 529682834 620689216 149285007 779410615 434898605 911564818 797794436 157301002 526651751 76443205 543950504 592609047 877117376 445027290 393222227 56063057 985511284 977601738 521306300 901005976 852829794 817285465 63598030 927326145 542456258 535007537 196448053 292358623 991901934 799007301 133491272 337417915 598715480 630801464 102268328 642159562 779934087 312216504 835651418 428754059 827427042 647049921 174149081 747677450 629519010 634384037 353004407 510864553 630017452 616692710 42295906 317236069 293023101 43737188 536654504 649295773 283726246 810165062 122247880 871769155 805267686 876713287 145121398 649745456 29040680 778028665 594977238 746023507 860971116 345793345 603539948 76659025 247017340 292597482 67892901 212826996 63191336 266978589 320187990 370134500 311756308 505856729 46227512 121810357 227886564 418117718 257158730 299543109 75651497 378112000 804240043 480438455 317686920 309769570 602962263 903107150 417449725 232124795 949998087 951887292 434701023 77649887 13579130 592840582 930079658 18884381 225441062 785510044 973214614 35456317 126604416 95187876 370002687 782457016 533065262 669646045 900987938 578342324 78391468 34842417 716274964 372173092 439827388 318690734 793852414 193526262 854976781 421348749 992620480 56197040 58320186 919090180 492454010 708504983 499986742 742008688 799750753 385089425 538011454 880144559 593457517 714826363 943643753 699015115 18379967 328492399 924729193 901349427 256130046 112448987 375623256 401508231 889469248 88369460 147549308 11658733 539347813 219818913 907958785 690896209 609424697 355941248 306242594 540304841 907256697 566469341 604769951 192988877 694432143 476432449 649949406 858099034 355064451 66494356 874639500 434503324 20636384 720337308 694544161 624333775 648660215 73036393 283983480 790868794 602901376 587503684 645203521 423957040 122546439 512296280 686106545 814152820 69457236 481886602 320799192 910087959 320616491 373501305 600822674 738382166 929030781 310005308 828615668 212278932 174382607 418808221 136816307 504929413 303294238 782616900 835347722 180150378 102686054 729333404 996771944 437825888 427593847 347615823 963261923 800050062 542320394 581278013 435478184 589866844 813810917 803520463 532729110 135728152 339419922 483868606 144418224 484701635 510787889 874631412 277682660 326708166 344295041 161438534 689828912 146714835 912239180 592292754 786130200 179703041 437168384 993888054 881713411 961080668 486166764 38398921 59208929 688685317 111466409 512775551 593357536 479223887 510973392 997886048 355989515 987786782 441079620 517108942 249476892 751639008 607022672 735801091 853453385 836166034 55199784 953400601 785776247 461891857 190601079 416408054 620285848 5688249 439330079 29254790 367329458 599520877 32770506 785568348 481570507 547444368 903729513 876231340 498903174 67394200 509566417 757974407 546441780 3185194 461377801 4528032 108633487 205877737 752853676 762707488 344350921 959035176 847446872 52275792 225495818 65973228 168491226 502835740 860534551 455190122 801534187 933534996 300049066 21833342 329034361 949758157 677650562 28174403 778014430 759370330 719553714 931489538 584769214 689749838 801992164 400317497 932880332 278420534 603059927 408575063 256798931 86297375 683523122 396025404 695613026 836817668 830017787 449308822 540059860 599403338 346428722 731002325 785586080 363471920 100615228 411383982 343688502 271701709 822074581 95861021 928214024 655800980 392635290 236828167 694651603 21242153 211587820 105896951 991622756 711443489 821811396 620536628 917058290 147098911 682073919 676885125 880170427 310795478 75668856 181005976 422176590 814434622 367987796 883152033 371243423 505330819 158113759 139931519 38185796 773456008 166249242 183336215 211628695 376968943 445702562 598868202 859608365 644900260 933906421 4047281 15230292 999106611 702504148 275826103 956127978 498129298 932926013 73938150 565062888 895840474 45210163 631486440 510962064 106394281 771993160 166390185 825306125 635785603 251539647 72322709 873211587 423349437 147145542 543555514 427077333 321782119 888909214 227948017 492430076 788351731 380046395 965357392 580680480 359132097 568009889 879416665 74196998 268507917 434630093 311571490 213188069 264577397 583663688 64483316 832536181 551831097 697011110 186320150 61494081 617082149 572396622 822627843 95103852 425059578 485291035 344187093 774293981 978555603 353946128 885909211 849030238 717372949 136074516 380704731 2373409 981727531 488362164 606623957 317937155 881739940 35367418 731343816 320130095 181927544 842376786 739116228 849524885 691315369 988511962 808933113 279733988 227087753 759177260 801019314 503595131 131093592 856482454 258130343 273301919 544492824 155553969 329571847 833704896 797936173 448181565 8398567 80760126 322546863 698333117 729328953 693672045 42459538 412531342 312836504 804446888 538345731 125518891 844354155 311551953 531234705 919950561 836132017 131985487 271916066 980189465 314657527 976385034 966555936 157425561 735130141 253138056 28498840 580887225 813174652 876384751 560944761 829622893 777662898 341981156 964256789 577784075 613269658 269733751 844403319 378297824 606043312 792497686 872121781 985002656 874814766 338222708 642357232 683970008 530703620 542366574 137178878 277008648 204067791 99425971 977423431 365796747 824029540 732897782 275041534 35118853 111037929 449960846 480384327 101493017 267009517 496227953 405381639 36525890 701170441 775682946 814704262 925631528 310875008 398971479 998228085 578341046 762990282 261176574 229874911 320858532 402578064 539257302 808634968 518694806 867514830 436948641 104613107 29754895 129185293 1289339 903018442 356171610 692824025 449010976 42444790 179592100 393133402 817841474 593301369 866047262 991524560 870078722 226956955 552636087 371523919 167204305 253770271 71200979 703492389 63834272 608870691 139613405 682980289 114137115 438675471 34487123 226417362 92256345 313077912 590460578 211513187 932849676 37033353 21745697 271879078 672772440 145297035 461341064 429676524 893492642 71051090 49949989 912231550 517719853 725031748 555460132 182279195 428346895 320944972 357189640 283194032 633570899 31289241 9744638 642691473 951630792 646017116 885527288 19125337 170091096 599934384 593708504 828697375 583822279 349118802 654067124 685078193 317028999 366549990 647417763 165198528 225355789 181892951 54978561 265860757 970879639 158533262 144869637 470308387 515009458 990065996 430677723 748453689 489962650 492817063 398806817 640014114 828157471 517991170 990262686 526429559 710068637 433040057 874901540 649558518 779121348 603337936 535090157 865630085 595011544 359338011 832863005 482150365 773102566 456263971 820139659 406648544 722086059 185415070 268345348 504982360 49866456 220862513 625680480 745016782 190098889 174432107 75285876 470191208 751898204 867417229 953808023 818556738 728299392 293570611 816873781 8681753 7497810 135063417 229418049 113689791 732115220 748891945 652544122 394713699 933932833 147508512 2343165 38808810 319625547 289609558 137593979 864481841 492571298 863956745 84175422 843618299 996602007 798852096 287234114 937645370 280611685 278574873 50814158 478508826 970992098 832278402 304894194 773123681 548469066 830120156 210154235 695199681 251307449 558989606 83926697 864904325 274759238 437621919 256221701 989431188 898309970 384764183 200066420 166051525 522446158 156651398 656072985 993912824 446806521 251885757 801774494 830116032 370380828 396501326 491911453 794431476 237301537 180571473 679662297 200159266 824800210 31940386 603531871 934850821 897468500 278250352 246442510 432681095 119310971 603385777 174347258 528352072 791120786 577247633 936752896 552702587 465294505 625166672 441855594 375815586 116690882 517756630 712726103 699038139 961015801 486680767 10949080 687357187 95973816 871750147 796144320 633582374 171683784 408071479 578538180 949345250 898131421 494537586 468133358 561155708 347049921 51860717 552808314 630833040 626320177 8387890 31307533 134092360 972977308 714852161 638988663 48835312 158186665 185547651 523531808 167829360 785304441 955654721 356664645 730729318 45875795 7423278 503379961 782147214 731033418 311963742 130610838 609797119 488669541 824974894 953404397 239118174 917215542 882086392 254086324 620186767 204001488 617847763 424228235 970976454 63684349 281145772 164273246 264095090 410859447 482170919 145483192 776749871 915621397 905039129 1779206 472243080 71054373 134306806 665546722 795345322 939908421 63769051 844150353 778478160 895509552 454161066 477978598 964798633 530477536 195099756 381931729 369160407 519377110 572742183 152509340 908384279 37767917 626773871 553793278 95458046 33790055 396698398 118779471 413212660 336967410 366704315 224918020 340884827 564897729 878887393 681172495 935854003 125413391 332438331 195302077 361202695 922953925 876497831 577565798 397812386 661091486 961030434 637486255 298808316 383868649 362483663 343047789 666295473 325721568 143796590 177048584 921165311 447105215 784206915 799471767 155063348 384569588 518479843 543204258 859999431 45324827 20472707 660412682 123629482 693972944 507824251 579794014 793254008 780107377 660715162 768950356 285259283 966707078 875175735 998646867 545438009 746785478 162140904 184527885 660558862 985187064 46037850 44381822 690914151 389435163 925995463 271201714 397689239 897415165 885716253 239681183 999910583 876570131 473164623 609005522 864584365 594003399 657074707 464568213 577435451 383541375 469127110 713923277 383529216 106459647 397160088 428576339 231251677 984573284 349183651 43824999 384358140 810957826 799968509 716790263 642607329 390273230 727011212 480541388 804823878 662880528 362188959 77530564 645363069 158632089 31294963 632717658 372368479 392099502 624429925 442313829 87687867 593717044 876585631 624368412 795270897 876808296 324405388 917928743 128860680 985345670 509809561 126614657 484443624 295463456 728531733 39654628 661510545 847299031 832801751 594540149 265951001 382141363 958969839 804839972 450354262 950317205 216914115 25297968 423593051 105126705 99856244 611636253 175932153 185238778 841163238 978739335 396266079 421935210 639431463 32629618 568121752 422073506 818445578 223660227 202641100 208365952 241219579 108932311 967269901 175672567 846789372 430887930 943314432 844253932 755020743 852417625 376958507 68650793 251862177 568077366 585155766 380266852 428870515 321743422 938664541 911740650 943058005 596280271 373711375 841171669 742185486 834051328 277618373 788586372 88746798 672649754 890368045 518252357 708362026 557839833 857886191 934959169 229349861 54844128 698012834 807274757 391823594 195926947 36521181 756089200 490374747 738537465 590752293 388555284 888282411 317757520 556208095 535282986 837400573 185747597 447574985 468914780 321974010 169993998 133394200 881476632 16994327 762959048 654653281 456583062 43925470 983262967 231255467 871911284 86256452 118544527 863543395 617430548 458987628 172942228 168345693 512200711 44362952 654614749 547904514 295156398 646889776 60438664 75775894 985009906 882555983 786585781 767267801 72351645 770920694 252226022 172323000 269126604 450579155 728236749 237980640 579988318 545715305 353554324 264363447 206558241 242298469 34349812 405871629 242545354 670804061 142809552 472322331 81578829 367393022 552261274 441802397 934207426 628296450 64858255 871730092 62031035 690512636 538857730 91453072 229371293 16850167 543496352 427510246 871514659 6354253 251034078 824964690 209797531 580485748 822155643 169891380 563045472 441018272 466091823 696154721 347795680 453199055 741911739 70391212 51425738 884995441 399251496 712648201 762347306 874244816 454388929 717501931 819901096 566333781 165113304 211876079 157579254 834966626 42692871 953939198 358253616 996976049 287769063 62145707 609520185 861081394 152707773 201244924 690067577 967673967 519976370 948447810 76250583 270870608 772480919 322191489 395057075 599633475 438566540 429331347 237267988 877428149 209303585 423172337 283142901 772511139 433797619 849860269 658949080 612452604 587295386 316821701 560722031 236157637 659663717 12104699 418931423 623861219 59671843 400735602 482781522 373956143 65775017 700268307 556332594 108245520 332564798 106661389 661630849 282218429 13451275 777339460 989090971 456985075 759023298 760120324 887929130 815441571 557031713 237048892 562144417 595140779 329935923 33486053 438898743 191999968 887491211 523733945 422943737 441697742 895452264 985770809 308217389 564003031 399610592 627039612 707468976 289097556 866445595 729133946 750856417 788774186 882252260 283445646 291630648 861907340 946000199 391893094 586301654 212842261 572390784 394462786 996821449 571223144 91912895 906184648 278859151 829362912 787139301 546560165 326096233 624598940 434646312 132361311 45299479 994006787 672453391 764863911 466297966 915157971 773437607 212946855 98280834 826793782 713513910 416253487 58917335 567385076 698026416 629683623 36319092 700669454 492207966 27434838 171194262 283037192 368466479 458329299 414719568 864881287 61092894 474947759 72190377 586749696 172961317 941025165 829638961 288519420 246742763 555015974 538078261 723944372 687644330 47969152 421855867 470359860 515600982 734846705 110991455 490877898 891967103 85645653 362917348 30177592 989580584 426751681 623792209 294757067 748808751 492030247 858697725 567201970 443610202 330816000 6384072 140404907 969526135 684841164 151482663 753872631 869575792 423817739 149815309 847409050 304454149 976973221 267559970 512612837 542072244 997899169 236651516 784806131 606052095 603722612 695047773 730100821 886079027 543875097 550752380 279265495 96949811 237348713 586446387 361643712 670238374 584364988 713122055 412767613 776990459 977162682 724685373 581217210 177751460 765522512 729932005 237298753 410817831 814592035 253418236 782225694 15005927 54507940 715475747 963460056 287624271 427890289 909561931 103957513 776167060 548791601 320714580 692685028 769491186 982147902 2800736 227994542 857650415 72180528 821030310 685961559 633591417 99210493 794146584 104098427 125582117 810888857 295977689 220807267 148581930 879318014 568147750 73142126 96491993 469213214 636479951 250378079 846268641 255950780 367772807 417172589 140170299 413769650 540827936 652574000 928748103 682223022 801622280 362984282 301056937 984015490 245759630 872691954 705812597 6521738 781017123 944585386 843312785 796464830 528666573 978854635 803965955 237951534 874366968 988107106 407381634 483346469 950568300 329046683 773130967 888273483 762752122 119341245 403798950 355252674 925862375 917090106 434127936 689496262 261764847 335051189 956969148 812366634 374627965 981315810 504359110 694390058 475206807 659383824 136264270 561140404 654284358 775587856 237397397 463288624 233216951 807890047 953998181 449582766 368508082 822947248 432826269 788514167 880220415 647195185 91243158 202006145 472832936 862150879 738784409 556015301 483347203 17485131 292543917 42336332 185280112 889479698 320184389 276307477 410446770 666604743 152360083 263612110 808170358 492030679 871970229 53004005 947123918 689294342 632477375 275485779 698798511 287631146 141539137 408859425 195968349 965190000 103705381 314109179 378472293 563941008 903816196 455251830 724002019 82895368 369305721 846638037 601714392 214116743 270384962 303495684 567368939 770036704 42841110 440414582 88538178 484287991 330852833 23746196 443257246 593192986 874317649 501479199 548962261 153633724 936454778 163330571 857132918 680370626 341278772 215320102 718097555 498963642 834923486 580403423 859980417 792665853 289461186 429608919 114918949 837719637 300423506 762704398 707319051 328949562 903687768 256612798 628847715 54161723 724773181 630640054 301663444 533111565 588637374 973167369 249569195 430080764 57073367 508499922 895414413 822200847 119601745 971346910 936360446 506700179 189472531 679952405 362912256 811854957 969075841 203254196 564110299 163335432 828129758 725594739 132942418 392246436 427342185 745454873 573530120 542901713 504673809 123073299 585240944 672412286 110185331 699179165 966143906 716397344 622436404 483384602 512486948 512916663 142419775 513753739 375885144 770979289 640992849 447561958 600124335 981768217 18637075 390719975 853870937 137328495 932506089 416092691 588592820 394518410 554014667 885350799 286590927 184980113 870576107 294491898 461146619 873965310 678232227 143515088 398428905 143640727 363015500 802698445 79892517 528625430 719731207 536128689 951993300 855048196 762046413 507040994 112553784 577688443 246829685 725379829 831361213 506487191 882548094 106699555 46630730 512682970 7554475 473093300 909917126 990192737 925685847 725768149 629131081 363489966 728302517 862632873 604340662 606311106 648492048 26883253 355915506 225191396 459961279 304527283 509234939 911190412 903796239 33882444 678159631 831893442 933823857 105020811 326356074 730888003 669267375 495240139 919211620 145403635 712636464 391950742 255796195 146184984 398301970 482043851 816411594 19844967 427867606 730817903 447802150 78621621 697285887 778473517 761313036 495693809 965409656 818795561 612465467 475344669 969087421 323230812 362328762 669028327 66794781 221236552 137574192 718836160 752184677 487410696 170909674 240211744 19089572 44085071 490833310 53803196 955263428 588356180 467232744 933382171 15074598 946903452 788033159 971804995 348798453 423456586 791709331 134303657 78681548 253580822 569529766 427930743 312752695 270839591 586766370 680000842 365656950 713578218 985834084 431648363 500588893 482519031 873559131 781960534 20428804 520828057 538493180 80980333 999754342 780776290 500768310 691925296 864736817 711496445 81673310 120343961 592380163 542486010 404415765 251279248 804098531 201085275 581855490 933534334 725822623 582533663 617133310 778588252 753155329 290864762 222850117 736292889 732159818 673971243 617136820 7065933 180596243 841069611 690543506 700913845 336904822 683074193 105195582 989719332 106016355 579912471 766565774 237315459 60329774 866569314 296155573 44640862 894624549 794080419 180211949 281285406 747722198 478387988 40858970 42816471 516426782 571772383 271462167 425926910 121580269 309167673 229216253 241491255 155779579 803964591 102669520 305958558 475942655 253345214 930925385 182272248 420875579 223447941 895352420 586909250 463561943 667453842 848374739 306748128 505369676 443468295 705883712 426534436 480491651 382061477 681189615 490793376 313249260 269088084 236634411 470651094 692243459 954386576 160274990 161884457 312579699 630547491 630320934 633356222 231940853 671590286 150905385 195071287 70444544 586527173 887343925 911824540 593867606 847550679 667142380 716358889 349887740 802180060 395981354 856249006 624595599 360818832 508013254 710762289 480418492 399677492 404437911 325563272 102056520 630788722 11872536 404607966 474985030 281964271 831095753 262352127 955495022 953804423 549531174 8878459 867294734 802221189 425819130 192108854 548718203 681527706 790455614 462128435 271110462 219255960 338903030 136359862 295498570 369233447 781240663 148258602 385327576 692740360 241415932 781878593 310166734 833940120 170686765 145091254 314713113 742072992 406207632 277940455 92195546 864949348 801239289 781025908 76749484 752222034 980178870 101821365 332569978 61624218 415307190 114414002 822375130 562936225 562124244 983413537 520873682 939204303 496127471 615533010 533527961 690199136 687741846 254327053 467178456 718503497 788146799 98922261 120039902 138733647 188088305 823334106 351745689 213616860 334804641 50411274 98890919 268576576 413338895 5355682 535940184 934257369 256309207 620188631 475965279 373486243 365434255 886883175 135762197 827130548 53067575 119044797 702717703 902919390 508964043 240352235 455020604 176663507 37765068 924514700 719368748 646927896 436966800 208154398 295427102 655901831 750963730 655868418 762121006 315003386 307528860 150655819 364632199 384358280 363182332 459003914 753819808 206808284 885414946 709066516 519247343 652195117 63972161 200516595 344385233 921124154 126646242 960376900 906203072 79380932 184956145 289133806 810685937 397747829 27748513 143062834 212716564 910655279 361868205 425085551 103147308 825915160 754233536 250219828 577259667 514551887 408457736 107539549 573517198 442369051 639757618 616001317 386622821 456540892 888035842 241789827 182086174 529265128 535609704 77638403 814718165 539429835 907891415 451526638 728349128 786989459 688576443 137402072 132375541 858494623 490126211 385314568 886463264 689838295 360301020 672130134 958015906 624055554 325176710 655447496 334225937 939607783 366829516 599177020 241314930 336280842 35779244 731658096 910003951 543370494 393847726 918990650 130278231 551509181 55723398 708746575 651582946 259020085 810570489 878081229 153455502 634678667 341614089 598587032 595648100 567625896 935382330 788194650 207042575 160928350 501739529 534513715 708620153 494024736 671706608 13880093 888387155 72357941 287309204 500716988 800685372 301247466 60057257 934319923 748746574 990864907 328258281 350091113 79270296 972040404 986106792 527454021 273742944 246273183 493423671 611791439 238027148 25189276 91914525 101521866 117283609 579180637 76115507 630997620 651473296 640454964 435894118 828759501 212175161 557537498 266863568 748757107 25849209 890709309 424093033 337103710 746446101 357066696 961741821 516110022 657588568 580885878 316302613 275081052 846944910 813079788 98349095 141579439 471757225 831899789 417468641 24982702 322138694 773649635 994494014 457710962 237519400 475674177 678618818 856486093 170125713 22895520 937109612 994891660 919780421 772187877 501605623 313704601 609475576 789584332 292435435 966020518 376026039 531111415 140690264 363709404 175139833 729058686 341664117 967267506 540963821 410901973 226055190 872566147 697385334 26418466 889683259 763872424 446368353 370308206 103423098 479560152 490984592 350377086 951876543 195317703 264781967 204628712 889777423 571930233 334120648 957655164 329840535 645811832 243689550 142857231 342695112 635694152 651903854 850799000 823920285 438069399 497129919 270262349 788528872 886542210 260401716 905376267 862610547 890034332 145286969 111089950 181248209 359096251 211087859 701167320 982266965 891568381 735715018 931618841 834395293 597088972 798281657 146900443 883946571 870046788 757456510 522671175 486662 615811048 261402099 567224407 313270775 256885776 986289972 639274227 165466135 985020661 491437651 148926800 967464073 637564782 34051826 233406901 186578320 873266560 789174308 660975712 545195445 715579307 597638410 776703348 60146426 376053080 322133741 518536898 50765283 634694413 98702510 360470583 349889814 885527600 636528455 363061958 108273634 194571696 697428377 81313716 834146489 418039414 357307988 307346376 207665864 670448137 914872181 825757541 71971588 681202460 203796244 118001218 497801735 598477648 668498875 428195746 799518247 808705616 604224711 711720142 276040917 719765046 193252892 80956862 349600086 971714611 660863561 226439940 825772613 473154509 670622032 687092628 982250831 729047324 980498797 663861029 261470899 61968090 430991390 859306981 176119083 119940950 942008295 426663652 938753171 51525786 123779101 600406631 413986369 809884255 485444857 289896815 778390672 77265995 346838129 255451399 394796923 661334536 942155114 753623353 765506401 319719820 953252915 262344961 813805883 707457709 683544797 626960570 555832703 822879149 734795169 64161128 791223368 246560894 756058936 145596033 936449469 880276464 622869068 65830930 593337169 79454191 444296258 604862086 205553919 373062654 115601969 79732547 923142233 790386995 468045533 304409116 534723928 451511513 973836933 948966738 133351150 987539586 747662419 456932991 233048490 669581481 51082985 618811915 834664195 6195561 558594207 598071921 766000932 708937214 101948207 61258383 994197546 167263386 28963637 42293048 131680244 972468065 137217968 365369620 472122756 675955618 281506090 336116817 983337067 58924205 195585929 363144434 414645868 672673239 919340960 806842024 324223671 921482249 940675811 883105465 114196724 943408404 297005468 816439189 381659592 766427148 919259139 588173794 762002291 255065529 575796007 280414527 806536968 727631048 727137708 89367930 930102185 704499558 319953398 572471029 194586664 232109375 208454823 885023364 250799067 956902598 169084199 923916418 765512370 975471434 862976405 73007204 481148105 740563352 746888327 182679962 817445652 541523986 874277732 449528493 151045817 147567619 812442082 486784580 863570958 520492587 714334063 124629619 660181105 351259906 241812651 49044073 803389950 896769516 572525578 18932033 159165574 247940080 52113949 127710802 217219304 796446712 276550062 579610991 660266408 223551718 584160854 12722352 104487795 436652016 175411380 806537105 640501115 470767329 427095246 406908093 94203465 145377767 903479359 830321485 958408736 246109220 499566894 94443933 778850326 869329556 762065084 302142386 827765292 81352238 371014417 327837542 782703351 106212580 157633180 536728965 564459425 725486829 811604350 803762651 993945735 952013822 530271482 144491999 18513597 99111865 773093320 326186806 239042513 956690716 663857114 522497696 971516952 638727133 945417768 74506877 429353610 436659644 570490237 234055129 819057947 750697181 775725710 87073080 821749066 192876869 839557180 445888271 650295674 775146858 235499483 24447499 470721926 232363150 453911889 806464655 877888389 177749948 953824819 979639994 508287046 454079544 474245238 101845225 127687942 121418046 756083763 238724322 441846999 515704631 472309363 947835780 426352855 750321902 703613959 513522539 437894012 399312307 935055815 589808735 522705934 154151080 396895281 681863801 918893021 682033486 402934639 979581918 508989522 564680400 24152129 238941094 362926285 810448676 854491637 4824244 627392133 115293224 986106620 510901412 507900123 151498267 765516304 861841438 766960904 298753627 481460237 360346599 104396796 635049734 661005958 511866267 22483197 510153254 714427083 851547767 81059295 748221702 92391425 276449194 336917132 382937022 770412542 802333099 762277274 890408402 199129433 582665088 861318034 298160582 526749404 647929653 133935060 462318922 972605794 348123490 526794046 100860717 888284745 410430076 857842847 124003419 562047165 950668788 204859514 559038641 537758120 464742056 888193833 78683992 856188360 968463145 85306981 951004380 193284581 368664884 41725384 919494170 659149571 310763028 137876963 509548007 924832802 164633347 980868017 216655586 788140628 967363646 591546681 144193167 990961937 632254238 597648902 216289864 271579474 810846698 451465783 279888210 607115168 638204495 705579631 349522606 987667015 892177607 624348075 741041600 863629457 948735595 256712565 185245135 646431458 414289843 76297504 81175831 663188893 868138954 201744641 376620754 840649342 253751489 710622850 824117500 263500367 162412947 565594070 855333240 16890449 699315457 261140476 560890512 219797293 704380517 527966521 75659214 342715448 568056627 23647665 240251247 786933379 528608886 72598933 532227924 711168499 362283115 65991882 93289960 401304486 904816517 473690955 949492601 945336364 519234891 326840652 546918874 130639292 100773768 769944649 695920155 337411761 793871889 980788895 871406478 818521220 396993545 400347570 258999581 445971124 876502143 671051461 347187753 165058912 130267435 329954315 356311944 702952074 749484871 810546292 991178515 616206788 809867381 784215339 180409348 919454615 497757246 15403019 835798590 505218712 82772570 530592959 86152396 259251469 798919103 815471949 265608532 537900801 85592710 656176832 820444797 985312537 387555335 37003736 161080972 250060221 600608554 585668138 82544181 87922567 614981219 720983188 352424278 202957496 440003884 368735103 833189354 409971884 288271676 127820990 394216866 873811930 459879400 123481767 692004935 158011236 491914910 491151777 389815977 110555374 182129823 256899267 721623862 521993261 412651135 811455268 173640545 159152237 726324223 220560908 151740355 112368564 940745648 977478034 893426694 985591774 252973472 542450463 589840721 708933482 617636632 103837305 388161817 185384316 450872741 90665299 319578075 276570870 629789953 158187318 196867491 549053313 712405378 536991311 119734466 31389529 94988388 880143996 686010243 685712088 651986622 564400950 234779010 331453688 881811033 302503874 845073678 699349368 371557920 927197746 921728634 225394153 215336931 371477658 301243644 922332443 65048478 849996718 640116086 997358136 277503851 507633981 400085887 382696352 167306587 74633784 526370431 322318906 696007318 947337973 654434358 668163980 797512283 854795160 466562670 867505337 905800482 615790811 159163383 343577852 967488884 537519923 547677870 991301733 146413206 16474307 560236999 547992760 719841429 459466234 328434757 149394898 867449934 802772281 246919533 374505774 244074975 827188729 876776012 304405845 154241688 23309807 471979832 429113587 803420390 769472939 771058487 830836253 514825767 730309289 765416735 35494729 11830626 430181008 273015161 801933490 264341698 43481022 952260811 313624338 683320278 250409741 974063359 686692705 570367935 451786396 13609928 392935839 323262842 974436523 240846694 264600905 693421500 959263589 43391650 106060032 506128821 311314968 970083462 135773425 663107791 613872170 848041419 962372535 199733384 624762682 407010369 591599631 125477034 446705930 805228236 26386551 545303425 909687752 977223325 26814088 114131032 829800560 207299237 247660519 72003739 293911210 788084054 348596253 826780961 279374558 70074669 635189979 56949314 77398464 999712332 876049987 778017504 975688810 257569748 967135729 645654893 769688837 659509717 709972923 452606381 787121163 375489533 363644016 791231124 688954 728380577 745278827 530217506 321985816 47179800 67430023 193996962 476997052 866997914 682301472 218609110 353530394 488344049 494989558 89382416 434478665 952935723 494755721 965174957 111817072 322602590 235060742 832592777 434019332 593256273 735812983 906201676 430729055 272465873 188776659 721704195 542478243 999580700 473140435 697584192 432731451 846330872 977005749 89664867 207951601 349643634 344668362 341319678 713258901 284736357 549512444 701367007 638139084 118726698 293617013 203010932 765400136 115243320 897561970 441242937 783774122 416916279 613673739 903831349 436443491 878162871 956341469 703685011 571588021 851096942 336220238 180959687 477802630 5899270 869788914 531064568 244798975 63865706 372554072 16957402 620930253 186054032 70690836 457697875 786904470 779813129 599808877 492900119 60255683 553760841 373698146 494346709 872662561 688096869 509679678 337106437 605566714 496678936 157249802 45995441 255979981 21928024 475955004 897047113 510741291 757287049 982988763 407941684 821319160 656613983 637223208 668983939 65495002 525980524 28501000 509748949 441302641 909457438 681606277 943231286 80035089 294716170 887676301 248186333 37630584 986257534 458514674 47102164 82535630 369813952 841083812 256358132 268193598 406071315 886717770 670968614 344004594 701866427 980925474 623924141 913931214 145499927 112110448 846831601 666390571 309953761 929196321 486483119 365034721 549855446 205450174 670418720 223989443 441780384 448463335 673162098 511349303 930182155 795484691 600311329 931303903 773510270 2347296 732698618 59836498 302069682 635069349 10318063 932559073 356231422 640571284 177360493 381427012 517173405 996238451 893868580 30870014 971764037 453002676 776467651 785042523 423395363 532862484 190552229 353694055 832244631 293563093 980508976 223287608 567669476 478918302 720839415 502288041 768448198 916976723 424172102 675708399 284222218 662683079 113182672 264459802 510956841 746595139 299662445 861247026 744536967 242273095 362221131 185826754 515198308 109755324 616085993 607854504 150550638 967338817 61426343 892563734 282523333 974088846 909447636 572345862 591555701 779296437 328682805 162972324 873901721 407204392 798864241 508918133 825332097 62536721 984106149 411949703 381955286 194942144 579586288 394009869 121939917 513146818 98492655 845789669 967371052 52059298 996130030 532628496 359812521 160813719 501672073 205048789 295099869 770184884 659102675 229424880 441907723 163933322 250912164 360551311 470476334 949783035 24359392 64684235 792209693 789679072 595421221 905833117 468624801 980894970 354528531 643757064 502757471 683595663 533151838 641021684 636505119 65587957 805634470 948705882 446677170 325149110 659376805 808236250 131729007 477856886 30410088 81956609 899824995 599811936 708572293 301501978 550611588 102741627 135684738 938353203 855203057 305047437 472009738 411776088 342131167 129074397 573015648 105221006 41626562 886732002 557031731 121033619 700384064 152058074 800270553 216806812 439827392 324900800 293313446 137917907 411494113 456387792 134723740 21691727 461287280 162470217 387573365 494684345 577056603 37327995 165863197 521075660 444979648 986298736 125848884 355229651 198455589 226897105 435802368 412520274 37417128 458146426 921512007 5091735 913205632 791324955 866002828 165222242 654696356 645653009 320640546 285532732 937858757 36622737 462105681 895592846 614839205 126026630 644200718 190602213 282426228 340163782 995239972 750137220 731906193 505999339 753388636 92961898 119612302 581147507 240671257 666741645 623055972 40234339 890401172 548549673 40491327 800525229 901433709 130493969 36795970 525348308 801977951 658866814 537097095 796030987 831369246 28270264 382387272 392545916 490069628 561794006 30462431 193833265 401975376 309282416 682793089 281459008 723805979 834213449 306200886 32800665 170154040 671767032 802102874 360494872 783416298 749475916 771004939 880572340 284370787 558648351 370083090 569493136 291036425 128445941 705555769 467695510 529380318 803748862 428291050 660938108 776539772 713223676 295113489 500032235 700866747 534624377 39904522 733094177 836619011 150053911 572999787 178606019 947229081 301496267 595038931 673635313 519907772 803005655 607411146 309423219 225344371 84431900 177083927 207384430 774032848 706327011 567114015 408630678 22956201 464993087 596465845 160253403 768334366 325836378 353300159 668597672 14059515 113465232 305178477 927031046 314098536 649260539 509972916 780348401 492402002 554486961 375212084 626044020 666876260 185479711 362556569 761730746 336260642 438742497 557454751 740518434 438676783 500873874 892008153 953731132 677535714 771180451 772299492 686404525 919032492 803648023 599961189 496778466 123693598 627116699 719077188 259012803 766870737 329628073 757944442 730171544 732920086 958450621 340082880 642244568 793400025 163072058 700169857 499382967 483315648 236193554 627514013 25627622 340594148 483729982 719965799 895302597 132106960 348035499 698331261 944172984 735928233 3915262 359463611 860949963 82288491 544809533 192766691 640385554 631985263 854436926 978328582 257212409 205248486 130873147 736748679 109688950 679661180 87731891 903128431 796602080 643076525 435063953 837589767 151655736 58692320 23702428 524871156 584199632 490187902 840424402 577090927 927106821 925502613 80949538 653877162 117018913 358060587 734637174 255142860 397149793 128643959 465148606 427820156 294015406 755122760 973764222 900560841 127205625 196079440 526269261 345248107 739283410 670074254 49692409 763633181 455638323 200019588 977946642 981878450 222824491 850038465 965523282 355967924 473890165 877973414 357256446 344719608 133265949 594649032 370782890 129984506 128926896 407778813 310595424 200322081 343429578 100118924 809595647 304924063 627293901 81787228 511743272 300484844 346412229 929011728 217134821 816574602 751455551 748022543 750428018 4208591 193591025 425375522 477087640 810183766 898439504 104429364 277059700 444251420 239667528 103563854 16429956 410765893 201579448 975443434 82269029 452982386 567751328 602656035 74486187 156985346 14904451 648791758 693564249 360466015 198192131 714947064 553670558 659169518 184732572 524155893 593471074 263140989 688166940 523997243 481516459 977850337 900612830 199705159 982297950 499404853 387334232 307510322 540617450 697345237 64446012 49316702 154735179 615375317 494288067 690737634 940952660 97373123 471267414 868554518 710705876 555246615 922896096 990203321 322287035 234056983 2428298 497619628 35866220 796209470 514898023 627438903 863776319 127161509 961068572 64872758 367721642 189984334 380852418 653584193 520069520 96297610 847485625 323046231 913964709 560265571 786402759 583069493 422804486 179230688 561551424 32759364 417634192 227628789 590932259 887236540 524392266 352482856 489522876 284317457 527896424 550808317 374006338 512959332 670821424 538092006 949792705 905426876 387454944 514647655 235069984 880997091 853205157 312390928 990942542 179878395 787524116 781563900 23984453 295256334 699940798 28359368 553127838 156487643 460693181 339186133 471258725 387910415 850487244 260689269 350935034 836852708 604745918 484579041 935282216 73742556 199390102 926940330 313940728 953034175 660410334 239659803 225841791 680790416 584287180 89170934 753996315 227645604 76762150 61751691 218540668 813717833 841640451 46650785 219326144 284321427 963061503 663918004 58783435 265031623 809421784 375845951 231441767 702375233 897187771 617383654 386137175 552251785 157583802 163883924 134052839 774566264 636365456 312475646 209383120 807813850 973986941 297885537 862322438 80540210 791497627 470012804 184995826 243972976 48820881 757697823 139047640 88999221 571409310 808330010 446630539 31064861 693272478 387102215 222693325 927658306 49251287 171876931 700384603 941868139 818941153 957261153 912557854 401915901 694689962 339041421 728600033 869652668 590788638 784550426 617108248 416474372 953123173 77764807 38018354 436000127 392380910 375844699 150697013 886198612 964311756 377397611 957247837 880674142 70362118 779442599 684789396 246707325 758387516 901278033 698499070 497113806 820909923 65000537 797604613 650923658 178037063 35835980 898479912 178712046 542344484 936856286 774155730 329297012 680843626 677362078 373895566 233423207 955878225 681281752 701187920 409994282 586859631 383462597 635390869 140306430 474674929 392522912 940342774 568534154 223509087 606650885 585888826 426104821 213907023 753798731 975875293 949927059 305237162 309025287 828027618 439383773 559242789 674460823 233942966 88290184 498306470 904792687 814371406 652120576 752865652 808325708 708474545 98445917 840563729 462029380 687006589 747314424 165833099 77871154 553984016 167338263 486815497 277858042 912274457 817418940 679924210 288878699 403248501 378821290 176278222 524689378 4302329 806715265 352667341 285975401 613548076 346204491 457730830 397533892 223140941 978891732 267139083 291468206 840836033 258172357 261081653 332292142 360488706 724644625 288940302 818670240 412497268 188928378 301432403 23220313 529466205 440952711 523815949 25109998 356443006 154102889 381862937 588085667 542072482 995226294 294196809 689809380 209731515 736551865 794089592 569152262 648605147 736013136 111990156 680825203 283306161 804959512 550315801 712589233 910864134 545112613 242557994 70347395 781508512 644766357 624882013 174007912 640570388 943195378 975291512 20025888 966459823 899246470 21407930 124351739 90899175 746713386 243477211 40850244 741770434 783608928 121190447 461187196 404712994 24990906 346886832 946394408 681113205 231428577 631999260 628807559 526043100 502198726 668867576 177590034 280483741 401977277 909301050 254631210 802810625 473952933 701426773 818395094 584344053 721116063 140889493 958366656 602607875 825535496 320505291 940421956 57653421 604306422 57884768 861649466 748925950 223185970 11341597 992021181 332787766 618082971 286498016 888963522 191415025 131032190 624209722 589304033 722319936 959638867 614733473 877384282 850577760 281287487 170817776 289834840 730436784 837607865 444440660 690417578 708054233 438269575 172986772 951389831 616557338 842093930 698196094 372320782 774571213 85035297 291973995 668007704 752535793 942327351 19368543 122833526 839061256 841899399 874535010 87309964 998193233 5329405 735265372 59475363 559071599 74577334 314289910 847757831 83862767 288062697 268891475 520579910 754886772 358636481 618075988 423455957 302655144 562654254 256068660 586761305 855541678 998806911 512494257 833269998 936823623 936939572 186558654 32435688 568779761 354853286 82552033 308413740 237543461 85916997 302314171 988591092 219244439 314434519 226347512 620757576 524473497 4693569 298496455 258578629 842309742 763009668 431659976 37233431 159163815 652638231 971378900 568549339 567972865 23876166 327176933 959373618 35444456 183979979 867586887 923598342 154121357 435316902 220496794 787649269 998663541 11846366 900426287 517294683 135884209 211485529 586856433 573489573 681621638 363742279 411116156 79562761 29951737 387602655 249647468 464544003 184866111 743368479 423794810 416908489 575663884 84974706 895970906 852514246 800851092 97358864 767753583 605981718 94379403 919869963 892633291 401711381 811817598 700281715 792454681 616747235 668600081 772919245 329469717 359066821 787127517 544957136 839620195 357265113 203088623 926997589 244697688 756408598 437812485 450423144 460289974 415206040 717530107 413317344 167834285 723440548 580949764 668803570 706014545 187884241 765436133 454462333 690056365 913495816 757303194 399974986 146797006 49371819 234708405 193875336 152031038 341644385 849017202 321228260 928043927 268807227 338706285 401083544 549336481 239350172 139132195 750690583 500324330 893677230 619471052 3207024 808783132 526880124 406786275 53982966 632304611 968462562 46759747 920661866 436629975 802172300 351285688 595912496 661396481 538084985 301482084 694306157 280637041 114832468 56907669 720367217 177941848 340533143 529643710 131060621 977912545 746213483 56790167 546093019 961280802 369612752 36830094 654152524 146055215 847513928 411779824 8878369 401676318 280531558 244364898 449364424 559221413 190290834 90695972 202847481 228040671 210590928 319387184 593776824 143148582 635173861 690076568 372238527 903920362 916763667 814907005 289749308 241911296 70233777 286797082 861513824 361177294 982172902 253728504 349496417 341655832 141343685 932013469 602356637 432317411 669223910 841383357 329354767 274740203 433517164 365128714 168564319 468518938 8440791 496337814 13180719 708602156 920811385 504907511 659654526 252320662 53521031 593257009 846088135 676068395 716619160 756974929 158232727 699350723 447645599 121185202 484238842 756135319 186922365 970303387 214711725 42273441 3219845 309023287 121370635 541196397 565707487 620600247 426588542 340193074 948112967 193830856 591783173 338604701 642949762 994256088 30983688 241492386 853441685 28156996 613092250 845608121 478052279 25129710 436787137 928376628 10948790 512455370 778248249 893345468 244691031 198605214 318923599 650256829 954382648 696714342 761163757 367965405 100523014 319485453 809959702 854727003 392314459 319249360 416261451 952177932 998363135 779279928 826185181 10033324 915583281 863223794 937545153 558725395 751536711 975658506 994374326 940840337 644428743 596190037 655291441 330473151 618346123 990426173 254320180 409139025 329952799 212794117 449242007 362050780 601675951 851619235 45772859 272585847 389280978 300116185 284504200 959360605 807677855 866137566 234210284 253773706 224039081 234647330 931984849 270221083 989842064 766605140 545091586 244285875 499391435 732809758 914599474 660661730 656096172 792559023 571232205 979978488 856749578 874154386 487209076 930168116 618028089 741094456 597370788 336930357 542231100 953355104 19788319 432769581 779635921 461142318 656916861 531967897 453845501 984638628 265326030 657684602 325526279 700931642 432071080 415973692 341424795 49273923 815580101 868185899 366170784 773806771 834698163 739595648 176867981 54632984 218056700 254557300 60780976 601470633 444470985 263911722 445303184 1682786 353559824 540874363 671837482 755637477 361793306 289367745 530278164 800263590 53748802 395174623 595261729 724818590 443385320 578248484 103357832 737908342 14540975 197839375 292560084 211523350 694524316 511574103 526190955 753437344 596055177 464999023 122955543 943379627 994128593 139562508 855928795 266020161 682177383 755013232 420323306 912106228 595744892 300093730 497473649 992319229 299303817 387113734 829497934 458064821 464599175 284306277 258045611 580346797 982683047 299771794 853983123 534070965 730834163 726424696 35667859 803414605 439846603 120340958 506229953 297567135 527242070 477679523 104992059 321512706 862378265 621002240 674504946 282363201 364792981 105165848 555043147 805365893 796678861 943664275 707886737 799350545 38670499 786507241 662401687 520165180 430082625 318192168 253655377 140592816 644930435 322578174 387105252 868386401 813128668 107904953 213626147 171265326 298332207 485975652 467311785 320488974 718448877 13025820 167853394 518277326 898448267 164739367 484269814 626340954 828428663 447633924 680126521 851869721 769303892 211183205 380944989 7834466 786960605 770220976 610565259 228017894 674977512 361675943 144071777 838205902 853964049 362234862 874693554 725893659 273169952 783832936 135890451 179605110 146486394 468585848 862288755 762865626 738021021 326569790 198008990 479039852 636006718 13200311 668920119 30486237 581058305 916314947 581373247 898417699 133122265 952208354 346169658 551181273 887630690 54305664 111132323 361265267 78137153 550988991 31447922 262414833 195319264 187763130 787021801 243190851 654331178 96095366 229294051 159092761 684002739 21354938 208545057 766117218 262250341 610136671 84960268 525423882 528233949 155684429 672306493 329495230 452665644 713066495 768843516 336797437 962208018 785486730 528709012 244951070 837996849 175030309 853945862 54715696 608108671 737321921 354804726 537394564 517959549 344772627 346384869 170234857 237167193 286198909 264300635 434273157 37436781 959475699 600473260 855831098 251175964 148616130 24007716 855599019 723831559 2519254 594883508 995984521 622756996 750865491 590424279 148182225 841142164 104946353 315823722 572434310 780356537 495223852 917526143 663481291 683034185 558763743 403258699 224462992 919324268 983621590 575738296 933202135 719486080 627824758 887115901 955428016 89908166 88464982 168835779 860391511 697883288 186220515 458135836 889889952 215334444 114095130 349886493 674642707 367010628 665213791 431829965 463874405 77577213 755411580 165127676 584929553 888126668 230216580 428835696 462415106 250546008 804290727 854549903 408987640 243147552 112592999 170017926 827782067 141050108 559038583 239268259 672453215 386310393 363191323 797704660 774889718 358922398 342855158 485526205 486403113 324231378 639935525 515276880 439616718 395820535 219643962 636280349 599308105 32613037 507216271 385368087 596557425 947270340 650321739 562926440 399457108 597620738 279190893 476707643 769560975 873961097 921357643 809773102 442544385 8133633 590298953 793599340 201450395 4905869 449958780 602284042 304837233 596918771 217859953 753364461 444678442 893321680 162009299 501215503 887269613 451388034 527588055 522282452 907253705 171161867 982990832 900238843 369699822 931208960 423208577 788770964 415519251 263999284 620627531 377332036 823928671 198343074 898222843 494416864 213916256 598908268 619079537 74036395 903247883 900088424 200669574 322718102 24776444 767397312 912857529 964598708 782078603 421204876 277743254 725056335 140107500 390136838 642414871 383000249 842651376 740824127 669114192 202088202 984610776 707377937 968934428 862053720 293944439 842657677 367736456 995074390 445602505 923166306 72272665 409522440 170258499 729891069 730240400 192111650 492497778 176134391 110057485 378632338 873335483 949529007 435045010 603259399 559927787 66892218 715021612 342758026 516176747 757123626 367345659 113938788 803297444 686462360 746579602 603235535 179795448 969325251 563829624 290061466 905852609 594317878 643102281 391950425 282655030 968261072 663663754 790443563 24834559 305361417 693849888 216732290 501723411 252874795 27386526 68878322 441990091 946695496 194150303 962912 269635079 386079690 338441415 475596947 13938588 973489605 455048489 56403649 726518042 381865834 327792792 442285576 200948378 189023751 150973279 29779917 139840109 102081145 199551407 562344869 52384203 849149325 176640905 22607642 386466236 138051534 462340480 664032468 923517713 854729134 306152772 380291683 558229293 544847208 395875348 453064730 565046173 174163812 276695314 703766305 597886392 346104406 324328102 361913311 401421104 295322602 64240384 463166608 908422460 794320052 381882066 208865820 63934808 114585310 762742059 699990193 892995404 383682628 649484544 367213294 48591763 825337073 225405294 933915549 839994203 871939378 115686990 192182836 891829451 310498699 529852764 936812118 905130946 623196239 11780740 751352121 984150935 125406400 761567684 476601680 847692553 386889787 1562128 397418260 356008300 105744455 96303454 441250033 496969666 631585703 170456083 729346343 701932783 225162329 330697322 744822611 135364595 898542275 725476228 92176089 933352764 702073671 144649329 486539275 941442833 575219275 794641528 57928839 505947487 584430763 828063649 309614707 23648357 214224653 737779626 98986248 222097683 963842681 819901127 913614083 796918661 300113967 311457041 26437859 808112753 767696652 271877342 953797436 483374365 276521532 388744973 99836990 662202852 413915583 760386328 484559428 214572998 431319428 180294452 703839446 770159326 440293487 464322470 638129257 156234341 368354331 609073436 966334691 754561434 277800284 508804654 435026018 624516726 391119005 728089482 122508461 222179397 207329482 938055365 953409845 180514285 106665284 339553855 764532221 689310442 128664709 501235040 785339775 780425420 670411374 983495368 747679258 140822223 256412625 216092170 38896441 549186809 788775175 152850316 797550949 188670553 694389873 368750465 201932412 910102699 153934586 105492257 76660286 473299907 753037258 193913504 678120705 12515572 857229521 290896413 231254947 71911217 63349683 587101143 229996293 172238270 561845814 37580299 820342363 505315653 306920758 551401254 724796501 383917297 117170089 83132202 302754316 896560019 459570970 99477772 213414393 67152287 203172265 959632034 66990293 799460455 425694058 430931421 609866188 956451084 925936004 350169994 691587923 395953593 59394281 584028327 197861517 371916748 183417805 118197480 206587218 954663257 831217158 288481440 308076744 154082337 887407656 615346381 898704808 290981157 174484138 592269080 51705701 787623915 220640827 453498653 157144572 807954715 592947766 794430439 427480650 260282967 755182532 152176244 793277985 425663755 873519486 92741528 420570578 681415622 44515372 803202753 351557561 107089763 3578955 322444937 145037714 476277252 252372091 510438926 909173874 876069260 912737074 162743108 159106025 42168983 672944140 616621239 208435982 239429225 22820825 147585747 855105676 378074150 65705188 254906153 870985735 591955036 663419793 514167329 170256152 359344536 319156328 971062424 158576256 963504953 208518250 698235792 600367575 778772727 480798491 857842041 446033820 219248956 22731579 973840007 210557091 660196662 265855265 575010608 9620311 44423606 353595456 519263688 857608376 128677805 803798108 620851872 678698863 824215506 104470462 920103551 987049960 58089920 195625228 769812372 971700641 524610697 710196139 166621513 697753550 671567817 589499296 305225064 389668912 438735284 329624237 483287082 561144348 981735019 27671187 372024434 345159817 51004742 675165294 549763381 911611586 913666309 324483970 678058390 775608201 958712067 649081742 123593673 498851512 358277027 874610622 151456988