14127
299956151 541306477 117619918 684107992 419951014 62203708 443751689 178133841 133424759 950372768 475925748 844258018 669846425 80949314 914620810 225283829 777485712 193698336 966633738 309994652 601704990 692360492 72467265 382432628 929321971 481882021 363598407 87160379 54075943 75554956 877190857 354032093 616861432 994810774 38140085 889328797 909530834 334408125 67462638 42955592 284780893 543388385 739729962 807143669 476854050 506867123 32427497 254339762 700565458 999061235 416850765 302270448 543938078 489318030 537219427 325776400 971200050 900817834 265453131 25275992 976372789 142643987 231824437 445750573 989971113 122480873 187595721 752018298 456888997 255058358 794973889 741669889 650963094 387220202 401329910 127817144 894087325 433757406 234673257 594652782 285334992 651524021 749439581 681789422 140842050 286659008 7565821 964558451 39993193 125535303 842350795 16365981 120695642 74175231 314632905 963183106 196656103 502228626 715201403 653545099 609803335 362691643 247731340 260766429 749911845 649061249 241099924 496515521 935335006 475773180 91168302 73186350 127297200 693124235 754975771 120655602 979783242 615057943 85214052 19776434 740593246 927564846 888658766 713805239 854256428 55808023 676988344 50912530 410553000 244706098 556973981 20356334 459914092 657221672 133639114 62342288 158799272 374739037 558857808 94134277 850512216 502542462 167320626 977809416 195666696 922296396 98465017 27966289 389870691 36195420 900259074 130463936 816276618 641434191 696785526 670533045 697242213 226290221 573961927 107795212 470996318 983452259 980667898 930910409 640673930 114307011 993252697 799473201 489046048 404626856 746123829 192074615 907169317 913444455 22400382 102836012 688257202 120865398 983318652 78127892 9577170 883577725 61108179 825853787 377528268 610410056 348903183 74770480 836700276 775381461 35082044 160212945 758833719 868266293 91123354 252024000 982573303 936892402 904013552 324135702 194035609 650137381 516210317 101204926 416098187 538610698 56557289 956871740 511992448 39875941 887515984 374085969 775970017 801140514 52456107 6014636 411550570 401359289 80785116 100767197 29257102 968383511 260980142 788090820 689166155 204619847 892631172 524255809 141512248 796644723 848391511 188064208 299298455 217118179 289269133 567912993 608245228 198342774 524784733 120237675 90735066 264817068 346839995 866705082 65957581 399296101 872719718 330024502 800655390 806021185 430791699 829912491 626921047 691771840 470519662 168603553 896391686 215667185 692859361 890420285 12311908 393767223 78484492 164126714 610885401 220269977 732039707 71646981 418612750 109340791 44401007 509347815 374157858 391241002 228569248 292631790 790537102 101288965 622656292 443708843 759826501 53447990 126137685 239263899 745219829 596657347 407867451 494127866 812324531 100726812 384548150 677152790 347010386 315548993 693795856 957895787 535818969 278351914 29542767 954431718 387692704 73943773 463779532 614366913 317701126 692348780 906998702 108238228 646154096 529654993 551947070 258496949 435619334 678084755 350277199 33355514 127258453 758144650 527483379 792099335 711387813 912031528 321768477 58398198 80096873 15564332 868810336 615915841 293916245 750869454 570347559 534125300 677329579 886643442 148492212 995030704 431508573 55490913 955785283 77662669 437662258 360248705 188675969 873281591 38333459 538953167 906637105 18108263 149614168 286636835 810207597 713518332 51184715 131976073 624432882 131281587 56756 345759569 747197427 146489352 96629023 170061337 680614651 626474953 56704779 829106862 474022008 488213351 737114127 282323643 418392371 27292736 642572347 459584691 753090678 533422157 998537858 512244134 551530419 668377 798880969 214254367 714186709 850065683 198746792 191135942 981347269 51319899 536895510 728544695 197809251 486040884 898606032 878423901 112515836 807827162 560047115 439054196 148556864 149677593 721377838 566949235 176970328 216466536 26533925 930061005 749888692 877588134 294821491 153935462 730772863 93702459 368189828 297475923 943768141 419452971 488611864 777631761 470772870 25507373 358692807 668582120 511548257 109815190 547006020 476580444 917642351 107053134 768150991 66199215 109247078 342045180 485664801 286217405 558511715 364715077 68794762 308400406 94819563 363616252 462335867 825592425 309835062 683042047 123068347 106119554 102495017 611680210 883751314 573267886 489703934 242444120 94366357 1252190 352259310 641372377 330348986 122418012 600941862 98499976 188617226 710188940 293061508 674282026 848922696 851573222 38997103 917717457 12489980 133816665 133850060 474825846 811925441 443685121 10384244 934993787 549804674 112879261 399190348 286072339 538663498 888894281 528516459 633029855 742662823 733292120 126918583 925528160 855710131 727860444 876544487 44327357 290565735 169605994 571125734 139488431 21179216 462639188 909722239 33669195 448972204 896088651 361011392 113413996 192290123 371395636 48407782 742094797 336791248 300114481 28167135 875454745 41525114 409199945 508484599 636704288 142492064 635403181 562232447 850718547 215779977 291293285 747562255 358862063 460899279 171204340 350866845 334594846 633843528 113105436 220780392 935332083 9194086 434308135 48746079 201484208 805703770 949670212 796095356 142495017 102301045 676778843 870466114 143826158 85978787 231467064 780530445 80987203 866870245 195279243 784222101 935166573 486572527 531784355 294028635 799988157 702988694 644895480 134583002 189348573 758000915 207879745 124680656 619711352 642187880 25943086 821195559 300408001 975613297 469807267 295419370 77914341 146586109 18401835 74256850 85081247 249868898 707303646 18584801 116739142 902582888 802806901 904422066 241671767 187107607 50967053 41659923 742612653 695862532 28759277 931961225 306379798 89155373 909158232 926091149 583859604 787617669 599803059 884267605 615747318 69610325 32203326 546178010 68712785 50605160 620434860 6310384 300474057 180254857 24895184 269729551 82837745 680218437 26667968 177025863 867326043 77635020 71202137 462455047 773497551 952477765 246932624 932393700 41633138 8607207 711001200 478009093 796224876 163320611 214793049 411972193 85447287 246996374 958150202 154160072 150117885 431101413 160470455 450591942 611356270 37881990 572837844 546710366 718100426 599505811 576252580 437942821 677140831 647454716 900397867 303154733 452448833 147330490 235548433 346598322 155937697 946549632 824607414 952162572 109870242 39400463 216651116 47833881 138913188 27317669 201993952 289031073 310935434 214980758 739623014 922291703 252862747 164977209 321518420 970963173 764483019 897770999 408905993 441623849 397742066 161820211 744778582 850190898 309150701 832843366 49305571 317604749 631909349 873912985 122283672 594295943 913313447 338934787 642129823 52226634 218768807 844123774 193774058 529704240 59104531 933397071 304512294 164483629 98374279 626030713 135446801 715373650 376318063 396869145 9513850 626576481 558689356 754292431 329283730 867840056 439652148 378589301 37961156 71561497 252502285 160244827 665857439 18332083 499179613 160503613 923075068 717948419 4627386 116849126 100169011 916248268 902762548 404681304 80731896 853653179 30712017 68695049 569026828 259546431 465564193 578540677 886122911 24253548 185349460 67922993 744609955 625001607 446512293 782571110 549079455 699014577 942815936 67453245 569863011 294511900 227956857 492938078 864976671 85100594 462303555 965145681 1348861 365066103 369826984 934597109 71235633 253055352 855808509 640262460 365118135 173889053 71319488 103757397 50658953 109185299 171680389 795268907 734186906 618192681 430356369 135782712 169723609 225688656 203235957 739586619 372716908 431192813 85041049 237693578 516293407 547344603 55355610 370158619 912410705 425182593 157272079 983646337 530754297 13080587 476425148 895872431 186969640 400260988 999629827 237628592 509446286 171310216 885413850 96149543 789502896 168286570 231932255 959226505 393975226 435168211 551329475 766692133 866361023 636370523 856902062 382654429 183715126 912257671 752813048 948642182 189956615 910085126 784804871 720710911 775682065 113746370 616583341 962651704 514007357 468729520 52796647 23453643 640039735 938210496 119603185 282058982 106497066 351535439 93801838 352988643 786703649 645131313 972197127 505581024 134018187 829099188 888235452 317733312 593873210 493564851 118891846 783829824 256166329 903696716 504540735 31848393 17443085 973640427 847016448 531450442 442369946 752329446 407420436 934926032 543056293 527023620 69501366 502069710 731075411 163303203 855058352 370295411 660950867 679771830 875876434 794969054 361387369 616628238 112702365 955260578 110193088 84110562 739090402 218875768 987807277 96147488 103240512 5250362 69787914 802773311 389217155 364674212 555102756 796637590 152116595 98159049 176177561 221617960 452745110 907252971 384921163 160319814 130064734 45872029 840091643 5941167 693357434 201479012 622569404 658576151 9255941 585278844 742686712 748346342 656670963 730493989 697010181 759911475 588260702 619314447 415201137 829994208 983988658 970303893 479148149 136105252 920979293 655325709 210239564 226240754 415095032 595160726 386560567 545159765 493549106 226652210 403617283 39422892 280647573 26186687 697999042 289903513 463981882 440685753 38249855 120652844 23696093 587776387 733080670 464473146 207090833 798159 294467353 43595842 971102051 773615501 32217446 744597695 281457562 242457009 970838448 549068945 690134086 209915367 94228709 36199543 436567576 350362343 75622434 717215148 229065381 773621475 7118660 693047262 66823580 897884866 666216458 90519672 338177605 251813479 554992818 545268437 252611637 701976522 441380631 76230039 328108375 473598076 673344085 609565936 568571436 496698885 11151232 258705521 706614251 105379940 294905063 143181826 308258634 370527497 712913325 537324015 144148971 572548336 82887628 63488902 322949554 749104085 154008574 661127158 853433916 561517743 58911946 106045552 263494264 500292576 34791943 591602638 826407003 708136027 53684925 394978438 57351263 64836156 506200310 763965513 22732447 801105373 759663690 330991081 24149221 325093366 868315095 20814543 897641702 951202722 84303445 73107607 552823159 90828370 586751116 258773426 652346112 645663061 217335329 915840375 998471989 252127271 359959365 824878991 812779650 266160641 72373781 870130912 330996797 578574090 634096425 206245595 232195814 246276466 537236675 108861386 571369832 258068121 129675929 321527885 61787195 66495725 394635491 467126705 157324094 981386606 725900130 809670205 479566018 943235458 578026931 330554358 47879081 937986295 7949701 860658730 56663288 80323481 730789641 387660084 511413922 217402417 593905678 743609736 463678883 983658705 852471121 35048714 94243177 834663401 209092950 156030371 901159125 603728440 623157075 58483218 437631397 201573556 868153422 769713766 144809014 298696705 100268124 192688094 89199351 108217824 53346823 145862638 41057656 636652815 533522721 552471577 706571584 979944751 148597664 22766818 963603455 1068785 57815531 57846631 688248537 119424832 66393354 589407662 723153271 542066780 500407231 13301019 743640336 221077005 783014784 888449349 519773709 735799259 933653794 608973059 844017082 839516968 754835697 885074737 328686134 140874769 290062666 35257717 120819519 438660329 58024534 936939325 292245465 968356416 847302308 980494002 87781247 913695661 422418015 663450869 308278792 922825245 676751887 51919127 143902249 312283023 792884827 663675957 48082281 726538620 125165368 744615715 418571939 880001064 482206803 747258073 20875832 772269468 782515789 141695351 63446149 693056675 931151027 355691613 661413090 778453334 336185614 601710689 544665346 758603628 265161557 852944138 533945225 794429796 757379616 677847473 106712818 550264443 194039782 7311450 129319414 319205149 604443516 547891353 51722564 939166671 147665777 72598395 563952490 930181565 66810097 627398638 475754591 997961124 983090251 137167681 628930809 171792216 591394721 26112507 930395844 856556277 731572996 316857420 503502424 488952611 994704892 462731593 891733405 41261025 322559395 21052819 212982525 927002910 421460523 264705088 718685932 569126299 337303483 282638422 351824215 256629931 910037059 827578806 107107406 745643661 817262838 736038215 917435877 261173910 614667073 700348072 117730186 346240068 17205491 473748962 687709030 864426734 936480554 579442435 905687759 259039948 453011605 118670283 38559210 726988479 235891723 757245141 148631129 573195205 892399914 500455343 829825135 654953325 180550500 936932541 400596985 850329689 525487107 170549213 111503598 140154179 870897284 81750136 338910598 888102774 555499097 26619627 605045860 344496002 458578413 363249970 603535950 764106369 334436604 494611511 491094847 570328326 104373003 639725975 143523530 996772917 992697670 825865017 651726241 25764521 615313909 904839577 876094210 993317367 75388790 987597807 985987897 946286073 921864294 177414846 686905199 329879742 56550824 144467410 674375744 515129237 507717379 130428045 131751957 842153982 625039555 622846804 412482308 729412557 115089130 408522189 726185473 107786799 86903557 230428065 133551320 554733817 135267642 862161881 548051183 63172783 702276039 386555431 861975207 624140333 563970276 401396757 954020074 620521100 545864166 480912169 135650336 53581544 611340213 119918644 895735526 236379767 742765447 160734185 965792324 710370929 421772725 544494148 670674079 508676282 627438565 656741750 63410098 615222558 518903630 463977633 678395340 73696021 850533063 392886898 697836353 267019691 794283655 504372778 887540790 340147820 985284947 875707477 246245716 449141511 995626120 141981241 685521278 590907919 155231777 503829953 301278847 577004501 900840452 971952925 938197134 528279016 481211027 854123584 143501573 114656 170617568 674413264 73810676 21150630 67300162 624163380 140686672 714100168 981052510 28227461 54247987 818853808 903934937 153010054 267995318 752077409 147507646 806032947 342985327 302739422 162379251 496780525 732260275 63219703 321249801 670457408 444015070 802460827 377097343 440032995 655091835 547714910 114446258 581418862 421381892 34262771 58098594 562068563 600879290 39151103 590296024 507643629 858004910 346747312 660653682 978516579 98824720 808161328 784549526 294326398 110900749 946928776 791106922 695677375 862664830 112356723 218651135 306679900 767333901 595748477 746712894 422425735 143463387 713675503 3844597 564845278 600454626 61943190 126913840 53850267 953610644 569726215 561493895 664131905 768989879 222147577 642648483 720330950 30308904 279714360 14657348 993726004 79159488 658280621 541919731 941824317 623153695 760570865 101020568 243003948 356319341 700249813 665429682 352299079 266441668 521790630 917144356 866896293 436250171 896574548 920746559 242377166 318817114 334756806 906509070 87806992 556904382 401673905 660654294 439729637 681388264 527827993 285971992 613064103 38624965 827891722 407404772 661778660 440978938 508425339 904782607 797298279 61191504 422728640 2113709 327633171 797035622 919258065 47045815 85802144 668348964 967792373 328179310 839682429 155065530 234688379 780005773 711969911 636362283 440660066 4215899 170266899 968488058 142704243 783331001 7113022 970595964 43252124 521408033 264091254 551677463 278706991 61389532 612868966 553951983 63503240 940502136 350987604 835277656 987547950 436789747 356142971 807856674 764969056 48341752 962922204 852173787 828347524 527408466 341052421 121523941 384140717 511319319 90011998 526844959 147166672 949641371 349957274 190418795 323565756 614048527 594612609 454789098 527954410 59997926 8741080 443974002 500061 212245035 131768009 840564362 649034782 487910980 500937388 266520189 536252731 316375943 118693975 217116606 696300760 312262748 338640546 80441476 823582066 281168895 607286434 823265089 83326617 957243708 13683884 406892372 423808586 460812844 861681470 951762996 520810770 722938901 395736997 373827182 935183936 527505005 66907896 436735069 867932336 567845283 703255257 256701418 736737577 674465584 473818023 433038336 986728331 812458568 365996164 662826748 93627462 973282597 338608189 176954079 783042656 204808424 436362802 59367594 665621267 150560623 11130589 186432036 873499524 259383937 560259218 808683459 786888941 627167113 97934879 507337629 47528747 801190135 764039046 784266323 328172070 237857069 69821010 167416752 50315636 435817173 682759852 996459450 261616122 21368040 25929880 897175129 226176463 462292681 956542722 891797729 612853304 967673310 930746117 486352827 79573598 343521686 147552637 866462539 970688798 245487515 226316519 870733896 899194001 990355564 507516570 79882423 80728984 577337579 247299174 131044620 865671104 930059025 980020421 127287225 803943416 5950300 876978705 30119878 468242980 833521427 774433959 81096283 653711088 557696427 419965461 733284686 901218112 420034449 452263576 724423261 665521963 678580094 595157156 417232316 521452009 102673725 497114738 602180993 532527655 744413911 585741964 250715110 526989288 565762384 230518686 183449055 424229035 107497391 66085285 892472014 793535169 840519243 826084649 299762608 250732021 98566461 33047293 151950132 518600910 337827220 876373392 36639224 868923665 324046899 453871539 390375674 279236975 950986276 992556666 664280981 547916539 430814981 914996091 927422178 996577364 145514776 110871232 273322750 105528518 176956516 18311115 899063686 869992110 844395763 198826294 120724130 795478576 84389938 125190613 166595837 274733510 1564004 203235060 143657174 178127254 509622951 386549199 309880580 313125578 231622216 974161561 861042116 662437196 889157651 640980645 511530911 887188778 751851877 784853660 992717296 781324744 803164775 891780981 651316854 500076889 943123626 624557335 295555464 27513564 749747948 462151300 154763425 603828303 517902712 298420598 781955557 27525662 684969797 91836136 340651239 916592012 918514048 54209707 431545560 660188050 695190351 943076470 547376828 299558579 727930130 392610475 80883323 383611256 136907807 584716528 883688144 80031433 61790214 31759960 960061348 811538161 493911259 114824772 415366464 11813970 265761721 49838372 891855983 950731517 994190859 85023574 719839881 912704907 139233280 3901792 425409308 686939982 946978261 972786135 986498561 527424742 217912961 919898235 911035997 354820768 357131114 794724141 434852200 418921327 826484100 247429899 82975840 172911710 362254670 498342303 37242032 628016390 400697026 929098014 431264259 394887884 14121587 3620491 160109142 5871218 7522282 585518450 692811200 954500542 410820936 531826112 334441636 628733897 304240698 245477632 983554664 513888163 892718124 270923215 932809489 571718575 518353113 15785328 744630285 733124134 366643982 634388668 213656875 767341007 416003033 644921133 14745243 282640972 501057975 27370736 288512189 508580256 612889185 833839740 315597150 876226473 218182203 650038785 357476721 522422900 748032768 193547736 36311062 640750892 464470950 821636903 64985818 835340414 689938582 809616102 568464547 909098916 296521121 782121421 528956274 712524154 279558906 543701516 995165125 780616880 571072252 136193665 141713488 36477788 970033405 309826989 912704260 188215607 959865773 122697332 563154859 560414892 316245067 451982272 53682135 780716016 126135526 118667953 468572781 816074108 928284054 37037327 577689375 77321527 671675100 106645648 789845680 803750357 502863516 785010804 436883588 73935767 921204468 578597075 962929906 743754224 888424063 728150518 931969831 700806187 850847849 347641041 113737431 167092916 799623312 167419565 800325283 925758838 286087517 268898064 594349297 66887923 158451742 172038671 144209449 682643193 131200670 934055128 486393549 634064185 571582283 923277137 560516303 345303102 354390563 523446209 89057326 95330978 104113078 873543508 648653516 954960926 221184548 762390946 122053841 20807859 929810511 774895476 799083048 215898027 43793539 393432344 282785949 54761632 417987366 426995397 737404825 549188036 213566876 76314725 183252220 785149158 852108213 743768523 130452260 59015128 119731083 72025937 154346105 223844160 945569444 802999620 31321437 19270343 417906918 5891630 40078201 347717428 780787105 691677601 416131806 677096995 85109944 698917755 731858626 355613662 978429503 321779802 904801697 191996379 250610879 88053916 977145536 102719091 684338790 960114147 161734218 656586224 32140083 168596674 880430383 977709526 971596294 911751820 996979868 242019563 917643449 889574421 589736990 550946905 433768373 5868795 228043899 371394668 557302901 812418876 727008329 388248756 134198678 631810025 580245134 237325908 572380293 409907021 340044998 109235434 222537520 354295568 765821658 254677602 522892241 498768392 84903480 347004886 263036563 934399699 589024448 33196363 676490471 31277789 584143267 110258843 37146584 664703517 481653511 446965836 477122393 61178191 835214591 463837422 692988216 267976076 701163329 117884860 530399449 893724678 79636645 752936968 248020245 845458302 7614569 770912486 196743046 945034400 117917371 312295960 879434099 559458171 345492323 408440921 590735959 782151941 518699764 480398894 446855458 852869626 927364730 776494202 914047816 615095672 92847975 459552383 735588100 794011303 577437242 265987548 540252332 657073887 18924515 788272577 355048540 879055435 411701414 404307937 676606187 382135136 716603897 408556637 941593306 62096219 816997557 384845617 696764511 188213672 865244510 143619968 41083297 645125591 772630521 955131113 112737615 865478495 267199847 848325714 512006149 844637089 114313261 52258481 354227327 985754127 693047409 561792218 717325913 104748822 966100155 246448451 339400309 682704051 655005087 133509967 597316621 472002644 518355583 146597483 660216315 236116444 142733803 553815964 881242035 915364323 361463428 993979649 780842818 628663274 842305362 145365318 325816714 809134974 197623798 680044040 647405452 890671206 94352610 217247716 847936379 60452764 463696167 39853040 595673166 118701253 25879358 45506138 443220248 544234940 192103620 955952915 780351383 334837422 509768878 514109769 250201745 871232305 508089417 883560914 352411930 202911130 28926231 678228644 864562455 79066381 210789035 364484258 969737586 305141644 581731974 670190317 365594407 897944492 562559708 961267572 869162096 588439065 6773709 164898696 132674004 51393681 120851610 765541738 386231102 483136839 132167859 636432846 206885495 640257275 372510111 559297424 695684757 401436342 237526067 560247211 480502722 448315102 924731469 302756659 753456745 358979794 825463327 971567504 109440637 388023034 785351427 978602732 976462098 644641488 143501427 961652453 696035168 116869388 579710543 82266269 600006226 711878401 571215467 806891720 204652027 943725577 366189144 900336783 197678270 456231562 313100346 678180991 904546663 90348166 833454002 510519760 301844311 658917328 334603615 411284947 899456714 119955041 389887678 728435163 764596528 385905457 542603968 313148047 502774844 122314510 395414316 102781070 686709262 966629782 909672789 743877640 762871710 128378284 496730775 960549980 584609846 809831120 491247322 341672860 752695637 324701323 704708971 54539947 836135003 39312585 465824893 735591716 11783978 708228922 316543230 776380505 94134378 859147197 89528552 596909222 833978058 337459219 552206643 373203671 156605352 314395783 117081311 919477061 442774067 613812085 732543392 879900264 276159556 223790714 74089475 28855192 401008388 778798446 935911490 237143390 818111030 254252734 825251457 829895007 962481655 141794687 458791864 56616033 941883 400836767 506041606 687436293 590812337 58248248 60639963 747417688 225160382 30237625 519411100 667934448 644049709 104470844 400351063 772725616 328261557 474440538 654097159 729269944 253238983 590008648 818929686 923866364 844261381 644181142 606277723 659259388 638492180 65069586 568391772 491950415 318422704 74433377 179386707 909235040 985197976 92543021 509169079 62874709 122780646 881096530 730809157 766830354 985567373 131160219 392072322 166345281 458117108 46169480 895615225 711356090 488694480 567061262 487738806 185472212 63758755 94016528 844731599 702250935 11602465 413123370 194201349 182541520 340073098 226104407 91776559 177787425 318647427 453461989 240662134 441428072 187074870 823987642 60774778 172642243 807664212 452847099 338987523 265781320 499016578 87119099 829653761 987711057 654180360 317392566 25699621 717939115 263925445 870431219 272706401 275527909 136070941 466907749 458069428 476144038 693012155 402362338 506447815 11659581 708340678 747109948 305604005 895415548 423613941 366378782 68057790 231278152 819225880 259561664 349575823 170758809 199197115 179229584 10986218 853377474 349138501 36685838 423832940 613063946 907117056 696539340 888591854 43187996 15963440 199177634 371848386 561491946 454056323 878296200 425667879 162397001 477922499 731271883 57812548 901536439 97650664 978386689 132814590 916876543 90464704 334906765 87635351 289661818 514136348 98621568 995555644 863274848 135307405 271904935 328855145 894940813 968444275 69963351 938128808 836924066 269140984 162493545 398416012 723197306 40789744 824083890 738110658 518712242 407872124 648439557 272765032 505522787 479342597 258095974 274915681 569807301 593002738 215067383 711985470 107139085 166205303 707541113 822930284 154029059 979446048 4301781 48969871 800406674 74265131 839615031 489847091 343406114 2108575 888263102 919119771 895414671 564863343 657230429 266643264 972735466 158186337 539408296 330774604 637528934 797504269 458206636 59852586 390507006 673274019 771838055 350162442 691995673 331895520 25609077 846024731 163857919 29910857 747510954 964264592 104175987 439642336 306628034 300098452 294267262 47407488 219218223 42198284 612270830 728965003 308841548 437522648 887151339 848249843 620813603 524680272 645754111 79020239 584532857 888777468 604810609 208887264 91456261 296806281 540782783 117065337 995347363 704640701 146976194 595374668 521421644 103668532 35017003 828049677 403766984 181800617 875457164 475501558 223998900 340244346 204466560 532840447 777766993 91617898 233606641 251096947 468814522 879360751 330117185 905863730 620654570 934927793 114750993 712110830 84250425 655533775 829176167 79597788 212690827 828668712 527488807 734112470 784853595 415022162 562162147 41136930 596822778 290135662 516638487 673338029 630380007 721105046 58694828 260663351 665239296 292301468 511760298 986570169 24178571 841877482 892433898 644833140 629321627 859701243 356943970 566088403 367751369 38636488 498202542 580442196 719821551 25691349 314554665 504675145 440713510 729233163 545812075 890052639 19368825 62450561 563390667 649748831 636071959 622085494 910412182 153827606 914386962 274688831 140397774 938565532 116566312 885348023 435915023 598404290 597565617 792858992 17009045 965316986 684011831 515211586 545759181 403833381 540902934 712830197 761024878 834132795 442063360 159353304 724185433 313948536 74320216 140092452 963697366 710392174 614694297 726625899 716736131 381597610 1314729 709650256 172679493 970397393 447514631 608594516 421318034 45080247 253969859 438327078 10397232 937981690 953538664 408672764 194331422 346957949 121502961 955356299 33607096 416082672 114709602 757792528 730031207 189029818 750401331 546244924 751938343 365095628 125387175 468674474 746693237 979218255 30841081 919372730 802131999 478355711 380483597 75966385 523435958 634453455 514293462 386349541 572435144 320348477 647538657 766766566 519822778 621557969 574639216 553429873 37640640 689348818 163738752 620188198 730894987 914140083 18949473 482833329 131752062 144336647 804024154 878445298 976071254 834865235 650334379 778203252 313220945 30817975 854169636 689173254 517787782 220979450 75522795 90222925 393844278 575577803 709505842 913667055 197135771 136661410 467096927 87292762 826010227 630835679 559997311 409421565 397492113 578946783 892254893 529244174 575799782 548795399 260205823 404387387 383660633 910540202 35106990 549397929 793874528 889276626 238571183 164178661 962772427 166610329 106917938 356616704 742188131 816423779 122800111 791840253 953085188 589897037 879133014 631611766 73249067 291646676 41033330 470741179 870593458 785804575 999985352 298909591 187116325 112707527 703296977 570776957 23247728 738403967 120174885 669638607 480196944 211262419 833817268 295485722 230389099 940735205 652102425 972577229 609675335 774902535 616933833 415276875 217315924 348583198 899404992 143081342 640229873 792954674 613822521 363339683 431275600 466324224 662249273 618391924 579031750 218062602 41685232 454795829 808982920 14376468 976950788 141696215 225638887 663284407 437181936 456027985 456535963 89284360 281121566 66211297 716703247 898055398 334004523 786535522 99154948 85925867 929616863 739384820 878880540 395955735 102724502 310156139 862279959 617490127 928548062 293828060 835552728 970233293 601140241 497051999 984609760 578091028 638748213 62764998 93891786 75930148 371309335 550427748 17730859 652430900 469155396 586950457 403002649 803159919 373485978 502157596 889085785 155619193 94058768 620482676 551574927 196783269 930638814 266371237 814273395 711703227 560199297 502342474 534452871 13855889 999394472 371578982 591946916 490659036 286860332 685838701 566589183 658169666 88782800 436836394 163116917 557938195 23786850 566119565 213614465 249789180 920793513 102700249 405408372 14852280 575699276 956983298 64151900 358854441 223354535 878425295 70557667 636070183 233284120 457526889 649926071 85194944 681622223 94389338 575853979 968482554 780228038 994959514 626652219 869010837 431795907 789769135 279465383 308099108 208405051 493079848 557888287 129198563 448296448 963296658 996567194 23995724 920279956 60719094 382850164 996150842 791660740 305924183 632221024 24944859 615967423 134663446 962656154 297589645 229052783 391026485 118588550 9280820 385985998 745240768 730808008 670298256 387526254 10273390 978397363 448447657 355869589 536285650 430162571 804166037 352098659 426729765 828161760 124894966 339965210 63528275 121045807 131625949 221968809 605783182 9087159 837936232 740446627 971743313 135525876 969499409 215286149 106630778 831296580 601272146 851871545 414620939 124086753 91914151 277410681 102484115 540361807 633280269 491286116 970524377 437446305 843384775 249770493 118124416 968279740 589735702 34169043 89325547 573878002 256137851 547625080 582965161 94074082 288071707 407224825 82116310 110087467 622510973 188747087 941384047 76299470 893134983 356004985 200386222 985049133 633415665 155386688 377927291 119212286 646672804 200968020 556658590 490057578 303254864 527299358 310853669 892990566 561468400 252695567 319384919 817606250 800320647 902350079 911680332 88392353 162091255 846312993 50996171 637118579 35060079 992380217 713418048 780711413 200901554 766320621 618276898 834317218 921707309 996204188 953529503 568380112 49688559 362704445 910954041 352943423 890003802 221807709 98450340 303988553 474503276 417835258 121594802 127340274 172701689 885791485 68248978 187309295 732104477 119245148 824427874 619680907 111625365 390362273 252908672 312526918 156682894 871185569 999360487 78390202 719906108 805406342 499286665 769594667 20627138 262757057 975054441 910630939 484564765 73504780 67135843 811584392 343856389 188730644 938924665 369074429 74522129 7173642 556383724 659142957 126418790 380811597 131340216 90560506 771173869 384248887 403087423 780373114 107950807 254964261 711279667 827856914 60370602 63082683 449967932 80997739 325839739 425022372 844145029 810404504 351043503 911280871 474505247 547416244 100011515 413429912 916490672 27049995 273119905 472874395 538709303 399538694 706202343 522565870 490099199 329892564 906814756 745702973 110265677 14765562 667234 821545344 695138828 61037835 884628026 145106759 994551926 62984117 422645483 838696954 873388620 773688985 602494177 200410218 173621580 555022043 613840129 90112252 434588389 886960034 415502998 973297691 139015079 121705341 348379913 481630630 451597904 107711020 227333602 414379932 122476582 80517187 88441627 670131761 141555022 973069653 815238519 988623299 36053769 90400353 679836604 761958740 864089338 282330780 962368957 37710917 837352822 428725438 980339520 124457562 168201823 395842518 97755253 159733253 370064210 298651517 641363882 821662113 406362536 868697484 88558396 381355469 949214670 177000023 51487229 943286043 2586027 719242100 784425693 38639795 809642452 464262297 653114886 526248141 599109428 468000194 416475410 288978602 749241983 396814929 413436163 917443805 645173798 363707767 77177058 15238007 662359283 571057291 689416471 68721819 292271126 777974867 450077287 94002148 954974889 354080868 37288190 957560915 73322967 674230235 848717061 882965418 138492531 354348298 261729911 590118310 822348491 678205320 879096911 424106826 75020248 292533074 194066982 572710398 656240840 123760391 587948404 171116475 694817682 129881227 239838293 987088807 907856093 542431931 81090954 862830981 896512798 970895496 672908247 969835764 645125730 521625307 705317534 636134612 875973604 967047444 78769273 550838446 497769115 957866184 974945271 425305714 102915609 21528605 998016111 759156448 145288995 438480867 930272922 840106676 568362093 22627566 827195483 476218185 565059497 760802788 191565517 314088646 731698283 864473763 136440762 229340364 238615421 841758295 717991327 967105376 661322090 796760600 370460173 11607556 754626783 197921796 436913269 857542391 219450400 434929380 469215190 364739394 873410246 252004464 204846070 294288690 127148381 884557904 770506874 692207877 645360691 814588742 6296523 229575326 531578856 142737284 311432041 770194276 837011930 29423368 589816003 350850371 826183967 960276175 362457926 433327101 158197970 799371194 143385843 377648369 86816925 465117384 742387763 812743522 717121847 799750184 107032211 844270228 684308087 730055436 388994456 182185129 544644177 247807330 264276806 76223032 243060965 575708847 698933659 932589246 605132214 141266013 135955968 283832532 101542188 498413893 569675984 112256509 150301439 713061826 489904878 89634715 30695561 84808992 902378237 747817408 884559175 9410447 444603987 421383613 591982235 686114794 456085093 136626411 933922124 720361899 65365795 29499440 296070745 616815805 962088686 753719310 758081818 98044653 37551841 712140357 448974898 459744176 824396865 451792688 25322353 166818094 541427402 56017913 251627085 443805638 803835320 988702611 305732437 100955658 262602575 897714671 787070452 718687668 886857433 573508927 439049566 804739579 455524718 587636662 274071736 270129755 341355971 884669905 220690760 231424163 596810261 669665657 691168338 273723477 121458344 716490690 440541571 515402097 772508602 692168655 959207735 428860274 533387618 117456523 382332283 795990192 867687545 21919086 514677859 607061329 595428012 806243776 264317260 50952730 393880437 538388995 173598836 587752759 275575251 394289595 819176921 872385511 63955251 362861610 146108987 37929946 931868651 439166909 405848395 556893605 131335564 217572481 985753878 517239533 335029003 220602512 313229724 55232899 242521598 680423935 662294227 837949609 486667710 926611486 741418690 733064499 317516832 915017526 320817257 593092082 161823472 992510530 317993944 78295075 207888491 316619283 116225020 139757142 755786191 374589766 696650746 739638106 592162246 534920975 256877638 927191248 755523486 422623714 982424146 998045083 103047648 497234725 688511044 442231709 423846210 282446085 175296207 741363042 49979962 348629816 186971475 211803434 341140345 504965419 290098508 549028835 821584701 258839879 541302328 577370891 633429645 90469425 169525349 78108242 625390399 426402986 5299490 233430237 849026699 840239987 83991671 804590698 189991063 625019066 246822407 613837273 907465151 274634965 207716666 809961464 623264780 394688140 21764897 964405124 899653558 164379756 365950311 573754610 275735987 907252638 3641853 909165631 997722063 173167201 987273872 475628813 599570186 845089713 561575401 301113237 537846052 645567072 105703934 727837114 123102489 205042692 194190738 30567639 479677657 254423755 693045455 102942436 649111895 567326703 919863912 401281804 731706459 138330574 975036414 7442445 898099563 978678266 769124427 748337977 4361818 608914650 76483142 603932003 306520715 638058542 757561591 696883118 136141965 715781877 277236583 259244454 920824568 471427321 142328444 253018576 725851075 835373898 208477364 227479321 402700601 980857627 481277477 986923411 119188200 308830242 846882207 869804114 140024859 468522985 618142091 144386676 77437634 694625232 748318678 236474700 185200125 358396621 933357817 321342090 74178497 63110752 580586543 847519416 534538072 722914986 100537992 112905498 558288884 161531707 192901171 813505836 142389333 674178647 800429246 114093884 983008888 499827804 836414349 123033746 968350788 307072791 267420421 898304773 1698022 868255450 134779473 39414499 226652070 920653641 360756588 153346918 983764392 941343130 866334 370818815 664258115 953920677 336240665 75063350 115452383 529141835 888569185 110358067 203320481 541514782 76968302 38845720 41342585 765899002 161879465 862209724 72971793 281816237 760514497 927186166 150071686 747810321 966600664 229240108 520980313 327357251 382587025 357261057 121216732 383453358 580596223 785474847 189890386 916836887 713054548 157859120 445978721 454140085 120733538 501815553 995654866 50218191 540661272 889513803 816117193 702540736 604239878 889088985 984356972 217270726 668791502 986945010 965081046 635392166 216185117 338577711 815265768 598772141 548355119 936482500 834741851 128951341 574473698 24632236 45788228 287528245 182491356 344283300 741668329 303224893 846098853 589839547 353443084 239276476 331869701 22076628 941817212 936109578 911165612 778690535 5896656 432473465 618151896 970977701 67865630 834337012 162071763 735647750 285625505 710426881 672130249 120367355 691894574 99120298 997515942 590199153 386648542 32523649 934482452 980833223 335748542 633097656 423189121 541707977 872374132 755058821 563784604 666707695 543684750 327466567 297914581 549581405 759940031 916066477 373075458 680322013 602919840 387663572 415969762 741061696 98090453 940616362 713945402 642501378 39736659 711461344 232700530 278901552 743984992 19699333 259734774 932249885 505313341 682923894 473957861 230203824 290499066 37742464 896911518 686700168 217725382 47342450 88797924 977665413 815925278 461873381 657987425 271361470 849536953 926473538 12423165 800143757 867089899 726368567 295161486 759342909 290346262 527862015 38244460 886847605 400077699 150495586 819097490 905391039 833419479 145571702 135594862 976434897 35830518 885022731 663135064 253555899 932365181 751932987 83737663 600806810 66322720 741725087 872168279 768376024 520714976 884591444 421036132 240321226 463476362 716197617 999664134 606338975 96575983 37908594 493186579 496653681 40920531 164800420 402044720 874340009 162888474 390155933 703291257 198718991 275178664 218942672 304791241 60060196 970875659 388528904 660867005 889714730 130253990 385551636 658090753 503485318 122659431 79126884 743806543 586135792 647840852 743470677 44991118 744416834 633895622 538177696 241070514 674816152 555494468 495631585 401672512 718382941 885787518 104963769 917101931 13482533 176422792 74409523 73542728 147298450 462938426 586926084 889529531 445708768 972477719 400136635 949194085 95137149 331779870 693000627 533789292 979620721 288987655 578780409 724037554 775399628 116958105 817624420 302732131 524968924 313256004 704404643 243351864 51559873 661884763 12970146 65042405 838307554 87379668 138585132 838122356 550318094 725511216 580168238 996026861 550505286 980304873 797737297 645642435 312084742 343254275 31948078 144221815 632241930 610728487 868259368 260157909 580202943 538400139 562890040 105171866 851656143 119811034 201040081 903216015 781695796 214010226 968258420 472519701 153906245 959359903 163158408 704224338 537387470 743326646 552767550 87892756 576147870 203021198 586051542 888232611 546275473 617999619 32454425 31033754 228728105 753230145 291191662 808931047 144146635 854081701 766619264 995802777 973892734 967659344 751535144 608104881 34185921 572309915 80624582 188092166 384186169 96299341 892316503 921573639 692142338 297600405 9466394 268290207 500621602 448034287 9039170 46897074 66033905 894009946 77930827 147278362 499756442 221638841 956209408 643903077 75720541 575345024 492222205 49613275 543004367 96273700 510234507 577190288 668583614 443375440 765282453 52769783 539674781 510115307 826859773 84333470 660232063 688842518 352623677 13370017 136876804 214179198 60267090 55427060 108189143 990714269 202705421 607945585 64869461 11431181 104365013 140590001 586776204 596587217 42719627 129780570 692860917 552954134 559487209 213960882 996329573 177286013 119247016 388520705 539917672 946106788 472854175 200149734 634949305 677994203 213519750 624342460 892173400 126303192 679769520 362542 969533812 882474940 460824478 34403272 893906120 565189490 27509624 480682323 14293059 70229251 462979245 707153975 475699736 874982805 921114856 324545660 52268818 40361872 713066365 444702841 986468659 38436891 644852574 473934316 716431093 710888676 98276775 461120844 837191867 630562646 313999737 659242030 513037586 774824215 693645301 259460057 192530056 721154924 740142380 206823114 643900526 55637976 913977088 119600261 930620780 687608296 444145921 835405949 727970167 9728637 132625141 566955177 48165527 777477715 893405844 617112971 340882742 844198971 78233814 30590960 474761616 244749902 689832989 840315553 19574116 235994641 99775610 64620524 957149564 692434341 123959989 453566442 748072316 37937077 573166702 531209447 578061724 869828974 219131748 158548242 879557610 351756888 725503418 780239488 981750954 471425614 249868810 322633695 315624584 180618975 353224654 642902551 425368877 43057642 483218104 297459344 131568634 435510065 214596219 88718198 127944405 338556208 394800991 728533072 229009636 967967692 112258870 807071359 690313018 331390617 965619600 422386979 535663857 543639369 55142819 517414810 15064982 305011628 692564857 183205917 338146955 45789510 826108468 763515831 941363504 161842923 913491526 72932137 597352987 128087745 14166686 725297391 466643952 261484028 306346814 695653587 81968072 418605683 355241297 772281089 749996300 320860896 194668067 138176508 864500264 249810885 655591317 732081598 407338865 200672525 915287514 745485819 98978387 741395981 361518001 40341890 903238903 275009526 965790378 353108241 255613622 832473416 78405631 722257573 93957443 237268796 270427511 28441866 655874479 625668807 800722954 258387130 799046054 995391021 396563637 516062670 97718257 52154953 248144267 505057121 105343830 15948132 103059291 204322216 757344113 464577291 97180457 513099367 739586817 62970834 866207608 995200438 747960601 797129590 569974363 694434396 34398386 692918225 722876261 542789216 171103384 376115567 801176345 970149437 224022939 197739981 486212106 321741195 102411285 586872724 679314668 207755114 602820856 782373958 412077329 212681320 246951249 509257785 725780686 839054417 424744971 444504645 686771206 25221923 94150587 109261920 572172670 981065324 802180145 147565283 523854539 973283528 523680849 177547235 943432964 747703787 375287215 282161422 69444981 330214851 869034145 601276000 537969965 324371352 383649958 802563645 537052671 483117558 164337782 115349709 322171974 589082752 559854353 8943179 466821026 506521291 118205099 38993696 487586614 772901595 186558978 863957504 746185122 710239826 41504738 542134437 310459964 269308304 676812210 232421296 599523155 398362707 833697296 137493119 722734058 69863605 792573115 259786729 552981162 956910896 375136437 875153135 398509999 787507141 736612665 865331025 294028432 707334115 904324720 634131397 332752061 943400049 498088901 78937182 506156226 392109990 473587971 816616189 661418294 2916532 49037484 260941448 401279238 882734779 250950918 124013296 952598383 43524032 236316376 358095896 852951280 611452812 85765382 251461278 251476304 822378047 116792302 545504735 382228513 873633373 32152484 714980574 669549773 530241384 646434107 175705998 922351373 972538429 992322186 436286018 975454961 893876022 697227465 376734198 629127152 800694734 353263845 434241887 696735118 589580220 792337782 549686397 53549383 878103164 653664026 305025687 552997562 622972680 850530421 935226074 349122404 882682904 502722999 18672177 265440639 1673458 46894526 40308364 974211886 39216712 476594381 802183198 785609085 26338198 31433748 414736236 827032931 384697592 848978122 376284400 974277812 493832256 925970796 27827194 371935419 432151174 332852880 924932980 55123853 35899653 712675405 404246256 771098908 67914756 275434784 36539547 69588213 322329310 929364262 896316450 214062373 258474994 551016000 999671457 284813191 582449747 266924044 964362474 967147338 115902166 340646873 941425149 462250773 119134021 821768695 834186191 551285194 7137926 611635522 458925398 43037578 176827278 863171653 814136486 97258385 138606437 703192384 19362949 313452098 485072997 915679399 527514470 743547990 319211750 527185926 28361181 901661496 794109969 845240006 868808833 762528486 38403230 662750334 77295610 157537250 337035380 911481800 561338795 344173305 375633673 20264192 387210883 404977303 735952197 53863720 502235687 727074985 609572455 521598636 40527082 94645451 289794386 568041551 838193440 609006135 947743828 719070972 510667630 594370148 416827329 231992814 209414986 455230559 747259499 286710595 612767808 84294878 50708747 26622955 428468183 426342419 46887146 668195417 831319721 782839342 722059136 186071760 362430678 184147942 707670395 402957759 278793392 997464780 823515661 969503183 606470914 771259488 541090507 969654895 218145988 957917835 54164060 427560973 413148393 801423559 714271567 878432553 885718436 764980313 905055507 166702970 43839084 951942652 834898386 875158804 587298346 409473873 61230563 949729023 593621814 621417309 205203134 724931557 618882088 28718794 694434740 77869353 652494634 88041598 47524247 870640621 45959432 101688307 150717945 311624177 755628217 864989511 190056729 493863004 629969824 95112235 660565974 673808907 899571238 347980711 401484062 339385935 609970936 315230977 141631310 56109101 936648285 199350795 781040658 408046725 80585940 327991749 338432429 733080573 416033346 238473028 456237545 461992777 192677686 606955489 773616953 948305902 324461352 816190033 442168905 954431175 763818619 955251230 480756433 515906209 155748293 734756846 855292143 765719228 49987822 849439804 821828328 839152459 48790598 602868985 99715535 129376538 930860733 438147963 714973462 199410430 676620990 23727359 661403207 869298675 630682847 287536511 670120928 955144198 103726544 112289833 762091724 720061514 920057414 95364508 235967722 75805706 830121354 943776217 841524933 732625527 793216020 515869613 424294337 694522970 118738597 376526223 823899507 902115682 814674186 391389320 101526111 343811527 415116678 615445669 65626554 45799525 755498532 735747481 853460074 711741427 700553665 468068150 431802940 473127431 415949009 520287014 548933136 98586714 464063230 242974421 831212241 109795601 758844033 108022929 804318570 730098981 484549152 480734428 484731014 151739689 872123748 438773477 348067567 139756777 906735497 413694120 38072653 662234028 1957953 891532727 226491806 555027969 212117228 658294746 28155399 628066236 31098111 429604887 726652950 495161340 672579307 410381542 457473292 283939691 370920822 114308214 866555023 855469973 595042641 203802389 859726013 319682740 642575865 207793580 459439517 401827713 474004051 497512169 64061741 475962003 241561247 143069898 30989972 306194826 801364643 911661722 934261062 832462753 341266608 513430363 180140444 866362266 776328256 637613736 2818308 147249077 751921949 869373331 855235402 199480941 73175719 714961414 371680033 568267935 775271345 831119549 970095647 249275396 181148069 886673739 577753750 275225668 29743637 461260073 581420493 683624631 372921795 368197906 368603736 566704754 881628268 548744179 433067020 510472875 38874266 435885327 657721952 643312566 157775009 365473705 842793507 230950727 80435118 66989891 799218661 708222815 898109439 621830660 957498210 931773859 508504398 387768311 206999526 390764386 849028384 788420019 74389017 74466530 9134276 442992752 641171283 890762544 844253282 74238302 253751770 883127548 362639981 911473721 378956465 520414989 129463777 74266323 603882068 62415247 141256213 255617080 770638061 39365651 877447739 580652622 823655862 238468489 968420932 30655387 629232874 817449315 671591757 703621890 891915844 680726033 999130993 385603479 424004928 843384275 312358132 677756697 579028174 674998112 441746770 957984638 47929453 571210546 32250961 651811520 633625792 26023525 907428599 256780204 65389176 637392690 837432825 741561389 875861178 805853757 624733127 505094051 475819423 148841236 61232293 220251619 829567268 60363285 605855097 106088547 756263911 918213228 636361595 187808436 445727692 78108364 998309426 346173496 501835262 883076738 997985015 987977405 909100262 757929965 244757609 827005789 247839006 82190433 568567177 123700183 740560541 45816656 481310586 68896316 194657891 542542878 141664286 24225158 455422514 747519382 982830056 64202777 518248961 619191650 104527564 816493004 549816366 102836989 162666499 904167979 985913726 13167865 892145383 747530340 623614182 989419343 574536128 871453187 924126128 995619657 995153370 517203020 41436312 328980307 586099335 236094202 871523184 727763620 112835711 179462049 327799353 95665766 96181177 698564666 567373767 200708741 515057669 969706484 303545729 530240520 873874462 141975807 543408384 618536197 889506146 19538917 460471891 316558625 890992104 384598018 164694633 738661825 901801038 206130944 67642131 340416724 294741497 791681666 920696696 407577207 971143714 101012400 355759324 67324891 799577065 775649443 120549983 167151086 745355926 424095711 697391605 471746740 418587869 93316340 942799288 160610366 112855257 403271178 477168991 3847360 640385548 641863623 742509184 394702937 700510919 662667666 735119660 995252415 454349331 508332707 255345974 278009396 609345107 611105297 197850638 408922171 239271091 318400620 576073256 984627017 595012683 125981212 308890108 13600551 219297552 104205747 174210917 332152808 507476924 503896259 336000167 378823 145759881 931025702 395081759 698787151 593693367 130201419 694039566 900559049 491050477 949385539 31084796 100395583 413007187 228935434 361834106 652278278 399852405 937907361 489421646 994865087 63888573 650828105 8465638 135702476 755033851 35192906 467855283 115027126 539089164 803855449 115405949 537365396 587397502 510487707 88668899 33607220 493205477 782708464 934166268 984255954 584610354 965251063 84651536 850133892 46702848 299001993 354928521 446555253 89425706 844350166 441420339 5830630 347694622 302402328 141533105 102728472 190111585 609388387 217755598 729200748 265760187 333161546 119082496 853157688 843649252 207751394 886764907 189371081 842976209 820931174 173627034 280102914 638698588 110794921 130236805 685401436 409796914 485165326 131956688 499222619 182031843 425893378 505053248 529726465 728295706 646586352 484971288 918407290 108491090 702726885 500124390 374251276 888404782 471723237 227408963 584570386 679474630 114173869 773941466 374967190 787621394 947568499 655070103 278836333 910879771 785306907 964237768 173193036 122988584 96194455 672415654 157536779 374604185 29985253 687263243 102899890 529087956 24750882 873823531 637579045 727477767 226464272 11830320 468398900 698187508 91755634 52969285 230178489 58445854 826910750 605145678 846067247 626995600 112732132 124903580 390391723 898039039 941657699 563584758 873543974 890368506 88516764 31080752 264972690 118502016 570860346 220388931 647589972 595611228 946728813 137685368 175605346 25709437 149515688 644004245 723896944 241271321 696973530 806591785 299717175 376400631 264253814 998300773 855912583 376985946 975720704 246304305 127541336 917378403 809889062 1085309 660263260 898405825 32166061 925235949 869424193 455542758 998141231 369530516 51153985 944870043 507215883 226759330 970579479 656731570 870763575 546992775 750519243 420253456 206100911 50236417 649170438 470354724 901053541 505083020 847340669 876774245 603903676 974882004 646668999 266309090 975967313 159448610 17231266 860649725 84684558 886655458 168708834 935342140 256185973 219862819 732728534 763401856 299138500 555824365 272649777 22418426 102817139 23169019 442671881 161434401 925921787 91842319 631789124 679491680 449441690 479129793 408782276 53345366 306528148 55451274 172170807 135011812 67416235 189402072 995661536 4617144 76057530 16886722 939959283 184759854 236749540 672687816 948161709 535888039 81028532 73327838 558306465 36362022 949013208 853494697 197796422 727451347 797853367 829585546 406943026 99811409 161231690 815725301 5673126 467759837 723692926 177843932 602771649 791109160 367246003 450949536 795726303 443303532 467836257 588201937 628063386 704585796 113406104 428741446 92990187 194434636 354585635 503813003 230796657 303598843 357307699 428593079 31050189 7677418 258178624 290509566 107488826 419410313 958751218 113161951 887170149 534960495 291005882 342458149 178586006 658251884 793407685 974312308 101555416 261243941 415030596 582135153 818346089 528436699 863392950 911336275 722871334 217978585 267665629 953667991 374093779 624973327 382261069 257660319 632650744 492956044 548169884 740139569 912366356 359437453 853301519 652052856 894397947 144307400 994511005 72983952 655075636 640435041 899812611 609147403 901678981 314843206 43798907 572541421 843279904 907191856 336394047 418667590 125170440 604059675 372335580 351780570 81549354 607113000 609440888 714200097 100069043 10127123 306856018 864951750 369564575 12673888 369520957 263962521 9497640 216548313 189462824 664573275 856983353 89275434 126237029 611178686 256634991 170035935 183720106 99914895 77227790 520114153 371098836 54914582 124173827 743434415 406695151 58239532 203063766 16136039 772439629 303132808 26263161 931811998 20600909 248344088 944485885 390121865 512306608 806499876 606670178 701769432 323589502 463653530 643561217 449826530 74832215 900196208 619862464 111068673 852627454 697090254 483699177 223726289 604521187 460389355 819677055 11216337 518628887 22740820 879868727 143584867 178389979 758648240 75396864 198990887 6992327 872399100 589112751 371815286 678898976 195782928 926101069 2488477 511952810 569662286 304831359 439301376 322374845 924693822 550370048 175002298 474300427 34069224 251244938 78821613 346974931 70921992 942554302 865603817 93662811 674939380 9188683 124569141 286103971 84585546 323560027 145612649 809500997 912672777 517427935 340916324 108455705 296045355 195921153 472924866 865707640 500752511 912226241 40598836 425446332 315112641 215601133 899746759 201698216 466846070 831084723 548673146 390284413 773639024 414276962 336463575 301094756 275981996 461032715 587198726 213083893 784592741 732811375 22584890 697265518 102755661 363501213 658237574 398801015 559422365 131162439 117025007 60174875 895905031 157623842 338137559 211017671 373224975 90400669 412715887 692587396 921485391 961389032 82871809 547640767 228182346 419335383 848735522 504164341 880368098 288450599 717248234 517477190 21261973 592349475 67259059 124017633 955850687 725496632 522818648 367789404 709175422 639843654 280480630 457596805 797467495 471134540 668614475 23208821 561535208 933846713 715796217 335536951 747752097 651184377 735694069 975934442 70519759 436945942 332615134 803404208 725396540 902379719 173397750 746658513 494729193 240656808 723192497 303096232 966153440 98527496 523401987 527845213 738371149 803882616 985442017 388354996 127533508 506572844 264080168 689068715 292935908 979876384 877122017 40688004 483577112 612816085 869138797 406613223 49762026 54270283 62533782 627674918 956650001 235931531 226849782 303895546 476588339 950042278 606991777 295258130 48569774 130393763 823103342 639457274 786792730 661061711 27812269 914326237 20150906 144408789 455911304 313086813 124285172 185549672 206291169 460378636 798365757 75429965 866991858 700644134 129700247 929525639 180835403 86350248 165457170 407685184 242762145 642045508 357727462 849753921 937303637 258813587 832664035 612923330 898270860 471973116 126501392 778599481 238815705 146652297 923008269 547243360 312255462 899809792 732793031 518546630 360188427 383675139 446492946 79696636 84319273 576193193 9222275 117671027 515059792 27195796 525356211 757821936 669241303 883083672 460092208 459061291 141897258 145272594 924500972 892684469 469762061 51002364 671283949 708577765 50171012 446808569 108337476 214942825 346618361 841130507 586005806 559323139 224805645 32498752 639019775 161641269 461208296 648242049 279312296 976268087 675437844 804668506 586606374 197195498 540268529 899214933 508773140 534682138 44487526 433274111 279882958 366765938 336792826 951166907 75343703 239480190 250491827 36197530 306939366 597110187 877328036 892945172 8949678 102133681 925443923 647969452 116291301 239168570 148727852 248119948 67953008 824165695 52788453 654559381 873877544 445573333 406290665 382650683 832771822 303294542 668441145 112654780 670060479 5233971 916338038 597920533 97230512 166829864 634118063 404169877 616456403 511446098 149631400 625406080 466096130 75075322 273375531 434903783 166760243 422103382 683023730 234713250 98785428 588328535 889272630 972662971 33901867 148079646 207830005 719190041 451374187 876271149 831844820 121434666 734021471 600699209 719355198 683768334 767529072 205989612 87938211 236501826 717435710 90085962 861907905 36048191 17677636 135283435 470951973 184437878 409903168 6492055 419151128 361204947 594820589 160940109 186384269 481238807 309019755 394214273 200428847 760393941 123001774 884790018 881828606 709539596 485489226 453700156 393307930 105534650 659689767 333762492 342036475 229641828 423848453 56460732 118206371 441526088 44260518 589158343 625963966 454163686 595650397 45115093 815368632 42987337 58571553 1752901 524226144 367591307 248483525 724654990 127985248 224001650 461961360 862330205 933541246 947450585 168546712 179365527 905501586 828236479 513128018 100054413 910394658 789492822 156515144 28601028 83535262 200775661 470275723 709499227 654939346 65926119 607130671 322824330 108913456 665702223 177093582 485655951 33293530 278093458 62827292 13795129 502095108 524788651 876125333 435636353 324755588 44672045 615001879 230257173 725424875 980646248 330311585 488335884 770139069 486826728 516936912 853674330 687602389 987212634 415689908 195058086 905655104 875336930 370398767 867084911 393555505 547492348 205257213 279365386 825585806 268084505 293160514 180197265 792873155 21802198 615833617 117628742 918990594 83351847 200402267 496931820 63998094 530713851 985267704 686653514 870056931 354720967 392844196 410175671 194449952 661050455 605233756 100105055 536387385 975632523 819706318 929942889 375641222 24963530 61824626 53743379 145564386 354985139 233940643 938437541 229303688 702290611 56066282 148294282 785642457 108984900 645226101 702156902 639698751 483010156 241326768 362272033 837731122 486687315 772447703 32181073 147737769 230197810 984802480 536641505 58346684 657025149 319100745 433987906 534505030 380925370 340247636 680069416 735910508 574188279 618506956 965214196 128995241 527089589 966024829 914637698 636074489 463767281 469310951 128289591 946777437 563154070 490561623 784508558 49841384 115525677 669205983 50095505 345723486 654008462 586737009 404070170 163549962 905837754 838058075 698054991 286763123 30822062 378124406 875189983 605010340 849147713 692920530 734005581 228753654 658945358 501159630 864828142 122712638 822986932 845634084 922006426 386141002 188712058 559031336 288498737 304237734 228237318 338594241 649961219 734762131 925331250 54031388 898312092 831169003 744605814 596367082 970448477 775427876 827007840 845638459 232954567 676155552 391075340 966960147 904909205 50020697 320636128 622253698 25249687 143623060 320404133 799772464 382280413 509116190 358803799 670779149 813353923 439557468 9373390 463315142 174319598 787220991 369862881 72631689 470906345 114468695 521515123 441354821 889896570 201039314 139509632 122851136 877194865 530584971 942327635 634620422 433122020 115480114 109390471 310888058 111619525 429794604 110660521 346416289 938910793 321980672 17195438 604781068 761538139 879085179 68096209 788374089 518822521 290475441 713522129 989728865 404944135 87553603 283600037 147357056 288592916 423109668 122724544 18304133 806210991 917568530 652924554 91849362 33048643 614831376 402737419 997184520 44625979 365914291 343600808 836053124 540411314 213312597 293350543 154465805 944914127 213963103 942839893 463736647 504438543 656362021 305981863 909382678 743915624 589581900 909256085 32508539 12691567 31980628 50812671 671418909 802065509 556253576 763268270 687630504 23601304 18522040 684815023 68227282 384436331 880932182 756796757 924847644 94244779 50147299 79313448 891675257 116626753 874669692 207928256 621065296 383548065 513910118 382964325 127463688 103492017 292220409 12488578 968699936 176717389 915817601 640118844 978782897 324587528 255903466 518929752 348188831 274425505 56261126 268932465 658861835 937193308 878245573 436225831 883954438 780909224 368055630 775629694 897535976 95241674 983557949 518601271 478789738 349984419 901565595 458769777 453476435 46302356 323774706 274692722 75536096 92108658 914811566 54318992 416696186 23231383 425765096 617401368 297656887 482026221 886333832 956518722 419219528 617095757 245260904 155690317 398004980 465832885 931320011 148057307 561074558 767394311 666658578 39864295 117378729 420740524 498634071 423371516 319559231 822408777 698064237 395095326 914517434 465392154 301930670 183729971 488623536 727695765 801131339 786280423 209721985 539981522 595315496 481457865 9593630 693092751 637148181 407598609 158925635 420984543 555655916 720000193 40895206 74830845 612380839 10790286 348087720 111014910 434161801 667646951 785940038 984742390 62742276 552973823 302650895 364672945 589220146 791274431 92368709 242867836 430071205 154607046 782849357 877903052 636064910 792442987 570995802 125729442 52557947 582437788 546713985 460730214 154954332 587609190 535561058 767335171 598399475 883648778 730866432 32561276 403812080 369322821 869820017 466554355 922296643 172470911 683743652 364033140 816261693 628628712 606900975 98849249 783235757 242266684 976752300 271817018 34709670 400264453 397546460 939783968 982702241 944260444 400514182 137656572 384385985 788591591 904991742 982785459 524756720 488374525 867863086 928568799 857697345 737683102 247639506 632510340 762670365 931383157 996543479 578932057 560011868 603444454 677781306 195763977 845711137 507049957 320097346 732937158 907314410 717643805 525237477 890016650 514420600 925751658 880189573 898806584 566859601 637697667 734108395 91616320 126072191 601971480 20185119 983769536 192170934 120340976 468796227 954841298 51724132 465339705 386289706 464252351 921300510 916587363 660016327 619527998 423637320 980113673 204981507 183468081 550273829 730218984 73484730 917210781 508486993 806190654 668533716 75346593 443888320 402642110 19479265 422476863 857129942 39664383 258762750 49300875 12521710 727558976 856658524 64245841 45415032 95464581 528498191 966715542 12051944 41030870 586243539 288205615 873660894 791225046 471673695 276451074 373960381 397674776 193661854 882447373 56381781 862195570 957793966 500270101 117354031 977273230 922746963 974483972 869453964 34026064 876301198 881975673 761585039 585476073 798737865 807000070 533457006 179752407 773715611 398025301 220783276 212475502 686230915 94444169 856216899 10420961 223411595 230177279 260612088 417073448 112624651 316993868 131785369 922934968 817263968 101655752 752724549 592527282 76139723 474694864 626553345 804957273 209186888 240654735 242949697 7924752 47654805 776406702 40193511 673886767 26948354 260976786 886362268 713179268 207937307 595095518 576116580 431348901 825272796 836728667 700938700 790413799 153722535 832724069 565865118 823502854 934379820 171106019 268546488 863035894 498317234 895099832 520509518 707504122 135754567 615975567 567945225 35925723 244898620 608138735 709812489 271846974 721631873 448691109 985026241 929569179 43786626 413659173 213434431 721575774 250387839 914373130 364505924 256626725 599613550 782887393 80129579 386509721 953993411 348676066 102061967 304826997 96292249 475087836 12331118 84563167 91063402 432792694 120488889 335962022 893447781 682817730 607808995 615079653 984025190 445351587 397165183 880328167 859010759 463115965 454420292 961914950 230005446 818926215 218541674 829618996 454329960 151187604 68645068 260839722 499863669 23223386 565666718 448672270 498311222 430514187 533235436 589374623 863306881 506240677 777852996 609271013 41574758 238178342 76867017 25599947 683529929 474032199 758444465 395057039 937148163 212864757 209488340 19669960 884307323 428030014 849288955 338637282 579217617 770450375 599477004 931597638 793673760 17660073 380269907 291984981 448174260 766021694 733875956 163997492 124778722 511728951 773268504 166353479 749907293 850135520 44469777 285953573 176684070 802914242 533526963 113832232 868295350 743015303 133502191 752602672 23561668 835307498 943756306 602779284 458274224 395749661 386893273 251947983 413409733 767163179 396449316 861583992 385701225 130325271 25581483 510479946 494570573 798849986 676833425 96994217 501501857 573819553 382947789 678185926 229250146 916474752 644534509 97545495 512006406 630553052 702664519 535568073 318376901 646420824 138347356 776651124 42170484 377756981 28599106 308096568 144920159 277564773 169680560 383137735 407890043 47778394 893617681 902460616 846628380 422967457 999454832 200646588 996787009 234918973 878832514 226037155 3910076 523367022 176099001 515916481 6436425 878763519 51484553 324813325 377700694 42348260 101464448 272387529 272621592 982579906 580484097 270058103 260144678 750164656 653195837 520551073 797943049 546813517 275528040 497087780 969780973 127499223 697734368 819084334 362418195 429083233 45121488 218844622 952450254 73736840 734761102 958886679 952500359 638762006 136216355 330201052 533626618 237680803 602588581 806248209 72777060 35589029 76306311 332921737 785753684 582018500 853472809 436213084 128832016 129000848 785817216 951129341 109016423 336067935 622730026 471434617 765151167 520367865 690279239 570117772 594104704 277556692 381520802 546605062 768835050 517737157 729322466 154978019 755417959 184427398 961226227 828195018 220016426 890048890 13633106 5770109 324583741 719622267 294499544 305932108 701139466 80316759 109577800 810155888 268901045 732307825 134106857 34052211 252675689 824386095 604169983 846780393 954459138 985690784 245901806 723294187 355944292 975224271 878272205 111362250 12168020 692014784 792073619 232184445 434580025 658223077 90470905 759163765 377845343 384970449 65095872 78984808 317803559 27190024 741657048 586704604 759497848 875763904 473273166 12173537 552666350 77443148 711470281 507125487 915650284 809888438 82936026 124110927 637629061 813724582 87989529 649797080 358255717 880063147 881981525 792835741 390802575 972452429 404515857 768647917 209939229 322128081 700149077 527742788 349318104 294322476 966963743 108815951 170086379 440236908 973505839 722752728 370196408 537492471 82394566 138363043 199897261 17846943 262473969 837526321 831571525 350463497 487323400 189827241 83042996 221821276 835179334 473845570 194273705 92211542 95009839 404212933 414339622 647675267 784472072 616174077 941997742 751435814 577506380 112084120 44189074 403528570 687353199 266901833 941021041 622264116 405264875 140918301 640111059 520255195 830960973 471682583 870718692 170800724 514026175 806278039 392622000 349205508 132639960 586895704 441417050 227649798 843624988 708273023 875325064 628097060 324447100 669839157 232049225 901953479 634439628 128754650 157998400 174309178 395656482 99019440 796573294 800921356 92454092 436684352 173692903 775931416 760883286 44411594 946732140 274909460 703205984 339354139 476631320 835845943 778766194 918048369 63495741 622391181 478837743 791337156 103004592 803284842 313692665 187570169 557754672 948132292 316324818 715753072 122441470 711981300 667288863 919014763 365419007 612259307 208215466 539111909 240707074 969098751 436039854 187439213 96524562 139245837 379309703 573155881 975091780 158075896 343720601 891103872 632983429 822558344 534957379 735988020 478359537 848650043 923558188 888630561 649298687 92399358 456899984 771740156 804380657 124188846 543271270 169799663 588964504 604003087 708911572 829671578 425618189 144951425 869627142 522142750 136713614 248936845 947814983 964321745 259529092 144051935 707941968 892512520 966610278 95415698 481016892 297486167 944065741 257091431 38633079 445880779 349490788 495533062 70137286 153871444 472238259 613408555 176187459 61202763 69927993 885099030 743390692 495546181 882566806 465534185 17688930 871796771 714471029 818020264 836118515 974000121 962072199 396576834 719028992 781198828 491992532 200045883 78684994 288574624 457137314 117318072 734455402 806628101 465367485 804592687 813015897 937605744 270517593 989203355 851324858 340445585 726818736 447231901 835991765 461901893 912766085 706197046 333698664 479753466 524217310 22333530 306269938 338805860 418910364 25298929 120004687 910902895 77861164 51206033 51993870 534998477 21040456 786449271 194142929 486407941 591041957 7158825 276530036 861559549 848878531 127854893 54521485 575697266 575086793 890513249 37599159 340369229 596710294 223814174 820122694 973443955 98664055 126392631 312249814 517574418 4207912 284770853 280993664 82069075 335976885 332987533 617067551 209533692 119436803 663726831 695941632 562995111 523402008 972471667 277071011 372280538 952842911 331592495 800494156 380446055 74622095 690609666 720815284 671332389 914423839 540937977 497292695 13087893 519846960 809542509 383178663 524054871 94313361 516688678 606123945 282806597 849676211 75707847 492340288 821629365 739434677 40798272 237140828 262836684 865786290 366728190 487633574 818629201 698320685 288127729 51591607 772942779 978737394 772406890 296791519 745677584 165861219 794084214 611281828 685708178 456143074 846976842 209763048 402972786 363665520 815886992 538295734 65858082 891594838 30636021 740003798 483545866 923950644 977144625 746382550 789736934 196389167 86532475 460882486 894709851 374660203 512474092 520168981 205913948 137397334 669476852 804107883 303258552 316077417 267906062 988966729 772220490 114882904 51246128 27709627 331064775 867133119 566005360 396922856 611244308 449157732 136926653 94790173 225624728 966587630 693689074 15361661 15493148 780221548 328760498 910202998 7398102 693750941 282888330 65828401 831148274 952365181 869936283 134406825 120958949 137842345 123373553 893179438 105241600 27136032 773405416 436306374 894269150 191927127 833229229 358029809 641084859 822672233 305336334 866709586 641776214 851541759 734587598 657269361 484279659 915864447 419988710 491677760 609615387 555393392 557506161 293280013 360274924 279958795 427686837 481233873 417801139 403576742 226929662 523042738 430712773 335078 959349111 177498275 192262204 645094691 388044435 685863414 320283276 693380768 405089351 814575841 397438879 139676948 324361554 881718537 908057746 744350263 225912648 370189485 152260006 783418808 663469497 512534930 63377603 91156333 993768802 333695093 347249426 220698463 709254183 630478551 73549892 521119645 807976825 265812096 18730688 48537611 951675509 339013963 741918379 209281212 6106155 139357257 201474511 330467708 873592145 109532257 74817971 99504792 479721741 79594328 735439952 143191237 592129257 651333906 86863921 585898058 985028998 286629699 659112873 546799532 917108249 732662764 67919177 577601425 998474859 86649864 626139035 802666720 278180178 220573765 11947931 284286332 212447373 65938793 614754040 86039517 175471049 542088362 38060661 507709141 621682689 773500612 503416729 213811946 277350869 442797002 652226355 114896218 729426700 311339227 661695750 499051300 44001991 729614926 929169076 894993201 668781141 407824462 550176272 946961318 628398227 414640554 231247649 693361951 480579347 846001688 631917820 508566747 240606401 669978480 16275888 862289090 295995443 519692616 76101035 573346311 962489617 580843741 688242528 544432668 892182968 202454629 896000319 788701310 932069554 825169394 536210862 453367046 85510208 938903486 400328363 713908434 206060391 484092364 259786736 686639737 182610403 891704555 47722836 423216804 414199386 63998723 285505893 710194828 436207690 214123279 136057490 251213659 794967019 676816370 795646326 539666338 879270998 544162997 180883999 663856904 221848742 569611213 117223949 307358949 508514698 370068664 21267382 714575088 854161027 133570470 253731177 36771429 25275024 301454012 459988232 439474410 217969086 598010476 2185589 654176775 812133754 138243079 905390433 459617125 667575800 553553111 851799814 546846797 97716107 32683813 63220052 319564848 454811377 180444001 626923797 963326074 550512664 500707530 530417513 257190042 634277999 636665041 293961470 512069375 938119052 606466054 951543784 8604489 204476529 806245724 662781264 869126635 797005154 568171696 181260111 464580953 121724806 33059924 863944102 71957264 918260088 927164153 244038464 373071464 107608153 870962260 188913889 510637168 224186141 571847754 767827209 710980492 208512794 914305031 223049866 999148198 520771084 27110001 7752686 577763964 833355724 670533949 446890598 482877230 91221997 628150708 947458182 65463154 513726984 663918635 137420418 431987071 591082788 233975233 657574887 551207292 104937492 846488775 914360812 181639984 270852880 534704372 892620475 479365674 449009402 968186692 331030223 822296837 995296692 338782908 400060801 681168768 861833209 699467750 16562349 953055205 180134810 964020530 871034710 693861793 480455517 860971479 125848863 71538304 94946711 635940101 475261947 52400554 334945228 242139110 86556890 605798107 776843482 979177364 85163780 78369235 799880408 268710354 900666072 647693451 607493262 153243224 181378570 321842822 852710973 197940918 127414378 32845782 14477800 998449087 726707574 494933316 859420566 705072789 418987971 806883628 193529241 894249917 859284182 528474468 136389027 945841071 134272575 765748860 777534786 71952706 844118094 429931545 340663060 744784165 77624996 800672673 898027388 259003565 122515494 603254713 456944483 249929871 636100494 471422282 100895309 215324420 966355597 960315874 772913560 237859919 619715854 966442800 132109835 331516387 494917268 121015213 129873809 481706194 739280424 907408594 553658899 583398518 189856491 746838310 180699034 267481486 547510982 931242774 379001402 522542827 534497486 835945884 772472697 23114331 159884517 873368006 90955102 978756465 686200231 863868661 216616383 158432436 830311461 201242570 489948822 177745080 174774134 619822630 659451273 914054558 379747576 65626523 349969427 569604066 812464833 383184812 837085551 212492166 314427585 68603304 735034993 701441422 904549188 360024041 724555753 916950056 85908398 815510854 895706521 624624981 531895867 964839255 783057416 214723679 18598176 273006238 392468758 193372310 892828867 904436382 959943219 125092794 970062904 162428997 694696859 635044088 545613808 384298761 700052606 860041393 452902065 287603950 413999166 209967604 647627990 138554918 126917659 586052740 806582124 875140531 210677720 190994342 839979786 993735135 405718020 858577961 119257724 798186777 904466622 864602943 555139510 864409840 989695736 377718765 26838836 684392595 12762853 424968996 68691355 565331810 137526740 374109771 852935759 551525905 584077374 353080100 542597175 710995033 939132839 201695650 438651915 2326910 392689991 131148052 996062045 798408010 989726013 967836120 449111138 746708986 832439062 4250647 463635178 674651150 381969411 342990365 211560096 247248615 767959360 132767802 812580424 905486099 506877573 518032534 457012004 90954946 871112634 999609178 654466330 810245472 53821179 93118245 812572382 446511169 224266296 661150778 244919178 66508660 481503249 694030315 813217646 166458663 550797313 129369175 841109812 932766723 472359539 52669907 32531690 240318899 185437708 697628465 145804997 692315280 215660999 455333352 635786578 86773632 307458881 290252907 749535455 361280059 235887503 414624188 807791227 460153799 928291317 905226756 379178810 409794566 451773422 44912807 576253228 2570734 174281981 269879391 787853809 646641520 322549297 820385498 886960418 360503356 370530314 885281766 52818636 586191312 193131470 541121565 525481295 353106702 831374471 127533102 714386761 67261974 394673641 374694339 379932124 322964958 132437447 759110933 585275875 584210868 804023740 14045454 586781602 978305720 283924844 227151762 477463591 606474140 47537259 216940360 966977495 270583924 102222126 872312482 856775236 147869947 265950398 234772882 500976648 97324869 214822335 67879760 17103194 609495976 295090451 249551669 932460933 427527897 861178953 370253159 11738764 517719044 384298612 451036717 348541116 668223455 678188478 826004706 127213946 578242088 42945066 94191440 848826012 997683543 819020274 558117599 145553489 84970671 792890480 499046488 34811891 7712815 419442600 904431436 469725142 714533050 6499456 254702426 142060946 867678409 624955584 6316061 237913804 9254195 457352778 586454919 677477649 135541255 412459625 804691594 713783343 307921042 751399385 415125706 305604584 422936010 973243304 303674424 360423033 618650135 655237263 247751275 478879301 74679862 4699063 948604442 789212911 11198518 203306867 783790208 731393278 828262450 790106269 969307082 690032996 247459046 408278352 220026996 235516652 820737976 24718589 949299994 128659017 628634326 216942051 286779952 904086687 190185354 442970727 117026071 808835489 98207990 364777346 140231141 25404203 221992760 88835583 814617114 85707629 144658801 450923673 817100907 972921251 241029941 638924340 515470598 341005338 47202691 735497594 576521990 720457019 612732534 378338335 701632387 93883211 595280386 840928691 997969898 785465739 283899417 114995968 446817579 234623758 332289665 587048720 260027961 554282424 528400654 74645074 639990053 673059454 378085098 309607311 498497056 619115039 948531650 13967654 960120376 848250692 749465247 389158717 421224062 214714132 767497052 975372801 308597343 362777437 816301491 306567240 759527 952717259 274079559 300093458 187341017 606369224 887142177 447368977 160651647 268059182 374530402 800641699 941118635 752615499 110249009 439615691 224246889 911297010 306099696 36883617 612064054 55564942 426042333 885804467 122795425 46055736 861177267 431392767 408833172 529995109 737960006 262109051 335228720 12039565 562202508 522569736 470925140 301861036 822455064 631576786 569920217 49501817 284734837 511038851 802117315 247500197 803170893 878880556 11313559 109270588 915764172 475893964 17351881 194322856 361698430 140147306 240378592 75392049 571540072 501728115 457903509 162016430 763837165 793132228 26572346 326039672 168218315 497497485 627900707 990673378 981590622 50337275 40175194 118841810 561376126 694808861 366342007 217063370 573689416 230171917 326333958 341969939 706065880 196202190 388809146 67764309 336349495 629187737 995672709 760405919 130915852 453576218 922422348 747269368 99224797 801511045 73309040 267443112 151524881 553726098 258116489 133115502 604063373 150808035 251957312 17955850 845616895 470815670 235019219 271822662 700987586 413869528 613792600 407053465 610071718 2601745 327334125 946421212 484305834 175523186 559343482 467738037 629099403 334282181 67523756 728324199 135793225 140832795 995767310 287318105 547075245 106400151 272949959 3654969 257208185 524907270 21610818 102825079 995722939 109146388 227164092 549226876 523015916 840956691 956280340 133087633 696074787 136130816 932025196 32896972 311654001 343885030 353151360 793269755 678167210 420675116 374110306 813960435 414024262 222393967 953794891 961099506 328794117 226744849 817270826 438518653 604168470 691397995 393860083 452407760 800544383 621024174 1634635 176076650 314497216 810431326 161680634 10572003 946562142 946222181 895985326 110732494 290107210 249136686 904002249 968274420 669811801 130628906 634751206 83836062 353022872 441062448 897451920 681816989 667807297 567239097 120335641 124492118 258637092 366712076 576899878 911697826 987736249 578534512 87774475 302233465 241482190 101971460 165321819 40560683 48193640 61307144 151293176 190817202 162960181 907811776 11607973 685288333 38440681 498875530 621640747 391463553 939937977 371609018 925796893 460261625 938848114 898648885 584753743 50001557 265360960 161653620 961699382 105613561 592704483 901990208 407847025 834186672 3961667 425685195 874747354 904671659 339508690 26040530 948005212 502468871 786368657 959613184 40273555 824809338 311005065 661914301 68789242 250943041 33523318 994586134 711204666 972371432 745751370 148474760 22372988 11112330 310128379 836588722 116725890 902832861 738578929 377089266 589535885 595056948 802774460 464283238 352244958 142283149 342840119 152766521 497268371 129208776 112379704 537541926 806534465 275901120 51972578 727840058 526844160 85495896 574942543 90565177 910383679 320693912 239039936 785273018 184322593 401684666 621861739 153564834 157033879 212957020 383170451 746569763 660530319 38461262 63369352 12775276 33260763 406209471 18058148 530529133 387934598 130437851 920587410 46985414 258855322 972559988 774825471 785699481 58055883 202284365 728781010 820955913 522978276 967820945 606228930 559817221 222021963 80607021 713382054 379055841 146080392 96552505 125625603 806610710 135013766 188994954 671902337 20790880 447720776 689960484 551320013 835655373 672914686 324423774 735157138 931770007 296983761 362498960 569985839 207555995 564783324 298766848 28511907 87761600 119104145 487257189 500095172 341126107 420380561 65993577 720181947 566460952 15062433 698323901 373071661 2592551 887318854 44973997 23383430 187555982 587450832 574703442 23211354 260365517 899127216 610884844 44651875 48627328 973383803 614637713 108699675 538167127 913404561 137211581 478445078 885025057 476985121 978540249 78667515 897365681 44533825 798849461 316342984 59596258 349689713 689414644 62188808 89524918 586904992 85572237 277080899 26872175 512792031 152808605 287237691 264435598 763693448 331889565 165579277 737077250 946527278 274278951 127760728 712448190 264006884 458722157 449989598 740992004 289778757 528657112 490874037 186828934 180022924 807217020 98941543 529712636 349148016 13646702 619237553 788569359 99218938 896318452 815441534 464527320 49127056 102679224 581479269 812820503 287085141 747058546 402414104 86128770 21337496 382691184 651093311 285344379 841413340 101082908 878852735 131192097 629740019 222243123 318021030 809762942 29460142 416962572 191991929 231124509 430609273 811229481 19693868 382344562 707547932 687651753 699388234 609191339 642847328 280867502 274528193 929932468 27926047 676942297 868577589 901779895 59633480 519670899 39640625 753563171 473270158 918493359 884755267 103010176 140736481 55292648 765289469 22712975 324771571 957281397 106353835 755380843 621027230 126047702 990241757 181091513 666215806 689629990 790282852 309063134 823013843 64811044 91511953 703456242 594269692 960089542 605236136 506419523 332276792 644876760 259982694 805546950 415886471 997254312 761073477 556622951 52546960 378879298 431852277 229834882 188677046 538206112 985215725 809704275 516770165 827973833 990795788 182985971 370120174 633594991 344565456 193134016 698406034 436077408 896590257 145192078 248683301 354342744 651611600 433476445 851735856 911594293 91539746 267622326 761364957 852613222 676761628 666428268 84008871 108613905 896263149 125202269 646820016 733995225 934906543 16106532 561969057 778218682 199092502 932089230 264330024 543657957 977739598 962736058 832251717 726846206 107928135 80935017 81188950 612056086 366927813 785441157 376166731 458467558 53063482 137531687 163597132 582341461 803959954 247606002 690955365 552739454 372808270 190291732 286734679 160231165 206398264 701220087 790966198 258007117 485825669 55296222 801665074 463565266 870548631 486433142 42927823 830993117 419884510 124116772 443049202 786812323 762074280 819215932 245279880 667654113 809263970 408877011 249995574 465740275 508999365 793467290 18479729 881807634 983759022 157730759 894555150 42673637 858950845 685521348 300680753 344776513 593333921 954862178 660858130 463882551 441295319 703785953 147392019 861179829 680419076 590441220 500508503 442493356 262173504 745788382 110147468 71437473 7181745 212659393 389694100 516181109 6126683 408173828 250505094 842402056 565904586 145060244 737592044 277371782 683097943 38272796 622148295 128948215 845651326 135522776 592830765 139462996 839308728 740222783 642824 519727804 183180354 353667678 814737511 297870209 99456060 777401330 221824034 959154156 990060723 611518133 327851616 848703757 19691960 578356709 543622164 438112897 575933304 133730559 715484678 111547598 24519706 190149324 240495812 870171031 325672100 685842928 9634027 17497179 278582062 862793202 537224982 461762416 216460880 204478844 759632624 168433291 981880174 981456657 127587446 824457248 445491141 307955413 525677356 317699452 886312121 69299519 755812348 314761777 55546429 323813378 278825726 80066134 366479053 519321538 950237165 692151152 57680817 959871191 709648331 336262879 675180744 99389664 798025294 891641623 303868508 410174269 912591265 138265033 244147278 892695062 962722280 689638418 200650474 488399635 7337870 939478947 410215505 615666569 106757075 465761933 791996298 385582800 545828066 158475351 904904337 348581582 703142854 962585154 160969124 265307536 151364384 836149868 364697200 949389677 580307842 521082059 212080297 492899107 659347091 308743926 238110520 622069370 998382344 438760994 962985356 858236565 230756292 225717212 326419485 337513366 691479144 118415783 723096165 89823561 129407485 480516854 438405143 832550338 295618359 599374266 97857874 446982742 288040485 315071425 248888770 868348327 836153483 460969066 213763785 348016925 769712992 451874304 970086294 620611687 890635297 785588001 331364603 121391588 11305212 510300439 311421305 555300707 481232573 34517470 645124267 610640057 515034323 936045761 295706747 810652681 387936379 246080972 110151774 675976863 413668748 359040543 544325189 102338582 820009608 758088973 450355506 442238951 62479629 272958151 915366989 953114925 58546151 99247943 927022865 69851362 609548382 90960521 477668420 90780954 125477990 122792686 553937363 493028664 911354799 849644109 156197696 299291177 948241432 266349469 975268039 361910179 625390011 372109580 464248760 297915971 982714904 914604265 740154921 45194532 40078767 508038262 850825809 98624917 607286204 630365025 20992630 216834585 721325545 498661049 160131891 846803535 473970086 714069253 192348550 237841236 416229713 348546246 537132412 364471144 614895714 364916803 578897674 240285725 589542734 43146433 538201695 572257637 810267049 130872967 469968521 850345815 638911228 320794329 801487083 98713784 951159353 822479712 315548368 525001249 173657112 475680258 224321135 500143549 42265862 416669685 737984785 458495574 765215930 127633548 822966717 380111643 492550350 254380742 472913719 82093083 150043526 11115413 506867072 960310574 994504732 976835592 663172740 485932311 150146272 317176174 584646094 953821976 139655885 900194462 478823224 165829348 228391071 703144359 665972897 270656933 119814043 256474033 729152506 737546324 384107580 404635575 117657966 876657930 659016316 443088037 811267364 809059842 306719801 170650787 621886767 301224532 2730 137575859 787156843 2665353 454752032 224319288 956487328 446924269 124513749 287826904 465269968 205421172 990971262 131242864 328594456 963301656 240233248 57746961 553364331 624340828 314898887 523538648 353515109 826431555 966626684 17298824 488007748 273346485 187949611 109894514 427087368 40468692 99986724 66760562 43134045 407255108 291079850 999621372 854179376 268109950 287448275 171965695 473531121 130935888 155724911 802125576 946753895 395958158 712388889 500118225 20298985 879804127 23656873 373814093 706235681 842799908 391112917 46759780 116146392 431578879 9170646 395750112 472047570 109157369 462510673 515181614 516412476 753590522 514802986 223108203 21700472 654767612 395073898 347747944 785703500 550798808 2389872 584973746 946756965 714778760 85091971 819572302 447099238 961265195 45902746 5851271 656581454 437015662 52611050 625244198 868594540 61781695 20994309 193158462 170939064 483504981 708340075 539867891 89611855 75659412 762976094 111312326 730427024 10566343 459060269 368646875 413881502 461450140 953620620 213154818 28745251 891228942 32727119 475844489 705010488 78629865 481695759 361591942 368161878 534306808 986836139 89272770 596088503 860346799 282431231 619543918 196368131 990771305 159411808 285979985 66430717 774904253 397292310 796857740 785470595 708868931 18020966 51868448 22835422 971641585 265023266 51580673 862870527 297750384 379941513 420397366 228896600 861637271 781989307 597058478 248460430 621341797 686331247 697065284 334204947 968762477 316609201 530573078 959533781 328537361 816553062 878480849 103441613 66361724 527854940 741428560 775230654 545875905 793297007 798066075 517517490 58320272 849646747 232904368 208587008 82104611 653301733 437483607 943741881 287807392 34542084 44718663 761665540 720873330 741783946 95870487 542152158 910909499 626443564 354202291 239446859 295512977 232683139 195404823 361874700 760538079 936833382 137105353 158930335 730130389 935171428 676447824 640967012 637334526 761868543 849554019 719439137 267686628 287037626 515697369 555494019 174096061 412932383 169675910 894969391 7232681 265546396 289637900 918142179 744506311 643840190 10105389 40019288 876523329 205510211 401893987 489577759 142343593 391515692 648508093 724990333 179203471 177472269 365957344 816537996 939340811 68027715 388493484 59543790 355065340 756707205 615037808 529161400 169639587 784713718 276647142 176872267 902776465 566285042 95014445 647282776 62641583 105119833 539818415 939164911 163146396 941712401 281259021 305489988 185744444 782283466 30480320 364947914 959755734 248954015 34002262 751612896 316981729 422495745 811156686 524563420 31719301 278710845 53724820 201358888 915940914 182888313 230747506 818717379 601689706 178278303 318516506 664331289 135914487 858334920 456012551 299060882 652563672 737271572 604550869 838308116 372071389 487547540 55772381 184343474 589017907 89774642 935956369 905999635 512270387 599629406 283079407 543989687 730856603 189320578 597864926 646797516 372208890 828612432 318031246 973898596 6890734 489064103 490746236 142805220 199915374 946758786 441866102 852479046 536546709 898933322 543303513 908618097 238997214 599075893 92961570 828015120 688850535 881434291 586531106 53637273 333580048 869610512 450143311 64436650 58931089 48008237 563750518 283656331 876620668 881781763 110071278 736027753 223362218 600817513 878832972 423277591 547576298 173215425 128272988 84123007 72148747 671576500 845257455 163662312 123168745 938219025 991677431 664535631 672169667 578208536 718172903 5749714 300335400 20832565 70186364 359266488 68840801 486453233 642922818 797977820 220751347 752994095 534005572 444113564 206327959 265354896 867391155 753904257 291086672 995664142 690543615 215751770 519756994 388317421 379414081 642925738 179052797 371091511 159977720 851222463 801816399 878150622 856972177 102151798 898983186 779674892 313934637 820340339 118644476 956857455 618318158 339395822 562367901 4840082 783509386 768695860 122711329 650900540 375116468 413798000 499081033 918176434 629549770 18838026 306493854 8963850 514280115 485546651 232571713 674257834 189285465 34388111 404924807 46257641 136539908 156424345 678448884 302990896 976764683 797093359 112364702 447599192 136489181 674732603 452439273 772514918 295944814 575150601 275931809 523577633 988948601 775012841 441754066 471014722 793850867 600764271 479978571 160647333 86310921 712550283 834905167 128112738 599454745 239829973 26886730 588511004 396254317 705335614 891501900 225535351 354945324 3866601 673134543 343950856 531115555 125573815 116465773 827060368 553240768 244913933 203154352 394705720 19926774 644908417 865720441 666293992 98189040 198215363 826941324 37016312 763281998 661846490 165129049 362736742 754192815 192015779 951247746 2963483 897351392 695265997 228498834 104813067 699132597 901633376 301280275 82764504 879723542 270262399 909824871 285480661 515176332 112979223 680186380 535103105 610403991 398423172 53913448 708593030 449154887 880854771 745609342 212436884 395217613 910738390 427689977 149410427 102754168 231454074 152373909 852621911 926720070 380872742 809951330 478369019 135022469 111231604 561133522 14746011 381494002 323474744 300226671 896670333 288970318 832929403 284289789 899374309 83868926 338203236 460483690 533023812 71574359 58609383 745460695 466791971 821864125 25667024 616202397 777134644 257121097 621092657 482272907 183841167 1965399 292224236 662210185 136987867 255972191 75860058 4250229 637466192 399334801 156993252 386652877 688305119 989922654 523459017 440195779 73791579 861662253 900679468 606815391 933236611 811805203 204792437 252544933 633669327 230459460 868747329 263320322 487580557 342356337 745593228 523938075 196838087 37817463 38664611 186342306 146306005 114524668 190592534 783772197 513859468 347585785 22941425 202164586 190024790 546400441 642360364 263816369 260579045 395556184 723148111 46332007 59877738 927940547 298876939 693547064 10916359 20140619 956867385 351013267 362496956 554976965 874951341 559335042 445310779 913615951 745677347 591616784 28140618 788786233 227905332 542000085 136372017 250846756 596681023 178913159 649763548 91557738 442729527 910342593 487113921 18393989 809190951 546991658 946334535 108067890 93055073 809767245 980724860 902438810 160780511 195738167 457415774 35731851 755073209 902726552 801864153 353266907 346859687 830004770 142053139 574765018 224521207 130941508 825611773 821202229 162371018 327891673 912759966 605100544 90750617 252390239 623494532 899941567 651898248 422345418 860525808 744953321 84629015 841250668 499908482 245409525 36988834 957324255 133657728 644578394 712567158 935521880 850361653 59426845 618043002 844931143 486708214 695080560 828389002 164836339 368799140 990760019 492728011 134075457 448376914 583478627 386465695 71871445 483420193 38363943 346733215 196462353 635833615 431362229 37713020 135742096 529288105 927218205 945582702 662945832 424312951 510666211 450984064 127190955 422609407 921543417 972122097 909317621 616623976 800511099 74153959 985423115 643787469 419398321 119498571 92164383 2876947 358480618 16552179 338813491 249360912 215801745 535275843 737710878 647163973 425505214 725969325 28968430 205239771 524068378 691914261 629552721 34734588 995414676 756743675 309860347 916958092 581382123 71694319 386098419 234409573 998364629 224037885 878197042 417762949 196052808 970361424 273156247 407049777 839429954 611969737 656410688 55231699 147245580 246637917 554912023 572750793 972607241 583880452 777990563 496675618 128311065 260059635 383926557 123725740 869319661 546303255 893200184 450701784 617997573 131814954 685111356 468878553 355852839 415824749 886641501 404421998 238702524 12314099 811471774 78132478 624283836 320398813 133364176 771529415 567036729 540792550 196796559 539643969 124673002 827303474 888835938 252984066 87363108 125278846 229226157 809199121 671582101 122426340 112417256 142096025 254241294 797528611 610974578 462610484 65869712 350132430 867032481 304572235 362446529 678504254 382704712 986730364 998903066 368585239 610776130 418456146 909377789 807572688 958100114 886567142 487392513 699452403 139551207 427271973 824731248 221293715 236471093 496313348 343720055 348888348 638409373 450477700 998933310 101900302 913088183 64803021 452032731 780120663 369375256 814479259 311141268 604596319 801209622 162560685 973181558 264502103 581016830 735075698 72074791 391633295 474159191 411983655 91085697 466226749 839255627 768333296 687520463 75726719 117162996 31240517 277131418 755572368 334234568 128581080 857472669 247322750 193384100 162021751 879959764 415275707 976501010 43617383 19872026 630226983 206178067 845569935 894729086 639711248 433161984 819320228 31344542 907321174 231303882 974946590 373547922 70559509 595796238 61068384 998802579 712959233 944825253 128450349 321047952 131576172 257031428 31036972 378898922 302931879 193058722 111375037 718207586 169559731 154992420 738079611 799786714 361170486 436165897 547032151 881734 869327880 366352378 884742627 776649053 450172611 712205569 2713326 373248471 160518158 916298061 224567402 873477390 713639665 353017750 194525341 845215837 462565529 225562312 76631110 765497407 418621033 188006146 483704992 440697116 342998565 74300954 93000181 704169051 510466850 640032331 557567136 232311081 6384708 294826114 8960133 309073670 859548034 864189810 682322141 20066191 780487871 906889542 893543580 346643887 112423643 940585272 191859723 574989171 18663935 268490832 340486577 437284968 456496978 676707921 877982083 799495542 751008874 970982263 356180944 113992076 463530945 766264431 346303156 322432004 61090545 207779641 631505673 773154930 71969450 313827813 793221121 704973672 73233706 539281052 51617559 185657348 332382676 95993633 760646518 351046610 217000817 101133095 788331577 673497794 630357367 518830011 325509687 233882592 342328625 534206983 347874667 805859569 300471413 546694175 128291572 214078309 754473815 612313597 987233239 678959616 926141409 632970711 236449640 999375115 24768114 140583550 37548814 357150789 89093534 798195332 708197399 306094350 751844778 349045327 979592143 382202144 720391690 157618182 616084735 62720314 691825164 816475754 721096235 844812928 363169928 701904158 58891237 970160094 166734106 898640827 501636061 92875515 384127889 738085700 944766981 261412354 731185601 982315794 618563143 820279135 633027477 179276893 126373484 384872254 380838571 958481979 619590749 101230260 116100160 88191836 16466926 660441675 904667589 590079512 357770954 120353868 144500021 269178542 90513961 311234127 20335720 592150021 256625993 404463608 182752073 53909325 665875962 913937673 36225118 136955456 586733159 521768947 168748700 713106643 906641200 549587270 524104973 378748301 650817530 492721484 466940136 519800807 5679510 371607724 109880318 363450463 491961591 254380338 632629005 434991903 565614464 652964724 27141923 822240456 57428332 62410347 876149780 575820645 828864372 764891250 565292452 415597530 139176548 734041151 981220524 45817747 283628420 505325496 277082399 786962301 998046979 744022534 306763107 3726488 115630257 269159776 219693303 460108199 523540114 852322307 895100101 941670929 505287030 774758376 616427737 415231713 689685074 345093868 843568709 518549445 109985117 408861160 786663327 101678016 142902310 767883850 12115 279047082 125725698 277094513 66009382 976289028 21117047 225288841 832531868 989263655 494448616 52225170 301888206 870505081 904547476 49504658 812176010 262350857 824263033 281120098 530098922 366464459 626213965 373667630 885013903 588715434 635045142 524193581 690393449 630463803 144593783 690405563 909510884 270319480 967500076 828036618 99124859 988617122 905841810 931656726 830397128 252806777 983881895 132285333 123311858 740945722 181789991 788004219 855812931 858569375 69124316 385911852 225033833 695338280 612095833 962564088 136570065 247140974 486757668 826963514 877604777 631351450 517369076 639632012 754187281 337385503 320184981 853312140 178518976 78543142 784968865 8916104 331349919 621367112 141201436 454661776 214829185 175507778 95182346 70642115 34077153 164306661 309070318 111627337 712161292 921166151 74191424 848731357 20823476 413465444 675694870 750944604 897333245 45580297 243092968 651520526 382965800 563277948 357349017 561484775 641821090 142317881 422917230 973171008 616201344 416635018 280349135 683546881 592142795 375531480 606705347 478736299 392354492 915775665 442879988 104515783 689458167 369587763 953247139 562797994 783053206 481458360 313742598 532902803 379555009 556835565 36939680 762520808 972629864 394288696 176521934 466967305 389122928 599439164 292654664 5324272 16074181 573003798 541387504 460733327 801051629 148092850 791985978 193406120 916384866 234865965 150438255 458359384 604453727 103685393 21157378 240023285 437660105 187416327 772926087 817215113 744251891 809865766 432252272 569398106 56670813 461290557 36365411 445793740 60729720 329020074 303634363 929320252 754540224 845021866 242569931 555591852 993114716 34555908 601514324 762015933 121938224 751952578 220375317 578908302 708154322 94049046 818931586 145814426 281465372 444374024 815545890 25717262 106756141 100314513 447631719 163426953 561605070 483997129 609220693 474851141 665533555 912855055 256687745 420073778 610393273 351774027 828181981 456024340 238846286 429696304 218040272 360784509 34165233 290931940 939692810 742319555 384980985 611140748 740650332 666446356 908031123 408712574 544679969 14787264 509027086 992311688 30730568 923148507 328825168 492467612 250516000 994358722 257839019 507203744 266948851 868232291 858977770 95130832 324256630 97824055 377343487 394813253 311124915 411508720 685745193 103334076 153828274 70726177 566991175 894478605 737172533 475022298 155707530 134368853 342325913 664734616 126680540 225572832 440399474 455505708 718040444 690915473 302380781 975879462 50635568 569329632 844111752 909613337 664460463 20884733 859953743 41803949 415697985 23595009 305829020 101443177 126929085 459657293 24685706 546436611 206652250 614374590 21458908 362359779 748743442 216301172 879610746 875423982 441874004 320010220 183446041 12430799 10925692 485826821 988310260 61561260 55156452 684938363 823690948 572133266 705823095 536161043 466453567 974037431 412272403 772282586 927996960 391717839 84456231 952682665 938154450 143624832 419573606 812129709 505984610 168317047 28430881 238111708 896257380 322821236 558121927 79703420 335252034 421563970 418046593 176078645 335641581 325719396 861017007 11848881 750369014 419356453 400526275 69338932 393393883 812798677 841621517 173907194 204516516 778594099 126589858 142670965 922218930 398679815 807317025 280719892 566996862 688264257 518831599 315770593 11085492 76953525 247990365 198853877 351033846 666036957 374932521 539191779 844272704 88465879 551040659 594641717 507822331 951566933 663980648 901216214 616881961 358118517 75123407 821398476 136712615 54229617 816585792 911447897 305425783 476419169 192167788 872422644 164683425 710999386 40709589 28285269 640469262 288699953 79655497 844019459 954736909 454588018 383211237 651525964 543053896 786768247 98684033 50876227 590851531 762664680 804608792 207733492 973299548 732248550 881648319 962528515 638994518 550750463 873976411 944420301 27169631 918660550 669359296 44369407 482176287 710068884 72654675 122645548 998768836 152310172 819181358 806022096 459414541 54908947 310064412 2468436 841677193 408748444 905861014 432528724 23929475 562986157 492778567 997229023 147751059 374426885 959757537 639261928 925177347 686250299 436198580 804863329 457427200 105557876 849232736 939603486 668143111 921887410 914765385 519428299 926713933 733946742 177966746 386128473 788855688 488031157 241113261 483049233 896779600 999490626 915577956 920709075 414993135 260872874 770454449 562744193 635299758 582728337 54522472 412993457 121494987 490721052 70373137 578922186 448795279 919605872 518525671 116938389 694009634 285807407 488883039 620723566 19754148 519366137 859368391 661126188 7397293 100481651 144175420 756693245 952488628 912269727 529918671 367481762 25658952 152889471 782742306 660958709 735617807 837264778 926468517 857112793 327985829 996841654 436034978 776781107 916447525 807077000 746235847 462973510 92884406 87635238 83697076 965154905 607001374 795581818 478797444 466915018 748579820 475489215 76124614 701068447 240275293 458559636 921066561 265934244 611449106 703808866 926892953 347066912 393589995 705877821 56696056 721575823 702719474 492731033 350873281 471683351 152324384 949625480 934656860 245208789 37260717 870870287 62880046 496778442 518968456 541677489 816209811 267548275 17166704 892334425 821133074 257441996 203410412 742199634 523376240 814859518 298524851 302785544 14442781 692114846 8663364 71138837 266207020 563899190 563869869 469596653 888098892 716194253 419222132 675272103 813919393 308999200 398658742 876799438 658293993 917627197 418476927 474503803 37691824 288159982 219354579 858824897 545601977 422764991 453540882 921494568 90140860 752065732 76796463 104583640 296696929 85459827 175722476 415420301 501875368 739592345 885016953 242490611 308302949 156755436 917762713 122222341 465754635 316421454 851538131 124048627 86565003 122531409 451068781 124256826 410691390 522939712 983081722 956293366 945704702 436622603 730304286 35845561 41204686 807100748 140429200 190417967 745076926 168668028 605838267 99468645 908260372 490855219 341959255 69079672 647610654 259721968 43818364 965881640 428659773 895356494 942446618 515224775 17887902 246031750 639481600 281095643 768971461 622563321 89905361 567192514 911702275 820209646 455554426 952906961 627310393 448499978 143324927 224903671 617168005 601679545 324372315 377944728 92534763 666331570 447024399 592661768 926053537 343359114 411059759 207229661 91231960 353506376 722454436 109119861 599538125 361936035 242731856 221025938 837015708 332637216 788218451 748717982 152846861 243772877 554141294 632673605 692272854 549982572 857577275 161957210 4178468 181949590 539901937 96713230 848281159 986926335 541891349 626851047 182801800 952951107 834080707 274033759 158973834 409051494 235669972 611028311 770987529 478401827 832054248 460519588 811039042 620272698 61753921 963885902 716561926 615895215 449075858 261351131 18394138 306653133 423308340 22572606 341119074 963210276 971802187 41916584 802652962 366209888 668767630 985454762 171677346 355364688 259488520 330651180 764416182 495158491 941679490 387920062 973560317 626250089 848439649 637115710 99039138 910193569 453517963 815601064 378605135 902593821 76952194 249515625 61763305 500260534 272088230 402882378 315987161 96406768 444798961 118640123 462616655 113566590 104094884 634294001 321447629 216099755 964945180 938380162 563774598 759141021 178816575 389851266 237907461 27256223 26966976 336946598 789966144 480484938 152547661 21087630 235595110 82016207 270603254 297358414 582276740 395207835 700240791 898263900 491614603 145039751 869420374 954231257 111122692 826031609 588525257 285086673 42131364 405986788 223466834 458422313 17644160 402283409 848273578 255551620 282055983 875240553 592498218 924538478 208241843 597562230 945626108 443836952 679578436 68745713 741195366 114371527 463953548 293952508 12635427 955568150 438992259 734572152 762315758 402631302 560603761 203357367 687717974 455251476 609344154 911184808 913673788 479504666 165984568 614463717 735056285 300556902 342220622 180070854 225095380 550462464 777633084 23237839 846815767 309727871 91983551 440527484 424099398 408453450 734479992 289251176 216537951 25988602 23823327 978853709 428619903 436943439 34727427 116337877 892194914 644071580 880039036 658385053 123576245 46023603 125365122 711148882 199096856 467585743 743736087 424192235 18048206 373885522 299946425 717380324 683613393 244446328 157907808 107712790 652899777 892387799 396963965 721954080 918376400 273303643 553324140 199512654 710247082 588051566 315850530 454958347 84639497 48405917 113343400 60732094 94429519 91224873 771880975 146042727 558810615 368133413 570234961 429375172 742018935 870181386 146755495 425632327 114627713 157179654 385861468 620043841 49567452 782825432 194514272 820460203 56129074 747838411 19972857 618892507 335889976 188339738 73850854 420529473 236745655 39710605 481261566 183691525 130935477 105658892 329734251 689746091 473792304 752485564 119121262 68327590 475183301 118393108 493959916 442327365 275572762 879821383 62371205 177656565 515163166 109401829 850633120 423808592 857240239 723122328 42701098 45646567 911462065 969068303 466176039 724071 8778907 799953956 36931948 992230735 905612847 366666198 534493177 231921502 119151761 506130790 300249092 446851413 624523898 646725359 889178777 752613011 379063094 804066334 930269575 894226259 913468162 633419046 170551202 770708400 356541373 65768652 816354966 120519790 34836954 135047356 121243860 896132213 935001311 10692159 740879299 693130509 377358357 275372476 777568363 349026469 781503265 77817454 795877882 258543514 577059164 537573010 11156524 956122257 341639343 793942451 702864868 107623856 279877848 873416069 878332256 636419221 791701072 547203573 609455362 679054378 534767281 583215573 427702942 322284943 593907732 168582240 15415452 971266088 296471067 645500166 172808908 77974332 575833971 821203141 189034197 152893134 358776151 52707073 109015391 552931845 699165875 664396610 660555701 979043722 390329030 391404308 467979294 182030102 938607880 77434655 861084479 325891512 660650228 141303772 648176455 107074311 309886011 516108258 78340398 606357078 161608423 103665657 536847761 737442393 924868798 578398309 742851878 136161300 631105381 704383620 689093144 182787607 368780229 202165196 161831329 759109259 593569503 629810622 793655712 384693735 559761629 507256542 710585246 72928208 648560313 358761700 180002518 958446323 874869957 110859267 417319752 888994731 214524923 806683864 478953475 991910072 385082173 221805353 128071371 868703905 926188972 669680867 51491512 147485553 871846062 65839192 759111163 317931917 695649813 552766874 702625651 107927793 60023415 413210896 180856000 561100079 624488948 360858517 372062753 351875256 471717783 789382505 240869987 686242706 448582720 719823461 530669129 833664892 794145165 511256852 554885149 572850489 33454070 606376660 720336041 905300131 672215851 331963555 75748399 220382015 884730428 778374049 328309808 797270194 44101297 509165807 210886624 668590244 870024324 582949376 20465499 194258458 224848232 113851837 880501163 673430952 833675298 263686644 359612195 480336814 774943495 914497343 53187302 808397564 373390354 626039694 566214046 45606204 958003248 641962445 118504571 695250027 420336493 299330730 345036572 464437789 808496536 555923195 133028032 531037211 138872571 6009883 725295669 363720802 119861719 458313183 37151753 806053368 721999826 249280300 286390182 349459672 163777642 192093835 157857235 537167996 818133529 724071281 435290551 776136776 218550077 406311473 323903155 638886569 705642202 668939726 955840710 366655090 224862921 941385093 897692300 216251843 947394975 475504320 579972644 919773046 786333855 469640749 725826413 360850032 718921048 864732946 710309704 735215041 56826781 868166938 124899388 874960309 444754570 560189939 503613436 663304646 966501411 827516590 154707567 524659965 348972668 110548276 891315054 573835588 904449720 641523705 790087430 704361047 117028025 222576425 624134092 755878231 544733525 202476856 116728262 116170924 67209802 827037965 851385965 976552934 547721255 976285352 704029594 844992176 388991642 60159381 360813174 208009405 887675971 515520740 732669369 89164990 478585367 623984422 663000577 235551438 118024478 305604358 939912484 87568854 380697134 416562927 843447084 925430659 619039783 960175346 41601582 538765936 639729662 892987546 367835221 39967268 721789250 71864814 884959444 110780891 132024194 98288969 318790295 872216516 613809708 51459663 961381505 944911426 527960436 476898433 180462863 645984914 782502790 120375347 733553767 15716276 389454625 429517203 941146934 8494407 242208900 982748515 399776694 881938561 728252413 767611914 774422181 302558014 691993079 511897976 413338904 824017273 610186944 584645551 548750140 76513003 488621565 510131645 21424428 16582001 987030077 54403642 515083266 622049219 27295340 101153384 637765494 416749965 530670586 431428779 277760723 772879485 266693645 677537417 507334398 994946057 297665682 134272930 150020422 989658761 646170905 563359326 666192385 256357848 521228 67458876 332870850 489142792 577590520 206811629 358241144 417136949 261215270 873324409 891702519 288510610 826994145 381984364 705260574 210181082 813413142 983021296 983060567 80106786 513075064 342911316 927569195 810740746 477184245 77589616 652915858 123355149 493465293 171624594 232229348 493986520 239083469 417616549 983129312 669190341 624428177 341370455 86327289 885643446 67211216 830546159 174154055 894205360 212530522 879414628 104386441 25943663 714952276 939963359 958566800 228027339 135391026 886135994 891284436 465091622 816241962 396716645 440963122 309707254 568341238 673192469 803693774 659941059 90809017 639339437 329131399 567753545 980709891 267975039 453396991 900437458 98521197 480067397 647159169 163568070 211998377 604061962 42028084 926950652 396541672 594883 7494342 531932698 739247229 898778778 997024319 408005542 295495422 290503793 717712795 716353012 963696261 373922920 376294070 907021630 13262356 557941820 327291526 846488599 825916858 780688516 599442408 776954406 113272265 246601577 793038827 325270641 850663538 835066910 252221292 99721561 688178144 259715633 631654258 279941724 11010762 481194929 687947265 306506184 771698721 258176412 22859195 587911333 484615683 251669616 347449314 350394391 809611435 674740840 49399341 488044644 307945707 648841748 117515401 421217971 895443324 910554227 746488611 598623213 598137488 851226254 698344774 138831983 110941887 182515383 271290059 121952648 516226663 959237323 280975183 140441735 69930086 156350729 728353068 554545769 260536696 928318733 904940159 70148130 455575924 954339499 410709125 763521631 455697598 380740877 37255953 203657274 143811455 636260916 802280486 741948942 487487169 353141611 733297277 450945407 388173346 4587335 425414407 904400008 816341009 558905941 44841743 886271095 715256670 625711162 293333215 975793365 554029894 50789725 898457847 9605818 857645575 161683323 625643800 313343172 542424200 515416104 517000445 686235654 151677019 171797283 280700948 491680540 377455245 13998224 942625946 765628590 871101910 220556704 670028598 687442918 779462645 567386692 426230364 347235666 193097853 572079930 175545382 599644098 622869654 926519580 461766267 333031580 88202903 87410066 646374752 483143454 455342522 15891548 21895459 607019540 40205182 155112758 98700079 417660427 21627333 893842377 183289016 892729242 966915432 705833965 432688512 598894428 273220656 858918875 946130093 318834860 283515157 974191827 918478958 906384810 900711406 380245224 91932742 841430660 320171642 738307493 177090465 775514163 606715392 51502276 235050054 646920574 206615033 186266485 64581000 228242366 932625213 100386367 120971607 899540644 806220332 553660118 350951424 79440987 265095345 149597868 250792199 548610501 123789694 169271156 307511662 877017452 402032731 399444403 570964463 722204372 990268247 748054928 350234886 596983639 799557203 437801292 96420564 6172235 624067776 161001563 86930952 409209340 261387929 207902559 161266335 67608260 614079028 512217758 999565599 879174372 661815626 102874149 280301224 785605319 272145304 440329238 515139122 674178034 839773640 86103585 248898758 682558239 686674864 451649995 132058229 338748418 889451286 228478792 197437004 366035413 389480354 284367956 775244752 503384634 492270514 936511087 423509246 106349541 448728844 275591196 838040265 110544469 378465344 970857840 748666140 650610647 411187077 116321613 177305032 103477069 202425197 278720141 786035307 889100060 730370136 918093535 80364829 619821421 146572326 277801833 985856834 388569031 562169788 613617937 891953664 54440301 550129023 167979261 13306193 851374219 443570456 703862809 814435039 822035799 527237001 415617530 325162797 938424077 531939143 502467829 894417497 734364339 781187969 532969155 475980751 364074456 303579041 556345579 983895877 302667718 834147411 822269062 691236748 248833550 288403350 435706764 155790202 838532373 603686024 21612747 542422943 47256480 725475555 356857981 721808630 105228907 772475511 46971427 43652984 156931005 401955607 790586832 891295343 35659927 323555987 219792445 399734383 627135027 628654376 236146611 929802745 315318138 58415672 473555844 564151688 199335373 761778959 719941889 37867745 217981335 741554635 432807039 117754166 319546542 789665020 839562795 424775448 414656882 886534221 320944783 571587886 141006179 111531615 315399580 176666106 287603953 387708377 576400488 914738979 16362752 812547098 697058075 331680889 723479121 23130271 895832576 922814493 784909229 468290817 813198590 2890563 209845451 246005628 120644728 529391992 888186999 812723875 954167440 155360232 551774447 127628574 726948117 692780626 239160188 894864049 869446731 526764140 282572425 445847218 294019471 151451528 110910667 843593897 483132416 834389787 866724167 231481344 757204279 504149748 699772160 422919220 359556662 762133962 668924848 332717742 144042306 409628198 145441616 98209745 564988430 549732414 78354670 144452898 242513039 317514858 39316946 111959769 696795349 174405722 410323338 990814819 325857249 521234004 686925068 808989665 208140142 406165586 892987360 965344421 910315333 445275871 240779992 122388347 207409832 909704839 307622440 351452137 171849389 305580407 302178233 736837818 855312820 380532903 881290715 97825859 550564112 920607661 62301979 247359460 95013382 325141669 90690631 273386983 698892024 777615698 82376647 907032166 36297635 827880358 724892938 946612968 273156228 965672929 921517666 333082411 727894120 229140105 684534548 899743508 534720511 839229132 636581325 242549682 72278386 370388391 192891892 622842497 143512403 107710223 870201957 91042137 432851891 813408939 364429119 131743914 443540988 299322117 891292431 479838622 127202474 616185368 278967941 252875053 434374649 200485606 585957463 162268768 282142062 123008362 62012275 816862572 962237494 551109951 59412254 34515879 921498341 104820497 657358376 65010744 212530719 380076684 8569232 645382609 46001974 372998350 629642875 489542961 672320466 373451657 969381582 799522939 989637025 248349523 52397991 276528025 301351480 490871805 438796792 583493542 613880167 353325418 252872465 576117660 756951720 164801070 463149890 530966412 269621567 120508265 448493507 482152285 353101300 457062738 127534894 399103273 830061087 609694120 888646233 502381552 983145776 710544167 154420842 825299152 958893689 59335184 101827176 112761520 550206989 393140319 696255061 16603507 598982088 949127526 592721166 355933807 113928595 55871055 886900219 383550161 28895672 187910077 865702446 234513323 644972815 845753691 486132948 475033901 307964162 227295532 829931805 143626289 937839698 984352646 821441793 749249738 896204182 775785320 862011258 298927522 21441991 558266318 315531028 620424078 359910195 908252193 976357885 473838790 816639599 715774455 709905302 698051622 903684531 428124099 785081297 401173697 126394141 271214244 876207598 434358302 498509775 558655754 430500943 288865825 395524751 251942735 38115562 291728932 27728054 900126819 590656453 49170044 310909489 906187480 522110474 670819683 666956024 350984710 997174824 336111975 66759164 707080126 886679948 822960046 135204224 671761244 76650095 114114717 795491839 952857692 548473018 146517966 364029797 978973960 435383790 759554547 83433046 473499351 51283479 963677452 226142522 494456283 865363847 389568362 253160115 387474320 60388044 772632490 738459029 910079220 108744464 657734544 469675697 847940764 333210942 457396272 372218359 409861036 571510988 167710198 215235079 119984006 314228163 579264875 951474317 749611952 191335773 887423715 75627654 95135603 851101166 154286527 589591886 568981364 543854888 695268352 956455684 456759284 467900841 547431064 366838503 429161657 57681960 836514199 129618772 243409253 146426822 501837130 653270288 717937810 669547327 721021718 690438167 836291841 152802944 494428835 438420144 344138716 381852549 514047798 439274319 85470066 668334324 28866204 654451430 64705564 576650907 463423465 521464847 44551747 863370880 888303349 326229755 921052839 577333899 455848526 16978443 723760720 957685656 670248730 294214881 479749334 243786799 984653047 168557527 396589742 479081882 606977670 740728458 713450782 121025467 180002776 798920848 641876143 61385331 305888629 706581706 638036237 621828445 80562904 535104335 485199324 968866252 713850442 258768515 398716502 22215319 275746957 974993573 979900974 798512039 269208454 312166660 42298837 106377852 480724186 438888579 585459733 87701855 32133388 151426867 61243674 212136163 950347714 555636168 126037845 108752694 114734225 764074081 730581138 195297128 151694767 68296813 16679731 865545208 179581679 267912584 887760527 455328636 242906156 720177852 106357026 364630961 884860863 148655862 471008813 218101400 440060792 56468545 158319607 472194179 60411763 72079632 684330341 10759476 627715799 810368185 972028521 594966375 426958617 555126010 790263502 431169736 623422823 659459584 149231295 803004501 927372167 36991821 110849488 22794674 609686025 217206513 387425635 347063239 218378727 858434447 565164639 658439518 767419343 723484245 130633697 827831106 795563876 667480389 691106933 275796026 330364926 663135454 870762400 757323542 70777815 513542253 41009629 694200637 173001836 190240924 349721490 100374002 79749096 313087329 123168675 689435120 530293842 363110661 36498359 748672568 221545107 454179349 259628437 988964450 177663593 390262133 669311907 973227468 57742522 360418839 101539845 240623799 876070644 972302244 997947340 946848459 485844496 38956969 493565447 511362683 81714244 843286936 464253036 161463339 8890617 439938062 850898459 539184458 803048723 739913169 140373377 24593829 46608869 400001813 866074630 224272461 642780298 387902888 50016280 553039171 748321727 151556124 793662969 476908722 123858367 644126660 423757180 462219214 535599980 917322627 973581896 617314223 613125914 290351283 778777562 622016530 730289344 482192372 13717339 533338066 74621892 6607067 410448247 121230760 406608880 129039228 345503220 49389177 516942116 248035851 454944699 117780194 399591974 248607667 594688915 375966692 892734326 870962447 690702257 280850658 640801425 516800504 898164880 106443690 807151786 676942441 728460220 537441129 11651164 594693910 923295547 86273055 601300977 186260145 207503814 7909856 315299372 553007033 909815384 684757839 801042883 217276434 802538032 53151208 465884100 249743299 281634251 211134777 120705745 972336507 491985434 614023521 489137010 242666666 720467210 148805147 919609106 301443781 686246276 931260270 896137691 462058174 17533324 497438667 648318318 77553490 357864874 963617689 630560522 120196609 500891880 284119757 337473042 155946263 189787316 655873493 405689561 471421567 867008269 378911657 443758073 211510055 992935177 785411435 454176720 565918739 934216581 226302177 867362519 472979208 10078798 763500209 935037381 880128474 113455227 583355698 957681963 323836452 399489739 440758836 444033060 900381618 724878592 634022453 56327880 914665908 289895945 314533793 238603826 9420566 545961801 682361898 73446972 391413330 320289684 527623691 957332068 254506265 606442219 824694586 727485472 616521017 440711147 515039205 349165842 406682725 98394902 306847804 730519177 350400992 747606639 27068588 103298961 325001583 661091041 12143193 92183842 950986985 179193337 330787667 812923902 725155137 865665916 886370873 116568466 185955600 266510915 73900533 292978216 872953134 751111471 20463687 341990502 44338969 388019243 691156343 451021693 338930497 998004146 34057221 689331488 598127136 61125809 645146801 775645070 722216849 657289993 867828911 525720185 836483329 51132929 338644087 414154817 916798845 77531311 530723283 955270796 344042226 457140167 248249011 216995359 60767989 121229049 558985860 105106957 509248292 102658554 408645002 848178788 100662699 442702222 390026627 551306186 503828030 35173427 179467608 78561230 544979771 47296518 604281415 233979451 950945799 942925501 648134268 720260995 20456811 31373902 675531790 217015388 341030420 776297152 434010746 401798409 897526200 845512957 359421717 259290843 948171510 620583070 959985982 901350560 63285292 202528961 305173098 419629673 90218739 484640705 498190903 635198510 384453574 102472317 721694312 335399372 897914169 222344931 55660366 770887331 253718832 583708507 987902719 594749252 212522010 274429816 849064012 110048210 119942773 61002080 221855404 920630634 681585150 34357738 821981194 597386793 236886698 127154291 17016465 327105436 464311347 367723719 962303945 848764920 322712387 536514609 36680644 73142907 758859539 92341009 696546590 12578371 528565868 536965660 459843974 741087877 811395475 161424337 703652438 783854599 222426416 778024194 557001585 904011565 812381931 231499130 501398357 49268628 211169772 370931174 376374063 675481118 591171244 191194360 524246037 913883631 727708968 560926680 839542889 339084858 505784041 536089478 204179580 886866260 73055137 664023553 480470488 736966964 825447889 36639278 373337914 47874305 814663471 930339498 804402221 627045401 14354979 158316930 528830380 225524750 529248103 905204442 901005867 120419346 948915153 277768256 886819328 529140472 838694935 578878569 868225330 196995327 114968046 72404909 83861586 40539535 588944814 416848426 630022850 266909054 453487703 855877115 167299710 268151173 638732965 971701931 747712925 653087943 130018860 276543304 878612693 511783314 34264097 779618559 484719011 983179250 57386814 224054691 364836073 748598101 802933259 233061402 798109779 770417656 157982663 734487717 663473542 746927476 151336142 146012743 13836529 604823844 1889858 181136239 725491368 640622822 5354521 473204292 146227116 135373380 602263947 24839808 647156693 636528043 656974719 131875703 472223644 566877884 208446745 837059717 167992336 11380003 922637470 966102115 781797659 80620132 700589831 297787552 827547607 704442324 443800295 693900488 161782519 445690152 875036726 887273886 938829325 880391246 212994529 85056440 868280977 815258475 109896248 367954021 304302869 619387318 352346075 776526513 186265201 560792820 466102581 354257537 572172822 241256402 172876003 206486832 321876534 873465833 504274384 1940492 430424508 948074678 695840979 592207026 246281181 423394056 479480911 37626857 156301653 692475439 122683296 24582629 360250265 85095895 245053001 664553133 704483212 597399076 293595997 743264765 158191895 759698577 97522301 582881068 954979 122914655 789367900 175347864 996380487 146158635 29804707 279321346 946749664 725645686 871528371 45547196 1556093 203525633 83174052 10374098 896001071 205857347 34956726 108767687 143469594 132526079 773320819 847952805 729925154 66916816 443733921 888117048 679131744 393772573 323514467 532603074 516687227 112882366 707950937 365584065 111557352 737755644 644905410 58307015 315917681 516433780 103854210 169990125 719959412 39544613 180364222 468476834 245401960 67837300 577244520 388871553 200363378 203081691 89340709 930288531 269998506 533074630 670921930 949130249 926847202 994436396 334249675 296050781 959835114 42200611 661634845 71392465 632472606 306540255 982215832 800906638 675490386 938586393 970896763 247966150 978131006 151260984 716442983 76049317 219098283 146203855 317437221 419461660 349285545 406777929 202266542 471800402 792368910 873188471 273447002 571732464 867624867 607696676 867783244 679976332 502413639 529418088 603885148 134886244 688474694 438617331 788309234 363965080 229720076 759205996 611931229 60367433 762983331 180890563 136416749 982081614 179610769 453853969 254059625 528896313 713148249 456326167 696714 505517159 182030989 126660068 77249622 49655855 734356743 797549217 582148538 236770381 179483656 186033686 224172977 867958350 624651016 12482210 84439781 854371091 624204557 696371009 914738523 239704239 729777923 903671623 74302204 909388692 210041943 328361829 290801356 923190192 637204347 144014422 281223702 819235335 270674489 210989675 721407542 5031231 8538891 303556079 94317964 188022546 342106116 318490940 55980895 966757132 183489501 140420675 673644574 660210409 689308035 440899449 899914647 271602310 197087423 974216851 180991001 407129366 155095031 471792356 330319557 792299377 615806777 611543258 611534711 886481265 822532932 185458604 744028848 683588174 489014683 838346811 871610719 831120798 9354102 780107966 650394281 192843602 773044992 176555207 853054010 314869379 469971007 605485008 586471688 667058429 579701858 619979040 74187794 734796888 91771395 257023702 379612616 560094524 868566959 991147327 299092140 543616242 29122282 43120987 79720767 518136964 733984149 951331486 201774114 743338250 583955803 704684746 936181851 209517146 881239952 641752212 376902876 203727310 99753572 963374563 870785739 679455429 435869954 944973532 266768669 380157701 54513586 646381284 940252224 923080544 490044962 91860715 319213138 519167244 987498054 398933904 889820559 721482202 202781741 91594672 317336804 639253895 648795770 106035006 848771041 382552073 747787218 78190268 586279383 847540789 41564831 457065121 379512569 329951136 254555004 498797589 710108836 309068589 145178873 502877411 84665485 487740186 594738126 256394974 859423781 434752531 655328877 749244340 8751084 710626970 693355363 326087887 349880864 194667484 432122893 51168256 577219557 32426462 129358524 163498939 879967250 23439706 473080411 111996170 353390841 727635414 610793759 63499677 889220355 608488983 418893439 973885839 948745520 13631564 82797164 808169301 300900446 738126040 409929992 309651530 301269361 955801706 635739416 651150225 150469190 67862308 554834832 727688746 100288769 684193355 743704036 832772370 560149412 216784446 944768540 913540253 796936211 408078650 829556281 686156565 869083984 100966071 512558755 817829503 114597635 595355918 478515155 268014432 185998310 740961498 577665961 487267670 696763204 213405377 990934246 699748745 133784036 545769078 279953842 234072805 82478784 23657877 66845174 642628196 92958674 864130065 408684800 889894884 124725066 90757432 428567801 993809049 191723502 941126555 664154904 158837488 388998825 995186410 426851920 427513486 736147908 4517880 914781155 285427463 70439608 758231753 985176207 204223644 156517182 117646400 290812800 238995965 141304276 210174325 734140512 234262949 74304390 142825311 124157832 51545807 86099094 405241984 897871208 130338948 198884891 414542463 289176435 587883715 409728872 568544706 15397200 998393131 425578938 782694706 136336945 496018545 393442810 121513151 552758540 549959991 91675902 843571339 788955956 232980177 53745664 375612819 319759477 980566405 370954482 296433661 32112211 457053575 701675644 782499770 587392522 900560534 197042232 729085309 340960600 459287456 297630014 208874151 457680586 723208951 991568857 594017531 71743848 237528018 568047033 624502387 787488009 659722935 320590078 428960316 745219463 374335741 804573134 64978940 207418497 175527615 361412600 92047059 485097542 63088243 874546829 72490063 816165129 71589060 654091723 157125728 383392867 951721737 365999879 841073453 527447039 210085087 287607335 451707238 447613104 708170719 76209625 87617464 220410005 249316054 516577779 965629468 623651794 321150913 30608407 831070290 349194879 244537358 923117348 834292420 160141952 650180528 759298835 976307080 574285940 413390557 985949160 957678806 217628645 204465390 651268610 597592036 414550476 938875944 49299273 714679931 499563015 978025249 802297395 719973019 227341302 318875173 685602486 703509447 492542437 568727244 387096088 841737316 665780953 162729788 676029735 825922905 812910315 287844921 654746336 387196254 701235478 493211847 197391412 771380474 697677236 848660021 368972509 112227711 640052317 270788134 679423994 139615331 248813382 481721388 859588349 328671036 653112912 397707187 32180482 145655349 818950782 419276570 987392664 484731735 582006357 515938750 163170991 247433023 803783671 670433678 634629277 357535500 163645525 832020688 128915973 861322760 533197060 350404834 826066823 173249376 621192967 358007168 165381058 722522700 839728555 24969407 51193735 345357818 275192945 83374217 491013166 94143726 355167138 330922181 431391812 789689846 699377283 447079154 37122868 355677305 117512832 524268496 713212804 133674708 208805535 694645128 994997467 742002595 897566313 673580641 915251970 371275631 31587808 80633028 93798331 723832714 958118786 144992065 69190532 85828082 80882633 412720049 32488159 288566122 596158582 316396323 78255967 295535864 763475476 967895187 651213168 880988307 492163682 216942323 14663014 700969217 764103802 862176833 295488163 661670115 388273825 63256484 32945745 272377985 143889511 979260427 848727050 954524648 976768844 770433933 892869081 910167828 35670334 925357240 51250302 631828915 94269914 129506268 927364778 857745389 949917806 431094297 591250048 294597840 500552971 458429413 995567056 264656772 173122597 143571570 778843238 561396422 206828053 664305335 686290758 203233916 643565761 535017807 10274915 472850956 157968092 903143996 383018784 193638425 681017587 434269085 825467339 775287500 416291704 605348468 633032888 218725862 36442764 76799287 513323701 389512086 535228700 361407108 654168857 708351296 504978677 285528447 122264069 711806729 949833781 808554826 915040644 445915893 196088985 925315559 918766849 354057076 828459554 154301984 547695500 361993492 588571068 373162838 137280991 857379123 978511305 622830230 76104984 867470420 699629517 589428684 109498857 234858216 950835791 763667713 943209511 308330819 49196159 65473580 20137548 851546291 726544757 935178191 297462184 922633741 713010101 68745384 276690816 393986006 223047367 824386315 755979497 811618434 50065504 893260487 521513908 881093160 368607069 597618892 601079931 68236585 39563927 710578787 155611152 842916070 326762852 98820662 151246888 228475362 16810593 23900787 80021653 595871702 959078978 230000188 518505442 524605430 298745571 647712610 918591436 521792937 324615276 674570932 185927722 374680780 420347771 707441629 108290291 788954839 157576872 709370222 709707775 197140799 419949008 865318926 40056868 746711859 816655939 43820107 975187221 685982884 67720894 907725225 281854585 879316223 137725412 652876378 403921652 436470982 300588987 175029439 958263918 625204263 849600371 144191639 852401394 122464493 704149619 960691684 763935683 861726491 670061905 473643457 58867289 942527265 191478734 951440508 541755475 8134672 847776966 369459047 694117555 915497859 277184271 828488491 647330433 267426034 481364869 51252085 703897015 634470207 78797875 514677284 112190821 928398245 511385274 964592214 903379089 68051245 925283898 667314771 929777735 447862154 993474579 841161375 242905770 184953312 645118234 784661245 45604336 492895199 154120291 739721890 260909410 283820914 420726733 908239842 551246947 902091601 812008278 107660314 389078159 890806153 622337597 501268980 671720749 986239223 465861193 427616190 54290467 243661442 94930960 984068201 544039948 940921891 677745927 786945717 125875202 322864160 571606961 23995889 668275710 578243604 763717779 929185119 862064517 36960863 689941313 413311463 939052463 354465942 520971776 180646973 97788446 995825725 681915952 622025547 982064947 293497 49641736 888871765 243954938 997089047 725456317 787994885 938010937 403202243 427456954 916402491 578582754 999063914 940398379 246858463 429823869 556632509 28559934 291888385 593593371 571017598 557716200 385162185 925483539 78687975 565809158 875788337 927030051 100241461 497813883 761611349 100534957 399971970 650483113 344489895 397061016 228455781 985001131 187588305 631658023 412458084 956507147 62757128 264038350 749421877 309615591 693862218 158570738 190691876 838266955 752164108 761709473 395983154 989842645 539709363 327187480 408168154 415497699 106733883 508409614 765827933 868345231 608944571 165799902 371344696 953434465 415377270 599800476 790951947 602965574 83974851 55926383 411989072 146731978 319964732 161410948 456347568 866343301 319981685 647039443 704610255 924662145 261265267 953109760 914504789 800974630 132813592 175189294 68988680 239547474 683598907 834816613 107892704 292543477 616514 479237399 98494293 268510135 79037875 889446240 871475708 15529077 945372622 135981131 162261054 117853705 297392079 618608622 984197005 469890115 118164416 541323612 394552259 379429683 346949723 161573399 32920664 479763314 336762692 101909343 719310787 20361599 936725955 827203491 165421427 789858821 158957241 116432072 58368955 90511467 5878311 782361015 106040543 803767284 918342145 268301597 774137340 68250575 739426570 610850696 538140690 857590985 4690659 932692948 89537019 351640382 946782699 122457682 831403695 136061742 224367025 550714482 8939692 13609331 230434324 174361119 803468151 241907916 290793190 861837106 332419383 149187852 496714472 290976277 805471487 415056616 559277873 579608826 483307191 151220794 42975873 21447880 8811779 47666532 806657179 950865149 399306913 605956229 73322831 230710607 742017971 150206207 633941440 750957662 163815537 864375763 925318780 967283688 106283679 68628321 681637145 291219413 70332524 30867968 582195689 875804010 445924583 993989914 307929187 781748125 145210707 350905060 655712356 6538837 398571591 314885887 957403986 797878503 920842115 883243168 28589109 662860085 885965726 515046901 266334099 49781262 231939015 44169230 869581301 190739045 112797551 403734797 481958457 183130074 434602764 916670498 58934084 733043699 910660411 219379622 514791823 908387469 570284681 23020531 914926306 968856271 337906417 724846643 766734773 258748531 460606162 647840234 774124968 199088239 15403486 40459066 101385852 247342500 84628295 970967153 438081545 49942197 227218301 920040001 233072271 514337417 689226850 144522706 247381115 452403612 363902327 614689289 360791081 934187008 637709819 128233738 755559630 975616235 705596732 374810755 86881118 18719245 22650988 861006085 217807483 38054473 901465150 319193334 137913324 838609796 142676838 575994868 888551993 369895139 348551221 121624263 884232555 37778070 118663320 984130021 490181682 335081998 598819309 703489114 121785357 89045480 831722851 877344987 64661714 389835934 252155741 151542831 408555178 127323080 12548915 626362660 17893904 766530416 945555993 155807227 457656564 88232831 731802095 346208556 310644321 80353315 320349170 47393227 970647736 291528841 31523247 313345769 626610838 482858907 16834882 748396195 571904386 701074084 625741181 636566100 90910017 730413273 640625282 499465194 857736352 505690549 125827853 728146607 124737316 923900198 883953833 582393879 12133028 468272279 928602434 175293700 401141945 101467955 222686926 224306033 392996795 254210172 537651801 19607633 737069078 554486683 620520179 161489816 108077118 98777711 798055915 198987135 829190983 291197548