2085 528120548 47214377 658873523 987498342 344838090 689204125 601105680 619180526 378531498 517381729 525080236 207452362 426708519 882922824 746181684 437930806 655703397 359091567 342204370 781785584 390706495 439885608 196345274 842952537 66383882 366295301 276932911 451874940 891842710 747715384 950856035 324532337 679179413 819968216 794356720 199396585 946054201 533214668 576118044 557674652 572122836 820399932 871894185 854216067 528670012 7083537 562929850 749972923 865340656 630431837 75005506 46551789 913484477 305563348 367610651 312449237 463093424 403020083 677421918 267902382 763873014 815684916 494993631 577612091 675510612 15194379 590098089 526652883 78260682 101527784 622816818 432519393 880036182 404800367 454439629 13762626 661928943 159538868 531802661 532640405 334958649 980738525 751009526 672567201 5812306 775192871 807886879 93385512 113150306 210220182 752654637 894923252 315780213 415269511 51709957 989927895 830920863 526975422 408934843 109767728 409095930 976051397 579638305 428514890 67085894 775414759 644976390 1601219 839503057 922634874 971356707 703854782 853751876 742469686 946345747 791434840 548648364 119041421 721781928 866643174 661018512 978561497 848803291 588662598 807404574 294660233 813873375 232634372 841899285 276287904 776633466 629033358 407087807 388167096 741086785 907333167 427019344 597112103 366933130 165543354 971741067 882048161 149171688 556119739 445048158 280766536 193664604 506927727 141241460 118711065 520533994 421698098 751804423 892718927 757888903 225029950 167385802 462715283 950188278 26983477 5104816 699223057 986558711 125923795 995054934 934060222 863873999 80465330 744542646 334459907 299544200 701204495 960959325 639298499 473619991 459664871 736790843 588883040 73831147 236371815 89418684 248300619 902817062 200560037 932052592 608161733 829215902 641387039 875788084 701101323 47746355 653062654 650336577 553954062 530987563 51559357 75104796 20640824 477599603 728029628 575593123 698462894 781794576 978981494 491246959 279432540 122281568 778184178 488938384 740392980 730649636 779687134 772905015 155232450 147987093 21566633 876765776 510790283 850979655 17055020 84691210 135058993 986201678 485643994 205841639 8343365 88292917 335076061 374162419 673790958 323278974 929036073 373881935 669395038 142088740 526838585 237135536 975881842 889251299 734831654 339531583 309770602 476631639 285202328 787791661 590154859 363550842 340054859 772964360 972129150 753450177 9150436 374640222 475939817 112642492 248773919 567006562 54407266 900345612 595476677 938181217 136515570 355243075 94443648 508811726 813569681 586213633 717788159 327398199 417019912 165023064 799950254 657646967 919366221 982534713 992443106 165170491 761694582 243275856 111446875 444719245 31490949 948218665 226509798 229393896 88705519 274034 56991340 45165933 94151480 285137265 356001041 504316361 735531265 476452958 466548807 103592252 289081283 975596820 734646291 576794582 786180382 347230958 180702486 143947085 125314939 771608733 536874214 821401591 391362905 346627456 818991207 947914104 810291618 158077168 539391517 460313724 677894940 453865561 454390447 894400608 956699545 562122801 875770110 180065661 819068893 822223687 951498181 9776379 987469384 625982097 142219706 709481590 534354026 238368923 368987358 503861626 448319525 941441653 241197502 634067345 78982706 989678431 96840388 896765361 506852592 236438968 800462056 7160586 68137486 909729357 788802475 992252479 430700658 236499113 212958264 421403539 840390675 951283195 1295356 991254386 847547706 75483934 161480817 463265723 293936453 841703634 164707065 37967108 147834632 589820710 773377155 305096139 784592695 923322192 303078107 430687036 312364130 60274262 191081941 651883476 870995192 922026287 148912838 254265464 184132914 941824156 896197478 444591456 533010014 473081864 368950309 876214988 581801612 819436333 407401534 882870109 829002321 536937796 540791427 743209329 100762221 515652519 355770661 122461020 70284577 758772694 274709156 826381536 829366697 217340460 429100846 134274651 358249212 297479776 197991587 717154236 711842052 769249693 493025536 618294633 449425731 753539667 551563408 269035758 187329110 100335487 630780973 574793376 920817849 977488136 854635250 346481866 942302582 104057351 368101543 694141215 810630467 571444016 996966979 480530831 145188257 674281914 812628635 661769030 998226230 681144347 342778999 55752563 466208111 662517546 816893460 37911977 514880816 247898322 43662190 354020840 179075193 209630238 496337767 25180361 246346185 305384169 270441502 98886717 425796238 900110329 77561656 553217701 127905172 907803631 652017088 271347806 496044761 572015753 771890152 320252871 831902313 757948382 316561418 796901291 785264447 38399829 601474022 571353529 671625446 751929064 211216688 42000587 915691320 256494157 559945394 595790883 600522251 375564347 385966757 413439213 537715354 260966768 395319533 782438890 764099608 238044403 607074080 976486274 695796377 83616302 757622018 401894374 714947317 237596335 187880791 64076541 569939883 558031824 179283123 206759212 312328218 525313132 200528591 428157687 783026560 627217909 54582048 52977313 724771751 659900266 479158553 423266307 418743942 697480753 189484177 147679499 910659748 53208788 2259706 196799191 967620537 426625048 521770939 440763943 393582105 961455325 607281345 974621651 704073423 60115865 474597693 676953153 167452262 918657981 743222149 765260083 967189181 428740620 573313472 916934960 758679481 947555567 314236890 441744999 439304911 645236546 132066564 980648492 874166401 861507798 802400670 222158874 238342171 887159635 529128233 665862720 840203484 195956131 510196258 766155930 524399665 507526166 337585570 6280868 309939578 47334185 301390962 514306645 705337628 851796613 261550568 599310274 579983790 681716567 485315808 680072034 899967335 979793799 987526281 181263920 370882207 17104028 263858111 55422590 782125364 881681132 331210273 268723656 768278700 868119854 34790374 778627430 963562389 481027557 835349178 114133926 478494408 741577231 467029508 120460467 686173935 823061871 262598785 98538691 445429698 221695512 115019571 718791689 348002601 132133919 805557160 343832317 111637326 775535746 967042255 255166704 806329396 925618608 19982096 185970693 357996378 583940037 813021017 253196397 998252612 410300582 903688273 853790141 310972858 601481410 431549138 711253647 333733876 729825573 605278723 680060962 81945244 290590680 547026800 692265054 190722102 152282704 46066690 135334796 424885490 110803209 810831718 413950026 202823338 490045927 631271344 286191995 822826862 409691778 356917486 247384803 802502691 118037637 847583450 954904632 667155073 361860004 876185276 487575097 862523635 103387763 42774882 684070622 520487677 804293517 327606713 52307216 609297733 276686636 850270201 970499849 853554627 975903621 450820927 183425188 565029326 715232121 831864111 18261781 925374819 527216018 709548351 208792241 907719620 105492582 738451262 239670413 641933880 623284312 911733738 511307222 877990964 745145278 295761499 593644386 636154339 400494446 710552511 323680637 965133616 629270025 737771228 14398459 631713601 343119577 641822051 497853321 771279974 829978671 805884469 593093241 133286827 824742506 264293083 224371382 884729991 238268514 142075625 338090285 914339300 920619506 425846892 901940399 784646779 540578702 327148449 977860042 265257954 533774268 876147510 528090979 664739227 680848677 268392143 338305891 16344390 591375814 642808857 29924937 474170364 247960069 427325751 102875994 997656560 355493715 750429104 855458747 5355848 287650776 596002536 583286114 888456380 383343616 356221468 304993763 830629178 581890333 986961815 881556268 13634338 883595913 132207549 925874489 462661552 321832279 374860756 550424792 427582058 423218557 927144333 831310224 454524402 638066560 344366747 119691105 17125105 192995382 340624017 548782566 607711919 697793976 45996944 215434835 653247531 247524135 357927232 657302578 287642843 538858711 190093670 745600033 600330820 6934021 135369808 870278474 484094945 998129791 932183554 602047180 822365178 324498110 149405187 962902592 658647268 379065437 575580733 438089556 138713167 235200843 453644138 269660748 147555002 715347253 387499633 998339729 96960755 398677101 601940403 628099279 29440372 797653882 984317312 349150434 217825390 522482776 671982655 748318038 981981789 879777737 53299047 469760876 949353063 773302272 974246866 306907175 432763536 871368502 650338961 795406520 458858553 487023868 454305532 87864498 507815152 844481978 537322215 157691770 518487962 116863725 685915882 617195977 430673468 516434201 418781567 351659370 633468216 554053544 259760834 657070391 786192756 551183978 564211902 198210697 5263227 964002440 717633205 913812445 990277496 34275217 678410116 209405653 926840761 244465199 118419347 685068682 163121 266006319 463414517 408582307 759860025 160577307 38714823 442066356 293388777 149006062 158820661 542083521 796537652 374843383 502890621 82446511 250870974 448646537 779194108 199240547 792302062 477649590 937310244 19291255 40888816 104205766 305235916 892797000 900767645 712693801 992870375 449991860 751876512 700341445 240333767 820379436 241523140 747350665 47127936 733913114 40668791 54374095 367109129 909660207 309861282 51132676 500396036 318841975 901144694 889283466 535741329 949870005 593954033 640029398 819929226 333978292 64814892 75093440 20382308 652950586 464641706 697556179 897369862 335772904 240276772 122383157 448368946 267676721 432932693 9256566 608831357 411621625 545087012 579199665 231066999 418692455 348436763 201140607 657185310 292284104 926262801 202508796 520381749 627004038 104754172 277314398 80966282 810878358 998489109 933232991 666800184 302979931 649983141 621565483 92819937 508446200 533411717 355709632 152436850 116942605 839261011 461354732 907195256 120726582 210500662 266472999 598934933 353816123 572485347 40776806 137490880 35875221 915963818 739404977 608313808 737663238 177448398 58072322 838600195 314967007 351600283 372154220 757760060 448299824 957163349 921097053 110708686 383923421 727277588 933386545 694267914 209036088 719584768 499638515 301115704 339190530 633443750 398756259 959244820 737365485 535341262 464045629 766661930 590648954 672122020 298063311 83042360 40486066 846422904 834585638 159378617 895943167 90401070 365368336 703737622 491059093 256692712 314850624 483051457 924248433 694457957 818890682 553030880 625530933 203403677 908245587 434728807 240961184 723347881 395996045 925712576 778509154 93103729 28048220 957831709 780340756 885871509 599180197 118969315 395684701 46370335 448307265 495657133 814543451 861452239 139099132 930710967 930678144 23903013 316900866 669539003 641670005 265079901 884731676 387451120 145368727 681787770 524774732 918007328 548914004 392445817 565879473 879884485 886554644 313539215 168612186 503776267 335676424 928877298 395428939 178990935 465672822 119026891 170051517 326130920 593718118 641821730 447955176 558938936 822501809 863814911 624674028 203566614 216301115 415214222 819026574 734354034 40793138 506385233 91935717 136276285 198487227 154830531 48373535 206595923 740755643 83360578 501556366 996432502 507065968 450124857 994751989 945615396 20136254 272949168 816621205 359039854 354920225 776798355 805640923 34921603 377001664 465939829 774933855 141457074 314381823 898860602 974637479 72003745 753232541 796096742 557142754 754790516 791764654 392404075 245224966 802062651 637828333 151407192 187748063 219886177 800629389 331060694 323189834 39503103 890890130 854754421 740902061 351700984 390557152 703343999 121600189 789564938 46669164 7889584 315947520 304588196 353567789 77825724 246310113 145879164 704956863 19045793 743707703 15509743 522968006 606342014 287178684 235166335 250057423 388559343 785061626 220639338 912519517 574458676 642443164 570911971 235496252 168770150 742496537 725189984 910725465 135484616 151845483 541031944 206176953 359227307 245328706 993659720 597271949 27996354 641212335 880217588 924425719 456700866 968869299 479210730 421012777 965308853 558753043 917921038 816325164 142846933 14060368 238008826 597397100 308339466 332017702 236847166 907486624 480156384 553613939 853587321 739674031 936002658 798928991 127496994 689583504 349951079 842663561 225283748 9014254 695318807 666178065 954392622 50082121 400799998 619720956 69048080 520748285 437730286 116288593 121480314 949592313 387387580 757014127 779622307 436030272 645221850 273804877 289344492 197182063 919903842 890082492 376272169 102143230 751084389 824504205 358496826 628989897 99305656 898353473 240099653 506542112 500121780 78537378 363102442 338871668 26096059 966532289 852510461 44838183 70733210 671212680 259939804 865068250 564720910 425541405 274240085 693883934 163415939 902969806 617550893 677003187 824499811 794042020 784026802 896163477 141075776 475195151 966860012 194826330 472370168 113864423 998577232 373402851 390991725 544379333 994693916 984528082 355516653 922831999 452456512 152920351 199691092 500352342 476977558 856657516 413900238 766886327 207629700 172397472 257165008 734093982 244615521 494539522 419177730 421182906 555139155 283683627 345603392 747787077 742920078 400952655 102834568 323141583 803764041 673639102 999072842 995552093 156668851 325344369 55681844 907326977 368461664 227899653 209696760 452254623 827889418 901272533 261875907 221585052 232476551 629849831 682771600 203057578 614356626 662676253 128785755 73391584 230420834 461222945 499661385 486117971 200257598 57722242 98309323 572705169 487653260 848838993 683530264 410190866 598038525 397477933 811281817 438105221 332845215 713032643 853788444 449658621 602634398 166144115 878479761 251093314 656478130 994950399 133888522 315319668 850953595 815617435 37507145 17023512 727449778 241457196 873510755 219787339 648989931 225382114 907046239 496629968 435413123 356691270 782200091 897418433 887280732 701032905 652234574 905495245 959910208 5595834 836416510 370714840 689296768 799591545 375775100 704806879 31271768 742570247 793757675 529693917 361951218 346034955 844272164 674818487 258964353 147935676 726067233 158796243 57157995 993196547 331270861 648379209 785482365 805830616 560474657 586917860 407674439 532750081 360905116 234244479 613676287 986072663 217547438 81725461 732108157 668519734 862739153 737611731 587310662 22215960 113648556 982786089 709436489 518431236 116334652 738134239 465442610 954499379 407077653 830084964 866663347 547372794 77007088 94367036 849635958 755631271 486981921 616477916 814812600 896931508 120684447 923611718 257941187 384689280 809156781 552894045 262959644 769771928 818659203 755655685 729374060 601413273 88221466 470892047 830374880 661121144 377482410 500396639 484059907 480124679 791328682 518782384 572317539 952242933 741551628 759091099 408602760 729743131 938506398 26258636 627182138 696692537 697196678 50768229 841375445 905400287 599155824 117084139 234278697 728960872 766478033 524637715 788337559 36392114 899731922 301963783 652134473 620270624 234449417 843055340 567132260 307517654 637200362 572660213 469042380 138300207 526797885 702859297 227569884 442843748 730662223 79443147 696464718 230206319 963009729 344178146 343091779 760955397 327115290 903148512 313435617 101753483 553707084 453723902 100501012 147732893 417434960 957877614 384159400 725683354 372182190 570748169 711364124 109800683 690521751 926268692 524865161 882902421 323344776 141675385 616792959 407210190 80958574 875328624 479996984 49848194 898137883 246588499 970659321 614875241 546949043 831054469 92919929 306739279 140784649 970248237 576931940 213545565 43579061 522151415 998759391 884744314 563500451 878220294 872697759 698308901 335185 179586918 757134795 691689833 403632845 741778071 683544803 156266130 495213780 694184580 327259020 523331766 620793426 398139122 824552166 62218270 818168750 158051922 472282598 981026472 110729653 517686628 232269575 577952872 960097575 29390905 271073842 610172870 457814824 109543375 892750791 119789377 867837920 391631850 231334247 654963560 16793013 839836702 521436011 59363784 508518181 64772536 812433463 939738834 659041897 617616937 600504760 765449280 544910388 492021297 532998110 961739776 164729648 877857279 175223757 334746656 742458794 536584344 875832141 548118495 573454931 587948932 529821843 570901508 295419435 932525257 113702187 33664835 16298191 575398929 48012592 333353476 224969230 118613743 195772733 876225815 57210727 487874649 712747115 361232017 882518828 884088350 888443581 228943432 153591199 641404928 2531380 91142811 737566072 243942775 478208185 375394959 886371907 839028673 747816648 863191197 212681130 387639331 929035534 408230326 997614483 464973763 516529089 473039112 149457131 623396873 743512032 803037137 299442157 32109911 713818015 395241991 630873879 507424758 426252578 998717053 243412368 771167464 246729227 311377707 370568719 832886186 670504604 603162491 973429066 577228551 836696548 557686772 209587837 146798720 76413531 573148290 628778561 974236293 489177262 743405432 356475288 360669705 653558084 626338405 807789291 543907554 378718745 759620972 806462217 555603504 892733254 641922635 390924984 9064996 134192411 975867282 677793761 577760790 771863538 966094911 576948606 853563543 382115880 883005533 479256164 87181709 830587273 103431662 1460765 332748492 147760721 468767168 162808550 702934613 367884510 636043347 541437440 465285179 494866164 668612040 355589848 174984997 958014684 543211518 221084094 903258722 795233169 733289445 921456690 947493883 926976714 796430825 143305700 429152934 684936600 373977395 182089654 306741430 31540125 649328433 618907831 935667663 254690550 45942966 330875171 831012870 820128588 810901979 207205469 817536370 517810886 24384716 169897000 933825224 971373539 296690503 296149922 668197724 286814278 902180941 826779553 648478041 890257389 105849858 379823541 108221938 1034398 653530798 673851777 262794285 585847033 532858477 800655329 375808736 772375618 896713351 677560916 236447347 907251385 118262020 109366915 325493059 651612303 191360795 456746704 553146023 687519645 111851738 424796744 711369720 825517910 180494359 147216740 337996187 264738411 55492505 162128558 685872047 785037064 527410360 727344859 228766918 421301455 679224012 365616130 202342911 796080497 437409169 881434774 248955962 745198620 169349231 411153913 166332592 671509630 849833135 392253914 78925530 237553061 660293804 600736076 830866107 897763656 52608913 551351794 290969155 10563563 167341493 547714762 28424255 116580478 849503005 11091408 718097390 687744313 77913214 360804714 594787502 466280607 683439536 437582329 747772255 438219046 941217129 554925761 410154619 616961385 579506773 832696745 368494076 721289078 243422625 449767573 554570211 739078718 592657675 125428050 438513466 906405894 874861971 462848273 772902905 87292886 307224528 742051808 403696984 857036669 124668829 703325350 350052122 971496326 817407583 902922099 944426267 541434060 935083808 351977302 593273149 925799509 381571240 436706421 638703442 260159470 93451139 820939621 785729727 197650008 502744630 408344572 530062015 578888853 906533061 512627638 245207007 115266447 49135550 49886552 2540461 14521514 14444798 729385738 355940755 597668250 762838220 446560584 28683550 956797497 5219499 260992800 157154751 709326754 536455567 15791777 820082046 523074999 917171379 684732323 536470433 870920646 177465405 270905953 300119483 659627746 207274604 676901886 174066837 65801230 656955783 514009329 488301943 513386898 772334189 175591069 16498472 195942384 325701005 398288577 777424318 210457090 367294445 396671677 416321996 989814978 420072610 782139651 696529099 753497037 420277824 905329354 71482946 656657445 36412255 312894179 807319045 574423233 279421697 507135355 8121795 68127651 436509577 355255928 687982954 717479081 80419075 830912102 610119256 619060635 355312668 89746200 298195550 318764994 218573116 548411101 606762205 833256253 134156913 448832479 71913707 662410350 440608939 601167874 591368092 105316517 968532592 332598525 825610934 591229496 552188002 853481733 157117125 635489149 864382964 975760274 40621516 82098132 940155376 739784751 910123326 523724236 38131933 257200671 861097565 864216564 535088762 484263121 541794985 839268328 52803255 212190191 688682415 456877374 272993167 105443267 931710123 482902862 680181610 162085606 126931539 977910927 34637246 616446971 733762128 637067855 36861134 514395339 879157580 475863821 562537061 559165989 408288297 144199442 192815596 137476369 136685542 517329128 129449072 474145059 334775945 102413407 894517895 613868429 257652163 968859506 827216905 509527246 633907373 775270891 781325414 586991114 651517564 15847826 955903459 772304725 703579682 119751164 485214203 359150580 493006463 295427576 567290488 888529618 383531669 542086724 518307286 197837057 244688006 516305059 559076347 3510716 641097901 755791028 700344861 209536160 59169706 310058267 71099964 49409457 904642676 211042040 628400015 750299451 357105231 974213924 525603996 240383568 37980344 610069579 327694739 255100985 26031775 234484044 139574193 303614919 761623206 582765091 891007898 421885390 451315409 554689930 420458313 323043441 553310211 600900170 360393898 157908733 944411888 5135804 202803809 717701259 497475018 876097479 159350096 714581119 722602216 577242514 21729907 196862511 902859125 530911362 649716275 524270497 526563572 318778688 308299013 426222712 771151290 326217571 373424397 415748497 377340595 849433518 736718667 752947518 235753366 788265446 582189690 606302895 403900194 338777709 511472536 282380836 348229222 172510251 138465091 349572532 772085997 452517536 777936785 134244584 627572131 507119094 313177059 15529802 974873068 469050619 357827990 373996774 294327360 693337450 492827578 558621056 192100049 385959685 86017274 895802258 616646445 61746997 93566703 709031797 302616196 283627862 599543654 192619899 951937417 678709522 727459955 901051611 410619472 221660481 296933998 628096590 515349675 745882595 280198439 82640546 850287074 855160179 854362279 81289319 748500022 316926238 805244534 607146211 784395170 87561937 435341758 1642212 20268052 21018859 593577145 770893859 191952199 411620475 268304938 836790616 618846838 794621444 898655345 621821243 643475711 148832760 616431131 716132482 333764582 791889196 279950981 613193792 791593598 652897287 320212532 493928653 189873534 693033288 988483980 324879349 650118809 878872589 793741609 729069046 984185007 630306145 803043816 420284909 532962327 845208339 349113317 587267758 457376570 468575573 881893867 419246359 821058600 427584839 617852577 704229756 515539844 678606453 197395897 108897412 572172170 914197043 493010187 224622102 93163890 563269985 716871263 758427710 32631714 572261589 87265358 940483072 946549197 589136897 487894257 695905624 941029457 45941383 276081959 70021670 218873841 939764751 548427262 244539283 620048103 73651831 126511501 913083896 912415077 147735941 637998303 477348869 933127869 598987105 714992303 974684427 913225007 212279793 761739025 747817421 314486801 474805220 306360738 875616302 206129128 448122763 270789170 881113529 218378569 888657081 755211879 712134442 482422147 738841995 656782886 626543931 354995096 41760135 706467487 97014267 819180027 218446122 990731753 194647680 141694459 830060977 238283544 157081180 76347132 683773513 833281396 299103821 333275710 496994991 515757819 34353102 108580461 884225565 1592050 931872577 203209895 642770131 253054759 616690593 429591245 748025609 739313116 901592891 448819722 176266000 988434378 367404483 460791099 350785849 426758046 468597870 22723738 58560860 462733904 561497146 568458871 6446032 343963907 787340412 157384169 148672098 977450894 98694673 220468810 512296268 172794474 49914941 390841776 558555199 497261977 57483806 921794834 554962560 532460987 758350432 495094459 659775731 664204786 808848224 335150741 990221408 2581666 126600066 863619813 307209323 163762656 295005824 424068158 22437151 907031677 83357015 941156430 437699729 236164383 357277856 434886352 357955532 725954467 113332761 43658758 318357992 797223532 62410209 761362525 255932996 889632796 594234111 522418467 98344933 793595819 366699749 458787860 427658387 245850617 690551355 783321618 130165082 688641045 509834072 788980158 753975781 568872637 155551418 843470915 582151864 936572750 833872725 433751983 984186467 158940349 579122495 932860817 43403060 346628853 722618853 99136720 388262681 355277129 991221918 584889509 950794606 167238803 803082596 35449170 529082185 695165003 534609523 419078199 176211386 544229362 262150444 826615626 892295410 720552774 224231050 917435141 729388834 889747997 146291997 374727330 374442462 269055312 830623914 414575782 680323540 829646056 795514664 202364912 681013481 360821808 349226036 992301399 111537599 770577332 13044305 680896220 393198559 121820484 331572310 61752310 74525043 342272344 205268936 570788147 390379384 120721779 248813628 189190943 322206594 280779781 846507709 152163454 638468724 460478137 77153822 272987601 51794570 620873579 67091118 312612592 194353244 181398644 109579740 688339164 698538729 835542673 491881680 258852741 561675983 831832935 104527830 59363647 114139065 398703394 873414608 254892462 280075433 512844282 307990489 994398364 368221389 719867441 675287740 653753637 159245693 72724632 837655737 281650318 616786567 136507065 510983735 564819901 526907420 708662416 2756171 530982076 612092973 548203676 280012797 332999662 556798511 121033614 135496 713205230 516914229 514181663 439394221 141367449 593642897 471399530 867475021 936263889 123408379 86436687 786254879 877986730 929092313 336270876 768029493 583647181 10566450 125167718 420113878 811878673 585057941 949039831 613985750 859079251 643148347 128947532 826551166 588495976 430206542 134759201 50977686 520864087 326342615 836126755 366428760 97367546 33559669 914184991 407945909 917816465 546651772 54923760 806412111 74477069 636054618 870580679 205753996 160269937 823123384 220113775 273529821 968955265 581861262 442557507 377825337 536958143 90314451 528672267 784944226 858742030 52628977 565240140 511727389 578974519 786081924 347895393 88385474 755888136 41687433 684631622 184186213 877858846 733536438 48421925 34981683 539084964 104133048 562404819 865918624 117118536 791850076 862999327 736378879 662441888 141832209 553599832 297335318 866982632 486718067 725887788 687636744 193262976 918483303 958332305 361233807 715541623 84477150 391019110 755607284 292620431 476820045 305295871 957268450 272191750 811954651 777640565 429522938 337909138 365700956 907736896 834889003 580409884 797290644 44693550 242641700 146433596 564447211 88206886 486848794 477941463 382106963 848928822 980713373 981674660 867656160 99776524 818663732 149306736 181651270 304200553 982856329 35401950 121789250 462732011 613563488 53962186 285484561 192614520 775934975 654499041 697968228 38357367 132156186 403868416 537333929 514678614 209659592 683510696 969018786 501356631 760254299 307730875 535011826 541152180 602827863 477766848 571959164 665070767 261394384 614238913 178361821 670624425 31972771 918482479 836523584 625397597 448839492 643044205 776542463 263947012 202138881 419922731 379890123 508048417 770100673 262234349 750999959 961802250 280518138 375741626 978548156 528332323 175778984 620414524 966673385 696116396 753895530 186256747 178310966 916497669 253991535 762643075 536435462 2897207 858199690 745465807 309741244 740306555 61069248 451140471 510937076 287134797 739967329 774577972 133337882 996185184 498100608 807296557 499663 482062269 421878647 892805234 766790686 125381360 159160237 321947401 4063903 584400990 598088732 942691956 719823941 272561327 820360125 724867051 115696208 523989136 794378553 478841003 426964034 515888603 455198223 379757981 828015547 821182288 585035075 634691494 540860994 446745689 35448329 815455908 444336239 656692608 60654960 791687644 876729405 940502643 512954702 812853492 699375466 284690573 437633180 934533786 769595891 380837076 34430698 372944827 372042428 743016040 86153401 194908173 369919442 34656282 480736584 849832335 263778632 17511495 343492361 144328534 880353344 525504371 608100924 788620183 869279464 389730933 903259496 958061470 462902269 690163251 150895320 685596110 980505109 939535373 869751687 965128126 132942888 167696764 317562565 443578225 153876675 680526273 128131457 799084064 137833408 961521288 468634502 653947504 992104359 406248826 119186540 76806322 271475382 723296341 195856533 447086326 228232716 795929761 673321643 574757997 232223795 29210453 431439432 807042590 20189749 751068871 686942557 974811860 898041279 844712292 616401528 3226149 672083999 955890394 856274200 791867678 77936241 404170650 215499069 622708622 746024364 632187349 789777768 932083232 740164024 697613419 711703895 310937140 461592993 619990981 152483672 927030897 520488810 369603728 141438449 911265292 237883776 534684402 232499284 907554701 701327964 809350259 2757090 816709572 453503870 35851392 205417775 469123824 820606502 179288775 721739631 910952783 836913115 519863261 400245201 896809612 627462825 809434912 869867277 114445619 370462750 116840169 631335851 174080735 874873368 97830471 186910537 412485685 5497074 850865910 99558929 126993820 506418947 595646469 306279651 364532602 973602531 730244287 420422476 658056855 894705673 416718289 792393828 31555392 462944983 150168002 420419370 213832179 213957068 426045292 134943223 639134494 455447342 184703736 762748423 559192926 299002148 423096843 382233095 43686532 85663291 273501928 249235640 861483732 195503738 53423293 387174218 499339967 859065202 283161020 878575704 171789851 834046488 259655186 20196076 506003512 506068874 82311613 413073749 51881869 264791281 889915569 84488643 431658109 722706816 263763039 913100060 905903698 703150786 745123367 303559903 950503290 676929165 498781084 459344702 117632076 459995085 99883453 202638494 933774475 611666618 713575490 636609687 288528100 909634015 522423694 646366821 136848847 981301103 508125609 901697553 370318676 228101921 935355553 637458751 414525010 470418165 766100558 326732584 375618748 175816343 309188753 283539867 266674272 327287168 147494076 788989956 561868707 579747054 206355117 539409765 965420366 434739371 172555702 940287995 280458191 807061703 858199720 942371352 579738045 461862358 792985826 487960821 163047233 633862586 141122312 854062187 755243168 395392966 834114192 829463598 342279463 13563996 319668353 480524286 785429811 273286698 423325351 390052266 917470900 95530364 152671193 138390553 797141023 83097961 982954093 879574710 962112435 222214355 100997033 281071426 23447996 881192202 843774144 585562899 763064692 176108563 103052363 955082361 500623472 459537176 304423115 668890804 553657355 958469548 14854923 897543683 208122603 753383898 685835831 667426861 127564597 386905874 648922943 728560691 97162752 397048171 581320198 131410376 243016259 79091905 858482059 441311894 777371346 979362615 298322593 451236248 243301290 203648679 259420609 593866318 801750191 58155204 394751773 420452762 726615267 655404387 542296048 633090757 916295530 993315911 385540783 306782070 157763979 466411947 384264220 703049385 219230763 823667144 143816225 233970517 464771914 796632059 616190125 824613353 725076386 553602671 753007357 560365954 21669829 188903366 502290333 914425001 554130586 959552544 61377617 323980916 257544542 144541186 118967169 210258755 531090683 846149464 486526627 507374342 279584677 609761976 473739069 555064870 905205673 434640475 357644662 942509374 470819966 515555202 249917716 955196497 700512190 260045271 824370232 510214093 478549336 322914907 652763135 930502625 113742742 507950482 263000832 638377746 126805334 826397869 480456372 619381804 77174321 504580335 467341227 192327421 487822446 334137340 101692370 130730483 698516937 227478350 848727060 415784644 858681558 383546305 285350546 236539575 682311227 737798924 996677946 767612407 509335541 470221965 105294028 488074316 332201363 438010266 640634303 990824784 427387458 950078640 813864799 247927618 737839015 672942126 978350919 232192385 898171764 346567296 767019405 450468115 342089191 29881949 527339128 220447282 749482318 934352595 706727955 497394421 74620621 762826136 265190056 386002043 51711524 737503114 592744548 152367314 73434436 16825292 970730632 264750772 293442810 610131215 684847936 628560630 870537752 1411236 460007037 651498450 264834047 304519657 830867149 236701248 883858883 378312657 653254253 344619060 13096875 471523694 145628682 11371414 181409669 261628994 984824995 199257094 779364698 593656874 226931059 748675088 777606642 887727980 397984005 88970343 717132562 305438158 722967925 694009073 738654462 435676287 129834113 460264875 729437183 600009534 636752872 19146003 948824242 973654927 631527771 336328465 374835250 944679846 839779985 507852875 384608128 775232471 683982409 263389424 387572938 444125825 935890596 427942305 182200838 60619440 650825504 962707596 579568812 208602520 473500100 754172919 96628810 371972511 862018443 143692145 938592808 150994641 903124849 669708301 774084159 559307977 421149883 787419495 507930020 149547759 292725655 705047828 930798667 970952254 225586359 657229923 419316882 83976531 890528860 638795264 81414836 902185629 941665381 982456718 99595808 662694388 728304577 54854739 623848759 536837213 471954731 713634347 625169632 99770412 802858639 537931078 646604344 419039493 921796852 275021064 991444595 875113635 57943124 725333315 461019345 532888157 225484697 139523401 586885259 737599813 762527777 254748518 238167303 944939132 757433282 699668992 437795422 108391733 363270914 943496899 44048303 833519152 305839483 490157100 298588443 165506766 417932210 566923760 806124332 215652995 542286908 683952884 965010480 930484038 145837269 514734022 985422195 698566208 822108523 887863783 853530113 494401768 659796706 893234039 341584251 293092588 511160571 252385084 556201064 572909755 944307165 18069279 889956740 596231182 797831322 710403315 72804167 791523428 224453874 769935613 63114348 192267525 188736872 130201442 163837617 72253457 554257134 633533017 183008448 479991418 2450865 294693414 383180749 419147995 385487786 821389287 111449908 769473770 52020179 18416038 396660496 973857339 331191427 175594523 553630547 913356972 206287468 452511633 401722428 77315859 35160450 808662827 627978684 655715890 525725863 866463595 698748156 314994112 60706986 169800917 639118377 360382962 186003922 695327843 61192804 720743148 8779991 889090159 606528244 316328445 949168676 939709594 761523930 650231380 251462957 420760491 943145279 346365623 840905884 728525392 404247546 661528589 964017620 811132937 474989953 14965281 82937675 556173667 582661678 904923766 447039364 966846590 867424564 437562471 880192452 636675981 410927125 195818671 363530721 699516712 417059847 917669555 204041224 954490534 798561615 266831041 881315955 330749409 369439033 282540796 933335447 755032666 337055200 160766775 641705118 162512381 115336296 953742913 66944447 118604738 592497887 635455355 122470359 152410160 441320121 529141074 92151398 884643856 813441820 754136838 9142739 539659722 713334492 60863307 960130961 277742633 763957946 556321968 370569832 605269218 505546930 545057141 34348657 805074139 283702655 204425788 409394617 195681798 313430413 497653136 948580726 60679039 374083328 924602542 680061420 96413198 634205340 992319706 403608593 820531927 457825310 84676875 271317499 238910557 420301765 357101376 459528448 737033878 98198345 938600415 710169517 81354354 122232881 49322501 702980434 336410002 822125942 960639128 801805180 857091659 719088719 546675864 168608779 406295303 23369622 696686423 944568637 591370751 624201177 291200648 923997378 420411604 440167321 654927063 308144331 981502670 423590988 201768551 690691033 589431020 756564216 564792024 619197585 436705036 309318271 649757937 789597798 162055142 519864616 715930551 884701560 338868829 664430385 854489456 536229264 710937972 610100087 593329807 369449217 364659231 386460113 132910164 520044772 667183044 863520031 510823307 712410830 200662211 44638742 316365694 679194835 278024242 761019580 488178681 555746580 577473249 685996344 292864118 719351592 408309179 750065319 222528423 298792912 417781960 165273766 432635666 100014825 747989322 528446097 347410590 794759877 331406184 521727314 657181177 512644917 411261842 314948837 934298425 981165326 770833360 231500325 100835272 439571663 111940360 555840750 823374321 780349984 327319278 858387670 204502603 630083457 138685830 580152834 789244001 823009166 410077509 798905761 8910157 316933296 194344299 458918432 16623158 62057773 252586079 785974602 816722123 169592888 891045664 502836104 676152717 675610743 759370163 94025241 66978301 346186961 713916937 136194998 879688318 426232963 9550325 259306332 238244947 329156234 521109574 178422450 577268149 108514542 280356353 508916425 432951677 375628544 623079981 949255571 338176621 423056790 190647669 18247803 546119874 102211929 836513202 151875135 165375343 30238118 531990991 437334693 361730591 347767524 868120043 172207183 365306339 178608510 85100889 884992476 707532854 768648470 199136257 875493890 614687100 802239950 322139642 815260523 151932269 46860087 930363534 396143987 28167834 326978774 593051673 873959214 958341311 266432130 783525999 236290084 909991986 321195532 540754604 477027445 163563905 750459281 129469173 77612440 699566820 845186665 980434149 219325688 272191416 126430286 966346562 209638455 334436200 54472574 429078644 89859712 501022068 997000199 264772205 633649470 662358675 726182728 627882549 935296198 234502295 477215774 753779660 27577438 286659371 520951593 586638770 919237165 782350320 587093088 571076950 404337100 451719192 987997943 398744111 404729639 738375190 320024030 458422699 328725584 61635447 211384193 679789480 547625581 97476964 420110676 644500750 933854808 426690746 747263918 470849110 419199828 917767221 263901907 895414088 268743940 425329219 841835297 686635462 719768722 875076681 1322448 997959928 464010273 930862650 542893833 318640721 334231742 613821595 718124535 137150767 781036948 436302674 750378307 305055831 714695837 98997915 336540757 985722137 211773820 166996483 423890663 833980215 699788368 206751784 432884147 593192467 960890611 977593242 848119765 459877874 572380001 136854638 219171151 894653614 439096134 750418444 75650524 57223706 722228256 620745114 339640749 535110151 692862863 814478991 161180955 601238204 57086199 359939857 66126554 246714466 186093956 609325066 544082582 515823521 757751391 148907988 329662637 353655437 214337460 509438029 207693618 981608116 930035262 902656357 739030980 277448505 62721088 750531068 510187363 532163030 215264477 725398195 750347466 592446198 35299924 782139861 696737138 848923113 292086574 9647404 4833834 250852356 876271849 559436408 91432335 270497586 190372841 599263076 779043475 462063532 392195515 76302359 431186902 925329346 251470881 827109467 804673599 567251938 462259 197842222 966884480 412399792 443264826 771687330 870851960 922900543 366402937 975469627 346174259 887801390 913426781 782491884 8171129 584107257 122624263 930404135 647126744 488863746 645726829 921478390 907765093 65245998 864784091 987041471 856791282 524616288 372652018 791433379 348655377 440801190 384460415 47396895 804199583 918698578 542523402 689892291 358231210 953851015 590944649 103462934 696374345 435090749 815049006 402488071 974284358 552802962 12983985 692234111 483719300 967313813 875723928 457503649 62108909 18887485 948318633 406545429 115393995 740751632 646025721 130778018 118162764 869755235 16048518 9966843 836242909 920486338 961408584 447752059 663074807 822783303 144013602 214530895 298245123 434280482 746807802 292817935 385473043 459253923 146094280 867833237 666262026 156205976 827988043 734365459 49034970 538742264 974748902 314165820 117268340 989285659 791009748 716590657 401030389 78360924 18599698 327320453 682548667 38207278 416938184 358576968 884864650 667011282 150884828 278300405 225434377 798005845 23699415 807792946 2932701 772286873 913734723 229767938 46561630 603775036 765099679 35741794 691939270 731104719 214646278 54068129 144911241 766705545 848084632 945167084 32078965 236082756 883500628 568137056 701260020 734926976 585220108 391535992 397772984 726108364 270189890 984600633 424414162 833371637 215445254 707071241 711114966 40909782 400386556 186240896 171197433 300144241 764971463 481409935 594118454 953537939 48724114 502008427 94608711 550255090 781847656 795242408 549245664 156800968 346806529 848524802 928514002 13691824 511064874 873981377 622482864 46611113 886798145 387578571 246686624 802956572 96651687 407625666 594607261 471680597 573536823 808298144 493419371 368073791 37184101 960024571 292739090 8223363 986528155 580807389 387612970 19396255 360020257 145261567 37993743 796741249 951053617 56977775 106079634 420327050 753589536 660487897 64078163 569205878 270597551 998317733 970025777 504121258 654151770 252465866 719231532 263583747 672353149 924957936 874152549 47899990 499081325 481433137 864018089 712281838 149547131 915769017 844980071 791828284 978198732 74809164 967897651 269143513 429590719 425810754 177752902 608125916 3973124 452577804 466939295 485662528 560394602 876235443 799147720 889104563 66610861 692809973 715372419 266840594 646011485 778170261 990746619 194020602 260280744 430658056 145366919 878170839 4813461 444019306 590367152 586782980 655073316 431306684 645885756 603280913 409220546 132155467 136529392 176085863 984099686 105455008 574696409 402195749 44281878 304991470 61437831 668592149 26138327 673768248 391932898 438294714 511212665 948140597 952078752 995732848 517443168 194524294 132587549 260409067 115011763 938161451 776344652 308409149 814138625 54612263 183079210 739229270 888910798 636831688 834179547 150525815 249545617 730096968 463167486 101402852 102035833 422858693 789518360 33587145 882764657 591178809 904089285 518531334 726889681 664390588 885957789 535505148 807086104 297082631 712342753 732353968 643279787 504825351 448306503 452638206 32916686 132472411 626387120 464542385 949948903 599929348 4288129 839470229 622228715 589000158 76884046 313843868 596207379 633509978 415842694 459371290 852071586 108209117 712430191 371084669 540707433 478848709 792519982 60234020 19511106 899058160 598526815 719239849 71991979 690107561 112356733 532285321 672217329 77992952 729563352 998326611 755075552 301500532 985559757 138258095 609632404 478449643 185437189 540712061 862399087 71130237 754481620 48764921 133504366 333537051 941208499 931091466 236375759 201544487 605138989 599741135 143781629 85767856 139798144 834707186 508465512 946202336 870063064 83296993 177216514 958344897 483491931 49927401 337527691 559469204 42727873 733841682 834349055 517071733 73689409 368185790 780817597 31711907 532744569 327017710 315132458 546928833 720586786 616789580 421604539 320305655 865610566 882501155 774489333 972893138 718634688 51350552 898328072 964681148 789147234 733370011 381365937 485113478 845706134 74984660 305511664 709112355 961371763 885144691 170428829 547988204 397432680 125326290 518291870 791605580 643376549 474136107 99661797 579986968 776998174 847005137 111467704 902269381 517077777 820855776 57826027 373788676 65113788 168092520 252141630 328398810 624661746 895760902 301896277 93653774 322032371 903244287 825081143 331754446 356067037 189563327 679777188 873709225 598944545 326014030 815286643 276161747 205294012 206131256 358573982 706092032 569029127 865058534 381577883 178190463 544131686 246580250 894525876 301539924 85789228 68934388 900422830 981439982 309492012 965486511 901227693 439222639 444219033 240001482 528363336 650306512 780645210 306423463 492109510 606032772 353821619 781159085 98413257 804396489 861242917 227989670 739102374 833947834 411154989 128918462 321056897 875095970 191822103 189505723 19458303 285214116 654838889 601195179 163189291 815882227 26532234 934701274 503398608 447923889 680825650 840332256 938177037 385630806 379100167 329085288 72678046 779892200 816421855 323261095 374116346 249927404 81744509 389835203 487170774 966603753 173953921 794019096 549682962 35151275 16182643 690753110 561599183 433733094 918780112 277982844 234724959 679087381 837807354 709721258 891122468 466316557 530459801 435192019 594351137 431933146 382593483 995030640 839264087 328885668 98291296 610638949 242439039 436486503 190108706 555306656 937641558 791749516 488985934 152420583 125854683 30325629 922973938 740852249 287843793 948430935 614353073 429417956 41671154 815370884 968641284 474784083 840252629 151838396 626716606 238160063 147611827 751931068 994056243 304330592 426293192 117595767 863126056 49889357 53704414 659652089 163389277 801041576 880495350 726291923 287558149 92362115 664954162 70613766 940398906 35120264 139642090 568258042 112838422 980673871 254770091 803942969 632201317 861550274 46029704 46890443 363980971 914937714 895442164 881266244 630008590 586869871 257183653 768613081 220185925 329800444 801864805 908009090 768100650 764997935 814441067 733107839 191910217 76755370 115889564 502252996 420598540 177044343 626880153 263157645 385435041 48177286 201040247 39096363 660090334 641769585 278722195 514378536 361447047 925860438 703795300 437803563 93878963 534539690 223918268 932261369 788861598 734447820 436822427 207481671 476322479 687435442 207796485 598388377 877658359 390519105 271594429 417112784 905357463 444130867 129835447 980339340 426406242 338168728 828664064 649923089 618165494 729727315 814403001 601361168 545743373 740097506 244704347 236137393 677758245 252157488 179344602 292140146 28750609 282841398 696270718 360067506 59720079 32065099 885673858 920310789 846390942 242150402 677008123 501695117 643525463 652156827 252313374 898711343 212042422 656549624 784683543 691515474 788265998 110040958 431743919 579028489 146525860 770617519 740159589 208629637 325149381 854668104 663136687 909758204 712341485 62688213 674800988 226528227 978178673 370254978 329871071 407160299 791172672 967676060 651713987 37334963 878442544 678455437 388669258 75802797 967070461 338075923 360791125 826887314 790171994 426755462 991271103 57050839 607785117 266207222 900025418 664948499 478687892 743977614 752942354 287204706 817454974 812335309 945189166 580602572 40759972 70392763 255861984 38171980 21745565 804223876 281711132 907788686 612250394 564953739 835792702 255345820 590330337 811554087 506767056 98458409 946443003 691672039 965123954 565130514 4733002 204599553 17118260 838711001 31738737 870708009 689563521 403733831 816816101 460157667 599147573 397632948 692037584 527699153 173680069 169516527 157592727 901042790 17184095 578134962 761784966 388673405 102089226 683815681 179431037 623158894 366926787 703798258 89709865 206622847 267491305 539859029 483383645 351729191 717176679 377072814 416685985 774902123 31898057 868701082 374640658 257965123 945935264 885750468 436231080 640711945 406654749 381662937 120152728 590998047 274688958 23793313 965009221 660263594 45782696 829361659 147589043 158625312 454835700 740670067 121201448 881978869 853137776 814817188 418305125 108577044 128741828 41696304 370540180 501395263 244437641 516869102 835503640 158446233 481659550 573606305 242285658 140750120 740472970 430741920 289993230 625753907 631163430 851071345 778132579 207466539 794921057 571455161 113891226 824156366 154412491 299585629 923369027 951659996 706683781 774813761 559775624 110938611 808336370 505452318 348492496 401090434 665159938 215658341 306536021 895785640 162372741 280471778 708296091 25888416 549264299 670054655 79212790 817518072 919332956 578440479 414923873 527950283 456387217 334983408 339083272 10223537 439752552 537750310 864233685 183955607 387152248 714407719 142733458 345174990 880492941 155049678 105990676 291651479 433052499 800955555 861011467 874113116 974846701 881397288 45727976 171541217 159899892 469162841 631706894 978374216 583481882 447446249 562081933 745101785 966754260 992819516 971813576 7609528 785259397 79521956 10418984 63463788 167740266 639799199 163999574 819872468 837566996 306779551 346831149 182424102 651732081 847371626 341908262 959132748 900443979 361672750 721395275 986501327 193085773 578723948 952866379 841094040 555009967 881549007 640085169 864078657 274796714 40698003 395778217 94118664 649509518 891058905 257255258 856967845 963187601 286794716 34368374 456642900 804945447 72700415 321846856 369875220 437548737 475148386 388327138 571028935 537582229 157116352 21672922 720227158 818526758 330870539 930229036 548632487 230272680 158072486 938181629 922318235 245183915 959516114 748925961 943277011 560639227 597175076 404895586 863972946 104189226 148932567 244035301 916302914 903565096 666126856 650891803 608148653 991217026 190927414 652779517 290849373 303727652 649672974 162745741 779152970 735909624 344732128 568662835 538405932 499938737 502869036 803710432 348031908 769597214 767994108 643536682 2437302 799712183 24674413 170287054 115553697 490310077 38392310 75829325 601404578 386282270 340198544 676318982 766696202 338854598 152982183 926948655 623725133 130060901 843229979 105172713 664193372 820291484 50321157 505277926 387381808 895425754 532296046 898061635 937179118 429967491 404788480 103580968 847543264 375791689 601863786 842307938 397768130 651764106 987414814 511349856 228583858 455136761 420130080 765236487 721447490 307206525 498288013 100926214 653147556 335200002 456383269 934720301 769524622 59846427 308762478 449322285 682435695 152551707 745802999 82477246 724496326 822769393 271585694 356900521 627085606 174815713 907593759 186433529 603408285 125593001 919450155 448684845 629981095 869489887 879725561 634396814 53057789 941604849 45247035 309653476 412637097 769861665 552400053 635831707 263460708 933610716 984895211 473764486 497467335 817214427 79460175 685832122 479337028 27145198 596234475 416370194 256802702 77864159 924537951 613591065 394117888 690817198 175002152 490459993 662627767 618123659 524146198 169372574 383223540 970586702 663621815 106138928 441945262 767582745 295095443 430397411 785210463 780874240 414959666 809494241 591922547 226809898 738444565 940166077 627727828 129374446 856450297 248840916 660191433 498647356 904821748 136325370 802119771 609251438 416131530 347429559 987506423 592754561 251852481 600810169 551302816 457499053 261682304 661069678 931299144 777666768 705421908 762402236 20456988 485439317 4364751 477575242 720264330 832583930 895882338 762893826 410682720 996950076 816354492 41277579 191902047 208579994 512759496 178337414 121672620 285620762 303424426 180761799 493633752 701584486 640234258 832761364 880467996 98535342 376050413 528240712 26046881 748783094 396535592 155012951 508580297 201747688 83434168 943882946 167844464 427735474 682483656 93339209 3545427 51787081 252777072 710790913 269025101 825560999 541674958 271607992 546385750 937662926 311051120 541106623 22135818 984171053 892509544 971942485 139457288 372154489 78289262 262791940 47030962 797618840 218770534 316522435 298375701 902776899 408487284 539970156 216537569 642169701 622662690 586226473 622254145 243621381 860973898 14992032 287920593 418075423 188912987 966222831 250827550 736076626 136045789 329886908 50443283 685496784 987847008 18188379 687307642 506358380 21528254 949567499 872179910 754229482 340067864 338462393 552860242 412179933 390766897 95637995 500892326 465561383 116749129 260145087 544746689 991492444 921665832 987894363 704633654 801662245 806320537 598584092 456412735 343473604 843933743 53987539 413465675 7757120 861953600 885639415 95624906 491556028 795764043 937195228 864940810 831332698 998431175 806043478 208242845 274674757 109510642 862046924 718408143 609669479 201150227 514704424 428075907 120364367 684780238 478023649 494836912 615302767 544242908 626381567 546415059 42198817 737501964 203170746 678601124 604719300 482364309 413325856 4934653 474533482 560687890 512861332 101305618 661454941 693354980 417799791 458837780 655133588 830776322 797515541 319083768 530962367 28615430 955727332 814590431 639385556 747803609 925909080 671598582 319895711 103637146 249151512 420081723 400842386 325569821 633548786 539708737 924950434 652418438 857353556 311987695 918636509 987373624 584388360 345941777 336652922 522832146 569063821 23688056 323494259 874704317 276471507 30657492 790987917 50909860 926794369 972574964 796343595 435610868 38573848 202691847 560378481 830311370 712355498 96004664 751232439 782058086 566934442 858477993 812070574 473464885 558984104 629319285 78952385 957804225 786061707 390826162 29853808 537548657 308552353 29965303 524327967 832060582 976602503 221261878 291779591 702100001 475861615 792704970 956600402 7515568 105839491 639385279 790738082 202274761 983008638 268831492 562806745 421431696 412379853 612949843 771550371 835287284 400873154 559723156 162721600 603017481 879240145 169386811 779617924 125024315 628125577 435986371 223982898 248642659 543456944 278056670 802472800 658208005 954198827 347487683 337259908 866986111 612037955 534553111 867908584 202665976 102609055 540199232 59449527 546059285 322375554 455021415 119059988 418427491 784379938 726710515 976423505 145190500 888918701 443589184 357552861 581306046 251668093 266646931 447338658 840362150 170857495 234272591 506814557 650254630 639261273 694498925 556804062 839263583 6146939 774458694 919858483 319564861 169646298 505346591 144645094 496144321 718586905 675243526 286830567 520260316 642469116 105565992 283876203 215649005 223098266 624470538 314933021 174405855 770820877 149321339 167901969 218806801 59267346 683241275 808900004 66951591 214219850 216346475 562383129 66871760 384134388 351550228 201811249 653663058 60598830 390520104 790386780 452332623 453327608 944774687 342161935 626567305 928667081 530683518 539964623 532125166 597609938 457307040 74718365 384563616 391012119 768615313 721283132 48191494 510428949 203228944 857900237 560823120 701327828 873809745 154256469 299727930 184889001 673238959 152230947 294239158 659173785 546788900 28637645 909895228 775084249 21761154 206129978 815288935 634211257 161474144 297187884 669343723 275071893 148186487 582091954 441024579 426922427 85514351 564454297 209930576 65479750 473110296 145354618 955958707 45600822 857099867 222945387 170569984 319013671 312978445 950084062 853580292 337363462 864230124 469239294 142814791 292481174 93662386 928117569 814490500 354005140 84793240 688915958 552966835 567608866 68193677 188238397 92310932 913964631 485592705 258896077 599513415 363195227 396986625 42674771 333761380 153970444 299880109 532571260 25799001 781686445 32103930 554941636 136184861 52081528 271856489 836271152 304587349 181681178 149605559 388054016 72031164 445390932 826367926 90233539 309262763 693795130 805774264 174945826 861047146 340472908 943757251 310713774 182886273 523466785 211929248 550572060 40199968 490004879 613363145 59500733 500872699 289382106 126040857 101424423 272272192 906910803 485808640 448214425 299117067 655847338 885367606 318344986 988671510 169755900 258714581 672024567 688520809 389518898 254064098 221467526 652879237 737084538 36868098 238077327 220004813 834929165 308882683 36485028 504614781 170663333 18097639 192865454 716444140 682939170 676439631 752514668 515936012 701770934 789906786 548927168 37679519 454068567 450276914 352239009 757596874 423543209 852543718 173260384 62075648 491534567 860475843 888946097 138287356 804904335 761942339 927015955 754227727 282483674 777454009 162087452 51433125 198488783 584111826 515760890 779120284 422634286 562242614 562046490 201760983 769230192 718604970 88287242 277239106 531882505 150272104 170495230 709141806 201248906 528080897 724145694 964162078 884961521 278728630 960709677 345871871 404868564 952573552 626436801 581037714 395109028 409287489 512768232 464937935 951855040 208651294 702306403 956532266 989936552 930168739 266475368 821670707 96258549 96432898 746929026 974664778 687001689 599094654 622963831 343517699 664794590 958448571 905819921 428655845 942323489 418659154 454036694 655610891 62117655 865501685 261762807 952788184 926503119 148758327 588322883 162683933 302818404 796900516 865717462 303612533 865877250 963158383 101443209 138990098 518618746 288394580 281043439 561127723 200319117 923953167 361242218 69728912 604171463 470291832 849037800 761890888 604625072 821155837 294085204 115725644 166184861 849001475 494259247 970851705 792886277 168055942 717817392 721638154 385991874 191694396 15140739 843394475 122733795 441921034 681505757 838323940 130642139 620664647 144940633 366458268 346125751 702824134 417862468 234676036 529112058 472860891 320102736 876776362 114153716 971837789 631773549 8455159 502957353 347364797 712466978 526540450 282947448 986821164 889518480 586064203 567283138 146983503 762411377 178030594 224505257 354534095 888844712 762617291 47614759 573904140 320650103 858489832 344905140 780452339 632449046 702370401 577780544 904422914 886336630 424066625 427795529 5647151 398422251 237937500 926263551 11350024 278898708 241595936 248771209 536002347 286185881 290851091 12223429 8861780 215286695 873801675 122939118 507747999 368311726 472331042 827380139 866640750 363566722 335841207 276971400 591787318 770128910 968679424 785800323 141564161 647706017 812021774 369627001 422711544 6199948 728186753 169568936 289101879 597437358 525101708 312848293 695859116 332785477 370295689 11640701 998262405 712375837 963554590 644532794 738980631 935164911 744290301 940796485 9383620 417698638 710910392 941584488 805743978 7169194 893316074 682770740 160001739 519564569 720624414 215268883 451620304 264747497 442466188 817175529 903555529 663332470 585216517 829928093 978786770 180761985 809665511 240846866 348769713 340293586 515253211 517505734 141303828 186841720 976263122 834405654 269976258 967633516 168531271 127762609 189378968 438027465 160275696 904722612 92131981 568623564 860303742 481774696 389368072 685710244 707773391 742069295 106431868 137324810 700015751 612553675 941290278 926648566 109154870 379030976 541330615 555103583 771511603 684059763 531174981 232646356 735815545 125287232 236528104 996443425 97578178 197097062 847416861 166230801 979568322 74545748 988443233 10059986 285253659 33062783 438276829 556767390 783378061 869928030 132728993 855329602 800548671 409748323 339140419 314977772 742781162 92399656 22506100 983589617 518122930 81162545 475438980 417776197 291110189 166315461 331071658 262414654 321029946 991461913 226270581 544023200 775299926 536260415 147748196 648464776 904576567 562121363 236354388 535342469 714595718 819865346 29823911 271714840 827209556 571006689 731994054 220765232 845555771 782080113 802753043 154379094 789342884 961793197 401225654 757420750 391339873 333789790 551434300 979431284 344576905 696583464 47385162 661332541 370985765 266221761 463318638 428953404 480762347 285137498 399170352 449780889 100812311 354384887 575687116 807231222 698360063 258741729 736159281 888318622 516818219 672833991 682263608 580825216 742965741 475652253 115686811 275585264 588434094 304599607 577552363 686196540 417271213 111502851 358287289 659785089 551856287 649327450 838116270 925996323 673635887 219572151 886454296 271751700 86755183 702718572 76812154 908920346 88824089 712879551 980518888 850298821 947869837 922391208 509838675 462811365 294942095 226088216 805478102 584018852 762437717 834646068 944645032 83808348 415890710 104112868 700069112 623698582 22017097 136427342 705615305 893583777 994851700 318075117 216461610 579009065 39338651 493985692 146844327 620273920 460255259 649346752 888326728 259396550 309669579 888800743 727377053 79084971 804461993 380167633 75232519 243834184 527799524 206583320 196008097 707092938 850173004 84200878 480484790 919286927 138664665 171859669 85965675 145455795 853727649 668420807 31202017 154867859 373131812 766720220 310047821 18760210 772401462 985182261 32142504 437691484 538067131 765393716 430213315 283044191 668792193 315875641 207289932 238860219 613383592 522395384 600374525 980703546 741317611 331166671 90726125 560403435 312926011 812673990 376765793 464688587 427812369 211512949 704022756 368411629 8799776 880570022 430098151 403779132 913961227 714184537 699841069 419762402 379407540 244908222 486592971 288660296 955929725 547697271 553622454 615989631 809430966 738851014 712405851 844589872 426038850 680689385 618375599 967670005 583667631 601276762 229694890 268259897 20391090 104038131 79902311 664465632 427067481 643509416 318004060 160444723 985568254 907731764 432997671 563075622 986321479 648972487 766642587 413891849 787200457 627495590 994546829 961902080 950651336 329476703 129585626 856505338 246366215 402035780 188240208 247012451 666763465 138311695 806042033 57225004 588726985 926210333 896203509 564226252 348902957 35485532 445996219 213437601 804341088 410044166 763261291 145258316 460851020 698912998 493025971 674425340 553469542 821974274 32504318 604284838 392477169 702651202 23289602 456660283 139435185 537616109 102834384 417865372 125960791 214889795 93900354 47467758 169684746 667300008 941698735 587568216 592538893 876000802 569686149 454308527 903738227 676682075 933504113 987100953 941210629 477868420 874508166 183892822 829395189 115966524 901475763 347450187 394548206 967746990 545655356 855829412 245809549 766033804 839134140 668042617 134480367 756775534 954724625 340568577 137830428 661735863 549711910 876118538 804239714 90533608 751734480 617730094 44404722 829682380 234089439 765581049 378787914 464227844 545102329 983429887 568989179 488065647 126066111 624422366 929217391 159149768 182153549 458589241 497416015 834135555 878660835 353423636 317286534 723603869 165956201 445905592 533168342 642587525 221142371 34571884 779748742 960243690 461903924 710344375 136106199 924676418 257021074 706381705 935852605 178013092 890761529 646806536 803224703 183979297 900883651 255538695 619858690 530767498 954075342 133566225 941018332 981977312 965529538 839106786 110339359 314495128 903601332 722052187 839917133 614833997 455934748 856440676 808065954 835704649 194735750 620469548 925622418 801703811 302132545 277834408 631820962 195338340 492908186 275406500 823305833 86339778 591469487 680722308 693018283 667317906 531174418 604479402 645976907 840456096 890547072 513355333 399499651 566640470 63081530 262617914 363062501 362073879 493893997 668812074 86789559 530622067 483498949 187458817 935524407 524077140 222052322 457017050 855512175 156952430 509215896 998176844 394555368 471616 550017681 614847103 393648842 609640438 755628879 669832112 862579481 312790662 337101885 782243328 929778461 117914907 762214054 23628436 557372112 816844674 635449864 288780912 181344634 695034519 945305098 988521040 786572764 331889002 226526950 402473130 739575141 910189720 435447804 991324520 269567920 844915366 216165201 349166148 90462276 373259513 475457545 427274316 371764045 860498215 590821098 430951518 987380451 234374708 652607458 770680037 791224910 788022525 943027932 854307498 49038645 953485744 388946997 264161967 774454497 75364274 810626812 436376059 607214171 506443486 635965901 475712715 333479371 955448585 852921694 131420521 808301801 105565120 950754458 931730903 222684375 759696716 148863138 245375820 795257667 298782910 145576842 212366341 716748649 392522769 612347207 559929180 882232409 496977457 538276020 476362010 236261142 626734423 122210674 563032859 518687495 688037908 649163101 926272740 769607424 737445197 298491047 592118801 266597476 516224843 463178489 421570219 875083570 781354156 991839623 617098651 961081251 926451845 371387327 688117376 540466841 836836586 680400901 211260708 49762370 692626611 946619719 208043493 323411709 863609295 302304270 412925758 328835970 918413154 211576535 852526913 65948724 602280180 297815371 693145508 996597349 607571174 186062370 349741100 911779895 508328616 264669153 82315907 420547791 662452357 302178267 428110975 482477349 131248642 607152724 434007063 819816090 252056999 992789729 677608284 226076507 787624160 137622582 168421520 117474305 327415151 137725654 942423054 401145689 953185515 927335026 863515145 50265433 244275616 25285840 541499717 538229078 9052378 256930493 922461909 636797950 799808998 64827519 934424092 749220041 819643786 190615081 849203816 985069180 667763847 598779532 189513550 337758016 110697796 889510923 78510582 219027650 902678361 80623556 354187131 100715894 7948554 955298045 728477912 57937191 500454516 472549437 733873018 895478567 319466198 157153351 594438415 981791372 536579181 837986568 295654666 887177929 506590401 134093326 35100197 599167391 807171581 254778616 468266956 991443673 104770114 34639945 174468562 645266155 431855578 220870455 990760230 716121029 596993549 502951017 296115327 311850602 558657669 255238584 607904417 257962917 309847497 789176745 229729603 755675042 233808854 907813164 457993081 627975953 390473889 428041574 735070823 361907360 366561544 667061373 179683770 128522866 87644365 356475354 182559812 164337768 818317271 690418468 894791650 905657638 793312676 584236380 480963050 255498044 68554688 604824785 255749194 461627225 179349188 651641326 555638791 323773077 171640095 674701128 539216097 345656933 104841625 208817834 472313093 796970295 541421086 538460837 774439676 582227864 787242968 606610908 185131717 532646450 252604493 190369855 283116352 670284493 949853238 64623783 625004715 87137886 827529272 778523842 644243598 971841108 933902844 63056766 979774340 640228347 632708083 268173508 771056635 556722850 336057420 233431313 536505648 920548493 679159058 261812187 459897640 78256218 355401449 214043262 732009234 540307721 833069327 749642417 970625266 700700391 708749113 186681000 714714782 610737243 820575306 678512474 164950264 728606389 537581847 154001427 748855392 959499413 116040345 378429011 982844685 139043358 277637011 958955283 520362395 662246161 612943202 580861672 25768170 174003520 283076088 699617040 332847342 270600318 311579134 980862337 905256863 658339230 819060675 105433295 354221244 253138319 473205901 610550206 749594997 382274600 971029015 963924863 307720373 10512427 911596920 658979142 663854290 143838386 101025189 592448685 480132716 946042841 256801806 981245147 665951110 912228437 151591244 346696971 879007233 591694299 171806855 261092900 589602606 20786042 728799078 135977623 411783245 21160977 518992627 465505816 137873361 137408907 771795361 269326983 407840367 488162880 390007571 596336690 799496145 184165780 966359410 244778590 251390898 113488319 70012438 169950766 724209009 19073974 948097941 133226829 864943380 169658773 690741971 582966075 951676466 548770622 724792137 148825025 338385062 957322266 916518177 274409241 77988964 421370148 373485342 869914538 448465506 197676851 309233403 740317425 486169863 536654398 298559829 868055085 354550791 381143687 9650876 626101500 784178402 326278281 310337462 545084071 397549773 772760073 471534381 995459057 508050538 880560137 267566616 339396886 743190180 147408333 860000036 376626205 802547417 909939649 410999873 174608022 312150111 446214914 740649821 527053651 410060851 257982231 787934813 656289393 539781550 265541747 157649228 484333011 922914426 351163448 379808000 892990761 28622745 375796646 674957255 20998951 637630388 294588919 368977686 57907701 464970756 949972035 369084832 776949743 359146497 310978851 543068046 127847875 883030381 636375085 32191526 932943916 262880212 278376285 732627660 959962975 442379492 561074619 601279249 318409621 344551512 221059070 276035759 737330308 663339035 738906711 607640186 565697645 384048655 51175408 563493338 41008189 648870117 297758052 384694975 31256217 566103168 825554114 844200045 312814299 518611787 852939496 365710953 801298656 442009563 848806288 608915624 506171659 617609421 724092259 544206683 583359712 561101552 962810970 128796052 830994388 828591543 554286015 18690781 203802015 316596581 872212709 96107878 348745619 235323277 270995698 197650720 804122759 763613000 439155350 643709748 98891437 686036293 404672099 689079656 567797220 45689493 64894282 787683788 373021228 37888657 103097589 441227496 216027959 300753892 374297179 34314475 537194615 149733943 394207537 92721456 6757063 421131143 743973542 428485697 569033342 615680853 422769259 385665690 213248109 683063583 381400114 847321632 83805895 409927551 441897521 182595444 673690733 831384086 627768566 571326694 403329696 444564728 247889042 558061887 320878902 94510881 768586258 745887012 579805068 981731758 299430846 630902968 93189588 491716124 19070133 495997448 915624089 446582271 813005300 902983044 635574874 199684884 207225255 344271129 922332274 101798222 468287246 454303523 205551750 311240774 533997261 677256010 851825213 184413303 137677502 464148433 663525069 22353312 565813886 681138060 85035172 435064557 988745418 55080341 991901991 18150310 636860240 263772733 231883896 493441525 419327785 192092373 386056883 786482279 72046129 15974099 417672592 88857563 176393509 760307733 160430871 14890243 901157405 724573740 841909496 395196805 587409077 336812789 330412475 892314221 852352438 174837055 848232358 562886256 379101680 62446841 49613812 315677219 703361089 433490644 230499026 669504272 683720370 265515681 562066889 322362082 794376459 357699076 481606731 165745281 241498172 178815137 861980930 591740399 319763503 926191585 315460664 123254739 919537230 265120417 193716127 998003820 344583630 904095585 80897305 142219261 372246203 706435249 802218276 927655444 593550147 553625341 353091707 247075412 261626708 630820430 967282246 119945808 265878946 942731298 989794793 15678822 883666866 522577805 264164705 233091518 548126287 245955779 634696345 594429089 557588493 877742736 644532376 159135571 548267784 883147795 475654083 630069440 145358236 715773044 370787762 338901445 662470993 462489769 82440291 144976299 58775926 237912484 975659003 398290235 492450079 229767120 981151861 601420630 772944450 750112909 985293050 500330884 636052109 349399661 629361044 287178522 36286981 320282633 449668343 705580206 608740433 107998960 851259045 254209558 393233727 958823085 807609735 59029514 762011701 625675883 151129432 206242473 779664017 213302118 11987050 530896679 294232652 456269024 752913203 138889265 301661798 992023811 928452502 6121523 907404920 757303122 934194981 164773141 928125334 942238771 85026318 853202997 426078029 282160768 856481266 714104805 442327177 591619154 144830370 467164953 19323537 804136724 310551773 724547723 496192518 522587981 625362917 839753215 694550882 427550102 546473783 712851894 231777544 75013695 911267572 933494180 451627030 926013030 913636714 257345748 734602484 926723365 563897906 754846832 932872999 483518930 327511479 192794568 123828834 853040855 724246974 676708478 682891962 59581274 203883949 457834270 281356186 789159676 207808667 405138867 250474550 763448488 971159617 263584600 569632505 506834855 79547200 355537877 408950188 692642549 701576018 255293656 857604729 814777401 498092509 284480783 495441204 348044426 985388392 427128268 928876258 75206539 347127161 709576166 680659955 590109467 312479719 294168229 966192409 799927119 922178899 265350674 730691221 611011638 309109488 88204435 25546367 159663959 594795729 784511219 949201817 28600153 380139360 311124079 968718609 243062171 114997291 124681040 813373466 403043873 188784223 229378426 680699790 22611643 818607633 874056247 448138663 829693438 607119364 186388605 357827628 838759706 345449096 711326875 896594822 180941093 880317626 760340974 957631200 849752773 942833181 396266061 603210544 19470192 719378551 79899672 310305598 686142092 995932377 49463646 165403881 732944646 363581775 369706135 671179364 466866816 901831005 794205393 279130419 638633427 719837738 77919468 768971339 78984626 530917495 251991550 85779805 193857548 256334295 388475446 329044454 376936934 811226935 753403610 38000744 727305157 250065823 763980551 371261066 721078963 577585003 295287616 363937825 952107160 197522250 887790173 321736231 258035736 304447905 31400697 345898207 830020775 132177995 719131072 765856133 88582318 142667866 43838466 86212873 706617156 221697587 614639943 51334779 67378147 509081705 924431863 296095439 97847107 229456426 672172256 386974476 507862040 304705698 373918638 738437610 247137604 761836447 999379249 82170671 746279535 948427677 534217010 649088639 692447199 369791058 410512561 205257795 173864807 943499610 842829228 419443046 463967728 301762632 910286530 983441880 516233410 972740881 770363224 558645882 872098890 436636037 809579495 902376100 275158605 359728032 700288299 239981023 377833790 714431772 918917416 851763843 304520530 106617593 650692067 709309027 712269219 899915536 596102364 203134307 48439123 769849845 954100594 611303043 724363121 156544578 473647630 396628133 460049402 170878805 861847979 417038717 595774550 753178759 352734630 445528761 78824771 963924265 94307213 745736492 291328523 156200818 639957358 559525511 393870458 589426896 350161348 470265072 960335171 539363492 901430770 190938960 937965453 41204836 725665991 971510946 547771963 533756347 266381772 885656729 976169046 75395527 595140235 998547430 945676678 629489771 2034912 617184528 215046933 716004984 121489062 300637623 902174792 982288283 871882059 577566477 337028283 834384910 176102338 896143683 359591819 117844860 434777012 20937593 754217416 316679129 801073229 424585969 579983242 480976073 799454350 864297731 474428870 276982204 601520785 265800588 978688738 758178462 444589021 876532989 173373990 649128515 816863698 317784324 312754978 554847702 150991559 835234465 29169361 932546393 806297437 224985793 329013548 31891586 969404681 337615225 539672798 359432314 434498560 375884948 51143062 474974028 33394549 557998538 740966818 619666779 819137228 367881208 362169140 401553698 92103495 41160754 407867531 322537268 591486333 996298221 289300433 15784905 247468110 10235491 911239419 426520693 704744807 246540519 591020339 871985579 201261435 791695647 731625670 468283772 283628812 613169170 37772649 906813421 926729948 56460809 892948516 25215554 420742655 745903461 941010875 888944341 607135926 388551343 156543609 76626405 588732489 295461275 980736315 206027157 48821728 46422776 689917019 874859775 908102432 61357503 833031002 270834814 271858557 190623681 369361095 502865351 533321235 527947883 112867159 542711080 121166203 480753321 201298754 949350930 898660511 154818691 681980630 16010822 243114100 781909751 974169130 827212863 774648863 555373608 111466516 629946702 275515488 266783414 913035331 634916496 460744818 287174805 729471253 245194340 394711404 543865997 959505551 378528529 363646147 942954184 852912488 474049516 457335436 904257995 263395041 649472775 679612135 122321552 290193869 658137586 128635410 783049873 736600035 269576376 530612208 261422630 857744301 171166663 575394550 74367469 695010595 615840357 22500507 668628518 316629289 719592912 787312163 905182311 873930017 399339775 570486818 244800579 699255238 532217942 450870986 628410342 291088839 561503316 702216696 533638299 807832420 66298210 198889411 990000391 746286065 685669124 322230423 806521807 591755615 371942810 540634092 579240902 709024691 128066748 95756343 96094438 777784415 972998261 646924656 905508036 943213248 910418957 808803285 794515463 765731719 618506066 714439159 364612471 751461800 335821856 909353428 360002294 691169766 499254475 499503133 205122889 951125113 350364974 528207348 401758179 501576348 679766420 850109112 888414568 614484087 60013390 298465678 167581120 622227048 282440835 186480249 279672977 742796418 553329861 364892156 359395272 486753736 95246981 806333031 552796001 39064898 401402489 40023094 767880730 853546692 51992187 12132605 298831816 739380666 553688799 761406921 519828028 262144220 812966424 392548722 518430759 913030918 655648950 40541388 275860419 117561516 326496969 674301643 704229467 348977628 936870751 887752390 916849530 804666307 739302919 499502266 603049201 654027256 86483300 703169701 40916430 226093519 557111043 300754020 726504903 883515106 102125316 905259668 98875312 752553736 271717465 136343661 939895830 813721775 67133428 259620246 231789765 813663549 145775281 791268754 988587049 483379728 935892419 828523002 727288138 336691586 590893183 711975037 872506989 586327258 692457304 88795459 761018904 109705943 776224937 110908581 458197538 159463102 851571521 245036862 370301911 964387743 705526978 672358244 870562638 377727716 196880684 629602664 992520258 126552960 766951673 14069601 984335549 971819123 2235622 917998829 211833051 604028796 426911559 697336967 93419432 974845992 964424666 467509371 949924672 480300871 274002326 362549713 625767838 398580109 134619804 224807561 896464657 963016441 580145352 213629798 162289306 542959157 213649633 289135697 848734542 173829570 37587695 691808051 103560112 439023551 511615337 15235863 686516783 553693928 766884282 675945604 207107843 230801576 876665919 105739385 108180726 711716030 11015089 588903903 659898757 393179245 183053109 862443693 944787504 723085439 997567611 555567590 224694413 549045830 388333211 460270189 452838649 746404800 275315107 211983955 338375553 924021788 999712598 782943725 207114763 30245702 932560238 597122645 955584095 801096513 798374598 390708726 673448774 459697810 381901036 139239160 88659274 524007966 574398288 234999352 904291317 61359999 200618689 925605123 295097752 233276842 15348975 529314034 423540429 610712861 68945592 450154385 92863937 596224230 891128348 513884965 606155785 378015238 156502815 58384825 832040455 226773349 745057510 372814832 484698169 515812044 951430629 736874665 860646630 817072395 803253127 55356243 781678558 781026636 88097756 888302669 211188536 9512189 955049263 832052097 768084835 276734657 366434741 318925267 984980923 90603945 787255814 371574315 966643498 517275779 950883018 211976730 659381972 163424540 272173256 679910796 600441785 916723072 284015530 976300013 138783926 412620925 40353955 779639492 879896067 145518807 245013886 645329006 693828267 718410522 748336007 267773640 315449100 96794538 394374902 925026352 52877204 687497208 966189371 13638737 311468317 353789584 173566698 616806261 610130318 476145204 836492523 777081935 774205714 368862826 72189048 58960927 228215826 568634707 634294233 12793711 769899266 574606668 7191883 805349325 725536609 534825316 626957106 350157988 918788702 917827184 993789905 45255308 102438026 579913020 679872303 649781535 706350064 982338831 915629431 459705053 318188830 84246960 52248533 808631481 406821429 74633774 977636977 883677619 603997592 184695802 610522451 362367097 65695872 949312736 22403900 924887445 638180459 442867868 410791190 885114792 62639371 828954242 614385475 394969673 610467222 146407966 615373453 909451663 613837536 443577634 521916602 46853339 822027922 449474303 123241087 637872965 287038682 64788016 490075669 197410977 511189947 761972442 165388784 381200153 426690470 385434100 579659796 395719153 886759033 478268039 225640393 782079541 792163365 296778685 687210275 310279018 923696349 857565982 454669533 178680101 548997304 204959312 277775596 90902531 755192617 373600484 339475388 611658823 115191921 962347332 643143543 49164603 859509814 261288892 538915889 654755768 535893185 257796486 453314266 540703777 995159171 850239206 318757279 886400782 222445765 524776037 150724408 384451542 161429897 451805069 878934813 459381164 776350579 846902581 334017069 679374154 857101003 410243312 769365788 6581749 501897246 856223574 513972107 438974391 643954962 139454009 273546083 654008277 150145580 673597509 492707854 309887289 82796612 672255185 626081695 803718780 520653216 650507222 849634518 695333597 163389564 469774291 931569693 998746128 219390821 517090748 507612127 505691776 423061580 250893934 204545594 105991833 933734080 280227348 776915328 114439394 397734650 864335122 135772811 314902241 938661959 354191520 760684839 477159116 557506565 159934513 817757763 100852805 292987240 440963398 349532201 204332419 324254062 869203029 292617327 860481797 891915263 331543380 76071442 828017633 660392270 300280177 640062996 838108045 19292625 41158547 910053717 244276399 604323602 991028702 485203503 824782735 730647907 2337882 787737607 430844244 915265378 986217988 577143431 685264180 759670817 577173793 944298391 908752434 493810232 155756621 321995497 831355987 125953255 521747626 888966464 195566585 551648638 646674306 258474498 817393052 255802196 164466085 482157153 67675927 777260738 884336920 511877383 511005588 174606807 188325426 197233435 130102072 818777470 674753168 463930316 446173602 496400750 959088551 969030526 180142381 309198650 255923217 696646245 103845744 273766376 395945905 874093785 605026284 612821141 867877787 533547186 148901135 250814373 11614468 714679025 20377841 482315341 298841558 509727091 589795331 712333534 947830781 995083696 66318149 248270652 943700274 982555618 254288618 20589007 140477749 553651830 677549301 718558965 89766270 497612025 512842227 729752777 483948169 446067689 611101672 165501724 785219762 53771666 510838660 656396949 439367636 414137583 169394228 13447631 996917252 81252801 473245924 417791591 410245058 470690916 110315793 450705298 858006813 14764455 705617437 677263164 584130831 882823299 220853396 295185933 593213367 982467909 761074083 598294384 700677491 124808640 738651597 943570558 434514187 100156824 653087955 950104896 60455538 827169791 596930827 697944996 205013293 767763581 396056036 859495754 958995460 950244075 185903230 714998802 242396787 621945881 995303483 181606832 950500945 564524515 484533163 195913353 344742139 450235788 751018344 77730936 738006550 283071536 879604879 974801037 785867127 680154413 129552750 875512510 658159381 718126230 913514279 636875488 56331030 801007096 224853089 792939992 13530430 839199375 763062079 941525305 55473934 756219492 338616755 991920755 209728277 266445081 438348370 581809118 574438572 422596430 297999815 655716363 893987295 589713201 172511280 36481125 287189466 839795849 660817603 145913294 173743693 829701274 164477893 66192402 396317342 920358518 572092955 728987423 303530819 54736602 228251988 420962145 464752510 587839734 174118231 237127865 539067434 883719742 498264401 604285989 964345803 564867591 574428149 803703122 493499160 456519992 238469757 608159975 610804537 61860592 390838776 200112688 370531765 56178492 667737341 505368850 708614495 79176361 599352834 319391696 589789399 606987086 944070986 68599949 638123852 657711155 634599159 591176768 911923042 533827662 263062791 959489692 670785500 737184035 567068109 650777772 176051694 964715913 975144176 713403705 833472488 593096016 19566711 512870407 11777623 855616894 650999437 908150979 200687925 500688332 753392287 689842738 870766374 427579664 364393721 803411805 522217865 356050693 985989532 871238121 364076363 955003426 793179916 713243872 256686542 496781278 642391318 168023916 312051015 981939881 424066222 357670656 221011428 759363995 240259604 876547052 550689771 798295050 550753339 358613148 423480441 485215374 916860821 852554350 190082302 611626558 617267096 359734236 293302867 378162237 467940481 119478813 966996910 531023906 54875254 210529021 312321772 726944606 614877678 75254387 692674159 122230391 976760426 63894690 629004196 260810279 67235184 586038154 657476050 682851079 570102815 93274 262770595 834822291 800473929 139440078 887197785 614157038 427821259 537910795 819564939 490306145 614168357 531646701 493083843 646781824 5704259 589852877 434028586 263746995 191500487 725825044 265495429 786897197 964982403 560866793 434917723 693526834 566349380 617483088 607322627 265743896 14809770 830187876 700420009 688641097 986131186 481100702 386095204 696507595 373809030 756960366 789159400 645940723 345238816 745484795 538830533 450055635 647829479 833007148 593712508 413692020 405984063 154006998 342019868 638958888 592302291 876945444 287028517 984400633 379194214 335898332 843648995 19482267 207561408 305145744 712937586 43428167 749250508 78471061 800630533 429105413 91327122 631736001 133475913 582090179 54914466 426072894 169703518 314440469 880504230 725051483 679865891 521638992 824017200 528696614 87701062 336138600 117576793 98996022 254374678 271812046 590320463 440264706 884134133 220878179 419367969 326499320 8203616 39781289 42299454 309157314 134445020 571092205 373631100 767757049 530669714 791286928 842723770 489685627 662453643 660118288 967336236 434907035 171834700 39607128 909849303 954052245 109775297 179046890 58625730 691854382 94644353 471410478 899575448 281694105 131417371 316485056 418917237 349138207 342850889 43779043 969125945 824808547 479761862 102872443 633571652 829971075 302705551 125159673 122890198 399867292 419708532 298635113 765085096 718489065 583393555 752531580 533702962 93623675 105437661 713962985 950014352 875901095 110038180 551427158 221267740 696316763 728605337 851620739 470960980 791398476 138134908 234662125 768844340 911607635 974026866 141966818 538432090 644187784 646029067 670134736 633383102 506406932 955763564 116667443 233871645 183552665 434078780 463062463 564367372 68154045 477775054 45230143 503836346 630101081 710038775 247539587 738028936 656098297 76921318 913571548 130328723 844404438 83493042 232325523 985580242 368948686 411406549 723418218 553046626 946660850 280651037 35007839 149717131 141614189 104811729 42438390 456151418 500759492 276597044 449541572 562902143 514213269 662596890 819419253 600415589 566340150 205777462 867370233 518743257 153384201 299599338 574281689 940138420 59545624 419735602 353190603 187000717 252654398 811869549 412736825 231427207 18794231 448401160 123142369 410771785 205279072 22736666 19083251 854641878 641724871 28548958 951723758 146668919 500907728 206028110 337958797 3508222 171137130 355682226 320196090 78127557 950221170 434681574 205989332 558665385 861207010 703056317 839624169 959709973 419869471 218759325 413415729 631321058 791167476 156507375 873036382 987140509 415841607 259599742 252502044 669047488 942496567 120385847 462698644 950621184 61048675 845338549 970603122 695006138 467796238 452703514 60916745 831481707 999737269 291313010 381641688 23676011 370102379 986610963 972725520 375022759 558739954 463209595 849054864 105431795 470088713 331056660 25373897 565400840 121607185 813601390 277977552 326007245 400633294 121444389 723162597 3667772 762793614 834037122 444237006 47043808 476080809 524565014 564502096 798665545 183352207 989007053 187764347 649541787 121705221 736534411 590681893 9754441 117915332 45186380 668649586 531634451 141607155 933452605 74360849 993616557 503666962 601598958 8416840 358127715 529645614 445528730 445821336 600645182 478062729 283721582 372728452 209650842 74423054 891934914 124050617 878328276 343706394 398067164 104304506 782939069 347642481 953803132 188247238 977795630 588493923 981870162 818159775 870237994 772234109 626516660 295741011 503166397 955661965 70673195 525025158 25974000 356481617 81364773 764873631 88084440 448429668 73843533 653251658 533118565 629859285 533854391 472396515 807034939 111615541 409074899 672168872 793838760 531903361 733394379 835004420 871904877 195971632 796279246 628130925 416063030 882410818 103108726 488135509 903581890 845378394 398375793 815593288 870359877 895177366 984913210 365200419 24762251 254360147 791950369 189994142 248764361 866390855 799755970 626748626 550471381 519348996 9797347 831341202 964270621 939379795 46407425 675615949 759934076 513713540 215883824 982435270 665346783 483104311 561385496 290573877 732333016 379753015 304644079 12688166 599134264 826423911 363659015 914859931 864119653 668997627 472065467 780506343 950402537 150440010 552047742 55939607 73384213 252052146 873309009 224507676 878379841 894617815 35861364 868404169 574436389 26976662 524779880 592684764 951784646 987333307 302745513 231322726 674887635 555559490 476465610 522605704 179772737 87264982 190611225 542269527 255851899 882086139 239260964 91884444 266616590 267424731 534515200 340796138 525152855 674131040 787853700 731390390 696109231 838570012 745329548 974079825 61365770 173746927 163097453 832146517 340310021 333794642 532096638 172459681 488019181 992169187 837844890 841078186 592554927 498940973 575390757 12674161 731867185 905397186 547793098 754386339 365542502 833953649 158244854 120034429 720755485 647407388 628960414 675596770 392348179 708828673 893668860 710239055 607481992 726183498 486449603 834947706 416808716 734208924 626814346 642733029 979358796 726678165 469700491 925601274 822210838 624259365 972757937 243803212 58985797 349766799 855614499 174579101 82911761 283826828 169577305 465207903 696263636 297612149 743934958 554400381 451207448 142476979 724461804 49960808 790489533 896076863 321758544 50494150 695987145 44321671 706515920 838435484 451923371 834367772 783354487 537189284 693110681 61391456 274935117 924984877 480785566 2264291 877928951 663425164 299399740 682955671 289451095 546726885 570216845 620924074 245343425 132372406 915617426 308930085 490945069 561649871 136102508 90944567 991844755 744541893 718356441 595841548 951790681 310488905 819606929 507837863 652412952 250407658 625771388 273566355 4493144 553000121 38393185 25076210 735785999 231107591 865572320 254361581 740851928 416619438 171561986 261906902 189801688 687340354 419330190 216870002 10010176 247139749 496342714 62443013 105236676 552942499 422073673 666176601 339020450 345769907 254079 799358638 924336515 322997543 753227692 708113326 725889937 659221008 199314601 856198027 246941285 355481601 439617006 216916791 168447216 744983320 262872213 555324948 16149193 54199211 127467431 739029695 996438876 42374602 970801917 847677692 878933041 945161495 971957670 434875558 215241708 658334427 763686550 491494996 61151361 350106831 276136936 344390494 645463878 595590684 892398540 705999567 885382573 954539469 882294500 604917288 428277194 47931745 508971070 946755251 573176114 344455853 941452126 678330352 428607982 947762093 784980659 977515754 626458750 497653319 433026348 871396447 553081173 978959406 592040508 187746730 353451403 763938449 880106153 109098679 325558459 776827276 298988355 20491295 159566943 705555360 245199569 394067261 225817905 111949084 490581934 943372368 160664705 595952101 517226618 307627086 432495046 828099762 816646985 652481704 67532886 375848233 655422382 835077711 562530305 146572248 875839695 846760474 293290566 658392372 373580036 945626051 667801256 763247902 367841629 20432043 528742213 440620233 397906324 991327215 610044469 627850275 107071184 756966935 463593816 990349304 180521694 73019748 864844873 138503690 379591442 514506378 915978848 213159992 481333332 838109373 910013913 242100566 275582493 443254143 548271781 261313951 421820988 835476376 731712354 505115982 458429821 17371666 240717935 377938716 827168627 194321243 2392003 934611174 321042691 472131596 791385840 63256914 93194485 868909837 360141033 338050646 627594030 615408208 689770958 418307998 98927481 921371837 312723597 742394650 91038192 200461007 328951005 168364702 711900394 141216913 225122629 517911132 562608789 116967708 156878760 706329537 492417155 928219413 679097603 5238719 275345175 476898744 222882581 121867306 417161888 300127639 379423301 792430497 497087355 545787533 630052302 750858311 242423335 434434132 516124766 71897768 955741108 828727082 348275384 938158898 949377259 885662909 960786956 674141775 336550414 613758405 735807072 112879555 921050749 119920622 475872460 910563421 35884386 704110709 151108968 69121761 598214698 746094554 500473545 122022379 846468050 582813940 655447455 111280206 689070109 833611784 239781862 942811635 121023861 305728677 496476729 504801791 565031202 145498174 589949618 718960673 846430237 412580179 539843714 419220972 245550135 971540801 15446068 778085398 829278476 69481412 746449621 364993649 493708648 937794514 941015398 132462999 292724039 827390591 232516736 792975670 639698219 232993256 559328092 253425013 404640502 815338894 660254378 250711191 833804390 733694575 380157128 813018328 245920451 450447069 408363280 94991224 638821121 131228708 417950894 446950261 102530585 383037829 616011484 103204647 468291531 568626226 975585067 804928614 340988933 709094526 207166831 649143746 868610925 633747546 621456587 636921369 591518789 941202161 36148690 117691282 607582333 178200273 757641761 212805772 696294598 172280975 313449393 272970571 898537269 624534491 854246812 722663134 878780497 792664954 684120016 820234317 720931929 635842966 680733248 96805962 819379337 650423576 854894056 44018110 541397209 699348094 645944047 897967802 611916313 432854506 453139122 658533693 716081262 595923645 837344 251837309 846405122 578826068 910591295 627588082 967618586 575670524 808580187 545193153 154236860 94671267 420847517 473864516 774162172 137273215 353669575 663467184 190826092 819736655 162516722 716263177 230979215 861602253 17197623 194546235 320381676 302120910 32941814 964377785 667021181 846685671 592425541 851122579 659421630 330291674 47993554 31462954 988792353 771445859 39619422 634153763 158887920 26683361 951447517 263777918 886183776 326062122 133222313 580885104 139487538 411505315 190640052 536610693 528699431 735224103 326255049 633401540 64057867 159830363 620168342 586808066 402705464 407358559 183234077 931944803 582270957 904879076 497048710 850142448 426123377 147340254 222995990 193996770 684568690 322162385 94527916 420879499 268990733 42790238 569047466 179753003 213477067 733421816 158721059 49351714 930754934 84256911 420796526 622075888 614431645 418014639 552899268 193301488 554453678 424552393 726183459 295729739 607939175 484514704 36926104 812898822 353521747 596639225 577407627 857491387 544730774 396844116 291450661 648469196 767667310 195198811 258514585 717854539 251616110 696084424 780526972 462810657 670831193 92691594 385171447 950642489 970217095 334746266 874373933 238153890 403035004 517264933 253266627 956474394 209115898 296786705 472447166 78010024 702152718 330631040 617289830 498348754 995825050 137368335 793663911 454378120 55555993 149020481 503343195 174860500 5004636 520998858 489149215 506744309 407631678 603394795 706951721 195982604 575453554 689391392 779239875 543281274 977293855 631073120 216487254 9068119 624770057 612349570 612181328 237389920 522370412 493651903 591863770 396536229 98218567 270856461 316416596 186351825 676146546 876034911 642189494 400032147 490460717 517413544 153156360 64192029 597312417 814002625 832472059 349744604 524788697 851960664 211822943 289945991 56678991 328268373 746419557 966684163 10641394 725932844 533851229 301303597 530034582 440843287 677172090 931593690 551033464 607454359 165468024 227848037 28870173 94727229 419429893 649523593 205365060 995409032 61582847 331322001 600194367 10747244 687775022 708683632 468149533 991940368 744904671 39769432 251724027 931242692 273321475 84174209 839631902 928475526 67412793 765184615 133811527 776060251 406183005 220711363 134051973 433995838 329609860 839976497 762341402 393836350 230653379 347264591 156729651 802241737 457540253 582303610 989871185 300791591 509039130 447083042 716388857 367178787 523965925 113832830 714011008 784308911 883763760 356421754 619993957 173064639 93164255 499328094 100775400 867087263 643675037 642307698 629009578 711561483 594544831 218674720 460167015 679156336 538329379 819400114 805844730 201651407 529719741 351065285 448910818 44626333 881266819 663675417 7334789 876163629 902059745 511578676 721059210 577198675 1677840 324692152 682412354 505092974 723101747 353970834 772591420 380713477 98602352 488634933 169817412 881027527 374154313 381949288 347608011 501938820 467578786 677328820 15332022 609372694 221458134 334969022 282968954 875455547 644984970 484809837 579082459 210174435 263436379 324366195 703980844 441499046 447693739 39657264 319785616 465950650 463681283 560176511 502152071 724207210 932015428 60835860 828305180 876875305 236456197 376603591 863339574 111903288 955777504 609880157 998668447 902877854 95452840 959431612 343973673 511080596 299174381 451705178 940586467 87283568 530676448 542437290 478610737 12406798 302448813 751179372 890279671 716514940 966010591 366597955 692936276 648585276 636875799 479775971 587504856 440634126 377726714 194935416 999457148 578042046 157331111 811795655 552658277 741789571 863865009 603971103 441694046 32122453 847299979 699113781 455082199 304252783 772295 899016596 480513885 227983878 403098044 135663105 785885138 441556491 593548439 396154499 583419532 34486446 386413285 737625362 961596499 293511078 477552046 798001813 287894720 533991684 872494828 340990260 687192011 19943997 460456481 50489522 66508011 420648280 313052600 925509579 895839689 70588088 719247731 772702309 853111345 425138131 481510526 94048314 881681778 392796992 300303824 225273472 736502487 324363226 698210573 310315580 998374649 184973143 20941423 820265760 875960469 440410957 740542416 967565916 447912491 40198265 831219855 94517063 972871016 221523815 766634674 645974843 319259520 746635010 891352221 334873138 888973534 23471328 596254449 708329079 683409447 953552030 264757946 643203521 89679402 120666042 292951980 980640554 743335614 880460928 191945612 919008924 376320251 910665916 438830754 179355547 494675974 276998045 631996738 255162499 256996421 647884709 728500772 671514595 220337081 153218945 963438022 656031484 768899358 453023435 452877451 861280089 10934760 837565543 875967446 978303963 560264308 732674530 133486557 950483253 85755847 173824758 915774660 227137121 786287592 62507098 787494428 749249522 19658759 987312009 460839134 204614030 694142638 423069762 996851002 55874976 496020062 470064269 892248100 564487603 885274789 188735185 642584245 230638550 723971076 154566926 276822693 201108071 520133837 202815942 257509060 359482612 926681585 963252847 619273483 875793377 219897112 472086535 214256789 176423245 703757524 33696743 439539436 625001673 782956233 370628837 622596787 863129965 128894374 201456271 553257955 842288373 560956442 421779436 318924531 738283338 114623004 60752251 868607388 444436399 567318696 702290140 133171218 409549813 41117697 589986580 587217763 191991950 684424638 221836350 882095448 246459193 794095103 251310331 135032395 177946957 516522632 943585499 252402522 630882108 510079293 37245784 570297144 260410215 138960766 461428155 369418702 114976069 458722632 536827321 344878984 570159783 978815667 196635248 120901466 875749686 771108832 197966078 761450922 440127517 276968743 580875673 882368751 602531730 225968291 560650357 445065018 250298124 802277015 892519739 411006667 60947375 730293401 38112255 887248800 85277857 691210574 411769806 724333290 328454743 772846464 85882306 571563675 435229096 871982396 564775808 158005493 786074419 184798581 975509451 670773133 553707190 397719379 587424455 492291564 98757999 562261327 805867802 159607831 50516498 683157667 312290515 612114558 203571984 290745126 489651019 820773173 649471300 775928312 142186204 435688514 593876099 894944336 419833180 859703557 517769373 129705310 480504663 831719908 668853222 108207271 689730383 460843862 36747318 444100899 601223912 799914272 895425439 803029 879474440 468333114 184610124 749266064 428217295 533806445 92187667 757719408 18917163 870229522 378472368 623535200 977851052 713809550 129126927 759877103 340522537 273910299 710665734 258190431 775222669 137551885 401959456 20883870 732134149 3161448 172771264 381003234 92067204 80412327 438787402 87591319 259617550 456361875 739668235 929224078 642169146 540268181 853299221 984025570 981611994 403120219 122473644 671735940 562141582 199722345 165416778 68471429 157587848 644419670 569658074 166153011 350797242 960159966 96838439 435705128 154446356 900616118 301320819 780997197 947137629 90033763 565183618 526200283 409602313 546103211 692692407 461219051 64514987 535122991 177115189 151310575 348080014 108871134 79426373 821251282 304974171 931498968 532243537 135735010 685621191 991885088 251795244 515327941 707972273 677606067 166976629 596053895 903624508 827558918 96932639 112714470 791280918 426269199 645582805 201117083 941074385 316334331 735671909 723264962 320964638 653269049 770585608 657916173 206105316 434311446 426983972 987747838 876474071 216639050 289637537 388793986 101960468 463299394 818073969 910760008 604985127 180884160 934178523 603718672 779811520 940290449 791055291 758139013 490905530 354874178 846151065 953219475 86573360 69241590 960436288 685005410 964490183 92322993 165044232 839336272 93800391 762640809 222125388 176606268 277565792 83977117 62357042 114986623 959478844 70601627 183057914 153887262 995600683 526203234 267367717 220252321 646782409 889941205 739269850 188349915 775793417 689492345 177385579 584506514 114098188 593190576 466989795 741178270 934629427 178763242 13891929 663491316 95877448 683233693 704614206 697812632 787931678 71020554 857936317 479056164 107120749 436276597 285068983 847126169 253036180 608662515 744956074 455609166 351400581 988539425 58617955 224287275 261839696 565525648 397965627 807851112 921959730 984100855 612638118 984407366 290807533 323424708 337173735 824840477 821164169 265030706 148193924 72492897 367488470 671837775 574068301 354905475 857084201 538689865 536295077 870612022 99900535 121786419 353952843 940570437 424148745 757950164 679130655 93401574 633920852 978123275 964092358 478963466 942514714 774618789 866893157 917234347 888571351 464982440 56759694 742850196 671842269 18723220 158097669 497544201 604683545 505624363 350633119 991720414 373436956 956971174 832121882 627661479 273571971 775850341 750352947 295029516 254687172 733186369 235638537 235698378 864737618 662458761 886827757 666000502 478679301 18632301 139391192 688955009 417589742 394466082 662927513 692182171 265941083 365039586 747463013 107049716 648590765 399445108 650368881 241410813 680748557 696829790 518605994 847724296 635159888 20643745 191488881 610080074 268309060 671739359 291689132 962679586 620328732 808582154 861757483 552448550 686028663 40428166 532334601 34814801 220177062 155375455 478957441 422109722 998407248 791068381 659741074 300782805 181795335 837399467 362818481 320574897 181737296 563863233 667681177 610910280 435755476 578774093 969157390 739937139 731028720 890944558 694798775 811603431 985325866 131044389 207249292 444570579 602026968 235191600 854327653 491816602 649012824 636304109 70912254 349400962 291869003 866458024 860054975 56241755 271236160 846301338 135689349 662403344 579402857 976686344 712885458 267930361 843682714 118253086 827747055 915071212 959108928 440738729 453271268 192626196 720615078 760122729 652688713 201917685 567153797 270822817 145454372 686194422 848655219 907181620 882728561 418043766 777028857 10681726 892482238 378126658 609633545 615427196 841745349 712651631 293586667 319532622 29663479 729429731 829186877 343418681 343121626 567517612 2627959 204359294 787339616 745560771 19579575 329436944 67883524 764610473 412209633 301323701 68292857 803241983 278186486 106703367 459971354 474952007 836214270 154978988 539655512 944590926 103457994 576601538 322051058 296919625 455614403 361969873 349380386 810158093 217395347 978209380 399544319 935596373 935565845 913560265 852288528 937418101 28054415 857698107 103298915 23365358 357477768 560624328 17338528 934171405 916910621 170690596 484805037 165771573 444488783 457222532 44467827 352592972 316276166 126946109 338922819 556051610 180822745 702623958 421118933 122421767 13110381 162123434 458810877 467717607 697351860 871481054 27187985 305749287 260913226 340232672 534856502 824805083 798086 167832464 656520913 371736972 79381787 824876054 421833071 351918257 927221441 120927465 885568756 142188175 664453225 373101772 897769470 644701628 797279722 292813029 925170785 912431186 637981302 688574108 241287538 394705263 252516211 120165878 251668222 301762111 553120722 165229642 849136123 170439095 266243685 686698483 846869980 508980541 599569523 491172303 515898877 1480067 726437358 648231662 119370685 615793649 907327998 398194915 795876578 29196251 420458359 19475076 435478990 374889845 28052684 337932183 949221541 510923888 302770733 595966621 424766988 365935726 533447701 651136099 265743246 947717256 217156083 69657607 368570575 790517607 525533185 539390418 139162810 124913337 49400608 720899262 593226126 180368175 75265580 447894512 355188343 259725732 719820751 914904298 834418925 50806724 148078808 214769265 555434838 84398565 368894486 188405216 966139622 494817660 630435848 307502849 308578588 676178722 382119000 216310152 861940642 808383869 307133000 376343277 380306373 5142705 487733374 423377500 939230146 837193483 476622670 172127971 338766244 96319033 183659597 796476813 610607432 402267735 720131182 667993149 73781138 560973437 181481992 332645887 519209480 951708285 345785865 764631378 809173237 430766354 31846535 899267503 219133562 319610386 458006564 985146904 250760603 376162542 991581266 709419905 279994695 122502112 898764609 50876965 105120629 278506958 274353725 332831908 321319975 773431899 712622491 700324308 438484549 604357121 787712832 946782670 854647641 369731650 127639870 409168724 348635087 959603321 150920636 907010496 717534079 803093503 533586898 334128849 347579376 66781537 432741696 198533177 356615778 706368403 637211907 382279562 166135153 804693385 808009774 921620075 727026708 606709316 836972256 386464928 382666654 18235774 745453726 69188456 559989799 937865945 393069605 170551693 210294994 211260276 377346411 157845648 47879329 446922113 441333388 330894023 226341497 95900418 757065529 402524215 729503834 870300419 113681203 567586666 103929950 186782351 635701942 903291502 368231848 267374604 509289589 464828013 582012474 88752929 861734077 159320047 345639029 39271635 21773819 110475098 404105398 398813239 708164454 729158862 544888225 22124467 758995309 481418937 379243091 70064338 574854460 487831983 929450212 461216060 789705131 240966608 346377490 299291986 311470999 220489518 731563997 986007624 469389413 892965897 626717917 874098396 776625551 479380564 74656181 545050472 355370453 494814229 501573802 646109428 348220193 749719818 180918086 696052631 655557918 367892504 984592410 355384643 154278519 376494946 457968960 234888145 658328822 625124013 948491933 365733603 97122874 352894572 571908470 768307131 666426174 608676734 143066409 934906052 21749996 888123497 604920208 774991278 904174162 154741975 350467345 214153553 747634774 129954618 826108528 881249400 76930906 674990735 639040680 316647259 568654970 292875481 742728788 246335769 772984205 779608548 684362939 371801496 524440615 245133531 728391916 997635661 136394196 228173429 249160288 662802951 823799652 990054310 612216702 342609868 779126622 595968942 718729215 600985621 920154087 352550598 885414633 206108364 454340417 764282102 221494614 494213913 895046889 147377596 547781782 531449024 513043333 835001043 958392222 881091878 886086423 547935018 31793985 825343691 461665305 851004891 272232340 244952237 883845401 851763157 716237607 433397692 782423534 427033630 674323631 943146529 949364274 685459664 877181638 36462570 218458493 876987179 791966828 702346826 183596652 517494374 18748832 987682501 36327505 891877866 315346078 705449421 600337447 254676752 460146354 675216832 859718222 306456114 411467099 7045419 805730191 714379643 727052080 966696327 49924226 426474214 793249538 270125017 770439004 440715373 565608341 725694587 138965651 410131892 537817912 724693908 369348984 53163959 47923599 862030115 771707256 428212717 761910270 148586369 320832376 736853122 23520129 952308661 557529808 175774507 155175173 961349314 100269277 520052346 757108075 195242545 634421847 536186525 910564329 3515196 825619831 57810420 32485655 348725867 367815711 969738746 292959733 860641794 108542227 928135482 157102163 523657668 651382752 704385729 43406889 277718485 633708837 884648050 845612823 701030331 28585761 461872601 784977306 926933570 76743139 831199893 660378263 368938376 370096395 227668120 735318118 806644176 825958469 911671109 856158981 264333006 793275799 961495794 282102677 274073082 112214728 838052672 876567574 24680444 167739493 311374682 238394337 951981008 251418556 429587566 55894693 246989253 234991736 523537161 561559824 284676734 105137693 89005565 86359651 372237273 118854755 737394662 51501871 841685435 414216636 511673844 115492095 371304598 634381193 457049965 25071439 15580567 561670396 509617431 428655357 774479791 690259951 174513694 836810114 177660590 908789834 503928864 725346579 785498641 514429311 891906211 783623242 322291295 862823368 905550466 123040334 867895349 759927484 64038497 509977395 985833600 237677424 297344942 222529975 420942058 660375559 567125023 57665655 688805382 966123820 238357624 883169007 751319039 59800883 81297836 785985832 819316365 445015120 136542811 115597952 107610185 984312340 515263658 894967303 846856491 110061570 580353648 775622563 653244216 494419682 138219208 270398843 23941524 710701357 881715621 524762448 184846044 866290982 484909880 281853904 233049414 714749378 738763095 453352760 867602404 236559697 149443459 152608030 970316762 779496134 156507665 977642574 70689390 767480953 861795895 211068477 973822765 233364179 339537523 131677324 241579791 392070923 736960478 119977592 448476966 555537666 487027407 94013962 947657749 513909049 876792192 797613843 961137696 274600292 588919164 335257853 285937109 957041382 873632578 844843473 250892332 767381 43320191 193610908 42979597 946290897 472387860 73386226 303583778 278660362 637798602 623668590 604518550 481969095 565704287 763962499 315724681 266960595 470714756 685227888 783209505 947469478 21806874 504731698 293522957 332684262 582538151 265110390 251790989 855413558 116794399 145760917 364990663 209663053 676361765 833769371 410565967 285971572 983976605 202635705 898632628 992683520 288893016 736737886 527853270 295762945 500544373 752725308 83125959 163786240 741594408 567177873 952840119 4158709 535114905 696360687 24567554 531192656 659269239 64945835 921723423 699568579 54590711 131802218 390819159 471505903 553929116 529265442 695549119 326324362 33773717 667959785 908393606 761938576 547771920 333770931 966974472 901962628 558096449 823472007 313199589 65682128 23805322 888084271 699201155 149336975 885379687 888969083 114338536 295409756 911059325 303390593 237295003 460672126 419747302 983827669 126412699 536709345 516502846 389807495 816550316 123926204 862764493 447814947 309386604 162447774 457150597 919251671 770251788 813559881 36165522 207847321 315787799 478502134 42028727 104667448 896309004 200101024 190612191 661685490 294139727 615719623 151554682 744105686 801370141 350719858 400650056 996171948 251680346 610866054 83623193 466879315 251552815 434516047 997623755 392565651 450394411 252410752 435359872 478493044 249522757 314944105 590307173 145341228 581194544 854300914 771102932 5471348 38526300 102992163 880585480 342626958 800871828 741381744 404841328 985267072 749475474 935105581 333024538 126795191 961982205 363053205 738856366 692083061 387719945 481785038 701174332 782829892 262892625 145056697 370426922 369463609 811363722 669614015 194302952 312425672 134117732 594129390 47434 114802958 699823344 404022718 909090962 465990372 547457561 453968117 857367059 928811056 330506201 865557236 811338826 268328917 67675696 915821611 887220356 99113002 335596656 695854242 933844835 145037035 30356 522378593 120738763 300137011 83718764 895176571 357194342 177937348 807046215 248894725 740388941 728993767 433852779 826488588 206052691 850493062 810823227 27682630 455217277 829471656 177354418 401828523 768067152 490302199 617788658 446715624 5588964 493407525 668707793 690933947 46086534 382355160 473783792 164235137 512458997 462511214 431122718 813301123 569452150 754209200 474318604 13894193 749467083 653322993 201136882 19740694 88321138 664532198 426076206 911566296 737624606 475593401 354526383 757455310 941357532 227982906 872085021 123590987 617004683 543937333 77615569 162024855 749624413 107985553 531982496 125075467 42288856 410843612 468319945 1719890 856192671 161893394 566974483 469168975 333204705 415791039 521372065 997611373 115391025 832842528 736411507 10397462 202055871 494328434 210491528 211474690 236344523 253940916 148283989 575260169 348532155 804865844 859187969 651243432 82460447 141165791 29129508 658053250 369696495 738030436 940941265 532240272 811291509 467105282 830121929 502932196 424850570 898952404 731380180 857674143 170300620 221964051 101320833 407644433 768953985 525375328 402207233 495079237 680313333 638790096 582347607 499478172 364094902 364623804 846224107 36448522 106676733 547499037 64293122 742879343 403392777 446965911 305095466 869734721 540305022 805806241 631367391 692531930 420784817 424720010 9652751 42247248 201461745 614989107 980198584 817380858 750028866 955172738 502066682 204612628 349765016 668762028 941771638 829389005 530095414 766712342 782891904 501250710 365469231 923271982 951933036 760604341 740868459 647861255 700229811 353704764 410643724 119373051 265900259 49399169 750596013 352212117 943622527 14164001 326526950 721084744 461682485 932791594 624875694 3753803 37879716 484486675 977513936 202893260 963128569 339641435 984110627 872181599 117498614 853256328 216517718 451309887 441525772 70940773 71943354 990967713 140260868 644611555 599243852 978415574 801107097 145511178 344535145 851049706 800118998 931205062 640323756 535303373 179365497 67965572 966913013 833806364 867665854 154255566 152792425 991294591 198844942 460464714 458641871 248283334 172759308 558644696 826262544 308813574 320333745 162388059 801758032 159469147 913131342 762479200 393785450 923868028 857761565 198004201 61103895 294846055 420242936 278940701 727593828 418203878 967136013 541132192 798102336 880515607 559791777 477817914 399171957 941432293 376770267 923579368 333753791 714000986 91268274 492830123 911706560 415085234 626750512 860651961 27070694 651378664 445401484 429736212 978521000 331062271 818981825 914309695 429181601 19695400 631009472 420697513 787437540 402742788 37766718 760951879 395762051 796990239 395597764 895589925 280500057 523724962 373258098 636035476 208959446 558609446 508284808 304016889 743945805 627006253 665386768 530558227 548033730 420705494 647861398 947141377 934442491 6055683 487263902 881924618 595498985 231112970 257212926 436857055 140486612 410145163 136837849 732196497 460002273 756426325 238724582 27526840 902457259 775408702 925344355 131676421 488552156 467437715 434536748 229932793 47493362 261965657 514234900 744941221 626138500 785343980 564598605 534885363 856777156 815634679 2282905 272306365 993318507 654677046 343726810 852016859 724024838 859502691 318710551 208864443 819110319 387482682 631552464 24153530 638915243 32102091 405540731 447283654 964034428 986745693 565605485 807486347 181145076 783643540 710644852 760066934 581392093 950929623 405980724 571649266 254659033 885794763 847066448 994211103 27702574 52170081 948436781 693512389 17305174 758540282 673851965 774929021 651374475 809738355 451763399 989007035 435907711 444055658 367056194 474878084 53479570 193839056 902602086 603732714 853787424 307739370 950551370 349445188 550504937 285017478 824957115 554804600 100073098 378498306 419812095 997384673 407370571 534574462 174827829 467414510 136704030 647567062 446057291 794704892 480514221 818565577 673695698 934184847 663292404 687744013 95145178 441588695 737784597 719718954 871594378 211010540 253884891 944586829 872885585 288990033 406790515 271186809 771052116 860561174 431468586 737761514 621852729 245398406 48440534 848628777 794741070 311648288 605390956 137145658 840732964 255736784 329610580 312665759 733453339 846087852 852106538 684531478 218754940 172705292 726598966 635328369 510185374 10792819 575752312 529661832 423236642 263699051 517633987 943470902 834983573 430014783 786449651 352232264 602481987 17088815 941912985 203333223 131882449 589090486 108862559 478157962 239484639 451096976 383249552 159013599 681686487 814227969 412206853 298916240 810955554 59346369 305017264 989233225 327036682 170206365 633822884 88246434 171295291 724155548 742510365 702230326 819433213 541798432 153915909 241722084 103416292 919919597 492490824 822732796 208254676 333854965 944278032 24298842 518966152 805983002 829928693 15977024 121017202 14302335 898997239 31105417 579138270 665866385 650344177 728826047 301285934 364293842 3715318 674546728 230826938 869812574 403078975 797828915 499892782 906786631 939426098 518969849 595120480 969457413 194043544 934227346 709894741 546049925 79316242 726462471 339332607 186942040 620389519 720368654 918762132 501225151 237935964 354197179 199812614 373199529 610634853 575669883 465442958 339529177 311540622 984266751 639603555 627141804 233567770 491005337 15885873 38431578 755083447 828382160 275511563 289583825 89586931 858066498 351229506 835009692 477023097 685194765 909464691 752440929 982294232 968516601 776207860 610328700 495111746 926885217 294643375 976273820 182485013 664089454 49127463 700304922 17393773 742223330 621046297 637912651 716803477 542752515 365361177 587246640 457717749 777256198 810078407 567188165 956221176 709641567 841645427 147275601 540100418 206901266 349318248 183374293 217660678 795148756 610082482 446680044 432268618 136005201 444372167 571905359 308382291 475295843 171309292 408804249 942675244 275238311 791280535 865524934 500925851 516165975 953233350 92902936 523101956 461619689 998873800 595571615 360748527 234526207 371973573 609572375 967721646 625699823 723168905 795916942 962094274 271794922 94003096 545631093 79454247 905751637 605500433 979837468 137907138 282913160 568269685 244476706 955750533 978946925 185224095 716089030 328007672 355879472 926838516 798946805 536295856 673445971 86205222 706180440 675846883 377395022 279239454 605683350 328335356 81782927 936041251 100160778 894257585 603701000 953758513 981460335 695330204 62216498 774304212 224195511 192425532 13053515 956598872 181869022 740228362 597539172 664191229 943245 602534112 9712581 381988627 111299947 843813208 594794120 225421034 408562842 579578556 10170542 586759658 778347947 882368928 767859766 142107882 326496677 27329112 390753289 537563214 835900686 973341566 721696414 89765011 54689633 667441727 698063287 492660505 730481202 396891031 150763281 67991206 391729104 918211114 885518808 204748901 95784647 729250054 704633314 91559037 298417939 669462117 259770357 932771290 776268028 387351111 358427267 139541513 545549566 118882382 726077899 447730727 199400418 787769554 916858151 429774503 369675724 589098486 525758527 387444268 544758685 124767923 147312352 48248835 688786806 538171521 899384790 998549930 497979209 85751410 572789050 438646338 721096971 26407257 864856547 259092691 920065334 342517427 611572378 600348996 471076801 151521257 147191934 48007185 307652234 464482443 46724927 367877497 581459224 6595711 30689893 205843064 853536175 679032711 259581788 450517162 540880146 448883732 582640387 146351134 212926689 989225928 391431558 228764909 939116287 200650153 423602237 630470741 954865145 477523143 434463478 634825146 235050807 504358167 754430854 780830700 431894968 834211576 271160561 542017882 780114889 307451478 117307413 637271599 589896514 184560515 46410122 197308321 823006160 606057917 450685645 619807415 281913701 464117797 143558423 378168320 336601538 255572850 122837273 972948226 113561355 980526774 371455518 148260553 744996252 484031942 930910348 645388131 644104883 214903824 80134300 654025020 701207261 880203102 972805132 641302371 437856581 29355079 170860991 910215061 307058588 389710761 137465321 180267333 19303016 979506070 740657816 681073979 192624978 407518059 315620960 923394865 152440759 728111574 200196404 361960842 567087340 805350448 264806719 81208915 984841746 61523141 71883404 290450287 946525884 460732490 847769183 958705107 928819617 629798763 908081685 856273587 369537444 820508616 522253511 180869295 611725395 464050854 55442078 890590545 417278579 433503631 169613798 75989490 694869473 488228158 661553588 755404432 321203565 436410821 950428516 756229721 576450078 509656974 677676948 768454469 391755660 291947806 742644185 351319482 643637057 638898542 794812772 550401052 415591221 226571889 619468786 174460058 257929013 194467802 924654170 615457917 682018315 753432112 14246040 814387205 779661514 77278942 841614759 329279833 536779929 594012412 906182780 904908879 709059004 188531797 785688028 360826930 792830960 43804640 767706646 118835492 182221679 744044906 894609587 464558383 855312432 62154110 140864367 788776863 977144878 403507192 659585056 992658974 352825549 890774814 573607101 702555140 269988961 982350814 630011631 18091445 297163300 610009738 266265631 303218145 656330281 43381331 420159022 520777557 974402610 813202725 566010450 127394661 299918510 369620295 267741373 645151801 890647682 145439829 30543594 482110572 536239297 6722129 568551442 340180812 116733986 649764098 300224904 623106006 538603843 724218782 726073729 22766978 211662156 837791155 116730988 94496964 339493242 779125826 716197466 980569012 57233538 894087494 665900835 670118821 403825402 215889919 945294793 162393690 517948679 930349671 498088634 495078580 811887250 369864653 797866533 267190254 534558531 389660511 640766343 571703884 669966152 920163789 473058279 617313221 586491619 236571135 42118950 898913109 879500622 551308115 577609427 561115536 667728994 827921448 146715133 864715402 219708570 684934139 338056305 183962393 213040519 300812221 532761990 17817618 622161746 768428782 231756660 235927571 779389845 760468592 693773698 512585329 21929285 510926130 316787968 939208589 876107217 567647537 502983987 190761358 169435025 847680841 622393512 983943304 666299201 995703767 653364265 388201602 602650622 616681182 23053181 227552155 544124366 286984119 920738958 457029989 692637725 830094475 22584378 165823982 855632303 260923566 214266771 453260623 221030259 628421143 291896217 782062188 765954014 719174929 388653923 420450482 862509885 227289698 634459083 238966726 463255025 717128986 301442666 430518019 28386803 198877110 291995295 785433500 134793654 548031899 145581547 706142164 155446050 596890871 268136530 185040109 290929170 391241752 764593369 290562283 425761828 320733677 555453687 579149725 457773214 863042788 398499604 701379211 392539989 736630862 748409171 958240720 203517663 359540767 344366131 839407274 919311666 294337363 893470989 74412074 615392246 92155101 941154588 691437362 623982569 271368533 731939196 64583971 267648642 720886491 962312706 651041865 393135985 985264185 644550399 222579246 946193656 398511098 754703154 153281650 859755799 222703515 729702354 609539405 255817367 452286103 229065473 624551904 765271547 176799166 111606352 157412651 91342835 51162081 623055024 739945745 907624773 254635124 994742398 782320978 693158400 891367007 944969959 488296113 86363592 952547995 675333002 269111202 549821192 353661252 189930544 975254672 602918048 844907071 634130117 616797174 9941170 223789833 932206392 836606651 731197090 173632762 308153362 219416009 751165782 575082008 875001254 35084340 543303295 623510511 63323363 250269220 993247004 799962688 964486916 411606265 929017439 632392303 898916040 388551051 181531797 405976921 242584956 799686968 832915266 645296541 227309997 873635109 274388631 57447358 812632955 285713830 227466985 998107200 953763509 436695243 576488157 883551917 588460955 792205515 367811354 797757846 789839282 66898471 131561197 773175267 867857055 483440484 724589960 455598693 704065650 258771891 283933204 292476300 285651902 494598541 652348674 567487957 409435490 865985099 662959817 325200417 551879371 27645772 232084059 296581025 865298252 402840802 277147417 448310099 92629123 925079176 68887573 908462784 563601081 769581476 478075271 783547483 689700241 226902364 952685043 985242158 261323618 291663549 255528200 895484410 604087008 403270653 403738932 850101850 971288698 30255511 148887420 39322242 85391127 972604015 743184467 829983657 689733328 955385187 512917028 357632321 480628234 840332744 607800079 177202102 645118080 1862516 92414553 594515126 388067746 851119294 549823281 811681260 87289209 450031163 111543099 215106831 682457614 854365182 392975700 220768517 136317971 709887573 207557696 362272456 116347481 659282715 942542383 744923106 317315864 545619928 98392926 941765067 478150237 41223348 362454537 312004414 825450605 147618193 615683816 764475132 557321310 311889869 870980690 766828740 88502478 780266051 684867175 227900764 464267992 348728629 353361882 504311999 799519495 688560228 827178369 209789438 739509608 95867977 530094089 910754433 240795957 836967030 200529871 148210719 243899032 512378146 387472994 726675785 218690908 81269481 778800375 36485548 494603844 417095791 498747025 718904961 302969566 434051587 434036484 466981593 86024701 988819007 526885687 443882742 560849328 64506705 376843830 284003212 143298574 619026135 547091753 127152250 336312717 943150017 507674189 829995592 208292289 994510241 51064398 130345709 922942760 508995624 427974667 629371104 41629548 710917408 49198446 2927605 447833671 3933363 358787657 341622069 79642194 925641565 743702749 941818091 336036762 220354300 268634445 819006745 138951718 650530980 664807705 201335405 827347853 183334405 911762342 126673564 675995311 422059387 771988938 491493982 667372589 894953564 482435179 488765830 614825164 753877644 230501330 407202470 273506454 130335014 575437994 930781906 771692749 213547368 536201565 255118201 912508030 126093095 312065383 388319100 991534864 364095079 133538487 152440503 430836283 727971168 508608340 647646765 63889095 855914235 652490437 996518763 314680722 50419441 6286277 601339728 7628282 995063805 251231439 67683102 810897878 970860036 522606270 204014473 222150080 352538656 250443683 394652829 273326316 318867830 349083322 789399953 38910078 868689318 649245374 661178910 708287391 127908234 494380625 827977573 71006415 487028233 702400619 823353343 707839190 487333712 480090826 700173642 820111613 658559797 20327901 803040916 168729360 643215717 159962854 739455678 985109084 757695267 829777082 239854535 644335622 869143844 310120297 141069511 25020992 595130109 176778623 728814043 78248178 177750567 787259510 938327208 89090925 19397340 679534640 469848215 185791886 304370421 950728973 97142674 166796577 866104053 421121141 114587979 805684217 482125148 544521001 63389268 128709937 2489838 297264791 374301338 297340188 716657108 35240309 314705228 305187629 285406403 331909947 263222194 101251213 115289663 855775935 1436737 276176303 270915778 429294889 212677601 205005369 855033825 279225872 725053693 857988094 800780230 259275159 132746672 561628565 234525051 397323956 328853765 640239409 841818399 276391520 904131751 529456943 316685349 375875854 312935824 447962972 645082795 621352050 514266723 535896524 5557808 926769499 121424118 148180861 108209504 989822966 241470752 784194204 38527888 861052300 582723006 606795279 744522044 758259677 434056510 207802085 570736851 677534942 895492118 497966725 787699123 587916352 422501199 966376400 196566522 479394611 377359006 301053984 208658361 514487380 54071240 455995449 204137505 648566451 475499869 123021761 906178410 937886374 968212678 919046859 264767030 680752050 926223726 375384345 692436049 909317034 63579162 843905264 175567872 779519058 836180397 878553399 794197855 551238756 50719528 433912024 39160331 300209256 62562090 22627671 731029254 202586452 641245428 540785856 906132641 958946182 430495132 737415335 497931098 157607658 434876181 862424075 748296258 13684996 501306486 231576591 454919464 872824019 631033416 777183837 639272855 179039959 234432944 216762729 628697562 899424127 772433421 681774450 854621589 760208153 134019330 230239030 649326801 677273300 644032055 791685331 56363079 997961719 925827451 577825260 605363674 893862279 270753977 755595746 138495912 172244654 326927342 227125380 130463249 149381829 341416693 227527774 56434482 92554215 375075444 562303702 82686887 727396389 647650475 310918179 956966871 527979796 443594623 774441032 924130458 141120208 560602303 449889355 587541524 312493226 262055135 411592252 101601656 622749543 56122461 852705981 571049798 833734441 969943532 897462580 292434413 81491575 494869720 813596046 890520951 417771753 51366463 744417984 512085850 392786266 437943072 918913023 834411825 135342185 947631493 318432143 18282651 865401304 983683541 102331517 547510806 935352797 668396302 950162766 50115741 306018683 979615669 663691999 595562472 238881140 26262458 799581608 62146567 697390337 456965079 831637608 518080554 200034030 820264100 117214829 824366509 503800059 673569509 833097603 580736302 242263043 407634887 919620394 442303357 162112360 523122904 370576202 168570709 536172922 209976596 500887077 356463525 944158947 481636043 490945076 489678354 556122311 891115034 986378032 940463770 368065688 987682829 280743904 370277279 768571487 884656653 845132160 158901390 379091856 723914514 873805726 391677954 842619775 717775677 441027906 323592573 197495103 675811508 549540709 776548445 384576579 720816962 366820169 541677474 205526364 332099085 76641007 796516661 345625511 12856814 610035213 677054138 306035714 139563805 67740542 700597343 919090801 927379856 131104143 308867960 836434319 421858243 248753664 179428917 4662252 300784554 265397181 541306073 201045001 29346143 427097944 368327485 978441804 98103096 464274077 392539928 79034340 836395815 136036151 621024986 752453694 337155157 743386253 574534150 480747371 681482885 541357956 54118147 707019305 603731293 245173069 65971462 18843784 774408834 115670140 149685043 977083982 462262345 496012620 985690409 976336465 919645044 359732241 586141382 53899669 787272308 277098721 157073320 89787603 472539446 346404991 457691063 182514585 96819243 302006700 710796381 99695790 287914196 150146895 65210713 816740093 567677180 423422005 100031192 440712534 714192495 386011582 180129186 478819413 34096886 253096667 836781954 962283522 224656826 247523998 779926942 264701812 235390034 914429935 910095509 644559246 537898948 123891615 934146659 673122947 414342496 215902436 266781747 40918193 109323170 240278730 857161234 867188969 688296014 183414875 993081695 294276100 784701659 520423020 945894187 969611170 388081288 830621696 460935460 605015417 78392271 517094302 890655055 628002623 490700510 791574593 631607966 934697095 53680864 201230072 603657761 799654733 916624998 604677913 278637110 947657758 625123689 18901025 319613225 237097467 575908227 915580712 878780254 319676590 247941675 311317659 353016742 218897165 414031991 430299125 771568541 595179799 284773397 176671345 849533051 379795394 119645891 360943045 468649200 250917517 237909108 150813002 222579288 539384451 709569040 975354000 900486982 726838649 437451694 229748053 645689991 992249695 42992319 220576871 222949717 894127830 44852577 625311492 904071175 543621535 1404384 711919939 806453258 804345791 994176815 631045975 889135171 895529174 217674934 242975465 645646561 986068274 326665357 542020278 692229544 636964034 862013882 350926620 513545328 660271976 218960133 1214883 633141084 983800739 749845958 552272767 615002715 226697885 447689963 181192771 894167635 911916821 4655160 397976967 23610752 721547163 172351854 166045550 913944223 542871827 107536515 817777903 293960528 583461506 681160925 229333077 341603357 505235191 823509552 533105167 556238122 747811971 268807729 261283889 993491876 369473488 439585627 74803779 303102519 30627485 144352049 989213941 522425565 408170067 611201056 881087001 628547015 398935321 533542402 103498481 336855133 693145269 846140385 767543344 743773797 136265761 223730879 538037380 908644691 104309733 700342055 207412012 521182095 475238671 419080409 395109923 927792395 691140762 692225168 981277570 951109668 588783441 230164968 812203051 839615770 427443260 201648442 93064622 471443649 573606445 536051959 443066669 744727418 346825469 250497857 831509977 656819535 786339665 16827097 423686390 173564011 542723123 365903125 353130290 868283890 943966216 403429898 629097003 789703797 593757046 371595072 167608906 407675483 971435306 429141787 164671907 157478103 463334085 9449898 619662360 73883593 658662606 249602952 135076949 61340111 231253418 570886283 28690285 160117019 811140434 532643228 943806363 41411065 469738690 777009814 67548759 560465076 21444693 539749236 707726748 148077556 165842203 822409712 445644220 307921757 889460194 183455276 637822499 509347751 304316296 707155161 512557687 535385463 467021547 811252863 253693118 143864976 364732650 264159804 521189346 415434377 725750486 16674042 587259000 937050774 408156309 937055370 946174179 946938469 293579582 389932375 321444883 441753668 806197704 222719355 426633179 720039869 563173899 352677166 478416058 89685585 171867767 275366489 280135390 345626606 402669691 822883818 761464370 510603243 480097998 676514953 974981894 398708437 534186996 904465903 164376753 866767283 583930426 701999025 427670418 854284118 988673832 452805941 891103451 170899529 722055250 65295574 560592093 492193461 294153925 926185687 659138983 611020337 768812399 102240256 484946947 673069582 616620751 552341790 618023984 213771262 110590914 69830387 981077696 169856081 890668613 465293153 339315413 697643870 175334276 369290153 687013399 185000220 751213647 5981692 653629700 966378387 848644499 388305019 773006171 169221567 416327337 12398610 916758026 928583148 543174951 667965543 176929060 702499531 271469092 824688538 389527130 107575875 756267338 398521045 170740940 513510938 764004421 702798674 908761492 464430304 817502478 44617950 127156887 942759891 27052978 246119504 679650321 548920628 406233950 22896450 478250782 959730780 651128469 540624270 558929926 451469694 346523791 404424312 689223629 100285646 830544341 443050954 595688042 549454599 119648230 353974097 570239282 15367009 850813198 622070185 370030522 588088342 776604235 964826653 172115928 366858868 418039024 64387902 233017721 926680012 901682530 137442001 453487755 852387650 395177569 351239045 787530773 934942315 360791529 324696209 129226160 693298678 247962753 142783064 450664491 156410170 64446242 281389923 741852555 856656810 11271795 288728934 230597160 160166776 442221499 767973623 583128203 390526743 112396632 981709015 618596221 306100396 68797967 543880084 542148932 242214728 66642155 380902705 416380954 728873967 221343217 892335878 989935240 505397290 623669028 815643732 874655520 271082970 454884621 374993399 25112265 346805076 896678454 781405687 556447979 1686878 16821071 382034195 394844998 723888695 101044649 673929417 451531013 472958251 83476789 797008713 350130968 822648033 577792210 738685335 48135423 172083902 191984150 646516165 697702395 541130177 965501343 619128653 913860247 906924708 886225286 979883255 301508868 781810462 444255695 938015055 958189585 363361500 872031112 670236738 326824588 982969946 266502552 891199395 267065244 785541641 562766306 732268637 687180840 524781164 828745910 214726300 947915267 975302327 679950394 842755527 980149689 506244775 179589968 527639463 281359495 724854616 777122670 818752292 624606363 303758533 230575572 741644532 909585457 287879377 902832883 530841296 489898746 616500756 72892677 325309333 661552761 748041933 483600465 451544245 819983498 370368431 797384589 982261121 347229885 72793165 178794564 548121221 916651278 998105811 205331250 20243108 482108017 292067475 370793510 683962826 265514828 124179312 328658406 965696433 951007175 873235985 387063841 767541111 449254835 595766323 979843452 12901529 815497823 342931728 785777405 476216936 955352358 717460510 634218158 7256429 624340228 820039523 752747503 843401251 967794769 189005820 414018374 247704680 242088228 653895766 982210690 130445607 585150944 124290115 975614740 70824117 179747194 301355369 397906525 125679528 395152764 437575231 896368002 744676072 750265318 399742278 846028298 824254501 901360256 612023037 309317973 104869899 406489250 264398871 538395388 463989545 988546383 434150409 325335524 396506249 608789764 481449171 427679399 460207469 880419849 894343451 265177697 629750498 456696003 974396850 526972690 361180503 611415305 445847583 622873066 610824220 499807277 695790903 85722241 253801685 136233233 449620073 308203400 360931504 846867562 482094593 618997110 127638139 202863735 808191026 130461506 956574731 891908839 731096501 95589627 783201600 83321772 756809162 862936761 178452018 883734882 162929132 333251743 284401831 521413317 687354333 175603169 125986946 101742380 51601673 612146931 662684870 789102015 446665543 551280896 814584518 430014092 667995519 116738945 404255920 238729225 207305101 148369504 160424566 473793818 421480907 974070446 663991624 389196363 441650581 690321054 819691998 358877389 162075723 387619458 107707051 996318834 368600430 928333763 645610155 676680637 104572647 810688243 587065211 325969800 413178904 74306129 234904868 872854978 642942254 199254935 790423588 593981778 423025534 372304312 83132220 983783280 388929534 325856965 324588424 979721614 609196519 525412097 707411578 733187554 461188537 912833914 455907572 550109272 412758724 98216990 892746438 84730983 318579023 72245558 133642984 73607012 526587315 43262756 599847674 826366628 713253584 441860581 904812101 814047840 189502947 544321644 403929608 362299599 698515892 906684116 260634692 234564081 294485402 308735587 331542474 4117781 664745445 625579732 241999583 773412809 59971929 430188656 120822618 520806258 183130312 80186043 395334208 118259597 492689770 198488115 692512436 143690760 129694754 830661105 88957013 353978319 540227962 941540241 751042766 454751839 571989154 574273264 647580938 524497997 747377542 822676890 387852881 645731387 44484673 283726207 250586812 916733439 906624295 734898946 424683867 882663114 670887233 592639305 203478286 459003609 965414664 207182473 967731060 108612693 390886185 345716335 535098548 977179446 991366013 918586620 846865745 655586487 587204406 445754023 70182722 55074042 581210445 76137039 322208530 970945046 424749833 191456870 866600284 535807159 325752441 406226414 310233767 407642946 347062157 511646797 448611918 201411466 623450835 443036654 406978584 814749541 750460380 943787646 576133623 844027082 529919020 459822320 151064134 702470425 298173160 773265222 208548676 962092766 238155834 224232273 971601626 244500160 216074523 74557518 884081935 907816483 778392402 113986603 618821490 885716811 409102596 740553282 511514412 674047685 907044261 16702334 158016379 957468537 609104913 525265097 572464729 111894376 955159472 311327926 363927328 98948205 303013704 718123795 830526251 105114038 36270830 516343088 175459119 571300993 947236835 202356968 301456698 884181594 311757882 366346926 4067596 345284420 713283465 470817893 877302882 568784363 683991806 196966202 792522924 279064828 357790309 887672355 258137366 523957225 632820869 65956617 81122656 512154552 83326703 118809205 159999503 349605257 458383684 599585192 782552230 378850020 725222624 918249518 401124547 285090393 451323143 879599380 518803475 781124935 850482831 632409708 705132560 524129754 373447557 64903869 610239726 433088764 841067834 833052050 396502816 403957196 70818471 143571904 451610532 971699204 984144453 928708413 219463753 468684886 533813375 65134447 573711482 989818626 464479213 911330534 303049947 693775608 218096695 621804436 591576741 604676207 845906725 251869091 840786559 522286422 409832829 291976714 281810652 174734359 985532721 234982379 137902601 75875189 13484948 660839323 110822546 454518184 105822635 595772713 713871540 48386031 402575166 372017656 692436039 70553038 206097142 881469705 492181732 30022444 62526010 174189824 34876174 422166257 289363131 302541901 206667027 309852150 567561747 643836435 128136754 543650056 314338543 390371814 209751823 57462813 899224381 26820714 235515992 104376219 370272835 837626582 418781254 761364192 292133169 977584522 784149582 535825706 20583468 242175819 217335898 396487104 784026334 254210455 883432550 659082224 828363916 661702836 224548690 81368699 670371916 657772355 506513692 14492747 625731096 101995998 531059091 641181810 328183122 398537128 434491829 344099504 326973280 799571655 665833217 907283022 825529710 374897548 669940841 507201454 553470181 506149364 103086532 833511648 805590298 773507617 520287431 255661309 169168854 678013510 413480153 315949606 346994884 967124143 350363441 396543246 158388373 924968410 796640877 287593840 151515497 494945987 366573015 215972950 438577310 287285663 155129955 843360411 651585634 524980320 678805443 405027066 866017228 716692167 17512513 120927599 991487537 960651644 159186133 859934762 190087350 950346009 564138591 678279319 379757669 891471980 669506419 146160199 951261652 605433324 823668421 375752593 684441454 718559524 156820420 687780135 459886601 327587871 320197138 13759230 655071822 153559996 116701401 314747130 705715061 441250223 411849488 911611736 163412793 239883952 679476776 303439532 460719575 844255843 204122667 51731221 277792424 359964492 301602273 540268423 979928636 921223282 45277653 49141389 502502650 810025657 151384970 68171306 540476411 466397292 601777272 866049653 192856276 706261748 862253685 912878199 581807893 466584425 695903632 316802961 805425831 571326115 523977453 388043799 34775695 496773790 403720093 411884169 143920924 567394721 652537606 259729091 349209025 926711084 550304477 472705348 190055850 720554858 432751469 220827522 966184942 149413720 78025005 312330118 418910456 780492165 935065746 990499352 232618125 647846587 571121638 798316875 491532108 949893470 580182446 68052578 844983606 248104189 312822520 85285776 210420030 192446161 415041645 780127500 834316318 299327748 198395464 993313218 114943729 576646612 843932651 387765067 917264396 605965515 100709770 162481609 613525696 729058814 179215720 360155220 127915207 564093231 336892075 127015181 773070475 840518389 208303061 1401860 724552331 140246564 298201336 544167528 624662894 398792381 19098019 73182515 671142853 352802076 547210853 688647612 262609635 470061819 919599015 619887533 235162171 419428281 898475990 590885608 855656526 923710592 476266857 878704625 438574693 549213578 49517454 297443309 382407024 838155752 948094919 223739259 863603563 675138409 21065695 994529441 768397729 776890365 665156961 438074562 887598079 849961385 980445631 158205103 450238237 317432075 953395715 211845965 380752227 96584910 555968539 772535199 189280766 439223489 709690933 225510629 776467141 189900291 624322204 173901568 301481978 970496037 757017909 548631710 391413050 321984811 112983001 872599940 333793492 834993832 275746528 891343566 690580272 45209230 254161706 513755680 681292312 978258738 973511465 591358169 478839413 870938540 923485525 556622126 460948329 214936019 127986992 171112434 523207117 765155289 238653613 470061553 257600487 821957192 601197020 45306585 897244987 845080897 54717825 887692903 179522607 286752052 24943506 923501398 350932947 503515582 966551451 638355346 370032847 601053710 679720915 802127976 456572534 922508386 968967805 174596830 693012656 921554333 227244994 414124340 929520558 415881669 56409635 942173349 601005337 718077186 715411894 750961576 360453403 813599386 122999006 101940192 204158860 545172269 946811362 130300867 781393949 999326526 824347049 700794135 913385004 89386036 57136432 866187214 143217665 856054976 419642549 99818200 661015519 313289953 635463644 591037529 131569172 218351689 810576454 644813964 511599502 761090036 969171446 979499342 134916364 3063934 294229106 899292205 280930218 157135286 79011031 481993639 627651519 373161475 453728904 391304998 507617903 718721408 581165217 923824938 481785437 107232786 127632553 789019123 265725831 667888185 658536965 646200132 322222290 718974263 244335164 60601791 285844310 823134982 12661553 910222897 247219762 549820331 530754903 128321276 408079552 690149040 890403448 809363867 733893588 455190355 465344075 869185686 404159417 528055252 399684386 298224060 823312086 553151209 189992686 792873702 80326771 518452998 529230391 201121330 36716761 760426634 800686911 427319588 409384541 594311938 432296310 262503575 571580874 581484361 480065999 877143489 404823041 204238503 781732486 136136878 451454059 344530181 564931812 338713983 162470803 729416107 515824366 375546734 512536959 228387431 884830616 946543115 907830823 582519263 442402758 747052649 190919484 316037507 859403708 324843203 197229616 334655977 414938024 728455239 747040605 211219479 122734903 847563735 410856117 628279994 185762188 380441936 578779691 186117081 443962528 723114915 197111719 119569411 594680959 966237180 983918512 25627212 139946319 711525481 223964783 14468164 871701973 517918190 690109826 833450750 331968671 396142804 638063462 367560898 347806383 136357158 110571181 349640016 968347415 446281697 687742406 566637953 940707223 474920168 388962987 117434950 96519254 489665424 954598054 186982570 660516262 106530200 921197304 393296623 40250206 180384077 57080481 375995373 692368649 893138888 75258470 550406638 873107467 473501583 433376041 175611002 104031317 334822385 597150065 923402662 912747738 919904076 63341695 151378963 721574184 588284978 402870256 644937174 717728977 405776040 295136087 109298941 694965525 281040146 679178906 793811509 854101712 4386836 858743298 390808787 175307014 118359058 574890513 273423369 354079236 148416180 102385058 792892010 680797499 719482425 218902205 107401855 815385716 14578407 500279291 602982270 630770284 669060639 87103883 754241804 536507524 134049700 79319722 372238267 122609712 904807486 263913757 707421530 473713957 85419538 258636389 998094458 703481599 316370886 523783456 531755612 109288362 870989360 283482330 877799491 246426211 759034024 39080626 771873177 432652889 39197412 751598687 986782098 625186955 807277878 292836888 957975000 892184635 320355209 919846380 968383607 517527050 744571970 313006753 623782369 703806016 410485589 963407414 394231253 640221407 909351202 239974762 501742242 802474744 166363362 963041067 322121498 981101087 364132718 893922967 414762585 130195256 484421742 215826200 696907664 239453333 635643642 394664741 515763600 878347426 578188669 948272289 475789873 895962283 594735026 221090032 849621810 807824407 17563734 202932386 379540269 10917792 80445183 866169736 886718648 361655736 712977357 316298634 259695525 437299977 462195299 87154729 246206351 732393815 920652999 894997590 52977383 352544792 828265376 837112774 250562611 108762222 658092126 785692807 857759187 957394996 36880995 763210584 502849576 727068476 287948752 529183651 761008357 554875221 947647782 708576106 347565679 899039484 541451406 733698341 936074937 18681191 585510041 696112637 364294860 416210564 46116413 889731212 8416806 818638815 204880445 742255274 553912227 520450605 12337929 299855829 567586676 402125430 265455625 688108053 59739437 601943273 600676297 846750387 896796598 911634613 534427107 229089843 30598336 317429830 834741319 623664699 359000538 903795916 126753991 401933412 889922506 20841951 265793236 803464959 882492379 148647364 702111667 376203968 734238864 863822686 777602927 140042702 344448112 910779728 753209679 589595415 393244320 363825395 388838445 644977421 625969567 151065203 213481632 21180070 376610411 794517098 176734303 545949492 832472222 784217036 220127486 84390389 595830306 248608919 51663148 442458155 417019296 321439968 625808259 280071465 23486368 110633070 753944921 715500017 441210507 126746152 62396184 496877744 515232268 163837331 269314069 236603859 502817193 13229038 325320550 87752730 632592213 925749251 287183712 475204362 264357983 169526199 291182283 515437566 509260085 601446595 479633530 780570378 345236365 239376760 988828081 74725997 413119970 750244743 400275826 861581213 755498210 311205533 977845709 614943183 652089612 481291951 87547060 121556839 581359321 75392327 269728477 229995844 902920971 879056392 839445582 810371831 414513706 422321651 270665711 289060188 347099634 106880483 776489949 128980468 889011753 540870775 532072843 553995313 402388400 9741405 546583335 213619041 17707449 5181518 936373936 16932286 957572479 984118485 832035943 61500010 467152890 327277891 294983610 664246130 371321437 409334961 44553563 142041902 273588716 105717713 105503775 772240554 810959969 946091404 775286872 192819714 498814497 313872028 37634229 408563935 445457326 255366807 734228074 297801987 747941754 966478568 718745717 623716953 590492182 435379714 333072111 326235505 893501686 758766368 555080412 961966655 683863465 817531320 237336047 466669859 725838934 165775930 581717001 129591574 166269244 192046673 877384524 845757210 576115549 586039941 189936914 727822361 253771530 442017923 465687201 193213645 333600904 534917425 524507567 93827296 424535542 490118747 269053523 166743798 634162415 873495439 364035522 567499355 815725894 232188195 456574255 875878845 616995625 569015559 418928954 222109997 442490925 140218614 250033663 22214859 828420221 600820963 321125690 899546470 655619702 763348262 613232916 83537675 676889848 853595372 333128477 785250541 822663444 763752292 627736862 814500688 151746937 872359569 373742962 435682532 129384255 738095917 597939904 316918287 359780000 372510944 553463160 553785435 476881793 153478061 880984206 703663682 960088904 336933678 77202372 951389556 475662236 368286382 681540557 903646967 511504154 279002655 112292378 15154957 220432130 384489286 972635507 311131650 213067622 942730494 211301061 50564130 159864244 308775451 185888100 65459095 423188583 721107631 680867281 837535257 47223008 17805436 75265857 471240839 136078233 879664972 903941289 588622675 676261993 454202874 816944890 522754641 16057813 676004175 961926661 480107472 399864170 948046973 823294806 512839105 355145727 468912793 657781235 496428573 599256192 960568516 407306085 858974555 392927683 250949892 673388809 43709721 609081171 772304256 783771361 617121245 3808369 681517899 773941460 815386110 601246954 89782293 695758629 828551674 512321424 256520969 829045679 700586990 847210738 52330500 975724794 243028275 542195213 909515173 205447295 237058302 272472579 284511925 231409446 981361571 313205278 798296946 996825819 807784667 329575222 576109110 235812813 653287907 653703276 360250863 956974637 458290227 584484059 706811163 578611320 717010950 558082021 550203419 444558155 590987193 623515347 702153943 616688865 657931146 203080239 429778281 236438969 526387603 390817807 512332744 748190147 336958315 142120515 258590000 380287238 951759009 74091611 330748821 936001833 54076962 431523097 44025744 921724153 96835053 227662221 799299757 484525677 981410754 403506873 55964045 571028942 315006762 328051719 893815568 693949880 111213905 297230111 881596645 421000071 159510513 409513718 950560188 560026341 73459868 783175882 962760127 146009952 615626438 16461529 866510276 761114241 713365701 35012705 53093081 519359046 884993476 338304034 921289004 952050396 89682433 350356579 152068397 269412915 715376959 347480407 122253893 699326539 497807275 600926312 334784111 246520409 386968553 976609535 5241194 414733138 714832247 838343222 188857002 841298484 521341182 462129293 316686500 579597999 423216064 956571484 191357143 719185950 184235996 311047164 549531040 78620049 889645532 961308544 417002819 343982698 126958828 222067274 882324864 384809790 484491493 825704392 761563941 951240387 903125662 459873179 312540329 432946108 898383403 53522459 481470660 98509636 512607633 173902631 719797870 349759068 255355341 915881162 698965280 396872340 448419951 714653328 551795609 698647475 856678019 996537158 261498287 185715760 307963834 69930764 978725524 183691226 729632047 253929752 310235003 659381653 722704205 698083067 244038298 623206229 160621777 440118889 876185998 250104196 428801322 641226755 881529701 573646755 960767356 939349026 35136277 532992316 21124373 780812246 743567407 81714341 13207964 734336038 233563035 601541790 755325570 782013323 881196298 627204541 427504732 936815458 54890977 970312279 597212923 953046791 77243465 845990857 238228245 118766596 474831262 507158255 349731527 948074245 515936242 586792052 831632587 445077485 647250979 78833298 669614822 887677992 657112360 973242020 537021791 727177683 959641780 778652143 159929317 185258169 707600706 973285606 489341651 790945432 897228878 904077296 542064733 786244719 875054914 308803372 356048892 771461049 583473320 666588570 258570354 835991682 642530429 41038441 693013748 576324913 174967520 385742544 465393453 262583205 496073317 509321224 62764750 43402181 612771291 26582128 660889006 236655651 458062750 2966653 803518821 3134189 468076936 424167700 597714006 67907812 764377627 914571397 236157610 356956868 681517501 971970949 892196473 187142169 971799599 859470801 679957933 69518017 740495169 629641742 398735599 833420438 823946071 240444149 67768573 655952678 662242328 153450065 868640579 407226036 323002813 584000953 840209691 629926390 61535978 278634917 568981311 917797786 188825722 835518660 64998061 948895005 35650559 469390425 702705282 958588507 112690086 367326474 466635261 256807358 539732211 539055011 588083602 397571194 600856030 411876740 865753017 636853657 198065454 214153367 446320402 484409167 663486207 32305195 830299934 696971195 375022044 628605679 489319032 979595498 986583772 8854415 32804134 349379573 828587342 180401995 171003977 598482495 783824960 292239451 995390044 782582093 130754363 977621405 838580559 663371529 76816946 819678819 435792741 731049821 738610740 504490151 135313987 426664818 653782731 622376615 992375623 417627751 167671817 397525609 934237139 522315567 787568014 516019125 169735192 725872795 751423932 887878639 741787265 43624285 659815310 262434222 500480453 109009067 70689227 610567582 320955704 988898250 10598561 115811859 690903144 900256236 154587362 522049743 158819076 326343406 174284435 68128583 160339339 238023994 574023027 145136621 235742829 866003504 124894727 742908077 745642334 887993170 746036889 597634555 71174469 491639690 285651288 622714014 175844484 90315107 622430276 568452345 371803114 697208707 930204800 682727666 653627119 190371720 508222474 952803006 711148617 638008477 628322501 341337647 473985746 667294687 830717198 533863200 365453806 371746842 56564321 625327867 495512329 154763641 824539266 176084625 74868770 22920116 953090125 892750750 771480997 477201240 604209619 224198446 11121186 84969981 814143290 342993736 938924359 205711436 944988895 367139148 507437188 74098085 84347630 405683093 935078704 547160240 405327071 582811259 744635479 343584209 311605211 164751352 479667684 998962194 978243788 765614144 777096365 267440662 935362358 688202159 673832048 210616293 231284428 698176356 877933084 172504064 555501582 785320557 626299845 832038344 923775867 179006739 85244590 519828415 874671822 348821784 250427808 855006384 244391138 255738038 476063522 508131167 617191629 646220016 356175572 412186980 588351377 427175126 950335646 789265284 981897037 979937006 843136561 809943111 839730119 669935925 808917694 912518710 963811578 543127477 926237354 974018652 28037037 503903526 733951644 147425342 410757412 428912432 395425209 217263207 117141631 665582110 965508137 921059329 523498427 346965768 146402740 553921276 815326587 234621672 54931429 438787806 181644893 676064975 522881917 322698540 513878389 644927042 266846513 913427700 130676771 882846947 196656393 825678476 9558604 463873385 690327381 695522393 987609885 345219031 189838652 831062922 928835198 412699216 173018483 580442259 405988551 470822046 383906686 498312443 707399339 557271883 713251715 16888970 973408902 240319236 243610015 592526529 759671749 31493367 495846663 585774885 143016896 241984148 629759274 294207740 564633160 641947207 392163535 440488310 194861479 3688820 473926867 798463842 34884842 63343845 186482626 598830264 257791599 404000902 613089128 274335382 331550529 386217066 996867827 440853373 488881072 343576709 889625846 972666121 858390179 439920356 528416492 104975717 312201665 395421121 871958143 115696705 945276083 4150414 586922697 251952719 788649119 328060189 8307383 165787498 835136703 890542994 58965533 753897186 41729613 79649145 786258969 573286769 149970258 512981542 56556426 251677337 730004244 746661248 343968523 89010057 344057089 307243955 194804009 14152666 824401031 429423031 275822394 292309732 277378431 196360981 277330276 709120602 987173811 743570485 290266045 886556050 19877026 719009588 633753805 220061897 863335555 493434246 265785010 537841288 258073067 809652150 127697789 322650777 694212298 457692114 41140726 788031440 272171715 326610578 260666580 853544571 734110029 115017925 137128713 810258939 619343613 290928947 578103767 327296640 321735823 755191355 160807502 103881268 948633121 937245181 118554037 850651804 396039950 364174581 10818157 29483128 398528142 426581798 993616493 319230578 35548784 700260856 824258250 655969748 625384162 816730577 50705663 158201896 72037451 776516774 492811384 69650348 586672050 460415185 35241460 958955300 350990019 695851146 861308160 709060263 54286785 386450754 752668227 371240042 203983481 996030202 971308829 731154095 565353823 908504732 551814349 967406701 927411021 959356526 75566548 544930801 14093276 290628074 788750824 7508956 25829138 564919045 619174763 452531965 147558503 822851058 500638571 963087549 932812595 695104295 13302953 458803508 238042804 427012433 681855455 426005298 314535551 406923190 601204250 45645111 880069480 436541484 49169165 578001726 600453018 73155977 426531498 472768005 552414030 231941876 479131076 695340742 482032312 323019722 967952596 956199872 591778095 426166146 748041956 24904170 680417777 896947216 485771326 881195405 980932480 440374955 44776229 743907309 536051249 333014027 15496033 337260709 734273415 565687610 997002697 287891563 660259213 130893483 636368754 27995992 217746011 15219857 615955171 786702249 859664303 424250590 79037216 778834864 939666782 755837780 330971154 994661829 326288512 423728085 171068998 195436339 950373849 596436749 156428717 778900153 996263030 765278864 577153475 170207561 104493018 99716373 121600361 205341377 643585814 438339241 731865119 863131136 502720050 77759243 427132860 600516761 922618064 481376125 696280856 63076678 743108060 93580226 674134342 500126291 833696782 375691733 235231986 396457196 943986584 647159755 33962905 941925952 952270435 843954614 702348764 505609990 241260033 582439810 390977398 559970586 82726849 496922692 12566696 426461681 90977459 137288370 883381818 204075496 732864238 898022252 880130221 179554359 929646034 825995163 480701399 508670566 403414081 961973852 350656398 831206752 545868244 29961766 795527172 448986922 79827660 732797502 718816690 848989425 623274762 905826036 282424623 945949847 760595827 851589597 503288879 275942795 334645007 557842795 761036739 52319385 68683150 150215218 715455985 562930766 564279276 818085546 103253961 821942348 297585365 684534817 732246505 723758005 333886480 496667361 910521992 753189864 268589949 358065390 436810553 586889589 241967839 853043212 44703110 462321059 497838005 166483665 402238721 999962379 980045705 747635348 471672846 200864241 663103059 654846435 497150496 631733664 800885070 441404634 411987306 254768466 120231482 81044678 741439798 373919890 585499306 313733250 441734358 958758193 232059482 252377372 101645045 735279220 488472884 720014473 783705401 952323088 422606219 361283731 617557554 996155496 989835404 548684696 995046481 373018776 170673859 950828572 220052207 691332634 278426943 53777516 805800303 965055247 456837775 442231627 16913760 379400158 809162460 246465540 822235304 174764791 618174352 731480998 522466426 431998085 14249716 766407412 450021776 501134955 618017549 370041960 802364751 529727193 44975526 683797008 395923889 231857770 793214366 462479511 238842007 874625493 670347472 337959629 960173169 822383297 978381897 8269427 675887412 450907523 897307320 936278736 90622018 872296288 68021965 617575442 519183106 587756898 853713149 524797797 78206988 860326831 907026057 940990468 564086176 166320927 646277790 453618381 819356648 64549061 745547456 615562896 593990503 723077173 25744772 529531027 166315847 581246884 923881198 525577179 914916864 154093570 386197457 19503307 181817717 514583648 889775791 789479238 15147113 47096462 633431926 847191286 14526615 664461537 84718968 396515049 404969481 218935920 409053060 940526624 991904774 278154202 493550292 983958022 820054235 220998060 358388859 71661005 117964949 923514656 371980210 234559718 803761543 711332847 404150638 526240686 128026041 799962275 30522799 602502690 69551547 830972925 732323278 585920462 18754732 261286511 722003769 203464527 603797349 553367644 906058562 199568215 305855546 56596501 297999873 918173753 696698404 164346704 436585592 199615678 151806989 162200036 715799551 406756521 114051729 864569123 62368236 644005805 926750717 343873580 117981807 44793629 750516087 787843181 887887620 841559048 412935146 284189654 777575072 750452609 225143311 71804755 917949983 892898996 537878574 145820797 762375365 544244322 36919079 835887349 825580426 211628068 996974321 271022170 462077174 740610737 644993046 235134387 997291193 501519610 73271214 100849697 432969379 119104772 829907590 282147851 144378886 809074621 480190441 893638027 188095994 936788225 673779628 363258072 161321833 265860524 643565075 643251880 759002564 914722861 962351056 302957186 400124449 648468040 186035275 539197373 779705289 86399 939851565 143316654 784516707 136751329 108036090 578207311 418417702 284933157 78380983 7821616 12421007 327673913 994890693 299365121 389175493 514197398 855630315 20054310 909117805 182728379 683178115 225529025 526568472 319702644 459925134 380208204 774403331 326473415 922217201 227840925 535212106 748911757 423555179 325532817 961051630 99791671 209821616 758989231 117560240 207133577 669968079 484949132 488838976 869163390 402981237 233562120 513299177 76243174 617891288 426553426 89495099 111747201 63267057 665075820 505378832 891959597 985301825 408655649 94620224 875389945 431467535 253241658 448323564 939138770 924308082 700512597 393916395 414977008 494450207 591802322 922349399 510425143 518195462 879585672 846946102 472537755 874932499 652963112 374240548 519996504 905703797 926001313 542473226 841886610 33281671 540249413 57949324 145712686 453558357 248416147 800672415 45132108 53069490 211367151 759520945 79232085 699026832 211969813 329111374 723657147 795756234 969955426 603778148 568598344 768309763 834296866 963209664 230899302 142029145 367761731 792564162 257289253 968084988 81181159 661472069 933300427 183248340 468989060 737514847 188646078 708489310 29699425 555543099 524425614 543996825 821961984 239636417 144364175 889925800 872336397 858877049 554758320 842509073 354015993 200424415 487583021 625091083 72537098 925935858 602934159 464942779 680455743 97064524 578086303 709892797 326384223 156747164 877409316 8970769 989391436 972081786 225022404 617929233 758377311 294798443 18989725 507082018 385074669 442179210 562388709 586873041 738122842 746032578 573818282 185666450 113585 48923588 381561315 657937900 667600268 491935102 221427145 472910221 847550543 370924393 159112760 210711708 914491478 585570932 919415392 449870030 653556626 628235785 783651567 213241177 655086816 853372994 846709837 106180268 133931042 976647923 381738567 174953223 313355610 649561976 190389755 296044354 402636081 629699764 30647217 561463981 985438788 18079808 626194898 931071255 628374912 294002351 51711488 377298981 485154674 662822976 302758086 419793151 487063134 227911189 802438576 396073356 577629825 901850873 440209120 642746656 251393591 857731834 651174150 34706690 743477495 807814711 24575759 788176656 135942917 311860227 801611699 431268293 58813687 88302802 290881687 54568058 471323104 797373091 22239053 291417994 418196559 331180305 763069292 468748315 665588579 177615290 436786181 733962377 981121293 987688262 310902339 17485136 942630780 510253483 57772730 179672436 627035479 711108977 935686201 30468621 648772647 759795371 748208279 911443770 16230452 442894915 966294320 225981212 117237168 36255394 519776386 525555694 359499213 318796467 803984497 573031719 402451084 307129844 374501441 210033144 545976837 754221745 959658967 592763040 50896104 849977851 924285086 327262956 553264599 253101305 585244896 793216510 139122122 438600543 589387838 424635313 175316949 734019909 911906429 857839248 936911444 455595702 819497473 145688286 761603735 235438078 685186285 442734370 952397697 956732969 725318552 429120352 427149124 702615571 82402907 250272550 683629261 533051557 572433811 353840352 530128455 597064591 733361330 203830530 789799606 993425924 769460642 793504354 524168137 31294216 57694284 12951522 484851601 77102129 323612727 53459357 52138257 136940533 421157157 908450579 166960703 635791648 467093113 293443386 959177012 783481359 525023148 912668128 347698850 34956597 88051932 33873863 398158917 22560902 358933768 727339254 87154885 98522780 705952425 806616827 809863513 987355064 17247184 338553246 838063982 978568288 814747214 155540115 986281407 133082051 640861547 216382276 608316391 934512121 658046408 504532961 286053448 865367854 174350570 394835700 296082571 778624653 580053748 137006987 628849295 221784662 214845569 614144066 917006249 454232428 1273534 513732190 400436421 539303950 470020677 807512809 739562379 763665089 220625512 893221855 250273439 656632322 648056839 244010078 317946973 66872356 672532505 453605356 167747785 71596014 379917905 736076701 417807042 136450650 803116699 73354017 821609045 176847324 293091833 789146180 774946762 482625651 721502182 205559581 657779555 793525635 640356674 170276080 380888372 625583376 484810228 971113512 868879297 53433111 330356442 765852186 592312047 80974558 537197967 7912296 893272787 976678108 119222662 14526378 195766414 82717939 979316844 215250818 763924180 409505284 277181894 580067192 345948559 693887977 535579125 686398281 884201456 115705492 63521250 805761912 595999292 246162445 470025901 384356016 326755306 195420739 395206121 413047704 222986848 224036995 602655606 696215001 226776383 446520611 947333024 238985559 575138995 301160376 751001607 57230920 996041824 214786519 77179835 60134977 614982169 942564373 535614411 745326083 808706755 918482694 508580085 399515558 244894860 30424616 450184050 785798484 78096016 649093208 250032743 485435683 391566139 671231493 863349232 447285451 264546982 550275687 914819699 901762441 618257192 523691255 317718737 756013647 74610289 679445127 579428187 941560681 297490213 569138363 166932977 315763560 3891018 502472182 604359259 604090806 355546350 542836234 759660977 696887515 151713517 686381740 594973089 453878374 282765475 12891330 516255178 284845296 321928551 641412618 646253405 14333822 97372038 809002518 882921322 133194726 262662256 682648644 950540094 573303182 276833685 827234115 506609809 478224417 524330786 340071490 22429903 598656905 94278075 281270743 835651829 868631707 256718224 924712576 473571694 297905706 421403630 841475465 481797689 422496394 844488126 135615186 802915401 66809207 208192237 836842690 351098048 985433211 221987271 844008810 787085328 842502003 968262961 307202913 441352977 318876285 108323149 543626896 251439235 952556813 235541079 508858927 997203794 949123866 243876544 678654083 816886112 870285672 71098828 590884746 342120556 517023487 305296557 452601994 958526452 371142330 649877880 620608417 341305935 822920805 198831626 94607526 213030621 650717237 294261422 671873567 62485790 110276624 671503044 853269170 181299470 282006611 451541813 499222235 85311773 364342608 712901897 819000679 728058378 365873594 609125198 663572299 90443762 606853244 810653851 333956193 735878917 705793289 673708088 699437933 932619176 397893424 231215748 721991921 131995307 955209984 919300593 940158398 12242164 144925940 717088564 513337476 420994387 86169830 358720757 444223776 26712572 946460657 364059658 926396974 195603772 757334673 612853723 206208718 124813534 53791930 136916126 994236435 943625982 520798064 595217613 254151721 509645076 557714957 861438723 686745334 461306378 916984553 233208062 282784491 279888684 643493540 26662147 562325805 959364323 695251221 648632220 78715332 14747662 442327277 491288577 124990749 28305387 927917070 54056811 571965145 275309466 823698742 144817099 744327400 706989270 250099754 569956445 232914923 147010347 904874663 791734436 448158010 986516489 977780905 953512286 770213218 384883148 390907390 218901566 639659805 266589916 105024438 486215868 744490085 913360654 624350848 281216416 801474081 792489615 128279249 937552800 358358732 43118845 882230707 609940329 12493600 614372835 339413088 751290960 717441536 743953358 698728258 298966120 244579951 230346231 745472438 848725625 626513693 378347866 360312771 225272880 564430294 453407628 112537731 304801859 603306653 193206893 553726085 946415184 538906644 461169277 907762654 807044047 412309717 811590485 431692576 903133654 810067336 27805354 201852179 760177436 408362081 607317450 891672278 486096000 553715564 420943157 122257767 148082901 452310926 343918365 243282086 743756512 605499138 536973918 176555454 930519201 939344940 751282100 450685590 88325643 820758593 903659159 675834812 914182399 436847587 187592123 869136494 599742655 387759430 962724629 744048684 393076034 970556014 984469435 264170206 466671494 928388841 28093798 768368065 986017101 202320287 213800006 345657691 23497060 139879748 405273398 646427964 198949914 951701977 152415606 194207087 500051093 496398937 397642145 419546877 891852170 979141662 977636747 796761732 692506595 923756287 347779222 507748334 199608073 152908549 531475027 147195297 119389716 901506236 114699566 954962620 953787463 694758331 101173248 543828635 130727139 395696703 708927975 390226056 524826152 994281380 417230480 911283223 415048763 318710756 804878413 403864611 169718278 208289956 382966689 760355863 192176518 155560913 87557050 945538520 9448794 643115207 222397752 901865933 409218112 774251201 375462336 941138644 881421572 561954926 349131276 343300428 419166342 761353515 192017951 690167384 358505157 34020677 590676370 417798321 734294031 267821458 866485904 53000943 823044646 895208222 390061097 468289786 596213540 918286114 129820427 397404486 458151884 504838972 472803571 648455044 438429011 12881904 218027808 49892580 949314340 828973696 339475377 889399309 768989882 410201047 4738208 209302325 578101528 400715823 240363726 26556345 529363569 754993687 149971390 555565754 778743558 228193987 924605740 363447085 565067056 305247622 810447872 350497902 714892949 946834502 487161559 321097667 78388651 213818928 746529159 400874415 623877017 19601935 236233170 906499667 739677873 757071062 278583927 191573193 359923839 881832178 451331897 123571046 680050896 210410698 288711079 494687561 486281483 337965505 913454186 426864776 30008403 3925507 533758037 300459481 916883023 804493154 629316294 517231717 900472864 37734623 964487120 675515682 841385015 847729874 364890407 762797722 990219059 31719981 892624229 108095241 922699615 518061320 104004374 464876324 222545685 3800451 73062454 985260206 650005821 856673626 329524156 876995604 155935220 360510710 450449467 178119162 478111606 467879076 421565499 887103078 332173681 540762516 984915094 39854810 537547005 501583216 327465937 537944265 631759870 242629929 512821322 759572326 7078571 30337902 241628499 10077008 265334493 308876568 836434492 791391911 835885004 377908704 372849865 860333587 985961412 236302330 582829987 161888937 492096074 384030157 159159666 182162213 819170368 823294017 344909953 491133324 324018577 141546322 370783156 950092376 488784653 422614336 246325295 198271566 326475054 339400578 271240733 469070298 807793154 271570276 833764973 48582775 572442099 887242865 128444188 933074533 210858057 454472870 134338332 742388551 585464721 511165212 785611481 593167509 15586982 639107723 975574330 812767150 708243666 998030018 409671628 529788313 153903601 782582471 576191543 290905893 165792073 416869490 349159024 420490415 100001226 405170940 148619391 791675238 542729475 332038340 341507075 691832842 794622909 664915102 387979889 444792848 579769910 251894191 295743413 699450104 912966015 371028851 829148085 879034309 18903640 489838155 840904668 354953660 573929079 739069100 869110679 531159079 548555267 770397779 759892947 915268684 497503147 308970428 304162800 541981396 443618957 789017323 136077648 121679822 625280548 159357457 33923332 185227367 315954143 938568257 861335381 229305831 832320556 262849038 721893921 643081012 524877498 311099085 404608804 351903540 237847529 806921168 199502873 318650377 303913298 690158561 132890309 685584542 792476631 582232738 390142729 118708137 100623745 951106587 984328043 351504068 750735191 917492469 761529154 898149327 803010068 403138335 805628335 760408946 282328251 136131982 426084169 374535433 256398122 567922368 549926140 532203239 512495927 907334639 142982167 505361822 988382333 918143807 361519912 612859912 148603432 752703316 183988764 754914448 703945949 225244660 673253253 353879551 527050323 539020101 960430434 497766084 203167443 138122526 264639119 538641254 387254362 889112406 615949240 85500475 578679723 732627630 637148787 824636183 478995436 675834851 298470646 107903871 376233393 319127909 540534178 883807134 254578278 99301129 850565022 259848955 297953791 979130570 311017587 931431803 517849955 994942347 98620997 902061276 174605428 695953637 938021130 595063090 587319513 492475839 709837279 29476063 715538531 90019137 89854497 463057046 334415631 73408770 539244630 807644581 231884273 507392461 91750811 538026936 613038864 776850429 518887516 218141901 234713743 789171505 807229613 310455299 553984387 581151657 990809957 769209921 973511367 469257526 178178587 55505981 853825048 426187464 529377255 963372322 244778235 72267075 277174004 383663714 635094995 690553594 890954788 900778461 114487668 266786952 170261186 864771893 239626085 92477410 119632263 262326697 661919659 203352752 649320341 445340231 312608185 963131347 633014688 133165328 45686905 395479392 616036922 892830069 255231885 838904598 240250020 237251985 968492240 737044628 117304538 711299609 476993145 421255717 503808484 188905717 813791701 662874160 941110229 842907597 474155029 194912423 629432799 380321049 730727138 553546430 826299860 323720094 503160832 873140993 648018595 77311270 799025265 242336353 851852104 252474160 604495867 996713170 853512710 261186022 843074579 676634128 160491495 945576566 903872226 951382829 809619162 806492897 88866180 696081585 874481811 260297313 727513563 242628350 109959515 238177443 464095192 409771981 681169636 320543040 777915165 720537750 999866685 712531466 798455133 48398624 524769 881549182 77767404 404245789 938792199 281082217 176010614 295184442 542595653 947246548 261945798 615210142 322385003 656434938 637902794 454969182 189929042 670331470 615479590 425655406 194510676 576687200 863542489 626750832 80808828 833622836 733715114 840370586 956991975 101467509 470441639 262222554 805453069 406794223 997915283 403969082 620518426 10677403 792094099 171715041 533826729 373807845 761450120 409143546 28573967 486132378 100556222 854723185 32506378 583859397 982670927 964384879 283566244 518155774 770761155 672448494 556507871 148324708 749053867 908834720 797929646 985560350 563577278 557340667 213192063 729660812 594413369 730787459 410155301 163402356 6865123 783439561 209734498 169219081 473343305 663412847 820915720 69780313 355758978 153244924 765490824 816124803 373127055 304531899 115751496 758960003 261594549 684725226 227682193 191783600 956359078 32512834 432196751 799610229 828298817 537207755 736810828 912901248 786508392 621069017 319996059 812985214 268491887 470780559 424994794 822254528 906562426 581419100 599691797 84655795 228602413 394469228 875645844 812060251 223133634 918829375 926918643 393465833 576710127 848439217 22061140 701904497 275342845 952918410 487827043 679240222 548343624 311292129 889169010 364111622 724345153 411569599 133610821 287903546 108833279 772624352 590697241 824267397 645289543 686814855 332063047 604704395 163591733 697167914 243633910 840570257 738382432 367874608 835990562 149181153 762385352 511058196 915354963 520409390 431780474 377424150 623760409 358285272 994935400 518950833 670359350 587584011 548023748 859471323 878244526 437865786 96292169 663479310 642487315 772138636 627234270 946993143 603487947 765361655 156340972 959500962 904984690 203686590 101453033 224514787 98350804 215551895 681339610 204676885 1074298 309672380 866699351 904653587 978431434 681011420 947580094 459932403 119639808 949352256 595328285 357928521 916102460 438682171 997839890 604627458 645338058 883230297 106148438 789019386 742648316 326346408 332229789 525713230 793839239 986031833 483103754 919740232 351904461 549309319 640008620 529344905 731626068 58697141 918910612 143567219 250065154 418231666 491732886 426295685 75607388 662202486 260441003 893207410 7420930 678296128 827079304 351373212 633759752 787407916 311572376 662457124 545178747 165703025 787171664 487105058 241885282 47075650 402834973 1095186 436388463 813948036 560655734 390581032 750264831 565516260 936339740 496525710 837234350 997659235 610119123 818851111 756387659 975252337 60145325 449123649 826868716 429742891 352627012 703730338 238948313 496083231 337967992 941843888 654323226 688248249 79473153 594469950 429502968 517721835 771975597 341036388 242230775 946794716 749473741 365301010 682965002 588631050 710332082 388633902 220808210 663669162 525551456 289133720 546544238 128692589 287597052 863465618 324644484 936450303 35158973 277602648 197075902 430192461 663079957 630915825 92594166 30650614 932027728 188601826 390827753 251028704 167401111 871764791 599335905 628274210 772170468 235536274 145419201 280231753 894796600 736411622 415365776 485351120 2010828 247530594 96378807 123745606 315055692 770652634 283459021 276206785 688933495 147900827 301047960 88419022 911390473 520475168 150681103 84925635 950995456 377274467 998093649 961539674 160805544 526160642 87115726 829263116 693785756 834489261 471322077 152460943 568689343 34880224 128220351 910768555 642194840 846758587 995084420 761089810 389095383 657554619 622346799 685867451 83712968 892047397 825519869 596963554 595023610 338233488 388569749 639454045 241948204 383886219 810085698 924466606 327262243 224976675 451869470 585442783 217477217 305470791 769478903 987897934 284582919 347312947 964948504 179605039 554896624 955287935 665574007 251437927 646050704 590293766 219569753 624462027 186338979 178577553 801858483 724721412 68631800 299345187 542148864 75522485 148634384 962298773 458544209 273766324 500766897 922214480 803958999 976305746 266119656 371131712 916672947 910088470 136609910 393215360 827346200 200373436 567385593 825464278 656506146 847029380 348524748 99677424 593600566 404717674 222195816 544722603 15912725 82830798 621000051 312907154 955050451 953638856 857303668 748040864 221236390 669988709 859411392 975819462 760610500 580415078 96091556 287988784 967428416 39704054 464434836 989215942 706765622 206789179 735819604 734408950 652939722 187840764 794467157 234836063 529573792 783439715 445493866 63911186 191611335 37293761 913770254 350798257 765435562 101332790 765537413 379286948 794850875 156139029 909229866 87212833 931659964 762150498 935853143 522261560 182494336 728715745 27481476 226420647 160730790 489431149 711596787 171481293 315332759 429044063 747255736 242649256 923315614 544678349 885033964 976271685 709623529 796182805 869436220 713037452 147667834 124358935 110661790 743283517 635209809 999714570 971747114 639863208 474958599 129815572 342026739 802962683 371929808 475790307 71748986 602421345 513389717 873165904 35999565 615865496 866069904 641578395 397971882 850030928 857745032 143679400 808784220 29060298 543911577 677566856 240440493 209472875 443354209 905890207 334855582 238579800 265371553 386277984 793522892 323542277 32981104 729905494 967212134 721068518 465149452 52057231 862670311 880745559 961477872 397970059 686433253 976963184 31504829 235420230 345103099 855681333 481469975 785921255 231213012 19365710 588727893 972154659 883674209 313428920 722860179 390296536 696257705 113557933 84709336 857393944 532961982 741502080 193132234 265628392 215503918 76931353 846745690 448067855 191034475 599610297 887444327 957112729 243500604 694169163 840712328 641717092 449900498 435891831 92948210 90864977 473911992 116748820 92590928 249905485 570878816 715726464 821631319 620084433 6175929 326585129 517653312 969190224 674124212 890663411 515433511 608975068 965917328 989538228 582531486 642585747 88802351 733600521 681992789 451374924 398907582 780340843 737031318 354333040 252044012 268836114 927442373 715287182 780658881 56250675 878092256 720599034 688894878 665255944 625226580 794089983 842415842 828177079 441747808 451362890 262801987 88194310 929063217 981331351 975448236 781868373 777083298 233240463 933113694 618621292 590247067 677338498 718519371 663996560 852180773 15727835 823990587 724698195 388586052 195388371 396666882 236665262 873874263 577979771 197268886 526055233 633536705 731560535 898117066 135031775 855369515 187429574 304234098 21945625 713916692 25501672 919792584 76372630 464574425 710157714 743939829 931201597 547492596 355184129 872090981 396158973 525254675 54528705 381594067 84105292 376503017 580631134 716169497 851442595 667618791 760976440 780336724 73827697 355449071 281446903 595300165 87776084 934085098 445934088 588224238 36871063 212033316 127718829 51588301 455982266 397198648 750865811 706962656 664013733 766323795 583587053 210177015 377043164 459251355 314890981 306392986 87834088 538755720 224350562 390934427 490346857 466714042 888216626 104544421 856784909 359340874 740254528 979305141 813248019 634302709 807959310 401808611 639233298 893179198 585543415 755265753 446002200 159368395 2890355 610065041 823383620 690398701 316448670 591483426 993059219 826493314 826774382 773341698 581648753 930383648 628142471 627229517 34232349 745750698 574773261 113185270 520477967 780617589 852498875 578754446 239671745 580893379 32009773 153582566 345655022 549815886 266586018 972228514 706595438 961752571 555444084 916172690 609760167 643260665 402542549 600503120 950860499 896694718 936148977 97730786 30128144 151709801 683438741 395797186 556873831 695152990 996402239 406346002 621043335 116423426 129336448 539042058 985849720 650247114 478040149 296040015 44513250 106049110 935420591 628574428 323676059 305725327 171241450 739408961 650223040 398019640 464088216 710193806 423491690 125093188 175994226 525048170 232147214 785368332 865468282 10834461 91901510 635651139 632600282 331704023 58659307 384287191 459973477 975372792 253550924 236618248 585746997 830586267 9624584 720079355 481532080 114083708 893476968 8899559 196498461 342816447 395860813 950168232 939755330 753539235 317270154 418272837 46306292 609095426 985570180 677774544 303070442 223023767 688964853 59297274 924380806 788078605 690885364 740614771 623165682 131052142 197599596 135814541 590412620 958845310 330315169 262153979 375860336 686721962 676561927 218559868 900033969 724915944 188781129 221875027 173506831 742464639 954185990 694873500 856808234 578042529 656864143 332062797 381224473 967859201 735253073 96844818 17021326 447811280 302315321 473931195 192915403 348722188 632878379 165128358 148848972 26222582 967578383 36689921 265148188 983431537 381362650 735319876 950642334 827768355 128496933 335877407 105476693 990471559 372952263 958497043 741658149 306314786 20321770 903817162 778283157 264359287 351612003 424744294 434605794 220350096 300921828 822287694 700669383 967132722 657354868 530741666 586886136 770472657 167390268 613513512 387261125 262861274 197708501 601527443 573940234 311614922 689687839 104216667 754540614 650213643 60984381 372872929 129064934 381217786 911527595 595105841 6422044 866775476 181366008 151030811 93670987 465795501 438375233 44530076 539741527 375992137 227083525 975390989 887382441 82664418 287525708 398581624 516827490 607391268 126168733 745979846 360056309 442663005 149136446 852489138 245791434 760842254 868681507 334458796 137136348 752706325 95879286 190316995 685823972 694654389 122251288 480479726 62615004 147579539 434526422 962927046 360805786 55525273 899884921 348753934 225236557 908496358 928988683 864501919 56080418 359370840 413218636 764900794 774036236 719775919 544951360 43627784 966513529 1356771 137651038 566771992 205056443 159019908 484944341 665942497 293077848 427167796 27283723 159048133 833653982 486504077 26059841 234310586 556182458 645872092 848273470 658125662 667681185 123233804 340884660 341886054 818567143 646435234 837023174 578482296 370824607 572539956 720456216 675161416 136789238 946270543 474074741 748900501 845726313 542049952 865405130 262439869 8162495 334477252 647144545 419488585 749316706 214723017 168826005 467939333 817103848 599418260 19906390 233204833 95220724 160625544 469643242 602640025 64165503 971378790 658956171 521529925 831434304 353235384 266723157 536992721 716796158 232388656 140263963 759560482 285640477 322178002 88064438 190770739 181134482 892400829 547305970 37896855 155982572 557945364 149669014 124852366 315161660 732190197 26413928 465984060 908277614 668165985 601614346 172852956 630291554 170272683 912090637 969680728 274390012 739932219 568251247 814439427 634336527 59433903 577672215 894533046 255327436 687969276 863328819 208332702 94951798 807091582 543889979 62442445 389870963 541736050 327783542 332874671 529352579 543406832 875155322 54958238 190987141 260943593 173542012 66514705 333987432 360831884 954354886 701973986 590480573 582625812 547376782 370327800 867798481 255256964 112709469 490509643 654858978 612172651 473757480 624433617 83136830 916185519 195643001 364913115 971648184 736149867 415403814 530884095 826793509 263139296 717012202 733721708 145247718 762355652 20728249 703297168 751744659 509602428 108823651 463715361 551706138 443330802 403286167 68656382 523607875 641086293 581344770 173503595 625941260 743581495 561576860 785372840 7910999 837752486 469136725 69017773 832557237 19080833 509466826 243885989 456952127 42469184 585167690 653954114 461167680 953250810 284687301 146799769 423290814 904564867 392824617 737477291 455373136 995119910 94289585 575024181 159792441 61617824 653063429 699177646 375693294 880541010 188354426 787704316 34773426 123609527 769838230 855848463 100201763 27639304 515044222 244247896 95041416 548758747 231694711 767068817 652376490 733817598 611541542 78438818 364588117 53449460 841330916 363954799 162511344 502190325 219796607 820209873 401786116 172423980 825429242 129751490 334891435 960068463 125108015 618617125 826457436 10511156 761294176 929470109 235787937 864845916 451375982 205823285 740182196 504265990 984722848 551138776 245359647 609902122 629506875 308249434 398001095 366197882 868223481 681845656 745564355 339447300 801508521 984290687 98218164 929789707 446681324 331023849 943098465 747781276 309049741 941860455 679903004 344203690 141686976 745947193 552922206 720711340 394198929 823186229 755784851 683018315 597635610 164475583 260363536 454951458 869893528 686856774 340286983 469531124 597172240 184284677 840660149 893326967 322132951 162635792 385034192 703811698 579891006 394527796 682925844 438336305 432712626 192138635 30830360 797774868 812522154 58780913 363659783 323684255 541209649 526549321 941003376 703868301 586819085 427787292 54548220 89926105 394990806 755587080 483322781 882558492 150200687 652488769 871611084 589717343 602374729 560186672 254633711 415019638 702517242 182028256 44721558 426623848 858653457 80142370 977523864 961764974 201611292 19561466 939645812 155310586 667691904 478866243 253252226 424381420 976238807 151089983 790718763 200426548 903398431 311087852 924942247 59440979 560367525 825421691 469759630 607729418 584059175 734107304 247447560 631268112 15664010 39413340 541397137 839148323 306657823 879310499 268342254 537765846 301185306 306121204 112852856 595474364 420957565 479018823 323945018 516486338 96211069 482789188 189169181 495817390 636796421 956322521 472255951 248087479 432114792 74691258 766870873 423233048 696130000 821919365 944214981 643338052 650027174 781645156 187067455 353419919 636928662 115430447 484204414 752602882 24503710 182865621 796074689 571511267 723917969 785402586 616975470 274212242 385710020 129526827 224652874 529085240 53479510 454650848 523344863 283728455 409087561 361480040 425482178 300567844 536010215 437161194 728009267 134049874 146893063 846227704 631854495 586856984 972434918 589961171 905960484 400124787 456373858 77178678 178051188 303817944 972099853 66980181 629936548 425571138 499141206 347556365 62167547 961060479 494754982 212310583 489658798 171973193 915563566 592790902 87720589 26875418 19991210 306817543 726051744 421432555 245746258 139504574 898233736 543254792 479032000 385347949 957844936 401109725 679526472 904908014 406015027 310757788 976312546 645075944 91178989 330287054 32265227 666013358 546890021 342876595 793046656 528495472 714308038 125265510 411295341 725403185 610034830 821978512 707474511 248362613 19874165 238800988 896036430 714191422 887383585 135865888 813825413 136584879 890711816 725322650 16422418 711868295 79149272 49609784 289020811 528964129 108510888 667734735 49694326 650085117 325925358 744383047 998501779 37483907 940935524 403981643 85317198 424953146 910188823 820295628 941382930 887629834 819919896 623440089 582067528 950484651 766017632 854353332 418300456 148172403 411722862 10750237 927833852 936667402 24372591 520733452 651755001 643813240 860183480 297091910 461164913 78650481 588208453 224235006 975720884 55806524 466824730 992225265 217159249 626646623 867054978 282480315 229353476 965898651 693071892 595538599 578799974 415060572 610533697 715669973 351082443 563512880 916286039 410748451 772038925 896490267 501593452 17533970 804207702 947670057 656827367 897325243 951255208 306918567 428583183 597316195 768491467 386737592 869300722 22238385 97946401 315309714 418893940 405671036 893482149 349968562 177553424 732109792 107305700 121400575 737837279 605038675 72161464 73303019 829400368 306995916 61490017 310670230 353222250 461255045 997324385 80151543 913838913 902996874 681362059 215275781 592912283 970150124 954831169 24965804 438593460 882573761 881335700 859639547 234180820 685765045 174758813 603503705 552684665 534099851 506415226 588431654 894565305 178435602 862487387 939348270 687565262 791069465 232440059 544391658 706372556 146023402 610504667 987773419 1858671 330694162 389620604 207629477 517833284 910469505 569324980 728203993 414014886 809881990 881139719 176533519 574086629 22534872 294443716 245355066 550063716 624001336 203865215 504913829 974131067 897189006 864974224 545340841 64758353 108602205 110500018 64630982 727621206 587713773 753338500 558551863 833008752 790160275 441402125 369825299 336998302 352119516 754288128 751983331 973890817 345156124 896969652 785210705 355730923 405569784 229023098 783865748 691033455 918222746 139868735 575399816 802766905 251227123 849466380 871931678 817122221 535868535 849611068 104911951 938691784 870714852 523022725 16518815 351763118 930812597 3369369 547944993 87798269 571238024 562386449 886670685 325683810 391925969 226637664 523453244 291022107 780810971 667512794 281224078 507963195 326200029 246798480 666468533 982421663 161996312 271452254 7975500 272310509 671769492 912356010 479870408 793944468 519908706 988502143 445468265 625370945 900393050 577690058 364710023 308907496 6441524 984966434 492286061 855272130 47007269 108629378 352584257 398221516 357006230 706091239 986943116 291370161 268874315 377484456 961179233 314499590 277419942 740751896 631114524 828293530 91833410 951862938 101151387 569944318 291130822 977027785 975478654 126406081 779478995 968105025 515779107 845583009 578434061 425488250 339223455 581511360 363858134 778586128 940098745 851282763 81145789 152022334 983375602 754683707 731361002 668826622 863710970 311380928 230641259 642507368 98040351 843696238 298672772 780657083 824007764 579940055 531240918 382781910 520773232 657116036 366984375 962202883 294790352 584800250 851451955 613239438 461633519 555048767 178333881 839209101 624958025 254384733 927175518 516640422 636211156 646434780 285622674 979395550 637302778 196333107 714856774 486276773 776011230 98408973 880603512 594945358 40447608 867762872 50364 349492007 150421363 619980519 337559719 153712471 55075535 344687904 198951268 875616538 449402450 936258235 479362740 948630256 196483798 109371173 732284351 21694299 386295260 960714433 593676951 371912228 304926401 469628299 586518830 607425492 304595560 297337004 595554169 214451429 278048540 437775653 929732434 886380432 454147514 279380781 704796482 144258099 887104064 644330573 208673143 997510961 674712378 813164811 824367178 466858882 360862618 532858272 818157256 695894416 77218027 814171586 560364718 288182136 813476879 790006995 423327108 44974913 600795529 940871482 148997173 235566367 559997788 232983257 103633403 373412516 765294299 537191119 573200890 291716310 561136114 294365214 743792647 230470404 38261989 210812663 759031936 451339873 150707319 454485171 253363136 310268433 646624241 553675245 317496790 509106321 379978333 955645146 85202454 744857116 857358278 176169851 919478906 350208816 327474574 984864384 596791606 872820855 677300491 809756561 423147903 418851577 875419094 603573889 107590644 181175626 585341740 921065160 722711167 463889968 669522780 515686615 697283993 525755792 44455519 67121009 630025398 508149338 224782543 452522873 354058603 135131506 217417083 324311838 123429081 970130968 181516609 580445963 582434686 877614598 950958312 912291735 604341472 616934887 361256019 237667275 134753136 233357152 812397998 882807127 72181294 576322446 9302711 475744023 234202383 863758192 800794761 744435915 345103756 647286261 54232167 825117330 653579823 562222679 855687428 268807501 554611690 867002621 929171316 438677350 602469768 280399125 944722508 639503654 80696069 703868636 92091311 532174384 724921712 415315408 367246653 677392302 855610721 16958883 654286703 59698929 879493892 688182899 17057282 524937896 235836702 709569550 916392409 671148750 795971625 176298161 453098480 699434970 530440613 746325802 549344222 4380936 171275702 805960360 23834253 276789739 870920651 8940415 260952068 782404326 831839370 689422387 42462406 409332878 897747576 817046753 539873965 437204578 835345962 665286819 407289465 841271399 42444208 745182592 345285572 689826630 823703211 130757999 394242810 225443568 367239806 978498619 785416288 736052859 129467703 261808708 800564230 604222821 879475612 509370127 517856571 14691980 467832070 252396769 857431032 139615388 172093614 761712256 95901878 310686866 803744208 158205357 412355510 687295732 101607235 503320173 888548818 710360222 632913070 6970564 524575258 422652759 266377541 556235647 397411491 506258548 196348807 834788590 596459035 192811402 173384131 299874610 102002522 199627508 195091572 952301264 21155239 590357968 37860210 451267197 956587898 34167580 80123502 422116420 856254660 768859614 544106733 895907569 645730918 794891627 114253859 235211043 934644156 295810782 210573956 279816341 848969921 427573627 185214023 980568032 86581255 934455788 477205136 530608545 587040507 674441625 989696198 166732093 214077673 546776359 269752144 682348199 952178950 312603623 218055121 901745854 291723989 931891824 954312883 552561870 20912512 950262216 634257900 895930223 208807792 301812401 472022180 486461234 758460047 412405299 506768525 581524175 961339558 158651625 727544068 758131679 634687100 942745276 322168712 290074177 580168238 983247349 354283595 807900713 954068633 588760591 358469311 365545323 867982562 610445322 502324246 12251364 244109976 367866981 987659632 191549637 552238257 946267634 751892023 142925279 206530798 546081849 44725877 802625481 189825296 525854152 442091471 728780958 696243792 537889708 174250009 221955153 236098269 880267689 674219193 872422561 919894985 12923744 452591219 299676768 102987737 738860088 326004932 702833297 483684931 382609536 431663651 318486062 128674458 175904731 289121460 609727567 902722455 771719502 180287636 689105414 827046121 767006819 979491724 302836983 447170654 162877258 970323714 675039535 728535 100867318 428815090 940655824 918801612 539013257 267950762 600371573 881131064 994264589 451259031 744884268 752515541 458112422 981565955 72888611 934749864 922253101 269331569 813193963 945519414 988106733 344317123 259649905 773586544 103870283 599195342 559817051 301044655 343490529 566800926 297190259 325844577 244936042 641692052 337179155 3818285 146508300 210626300 473171753 247771570 396698226 338527033 759427857 669000657 785240245 617663565 21436123 884037464 84133971 427249622 570461893 980203822 475086950 871750110 682930941 125406440 997628948 857437166 164491545 932414845 482750020 431585371 591373071 672578295 458914619 860127604 636841038 63103168 293490457 227673573 53078603 922944833 947499553 912659632 758345365 461099769 982836036 246843767 467695368 836844026 440788153 536573602 185574246 974342650 492566037 816893344 689462289 949945908 51074670 62944569 74181192 741146126 442146614 128538921 404512813 237920985 527635765 591066890 14993447 924782674 649972263 300209790 634683636 511686047 281162904 231163701 835916064 872277674 108250207 95903047 530753784 888130990 114919461 968417973 590686181 233159695 806582106 912810701 125291816 185249955 970262868 30247902 762905962 258035512 176695095 354583687 362228393 687492052 88491116 592856144 447780705 620394338 263179485 588340651 996866030 311970907 367581729 420751314 451647632 706771506 77103290 358041712 118429556 995539199 157927157 19268779 529725552 112777945 855484790 613118239 260948181 433306179 235325696 977241722 665854198 788776998 555888962 444587274 579841595 144586727 101229963 963527926 70561875 66729426 730705726 791737393 572703396 399899494 251108003 77826508 597384138 501982263 593008527 385728709 22053970 774677562 530291845 404177935 619980153 391731921 822946666 529438219 743112214 752931791 84742437 685289719 258503365 697556275 615640283 389761368 733087981 344519469 358909254 100281186 89537235 12416807 848234087 441007731 904718887 738614066 666276222 939330766 16642919 701031397 568865555 30121907 890667306 189060507 779332168 513077703 480611373 609055723 120127132 866047337 204226115 583619960 323360417 939805767 534260719 604506880 575314127 492634186 100479991 77515947 267671165 196354856 600811861 851783611 130391728 798049854 771107422 377314678 812577966 990490112 308566733 363299046 760992053 847672417 154927350 855331827 573274353 812662041 734268352 598652523 930273510 427616391 81241373 868029571 211438657 93938029 853767060 34845985 204333820 295992096 29255664 613252345 831204911 630393273 785597999 162200658 461569923 228883034 913057586 83207978 965026685 48051155 107947467 984855500 740740371 383578251 130742309 349872500 913296998 938590311 109336412 892510852 370053150 984422661 559259803 361993382 253269168 507982214 753616789 644234936 651260505 166461661 41957423 264677250 264661654 273072376 194702204 432450133 444823520 866475857 392825306 468489123 94666473 922437133 888281451 226814138 83272353 741741064 868669143 763491181 331554676 503622567 274277460 442657962 865817434 847131701 585178556 293926626 993748276 483777434 640403460 283422244 706988681 230538030 372276809 101958093 958274145 438314255 252250224 749979869 851869076 277747754 96820030 528748668 184907499 213839371 766449076 799029320 972071551 535690151 599356838 331394444 662745052 727788079 821802941 487572228 721946927 636226058 75479905 92740621 756950896 891533748 994974637 956894686 955201826 177214444 488389225 392266683 117079884 133183748 849781564 604268931 205951239 839033845 14850867 128292713 662050077 846250684 455619153 522598736 522449454 452075480 204377857 730580552 434248066 327495200 719830990 646578556 125701220 893123376 162258779 563340237 107326977 155155082 248010585 934986704 210054637 286216237 13454001 338700435 974204045 349194267 666356676 91788531 658307201 260712019 112362013 623718924 431497342 408898325 761207984 881288454 167750405 896332248 967218856 831025775 307467819 534948721 467195642 293917739 687884104 245165988 457968280 395352300 186604181 865559606 308078149 668990977 885529479 917403980 804955560 74693322 477563119 274869733 554459659 320730698 640992227 608331165 27558494 773845775 473334007 323869959 77966259 158435340 397341661 416420132 983177214 696609848 801598761 325540445 95704324 653610302 377252857 531047179 572515625 679876297 314241152 526580571 788109442 823663961 706769469 539053607 239468935 608248343 812011156 154257215 357915111 974323223 283422965 824530059 200600723 744941395 905523561 390848235 784840202 893014223 560595256 466766466 934521940 427457604 557267901 64454140 761009711 582473141 552396260 783912479 6318347 25137332 508253009 368583487 646656493 798713705 978840223 521365222 330511925 90850649 178323405 528425624 378019114 512104293 840078318 887696592 162628213 356072674 111718869 153969329 570667461 368941393 118551259 889164820 628707731 80904322 721840057 931123975 493016113 240164431 90453791 916414298 454744386 615340519 231297322 394198265 105421266 449159468 877946323 100799224 496850571 110651976 631142665 443765633 537395090 457541921 976683097 591430350 912210120 502201749 748214309 136662331 686492597 783458515 809829982 548717796 526206017 956663316 580118986 981473870 616115272 253532060 322683635 929442788 685085543 485530706 381339974 63065213 265682206 677498736 167191156 193389529 648308677 77346583 715612575 177440789 225536590 37046285 677964963 546793844 249226597 754723275 728166727 863947273 645625555 442438852 672180575 73872989 556942148 290713661 571491156 811329390 643610740 87752163 463413418 156632452 698681884 125709563 963921227 681453370 441909355 602328774 324794332 263081215 212542704 476465138 92744350 680310203 274062004 238931497 79844618 473709541 630641508 774953921 765250348 174064709 433186962 650484517 847086446 535982537 531209659 290145029 372118330 244679929 610923095 203605845 307522997 219802316 6421199 186753746 101343254 831641909 375691975 895670294 317037970 117937786 127037874 764508926 449417555 492842264 45176532 759877238 749957433 313034265 591927228 177831252 18463544 194331814 906005243 742212313 579974843 312206243 810898670 726402451 170618059 764167340 910961355 946411307 582497851 79460946 186581044 289384484 63825247 163613993 388393553 96894505 9709142 992174583 609233177 992549837 905187772 911805058 146887246 767934304 973470559 114715118 547590508 810230706 608783867 883465508 16749417 984931213 238826265 471770722 815815238 379741471 883222309 926892355 166553310 898582553 422778740 419036764 409970516 985051531 447850729 62499649 854574676 593104295 905847354 323629097 425874350 492693419 423316646 453293544 694469746 135748167 773937964 869981143 980336647 893227015 249357219 949976335 174376580 838107347 941938503 587270036 545338698 345099135 304154217 369790428 300098911 139421504 61987953 938141022 760856815 833658318 770952943 856936606 942360452 842431436 934372688 975850719 119802867 218629590 841686758 797863002 121428656 409663571 192979050 211948323 590712587 69128396 783713406 154241903 346540906 471517227 676556695 962919008 910125875 520475056 864472144 844121234 898055469 644452786 825010111 154312583 706437699 917042799 274559772 133776413 543232479 617237036 86813602 770550292 156283945 921952253 741911808 264235631 625371708 893673215 937141545 105235544 391184926 599057169 967439874 386622329 512274508 886172980 555697338 398941690 189977637 967007183 303730614 48993218 104647824 161635568 571900195 9850528 45441724 115277484 122609131 497667856 780725072 869569426 739957870 307808886 793072580 551147584 348706572 181720532 408533388 666222408 668372907 616425118 736060589 979730396 235188777 461799582 859861172 249088526 205743700 521658824 352921617 76536452 246829368 232537408 220496658 376857271 201298005 575791542 318532044 404987860 35368136 260957682 572990486 17856873 440068448 541598825 844099615 643865972 756502745 874874864 384384225 68420866 360698384 154280138 111695543 249299876 545811906 364230960 783247641 812967561 650344649 727252230 874795039 152728587 67987767 975483638 800805469 448668157 193404489 686066682 329216234 480615226 122398668 744543164 223509326 160003017 342595707 80780634 405330266 924192235 782107629 802063950 368926455 560013802 550436289 894626708 220522765 588658694 174401396 32207442 900423962 710198438 924244481 52956003 969575917 699397504 232543166 807791913 355453658 211383227 884150970 679666451 552036307 964877875 37483807 550557119 185121312 361652109 181524658 428685204 646066342 198518410 286811538 885906473 871138362 998605228 889334857 669828724 684858652 5680609 324932351 907301621 219029565 823308163 165779615 679266769 824578935 800717418 403050365 749718618 200422329 477130627 142376114 142286791 827840438 148073467 301057667 617165662 351558840 866150858 773538317 10936822 407932102 45836932 384367842 860067787 359358384 93409179 335687056 362265441 194846351 796471866 656339811 955881769 644920226 926726020 567726075 578274628 210638218 524265190 490004934 91208703 462569385 229704418 971674225 544169514 200481274 729417884 397896118 839733773 773395129 421765056 23006759 460141854 299671229 826689432 90243874 305901642 874085343 433125427 44572307 825192405 446703167 109330885 493524639 767269885 630772140 366161460 929490093 83411443 385110180 281493728 719261626 103420148 275775181 16242118 877776119 352426243 424048957 782789699 66359662 31953960 105343579 870462617 924986490 435236380 665703522 434253768 260673010 412013823 38993759 964913578 70375721 9932334 572660878 188530530 951338949 378885840 220198854 189161865 45845443 353791778 497597354 195221413 862806294 179920175 222648135 301184996 179673022 983450682 913193653 35228295 84022711 663376680 428063244 635333464 68881471 483084725 790377162 98014890 322335280 375218240 538355445 519779007 9123778 465047820 553665082 747146658 700169890 78283165 246731628 320694349 405146885 788270733 825032565 953987081 74821104 721729439 432803609 539485707 38501586 682106244 509069248 646045857 817146306 880128600 939537197 693694668 805920509 105952004 636489864 661548585 741666783 932166717 524135776 380454559 253215868 955228720 237325366 106438311 51512667 152865194 40782211 782318236 937428625 974840325 484096852 820077168 53624247 741527800 473469278 945286996 284819750 164305154 297524554 476121985 989949533 207484104 869955029 664657962 281924784 637554198 772720739 366766453 774544603 337055480 762125914 901912767 251789661 397631856 652004770 25314850 85395134 728289547 231545697 622919725 378798967 432880666 398624164 900723501 739856737 509044207 440070752 459122992 54070871 484330724 655586832 868395258 147661490 173147739 779571293 522676202 610407864 801693617 814018951 169735835 477323694 737391071 795160630 470631849 955889148 363354649 797642800 979723656 122159756 232242965 576069157 848299487 53858992 329013926 208478903 888874920 191921065 906682005 979700006 20687715 104126779 728118366 298811896 502670150 39701214 746454285 639156039 484844326 644999298 373598689 578705541 842434021 82039505 207761885 148105017 325645260 175712077 236866878 745096576 900478522 522941871 700571805 646119015 900118813 304298797 533290005 149102603 627059349 367263665 784170642 478722397 187400751 203396498 765832555 243367001 333618885 103991680 654279269 50375922 287698110 868213069 135129953 82904089 405140196 779869302 463230939 10781910 684205288 900542035 735027156 613533491 533200613 805090080 772612098 822631109 429870614 786933947 674302869 808724511 526997332 401828988 626708770 38614648 381981819 127029870 77197854 195407738 40721804 905332112 590033531 604414384 15861037 699993962 96749035 216598735 544563995 615718048 490142667 733505603 13909695 812085224 907788842 678420802 668323618 227162732 84401887 72736137 95384955 682293866 836563468 969906955 770007562 530568234 860136115 927909687 644255126 390318204 572696954 544130907 391211400 673638918 454231010 227332979 604706215 9518637 980850548 134385501 163384477 479574563 546051853 788746007 837627267 588651772 180033086 721592444 837883588 742243726 978346789 43509151 869551134 423859470 325901597 352662178 156284566 530373201 792847631 212402750 892047230 252218162 951932324 193393903 207556603 78286170 472954766 258557160 548081508 675944479 369059790 862835468 692806798 122104869 331163628 996091685 145326011 256431199 358652521 78563736 558169448 406405084 527367455 223683491 591536643 52164548 627748321 360383156 313168384 683150573 1589083 760892184 392979286 382060563 212165866 91856443 382501538 872758765 403658099 489515251 478066243 819378684 468032616 218683181 645307240 134451190 821373320 872318561 826603550 495782670 462826185 340764537 305931905 330789290 364408393 755635050 912370466 338441523 390357617 145463982 129740299 494967697 398228602 601579018 502742603 110427125 353751217 507048508 587180889 897357902 276391057 11885800 698655279 373422957 595381836 217163178 628914193 839972130 350041869 221502980 645443060 394063056 225583160 867600101 315904946 932278926 319928972 887003761 63431580 715119072 405174494 430814518 982609823 503339423 742854253 31275029 579364910 11231961 544581429 896670300 307204567 591051484 807464095 131354050 330071717 164111229 980122660 15354909 490608080 856443220 113496281 381138436 116114433 159139310 737162695 886800067 998974601 806483409 423768964 220510294 960103004 125666405 691629847 257766896 415345855 615237727 834921383 80819617 443131186 889988629 131434321 407306353 1403661 962424627 691169501 75492013 462302861 235934252 727542351 882689521 835903939 337913386 717413260 156695096 371902768 329581026 424130931 942648315 340356662 4596076 484260469 360452386 899863160 276182956 947099544 798910926 473530806 318740233 427007087 886472590 178747374 552797081 655293344 352514320 323208744 325881785 694573188 341783878 940821274 791585695 967504008 390479670 675688679 911615476 138764929 859727394 190238300 87693053 681462649 229653014 975354919 144252386 357350551 196014220 31112410 198983672 618453777 227512601 24528112 401969584 567764064 789971460 226403582 102855639 38300805 832368989 574220655 547280278 122278701 14772795 148167138 265694241 392897126 76234382 189169252 868012900 828205647 372426978 575209893 536247494 73661244 862032903 173574566 976524556 294226528 326933088 496075481 589745701 53106965 559712944 350449248 476911206 562753885 399403132 964223614 978760603 283399440 978373739 538460769 882294949 881432591 713992994 959458719 132728152 186981075 322745205 319055999 853347015 406270163 166593726 89032591 178223561 85307497 284968061 57399699 726880829 933098556 273899855 198343358 729907638 199822289 518474609 308393459 228663268 936688078 436747260 41875712 927972862 379157772 212257289 945404166 668330828 908252225 457083264 971780764 285703115 371706565 570181821 567048294 431504949 814090558 700867259 711036718 177164288 141532044 362439582 246434175 2292647 603581239 6085689 403259217 366702739 456898414 74418437 210430722 112927307 260130132 793574334 636560988 21587493 933273229 938435471 749084126 858723365 841619308 192689716 480508168 487962670 617253476 282079179 437262865 386444563 641892817 441458198 389308277 479178493 911721132 735653225 698971399 805575530 371769888 932341984 166888131 821789223 325127161 157736341 812505795 364966587 691065766 644356991 319609255 450119135 708566885 432139840 234509469 831269811 738039063 396050784 429475902 858351559 186996197 299301323 800792074 1301476 622620954 713706400 690224654 257998153 446779819 222782504 595242368 256522578 969895434 843974512 646298519 396217748 350385710 735231685 154408434 207650006 581964017 819050982 902493473 737758714 210527946 430332541 197652868 271689554 957883770 29449644 959338613 572279590 964730405 456081524 697441417 360495132 209790553 705276196 866941777 992234625 89542278 554326138 576035468 410230068 875309231 195065018 362297181 873775972 531254183 19003638 935982274 250514150 887328861 223705529 740256800 696474601 297667232 306375517 258705746 80758923 564799740 894004754 456096628 197956543 457797545 77402431 995873118 711882672 33545558 515227526 64228149 458913860 685116258 626867065 748159981 229021034 142052605 817435592 797123936 465941882 43730602 991794276 200535339 732200497 193263905 980298460 181266419 754033437 910984426 495505535 217522548 647329682 875473910 64361090 111210037 280196215 959507135 874217855 209508265 885789802 227596062 531256154 27055066 574268284 66436102 163954975 59218950 639074769 706354813 128110555 948149978 908217140 632383125 700601448 100077560 530220108 828421849 493605103 930955308 392014939 82685301 771005370 237694405 952271891 589188430 939637064 116385587 575096573 707120349 476374028 318841454 513143707 59947215 957492336 449316176 254049265 362129134 245053377 860061016 801682807 474066145 288966106 426433066 146670253 941987895 878224591 884323738 957905042 550115122 784601637 56209442 666693433 770136839 95255299 536590827 74519768 726178284 650364026 107125996 762239169 711608946 856692588 210377331 717232338 39661718 300772774 602864720 7054434 795065030 184941831 163693384 397540306 304307633 960730708 174092865 22516327 405839597 876354701 665926998 883012574 959255222 841465299 294181263 300566511 106099203 79527724 123040339 320134232 104812825 820951440 320241363 379821174 253763816 28887809 227672268 355941913 742036804 663321451 584755242 588582492 527855869 453490033 534823636 398289714 648719102 285508053 780942472 192068388 980780466 110031420 939926377 240733364 594938996 283423620 996049678 353977001 812410514 375708497 551783292 520277682 723071673 764564406 519203210 631242287 542175021 338696582 426893964 798994108 581349118 784623989 619864658 787615967 56565607 683270276 559212490 915428172 845259392 99163369 634818549 213954969 671857642 903047817 578798608 927414964 864653174 477098690 764937511 279794969 288111132 508851995 153952056 581281241 875284710 638564134 202696135 136767559 863131661 362632976 133402093 6231072 657526731 158375763 886820879 398131872 499671745 820870732 848161652 237872290 43583477 49881304 999789362 986384379 787361287 977028257 513497954 558179917 890210690 158417225 74361110 443644770 794160948 520960911 952177800 559781064 244565299 921551543 26542087 192704031 236880216 786831392 429199718 870173044 540712509 604798578 912545704 534399294 929300765 725015842 872784080 586184436 343315968 529773471 430568908 634128133 39120033 30731305 503604423 170568354 179171694 207022549 15844573 477144823 391299641 380376275 30962307 186670078 155865617 238577277 324246590 844854324 552943697 173465671 554673758 94797371 439533786 3736051 339788146 579110163 44322465 194350882 326535920 876186859 893545312 382408577 816568789 447136324 457040000 958789175 784861365 32100346 453109272 497964871 513568021 722994489 32810699 896776388 6690580 649347328 177888336 515887696 979499469 50992435 659881807 425681101 79871222 516370610 783620399 31169925 421783366 778530773 804888004 393485957 810043805 838942337 589865633 633797466 900731557 523015970 643194132 914403239 134900152 978118347 200622407 557543317 12189379 602159875 813007977 689431318 829529279 701682847 27568242 407589768 618935744 558206457 141050997 703233420 442317856 819010199 157615776 367165866 68525329 283427826 235114092 723987386 336232983 754600402 271854053 599650568 352031777 149521533 491506709 929301850 445287769 298064545 466393101 146290934 465554974 461327911 333206585 996696839 484812027 311531753 672923012 908603184 233634329 904970018 705740677 996641479 542627857 148155708 576382337 840980672 829429226 168166232 433930822 664202714 393796899 94187617 564362233 906373317 744038226 154706982 324174264 563590132 39747470 413671102 415555314 763314457 7121428 816242579 787949029 448077408 57846938 422456385 537141321 143077808 825818648 27147174 948058885 546385155 906390100 318202444 981554837 451153884 669366820 691362648 554166396 921305804 70512860 540660895 128946967 70739847 501663770 715636363 16931434 696229018 378621919 489719406 356384610 444332625 679513045 561027029 392933346 435359617 996606315 661478296 197939356 358076389 457602731 787133173 24569119 115978001 279083381 171624577 611041503 96102479 429646386 68471895 597835929 772854364 876246601 329207991 380668342 116584956 697242988 738833368 785523382 522747287 432120707 736587547 166517450 743151946 862107422 108497850 884101643 71888995 788161557 496477513 799148589 32647529 468428800 427212497 241500457 198833567 739329102 600709492 466339005 79263506 751530359 698972640 316423691 569978660 198400341 975290714 72980935 987134877 864259806 194087801 105308351 82179088 739810329 148458131 496660864 372257888 961891168 370180051 631872403 904469548 257257678 770772760 973686856 718872547 708314435 588264361 572608318 540229277 260896012 795420540 636177377 190924187 887594238 181536433 173638720 694029841 951868834 518103336 417740748 560070062 474669567 935847236 673381630 927550245 608658415 320253843 239235660 985726493 627229958 915058739 314375831 605501119 185564730 317067509 147544398 461306465 891819701 882603553 930485601 234101862 372737807 185372016 435246110 894911549 759948780 598804659 690693934 557012386 73608672 715556159 485005891 19547775 276116642 593108723 237531480 829840684 55010243 724691991 58522521 346688592 928087825 609644735 864773325 11291618 866004898 599590172 263698647 99329184 313777755 357951050 875159463 234011253 820608836 889595665 659498358 562680260 216545635 725127825 759752573 750643723 997780273 789642889 779006327 668952893 76436767 581517162 480219089 654703700 513592407 91188038 858694791 398820323 620407385 462066132 344598844 947508434 841569449 316083439 728075916 193211242 412038896 951221365 200981227 460294051 711309027 488269703 901977880 630269360 505855250 886935088 993075576 146731990 698717823 227855348 689028726 673228050 605832325 193478929 238747751 676270850 448440742 102619843 872864019 126741482 764442123 55428794 707312303 94812051 546370479 860121323 138175460 246008905 880854768 683987933 957497427 792233446 435727469 218099710 626689955 458297881 590007146 958848681 998424606 370388180 389532910 73121739 131292052 99603885 108197517 466246409 210650539 646596608 633349356 254960001 767692881 370004021 275868217 908586706 676023961 666659283 925456690 833059800 974583341 927581713 177865377 194706248 242849812 115379723 804607275 226748450 403738548 841807302 634151606 696047665 213997226 660232758 781126801 730046141 763301417 420092994 905457526 101116799 380154923 746651302 123377582 85522928 241372615 638646766 45590477 418885191 670720302 905802509 671599186 352757977 291559183 840726281 514263413 156358393 826193636 143472589 201332270 679858061 644843396 673987109 438090573 111591651 213819382 884612367 827857409 730094342 630106633 125570489 544756312 370675964 83031469 765787343 200198918 333192482 688241981 928266251 217995644 477805795 41359191 737592988 90811933 402245234 806526757 635100634 360256490 559960314 698714865 473975851 609025468 255398333 149811211 671373232 937069098 420580100 800046624 538095772 235043623 693687178 849674143 48592920 568558167 563765712 999296912 781336693 743070948 284384467 633415547 279069799 143531765 666538755 440684081 315499764 394623872 687040618 378153523 16409928 706915332 407815166 709284997 569596955 859144147 364564403 18480224 26426296 56448020 739492418 9426424 908853627 392393004 342020000 859006171 896509420 585934807 299576762 968894130 61461249 425633068 122223495 599935159 726237743 66543676 773812775 687346700 459237555 186005217 263371800 632637406 404267086 786197220 251445167 935795285 137278915 409900288 411433309 834740546 432423220 755580621 783194910 187160563 154987350 607686507 873352366 76659972 38812570 613015221 982838091 678358825 258244200 832129713 324019128 391555728 526679522 149569811 433044563 433125188 243042406 460522871 392431741 600890588 722593185 417883911 113138473 533660825 910832413 423803575 164711805 334377750 292459241 235460535 729966006 429548067 509089802 366122066 121021975 145314901 351853903 132919885 627186836 197762110 345660164 184704127 761460609 353168642 551145647 500442092 955133861 137896804 40979484 461628548 919491084 767381348 120324432 504743322 804658272 636304545 885970977 239986213 443857219 131928023 896352288 438993571 196602402 475310401 654348883 775102003 886560673 327664827 674734678 946531203 752551690 755806318 401738375 363176392 884935648 90205174 866292956 945827587 729290032 872076441 766171776 552769116 335811292 937432696 716179931 589666159 66036401 780398174 488228649 913898968 888685734 823068384 789193829 606715724 161041797 560629065 928122274 784371099 4763254 86531203 251624724 798290780 919593890 364943541 758643212 968030637 140658834 343004526 355887114 814426371 947531953 86193618 380091255 917801558 476771250 630725854 426306530 47263905 267467175 953175276 381328067 567079586 729296727 11877413 539647368 414749368 844523647 315825052 463746357 538347784 63187994 73114594 28895404 134241967 387164300 24367169 190937480 203510279 774000018 314825770 723009910 111720809 594592768 472871564 716612963 226751007 705974752 500068019 210929735 970666350 779710131 531583812 80934974 526772045 665002368 599863517 925218855 934044314 594797847 64599393 996934379 918697341 308747347 790576825 304443034 182352683 314238390 627418095 687465908 163592841 756644875 489364524 64624904 632241044 477639845 144185954 17058112 410563625 791154056 536838705 182008833 740024640 24225729 306944997 670364757 959511261 121405985 237591610 830685924 420124664 191086705 699426873 396571583 521610203 800249597 902676824 392590504 224557092 452235260 604896437 454647482 830816943 336524923 49985538 699405235 562574348 455632984 52167603 947936981 972667585 864299723 434101788 799925217 765145358 508081396 227893443 529998187 663806843 853394388 48514229 941677108 551271008 77872774 897804853 47099264 604082323 88082425 459412961 885033309 518740001 224396846 333556387 357067294 902800332 658677110 359172967 450622086 64673324 174439950 194245383 848171587 102595761 862311359 329991488 473921548 429819184 146778523 182599049 678291541 767684492 540262367 724752339 83691119 562437702 124979857 930434683 95776595 222098340 485737125 954999302 411372361 340834552 368144603 699518945 168006783 171305053 139803949 847323577 56425224 817522148 64417913 403908413 315702772 987123912 454862913 904323105 364729621 725490605 304218895 229501460 922255987 781784428 862241063 348727244 289864777 688435452 719906914 148961156 449284033 194938289 498706692 637490270 406469169 58439680 752466265 579029103 657700126 736859069 299868539 508781346 906654946 726882651 79923141 845547756 168691551 814372216 746595971 133980862 201084773 839542796 396775806 342761476 21078844 390109935 139056118 301341733 43751263 984095518 282793474 769703438 655882807 187612317 787023881 248493931 931457354 394888360 964243719 246707671 202847110 907868352 831225262 388803935 759389590 399041077 231760055 532311043 657947784 208592212 236274008 120981823 245905258 329124151 103295291 89310410 790840145 276287550 793842361 566810480 545701324 816203351 726738582 961321089 991846707 839674991 642488326 694708827 922168525 168396214 706980255 95721572 739425900 185439424 207661175 958272500 62777716 176760003 913614458 697101411 19234861 22351905 654034432 881023 758744877 133043105 155811620 202181089 412911914 720859601 154908239 739926166 652222210 580102834 214672512 923624387 627158236 443139805 143048633 492972246 482910335 56817317 10259477 219415437 57229313 381937596 248095423 465837062 269097144 523720788 755062793 39614715 855038785 182310494 183073414 412439504 814437190 543719921 660403568 171346713 453857652 804452487 258952409 3909237 509085390 438103531 756386789 363530950 914409029 402077550 964356316 332340746 772564126 123037584 652004209 100564052 915124002 243885917 940009753 723081968 921971886 959716385 676281491 549017325 945102561 829557847 753347912 129837070 191249988 103729131 293830429 493372708 391166898 937705128 543388405 338263199 915936456 708069419 742150775 130328090 404191546 932998914 911629944 250643227 95186865 285314158 799613477 421998182 647200050 329167103 903447568 701795044 22757357 961704782 569264574 992650782 621265331 926967024 656001441 747228751 473855657 756926081 195941496 987972513 782530034 740108136 548280968 115981940 159392913 570683992 164920794 446261469 429017672 398615976 708124340 902170030 726702465 947300792 278847232 620149024 940859332 177581326 339625850 881658911 327844787 67349024 681329643 574261670 418593944 822467353 686470807 181874114 120952547 753805160 307888285 293976819 443904864 997413388 947241532 788773972 584476724 396579822 156119504 389927765 158854640 650223755 505603448 54917610 762433016 280506997 378363608 545203204 676885131 78675699 643036821 602566488 50897595 334236866 523864875 836402195 106121776 592732079 966490417 991154189 918806705 869979891 787645459 777331755 882195620 732352128 747368309 318420195 915923773 372361421 347212803 63652640 519622218 279453071 521895466 109511504 553836056 553966445 446214076 42350525 911090851 743622282 321851146 656691601 768239550 177353786 694818443 501899824 980368597 299427500 25305464 854688332 623682413 158195659 848938386 167978713 417729688 979228667 211329415 438070738 4730085 720559663 716033939 985471534 531257152 203353148 440523375 380960067 60972388 398180341 194559273 84805118 449669847 905829247 573807307 762191865 981611762 527612105 524075164 335327325 972055163 320173851 717895531 855745224 808724295 637665060 73193488 695365956 215331155 721869344 75744492 3579122 297586837 725372773 565665561 994821523 791177549 973810617 901000343 758879600 865976552 365891541 870976123 280984401 89987176 683731302 728699015 141344999 457491736 651236749 495833384 695670933 548058973 198881562 377182170 402797824 269544309 533681328 575464704 141460919 119289752 521947195 719570376 774906866 80012636 83128706 881808187 803206743 176759296 844006487 247327578 264329359 356654349 662183118 881138548