10000 291178029
914071471 949776397 118326770 677511955 538679612 139059673 116875275 718452829 877378571 143274629 898164287 250119859 934597512 878468737 342789504 258517503 761051098 404480553 202249470 145148888 820473270 834041771 714712671 700014786 526732348 353971016 741667548 158374494 729764041 87122328 571964297 962302590 279894386 25714702 801531973 391425881 619652607 443999154 777076583 783289888 609616505 652153730 849459243 258332467 443128402 886597788 181182936 130878218 319221550 37058873 700645253 119802413 299058013 20766133 788977215 91660706 527164403 980523136 854461417 865880988 767581525 124496372 371436686 510491525 427347858 608500080 624124625 27345029 183951987 949831292 52957106 191636173 124795858 262579468 503292057 492396051 319888999 385082590 9715846 601438458 921270953 467539584 366427651 697475377 504864835 386774696 587819433 872124160 960675501 648720767 59542070 652917024 166918064 234294519 486595722 953055888 432265670 742375218 239093210 320206583 183784793 886720600 585683841 919613845 782214928 497620340 701815755 505516796 864435861 358868475 915837478 294274453 770826995 389327713 772993247 164592330 220905303 219791558 240623631 46844861 660206469 196167668 398177846 738598836 520805205 586652856 280281412 472703520 331259878 724958796 939866448 465217033 547491993 362200723 211599963 222941060 57370132 991556790 673055520 917099367 546077439 599886076 177707845 954889944 94272979 961680441 685040522 259882436 844659834 772837104 790376871 343178599 673263373 25285451 716157920 301763313 836692604 549002549 349960190 867756888 716164246 119572449 282457147 42843409 474025388 734662739 463580308 991446153 904998965 999083537 769395188 165635307 890187494 930812200 893684638 26324654 466900769 55405569 528964171 74631512 913486999 225134265 215039861 828897080 427178134 958617465 349402028 842965768 369305912 418075024 922782514 897951776 849512305 139762121 741555685 144642639 170628343 103816969 707907510 725255001 585695101 463753020 841380586 711480001 324752701 706132271 177822131 536936675 795335519 758439201 482104811 166920170 816360178 852962237 790931198 35332312 563075198 642906313 683748184 960080500 902567314 299576538 714468825 476074829 822304860 976606475 218207961 20392223 248026200 709035550 179341125 201738150 31526258 209038420 872795056 501340550 745653868 41678129 452255630 174239471 681820655 754824290 823035744 542892356 320690981 271164844 503317358 519809680 361616748 888700642 649889414 25702367 748341633 695469466 724987577 797365338 72377329 276685596 741261680 718397511 542422681 526989230 702426819 60724688 729757365 723350496 191337551 676028502 499671459 326725101 893089866 72951213 785514988 459036567 280029247 183986110 348023067 400004058 786226924 191128176 914308115 246510639 736078858 675452828 502368546 446101805 271800090 674059093 99530249 824638291 834062814 761435422 969814374 622714592 896435386 701910222 242179196 356705349 839985459 180887392 507721726 382779536 959189833 883141300 796944449 162874634 950016639 351440989 330953808 434764917 912822380 761276279 768869731 721869746 778369228 923021455 145557701 669201826 88741729 434337775 249761835 827151745 489468806 885223028 902925562 783311944 508491250 735663815 76603446 790276948 692392026 891377483 837577214 600025723 349294188 230097300 446953773 160541404 980503831 88502950 528823743 181696361 763179596 148495724 864155799 756554723 677702802 172830063 211055834 74722349 752489372 420966313 157913112 980871256 272877041 575948665 561895187 81208571 853313636 214352972 51714940 965894038 195550135 433737316 256490893 502846668 791240630 55552959 543125830 523527872 883390851 863465906 147616312 559348379 934639468 539423935 199344631 434946383 329845561 247833421 336119848 300364475 190127754 788737948 67264635 126204641 261672323 601141003 978363396 810436810 323438892 922257254 934781185 338940836 700281542 337390382 595222947 860698243 150072481 252613157 577574976 176684151 862448814 170099742 991027680 124480016 115167402 182544372 736707858 298586798 903442470 655766188 792023259 436680820 36479830 935372118 335771989 464609077 588243411 890255144 317520915 887239025 714099105 48907591 305613117 282318982 719026335 473413210 329196096 844924213 64148115 267144688 40924521 500107896 295324159 697109980 430782168 174451507 125985741 444286029 935678562 31941089 151289419 112232924 11539036 8742257 160518838 795679290 528808069 455909708 35657213 569334800 169686174 324498931 821132776 565058826 631404990 55813280 102050025 135514017 304088855 156477247 623310234 582306552 302208194 789209105 56615294 365822557 476860775 255670613 905869989 942096837 78440759 132738965 584380960 445353828 439003908 258573799 346379276 128422806 856139472 699763991 470086764 6082299 800738927 403012993 165775455 909259315 356272399 562437 743909241 180103145 632811994 71996691 80628957 14521553 224369529 629801687 901846469 999542896 99595483 544163 316869538 203643125 747305036 120486512 887283180 780055677 170941348 543182322 374060355 334658031 667326718 115122621 203273359 268453574 235493848 363173882 159958757 829553596 696910697 330051244 458782954 768427554 23195878 844609115 863262039 451655448 169167302 341875991 7201947 797685187 797790145 499246146 760772778 782608129 425299119 256575238 316185709 401850587 646288786 1790306 112240922 413408702 395003683 739097987 681908626 893076391 456896049 117438265 771719686 583411741 963297569 766293295 5262324 830650941 260064728 546040643 541345720 576671819 579279498 454312214 285199373 184274712 677271570 784389876 75765122 783007344 99851678 508795002 187327653 672014909 408526715 937580113 288781576 588078323 534275114 611941724 134698026 358726180 385130281 306313190 1895389 968000500 692794330 730272344 551165500 335867180 786881862 420913656 797341487 828216326 325989966 417887228 956998805 856367901 182495353 45090485 984284225 11565320 284222437 957080931 647905760 44683862 222761905 671795734 602676066 693679219 312210951 761797159 687185807 390068941 459643991 517204537 216588800 749749732 148497864 414609094 525510960 427301451 503137672 396662381 876554401 357189755 839472542 977739056 945780256 980338191 149162216 312686829 844989156 14005014 747612317 518351028 332819691 583083497 148907305 737655240 910590016 531109754 666446070 197245065 826585620 673082505 908545102 338029673 542906748 838810393 87908538 529500052 453159945 817598405 226411481 701011931 240216997 16820009 633146413 547015927 510864271 690054964 8186462 451917845 921461800 84292749 235310440 600193465 213431498 746136698 44449555 268345473 999664985 511112844 641015196 110289562 243319071 382277664 89541138 577145584 256602378 546786219 78240080 869478510 348906361 666858513 748863209 584524863 809871295 517141096 965491876 501484189 26650606 594870101 218478595 84128634 721377506 681698673 444775472 576069765 904550115 65411421 865873054 986439546 717122903 932265432 981004532 705255027 104428499 268477160 545240740 537173106 642000272 989130756 841981077 920710382 196674888 690171645 50931379 741890639 696225089 663775517 347232155 618472037 846448632 428723667 71249882 665653000 525620118 866373621 17015104 864761872 108622682 954414641 895331534 170790605 415360813 601934840 964066835 237689293 648482378 249325025 879539529 812505804 975790936 218889467 893788667 798939349 928148518 555630681 311978671 775932697 795729092 526906437 333455646 136998212 691855013 631641114 719984964 110514090 726192722 561766730 112199117 732324388 930686370 501675717 792300880 771872561 72589525 915216190 539168821 259969818 895297851 100149138 24220679 565262174 381412257 749757387 292709684 605403021 814288827 775462679 375918252 707366791 379731578 939677315 529428010 213621189 694421649 584560432 352148736 62143968 207538668 539974500 288589998 613293708 90100 96081538 722588914 943261344 54376073 493159700 915941131 600708648 732064437 509529387 41711675 545214495 517561773 349584013 421414204 132482957 474749252 132604897 482317190 482881759 790131425 764128362 861024233 818586518 651220186 887156698 484528449 755251874 464418250 294189422 57076284 62474116 890951301 706005903 726361426 686735763 281703271 594695647 102686354 481818396 405031058 221410521 223531957 414034233 749023801 246542023 28300949 306178820 183821983 699096826 728274119 389597999 89754466 913891808 571907287 302906766 402360319 541628348 255901308 645666893 339789805 498510789 969159539 533921381 225960939 834243813 451127264 590516573 596511440 561530717 136034744 707598703 769620315 432986910 340591082 419650280 47939439 822247440 612649964 517079552 13198341 758307355 723365797 172742838 350589245 814189623 92557667 170805435 904999385 735906223 697315349 863198275 121495277 160791460 801270736 129621192 490468594 563436374 5842440 78312008 469058572 472658722 359543084 874048367 712662041 916584229 855145249 192551102 868744866 413615556 148571179 670289682 628122794 85930111 817839354 781744162 493961604 140108791 365442274 913067892 791545916 315766133 277675541 209131293 971672441 993821297 643155070 919562195 352689762 737932858 724292466 424603378 93706722 927322838 188278387 569516942 623653740 356782290 847497318 737596353 958276756 877487542 215288255 686492030 190237606 220038670 464538237 742068572 47474057 907965398 532948599 496164112 414650140 433602011 771973641 985145468 231983904 323174185 742428061 674764829 934696760 735963907 656346489 787047548 618950876 549854520 357587710 178698081 37120566 537366581 655109533 688439893 732367858 612387949 252132925 852182075 597611934 865843308 493419678 113747193 583451944 163493561 46823311 525570789 271091046 513105410 502726956 228277698 131570582 937492071 218205685 57553601 329873443 42915800 630360588 407701205 464458338 949418221 300898114 317891110 990270615 553289687 269176996 667884694 629203017 657127866 931985692 200524540 833027972 838617107 769390151 330499174 634594720 13821658 835714285 131876452 788532460 272336025 502611540 137828530 765858923 827274847 66588932 852658460 451113134 159885261 803726086 193651197 924352568 319811429 992046181 764732240 40577789 818005525 483426794 681063192 140359304 540911296 523712136 114876821 533601475 535321449 763480580 754842311 536268611 714947536 440973325 143112836 5531104 915716982 62565446 647572823 867716216 948381314 648286020 741022610 5014740 287582308 40164001 28896594 558430895 213264662 762243538 625472768 677948443 618291745 973839983 488848385 518491317 864773443 651754249 930358580 425860190 397431166 230773865 284938474 809490861 842099502 358626347 224981833 390191940 728616520 965685233 382765452 183840844 47052829 422313886 806894309 820848470 753469679 465367418 393231040 344429245 719293959 445700914 68336955 764400866 920575252 376091865 503629969 511767052 651462587 977320250 514199136 577746275 693144481 88543509 814721208 14399218 875707776 630588920 36697444 696239546 448018347 454721600 937252018 950949547 58220934 281744745 248631606 261275316 159118261 596616334 925663840 863567230 671405145 537596612 662429756 536111948 662062851 853627967 459502459 210439268 498137674 172209035 225328479 56441318 873259933 704625178 833992400 727974001 151958208 988810215 42229577 760146449 423217780 919306399 115180694 483577355 447671678 795510198 748062500 782208456 97417063 174666612 110322531 701396505 726720259 344926303 348645261 281883827 444580951 238182709 356816236 670511301 205400878 363577978 724375084 914946800 265721202 451753213 273326426 557400682 341234149 472926279 106787146 846054264 724070203 479918566 794690561 44362894 660681844 633062663 327861379 460511317 385634830 84323055 993698510 106530786 304441023 119411489 230364921 249074219 974062337 240876305 35461888 862063030 495959084 563508681 532496356 9787623 328338480 178687114 616660158 585172263 63811049 507938428 698605723 574698616 248303676 167279953 681216408 289450861 683321725 696697444 174024860 268599291 737450193 82488145 811488998 838323449 243628120 56250836 952994309 623375993 421638153 198877664 773229782 277619917 839065287 205994697 355441543 677066809 871028533 906723654 404365743 336349339 902998455 634891831 744477060 517200745 43126130 286870905 693431284 554357151 642340900 522960238 988541309 155626486 913492223 228911198 140096661 814922527 294969382 667008632 94480761 729168551 788403213 908856758 939784998 885153793 498375664 784972142 321806503 360884410 427643556 62866897 767176937 718777675 918496103 490786462 399391875 349927881 908198217 155153571 732767548 759325456 589552031 558873938 747925071 130690744 966771454 141660882 970032487 438018409 209907358 350934394 822198542 4738697 816115967 262365117 730089757 419857912 832439259 736761768 494612046 535467591 782938632 244707428 423576608 643666986 667010250 714845580 917532849 477038993 693377537 345891399 540110261 778255233 511186690 240075471 20371835 546604573 475827883 778601980 36472705 773712388 613036990 452091292 642752301 274284516 710597892 522628005 814472890 956593143 962565044 849512973 518067975 653617582 962999339 791624133 906374959 855414945 783097359 367680570 369360084 951168974 973276827 608291257 232688718 412607444 680763716 230073635 926051766 956205538 966470981 194497056 457473481 54687935 117175638 254935867 99026525 82966838 765871683 65449125 120417920 77241080 317171590 307961350 834635973 793214533 660234155 758888100 474132126 815134131 286265341 501529218 35264114 520933772 32978204 892409595 703573563 100753911 792760101 822362723 888924242 956457780 970477075 984431438 317373296 806801718 759248283 641345053 643908392 706984248 842345411 135838592 897950707 452282604 159318635 482826608 402823492 908650509 518410361 532234588 123919409 543068524 434849547 738917388 882279917 839235435 786014605 233556590 377234126 295281434 599514391 961076137 372790931 541847304 465002222 501699426 407915172 40159465 737455420 727029940 105206154 836184782 204905007 995567839 378358022 827832242 176318446 381530031 174951260 356331250 201790213 622917034 153439421 743022779 332247440 402932863 731590198 405689397 289404868 74391062 786843947 474070793 366246203 956393038 93681248 375665223 495709399 131248720 510576935 174139010 854656038 797773852 930842152 629025323 261038001 487627377 842743624 924242623 536672134 903467234 743001892 443078413 135565907 355048321 355610862 841292327 81586815 994333716 421126576 177802604 882356992 146792365 26072521 325359564 922876459 751024928 572302124 21878028 178096004 144241046 302382361 896186874 103725 881691383 608622588 105074351 513362929 573070040 670793672 379726761 698434545 551659999 767690133 618955902 401983537 969714894 1581099 113011912 81233350 156124796 16653986 993810341 232376358 147294144 351491062 498130240 261734259 572026464 376446730 230347590 349028749 239475490 198983286 314704489 759890447 25992818 588587886 786958302 403257185 104113589 327624419 575760781 725144344 165933655 140952870 236943958 923554766 148175970 365879961 563878103 710947865 434935876 359091116 642410824 70834772 148793501 247463072 610122059 74138791 706417793 135050949 542049415 971644120 80510242 487359109 119149238 832934482 574657138 850671571 980944064 983196368 31456171 386529761 913939135 14048699 867517896 828712061 446371034 425894827 465777578 444077535 246674162 88565081 925359203 199855098 616677320 85421212 468755051 520739324 144447215 385846192 503606043 505610538 661742017 995226148 422967209 350050458 155036838 286612816 264680923 80935256 120398239 188706116 476886170 130711207 859878652 687547681 315891546 691271264 122467895 675815188 692505268 1933488 728175547 361813759 65064924 293116613 2404503 367846037 478582959 966803270 546554873 106198372 14565051 4647711 520614196 283299341 298531542 752601893 305476221 823612328 971965810 928448884 855502520 826496213 689339750 201192965 982322927 943681338 309395357 954199176 70867587 61815504 852612164 327919749 877042073 331597015 656847031 515800874 470788096 277005430 523707686 947893197 186030704 578124205 178778112 324771812 894849635 54520381 390531717 562035457 782491802 231211727 474856228 81254388 983328641 7615547 779886798 135288692 47308983 348901003 194219873 645456089 896967741 807657146 600061901 886411127 460470601 958567767 484577161 102420533 174193141 500170004 310626358 484884068 380624675 120417987 785926235 339961831 379698467 28873031 588422611 19485807 595555404 16820436 803586159 453805952 307883955 171272919 482593022 819055990 47599733 406601574 423890845 998017684 151317577 516575038 15753221 655756182 677614384 67359425 88114141 583418275 634435596 805888320 453340322 751357722 23737393 739905274 270874968 474295639 451535660 390743970 329624976 214825998 458017324 356551139 518751379 871265169 840903028 5905900 602767436 514038088 555059275 174284199 341062602 787303458 3583187 472322522 320738008 142802360 565057439 48794590 478939718 856227501 731102171 735083579 557924331 831733083 514717149 807630741 280758722 339960406 807144295 575560368 297965480 548255241 331983483 118970282 584534699 293066225 193231691 142626566 746389502 156359712 901268314 394827175 501177317 269792243 728220120 491709841 761210711 539376987 189474960 478919343 810639312 903611121 940391608 372611780 641721199 42762053 776249128 820864496 466528919 477003900 280723147 120248458 859249687 882579320 319911470 876843111 119081110 595132809 362777321 51616593 272334897 368640019 315244175 178905460 211712035 310266831 709172163 347111152 907675320 373076688 599511813 610886911 225432424 657946503 958240057 907422189 207735319 177969739 538374899 793851834 160511251 327982560 135281145 684059126 136133960 496309620 247912136 933777292 676326266 522545029 970095064 739905045 841680581 706241403 116963035 90884328 185976404 754657862 154808138 302356720 155071059 224236338 23339603 991999221 868704595 818735884 849686509 843404518 802405079 52602801 473782117 163107654 422212369 935872486 69032782 245845102 928987986 181639664 910940428 69949529 620338553 556042591 611265202 908050568 910137739 789939168 994551572 634196085 319266963 983833544 169670589 231053667 843024896 252810026 899533950 574153397 834693817 378216546 347204846 783669738 760192061 374703666 45082390 19959865 235121415 82535392 801025377 226382100 559588044 87876168 887295946 204986497 432380175 160010107 258607798 727769622 743127141 886349467 533776573 84151308 886041064 216817037 712523059 501302311 54964794 5122522 803683508 833735302 843558575 883169800 362674422 743107465 598157193 792903175 288730463 557915720 842197379 280366880 801621816 275757531 119990013 422650626 436541824 971437834 912242700 537408317 301205819 998825925 675885574 88526087 168021246 195542581 72056575 265776853 636105799 880625182 86753980 748693548 191531660 464189640 39915952 5501232 222629646 790133036 382429314 712091061 900526657 88629895 574313072 901662111 738816608 295111904 160433571 671237092 773099000 975209634 96390034 117479237 341306006 54083338 241557978 136494472 509490274 806904950 435195136 738278151 700498040 703497338 472307139 826222664 223845356 226991297 282254760 805493850 903135926 495078837 38383134 683027408 262857960 326246256 901285809 897261953 543962528 63511414 669002388 847652013 848151257 726367225 438452375 766195593 407436122 642688471 763420560 415061545 833373108 208076895 736479922 912682042 118748520 596148663 608979769 94081084 129807683 271499851 649133546 888452539 100931268 147748716 992885553 401547279 251427865 187558029 440664410 976744307 147664315 671681420 279634469 534558471 114336123 616307697 818140987 56150248 478099003 714039914 650393151 423316762 750300136 457496998 499796623 869082561 208431276 444804135 178886597 508988696 363563686 458234338 368487210 178154782 740627719 706443791 527198897 52386459 613897607 296093685 383050754 496103165 681172803 209391028 485599405 440636352 975653540 386188374 740578256 13130480 18942415 922787979 779205895 420784670 196318438 640684045 204216517 781148998 137761131 61084712 870268500 793354847 748572747 311157116 370358533 511506171 710986831 150848320 390626527 437158801 215442890 593658921 541621559 251809378 832627159 727627549 976208748 272343405 362871167 249671021 278910685 836375548 55175975 922686426 850057196 366372697 550700695 15328923 59733109 292524009 594826371 256352791 281321338 191420209 771028617 817733537 140916439 820949853 384172108 661483761 796022579 394121961 726516251 220444754 404954641 738003229 558154973 909152381 893353578 635992534 31824913 780737606 692115089 930271654 749055455 488715994 241380078 422973786 465980523 689197288 69553641 419305435 140568822 853464415 147317115 744034777 208280269 629209406 117689644 809930791 166693622 628633907 503411752 154426490 983546159 613529594 169581541 824731124 499762957 745357736 169624324 49000334 324142018 741977838 405411859 201039268 19012906 512626126 925816372 775372759 193377287 124838408 530268252 76499179 416546070 130943174 627861931 19454523 84817676 868819412 247395132 914366552 427082150 304006597 58813346 993539891 525512970 743025852 729324306 17282061 95214589 485329240 691752231 743453509 878877104 832998267 42845422 291520047 295527924 169374827 806052520 363172847 187701193 990365056 491699835 201114573 434657371 685465259 664888727 424783052 497834563 72009659 232310892 234913163 473242189 243657830 531888443 687909526 989840736 772331922 378309264 394081267 337611386 680750313 194777482 461034759 253340663 962793447 248187125 872656118 900292731 415949581 752550396 835921144 377323347 212419777 439046236 799745134 808094042 820068963 257021787 757605410 896968679 934404066 862912232 706677582 76211868 959237526 813238345 600178467 436034560 267305587 311373840 526115147 205400228 529749234 525149739 66980689 52382590 820623260 588400381 340167953 169949912 818488680 872750921 653113734 87890944 391751579 777948825 941121590 209022260 158863993 104516911 656011583 997396753 55121491 925172237 212105471 38681646 124960930 829082964 986029894 531630477 853347811 449867931 614080410 129259466 652985165 862173788 742415076 298735399 571773188 277799832 316125844 725433040 588091120 81888512 587728919 753219464 317190555 279615778 634507779 488678730 12118524 167620600 826127819 414352860 165128160 445044555 168005479 261967000 23013136 610876013 772214216 212298018 36875988 198676665 661795097 266419940 971788864 943090282 148903086 720809756 15028175 336413557 250092525 611350068 869145879 851640013 169508568 690728050 117661772 88543319 999116135 426497108 473015985 976478929 314639749 824316378 221165056 760039826 699011540 76728449 206360378 955777730 734267360 104208027 418349853 981813749 110700438 916140770 462178833 622609430 728891079 153270449 265705421 878940100 432035228 514214022 319815479 841213528 732172225 979722776 317115942 56431423 840485021 854328845 640796965 758650177 210893364 428339450 735148070 29128920 299263766 381489102 168083836 144652903 902554032 57906256 19622074 701545426 731434992 375427846 906269270 185245868 225549357 138626057 553908108 13511354 907133482 593849651 614216845 437276552 509849373 574954285 137390318 284570444 867089282 833444941 706588662 522965799 584211889 92507961 37474250 379332207 679572515 455847945 388422447 730098416 232677856 781501477 522333010 7117569 669238497 628369655 283268247 800359703 798638656 609464221 195180444 548085827 571170167 496971239 121123015 62778401 397014129 690352663 66809981 921615866 192091285 480780873 212160909 563857980 98956471 475758683 125892320 550239977 365751381 451358658 210843859 243325405 269950041 887719299 591302835 962753541 634048175 686862443 982531372 404898178 553356154 182915244 307099888 17692565 494673249 231574063 550867357 830734648 26540601 353029368 830242246 175364787 821103726 149662989 800858395 844332124 346994661 294754017 591458419 498521517 803660911 729659361 236272136 19246977 581339429 655197214 990658890 482381150 261034909 626985474 319803596 222069096 6176532 603237662 830390392 121767856 711580617 482679946 722915076 10401484 636391530 660738878 592572140 475270868 618796516 698590523 141916004 976249194 335588851 675254813 534588454 218344218 569686219 919110662 564984802 403960366 437815474 928634535 369383971 81994385 592177927 17292844 989394052 411200125 301873162 284498994 180571823 272180388 200033659 47559469 727915944 235037514 693546581 615473769 215672120 240394152 709675353 346930564 88621240 635118172 213548922 823680753 777252918 275234697 587528300 10193279 807035982 839521005 618180303 804387936 300850256 357702888 548343681 37461609 592763284 312648193 831748850 243178998 431355191 945826970 288343360 422573897 672630223 934826238 64339287 162555627 800947843 96046971 17421429 743736146 79205385 987408838 680297872 838158016 474689268 253069170 986492235 333921881 453724479 305742676 991211685 280353338 309730351 461254340 198944975 208407797 668439432 113521276 740527176 590133979 470334251 609645037 658156217 136347123 189352078 965754146 947442166 561411667 452505310 470272866 580415284 375620862 58755739 909866610 331762413 850646479 495034217 924916339 32457731 307960534 462803682 772476098 980138267 597755365 60801644 48565967 660246848 212716010 847808594 611949470 193824026 878858545 271358865 999917038 363186828 335651585 139795617 69473104 964504411 785410498 132689879 799893375 70054 261835974 216298849 530434640 164360041 454693498 485352434 22039630 149994320 371946300 255846857 711162781 172844526 492751621 188002145 344196324 961542640 283804096 969901070 516637763 31764342 644513553 253240775 397646551 578119163 724520359 196413389 70560944 16943384 328632942 73281390 823988459 38642687 617204047 516249709 432920809 715871709 374038431 606869357 387706260 400280405 334232480 515302825 259316519 582649627 481147597 218979422 253116249 723540160 587003273 477777335 444933977 849279543 913413466 538008027 221148140 975917225 31616355 941015752 132163326 633768653 843263809 286146415 670839349 449836642 144117369 480026426 720880699 528067468 630532777 450965750 511826418 200549727 393411943 634392073 397081172 43101465 145609778 912837689 938031148 879964896 636599708 786734579 827753463 720909711 492442415 983355060 295522667 652749908 97482115 714505177 657978291 49866060 782747060 192609718 365897653 178601000 807330244 185300629 926666084 166036258 349454327 117822643 505346940 274621217 397999872 206052393 732023592 794655763 371022755 158395061 294001457 990267388 452144468 879792465 249679848 7260314 785175172 896962142 339817255 331174845 24274118 339145786 539529471 260519703 753598578 599472747 517897592 272936861 988492187 463286727 685862598 972321735 155448548 182487431 331000287 887426807 115089717 550826977 211360119 72503539 101781052 752027858 705409896 12145497 357361812 645472651 73454395 61675548 499610224 225876305 529322508 517506144 818202313 754672232 399255810 452602365 315932005 883572966 648170984 595123297 350630228 624985693 843031120 296055159 79536996 608934476 251850334 218106494 255807653 905330108 817358079 734247112 257377617 944665730 215855535 443550684 567306714 197674274 805563009 719880783 436148593 850529791 571087900 420819089 386700140 406197993 801983088 260610955 499878486 471627645 259123920 779480379 582611776 636413532 835203179 983495891 128117621 808929707 241864477 476692936 661153029 775437594 60779812 243040818 614449595 434272496 397850751 104536438 606138393 327058643 827226303 38112933 55244480 672974065 274597145 571322376 930265288 821001768 421874769 967817017 724739272 440547216 450675597 51515918 158332685 997390156 943981843 294486230 419226130 236347244 642300505 234720200 262110070 47940182 856127690 748326648 211016100 894935975 556151500 666590564 97045152 844375 691749252 853945038 956357902 756602193 14341942 961680594 123230307 556753476 524907720 573745360 495606372 520730450 363065896 372423003 357485925 319731138 212589022 33203604 936605242 413934676 501723660 945872191 216882234 336232030 486011532 41567159 696960122 276206026 32622630 153403264 9157804 282221258 33538981 808685556 379402006 219882506 538880866 881108091 844552796 272144686 734659051 440149018 706638983 977530231 415720214 711464221 896573977 613929177 568066103 40864822 914466708 63269377 473478106 602948694 913274916 396311208 467600081 446370729 239781424 128204806 293480850 387878016 403361781 630690354 166769341 452374176 627008852 447433230 551887399 628750318 412410626 976279057 483318968 950117121 257538330 106221724 178883393 937005134 455934827 655920436 542507453 670927071 396769553 812194898 135430049 883183030 513363677 780748733 74094221 851005181 449748472 890422595 17026613 220408565 50587484 574690017 767428820 625511948 305861687 491177319 299936190 925556429 120252644 363491775 808754369 32069409 210784119 211561873 531651363 78334127 285181196 551657477 618630182 434158670 897292268 952232126 205247753 324240884 370263734 264445338 384678037 39779680 219556174 116693885 406633693 149714320 205351477 583039919 53448728 460565273 139865010 429862589 845991477 349173715 479005002 897396142 263492887 650690406 375915474 401745807 828880128 688438235 132705297 932723304 457636970 972875647 843476894 470884550 510515062 884288639 200363350 600948090 764902050 336725523 698278690 44636293 524634418 792871111 55005083 839520112 583477175 652287094 849486373 374583604 430650318 62662690 663806803 446829648 793205307 505827575 142209999 703591756 101272804 319715981 364251839 510745339 535427515 462921988 375854058 933973899 361677116 869167082 957416925 456835226 237991142 254899260 118667889 396942324 899811563 793974102 43393808 90395032 784602628 877422046 230453907 355807062 111078556 998641829 140032231 364741250 910826381 492427401 558980244 605203188 432764985 905245536 28906128 769986626 434038984 887123419 887560260 837022687 646715972 508127872 44791417 99796139 648584929 56387434 368991523 784655318 132225685 106385924 188994959 602649252 900124311 603023383 76335498 729860805 396213247 760814690 706043508 503603926 864617385 952193578 790886306 965171961 724800211 587845676 312512209 833252751 657315546 286171803 693713275 525702655 51233058 498286375 523103038 747085999 77674091 556094683 762977619 50360634 813679375 943858423 47100211 939582487 39659198 460253341 677785151 34151311 341270836 736540272 802869335 257994846 970799593 681816497 174431392 185708141 24234647 586593404 533854750 200759516 776937901 509275242 330469825 827620076 104625617 544204234 752083110 855697166 128023772 123674282 295449999 614833876 558990841 49749670 278864100 595902509 254523599 351919394 642433090 274235346 826386368 269656357 128253536 969943675 406224477 891301065 462234692 965115635 327936290 103420194 941586934 702295191 112604621 454938159 533316325 93791026 626622256 26098797 979883661 865263891 459479158 896246836 984954924 147218929 826353642 420944641 410177740 305039927 246943526 94183110 260942035 611306226 412358107 494571615 326118612 767583530 447395263 247710937 534589501 246327667 410729114 147718568 749572907 4696369 920509930 197076182 805353628 628503172 859918604 188444519 88697427 797931500 26058825 204575478 247581455 820330565 365378118 41646118 493436244 732983039 468992508 196113185 251061539 99628016 175722695 507439592 137597681 447726060 876791238 458893774 524661553 251226016 768131440 695634019 351164669 24967411 210820719 710621242 268929538 15055047 28576205 798468415 567722440 182816809 767758817 336594652 828395445 304574768 464985235 407452617 768160979 811291367 572806757 534467466 626342285 857900629 672623440 334975208 644931279 228505688 548778637 93134854 44453935 968817528 873973075 71635037 485984657 129678697 427507697 349229960 471884561 648873393 72703447 431226059 364388393 394458366 244851997 310562460 603020181 651334316 541493108 644751722 639129078 455861564 263686115 443580060 893341469 249689598 42754638 236563275 244937622 99777111 71034006 913771506 224556478 471628556 843534257 149034405 906921552 292057320 54437816 238784996 503124561 754464712 727946032 925554296 484324053 110495047 214047620 666667386 181868746 612432829 252360042 304029130 339326771 250019367 916909560 661885605 815017794 835234290 357214451 801496038 887533742 499871866 865355708 46060773 996326653 951641617 742066997 342062636 840738117 855815925 940750521 732434016 163118157 757563591 846457261 120815829 377774403 451570579 780396586 625720563 28444184 824700961 832676100 455355440 835459784 552958049 339806503 389196020 388799839 709584122 271051423 852732151 123580385 918044207 426896198 246576123 870410056 875341291 96578755 287784536 453218196 710686244 620215394 160701768 784292739 913329487 980860974 288207095 934899585 804106205 439777134 929974274 253360725 188028734 247490923 593765269 668165005 791065930 340010399 584448223 139554674 711877420 890108941 769808858 804913519 684996807 440891301 342836827 803522926 299209666 906734330 415670052 873461570 814777129 575178968 22898963 322853961 705137291 636354509 979531853 64560921 115125746 951521690 784633236 186572317 361808391 504848676 234601803 284864498 714673705 803575778 435693411 589031333 795356311 395046237 162945742 725287909 299690739 598951759 103943610 704883444 641414198 5988365 90152671 30615896 722148972 334362317 986580372 491315734 956435193 416124498 493128896 437268292 586767297 334503272 269051871 548443898 438042145 418565564 810923843 406736608 547187285 795944620 57757430 283761885 204436527 746930333 72869650 185210033 598658850 259554827 958721947 503422436 527919415 737959333 287228893 914320901 279970189 863067742 819938781 919928151 688495387 894714271 836002156 245872369 590210449 786515201 8026868 179057515 845973002 880531133 297033998 732080904 845014982 556504062 127167363 894669654 581751559 951213301 546063469 819135050 265047451 455245682 511226874 143878797 382980184 275966378 647999952 678198673 895578927 920754787 427480444 655377230 55405982 58417986 47575314 190685490 877864460 294064123 153700679 471728170 670182747 702332089 484298380 447124792 303298948 40369652 622123522 278348623 687410646 815779371 938273949 905247484 539659885 459197437 824950996 351636063 686261105 606073394 682429410 851805341 188897217 64045514 750641884 908620326 327685120 135295808 248612282 74759806 791767395 14894083 674472199 75928326 242978891 145600968 75973817 906244444 779342751 458127705 701665401 781690015 203462007 694494448 577349353 672039093 89020903 354409688 346939789 787576362 297052149 455423771 899707694 796913537 847148852 120572074 186057260 438301939 926037748 434402570 961859300 110901397 538270664 475226885 142984366 181038771 253593873 313139080 777514726 652653179 584307857 231374750 76395543 494564932 970698452 75480757 376099177 182773453 484407910 99354865 861497614 847402653 420514356 460540645 246930333 61909799 946468687 130441951 729808050 739748538 478939960 874409471 593558412 737775776 462273304 174673120 868869929 905501918 992745194 500708180 163347635 851970519 999778197 786874680 521373600 528517805 67483768 858936237 280923546 823587916 504884876 266450604 414000496 160737859 19471419 817322177 8872828 705177499 944525702 591216534 184751795 310444995 935201893 717654905 965013992 395227492 305487565 243549612 790924268 835902263 956758356 112464814 712805804 559394611 508130437 250247846 972995271 389683400 647999660 543720305 304384517 458419651 341005602 228241019 972891612 774439381 526924837 442614305 300350249 604052549 485752 934600335 820604247 462671022 250196093 474783372 1916273 663439717 458611205 246776549 623494054 509854479 615855909 805027099 179306126 505284719 801093819 285052272 900411201 11062008 502050376 181388014 300046814 367963003 366939691 931347368 708142552 119412884 433568425 847308403 958959518 108320669 449058983 419775718 698388693 696877092 203521573 851122826 548879540 823134564 368160134 200584017 225375518 531781793 490262661 3742281 2593622 208498124 647943717 943564518 630592319 636737256 690565935 344485207 62318469 150677235 323834340 704349628 672171527 923378935 174650723 763514212 545567931 646637595 706579905 791702727 121869798 630228012 289969539 952048794 84751901 292605822 547632620 238365756 245534879 184352432 971477212 831747833 58940453 651601936 214217333 926952598 103151806 558470128 656711584 609100780 748209935 143421385 229400456 823916367 284224577 133204274 203057595 179577168 35461242 15821039 240103499 189252655 581363972 18271624 295567426 618993985 879103889 737665824 799809753 105905389 816319051 475039585 368901933 619107658 819003672 670129065 346686666 237796879 893290174 454614723 680829460 524170963 32747396 655913196 553263336 751086499 449433051 487765606 835544477 401985181 571485722 509501156 171001909 667056404 268412017 133595040 794034503 930843725 807438108 372621839 765444635 353948101 809865719 740978235 307007619 814978883 74801151 771976195 267376161 8448304 41218498 463451466 363617892 571403830 661814778 635955313 134493699 354479177 419341014 840870762 435704525 896220787 950736911 934262455 416639613 841366046 884582041 365744044 36896636 276943871 653184964 20869293 616696461 181439664 499461474 410147653 961139743 432249028 388182374 274959678 566274160 473647320 394868059 593461370 698339925 298981600 651261874 60480870 49533700 906694578 534946175 479384641 942714446 764055222 671866718 335440631 219131961 466177550 272910010 211182160 576996360 938183940 257602230 789476793 333894390 150226515 32413380 360733034 556195239 465411065 816727469 132322715 857242305 625054758 609752330 502265451 212518962 205650766 530923639 907204316 900500610 631855595 509533294 819294063 967766419 851901167 586331575 626518443 97045145 95163621 81294229 606223655 300960024 534087490 847742158 132772600 116173952 541423735 380092257 779398817 760835165 69050584 968868442 984863510 426630570 329664758 370342292 567882165 971160558 649157473 954020356 329711486 80467706 171815573 819607394 306034285 464548021 582035695 614215516 146535295 249926522 91287115 771529313 18000522 627536598 40033474 571764992 772202655 31981516 720888157 306006163 910475992 892172450 364762299 89128872 314511096 43627439 89224584 323211656 899055608 208993147 463435209 80808780 538860396 967188945 166486046 189401827 24750613 113176202 703174958 945101949 768527257 730925340 895623025 227510779 143768871 282449745 182697239 71845790 814177805 740538212 631951962 42862718 689848740 339286812 977023615 870250469 485690832 341298570 973850099 906580512 146851562 433027719 207811637 542527536 972297828 601739867 624318662 253676214 417804698 526530545 322795834 906417860 544466640 354460225 458039326 7948427 89612837 592695430 978792513 314717409 269687192 864863975 799621205 651568158 714748680 439622859 221581639 914773463 634698570 254712482 564893893 683225800 575061934 524872954 906748651 926699514 562489073 975090960 142560281 183188983 484665973 76633496 679355174 382873751 751248996 994851162 978662660 226771116 989861665 747281632 471953341 807617737 365450801 779116805 437981687 109251291 193589154 3679604 444623358 953738736 42739161 691947451 778375209 88927898 706678875 494119848 133562355 674190963 440660131 470190351 672168611 980879281 241055011 574607820 646031847 899842238 235815781 124311189 670699839 410365750 817502916 17307199 480128409 418120589 606905579 213092831 947483475 686450222 593970261 778746508 261335642 383730836 241587118 423335502 359755038 234085209 235522249 594349134 514021645 408321766 335301996 855663187 737648776 754430433 376673152 538456729 986185763 507045508 666274499 549476819 464077303 407032767 63172169 147143288 857975366 305165918 679350955 838555748 804404791 590954866 369422039 914842398 439715936 707706055 978294032 367995677 490609779 394137042 247586893 607195365 35562257 823313452 888535903 277607542 79917580 254409409 246909358 77808868 58057074 574335613 456348162 311422992 83331977 565553598 248650098 21319632 217780147 752234285 627791754 347758546 718864365 530602345 102295818 116339117 692356697 611003692 454441656 836355329 749802467 325578126 202937015 285570705 112732989 516187398 850833536 207868012 43116680 348676200 994414116 475947575 164408801 310887044 210701857 588216213 445127113 975416105 605861537 383230014 403718662 847028823 235973782 667776196 569817920 918311768 993656832 127239783 467523176 152898034 960672241 587479313 935322880 771387725 465207665 597068730 47961130 562243124 419134739 871561703 490386323 999301508 284575891 382062050 124855076 72109724 494585181 559417678 350990174 153620268 312079887 739600553 926543271 8692431 425038836 987430754 651345796 377678 805771508 925882492 521231605 928941752 491223046 572455628 617405730 48693682 558057003 858200803 102827834 783935837 248510442 122605332 732409022 827885536 406244714 737716823 933455903 889660444 357134552 386413278 344318347 587575069 479018104 310022161 659418665 789230501 305123806 631086202 480718701 191960860 882437025 680819525 850416940 421156061 76935193 338450825 513880950 320353259 137156251 523929570 606764074 599466880 552978447 937968175 878736699 718689458 205432104 416253946 675022364 467631938 525946778 816843456 389478165 335100316 381931058 420742205 595512026 433102651 11925226 20399115 771301045 248705959 951635801 406468017 204588069 645579593 305884731 661086854 43829080 384453435 167621470 736770784 650005516 748426512 419107507 980168706 276701803 771151475 388553340 19362430 381608477 662098050 810434137 143615066 134947118 132198298 972944685 778499501 908491825 218529691 256907242 591185105 400369237 300770429 363675365 957187576 485473686 755916680 805152879 522326069 265555466 177273979 685603707 432440062 983819393 444987614 479839694 662217178 6314760 384992941 226215583 976102530 844760507 630765027 218119675 585397546 99510735 591750236 570887974 290725041 822313311 431135609 307875362 154857373 420875977 269419975 164244044 651046494 685158578 795117959 726370574 302440573 663102060 1225927 814306324 166397257 605077089 598872036 487416448 349003897 186018361 516820829 186566984 47356880 986051582 954079763 262537780 859369167 83824667 643971858 367353708 705209808 566601078 628906447 913794608 222820832 325686368 291937446 757929341 783492098 531923366 999088477 817211430 643652195 527358023 627853454 119656619 730318801 146600237 156973316 585197181 402341392 591458371 358684019 443108150 428369499 731479825 104727390 141032906 207789298 411123179 177328858 54907119 589400523 624164049 608817895 646249839 695246333 761097071 485838052 447347546 61153025 713720573 660660111 182935446 251967974 56777969 725118400 460855403 920941451 877545161 262152563 198906704 234328368 546596143 849585360 102240997 933295013 632415180 210094344 288420789 974421450 832994909 51903554 776963019 365884440 814173354 673917058 478847274 687550661 934171542 370131926 992753443 197728351 354497785 41572727 845966151 117333154 167797065 145326588 602540417 385261262 649981307 508084319 154253287 495054786 638585350 195267091 504977797 917989097 785617124 871342429 971640019 638951056 790960519 382601747 179615622 185961857 812104645 532348401 601998767 365254500 567525400 359637095 255903262 584981427 697478880 593535166 69413783 657665902 631090429 91693661 514187368 604366477 569356588 98308011 365980490 606277612 550866008 601158681 368809210 162855978 121016302 328091853 933825455 711548569 853894786 446604517 798848545 883675103 611621261 177168349 799481493 426336971 782426388 299296169 724887062 208499751 655660786 18037039 188701898 472954947 18100433 833349601 664830244 556435284 314695114 231591343 883571359 857095721 725913684 95804715 177104744 451865515 473896952 883561631 810603860 754010029 442618479 297050228 534341777 925331723 782552735 542835340 239722484 456390452 39042835 839415505 211802135 763132697 961698435 504634202 293390462 351147941 736702712 807585690 438782909 530350644 269011084 791042539 275360070 884350764 866885114 537396170 296963657 384517237 1117519 516184729 603316247 313932917 55335601 80130206 404410599 32968441 23441100 616419827 297032337 51797167 931158778 996031764 777788701 126680915 118989405 499494603 444463790 394159732 288266093 127054137 810930322 76550839 269738244 803740069 742253144 374960408 414811843 575633128 593298863 277173684 397282741 122692494 628379723 949362632 970291514 729122463 287155012 380545744 925318094 816422787 598668092 67770751 397299674 42087175 366649444 162349845 705380969 510042332 52935693 8495746 790179617 317696012 184342449 590247605 727606702 933790946 918442628 108746694 892411392 636583024 886451525 954991511 726734948 722881551 499435357 936844971 46083854 249559870 450255529 146323930 620985473 524871733 907715573 32807219 334820583 13305599 185574682 113501696 712528127 267891043 927159356 798285388 524282763 490886459 506250364 730492268 758163751 22793411 661487208 136248918 235024829 822145126 36047303 251668706 430637338 944124663 456758810 916868365 329346164 748200750 145063008 881390994 284927734 181113578 430339633 659726194 543360512 9836926 220425925 130973037 702340090 547276631 598691914 174593296 130383633 817780340 599387280 483913853 243823865 776168174 8658108 563763020 65784341 894693562 545909357 772913480 466978454 36197619 218885492 997553915 342970371 891022065 481600871 309605667 639677767 153955497 864593791 294822950 215443005 312094377 160589183 25630497 812481178 964399627 294786434 460073733 302522265 933527167 304063288 84324351 35600855 743691332 907752096 73848698 941396386 601373528 279871650 159613847 453860645 422496178 935215450 169187713 853833828 407773542 717407104 894653927 158205247 444414559 965287087 725843828 244203619 267323041 319364995 76725191 205689028 973216346 629671964 602686107 140258809 241252870 935383252 909601336 890971884 569857497 847443122 407660057 398682742 113160646 848576769 325253416 544389878 219223274 508865106 595840181 889157433 205759492 709344121 631100162 649417084 417310066 771058123 352772981 111688154 538351945 585277339 977774773 273221322 228282184 373652311 820769977 357450116 419190968 315159908 937506251 591165471 145976720 377921482 293015331 481291731 525540327 4158751 266930157 772610020 547620204 737973644 574141250 442717275 596785929 812034249 580170393 907985920 993230059 284883520 556773500 592079860 374380591 525796506 724497502 468230264 958423065 907271107 362910559 555366838 535852900 700698131 625910216 757370959 345885739 395257892 99218178 165728422 103986501 423000921 241673607 367015149 622141193 669110020 762951447 630130968 393551604 212459109 525542899 541166910 455974564 151089282 371365675 559365452 799948845 303701396 555526369 655661570 240668294 696252862 253221364 188618252 912033543 454523836 746657007 580282538 935690919 963199929 165802012 826589637 186313517 412132171 169421984 662151476 864303692 979460067 101384935 675893709 454237227 31927094 588646594 964889155 860833483 443708315 634856899 799453674 685158186 598602464 214473385 892382999 93900868 542140719 222223654 360909920 311712998 11095607 805774191 995974133 475645280 678079219 598787884 469818456 238512788 824041630 249622107 630318051 872736680 164886863 435693042 263768711 417690636 723676804 931871197 849763414 760073756 73448687 122990358 681520039 968141967 189871240 991695048 329938378 17235917 998331722 424727879 137090400 94847488 63159142 808462495 899985172 99446495 105785466 341951816 997415153 679002146 355241753 178806139 619649513 13046981 47944565 275202703 861883704 692573922 233656426 82564993 398335798 922980369 915619368 885094968 783021341 689872830 926819839 257821675 433486531 793355193 935666442 343791152 832171197 993647656 626494704 902061190 411287172 44272407 744209389 466030126 85129000 491902304 320259273 307321555 474125368 61164687 134176478 800390834 641469843 874681713 111864669 834226766 672718992 157351491 644816822 941821766 22624716 369953768 849829196 829097633 624104074 419500039 88805037 909812984 851996544 153297110 781465983 496511090 881852511 893845901 283278301 576450608 9893200 943561860 500855283 17242094 646928611 660889207 440625797 572868510 337284271 414492452 238812979 231118052 992074836 231866722 140775629 478024620 786737254 166725518 852265405 321788851 684099771 293329733 234431048 708438241 766882290 884498132 997505612 329492424 702324315 873732973 27360251 548345796 775440568 96783429 307217649 379679058 615934034 156494174 720234510 556929206 559256249 27715500 538017561 635846310 276789986 51513399 256229892 87767430 53574212 154511650 690959936 998689505 511011048 694468301 768668259 361732836 141637038 562415251 965389868 60248316 881053916 621421352 300311789 232869373 85609695 15479985 946188287 655113906 829651722 673953056 642020846 373650069 877804303 39122836 601264981 281443464 476812426 349620062 990464048 161883232 965159207 564945880 891874137 610942986 117737980 11189828 183642277 700053970 971640023 919368088 154168263 76683966 788087312 871595873 251253258 167247877 760900046 778699173 756343875 910839306 976961351 331572102 290029883 606831567 929066474 298617473 571091982 742086037 85932825 660325090 568378180 785195170 40542964 675734686 479350015 727762397 823076629 369600878 576692612 83131452 919647831 654995495 441819050 214425184 607033435 540549206 871243410 485488575 50360975 402307101 858449627 319748534 575135456 572025953 632033498 146577791 369885465 995722891 150108886 852477646 664536405 301782373 101616618 18507348 877563995 318281953 707760502 399500460 141834054 77231664 802985972 680555969 119384748 55885278 852634819 66075456 704639639 681310166 840986979 361882887 354120419 622523341 864077043 167033376 327434360 9097969 989791510 350581677 843307111 677359312 350016192 213231355 767365347 913851058 380782363 627489525 81357954 535394066 100797363 954355196 729430561 598089225 820688889 1511017 839035615 781463157 666099529 348889683 814871420 388015609 454550550 63924994 213674319 326476208 135644374 924361894 324208912 647857431 896163302 30709512 464246220 136803840 377278526 39993028 703876497 971812745 888774250 548473403 161492997 89187948 942096942 958747026 811179171 465026465 749281209 201750466 472917492 803631557 92189351 840454533 876120492 634778270 326189441 279999460 18681418 570403784 272764961 469937483 954498957 994269926 882247686 799985836 162821696 278304584 69765065 281453530 247526664 855790459 12556288 849342792 986811769 826534989 595259249 133524477 16116197 667986751 762304650 171919422 295473039 574870981 356710432 456611045 617303503 992291077 883094726 236812157 113727419 95009422 523058114 529611770 739881613 48152004 419958473 944919887 621022536 869500676 637708146 989357783 701658823 1361974 232731212 769336449 346566939 668172122 246198357 680023194 26400484 117775475 126589290 575733510 821823853 584588357 47478790 809423499 780191615 336921815 877245174 268254246 452117022 575138754 495003755 966751360 976262890 295758030 547231561 561857142 819266400 849593148 83412393 592870625 316458374 42615783 154452086 799016532 26248813 889668189 700045991 131322165 410247532 82819701 48125793 572759526 790832243 305868661 376848715 304920481 464463081 660958426 784424180 830577814 509389310 440764982 639296077 319119618 208029980 409617331 345262125 94181778 488410954 341381414 772580175 714147769 500209646 297103724 745258572 282503811 337600148 27948299 999605886 442457334 328801144 671514509 131643623 837734373 187242319 783814818 176813022 103498773 321979324 636536002 907348269 173519661 624711499 74455234 821479458 927168304 529504122 306620335 922951567 752882455 659773436 496148717 184525180 847321985 274509090 354084525 631977070 851796758 146853626 527203892 231006588 241693912 638675080 733957509 648656276 92407673 892037780 633125996 717734934 891030497 788320038 969723320 231021056 159286875 104534815 495936805 466546499 822833618 685481698 990407892 282540521 979056494 385164521 860665603 760903325 196113205 130257042 967351103 948043312 238135953 850061260 976705773 961390505 537633134 824518277 696372200 593820565 735804767 348566984 373068013 615238023 518266164 353710058 755138122 292144152 410864937 649411609 196939652 786150012 669926257 556008763 386552069 799535506 427571424 848915282 778166312 244605883 765072676 146150307 422638340 998290972 508190847 178994133 433466174 355570195 619026067 871402868 510897192 257543900 361477383 22683863 476514285 172891193 417201301 652142431 643224641 12476410 296596930 541254571 766945905 502361350 93706832 553645419 903598519 524388017 813250916 365306135 461388253 770996744 743192844 785577427 867705894 211524167 890835324 929713151 92489997 459397571 271038205 669300723 159623236 300519012 405920663 42705465 955361991 218564079 706810871 813402468 764363514 171851937 517101409 637322567 60026078 138542931 472149434 237290674 673949287 990143263 723784267 550147413 437737136 621750904 116530769 159277518 156934054 393550725 114590641 903510731 219652505 573722915 511585824 322103899 151227476 550625407 152871120 265820819 406317427 559523091 792186600 416707007 89881204 983739787 58287137 130616185 592113406 453311679 80339282 257203109 264273587 586767239 732355821 157438529 491361340 947390181 237040383 152331078 517533766 578514466 336859822 268087973 370595926 893612212 282364846 538770864 839100303 573458339 466632366 766437245 289336445 598563684 87358041 50081772 417900428 646146357 216180870 28359096 62223669 504556462 386288543 538291890 98627676 500642722 891966354 94733947 518276342 977473814 991509097 939039040 202634887 806244697 69327245 27302595 1313219 427495966 438278710 596298986 847488410 550221429 972836369 410997235 730622774 198163230 154252051 231293288 700883786 313063741 641924793 662689883 527231000 566460266 976360268 215800878 925409439 870095661 171452908 283277478 438649109 153765524 941102540 242035050 999276227 902276764 227143154 146357717 98549770 455940111 852242230 579819677 529469994 237064788 291221329 39577793 809803871 496769190 843253549 619571771 948283584 722883965 855036775 591272200 246817854 867994930 753312678 753424097 845515802 716275161 16461466 464396215 298653357 980863555 907383139 220932893 213285853 161816715 876275953 157043058 410923544 753224568 38610181 309652191 517409980 247498108 999044029 905308107 40161563 759606679 15678252 230771156 721812718 320914767 282313949 765352022 217403923 147952666 49463812 8921300 271099676 885116860 976795220 527519856 699797180 89754664 961914613 289987868 401495516 116359759 290446961 192057226 561439822 569101235 548937277 200724815 504683816 872096592 959780271 175663773 107002492 127254206 259938892 492068082 486062290 920670162 50783975 108395831 251377993 635252406 436550508 595559856 872350355 723328182 617792784 177406314 38940724 784152769 4471179 982952315 697446490 881042675 425902778 432010131 779091838 308005352 187420153 240741096 258009643 928627162 386842573 617552253 169364490 199460603 827162323 872061079 15157567 364304192 409267433 662769342 786569264 30658361 798774954 890531090 137064997 998482847 828587941 672983099 923131226 324043242 183501307 949669152 445033697 432504701 85817329 917379457 251534764 757000091 779286469 118560158 157630587 356724142 20192181 793743422 577413725 154480045 839706316 390477915 550848106 498246319 361337916 194889176 149209779 225031788 303916123 710525494 190531032 560429221 950836139 431786524 160468482 497740511 380193770 522196149 341761051 413645926 870352149 925199388 788312972 543306150 431647779 272279883 399529515 69926379 180668855 74377806 245210825 679056442 272849944 787084146 503191357 118813788 340119354 671782887 728368658 19061780 121575411 96014799 240122824 223661996 386723340 467709405 846628720 29974118 648902846 878317074 661942607 178372115 526336364 132925771 176293472 628130049 701993598 94652808 290538162 493564714 213574701 828157926 320609654 270992685 172639555 866403401 457191624 435783176 548188985 909653219 357018399 946788679 978032033 600960853 271448948 1143887 370255570 352396030 526898923 918491692 426860452 866006333 956637471 525287300 470837327 838211742 626821652 408373270 965463843 334878662 398350942 47665387 137628304 656790530 532277805 716948603 132231138 90217336 892777870 900484698 237712248 857316306 903661328 518215106 517821163 642494938 192422907 878674484 204653482 192012040 840878551 174703811 796632967 279434922 557532421 439116500 845031886 573766581 587506016 284119918 867196214 892813899 139870990 354205695 593384412 734377408 980178563 904258246 476944898 870742857 664746783 559678318 788317360 220700276 867621977 558849630 819830938 592365972 43562513 94090877 649412916 415283949 83108307 148471655 371225612 685074827 581536634 258362873 80581958 871047657 194866937 63204770 133891003 103580047 158774124 946563210 657714667 248264164 71683318 359554305 856763523 610947179 226379386 473251083 717908577 91536195 819751592 373966449 381135576 368333932 445306193 97366012 643043675 266028011 850879175 666755354 504030329 900868946 641343929 643340188 115945895 313004322 403864316 694559934 501019945 952811252 436289080 22354440 399730890 663260373 276856173 880493306 742880567 864223776 1585382 669607181 69333989 454306084 122183420 501930822 593819397 895066769 157121329 95738900 856889111 731415677 685113018 328873950 914868233 464122180 922389471 560031580 735372046 825005338 845848836 686452796 184331541 902692424 751101311 170347694 669447378 318556560 296225319 476186145 178130795 369817993 289455225 461923260 878579911 845122780 784928925 414044187 401831107 126248549 803518624 837499056 505546136 859613495 261578932 906163884 448505841 337112682 827825 115712066 252606750 189675459 109145402 864075186 979623892 899947744 570756486 656975818 308079555 74252872 72010930 434033536 435966940 49302081 431592042 608576979 953495585 756217766 668352776 894321440 773954729 582789650 934267907 818327429 909020403 436650234 874575308 817861468 838019662 285194203 872085900 330762453 265576941 714682229 12135941 381088872 744535162 710060494 981928776 39524398 533880565 883789763 663427424 564585310 285832606 178039366 709377667 277710213 52850886 473824666 940147416 87293315 319624862 158425675 406431677 690922561 204364427 206747338 686675078 344962424 864566518 619710460 924454519 826852013 224607771 68462720 200424540 586762607 444322817 332616840 915049993 197017929 875101007 9042026 869789327 780784213 424289101 26548789 772134486 589422160 171493658 122890066 402332420 520812986 865544035 399442232 612994710 129372339 393124160 210665804 741220333 986948852 932802223 4006797 656138397 818823535 735037631 125070039 84562464 769149160 680012522 196414967 914088719 374614394 211375436 912900530 977081691 94000739 101366162 859852600 118903565 629340908 217689873 161960711 614359650 595836741 785653348 186447429 280413550 222665751 309968526 118252403 694823487 66363828 267826862 818005915 541748042 273674844 683814805 297260021 428422067 43325556 632487830 279169092 483543478 391979961 686702527 265975430 351500913 311155501 275024253 767014260 874050085 77290535 23539125 441239198 400005923 534116164 373436152 108157934 271743599 66374310 985077196 449214311 966250126 500020746 340087022 62521987 664240533 877481262 980470286 126924012 134587286 94863248 561291797 471746607 807660033 862640578 946396885 600676367 113878515 926203710 305964077 277351566 971473492 842458912 929495766 848029369 789695274 116364169 224302836 50490198 35923869 857057347 876476336 411700109 462396197 220400283 577077946 440041998 187872158 301157329 790569292 41166422 978814741 943331326 362510376 839187116 568068676 759060295 599303423 688327570 324602095 203846663 618264411 535902532 386406675 653986172 240750821 462654041 772699599 204527832 863600425 484423822 110543119 241855994 917516594 946906626 873110384 836268548 620862618 946876050 326336748 360273397 629232127 519081467 300148778 971722755 22160468 238193660 826108616 832203438 288849618 450995384 338277415 179744243 95883262 250690155 414588835 302736779 829251261 154977142 224115238 960802673 503405335 461876703 669407091 487414769 901433751 255437331 599530349 123959304 352273650 978970002 736215913 206047719 737583963 836607364 970009842 799302053 547655424 343904760 460196577 1721197 886245182 381047814 344619872 385845755 624640427 252069003 280372840 423453780 498775692 313022117 700398988 811301831 972228584 633853384 284860527 424284564 281743390 589224178 900481237 182684254 502437320 71858954 266382483 188093205 453713357 58211482 358071863 562699611 744974085 104099537 88118110 224817904 583727172 585025304 580366407 678612256 954083363 601635756 576573176 644226539 562621480 757688508 638887478 73653154 526814366 484239593 979253152 107197950 666166447 286960056 3655089 760391376 971814676 313281573 352856933 153220974 982686081 673372174 765456144 35971526 395470365 22377888 493345477 810066948 975655649 658239853 172538800 277906768 830123495 612037510 776089420 471130908 883913739 361727777 940864894 315921861 606332743 680712782 824100119 291463330 550822853 3435790 885663071 99102168 797022712 779875513 714232619 188317696 542294923 122353324 413564978 537837875 284994819 782329389 960988123 880210283 692008843 283100347 342252644 31234332 533835690 539970129 728871492 712156918 504963813 431098396 974372811 364716599 381680634 90429178 511000526 95372318 680266053 956732796 663996600 372223035 849834913 151297051 730766678 44026949 45733566 724005055 786243215 791659936 374233141 860239504 477246693 697056543 797529905 221555481 397700900 106432664 765800013 927568077 785923813 218379930 222104266 831741629 125450560 311547628 976104893 454044639 330837586 419511104 440705946 192082208 227764657 107962105 640461835 286001584 337160224 978291261 897188014 4001861 944264721 984256425 981315524 624250913 957818175 579791260 766370395 585089570 473326912 994496169 933344839 668517977 394785981 963411901 373972491 485702170 414317376 921724751 874219916 993618082 491039960 475770229 364407274 370727119 917258867 750764335 725337823 257202645 922066720 426178442 151935548 84362310 959294804 508770563 570629983 118154024 883763157 968526830 372063567 806514954 422197401 576364202 584074405 300896112 422797094 466046189 7672868 308844787 507491138 60227382 181291244 435994310 203252187 470275442 529065064 311338486 124328253 262485636 619371174 81054771 395102566 892719069 701663001 82014167 620115193 105853515 377662907 683470581 58143015 433137347 304149828 427856859 206967148 147385108 235593151 503248321 279535956 189877591 290322300 452619327 743846272 159234129 768021376 399516921 237937148 627909110 188535134 869811747 998869678 212030416 107528145 317088808 247276364 497603665 704496536 995551720 465134964 177074858 810640440 933432438 614929247 875280013 984872665 671045380 44440117 114024850 809262114 851174770 437522878 701177100 302326524 598686355 679602131 401053357 158837074 129884193 218829478 393072457 177153420 986303989 93467214 972671859 510385685 617198065 427213553 813349144 776557845 240963973 432853643 758009954 518747195 519887734 711065826 697532470 32052166 713289580 419185703 348063287 803750766 697107470 315978579 672096656 260077115 111324227 992362393 591985249 224149046 916840259 975954753 769001466 659204275 762607092 585128760 301115724 298630065 434123857 623297907 139453974 49681265 529694671 23527348 950383326 589066547 534700118 376965758 219272747 239993645 436604203 211823035 157254338 340348355 976393271 306160134 214116055 736627735 281353203 28174039 256442281 346373115 24677239 557201488 590723436 683212469 771398682 37536811 303118993 697333397 938029446 124333385 4076426 55699147 444268775 964561953 268839675 899735602 995602515 677858427 775100208 85672758 953179032 72699044 26481185 532744704 620731996 275247619 49021030 31895734 939976690 312743758 642046058 85755744 347011568 538941151 114727137 345130773 303606263 913344840 53535194 88945102 646359057 305771209 917774752 201804346 783554361 181540877 256850902 817874019 60127413 928418418 989896965 668013527 496675183 247597819 143237926 778867416 402753057 349424959 850550566 83330424 828732700 58345872 944563714 600099312 850948095 505729081 532033540 551593432 915276121 925096879 44388457 149591570 319507551 471940826 903250412 59184694 417330248 606942638 690084826 877928890 960112452 36497275 540115753 366983591 360032971 365451174 575185900 585159998 825805801 401405530 903001913 641978819 82845156 429145139 565087708 158464433 112285802 303503910 140281033 4058147 269292564 359911296 694250571 162586067 432570216 546441201 849364962 15745976 240059204 420755429 7807402 17188704 199371929 226198456 48432741 981971370 851382417 627424463 939143639 679766131 936888954 195923173 5528859 806988046 926578529 154155944 448331749 872987240 24435332 590571044 631569636 498850712 820997735 246580697 974870828 156827472 83814523 465854276 155646597 504464619 841226255 152761469 887836518 545947413 325852813 359570425 38163585 587369951 547058738 691082798 716240554 286016221 248935337 282741815 39556630 889839448 461369465 606686282 12079468 483851612 982981188 952791291 92310831 585803734 514460483 21288123 301444026 477764193 281382795 861630093 842226020 117345847 755448647 159875580 617887309 553841661 54078105 395221829 443072816 616220323 132873746 577327528 984925767 968415259 603709081 987192635 284452168 45130236 114247204 736458785 299226065 637386813 973936187 135420327 751193879 904324299 547129999 348071211 701829782 387466211 327506277 378453897 628044421 878656528 524501409 763309088 428509312 712679454 745057436 524300599 171622267 247313952 777119539 681097102 90075767 606103789 650062281 838854783 737670389 914400785 640045713 928682529 583455389 179679868 203367232 567075790 311480344 405814197 52004466 553972789 470672565 4166690 860794445 612973269 966304454 57329217 342329877 992095782 505212608 256225744 780623425 271384870 531789216 874045588 69689325 552265965 336903725 361790474 495193722 157125098 550159482 840523621 594434400 36801858 481378339 484730944 523342404 565981596 993483902 664240990 376863675 765412678 80082268 564260137 270557400 712767957 502412258 802214291 772703942 914387151 237949749 794036722 211738887 533391598 272282513 495343379 297855285 431538406 311685762 676513716 460669332 25699814 761240822 419324921 175271709 989410482 201875236 283441581 703741173 331173966 107583597 777228684 130116239 701783013 20584385 220307766 231890169 787907004 341982410 118495803 388328177 376342801 18779683 512001994 834543648 579570945 972331745 945496479 647280837 74505877 694107138 455131455 406937137 793835462 372825700 7188602 887870032 541592967 646483091 516498193 888624646 336438081 143540367 365104276 61134821 794873340 177150786 366444614 258619455 773474648 56672976 882708667 150536451 366551088 653868324 237383072 492967939 394696697 999386710 605215954 759090358 15511673 85036733 765697215 627868275 897714989 816028814 440033846 722450820 185558321 324412487 178884531 31809279 459548333 261019758 5588202 532592735 349451457 497343389 508372756 821665080 695480338 611585166 630140432 242530901 740285170 49065589 940260217 833933352 214960627 906066447 101862363 181327705 297852324 211188733 313753114 805652817 272812846 804353689 862609514 247721670 724665716 726466070 304539968 579167443 52414566 160548444 48748583 508528985 58796223 864621146 187210453 222639435 721597918 461880101 524688125 445248527 599261794 882654879 230260621 351382954 537461940 987291784 3494559 907759793 685780154 597948662 909266675 408091918 56333569 215754310 147592232 956504407 434599934 361235115 428805985 965658766 194512732 633054689 440154203 29702108 524478523 577434963 848947110 787110638 711936500 115545623 961473863 107032520 81231900 20353049 208844159 762068463 976980325 42457687 875049995 288475827 171454549 970709495 382013031 832798294 481601840 286000479 84971629 164579834 311110534 876009297 383009399 693063615 888105115 204223072 347079306 455513448 746857674 733429058 576153157 105090570 559938453 331519168 339711931 466205855 788675858 341122818 726387436 159845539 67456494 606004006 973749492 837685886 268033348 133829666 795421986 956730435 590066816 363703224 819205376 697526995 590594583 319477476 622654918 838846663 871461767 344407546 3606045 929966034 516055812 404747840 569405657 882188237 439020749 309538887 361654471 181528434 507345968 95755945 179297873 905682024 88173475 776523988 541813488 920307828 137716441 323967994 48700175 974865897 10032191 906306692 789478369 777834040 296953215 205470798 614673427 2387799 285257870 436487384 107715980 329631370 149677704 746923255 473533255 999715016 535876849 905117337 235055461 414188643 622751103 599496426 523953837 749210604 132580318 485275030 211765924 996506968 155656837 75643804 27663708 103454711 966920609 891557200 429913505 831743405 562352162 765607802 719685114 48205349 696061708 359149038 50854970 521915941 464914768 463798246 919825529 370357244 286073376 677087493 233702279 303671063 495421248 199343343 337257078 751332005 7049976 435897123 205169899 599539830 965711761 706889243 745201738 893380496 738144969 175089083 842173673 381406244 301337881 74670432 405662507 379181141 557115811 10100386 871398546 965835268 545987257 252961642 319688789 772848219 333144251 264289454 334655097 623812074 376749822 436214854 501792186 946144293 943588588 961693861 113351262 859208121 79960398 363518181 18280312 531274723 717770053 276499629 40828258 893009957 884115811 992677625 413307695 590059768 26059032 321000050 277623991 687283888 517689766 872535661 704794493 99019372 692276282 591030306 767309179 940706259 735497194 774063317 774821219 840604798 219989016 847734704 64761844 341489643 562447285 113533067 691897278 779579164 583035004 338907482 148590204 512523084 2021756 234548555 885226696 635686081 287839368 932462453 873102145 528622083 175509843 338282780 254378884 60200261 859090354 950754144 785349020 725591681 294751933 170523782 846495668 934779272 66567793 611219505 165277154 850210567 948199353 339071147 637334430 218962321 751269380 688159088 679646995 724984019 842828275 76922601 859537883 538919867 280428985 985722030 508783569 499302873 854197951 288521707 291170419 718650726 353480174 808036090 558214964 199523384 191609260 414148364 874250075 790021002 138530519 686514929 114583775 774771818 638819812 998279106 700299858 883324357 853977398 766816951 782859147 417727754 849225799 994313139 38999141 863498217 948275474 112550674 800316513 205976117 848210003 148150952 202416839 2811225 544794377 797129136 837041287 640275802 908758135 910059656 822537412 217031561 223548288 423562872 636459517 642095819 497969276 11586207 929104984 592331930 148954847 438392803 794562847 981830510 415801673 216353354 636565104 823167231 570134187 642317760 959139338 908359830 700525652 641530800 774404221 864267564 453048664 88701362 856858171 559375571 670534630 152244761 267535063 971242148 983567249 644106077 612770039 379472241 937076376 628672529 955400135 716778918 836832714 148156551 821013764 2744483 249825217 108583952 649793992 721057703 33323682 800441083 545938340 71611101 75172278 420740525 213695329 355728578 820142577 344195796 194151358 231500581 976174362 788421307 570857990 802968880 860295302 948015610 713009319 220926122 992697159 598834211 910329992 378501576 978205957 664688187 344385769 56299519 964249153 50051187 708411875 298985923 692218057 475135502 199779027 201305781 651150893 62399809 229875517 495211566 327020862 972957849 144819793 659138882 827160529 175215666 469368800 326932894 949638004 587562268 187384319 386460249 29482413 677894260 166911808 28066575 692923690 261911138 637750630 670903264 355142814 928905058 480389437 70999429 153036079 593295641 17129248 794139381 682106225 544612480 779148028 479497015 353593777 479235611 230556391 271774241 415303548 9351278 325595026 791151220 419481468 202444692 770671298 519090063 50664414 619420025 875342275 967801383 209077365 467878313 56594733 592648419 97116805 568126639 421172474 491690406 874113439 393658457 122809247 64869944 16835039 289821172 504750686 739902005 7879928 853523849 735413683 416049364 431075418 803208943 980957957 395570182 256153317 542609699 559084586 563641961 376432723 717455023 273545691 23590785 573562502 731021767 19806580 506873770 56916020 812653108 405497081 220752817 108037627 3408023 861667224 366813638 415834339 590432710 49793313 310594930 107738239 34948893 73086459 225152672 568525200 949652258 107842136 742704350 227151840 57240257 533954524 828872019 654930667 70397009 6489329 540498400 308596168 623050354 879781787 689720393 237981514 28663917 324671474 155794276 85991783 887961338 779116286 675931358 296342738 39712007 692396284 419302086 128869735 359872129 416494894 365222430 899169353 523865307 489827861 12919011 532985176 611908850 952760618 635472193 12768273 911127835 660315643 715636749 716063221 517738040 856601641 703557765 942308676 526269944 972997995 900792352 58962807 985315964 858981851 41512678 338019686 384250694 901754346 280953362 310433038 41067705 131906618 126223648 521317 510691977 577338884 611804169 74290759 64444646 117010169 236833053 563640708 702919099 82602649 496624113 774820949 114217750 817455099 700692047 785879098 134789003 346968726 259909111 352965479 66927250 849553792 130587423 204401805 912932429 819556051 570650044 434410458 151392994 197917159 515777978 302919581 274795496 21709257 159009866 111610969 167723653 459816471 382179893 230012912 638016576 599939300 108228681 628369153 879441941 173767883 800810351 369906788 777463733 862472718 728515887 950661327 569100271 660248266 240247502 454832484 279293278 120888186 735057323 468511525 16142475 23223260 359547146 834075625 824048261 260893714 728759400 191326972 323052033 739498278 563175400 511838160 848046277 649467541 687872569 275012935 766456353 627232092 864097186 577728347 753551403 97184527 434370096 18916621 150362039 947304792 144924642 133323946 375184012 891181332 49410730 314321678 47219398 891136100 179445474 40523420 503668758 214715256 165075789 836223049 565653175 926096499 296134322 333201740 131783675 355614871 897240340 693703759 541226083 354124511 147392842 863877957 549005979 143429468 38511291 147093322 480534752 455472690 701308658 436634828 776578851 721484487 391704563 721449820 364594181 859821398 473078682 843262442 22885493 16789149 118182983 77678835 780694249 673322151 28547992 819175918 77986427 177927268 540154892 863532480 790096904 766489938 788867644 358783839 804084642 468900555 773791861 143259087 592206847 147297889 891874016 565394735 259821756 94197203 468954178 730624430 915666817 926583008 926676714 935273185 461383407 925507118 174037339 782091488 769925846 217452520 213659960 418675972 523070731 490980323 997440429 699212018 946827307 41456743 122729475 465687487 391418525 919568428 73092414 489962247 706845884 942820980 730404608 134333583 574316046 245898631 782811580 244765150 977565310 667747668 80698600 941045297 971783589 896583959 882968555 440211881 718176180 732754692 307091815 633517871 170031718 36546366 304862235 403557187 782566269 148710515 418081133 181481194 548151371 405299792 249902604 424465009 677836970 594727721 370482583 33717814 949785356 932430571 695486144 318826255 393164269 786716149 6677077 100771628 793931169 481638951 590872991 891866805 352950049 310532030 40812675 606222765 395240418 106421535 536661172 91821432 17973445 619829902 280786571 362869861 993471728 150861863 845450651 704005296 688826848 599712211 48096777 743248790 779733577 255243695 984187284 690288691 648288092 506779139 410485232 29168426 629942953 433302339 284948278 470100761 130054452 978359906 40408637 465071439 907649848 342588506 812577029 453624652 612730581 623877501 225396591 821874534 312836076 958535957 441586403 544109503 663209489 10749412 62843891 702026817 924266724 625147583 40785076 750623251 516162147 977148631 638540949 410791126 72731758 363843664 286388114 634629644 806535487 934753050 301811352 223173008 132276932 688705586 408312256 119083210 824000348 72103670 419318353 290826628 270278958 58212475 356199324 93084601 34822572 164092361 280320956 226308619 756951066 216994699 899314562 300684527 191367289 20260914 918661441 383123537 589129593 820957707 561855162 485533202 475318539 195772252 477453193 592280223 661890668 677057384 570058788 983829680 80024231 424942643 167202854 443835807 140088420 265697973 407212887 557790772 393242321 378408448 896627872 460685943 496340787 469702992 864427853 742305115 396972340 377595755 616595507 800349482 640176757 880502045 137444258 193676236 882506109 962098330 862003252 279501969 952837810 221268074 973333536 859953694 387901986 923004041 279273647 567566266 409088711 904294729 835287067 805021079 973558859 361747827 575280898 846300926 183780804 23824230 30821820 231073001 257515753 815479146 563528942 862437279 750547108 18798477 234080889 658511499 950374153 808376336 237400760 859069399 426062510 456863210 466435092 258097120 313130284 345296819 729924894 771845555 765713589 461082803 778480647 568881083 411276786 241424095 260107465 592231758 636462241 622572289 16741795 787350420 617197212 724065662 28185964 697746759 599980785 899543455 937575127 698805741 619171873 76767448 616941224 993609895 936539419 201252054 700983420 479260630 269666924 176436322 730777719 228316762 349515955 85349014 684926153 107522386 583621986 34497880 286857850 479747414 850895241 959810680 58543209 785475639 252689993 298146827 869276550 68010493 228746111 727471458 430344674 121280716 768639480 809512954 138319433 611631508 830001106 437480996 230931927 896527874 504095544 488288546 360750686 471970732 692577640 416540708 921705716 101554175 640465914 637634731 627607869 363333195 732073592 774568458 742516403 619892803 53849646 263843696 309015753 605699974 989007221 962044386 88779838 127979127 955773183 443530878 994215934 310725260 473703324 603806694 404208824 223407384 120474411 445055856 795169762 509113337 12456487 633659014 195821309 459653994 409364770 207625754 438472056 484598528 159577048 19595371 898134527 799824666 770051553 897684963 444480692 764236205 972831592 834884943 277818984 106955685 204886566 632550360 488049966 197602203 845714127 976075419 787658907 467663018 862800258 854188498 377975788 57596601 334271468 69887726 38714524 804425441 547106949 298160136 666870603 520308275 762648574 350874326 450811365 803068 730899996 444812174 292979266 461758867 142685674 781532206 150827685 228674463 132412039 885578910 999794528 408221991 304102599 401800895 870020476 260458195 939096911 885355995 978409122 316973371 975058759 892765852 289972448 51896615 144358922 322020430 554535157 541872130 125257033 554905252 759317516 905133745 155570356 38474184 30226432 825832412 148049936 620243120 343263150 660877296 958057130 421727013 306851532 677549704 327655636 106947520 708547586 690768240 872647798 824926047 348654551 662335561 311317824 103556397 695237256 413681265 909690310 920532837 223800990 606083109 18901183 538952189 737852956 211650723 957809383 184239602 331702056 405424038 133002235 954089111 240666179 536064661 124808241 862530457 38856975 623799973 726857635 590143205 948821573 775831180 451098807 773427229 921882702 551684123 988362818 267094449 873410341 656578049 757874248 65920420 109187989 131574355 286034103 199789996 453178440 150726294 116109270 19930677 889864229 367091842 150234015 526128543 487228659 696157267 138319117 555359063 546933372 86202193 863054827 760953780 615189121 148991726 507418492 698263419 897164206 949974001 274145552 547489760 382787534 14890158 736113621 769622140 366061135 101425209 830773347 347644007 950773057 198323191 769577865 677762814 288487292 130576068 639611848 330889428 704684584 628650861 936422947 575659242 889894446 213856163 677134000 304400149 924896693 457821385 661298120 638722834 963824225 650923928 284029011 388991279 915780737 276784720 234137259 985163655 722808084 636594491 744400323 678133592 717447787 42887810 779203936 610962204 785709252 650818424 776044967 365174944 898813245 763974889 307801633 12023665 15483303 885745927 379033080 624306449 599035013 215461043 763994465 568561892 510006297 99196530 779284704 586850030 93314370 710870271 144958748 581658751 258106080 334173276 138844285 85660330 60095660 907188613 590257947 716772940 533567011 996629190 646440434 698411398 288647239 724464250 798420294 13188744 681803465 12610732 275292033 542882908 3441598 582043415 981586047 196696484 533887082 860174828 47679222 539706091 649476057 30486391 538196848 99504661 715325583 132997208 187578447 841235364 479276177 474206678 155530253 427207463 505133961 862811024 994583366 222697308 275738854 585129782 511695339 229359633 336563353 641731501 250562342 922050560 910194270 66204668 289816397 703668720 148080491 739267926 750154564 694547700 614442867 718727873 966719629 958834001 283461323 955664296 933107797 789849578 807884275 33686551 122684353 682452453 366673231 592474070 327499529 21938803 222008534 807626107 863343774 802963532 521623104 429960871 440052718 789856994 43506430 178135886 925543247 463345027 885665444 380441427 625448618 789199460 528371523 384371734 4612551 415866944 613350787 605304301 530337073 783251788 136354083 556301247 189572691 600351476 198776504 495652491 314411200 323307504 804577293 497184432 144800852 480907599 571420281 423631578 347333564 188730545 831900032 371184334 646066085 702924451 342610820 360772386 527536564 896659461 997989139 295102978 201766285 103299652 115005551 782709191 394630315 119102430 106824476 422459158 658436236 461765396 356191212 556835382 985080362 114520108 449208873 808181868 635838380 405342858 889615928 498961113 544873813 189424835 134087779 419762719 887617169 817117087 23296590 29750253 725063107 901151363 797781113 287846198 525853997 708261798 132581678 641054897 429824588 507422555 695018625 622207698 432445007 852299085 594241285 413581619 97127030 504866426 505431373 671478455 365207232 632770203 510998233 981019721 640669282 937734461 287698521 730915928 728521784 144224399 60213869 702289455 537368111 382106037 738224060 810256575 258181163 818271348 106133242 69118157 5280722 256320973 111522983 810891143 830305398 921144431 538779631 576869241 241243553 657748393 549982627 211414406 836621261 198729419 922473447 309817355 222596171 92804693 789578481 353083796 678165555 201770914 599034625 418852814 110611934 429754823 567770401 491984337 675405414 941315958 419581322 225127030 936181559 312954466 352122932 336632263 506716089 917674730 273051850 978013661 955222637 465902041 483668013 94995271 418869380 358598641 772166034 648502020 150580701 289878714 79826390 819023829 104375652 3062354 307993150 365352664 946799860 396595602 380308177 842346161 496299823 226502772 697240132 79871641 76638639 676162419 309657665 592316069 146021213 51064688 263205923 258291715 243975130 969183177 283063390 867270225 89130375 967804726 544910315 398522993 788025722 777695573 222418491 46237005 448690531 629024210 717308322 114089231 742420601 995309710 309435019 993861470 466080225 475754027 352872038 781140949 899382135 903998970 426398321 631955357 994034719 604675656 984973646 900125846 506999806 383504388 94747348 71795142 166419549 281171282 113663757 88502514 821230434 751022039 924247316 36753644 460252576 657354739 323249455 526316838 588369273 764171595 34249486 697400369 581624826 765644688 684142314 286027335 898424351 454434778 908017710 882417476 637004314 795041448 691852935 934520086 47024937 625566204 321617539 315733145 448337265 644239039 204917424 834715419 609212966 567148171 145093894 747478447 940013872 508369478 453253171 516007838 60250711 381750120 896677571 772549971 422134757 777522342 888000654 251856124 897486115 960927853 984997968 527278356 719779383 535141510 263268889 926332297 441073764 9158204 743425224 133383953 181683819 639543726 789577924 844864050 185400168 485213532 982364188 964793785 34408495 720712599 223708271 405586194 948915878 56383877 153562288 623263225 301114733 216941699 799603053 247597104 637255996 297043876 698025600 356765134 48772481 902630017 442885277 910935081 101050304 789949046 2643212 88639787 699104854 528566115 492282751 640445760 695222516 966884179 88870090 726295809 644510883 925006534 225454701 937778382 291080646 40523440 936549301 136968897 700363270 385103334 223288320 536015918 461751921 350823551 779784691 919568376 943555121 202840632 625774545 305169375 622909213 727693279 384653265 616066222 729006001 979801506 476775154 870832235 514970736 147633448 105214575 428184458 880499361 510121635 383826327 409538223 669369586 272003360 731823453 101670419 362700436 714034879 544625865 574725690 947221338 270468485 278178227 591802938 176718454 18264419 524144599 494947295 521844775 291401311 105253482 437867645 654584852 72108456 779188973 607955959 56131047 138106707 291522800 571410416 136940515 680986242 635484205 539910865 70221554 673110511 65967478 966035585 172081111 508100100 449156251 643755903 618812656 11141791 423663697 590047229 32190965 300975215 868137522 41822808 548444554 131943396 578548669 230070920 803438982 664250033 641703995 492148078 778516485 678763409 215172630 652643351 166071662 779853213 93332901 449300010 971421201 251024875 35486161 372032064 654281041 88580918 369722976 742241971 29765840 96041003 493039831 149804847 75974436 686381321 975866177 526070400 169504479 461755081 316556435 557109601 126512373 132926309 92803562 716209674 215185440 495292536 284435593 858079277 723378968 172278178 317634779 398109610 589717101 468829465 394987528 451033810 970398837 938061369 331931401 474680431 385548735 701382314 955212576 148980040 992504949 326038511 582617807 893709012 186057524 649182019 962250651 33596004 358086019 947456203 530798881 243605840 860922273 320011800 912488887 583735665 78435552 602004699 434424508 420828610 559017687 609107240 136179970 713317704 711254421 814733206 155627801 812557670 531736161 454276455 597982834 642319421 603891608 818171918 645713077 141209563 847944503 333234445 762476023 296628145 891507096 8724519 414022140 380696841 263674441 912233169 775750927 622839460 850704421 10154197 461168036 610625058 925976531 118678039 95632466 224593274 449950653 142885143 414273808 498407316 312708139 853763994 856387193 801632921 211537813 788533774 607578432 377201949 474168919 326990640 251069145 458629990 347732724 321683838 21560105 325284367 890909349 800469337 404787387 149703561 289447149 142010171 362841297 103394094 893735825 755204303 234903741 308119024 229308970 496881436 671701508 200690181 169352912 942338957 619089034 717944029 226847578 479536152 14836187 993429276 217846526 450903474 758364609 975782283 203397694 201099011 236917942 617972373 304741777 438105160 667750978 983264189 224416687 140671128 496869382 664736800 79406202 950887093 526621438 691595887 649597837 793665397 310414865 630717318 356313988 499643375 413199749 609869008 70689945 28725326 208999602 726879508 577698110 90988525 25530974 84237018 265553749 450681958 36134185 342075712 932609925 912719253 897903354 751641704 237521509 516039902 877469876 930638496 872399719 152014237 549592740 593863494 43240954 792303661 469201416 854951264 84782060 642032390 530479152 304800676 979068504 477158486 298176575 671196025 440368208 170771917 973961698 787586137 186613293 53845870 314525532 825501609 270345821 342546990 63086957 342828400 889575901 224320149 349349917 697202824 541146315 298128339 12509871 702125566 870503155 369541550 326597953 955021732 633337711 183633533 944113365 579196353 568172681 69436886 809057849 623153902 770800406 358201486 673055342 768666189 451748761 822869455 983234552 693532518 854702548 276350986 877817752 77295232 534303182 311628880 514157574 501471041 534993311 623930827 339120413 984403925 650765892 390505227 49865814 205651688 103687906 432693382 12603685 748184404 594980630 653079511 961579090 316662453 727787347 136488475 25612458 442125369 887989420 852929212 82694297 970855407 131804845 944709882 839766487 630118573 802173249 785985037 702175217 256648280 277680380 658714177 364928051 381368904 593117901 210991542 307525509 331489094 222649721 789578055 268641953 619039466 929047020 129485020 720246883 402697797 889951624 610976640 749225790 178071660 632710142 32090559 288159868 129312752 666099903 999124642 640620874 226759372 526112855 203465868 237161943 896466213 834012099 258009683 518784891 339786471 316497120 710382011 827162542 614455440 441690010 251037094 244097812 707403231 191006233 614816573 175467576 687915557 535215721 625409389 475131407 494432211 910786705 148424857 551382342 813854276 393204310 677444557 352559762 683557784 946276450 78328270 98140418 737336351 83759077 422179791 653427961 291990939 389644439 379251396 317324652 454490406 471918506 271558159 837132534 985955812 140970601 869253404 491105476 408139370 354198475 893589832 840132525 651852799 216665296 450040262 454933568 344607966 968848065 900506089 343445279 370543448 787662788 605401862 869449755 491087363 907939836 815877106 630169451 879214280 742492593 775571489 962759759 891025855 467464880 284714617 932972201 848107749 561966840 47408253 572539641 417363139 49067386 588378694 793983363 205279949 282600855 620532124 493376661 805196044 553142394 902357802 595209315 990315196 403113239 462905215 878139674 417116451 689723084 521511871 99747295 833348843 269664672 371728884 190253197 502064007 128155447 281812174 775245290 742267437 74399282 987717205 451328028 216734245 891404234 109602791 533240204 783225115 196239968 371051250 499265949 966215615 167840586 624351651 454410566 103812944 13011061 319422468 183511296 953615944 115231943 404976525 617129015 720068338 606902507 27045860 664183955 335131209 660366362 562842976 138279366 316012654 560609648 844708675 666584765 94887507 511525508 297073309 705914038 806035101 283152907 425408761 655708304 408210601 357218750 796625711 497603119 503262950 8562438 458659682 182565938 471273969 189761618 886448443 270470560 53454809 682927866 660634473 652065983 507678759 405675439 738219647 742951025 588025053 640768482 681776121 907474256 197798762 108138726 487933259 329095951 676348566 162584519 579323192 985055060 81277342 904680252 796610482 33137643 45500500 634950589 220192608 366027489 53958849 762249935 987229037 383891853 278393191 350891004 401178453 642073523 866190785 107679925 103291125 790453984 935060905 502055084 10684954 95050175 204754120 296067881 464463916 244000201 686437831 335848543 327898797 714733368 222212799 846472863 234652473 663628612 700567695 548786308 892091414 921551304 796303782 792219363 260326616 218630684 855437054 664060195 621402699 47957108 734175234 893102792 341060781 599611456 353772670 514245196 52937122 838403587 11606973 629052293 952054266 973046238 498235097 639254640 15923398 9061617 950529447 718605054 806260883 176640079 791937557 882795070 233020155 511512170 670781069 364714175 430326023 437077603 310779635 519699003 93810725 958073488 157997307 567224765 723389227 658347677 955436644 150956595 252946565 732506881 907417712 211697293 172955303 167033564 331492219 127112036 153172998 44312424 894653793 60263811 566009390 156885460 594365413 27332925 128021827 599626205 113196854 979381484 954145118 616409464 251455973 598985145 132721433 254198653 438872715 413985324 372305833 418726729 128641593 645067326 52884653 954422513 747970855 431952012 413102691 522039156 205535161 472651931 182512988 314862706 270901516 933535382 140343225 947923080 258240714 948627477 709985127 989525877 285902270 585840820 114724337 913905861 756139094 941368122 914407054 593402738 533393664 590307802 233787457 610948971 334776754 997285200 931286355 456346132 33444538 791900084 96510276 986178934 720266601 420435550 8689205 535076483 269504637 304112478 422819097 39112634 370992830 497948723 528748008 161575680 152576872 770070773 661306407 604922722 220664724 641060414 373713938 572243208 966938032 678754287 104551742 403852300 177832245 603858668 467352012 90732359 544068360 617038037 92196632 959394647 181054625 460928010 215016429 251769292 531213892 754306200 594393606 333180444 329948910 601167453 193056178 980069605 223746799 274442208 750102978 399158753 459654861 69298776 277478762 606355362 878029290 915323511 625081895 455262247 631434293 485534710 399125781 800472895 140641646 316343649 844305905 275592727 587055834 403854436 326382307 382593520 924424085 118899792 854786101 198437208 233377319 50375012 650107562 663699572 622607374 12894209 430364042 39376216 10922908 73946900 261117756 136866318 843434750 559934659 386173185 638142118 629893824 676894188 616900204 124671669 879642023 357706548 305010064 916166165 910294517 921895151 520287809 991318370 497532996 871632413 365273090 633055494 851796382 921759476 838481709 326157861 274997389 423310954 944909618 485399631 462695707 803514045 53089880 591341677 724180671 989178277 914824380 727962832 426192975 482261048 831696662 85513796 856681490 286458083 808581602 922387704 542515483 855754917 233883667 272676264 318965326 993166211 901360012 645506430 886135701 4168901 182073228 798937481 741512214 329490435 900186150 84865092 687830788 55292701 541234252 925459131 974361747 357265160 126665380 318069209 873937000 660631745 651795542 869552437 859057474 434545848 155055699 633605976 223048140 328471929 910486558 548086206 797964751 809688198 82298435 738937812 659996066 802119351 638873227 50558336 885004774 982584111 930833244 667610117 567211607 66991351 273732045 315351376 26473392 137697477 631009202 698136388 660162092 537999895 966968941 518037135 686247401 156320226 148597813 416427137 280867617 140519483 225953520 541136679 73624731 967163114 253648983 68726916 23148140 806538890 348680078 590036202 290215417 47278725 862445272 714560124 515512188 281784762 134168982 544857195 876845968 642666611 169463529 722820484 704821333 696171277 15272859 363059315 296340638 486062910 252645727 516697191 508259223 725003104 597424087 14020352 984110441 130525872 430548301 407281346 249302047 1912060 633172707 203423519 538702749 430469173 157643782 584609995 468399393 213722711 680402476 886820597 621179504 556368432 516946515 964862515 558699920 682195424 440777297 186569802 505102488 637765589 358573830 114352787 434674406 891513094 294603319 553413858 1746439 83405435 208561009 938272658 292686738 859867574 713334860 136838115 660588263 900486541 300998956 135805629 299077820 670526228 469744505 913348040 503307044 9600839 203396076 523916222 228181456 88540588 577570212 269560548 542482411 446372588 211189010 507484642 981341205 734103289 169236633 237837848 223730578 989811222 531989674 504038607 418745476 111364469 681502051 842768253 74260212 124250017 196232955 446288184 302730604 808604793 929352901 757931784 930571524 518125632 114027838 916968460 630742355 152963673 208695952 281476074 564927821 254302159 406264652 938846466 196102523 663366312 378692047 989325009 983889351 781472342 641944028 676180053 647923889 891658118 319360472 766271785 44900698 155089195 279207794 296414922 882704548 812460042 334285279 436042781 54845884 499716386 248009769 201339792 971359207 358528008 405776316 729844498 745333022 359670098 708085651 447482095 219893586 952660188 256900794 43876020 294609542 851038464 692672054 859436313 700692261 327102368 622628076 992056553 329467380 162997589 451583221 950795111 811593684 247753588 606326392 656276733 437628444 313022790 504927346 276556177 632697737 929474394 841988096 85569712 778754538 289249959 512935072 742897838 712407699 490222873 623503050 646974845 85357015 576824384 417665528 930892308 461226106 320416901 453268324 858947891 767067981 935389514 279181231 710853761 630958351 501568238 227898288 502691326 807432609 613178706 969635872 67418882 377467222 324969749 659905101 6530241 828716140 27893720 713505102 985777032 552537660 315078219 174438829 125298276 600571817 813358208 319080117 812225511 54727676 174390612 407223040 407524273 798653216 769609994 555086616 13134389 541588374 830942383 912986169 976556025 608054842 288583900 71108873 836177482 322388641 694657745 979100891 554450561 956667737 10365551 868222556 963708885 708641134 113085823 678411571 569144444 565236641 278992057 199955578 520971711 681174130 92541747 277314457 899576459 740160576 247917084 957731550 782923164 90055169 561842743 656026588 493022844 388570909 708982003 339077656 94692550 814027203 840728619 247254827 497415242 165317287 315987147 910322450 200336665 985967672 994793132 501407146 98594378 7843447 445522814 47718872 992629145 575784582 292805597 511585518 269050878 256560839 523400009 462259488 986285744 193615583 759936032 659806160 25642787 60309952 497810257 30855020 541343563 241040424 329696175 473311950 796798815 943182240 687867904 652481717 24183921 460038237 596365679 814615075 283403829 195996484 843142604 682146322 975883245 294204594 795953426 363046080 547560920 865621396 908904582 652740101 567288434 565679070 295437780 566801408 916487995 999523482 401348544 947873801 251694909 305536010 344669333 65714184 902890720 225652990 972596081 969275587 502587813 139626977 701833305 725564398 896289641 753438222 570899206 155872220 792382604 351821247 167968554 676947258 729976889 911526832 225301158 983602333 719296618 369996661 185849045 61107250 576048750 116897330 783059818 842053416 134587333 604936063 994703243 448831025 623624973 299595540 535273032 767028397 82620563 971366626 591254878 81469984 64906484 737764557 443411013 738765172 252605107 502195710 52695117 245341393 737525674 732822610 428350107 424589104 295566695 641334902 471868965 554925467 771525785 859978889 311944773 495219496 434850971 770253823 864522922 107257286 832620087 833194325 790247090 709484368 204308792 46420932 998295627 58684115 990909929 989076953 811387523 398489509 121631730 48297917 901414687 405966580 996568638 740495376 91372267 811674786 815427556 438539160 70196502 405089353 595357674 47800755 991600392 30681156 988588353 2986980 653598678 961825509 546520352 149481298 982548982 818716247 242756694 572049736 992130818 208284315 874666793 371737789 616263142 965010879 166643066 686590810 173916830 962479316 627819119 570181709 169223263 442252973 211211093 231074762 428180959 517014341 592525994 135216220 562218413 368737054 470843996 141362571 363920817 667513492 610120390 707296248 504251164 657294055 44873339 738265993 31177526 882183157 772441656 887200647 420022334 114414430 40070490 264493247 739481474 989173101 238371098 683993696 289164204 134860435 724783992 63315095 872977339 60864502 548233973 791106613 341362562 634172672