900000000 5000 169139040 648939898 360120508 81669133 430655401 41146357 308460048 224720969 503510567 593665264 725539013 6433931 651872199 331749435 415630692 641613171 891906442 121110509 136402244 652281382 713271205 787612943 847837255 634036877 667714220 425012072 425368677 155073720 416897716 155752707 555960213 124293499 411290937 482478792 570954394 95384367 437763531 196810852 746060983 94540671 617693574 108993579 700626234 32096496 246636412 418911105 463229891 656751858 755867323 20543285 53015159 406130314 492419836 9001307 449464093 471548452 739311384 289296119 511822544 55606482 574250743 564775071 566002834 125706263 882551775 162478866 252751586 287815090 581647324 10431214 767322392 422485980 430565136 15434821 296411948 785889713 863059764 79722054 724547577 36401238 259810296 153102831 355845686 176265303 487152001 151832575 265520439 311479520 552035338 381361158 487053083 310154525 782852134 451857767 819745756 646022495 811225422 847639916 882720205 631886684 891926687 102971462 355729537 382707097 679811840 523888102 536316684 407034919 861392184 466086568 816706753 677588949 859390571 317156170 541589061 399007506 456570420 566961650 895817810 474685398 515641170 201716949 531594917 36149962 178331257 84786858 207002392 2224637 824429638 512212352 623881913 270164681 313381697 540477989 732036068 166992828 364764366 452368196 521481450 260554406 623953704 277622671 453299259 65593841 550372811 22149430 846130234 644082762 704585609 101592342 666708838 17344282 433664625 633117257 643601294 332927696 728248856 547756016 646062564 25161283 658591600 93708310 788174590 144970101 411055345 153880074 667158184 172828815 282202088 36425778 774831082 48316441 838165644 244043284 658977319 593965203 895706801 79769547 246137456 271800931 702212065 696176531 838583432 319079347 825626967 193623763 309552160 814392042 814700774 492731176 543778334 470084579 681720582 48182553 782238937 744801579 839862438 435108104 491912526 367852245 578493466 461805179 778765237 89121844 538810554 325742966 559319322 140074035 277610099 193094407 871600126 321198373 856894586 214746982 233237955 659325565 673667376 72947501 891318000 437993018 675982835 555819892 775383004 512424546 732779668 156985608 535005194 377510060 878876921 249625527 792311195 434604566 607419016 554867271 864003125 108017782 593382183 204403778 826007256 66778413 147331064 163589814 552270883 208207352 283701171 418016343 588717822 34144273 276763712 528026910 647829074 440430667 860109658 156146815 450928117 301861511 775294481 362585586 670326066 45243388 563121615 57705980 212661209 156337119 653895899 132552051 590279475 161044580 513287430 35775453 233073191 127826307 637744229 464876333 567370994 211976383 813707434 173650780 335516625 119252558 139546693 671723907 877559684 100110108 179311725 138348267 637653635 439721422 462941089 7140884 433499693 30523621 191800882 19453215 271702844 203322192 214729969 336768670 398521282 19327962 667794232 332078967 884567060 500108634 858666989 209124968 836125917 92363422 466468572 235568525 342722210 443631220 884979885 203233619 462550194 544151460 568082432 247649001 267051207 221345431 319752039 2407699 166250744 138337300 431620007 302169273 874928303 521371354 798610872 381595618 537572793 170514782 393773314 108669596 491482929 470977291 559519826 162082159 423032305 700948622 716656928 65843453 220065686 506416763 831636561 260508 43064926 202306712 601953450 164216748 610286429 172876004 309136342 154290658 886514948 169191348 809283533 499440245 501052558 178261207 398559137 755744195 811342661 441323162 493142750 192999759 533062481 173042558 611283868 158860172 868632820 98024487 205112055 182847171 835400851 88432336 621475594 12375934 729509193 55665078 245389977 281535460 563787025 654976268 678920513 346584488 546755748 268898930 344805578 777565712 849141288 119836004 810454863 79629737 515270994 6122156 374475649 118878948 405533094 187386239 251898535 103677657 888144433 647815 310233343 4392716 670604416 312301169 379033088 181346741 746939256 200612449 572333053 462197108 827014535 61399756 799708262 546589510 838747918 159063782 159594352 375157493 543450456 223414358 310826987 349382315 395408227 172808234 859237911 160984947 485844486 272462746 519235431 164191518 291111018 197255556 484393659 846237056 857430746 238059234 562590058 54476033 135101876 300276787 452410669 95040583 705186138 8177810 161778659 203406390 815338120 519161515 697188993 283117068 482435857 656130893 721333883 160178256 270707862 22500408 88238324 8838203 283778754 398408523 482430704 111894962 244561311 209516237 580691152 163237151 379775984 456315386 640479819 85606101 401744227 560375196 750854441 71605826 139091933 500547058 553698731 101530243 341739951 634602026 663161487 42326734 164541527 465519969 521351999 717573693 883866624 70069493 718706832 778745408 824248930 429777931 726539502 222948892 684774630 158728316 186546639 69732609 835485033 51711225 793042631 605768788 623127339 54753541 488009355 347119426 592637175 678323909 809842954 75531744 888478390 123637216 792568755 82704925 259303331 453651741 530464764 95703808 692381469 608332639 696697525 431660718 530493332 219456518 689139227 210728005 279060200 225754016 845319825 71016449 577672469 119152271 495423936 98825022 820221850 246410854 421332638 163281487 433722908 371013842 588738962 544276119 678704772 239892851 324195647 58290118 896795328 297670010 663134141 390951246 612010910 333990593 571398013 209746600 679399776 875805580 898073710 112288218 857401088 327686266 734586045 86804614 405609745 178993444 875248778 100561816 829637049 908435 827701274 408526806 757246220 76751975 391582778 424796479 875985459 297408218 363807273 716279728 773583283 251332464 834326030 360347675 695855434 534880352 764762776 58341745 886816564 503975485 674160705 107729928 586308242 68426531 360901805 103714756 877399569 198015823 317900749 107865787 248035941 181217214 680803644 102946384 260885862 709872719 715393386 244348107 789350492 6955719 401655185 514988280 654205072 231645410 480762228 193654900 709012412 805878059 864088639 610449470 674909548 435128547 447670084 350243570 396529252 17550555 772037302 384352026 503982399 158638187 859826598 723309217 770523959 300054163 518748707 48940906 289243259 792791294 844580366 206928446 403603389 603128476 852353792 321998840 535933684 71841752 772463923 436862808 692162422 446405450 539243038 225835967 883189325 178289867 687651458 366607367 457701471 237072604 799416355 613891934 813132609 358442114 493847625 166808977 603417966 568616893 690704209 454222153 554848303 370185233 652082198 51759398 667873883 316811769 443764651 94119765 361783998 171111805 702961221 419757646 653233736 280763384 637938561 113288111 518753115 397606086 426580410 574017794 725019361 176442932 504074519 16103358 323416991 696000616 839619355 120906634 530446250 140455456 610322129 81634809 828236539 557804283 881650666 38007089 293820296 552863239 759490193 7900572 585033298 58753828 135125008 296026916 769133269 2207734 239388024 353011838 560676704 560815727 746700277 646324224 851334367 314406210 423768518 209417685 377237222 312468634 875405601 59459631 114096712 250606624 575949878 764786680 782402739 609451000 642005128 301447456 424098744 339257720 384376474 225784770 854767143 231214079 549768099 252552615 394571531 384101488 695892732 13258854 166132941 14926826 128271823 213797644 716956442 687035834 739182870 280988110 443782959 230669744 525816411 413627551 845489673 379151429 618201295 118993604 134524047 224007029 691068835 642194023 717936825 205289337 858971203 324868243 458002032 153982469 596873837 441221403 536982817 67337427 178462761 352881144 890197216 352273297 818702806 446098554 743660370 202011248 549702759 119877256 697086779 294053481 673430118 2475886 771474475 52013897 667821862 173293151 184993605 853722828 860411819 59939864 613870785 165460315 759854537 147201214 491591741 155866327 866016919 477783965 659492608 804844459 831400577 39507775 690575385 591674787 777723257 151618804 642701936 471408163 875432661 536333041 568917765 642795508 776528025 223379059 806914659 711025934 822724766 134209399 432856976 10777187 546506259 542912755 896973507 223632400 852247763 138805365 215803565 143238237 183245527 296169529 637600150 98911261 125700345 655358084 756749624 395358940 490224794 758645285 864215962 113922313 228568392 608578994 690808586 239793243 500573507 257487812 354691359 249220569 642657527 474082619 833711350 199770268 518175341 280526672 724608003 493869616 639232171 110498353 661525379 357863030 535678411 695939476 709510290 365960556 739797470 56454437 493920160 86982315 584105408 506559528 747007712 117688622 627161652 449526048 544966227 362017451 894449633 554331148 726948373 147846470 625881994 419911788 871337952 519262908 632853869 249664241 760875810 506507515 743075999 29839713 82415879 310999573 733293829 646078479 747965279 258781517 896748131 222777362 582356602 433908720 595433676 541036408 664543682 445621244 532446965 666666051 889913902 66309039 805883249 806126105 807813381 24885901 43880582 51401240 817215010 20351861 432077345 854191857 872275371 213045639 598409300 208510232 333517390 106791834 710740297 325780627 817173377 138652236 512690975 118754666 390313888 583310313 893153633 308937353 314848099 145303488 580568662 487301725 536593084 446772440 609929448 609191433 652511391 683104867 889275393 423656500 652470047 242117394 328112119 109930779 121547692 208681470 727912031 62157190 522297498 419782929 899225693 114082852 484920053 211566378 434204640 40461922 874109687 374794566 598609107 411890802 795148037 671504017 752226179 251837610 704126460 131000200 352849423 291834793 678478006 254250137 271881982 12875250 329847863 455559990 534364243 18007562 452524662 73577121 675258323 358165782 456495045 151074656 624874464 278640292 373701017 518814567 810053804 225996843 297316376 654028365 827778978 475910516 840058429 383738386 740030658 435023421 797209574 58468200 491935620 455162716 834532575 561656065 892187220 233752361 654795091 137088875 254645018 150653708 419534814 621828689 764135229 2017121 173292108 266687251 426082286 276638610 843178051 146984249 573828132 781889548 855111315 269238705 652018686 32664791 834827267 284229503 599546632 404655688 615770497 361619582 398564297 311826924 898035877 412230219 551975574 421464908 555499737 71623202 278881851 806755972 859440618 170548957 242596971 29553628 197139368 414788009 479879128 607831026 714165384 468746304 508876643 272961219 753804073 359232246 785106967 216634810 276948331 368887392 442426502 460931531 747303104 430492244 471671251 404886804 454760637 27295806 153349736 499751205 850550467 110974715 243353111 74185542 886723983 333107506 413915555 398989617 589153450 479975454 747168215 486342557 660048541 211704910 454278131 55701005 589252317 203683426 456284330 417826372 802648482 180236694 690740753 550528810 875090791 634523644 794773115 379899571 431022216 246731967 410643382 405077452 412666947 651235987 891562093 245252034 474127158 709390844 881836852 144374119 721008488 775842852 843664978 385110309 495685018 323658400 512014783 112938575 522869269 57163626 494154798 501782837 773440485 752728446 836265258 218316285 766599558 10066863 589764405 231201512 361982521 237201975 531157026 345354738 525701217 168591353 639402896 728873101 770601097 331797227 898148148 270077578 668208581 164217721 452283173 520516679 792367994 36565670 735144610 172541919 604526721 101682350 447492097 321514924 527460592 122307612 846026174 224498295 657233380 47932424 786567592 198753737 707948254 379194357 540309482 149665387 553691689 171513734 556832765 209158373 575570880 31936313 474630902 258874898 821281992 168293642 290082519 433787028 511566992 210578414 734304370 583607229 728309357 626183543 699083039 481103011 546816998 730189941 789807425 155785236 378986315 6338652 685802315 616823262 624653025 324240218 510771540 416529364 551443206 19196447 204856867 119205007 507845460 36812448 50919886 175232127 495020483 259155683 581358911 303210506 556991461 436151689 748090919 279045385 795248957 287948687 450460572 209410043 548324293 300373171 671688370 291825424 517753731 2812140 478978029 449549517 836189299 25594943 571216834 130195936 131990939 276927795 414191042 261264056 379595067 487361651 832720167 340678326 552244334 78955383 644104515 224612267 350793199 419559065 697315412 525886563 786117981 128848625 388042838 597331195 598986553 57120063 126995502 134619872 804027355 14181431 270017094 79511268 184690976 597470500 671212878 749875361 788111067 344417696 843144192 676042685 743747553 379532515 610284386 846909381 853647912 567558662 858898512 7422626 848760580 292403227 468859401 60013881 80173331 289287494 707558901 220469871 367242388 423739731 582329641 90889698 242787663 658147979 691395471 378354546 879865373 467542912 512873003 558231579 647362423 194096656 740227814 269102851 855053099 406822424 863799532 449440120 481892604 509984354 817160568 211302494 810021394 574001144 712821867 566918703 840863385 367007383 574074326 8145069 787786452 110058389 673301242 115231847 461283256 51574934 749317662 65874060 896597971 373474729 400696441 558534191 770668660 298823693 435596407 567250790 672962818 361539358 526537361 404715869 898104962 50304098 62624670 62120483 640419884 558523760 736122251 147916168 763954046 364317996 695540899 201397686 435740134 191177487 637089942 582820743 762232866 33421223 805793380 292997516 593086143 220046851 571796323 680741518 772773017 53439209 780087059 18866051 389877105 94912105 101407831 795950334 849845079 135283629 465401154 397815251 536986346 15951069 520780438 53620402 729748282 169857470 833858882 277757846 877924790 268775530 285529661 172934483 549595086 2624565 61141103 334837248 526828461 116293914 144810542 32572320 523632332 127818680 588152640 443499253 548212907 139416442 236650531 205844957 325516341 13643648 405488015 622030678 680254525 231350654 364125285 60422213 711221495 226562607 705118896 444832280 661283263 267298862 521376349 786372061 806467656 419395334 525487362 127638213 775194650 262303939 518390364 739001090 814780636 46018401 773139488 330842892 663247079 133299351 697070856 491984051 493332986 812809090 821179278 362138456 729859893 148848003 315564145 573525884 807701205 140461272 812484247 541540474 868062817 251216660 782477206 728176896 894778190 568011409 652715932 177328533 659428532 97568185 469782717 418724085 603797340 41254692 846168516 138165802 172872052 606877846 744889172 431130793 643209580 4314058 785897142 182667721 291461263 253186518 658822921 275496488 666909615 38190272 499569807 681783203 702197170 58755902 602538731 545425608 613658157 421026392 574117411 416978087 874591102 603210753 847910855 82483599 363328123 301346230 533659557 554543548 820691176 605761460 685566186 501698998 701861523 540966032 748597232 477457647 784858615 560260921 588972917 243387515 853753471 7769449 40101471 21432847 291780489 50064748 836832429 161212010 588367493 32954841 91443378 798785456 821413715 174438121 280920435 102549671 618052591 477121351 528221305 502310243 869686107 128318357 779226998 634905618 821357038 1538371 712911872 273688299 601996928 647260966 815079203 290845810 657411670 68411116 206989094 588824140 844619921 339685481 667661891 444131989 812751442 10219803 470313884 49545983 185230881 397310802 642550355 456690256 698722888 73222085 408453979 73968479 762770642 674467769 788438480 25388970 248850095 352881749 549951189 714751031 830541226 20600219 577040918 322959082 804161283 129850723 637851747 413923769 763891714 679089037 869696757 356337057 520413946 688298549 723442308 101510183 673682920 733096054 750569106 18940951 131007036 342876902 601019908 312397061 860406512 251316252 790663096 244733902 357890760 539910795 577724933 214206622 518265419 693543392 699324987 137078348 177072820 541058297 752784448 537126801 759394186 311714235 469031134 767393768 895828020 445005268 647041734 800043636 848341879 208468216 557790184 162438595 799560236 309598291 630415899 567773567 714269015 16272502 675772624 640762172 741022293 604013864 710261255 788775392 813209223 33646229 256485438 126880037 672910597 27196214 64763788 134863739 689259753 622452169 799564826 535621230 709659748 304794738 462282166 80990296 872070854 341754991 508270453 497399957 543059974 403142001 489301006 342310039 549153419 144130626 503931908 259396286 460679686 352902925 543413919 51174268 283793894 402339125 698800931 355065983 650193884 208746469 739201265 456472378 559339725 73099065 714325536 3954594 121439737 29235072 70534741 297357790 720530003 314444269 763342712 298125463 868382718 429031947 494879543 108200353 253837956 58058163 739285693 51762509 403140581 511373244 737414689 407972133 562740324 534640517 762725010 503878900 515657182 37705730 284095420 33036924 869966216 148393357 352684775 574568643 723662081 19039401 763528775 393359517 527977859 197657180 287899783 143482762 383926507 483980515 644984612 509170569 686982012 35760578 290142318 405673240 670136444 131646850 281524267 201011538 778745696 49842533 675348449 234664807 492342796 102096148 224520171 162055339 715178667 580776822 721810498 150182206 659649936 101515604 471464044 142534064 557778806 30087238 145353173 70962120 191825810 143565946 369756265 25386929 435141152 280758663 815420481 687065913 704558495 83341176 579636922 53017816 774423276 594843192 764968541 152630569 195563031 226933483 827027473 788153188 833354334 623529879 787155527 615360868 630821405 46110769 828026957 366353169 513754584 368744375 511655942 61039567 686542984 41115195 608366610 109121514 236708418 432231053 739004402 598138135 628854254 247160522 276954619 359535904 525487610 561708816 891704807 154353219 441570716 101171270 474957467 70933253 855067565 224771236 387643349 120520107 611688561 46518646 518110212 225726499 781777806 39326039 356858279 559081281 622412710 18757619 431890058 85541391 414187842 462212061 654191302 255121247 443141264 169183223 417585509 155168520 512157889 342211466 541574978 148763180 212252296 147020432 169841974 26642497 61417930 605170749 653510337 13836089 129198728 183947928 880095362 715357142 734348210 300125590 673706651 285324198 394653385 203791970 499358619 53361553 788844239 161893569 353921200 91396310 99378090 190097197 483848403 179666645 832891595 49923282 247724440 422615485 481027222 350042639 718661765 439421586 497045904 103496879 138677186 210832874 823928742 286194641 397699662 331758503 480189107 348041933 882014652 324462992 654500695 414141420 892831279 230850902 867978851 526898275 862989886 379583947 769751263 712944597 755027607 378257729 840092673 321013685 779329025 64194498 343615996 199286639 755868555 160989663 383458009 385635854 724461788 160859142 878796937 493336852 653835416 558608199 757885848 603155383 741387989 82342394 586559766 190650151 676059322 394292346 435558689 240559206 358576541 171377512 690861137 71857964 841962061 463686633 532125642 271740107 839737982 27419845 450000796 146298721 698602470 196839452 295587083 25365240 134319934 83079072 799063671 485844859 817062053 511015485 657317297 927292 365502576 637496859 891837454 562169988 898056610 496876347 658172071 379885486 869261706 315428213 715596949 147237520 516384567 410103205 705876474 15774125 726305306 7922356 684780321 539399872 786206513 184784534 567234336 498168579 842101722 47077289 747842695 666434875 852863407 253098312 481911419 223104729 796450323 499965261 803199438 647290264 706478633 690560722 760667178 47720618 823209868 243124377 758862456 139548823 683526843 264778509 415406541 406413958 732177984 10248633 716353459 5495820 225893998 261375249 459128869 401496808 402209402 26158683 651678695 406876201 517492431 254520277 464782423 130807362 653663472 436743325 887600091 216531754 852803105 805955594 811841973 25112508 832062073 25960156 26302615 194928117 576470851 264677402 372552707 16562657 368825446 71960882 459098265 62278786 813611510 455436684 821926807 73807993 413016009 198715856 799443470 526249075 637511527 380106355 708099684 35307327 899842162 379153707 600913175 192171792 883066045 88719091 657200779 451132621 831833494 32880915 869292243 703084431 703473406 735594123 783733615 18541927 517859978 713612915 791196424 44601385 85570662 486286838 836562866 552018962 605026870 523919740 732350433 94525237 746966678 626669395 796847647 48179864 853698963 94199652 117867071 296595636 698116883 429351541 825818127 191355939 454040367 29428994 441118722 59292354 514531906 379885646 562947195 283678031 699858672 155068387 665296610 465820172 499437687 585532607 817851534 304350525 649030779 154211273 194665892 57769422 210569890 526695892 717931193 235280392 377375781 758246296 809498931 143886861 490104282 200419226 665279758 70825920 513371796 53344495 763316709 71397868 484764395 53101123 528479372 82672558 458163168 380415251 532491486 208991633 837201618 515105214 811029925 144128881 451469229 594957729 867760063 172071786 871811960 142379240 499235069 51057329 691066185 534064410 724096762 340179618 569666720 76781066 734627663 379488024 605767139 150649452 689247438 483066811 832392082 336105797 416859134 693843420 833969702 592066327 826537139 74372810 450669819 92948409 521223002 311245070 797958656 444637163 616629127 415085497 731427058 764010174 771473026 162945013 587643560 134238103 371464866 433827416 777160336 672192567 734074060 92025262 724342124 624557290 705767410 251476502 787115049 839681677 844425969 324715703 424948685 319604051 613922365 10291516 250365679 197722209 862828746 532530260 662717640 347821973 868253141 201514417 854280507 118371300 303222431 615373412 787084357 10139999 269965478 237588096 882157478 146604413 480332238 188883680 752244752 206236462 755225298 13875989 638528927 434451024 812114036 114750045 324496088 110134122 490867081 329118382 888632873 521739824 883072182 203846098 557550398 436769932 587367997 87765181 391658203 511273153 751811985 526909414 687060983 80509261 175992746 703730883 809403218 512434298 570036616 195053440 841717136 41586762 808816298 13324340 802740456 687377436 796679583 248864671 885668020 689066275 881187737 312314799 479290316 209835994 650022628 146186834 719702335 140576256 398747229 297702716 384290472 204497568 442081025 96040361 445625457 322492531 877357206 207768852 345016112 476266874 868872805 749862763 799917423 188869850 431755435 216663417 822955996 602637417 804467201 395092859 666357372 346033314 384234800 246218253 862995064 739577550 797167079 223714332 810566059 300808455 419007614 296314977 389463063 136162463 697458174 117994955 247925592 170079988 861805891 11269098 159408564 55297389 379970893 493138838 893584048 209252426 265058508 487793856 737898638 111488015 694424617 121677374 177001114 21416228 633154535 66646963 730844469 210053468 652149811 180752572 588669406 597507608 715419869 97311316 202212347 160893708 324118311 57194821 453196814 67791959 268749889 52897536 612567121 461623845 590690119 231262099 266264810 404651680 781301361 21949074 641876881 87828201 425817017 680041954 817638495 444858112 829528462 529642111 611845262 290825682 663332149 404706075 689843881 113972777 267760095 74503125 287716767 395184544 670812306 65107669 568216802 425961506 803664840 666927264 791835512 221061238 764356697 521270778 662280847 112206813 447264202 240266648 678138223 344804003 656421376 122181757 449649321 4494311 714726348 189056123 882999918 156728790 347612845 616431540 754683328 265952788 326156048 89697288 600303745 36119529 40492715 223504891 395047718 311835824 448473921 328794612 650434229 592608923 776279443 27993120 298121049 42201953 545054843 457634739 683969781 220874605 362114398 231838413 399883443 291946124 522879829 343136103 737711807 227223410 384855817 81496234 135120945 302827645 571022891 416966562 464039791 158192937 309643444 653913456 665869699 167190036 455952162 319882650 872286335 424315107 827331571 149913909 367999856 152399682 807521340 237312696 534492095 68596467 632638045 850861221 890637026 20489391 70336726 567315160 584094609 128231545 637268367 242017373 669070797 485536748 501019853 170924746 242793500 398899265 877693856 354289810 595233301 422278279 668791004 386556748 858192333 69569615 98083948 4702720 483618547 54359899 480478864 708132478 818519094 564269280 671563187 80299641 879039583 265412155 728729405 31205684 197466417 73784536 539376785 258934929 522647914 292046492 642161831 125589326 617289229 283633859 685858674 238695223 285096104 291389770 780693363 311884598 699549160 150349987 624138350 426925421 813941432 529987503 785914271 183486195 189865112 300140129 635812395 94620000 424962521 139347008 230189761 651601757 656837718 487470729 703118460 78563570 705265537 611592559 765730519 434046438 670226457 602873474 799285213 50364425 554061952 412737901 664455575 548704490 830005680 625021744 635524681 271321004 815239039 343249108 569204254 379004485 625403504 34309608 497502476 500553516 508715315 26604758 779505318 85623101 722665478 805206202 815758266 249103017 679918276 317563299 875216125 205449346 879644582 95232227 332250165 485114924 628024876 181262517 537831855 79244743 114037885 132670660 426296779 478373503 533855781 75143932 551387933 124207772 339558957 482324701 854994066 173585149 496622486 278788026 348271648 599255248 708051776 535783180 734023202 78671000 552146887 235486245 276208598 353451229 500992562 284538618 299939063 665169143 743127927 359241347 535804939 183330949 440851761 166471729 490181721 42457069 562390147 104054929 581661160 216665421 524696502 485118829 569007227 37858961 709222020 290647919 867253067 66483174 720700864 492166145 887573570 423604435 747901459 689302800 793409278 475827029 570879700 51816012 296381056 230941765 375165313 118581873 339740643 404647805 889208827 400677164 787675734 445164030 851665796 553960656 748797051 604639744 616912262 327541238 759745160 170784857 279095084 545414809 661849343 631182256 878711208 644986366 847900472 20784952 442505367 249999755 846917362 250085036 453499569 52777241 191897550 606034388 672876387 5762440 429853416 274682907 293454486 269604958 522341227 351295524 535692096 58824220 451728084 20214817 858808017 776963076 856807938 482227478 634466865 308484527 628465965 394121787 720535550 369635434 822549149 608747804 687293157 71221789 142170069 192553048 620244031 235936624 557807574 342772290 722981485 393829506 486805392 180170885 452990596 146397906 523354346 184237146 498599344 289296644 487756571 709186511 722422177 443802088 828919993 130889106 703807367 171069085 398954976 14689649 762238569 51096583 288400010 442800006 548894429 51561733 147367695 71157784 810724831 244743430 744841169 580220759 728032510 276498862 322478671 152611701 815888948 445925545 511053640 228896797 313948755 188231548 697621628 381343855 468723324 181282245 382014240 569488582 792159525 411437054 532088530 1388830 2045790 647684800 725650701 426027080 659784990 155704901 180926703 102575979 368539939 59465874 493151340 430727143 572036197 454807541 573484340 439867595 504260778 469964239 503652803 129145926 377428657 157679598 873493983 299073894 511920778 463813093 678029576 574908207 806755686 18844938 736506922 33211031 899896034 498489399 776509151 146239833 878247150 606367781 765943378 151885691 501027731 215794792 477169102 766407328 809863984 143578985 867787016 417065938 819998912 251336686 662267234 438485694 514195877 50615359 281351065 450673235 889691601 595988049 858519315 260126103 896753569 100472852 863901409 295340542 337087288 4298773 565906819 72302109 436077322 76102349 665536787 182387313 354803689 43804599 46916621 162462768 515027147 616490901 696757435 192618511 620377193 58761232 541789223 257233209 874732724 36476653 332189293 57390876 600449947 378848322 828395236 154221088 837101949 562190342 741495007 21481766 319117479 373737533 732610277 123193243 346073768 137817076 148977389 756861312 768939478 744626351 783153528 399827958 412682250 56452266 111343994 228469980 489082335 633019494 769779454 406110282 418799821 152053272 588678708 114557089 175705976 697608908 720050447 130006947 370519202 120892728 794645087 2816536 283852373 252276574 648279577 651813864 689628384 352444650 622873208 487702750 682866793 362961336 373817182 333465072 895464309 598694861 861639889 85993385 615933437 325881364 430535119 546337289 824155431 583295917 586037907 104775192 891086528 79928354 175256336 310720016 741041524 7611026 326431333 563565363 820797252 74001191 191972491 184528269 373436164 653760203 713999845 308408251 730714143 527565601 827278750 52018953 546855882 6230984 771665316 49637482 577204466 575167990 656115987 44846293 460081316 337774742 881107532 219568165 811453789 269457041 608964435 101776619 781406882 560926844 855889755 640261295 872859917 427738515 502016409 132010741 685170861 570583691 712613586 430823098 769088254 46845577 539821602 59621535 320430609 138833660 419793041 473113866 636424287 6215734 245334395 93204002 100659271 167208764 432560406 23214873 852380510 25560272 742149237 262984836 786105148 321398677 662492947 469571572 865939894 539586535 777284251 351648962 689335852 280911317 858380934 450277716 741923821 205530664 870376565 31906149 250358618 230088958 754653543 33004988 163800423 154272647 302757174 605733478 759014020 350570078 637407143 657100224 809627815 73261050 875553784 573578377 628004381 377527711 898342583 78387577 307378879 85521303 785031636 1367153 708076119 305346563 594666592 49016392 888613349 518386228 809536031 414164588 756169053 556158027 810334518 96380438 424310530 666571853 885488040 285315993 451042866 315869803 826218593 842061 223443859 728377722 891882978 348985097 367226887 631117378 842208433 603239429 800660073 169165808 867771592 47318539 407794087 3089351 267012979 187223808 898869305 47531902 522915040 90562400 271286352 15856116 496896696 496333837 662284465 185390207 890788375 11964268 506330152 381752627 793051561 270400451 735597668 23501417 259836802 720937513 803373139 612819036 693090892 168082190 609669040 149386824 454218735 620176235 808245171 203210597 662622388 71190326 87275700 342886443 527842659 3090375 48948655 6286307 235037179 218514221 340758065 607291380 680171406 31944512 363090382 247490439 632775006 411505950 417361933 254448466 442108360 252909735 704244066 562998800 665040303 522712228 877644171 727428914 821638686 263969687 475460216 27216507 627544018 409351152 702740645 414044905 755310207 678884498 827859866 344155079 515047969 411079028 479366253 139867689 845075383 170821743 687953404 443000980 744957082 319545564 378917351 396867850 464018192 221359193 456230102 681767689 772902302 341401121 818877979 575078879 829726988 27807141 301459229 202494890 512706656 826710075 867808425 724123320 869771518 80175540 712894306 210525610 359072983 576538436 723781546 115236238 325359397 298410962 539404834 453319484 555299482 136096901 537953308 509001971 604641691 18159493 161184429 547155390 757849792 252948998 576157361 20341050 207225570 369923014 490304074 122763459 870692565 155839234 515965806 113744100 768646248 6028338 62927836 4914894 272823308 553767347 570263389 407582549 525977320 406860241 832721014 476051874 742827937 306733513 809134063 13192774 691079897 172136423 871159619 400109050 792518776 36320146 513218630 546714624 612849671 69204478 561240176 154326726 293994207 330934800 822221821 488975853 519618494 79092259 649792150 568862237 681553264 482020115 856749972 458134989 521941644 188294530 679510717 76256771 95558970 624710613 703414271 316441979 836164330 467761987 649671319 411673149 539346840 225837822 871735357 29178367 359606761 484655822 776541214 198852271 394821676 2045669 332030362 33473684 95008140 178590084 812275125 45542673 689590998 691447767 888600782 82784341 351151281 113457662 800493724 224355430 682348257 381523168 551562362 313373672 866428034 825885332 897791846 602573359 827025300 493795707 565199714 5856473 758812437 43666452 125348993 879398907 880685385 401715141 716396424 62458221 190628886 34397392 549417999 341038338 386296394 300678568 715255215 206566924 209113153 59968971 689100705 368743844 512422472 369243984 781506464 304876322 832296885 310147068 518848459 312261083 708954826 223596322 702135219 131077524 579310145 660293034 811660774 104968505 830813080 416708790 887176818 33541592 119205379 570721638 665307043 55621037 93905864 134016643 275570326 24425038 76800889 650508889 713049109 657900155 785817801 267899361 824995139 853535544 862076757 83167415 107953327 377563617 706668250 263474645 295140162 266890068 531663080 41167241 441467249 93864518 332465493 593781615 780180174 782911501 892763504 51858355 68142154 281213136 536521541 10717708 885941322 162565942 887681286 153832074 627230280 497929379 796329680 436605945 897714232 38973800 431433048 508075016 515538670 14865257 872402738 527752745 550650288 123900231 540806653 399645372 895540316 136593029 458051696 643353956 859777442 150845411 881929754 127509426 829046700 68416293 417674025 415010827 445310055 89250710 537423727 174619288 390859182 162562776 780515207 665514147 887587712 200383431 751263402 119313854 634904164 628017518 632355371 244421005 777337560 648506771 809250392 673230585 684741399 501449273 888118498 292556995 523778540 89319540 717025341 75096797 196046726 320433277 810631235 570564637 794887603 705892865 894827210 32053079 683242732 411274588 835657972 319047308 438452777 401869085 575725317 139233265 240889188 243865071 449893401 173385194 292977292 369720244 810813831 363510733 683576699 327500985 459899957 506847932 651415835 555761920 853261007 39419060 152180459 448263533 473578359 133283402 509097539 681860616 709581721 810018311 820770884 444941510 483159585 360156365 628437182 742047284 776109236 122150270 686344275 461354161 604397772 372266155 720254676 488961583 638654924 213196868 304629175 84859758 288717117 1226863 101008101 231292823 594539728 331886414 853060320 343334935 868832325 362547107 426793078 510450350 820884118 189381266 584247903 118226713 427585727 93768436 363779191 521916077 642646432 162172108 534620132 330445322 512289565 656166177 691139004 580590498 585676046 119902657 769852968 27955995 382318030 507807677 766524935 609167392 653829648 284321634 791349876 298281287 432559021 130456520 198986790 183586470 665386040 344879768 481641236 250037821 423504041 143189647 525004183 83695937 306989960 121702278 737615360 522395830 646042835 83884252 298934324 344353113 616606937 288656060 634946644 394997016 609833460 781257858 893471833 52053597 225872546 224045704 676951456 300857611 661141004 474068896 557520249 131258526 304738639 208758991 642256811 30175987 31628034 723169131 755304796 523252577 707222078 15040853 146951017 309959501 716212554 152464517 478877905 325943099 695465404 218016769 869758035 537590334 665384209 147338145 319413843 188707710 638156706 162445292 531649978 226923333 548701967 15492652 138065455 646758717 832489535 88057231 178438942 164758243 428948453 39733791 836524777 130520239 800549416 191037698 239790022 153332651 847782054 363319860 682944894 348065849 755441024 43102014 895018878 153810670 499931676 339224294 498964703 138644621 432556888 77891876 93167060 444519028 763758620 140449592 675466817 18302381 721099498 93705616 421907058 424069074 765304086 471529286 530669636 530995038 781540935 194123708 857916693 161963622 350357137 186193123 584316067 103316922 226531678 269429326 855744416 63831657 503074933 19432161 882779808 276709397 594026316 317088014 714809950 345082018 732639110 393470035 800030303 182145193 417865113 526600989 756434545 499922191 525794809 81961902 127115377 174685304 431064325 255694075 514252877 309967966 364948920 457250948 788559285 136135550 318412982 652073922 653717305 223782501 352748891 488463071 676217499 487568715 793763465 171049738 369439029 233332432 244283631 98383663 800801161 514923562 687114960 29313927 288933514 337405933 436223453 68964475 308875752 427905791 771255839 135229478 144627748 105494557 636060275 361390969 874310039 54937154 820277564 111293698 599731995 54532246 109843407 313064975 463109179 621695679 846046327 456453978 587474648 251344893 448640527 41429971 494184554 239757643 527672690 70962152 407074767 344243091 617166423 385683744 754312250 342070426 528646953 143180470 481531734 755511239 809288012 66598436 265344714 36465879 332199950 423964809 530959253 525618031 817939463 329313831 484594728 199486545 219009517 111693237 517505238 532294677 762290343 114411712 326231313 766714647 787240520 594334853 675098655 126086796 609247780 60960801 162989249 465487379 632850882 98112585 879523466 525173884 831847164 18893016 464472925 360000913 648178721 112581478 295627489 509938452 825170426 455400537 653471865 376012732 874056037 126703319 663758530 244196185 377311999 20342768 436764540 296387795 832520899 21757457 28124040 599173454 713076136 237995838 592076248 221228369 687764619 135249808 801049634 291886460 403512789 89076683 236237469 484009256 824435806 622181217 886426417 9332480 275828571 311249323 838888900 519759144 871117251 791010882 807474665 150680000 256420005 176512531 328587126 237333790 722588426 125179243 266529963 342200364 435889333 307387034 441220207 562942782 684578140 21913686 591146508 177289304 254337218 206051506 750658162 510110297 876483112 312309588 562128240 29916731 44365383 18356861 865299507 588553090 613564485 210987156 807205072 148872801 414304463 427657282 840871906 244425211 455675279 289151966 846404517 334049279 850682218 57816654 317266140 243638891 581007589 289164441 790082257 607065777 712561240 508199534 576853489 118890467 603620699 282481535 689296106 410725338 776271932 555625021 817450482 348597538 537434103 364645755 831169482 132245760 763464894 370525370 579676999 158235340 342686775 493393703 540932349 413079242 818410930 214074653 562916115 505231585 827838497 82108255 696342023 192272069 597857019 3531691 382899659 494978190 629221630 520882984 864662554 180210356 834198468 333361731 853905210 213265119 403847517 106191442 235423346 264276500 382359322 416519144 605520275 102015217 643118813 145072452 263460454 183868116 397942253 682510167 715004061 262479738 357743131 303766006 477806027 557387851 690108394 243559152 444559853 645941182 755976429 111225656 167408311 305994166 868641530 598777052 756971240 195183424 823241527 108117667 554285556 203636455 733848081 605001760 895180957 151276842 629498997 582406535 737228286 364962423 499502446 589568874 763454456 142550486 792187740 25611457 240884537 824164782 865954194 411913890 661977043 712128943 774252491 98914333 164294333 243839212 852365643 68272167 102042748 170096130 881289305 115612408 553630514 298294040 369893142 134956867 148866163 92994794 861980889 632050815 654056477 253840173 320888915 327764982 736352570 148694582 214507993 202178543 744296673 389113374 549949724 423060838 588021217 78739253 384435250 288345520 634847931 770888098 797465329 617785334 816740131 759785930 885468302 44266380 545385197 291718583 424241849 283758967 845828106 166365369 220991998 78928589 718389268 79013402 688995272 426828111 566156360 578935824 841961366 299445176 593185957 94603163 258683704 163948825 566980969 331046405 698508267 441486939 627423245 48042699 296037164 158366255 160086796 209599326 854033932 414329483 688147430 234452086 774934007 669893136 854725056 89543574 216010247 541650936 829822615 356689625 420600697 184211515 853053890 558724415 827286437 831313244 888716756 299875041 721392918 515218828 715242611 296085409 454139377 695208336 780446970 403228285 604259035 172321517 852782770 242244256 523099046 57472634 367520874 154073828 379109898 53745471 253966089 704179407 840543874 262701455 396394181 95068100 413680590 269479089 878188425 500175336 885312340 148146319 800211750 449868832 552842772 452901111 594548288 769216053 798535156 260684791 718000441 116704958 690379315 195090705 732061352 481612359 594541475 130840581 898569787 74979482 476385380 178131960 321083517 485044135 796679137 143574243 547524912 145106456 193612399 210912914 790171511 541972765 656595465 570707430 889154903 377381309 809980566 264160546 787434580 41048294 139160309 170680113 206348814 42902929 617911082 151481029 308117990 589586389 808066077 374676877 819448664 638202014 757450073 576747970 889681750 168604937 229777859 270155742 289244002 195873357 350152266 506688749 677596943 35005337 326942551 169000584 278901683 185413523 720187938 703413959 784299092 565991741 879223434 28535645 655296689 138252776 628014287 455640995 821082177 334637463 728045937 860524986 882409716 226514872 330783363 19370203 235398135 81404469 641173961 49782313 318395126 76825126 156269755 164579556 490913747 623273493 802195017 198105176 700314844 100519102 155494634 444731353 698832337 73994247 119931688 19782614 124875039 199135690 798614088 199342841 651714293 515226477 651104705 489427285 555269646 53109857 810591256 235355306 268907908 757529769 834187942 20354848 744671066 155557054 616910335 112314975 767088464 117340751 259757941 637201172 673396242 683247921 875568430 671205100 727587614 211848161 347475297 378825502 630802241 206291935 726994190 527805555 724438130 11737658 573303036 50477883 355588104 551925067 739019052 198850872 484339142 276436241 599703199 341197078 467628282 177911508 899367747 645140595 857617882 97588459 479712901 308504584 800111882 178727064 184837223 36086009 705451168 343931143 739127501 326793332 729278461 29012865 474483772 253236104 818343860 58495762 703966975 72087106 226599005 239735943 764270120 356471229 666669723 136013259 662623499 370356329 551009677 32424489 862116132 491011536 773642855 758415391 879660247 254476831 750302094 136095001 366297753 441409068 871954343 152635732 854657630 652984225 825106629 302844598 667355595 210789191 759155025 208044172 739370127 23076290 92900111 248829987 645938356 62795326 447612042 176693571 570861892 181763565 561429972 127131223 827176243 571165386 679002172 48292668 409208246 123253943 785644494 134206870 867842650 481202686 544124055 59744944 238501240 353440001 890803174 603901767 632493180 71271910 821462100 576560963 687263869 322794629 507800416 486340119 793127461 22830627 159346812 194235 794486805 149765984 354454005 77915057 894973831 516008108 689560718 692340158 874072020 485277574 644112137 201498306 461461266 25181276 131731318 664073787 806681542 344482263 872342425 362298712 714699350 506361969 712142694 267842694 605892883 268421318 648865950 173002758 528543205 108324775 115087374 646375730 854004161 155807498 536709182 613445746 888761100 625210570 878502023 525047968 723105944 526051327 531562916 452049729 527051065 557307541 622556986 112061462 585152878 668928432 769823796 244809878 264267556 144454389 837304228 178664660 551074706 114582392 479955177 260626678 294629163 50054096 434615510 265759430 647348668 506568406 886101381 116438162 225858459 175401488 705934030 147805989 340192696 115274721 772350759 203318864 323597315 525108023 710788738 683738710 784678567 490912341 810047159 619453665 680311386 452410982 876628481 448039894 500446832 42357887 772275728 553449029 728375999 155876700 816482720 97506373 642523051 616239097 716857481 80930889 254407804 117182707 513224438 65308471 69674338 718862991 804620547 239323766 475264866 648584750 745278524 556970031 677157451 276697806 584138294 521822628 607005945 113439082 806942502 39959696 839167055 81789811 678911733 56930887 536268572 65559697 535185324 424685746 577313635 55287897 877421053 552914304 743312165 178383234 417287383 326256991 515337871 270706187 848601269 469303454 634583278 463181316 699475970 293841700 679846112 672370139 727165207 367022305 501890758 48064336 282439938 124024094 143081434 167324767 705451164 25503838 255858567 183197724 574899114 296245211 870008909 713267567 830301874 76918866 303260798 208960523 585578913 200572922 864543290 297462642 884690656 357230438 683004380 432271003 783844494 43819711 226466312 56683348 157250189 442552130 733863793 409048871 441931472 376934382 612613869 177082284 808321725 745245149 788502138 359622919 831482537 409685563 820419526 213546416 373196751 171529809 690716595 65184668 628606890 379486109 700784978 253303409 631227483 321371865 775704298 9063482 610354166 19389355 817403022 159354568 716817979 124721855 186338395 477817712 542411753 20820250 682765702 572378036 832166486 228592487 231375638 246979669 849194782 851512486 859269681 309702256 374952336 202812645 857057257 295609381 821701804 672143525 804391269 107711823 876934145 524886814 639136980 364352121 410129760 401171552 632552410 18395449 611257867 114432116 366216055 91599598 386531770 499173509 502045376 393908853 677028317 384135198 682769874 509739286 604782166 238709778 396776547 418841990 649642927 387260889 726395483 489953378 736637053 412553022 757862334 249202664 512091903 43717892 110882546 627727239 649376335 331375968 741472517 103899215 155776420 240793241 796108349 215264449 520990786 172437551 419068293 440511833 656206996 83845608 128410720 52959438 392737220 394337890 444482596 224201827 268759696 4261748 785770122 425779495 747961043 153470878 480399125 207897577 239847111 677906619 751996278 253670582 665906673 287607617 804441896 318854548 500033744 401224227 474785614 140987855 618486922 53976512 329400572 147230338 784667950 126684203 258164195 510052435 702940470 316568558 822861743 181865739 316493103 132878054 726088867 3651184 766971572 250723107 501107063 302256183 864050079 442703769 810262709 661811949 880289106 147977911 463271236 528836493 852351384 745348991 760043986 25269094 306177616 183733463 627591109 67582382 743970910 164981074 868726694 363620324 438094187 394809127 626530894 260844323 807081847 340532521 736060021 397142389 507451681 792211525 898063558 715787020 839655216 479641710 892657212 250847369 830748386 486923267 861416036 144852114 807604308 512146920 887037048 560497972 667579957 348703971 620778060 26198406 299522420 358705797 849391801 286177725 672318102 471936585 894292920 433809227 745870772 154545222 513507913 41909076 473488324 120478636 156313586 337603488 753645631 521867190 733156826 126743354 563640784 305130346 700431466 336043804 523732798 297472645 500067655 61533599 818675465 359173086 894770346 773849514 809577347 792022388 828990815 77092345 512551226 20013054 341325992 81275768 162826350 619962804 712971820 3446372 425637250 474635957 519117654 213928341 437275574 71840537 855600321 74626546 854533770 197629661 209271627 175826935 647862824 565111150 701852600 136688029 576112940 455225534 808641064 210107187 828487885 404515633 615252497 624426465 694645231 363863936 787900658 285728929 600206546 499802440 798385880 772739776 853402125 90639188 658238254 125267732 867565849 122156373 248403694 256447603 617454375 406849074 769462744 506532144 738637042 227676947 310709276 282523004 371471845 722766676 824920123 158483917 427385104 701082821 754517437 181025553 236728808 93601184 375930196 10424022 36930484 354169658 868655514 734150069 777653282 169649459 298994891 519383160 635016432 228278158 488183890 693647428 717475118 129414627 288428675 62276428 444527956 463474931 761415651 88371402 694203649 35121356 120336353 353002624 697334537 97445310 174753227 573868869 673963525 46013306 611883432 160328913 255651964 718474703 771073511 172580024 400610336 353063161 851676477 277761458 882787581 630015332 706308664 380661797 873030511 441879588 555892415 290521728 392790303 240407989 664798978 429583034 448597772 365183343 857756935 514521590 608974709 348150292 685332525 293329756 811421875 282599981 288151970 474679124 620651095 519587849 583569965 119610337 643438857 350582877 639653960 375389844 511291964 130250035 419731795 256305046 725154035 176473368 228962637 272710458 452300149 239145291 869934370 192451169 242751978 171572462 279243738 388084968 895876781 216002697 870361461 4274927 577158776 796284318 863531547 300960424 324316349 248979825 533603430 401312313 661219897 33386477 664813577 586317289 685414432 314356653 386639219 49231532 435687367 819764324 888235063 27633399 862574778 105612122 123228032 101164325 527688988 599006096 828780747 128655870 179414838 345895517 568812056 593019995 702569670 767623566 785789490 644038907 673606370 270616027 382527632 5809895 371691688 235767027 373742633 567981721 784252760 318848253 402398410 55469492 509644550 457402890 865840722 245202452 827979937 26660619 405173846 413194481 893122552 453982342 613752889 821732994 827089240 286457310 672126113 44104432 562810284 758360758 772601530 205801211 642395182 244810630 472714369 478154 776099717 87783610 860417720 505981054 864059111 506836203 744133140 29923787 62025934 81637892 556893763 6535567 635612372 462667424 795576804 109819644 557935831 362891747 457181287 638617630 758781533 390946066 672933823 290277702 389776553 23363912 633874460 318278043 719350669 533685298 837997484 78981683 287927185 377408215 725166224 320708463 497499773 573611964 888097548 25137959 77912103 142039460 512386080 156980206 208965111 488223360 622395209 465709753 568354760 29306875 626370844 449650012 824809234 780539147 822703178 343092985 387361648 349163202 548194782 357658344 651650352 42730575 554077250 175625901 859277830 190076738 721727619 633642087 725690228 580634489 683351404 25099633 436496407 72561022 790380683 9417172 340585875 363511269 555406454 56958781 253829899 722291171 850450275 148893855 750872621 319894981 509950621 558074954 641546560 398031086 699775562 1893524 336777962 44418155 46881522 377074190 625878127 504112255 622173921 139748137 365654336 236699118 602151001 384693775 417223681 541118124 636793674 10864737 545930641 356749225 477886977 50624334 265808733 264673251 805492991 448718057 672961974 141405284 852001331 402596248 463650743 234331121 431276960 687545195 891073208 304732805 367853194 742401122 844844010 816257660 843422366 91644113 744093202 372336937 798923135 64644917 126141608 349724282 832272376 346684147 426973849 281281674 466436252 846895375 893783658 55875273 101642054 700474358 712868688 303846021 738539426 757785693 868277972 374255770 703016177 185264441 576241325 227923936 562791947 33216477 416185169 251797917 378613070 188506732 881803142 677555183 721376873 326777504 879062132 212315677 888572668 3907283 243591608 229443047 856107081 13309300 778341028 96401435 402289454 336501055 547073992 94963463 487420304 443529852 752121213 168552994 323596367 219193956 241964276 34018350 372235580 313618171 330998888 207347609 407609373 296539773 748820752 402852136 650435892 492182794 578475714 41503563 101679820 448363060 599593916 468542353 663601596 285951437 741170963 137825761 460965804 557180603 662666156 262263718 539482430 220841183 414849962 246228070 396027828 310882331 873407256 130792014 187951628 766056975 880971630 78300402 357320533 30552393 145339063 132348945 581120384 406139610 657068958 30306605 302199349 97380023 684425722 803797275 838051978 97359930 136053435 237088120 705481437 215990805 405635876 158485791 662630784 246317252 858365504 682502770 762362596 409733893 799226975 45074498 187970991 318606806 880672858 483452416 523274860 670592843 705733400 518675153 606680569 83309018 218699442 429598439 895054863 463867553 786562695 232020664 322121272 169883463 816275088 62081617 93367975 448570461 790323966 448926276 853240033 7411108 877891372 385285104 807434762 183562613 641672581 446848770 447699540 75070520 891679494 31220765 298446867 149153949 167963351 289826371 737144773 561638015 839347979 408895827 712596785 681975167 876849096 739560744 741025906 658827193 847165161 333761836 807780716 713509388 765698458 173722356 317738931 364156029 540451701 188976929 782885919 277996082 382954531 781885225 810978749 124205395 336866592 459446215 625250233 9832522 870796942 127099099 780050804 343369173 851351877 134360951 423476041 761879999 826735252 62341839 457063295 299391099 568984258 406322482 520622614 404957583 893240295 632653474 683142540 102667631 285240840 174737455 562969498 302610406 384730637 93646978 100225567 177012463 198530317 6183013 812759585 82814807 696410095 165889601 303579640 73341338 849470122 162136440 766815505 260733831 617164395 466726417 836299951 361397200 593233147 504676497 743296915 331433804 816784942 172100577 193791896 163219962 669711332 257393033 357913318 26370474 880932954 138230681 899073240 329670350 715073669 347495451 684898887 19505444 511097751 125452264 266933624 344380044 842384689 209718896 885143876 643740016 648643248 842071056 862406957 399776262 639771359 107879692 197160336 59782128 671035211 189136561 370558189 3684181 536761258 90877101 783470835 387680062 693962619 255618876 440108145 398718015 708269779 225960757 676586715 443249207 684415479 205950170 586193352 288031432 530622098 296176279 761213994 489721830 648872568 292035943 689551610 311676068 319537308 159838774 333550501 692293427 875048211 444838519 491796868 229462827 423934252 568012383 815361859 233674130 529762092 158187988 481594732 233397687 622540519 115666640 395772834 65788417 628446218 625873590 852423808 165394505 550702311 508136567 657441984 442596932 614095945 670812478 810222079 25875398 224119742 239211170 357300347 249064990 498613379 334110764 524595261 97998215 117823487 238563831 792447475 231443083 860713365 271533052 508555426 360014903 765738933 236093424 855288956 93712641 676385655 103242923 593872909 340412806 355151568 14560072 391008534 233661416 292193003 585066702 769331528 125302255 143876986 190393418 252192067 235681163 475413895 218926395 738023362 600825322 836320014 10523360 194993400 291128174 541275706 62609876 574530831 69264766 550594143 64757362 649748072 672319849 797611733 702253606 841287856 241947640 694328026 180009589 488803580 770544292 863993250 696017220 702498126 432130307 599799927 422743202 506967132 583960542 661376332 221329331 512762177 115600815 553259544 543387344 710465566 530033810 632933984 266236023 338956142 492504741 633352821 476945814 758752751 14652358 421706228 332217580 624504809 415079758 567067076 412046808 858996355 118855497 126025242 459516587 632996681 502289250 579809515 25303987 105970413 221021176 899775487 330309332 743594873 175499563 277372436 282830695 297052209 325025815 682930968 619054068 695006240 417466367 597516037 214369639 502847811 556544912 839835208 208131845 468842206 321233841 890647060 323689635 559693495 201074325 730682522 134418471 314050641 50225321 321565773 746257516 766419983 302942977 716565773 94880481 806145148 148176797 609418681 283416035 812867775 393850294 643374920 589724430 867951579 639462675 876771306 258036035 751042523 337527701 448163605 881262524 882940075 315659225 354725842 156789247 619202408 195884656 588536692 36523603 644377524 332225249 374677132 338570469 571531890 290829 303065499 440619332 743343111 93437085 123375584 647775622 764683127 613807911 711891841 184070585 678861706 434840194 842977031 46901428 78199762 129549145 722754506 292856402 703548737 473833403 899612227 11906941 161563603 727468744 829866824 553888196 694444435 573590485 591750225 120267026 778962098 525400523 528098433 575452361 740638203 385089057 692593108 436539175 815422526 602198486 858497979 447468659 675205373 215988684 772627164 574374922 675493227 468760718 795910433 253553884 477461724 476919257 608634839 146158281 785241998 194342669 276309083 589921248 878729083 343206489 815575923 585989737 597634008 724604688 725034205 292035992 890099943 588070979 692882137 106886289 623439761 200068163 620944578 309354579 780742398 228734065 698809428 158218318 730918341 448287915 575341634 382070068 754239953 399485664 751248736 112084843 498045957 212489071 796983046 29753014 373743105 231664302 601499617 748179379 883283321 250801525 450738572 168485223 857413071 695158257 803889358 13193271 676116716 37487059 225269242 47032868 750981440 300093089 896304535 184085063 494043326 92494819 886052543 679955743 874060734 193351851 241635724 470600526 527355779 507189729 789584030 110734423 436040302 7633585 845869390 633772510 799679658 351726067 391939463 161319817 706263032 298014658 418036062 264314167 369618998 529995543 836515458 315239147 745913269 34380080 561447621 302685342 681475589 325807538 801880481 766081159 851665159 66217476 347278011 68461528 523715818 217472869 747289662 594059019 852225012 130864725 263314094 147266660 742830953 322535353 787557338 82617882 492536124 165647497 391227242 442343766 854309402 704402752 809781540 102074858 185552264 51291846 199762687 561713244 692821280 57235704 634767934 24765484 826717110 32111228 660408554 60565947 600721200 245438654 609134286 82975849 111244839 275947885 336694092 344059399 842598627 286537485 330614688 39177428 561327900 654450020 862355808 269514387 729223678 466205718 655643790 406557891 636371240 44550678 161367943 69792957 789257093 251654067 707219908 124750190 638729040 134775740 274140362 220875257 888240375 439083725 843628078 150643186 660779569 44468837 891045477 117533983 734070946 635588284 820332428 520649817 810162206 239754485 295316936 325275885 409317403 404434135 759405078 240423518 492824037 759542884 858926625 70564764 343937840 338619618 409595475 69699184 531706480 190544117 591779765 214313991 351045259 145992857 501336313 448266163 830139586 143523197 810049658 319189766 588741315 91355376 273840651 176676582 402373858 101901512 181224344 342128351 795972954 107699668 323703891 280371553 480473905 230989447 871586543 323333009 528689738 522037036 608957932 610924320 777119330 762775206 873315179 622376474 821754898 624874732 877475257 397370972 410784032 73114691 745494649 632245126 854737288 260086392 398501177 222583366 887950329 431663797 847174792 63024787 100431991 405426655 862504444 435019592 549136433 732873191 894510635 518014185 899170065 87197332 685585411 202649695 382505078 78711917 184409191 244393135 634842460 467512 280135844 294393410 743689450 10012835 605051597 569127635 749013908 287561240 732733701 99683331 140484796 39237941 505439347 209008810 699419811 512783750 545998670 102329978 407525708 189137915 851834331 253211874 399216446 503374891 834182869 137721598 426959463 358617928 762923472 14554533 234771098 24414888 756477541 411184470 503009312 186284127 318085334 395747610 800762754 829488416 879803439 307175777 870629522 510450645 534801902 19858586 480081096 480919361 760759660 504305389 589976060 18121299 420723081 347488393 739060515 543266606 767362402 49314092 199113349 620338051 800555825 328504162 455010723 277994661 780273955 129732346 555556315 456975901 529814617 735730644 888702076 608749041 834083966 82152712 318476732 586045723 837719196 127361435 519461627 629148891 679517538 187960752 210391950 26633924 587497889 357005307 605994161 165483961 227066874 105782788 267279412 211124045 298117767 85659690 665468053 196960247 235088878 174415705 796455999 139719534 269307718 440434810 602370366 43420592 698161939 674589699 750038157 61715510 635823030 346421485 887464112 627412718 748630321 470839395 577146013 218027292 328832561 85710043 857342009 224683645 828160111 427612038 450686793 43792484 234882664 736283744 795939281 463440519 662728469 160708481 853355400 448823145 857927254 365492958 620756823 457136798 659988913 359320538 653486862 373330793 556736917 646102219 798563032 183989084 895466703 232818043 276896915 167315075 848753784 279612102 688999456 135389466 587548136 583214548 698369383 482865575 656774817 610225560 626992663 45556970 722572252 293456273 700801207 277201864 724739637 22442594 645139046 662655016 735897170 147033349 829866564 488606165 859721399 178615992 476775295 420719479 506780470 626647194 868949921 143081070 428417213 374224642 831700175 210719536 787695203 556553173 686049964 181355973 797233766 91039367 342432609 271926611 443798421 107177284 374012986 12749447 529107652 512848955 759045717 262102238 890276574 310937583 723662092 170791895 572154169 100571635 138196985 519581491 740340298 389682154 636979705 107163510 329176317 496204093 688795919 107773182 816349505 211517143 344494273 244889885 538202873 282182175 424840390 115588548 862521037 89160876 331801881 523254907 890465134 538505047 818325370 297325825 372555591 521840922 646151232 17717594 65828155 322985392 761535773 86617596 494928415 560625073 610834404 278622274 663512617 130444511 859516613 24431422 570531073 262209511 334087131 120750726 714032776 94855797 240383407 230805220 608005311 53441638 381121495 248689702 512920570 388129073 421757451 187128274 246176157 74538835 865177753 91920289 761360549 307831051 842939005 89947494 237426162 401984427 890030368 172475856 385351427 716715937 780794419 301699381 369801457 373179524 818231760 150016887 805039657 24097177 123954479 559863279 672271071 446581315 663628663 267379422 787392765 852371208 868136126 571133146 701666007 191270119 871146030 155788733 701652657 355464433 571994398 535199178 553892532 163151529 718454780 25665439 578055852 264583309 626041641 616096595 837404507 499352309 831053906 196061380 261811803 462408860 727172784 487653532 818458035 330205461 396875233 340162623 667314855 54341801 750318095 643466548 724499250 46732831 225700050 532954350 687843204 780748701 893645954 105375309 151768581 551613198 813692040 522699114 812694550 84168152 356768576 275878766 512405510 53402439 629691063 135752770 231904287 417097835 479226913 636803308 646729010 180387426 418856696 132669274 675077078 123900117 331786683 694409320 881344620 269533951 298626075 103439836 600951115 245072665 679022618 79606092 659942790 852253 284712663 300607899 876421700 262975753 661651446 448793976 802420469 39583464 897022041 622256823 710304149 243284166 492095636 213230868 531605042 71254499 248834210 126954120 176839928 323573380 467575413 37555935 487978239 53385148 154127662 40306216 888387913 48816796 823982163 341482276 386911074 405807846 439975368 271001860 338549317 106470888 745849599 252018146 753340386 501785412 781061474 270511662 382207069 519832760 701823542 421653517 776046312 814458176 851130501 13323461 412760621 190134657 866614687 594405526 661901824 57351694 220140153 99534470 510159068 282812424 660646381 317845312 482586716 53408937 369445204 458020749 518033938 254660088 324322441 358113946 839228003 1171903 364930526 217023670 286812514 433150612 527189265 68159282 653282333 64554416 301677585 185787645 551406563 23232806 473577578 148942297 392830896 334132876 866740499 468857708 564214685 311235275 731171374 208446361 708150393 171059536 684709798 308557397 529826516 213818721 586951540 222665345 798305629 723033798 844944640 113252574 171666188 338819207 774109555 269736691 524203988 352205583 352523369 570939386 706527292 159791932 541255185 522041276 856386860 584908952 877509240 375973815 730354188 325677864 668435771 59931012 608177593 56591934 236162055 112492339 224193267 109384077 168474821 759799127 882320955 46031784 308096552 31997605 520653473 660784754 689556068 83143503 349288515 205063502 278433385 226784686 408506622 86652344 660023088 521162632 643070081 93438764 240288089 478069774 581615177 145980513 339292018 11995452 888363124 61559311 537137115 141823160 156275148 332819078 578055935 647965776 776849610 436704363 675461304 286519002 498608938 426929025 785328265 58427265 291374277 156992738 879649690 419416864 522484934 184815287 814656270 76156187 628447655 654733583 672460680 273935534 787730600 709376773 729756341 470043252 733242968 242729768 700856160 320988189 331531863 294975750 874312012 321358850 413263049 493406527 739319351 156523897 824747979 330068986 847594328 266528408 509668924 321547327 812806716 374451866 859632426 164683645 166226310 10673751 78802484 549309430 717038694 342506953 801711301 568564106 828177305 448335925 623329803 366278587 872746054 612739273 825183447 713582796 715415236 659217352 677174482 143879747 210355305 101748776 768115601 291379602 897580434 598544929 667260239 144931984 512516011 522991113 646037775 684726317 715975908 411913879 636049438 451242487 769602838 404850792 518872618 546981553 771032702 262035361 519683988 363776552 679989060 223735906 579347024 51118200 322255370 185222203 435770053 286923120 770737049 36264451 403081986 756613627 833775408 772817321 818441216 632280160 762007529 346004257 793945721 53963786 387397202 59309280 497201792 1891810 800117825 161699951 398245985 618318705 857355916 354071641 843830640 192177187 399341107 412024943 729306973 414071484 424495488 132547885 605800826 238998477 313454140 374255049 374552219 464732242 645881962 38608005 487487323 97207659 176133001 13699228 244903257 397026933 424657843 313339403 856440341 363233096 628253864 667849061 704837525 681502069 892017434 437344011 827083122 312700504 550686903 36479790 483804177 335339116 486214408 36942883 867929594 619005837 815117815 719437996 758809754 267232735 664574806 221271790 556445460 504064260 652195192 445421245 573651616 38554915 625828926 281936433 570064739 6971867 327475420 520703555 600862026 705987835 863997169 360751059 796530664 191178403 295977704 266329015 564212284 117600004 215842365 489993121 549605189 92291246 882764654 286963812 362088804 230656542 387693609 84067316 104796669 26755459 230842237 6518944 360347098 369346900 755701631 421397857 530000977 510549966 662117762 579871121 831001353 270579848 789200659 153266008 192507338 216894575 861954478 36091920 268989403 143101454 489368221 384588366 548218789 571443042 854914664 408078542 779164310 343473573 377159804 393077775 687246402 701332731 859173345 149104089 258485331 5892836 812909998 3935199 358598771 64211950 528745638 110656430 485304362 430165617 710359123 275168994 499315329 367241079 669982048 418592814 453987726 55074907 676753942 205012764 228167842 353389720 689052227 660554077 828284632 151622166 466501279 554753645 644409010 109476210 835626990 282068500 579525796 341509350 361199887 367928469 556373430 269312547 844684808 158566500 483778464 742839029 879211134 91305388 870576640 444486408 829159635 274986990 644023868 153526333 436562825 624869275 801950977 445777178 863542504 154732944 714613797 601810328 651946280 95525782 885718684 174446343 303551504 248841397 577689681 314941140 529264213 421753748 740798380 83039970 544111858 308467596 458541773 419838670 867860676 330335817 435228320 50044973 846970862 326048352 818012350 271913383 701083636 250114932 559409066 359936611 625989685 696482845 882429309 246668268 456838181 266550852 777595869 637450836 674247564 333385315 385991983 214193204 815173340 370965630 704870151 833689548 854270542 280627808 837420652 96158681 250321635 24261276 239615618 341481593 631754532 653430987 657120607 55907146 682824197 497219439 749239802 698603643 842875622 367961273 723200996 624307503 698365538 513694693 721086425 5869445 118421375 295493188 296378346 210805479 763692619 828449365 888292407 290186461 882171660 43167699 380569802 162585119 745845371 6365444 896631751 42536726 276552710 57927923 375358358 507888398 614881027 25559380 222552832 25677508 457482126 199354546 402745069 443240955 705164705 33510524 218294094 192803846 508167023 3445071 559137906 252174858 365732000 432596320 893377826 708462374 899031547 177069354 569247076 586048271 647875149 856145002 876719624 97487077 848476818 165055529 235700488 218340605 466566584 316854710 379715424 385411325 821222060 387127251 628782289 155937093 774909558 221318878 672311874 406140776 428485406 117583893 422188465 829129522 841118957 293212878 640859595 33912343 214645632 648796403 857260854 181606317 893442748 245987940 464245286 436159417 659863023 378469493 896891037 548489185 852333194 538438771 572547583 65189122 623591250 9207464 837563033 150205497 841074193 590933843 803561063 23164219 354847429 27792457 110736825 296261068 799110560 84542658 221525510 72519755 436259213 659327003 803161418 1205797 733824795 17475926 71959148 226459854 734976691 456858928 525158943 313678487 528139892 232933791 822584283 595937201 793865840 160135797 316531111 41159225 486080698 757694394 870079154 29716990 506288729 293777141 849555951 308960215 351008284 373376253 776128645 752192781 827260518 139514932 314153017 629295841 790434028 265090360 695520053 361774995 661087904 141126463 644589427 186905713 693818891 209475765 742323152 167469574 606818900 110606446 242911000 316226113 680874434 309814303 320794192 712766494 877831778 32388021 316680735 698530037 799297855 566772431 645194709 280529106 322490524 651079516 703351498 287538872 774171989 506729803 872476752 408563999 866462834 311575124 551681238 88041112 710930661 223852736 691309296 184719102 488853434 75438409 744017126 296544354 518583567 59762137 656091417 461507183 595658079 742917120 866303188 181733768 476438505 378533064 554585475 139195185 350352319 44676578 871292350 144378351 315653993 323147777 643074133 263230338 391050651 250595876 576544999 363511357 789680008 26346185 578651050 123576122 373333228 73335173 609453918 622577500 660425998 162275965 843507613 519534484 787734869 576056046 642244809 112037762 748536078 1748513 464829241 579686584 788979770 280297719 770575070 617163608 704735541 486257539 724344215 525281693 580468255 326625727 614307364 600416649 697514019 312658497 628528903 340474538 654183113 141758424 668478126 297908789 892081059 126485672 630524498 74230891 749074587 50184730 400071994 591982488 819149437 694105312 850819167 47157434 285335418 53086102 711894337 137666227 186785555 160309528 755207896 303626109 567160411 704072509 881725093 418291289 594220098 87088103 798666761 450558596 823544839 97815735 779114948 637253443 728733777 329451690 549801992 51392594 394597333 497594149 665821471 46603662 197591712 432687865 723513437 707442306 820084734 303197611 380393847 249142286 480380378 424691076 689353409 239964131 606215266 137905762 610406649 163813595 631769953 523024865 802474128 174461633 266875979 580785143 824826142 223332820 514942620 441241131 784599451 143108164 791800160 404336075 792874254 90609250 377141665 219921686 400894093 43422655 409565236 475938771 892503062 513572167 570020117 262240784 555689147 550006858 657647591 457085984 628215917 129893261 808331360 216496174 623386101 629690382 680638440 493808454 573636578 461138017 798673763 54347900 102968220 142909845 281627939 435668716 805179293 486571088 640328034 228854801 648946682 61586280 642280470 289243249 543772813 32281614 154205180 292709654 866369655 136113200 450477426 464467795 743352233 455036554 568559910 275662723 281026817 135016579 463479416 76831746 397327487 548658447 804217928 439472998 770327058 43663655 472570681 353827335 538279775 87713559 817534112 314641610 433746226 127452283 471277405 200906623 291876772 375035724 694997398 33603246 732764931 256726690 880830254 133725844 228199629 422961262 779475452 29735965 820233701 294681424 443818536 389178531 461420779 715911054 734272319 533322849 699922341 5666676 346206734 232950692 324325559 566666774 606239896 152710458 175353260 168219230 596232078 418946476 475919745 13023222 736747246 653234356 672518861 412360885 676823705 186140649 662300131 271280483 720097490 454073642 767074214 33505249 513896239 65431522 262717142 435877291 749319224 213751890 886684214 681285681 685852642 658555611 743896943 16331277 319813933 117713832 325414692 757982877 807954320 261281110 439754695 828997017 840326168 223907581 257989072 62764962 466751186 234885962 488133077 244700107 574616781 378622330 599188896 624965124 782907262 242676015 755741304 240670935 753288030 313931202 727600921 227495555 602806521 364473207 473256683 749506464 855683024 54290849 506440138 100387607 636455921 424392659 511751198 457661484 637391721 231650783 369679470 479267713 691658384 61728656 641905496 35140591 320803682 149392691 787812873 428956773 862854783 366212003 783577441 316862973 823505226 791744969 887039224 268022318 490989913 402628493 718983926 262403609 622421143 116291510 316072570 365183474 667025576 213069122 309345175 13881910 708235616 409754621 541254191 83234700 798484795 235280881 665835749 26459336 245985584 518957340 544546688 788446515 835672035 423833774 802043356 227960231 533300827 123903058 141482987 600901317 685913595 421729686 687859050 263165053 450759780 130893743 729702889 231640272 519431368 289192176 503023144 34907367 637944689 22188371 838086368 220376747 380974566 775842437 833640203 82008858 725619027 395798792 573421068 270732600 749470850 238734565 450836934 860131464 883122871 708443230 819912338 458748417 654058818 520144865 752236268 388490231 662055750 666632198 777631296 73664930 821449465 113477835 531742763 324368596 779630636 308953720 707040848 298738776 330270859 61486493 740105872 327561560 742239233 97672719 412000652 300066644 654086632 391163932 809299243 387273587 407057063 583993134 725509903 192852638 733854189 747485758 755309643 58975079 637236095 6583721 22748524 307985520 669148604 44751000 370753321 110342822 398841871 191808241 565857129 77639935 855191303 89273549 454248628 298118336 749517694 81841920 608685967 47258944 381027891 451176397 721430035 399890397 642380163 236119542 511995325 267625153 868887207 538801093 854440592 61982353 693473827 506803113 693972133 201543420 721423467 383738683 726970436 781817445 865714880 259769231 471955259 12300379 799459141 621840151 688839895 575879899 630190763 81731415 318615228 704410760 828044733 613607219 662530869 208467392 318328932 522817105 690158508 293179695 619791274 675015484 842659890 587102872 654231455 87497074 368752549 414540231 840901388 304804439 714952540 211447354 363678529 3571806 253217428 607815477 648933706 209590530 887776486 699814540 792558332 356384487 470002301 665141556 720905622 210311726 210951777 208906133 432411634 303487108 363274624 27990787 542048985 213493718 492340795 245272065 328904363 257526352 354305018 288745825 846974392 365978405 813731827 132355718 447831566 348174129 517198307 596879284 806334457 408255885 696061357 267769909 492867280 54260912 521039804 306183367 615944736 514454920 529198945 554379505 653824350 302384409 823134141 339883953 555297068 341553851 509716381 616992490 702318862 15145246 708064506 62951402 486961624 231780260 793798779 304606701 388987815 729008521 874356785 104461334 860916819 15826374 91556321 659316650 862362160 178850494 406509074 417419184 731544451 268656036 862043379 496099382 774905416 284356556 711503492 739063487 825726810 365830642 671439862 679419148 777011019 674089049 848317932 163382798 375108193 144624364 431310107 288522344 490656594 111913287 491686131 769934144 781242550 540630189 689140575 8691608 894079998 32493673 664653053 470515443 806542962 382214574 526931234 32939158 62837490 436332397 830475337 279581520 452317938 73469584 811940634 495686940 869518986 91591821 428408404 413044541 503091373 149351807 851988035 253583668 564296371 561663390 745709201 445458050 784725244 44717261 239683755 208132475 354959998 15355102 665314467 227955524 369352122 164867029 828183111 430435179 490530009 403436675 426348951 396538177 413807589 92818744 483302666 87664515 215145224 490748374 553664327 163884497 395402753 459196775 710797510 134956716 891248450 765435788 856685196 71281274 850164734 419370225 583343740 605687090 607695568 31321622 400470491 299242864 817117505 320443592 399077476 103750254 299799125 64094588 332197723 424019826 845454428 596902339 857475991 141794357 894643103 667206259 747768196 223820716 592002454 22704440 152184594 293348686 662200814 66758715 377563799 137419102 781041036 40503903 334892127 101788814 758117210 103675517 152211288 648481857 745962525 776782080 899890897 481918261 702859513 258260647 869704451 237611951 335253890 163601887 802277475 632031473 849519313 357264204 386439758 338580153 394916256 258099119 800880076 697337368 867844047 574793049 631629291 355958333 611269618 429123580 783193123 694686113 844762615 289298291 774116327 493620626 539082649 448732167 750726817 24813530 429021123 37567195 276917142 213923190 834403225 138087616 291697747 510592853 577513500 551297090 665979441 97834186 428871503 492328561 561711187 88144318 534638293 442983092 749141179 333434063 811321313 109275021 829653534 334074883 865967955 457578155 720921755 453031979 817664656 55337196 864200076 334936366 827629638 94730346 152873943 430270224 584585452 448608839 798362142 125508984 383019036 352407056 447901489 277233058 389743830 405023781 577715246 303395602 372810171 552390414 717986271 291243857 387753014 435557915 628530556 295180796 777336397 468064958 789396003 6368011 334534752 30840332 862497359 50079002 528226567 469769455 537099140 280073410 676068947 428678674 594201688 468351835 468401882 195405942 724536266 675828562 862798964 14736865 162939661 293666120 798527978 343146480 861696789 428898279 866718254 35292049 412875606 262882537 870975846 267908859 499433169 79807162 770559594 846167675 890809510 521916347 898429234 564459358 671746600 188271366 447466359 345839578 831169617 277226987 343149153 85697481 849826470 474519252 507890923 315996958 474091550 684638101 779553985 558617463 865177282 16381309 525017669 116872686 524384174 434298399 851547839 197765099 473158405 232074417 405990480 447154985 861233272 422836915 845476358 153394300 243816034 724112158 871822193 712878849 718889060 32298185 859852747 24032689 833084976 33814455 702841907 80607795 719446342 397697721 850358218 279666616 763588733 475565814 707116828 211423652 367908894 13761706 81737879 8905677 248695822 157493743 711345360 533495279 837271768 390729097 831562166 389019748 699103838 94838628 438991214 283341328 552782908 385389668 555971345 174174228 220745467 49226168 866451440 166190188 888520972 419957680 672871141 356962670 854996250 703266266 744865821 699397386 805251844 296245414 786450260 261278975 769427454 95954550 657019997 14047751 126864889 351168368 559521117 473403426 790192234 459162812 840151147 219587336 476190731 161651513 536330824 267297035 772145615 664899119 679031444 103178975 129875079 519294361 643160266 373962150 664620442 789628451 821660552 119174305 417593577 652417148 865768197 555170399 789825464 46936556 206885462 378033461 602381454 454035305 479420856 636709073 831614013 487144423 799320940 403863678 816409141 16352602 21453926 476029093 873388142 332331485 555005823 250715071 755431771 141471627 796102415 62996755 709562319 447583886 539520182 155408571 816023529 497352277 715965855 40994999 295136731 624356330 873321310 523277586 721728656 828487313 835466589 357532316 728444286 82252163 895795234 267250786 320834864 60397720 448399028 195669706 550043567 95656818 486141755 273524966 559019830 364606943 837832930 831955903 848718712 298537174 716428669 175093086 408001634 130403605 412465203 838737035 889616712 566871377 663480760 180645710 189515514 192635943 236991181 621178712 689063429 462505696 835229549 321483988 708307767 158454921 344032157 178639850 641121635 189581961 527579095 552594175 598664580 278720575 414284948 203587380 830918574 498022830 693429004 137014757 810996908 560815897 690889722 93797551 856767801 5124011 609778120 212949139 275237814 106191840 120484919 190040682 446021099 45050951 894714040 252137799 457184436 502939836 605292648 207372565 705508683 214995032 627112893 691292040 836992811 297487067 826740620 769759868 843527673 273868420 284842747 744836238 820652052 142194043 458157857 746637203 818920837 139218220 240761091 618290001 688960852 540005584 803273616 375798166 691081689 66472957 402853609 329155952 375430703 396694711 643956733 365757779 387035929 431292863 732210571 479821578 830978506 36297949 54476834 370372885 593356666 550250815 675239794 74817812 624764113 68084 273023954 202810209 452176367 77682858 261148591 39055558 301521994 150544062 505344045 302637568 439900902 16202830 308554760 688165187 690494866 467244278 475103894 167207146 206283961 380406619 608253423 420343431 882455447 148941789 393468073 618322485 888075322 130793999 773732385 401570283 579014948 243707187 354818989 412998254 533248503 579524194 771442759 535143870 720542871 8399313 501736457 398698693 868307686 355067863 562098757 161240067 531665246 30164267 54737554 252313993 562914579 538582382 713090157 444407183 613869112 58883046 264513828 635637918 878855693 440768033 670468522 484754412 806115863 28437929 786832895 247050544 646501884 142451100 401681039 404301050 599572952 74495732 502496923 677890188 702672572 236002738 515033923 573970902 855419165 69160277 639863644 364181688 654215544 627162535 815258410 86659793 459753643 430304057 812817546 633432780 827810331 160602013 271648230 139670769 369438812 452945332 785136256 58472484 841398258 562413091 752625303 652591638 654101860 91019703 156330148 177087821 536631273 240116405 830981115 318745661 479115631 781452684 853200703 129117460 746797136 9695222 819554868 203996270 681042998 344459010 781447426 455235931 761077144 240842480 415793307 152659164 792419821 520120311 870586522 96753669 695187966 168643203 691969748 715363718 786216313 573988137 829256742 612431162 819118487 477497959 553371282 304838317 772602814 41979445 81906691 79146517 382647216 127203041 489678281 229697969 463413660 329983450 552192706 294475340 673373648 445828969 554274536 397929097 518051878 364881233 434150991 40845491 626311396 105660084 719328281 466362187 866743140 546906924 703297371 755396114 831559579 267021254 895147451 53837809 337250667 551159981 668264622 328873241 717301671 209960812 480060615 234894802 347268690 361746457 596381579 9758123 646617655 720176286 831520054 22313654 457866391 225712426 783929049 202073395 593418796 385948192 386953119 40421306 264893067 145415489 459444980 793263298 802042109 757961657 798839358 52426916 231070271 207983062 300969610 157927449 408540999 181621212 683749877 417572339 682755566 114588241 820603198 557218322 586511241 9726409 489523373 653792143 662843649 812267609 854545942 30337087 579676407 77060249 119460137 536235282 779959651 207932068 724984539 773821101 854976096 97393980 705226017 781942209 797124348 182251121 576061277 219060854 219511019 143103619 309662564 795597677 857808527 383977434 810059072 165278759 438234256 267866795 472704494 81084273 85835753 559217388 617450572 316699116 488022547 7888374 301894174 691907522 845972600 194382747 634345954 592247772 851641942 27199970 625797771 448087160 786861016 600825225 788231708 66655283 575605478 18316946 874376911 276428475 856823673 347803041 867576685 266107936 437452293 301370810 348587709 404824646 483453920 249498397 687472371 178769360 830246838 715197620 877510065 403188838 883386483 74092235 888954890 18363066 754668417 257740969 728136312 16143915 852297027 546729442 576841788 505173999 553103602 204347953 703139808 373500415 846721297 185458462 869677012 366665999 612290539 160868660 334218485 437781578 872468506 18989276 828178444 33519259 150580997 404496605 895147588 488918922 734606983 262946157 321020490 460601296 765170505 82557217 579726074 66995434 212530810 8139634 676503615 429108816 699302565 715047654 784025619 188327975 815507378 278420974 707858822 528121529 675614155 245950813 454121008 329579324 807454959 291887725 605063128 461401926 537847239 492715045 769973911 304350873 690811061 371912595 698112710 55341436 98458354 480729289 578320852 631617588 643573477 3992228 854255010 627401717 768552564 817872986 837304766 38401998 70711670 571578875 641124007 164833238 463663316 279423065 524254108 78809489 656353342 4569519 54505981 190981490 355996004 291357201 322124260 401856792 422506043 148178289 262000554 442621710 833908442 25191709 302415222 746966196 888203813 252616790 424713094 306497669 671865531 632755844 785346980 359881931 445813919 161291216 259490292 523840611 765708476 553136274 780316261 44480878 308983388 244663890 489645736 235956784 729125736 482270388 547383801 436537519 484752450 15399149 368236284 674321666 886078303 462759277 500288652 372048728 500685315 313049658 523444811 107771765 119106743 47362841 126539884 243517400 512654036 25027214 59993689 583196170 747388762 213089366 671588560 527242332 590398186 225015064 347420236 390030940 671610307 176491272 690381216 659899835 708853120 263343266 708737775 794652287 869902221 84133597 818668302 470591718 789035734 214982082 873187258 2590697 30452831 501727165 522040857 141191086 762219914 61268405 80427798 127650757 826538056 257862616 672546872 170795129 493346286 827216679 884098553 244815611 430774044 270049400 682190503 265608866 578018475 706401139 745480674 193224602 346518402 63558249 70827125 305586650 778582956 79901037 853148695 410859413 541187698 289130210 355673561 318943654 522082984 690395435 831475836 641876418 675006128 29665593 493081058 271353781 452800044 561713810 892070098 624837707 644702278 485836155 629023199 636199834 794442964 111664446 569442957 20199696 390724413 60521776 548687869 292570457 877809606 656748283 852030276 367193034 841263011 312381749 734048134 413766843 740218321 110031185 795926358 402125417 594471365 12895981 311630466 43447662 647688967 198351720 206840299 222058590 546195434 550830822 871456307 429917736 817416317 17345019 444162131 155389943 478894094 167698949 849371630 92150865 536864803 57144706 709174958 184888739 512462126 189489908 681109312 578236458 742346967 140191994 520540950 473979923 741234048 426420854 892782934 345791016 689246305 562705248 621044542 524798406 675051129 214639655 220782819 273478703 663249552 223950016 514482168 109376389 388805981 199178805 230323011 316428446 733562183 622331709 884606540 379671745 514109342 671418154 880019188 701138072 850330983 90237364 339897925 150055112 850563159 270305162 381573924 205392851 319284408 175284553 710323987 101566600 463090658 801632136 843937074 649988088 786621447 158252243 314922154 452100811 603354686 329010162 761097353 401828224 848728856 198742858 616111940 688376465 709014889 98344651 370659040 97945643 474543819 262687611 439158812 457999903 535199854 402286974 856823039 60174639 859099114 114780305 477990840 140988212 583915910 100253778 310011937 49222042 697216758 684465232 741416959 597578150 747210010 385505192 596796551 34018910 208737513 95515429 149809101 29935514 91932916 224165620 366963039 315271413 879754824 8978191 796533672 23082185 411320712 207566930 701493451 366413411 713161623 424864201 705330519 51143378 843749605 58477607 712843470 385759556 490003835 97983274 630290587 565950960 785818190 425179321 794219979 380252702 724178023 209835178 419125973 209287488 653261585 286906376 444723833 657977638 898422484 178994418 738331407 133252864 738885006 120696999 186391844 76221603 536123300 50765995 816908760 391676447 572021027 579471851 767643340 137383177 296761725 532777266 666893287 154440243 184145940 437394056 763067748 1463094 82825458 569365811 676658625 189021535 679521197 781111622 847917313 537889680 541391706 474548836 853805365 141555502 614436608 109718084 630020160 618648810 756074938 236395679 834673841 9449755 121812289 461537739 893867750 656615738 757675400 373886728 803530404 200910061 575212241 485059860 603065700 331481930 395800617 102845048 841180936 316378840 344678910 585026070 747604566 165142630 235061105 74516464 887949131 153783528 726149320 165575017 557629503 455365113 866221805 516971518 889609638 160404358 293694501 197191816 653212116 253157212 395769671 4987273 812913086 163041710 401374087 157515807 204468398 557977049 818743669 17353329 65973238 63019190 638872430 43827711 625236871 582803998 651155974 236145191 413041938 453486386 747821132 246178695 525084152 8217677 359211124 27352785 138259600 206246767 209866607 331710282 455559722 670767231 898064848 192011138 242192766 481039430 615148865 282674667 899153822 582458918 731778439 600280759 839917732 205814068 835549714 121653328 187495410 478209220 832038654 204281280 770687869 282704884 427456701 120953150 766568858 118541 704926658 116419810 399113121 342768635 358047081 359955122 449805711 771458214 832782655 280268213 387001650 662340315 763350847 498104340 891708711 99520399 777970196 350156978 728876032 533159351 729592142 358441440 522796911 402024895 575391993 567765200 756167794 267099422 348194732 47918156 203341284 5269469 536889634 242190612 465027891 191009700 602356115 320802266 773214326 262873733 308418733 388318224 823404731 39638341 371950172 654426713 864915957 103774337 845577311 610070688 854115052 365880941 382502453 186322865 802840167 342845891 742279794 316231304 355600917 307404915 507606499 85725590 92716205 293908396 720493841 103305603 571557423 289029856 486208179 869435462 884667099 440274026 883854505 147899003 478065325 341462911 708584581 54950810 344229352 414260428 452515678 31130279 51572700 390669092 896840797 30334710 270026090 241649492 265235934 460781499 680212973 471887936 882816711 157298017 181059976 515732751 676785050 299046329 424650147 50624709 793039512 233779121 563964902 186113439 318267337 264404158 648308181 83238331 289555333 271636075 280596741 568405968 614594782 119987060 306121683 34774705 299499077 206620247 313310052 340442063 782196804 106133600 791391751 348597917 878690118 47130533 701425720 109042773 509359535 379965457 502338504 145088142 529730417 48181574 715205117 298280247 664953025 179868929 630526892 449591565 667237386 313884028 741596795 518668401 735960633 180537232 586161040 233641862 677661524 29918248 821241186 68292853 199997448 230445679 608408788 399376934 606435589 667284289 881123898 661408725 714543103 446184893 790452288 332977392 855081725 14736841 523421675 326117681 656117673 108435395 223306793 128122191 199455783 300584352 516187543 267176460 535521233 101995709 655154429 5256895 173648537 416394608 520788353 98832278 130267424 551649434 759214093 133586569 666552956 25850717 70262681 46263273 858776942 63626091 469016650 749092855 892387067 449436895 840294161 45781009 375411464 352097999 889476949 404184088 876804208 503503230 833714656 507172233 648102009 323711381 731991410 776940862 874764531 131440583 342261896 182805964 585645336 39284473 234855179 425176567 748808429 198265066 566852404 812634057 823433844 628741423 835834915 748552639 788365116 207473567 552639626 90540584 136515413 125961390 198105586 117237858 573566104 121183275 457417647 181485680 253701563 462301339 801514416 315938476 811932908 381112976 455798168 24227717 46073017 375661009 386944017 486894277 855370581 215906858 421497054 355751125 661677835 161175562 634439658 186886315 577126163 509772804 793263328 38522646 466720244 88080200 563145998 376586472 862394686 98510790 140200949 403007150 898241862 45093755 536517267 238538879 362124712 146800391 602690140 60216358 487558531 307132716 818908892 500211349 661908144 174614722 198457627 144977585 420570736 643646728 686259609 22452650 381957021 405701416 584898434 511571295 547255388 241643646 886188349 134147284 514272206 498146333 754960265 453827326 633249946 127014325 750990925 314918570 745840214 288215912 597002495 743150780 854666730 331904409 842596938 147825269 304716934 39297782 403280949 48152115 594245846 13222166 543883043 93077591 622057492 616553880 824141378 272226283 299535877 74098575 852957305 246786578 890271183 396682386 421063362 702116787 811780218 328872153 364487468 92012220 323205872 231182521 271201944 544847748 572226616 58086071 861212615 328982215 482444262 303029489 770793683 459107357 616556242 427540181 499973204 201953432 680269082 702368022 892782951 46297080 760768787 334252568 526867553 800909581 828210413 179391938 754832502 48313266 272973980 555046236 778256356 211618900 312969644 319343687 704580201 223851535 591442436 487693769 699174413 282594001 685007445 236903744 689815435 673947511 758397864 16288355 32284326 482965521 804548726 79101561 305807094 335747291 817098802 528416938 715602447 282629031 732687002 359586242 602146825 111898369 800579666 7877167 172023496 132500924 322760065 72529393 722925081 28727108 703098549 431431733 467686176 363111962 371740360 84871999 438096729 80711691 398873101 33798263 74003900 160217685 603627433 485832333 645510372 571444985 698526096 439022542 828335326 400341681 786994577 169926552 599094400 426154357 575324609 1002134 47318767 62259715 229093865 75927661 780040582 470733440 558650341 698868041 709628601 197675012 811228317 404044985 553460795 160322010 636961491 203719344 783770346 659039823 708172888 236550167 280057184 582030090 725600968 685094630 733968789 319810976 417480699 610372984 853952631 62715427 79544938 156457493 427337170 184050490 438921124 714635165 751726434 358634474 414037897 20248166 753909505 46283850 514474966 770801988 874483904 266813378 582258229 816897541 874298320 46917745 733802119 469944491 842727482 435999677 884398416 331678959 726305773 174196836 524351396 276777756 595726353 104793071 782933950 237145082 530904215 446705995 757432187 447883136 793333453 21853263 484559418 192312648 672525416 573082199 620163494 721920003 846046009 645730620 674492463 147892596 356963250 10403970 391408648 153183862 625934699 362584012 448278072 135005097 158956572 40786850 683095242 92250908 709908501 605584921 678657008 504676636 756625506 612546055 738775499 117134292 819176589 33986928 361255631 53133597 878045843 71608323 597974469 517133017 681559407 63281558 291126385 517024622 694803195 461228233 876593767 67811118 741285167 294621496 825122728 160758621 764666061 220489721 634595935 90409473 287167904 484856861 680664674 781159950 884407541 240823714 532784035 63569132 813408832 268341376 747097393 521078149 561238682 393225875 875453735 48325237 489006280 378915272 718965081 290556640 453985913 326399442 480630760 592502440 717059343 399794112 862833451 483812960 521024978 44555652 522670894 40062815 348951833 145827883 635426140 247937741 369323432 489441236 544053841 213986499 332343830 395140282 737604680 782520625 868356979 155099750 551025704 164952593 423783895 579743400 845781736 157482643 445566762 670074893 898227472 580831050 677784741 317955209 431988676 416435049 494872651 443205311 584977212 817248218 885892979 136416565 796245792 256232582 275995372 39556526 822258505 423704208 710815300 185199518 749752389 138417120 412078959 33767765 102039853 98968953 852629035 825729700 832951271 285197530 288315297 61492384 82472969 131696511 441216113 267984346 666167197 477259826 785475276 522146781 759570380 302846602 353961336 724410254 839679819 759060157 874509683 572064403 611414147 94279811 246417301 416829044 599219251 73286975 655980123 57689055 157429595 294155455 643192191 230466209 394941098 471326504 474113012 650406829 800983265 575138417 821626016 418213965 713840691 54356614 115887395 348274439 414676585 532693464 577422977 138976995 235928639 309381027 664610253 473735831 647622182 821413425 859426625 352983496 701617788 4714895 723212186 603744196 604879197 31775917 543976642 330426958 438171530 267289414 675680613 399374507 770687986 89985065 306251050 386584351 661867954 638022182 674761519 359389437 445553513 301713416 591710507 147361480 525837874 533483018 575483715 771658425 779748547 345854550 791228947 262372951 628067511 204339511 655929520 425022007 562510391 610914706 773239597 621470770 877246294 283656751 596993141 37542523 693552849 594110809 659989126 292319151 396367787 413731088 500733971 138415047 349192204 379825294 740427301 148484434 385564925 189035091 369863118 14622147 590606540 595329419 785560169 460192932 734024573 469781334 721199796 575598102 809828500 72955131 812388692 607443091 719175275 26794583 655666615 192485304 891187970 816155068 868713279 48249145 269034332 465835918 735293090 327272968 781022029 121630487 474879232 103218828 124926879 78314504 416804432 457507442 873380207 392703643 635933571 160795558 802507472 37516862 708489929 417373056 524930080 257558806 604136638 51206444 791388184 209508563 587761855 735941003 759022907 581121627 880809404 210740122 596596099 814793042 830011449 174674602 833173835 82881881 521359143 505234271 889603499 368275218 493262793 572495777 851373879 31220284 471351664 411781775 706119090 705278700 812090147 139716076 842119890 74202223 394313258 82497744 602724854 324965974 475954778 317264092 581900124 576797490 580952673 178090973 330645924 9447055 557910967 186719683 746256592 836673867 891246254 610776698 628719305 70779923 683383161 445379400 632461629 328480510 619490465 287203861 711359754 190521178 445429774 421968938 741176766 100326114 165654209 506041169 629864920 290146775 653096348 66683157 423939892 298664055 427211556 231225516 363222246 457543230 504202652 16166792 673025788 571014984 676082213 142441297 283229117 600482234 622258943 333520510 692562245 236311785 428061892 210367758 441908226 429763813 599512131 532919137 550072436 229122193 335919917 45867674 669585932 684042258 897433831 399254997 574897096 4804400 748365873 273064952 775092852 16690716 497473882 6160987 433730381 377315698 476896970 136030727 430496556 429792869 755521581 55790704 679333961 72737933 739162615 328813330 484522944 103439259 739831717 137658925 435953149 53301789 247707705 79896334 467666716 279972784 606991318 488632596 847977711 5573364 540500676 95791594 410370909 407385803 433230912 654659084 771739814 21198631 193737234 682326230 795125073 169452430 454504822 247140488 613118871 110038938 225178065 521920448 626965991 328986043 573232120 603111597 738611652 30095733 790496112 152977489 324254528 529326514 715231369 250629644 555245713 62615816 838477432 849983930 878555739 82010926 660554628 286518727 636330791 36851840 628206222 151521856 360447311 35263462 648300096 185809007 405459439 527345033 535992872 25649012 782079992 40556564 543428064 394296920 609811426 264532941 508945024 85158218 445561466 706642041 709312559 9194919 685655216 185866645 286452627 131068058 684888399 333107686 446963351 527995657 562433937 449948197 723991285 72352180 235662293 285275175 404214173 128462459 706360985 4556425 137496535 148089423 613207363 728363377 808370866 441381173 735246922 28044672 679782822 204430567 542137849 339598843 357950231 191688730 524545482 282681798 392934944 337441271 564931086 289457934 456611775 255191407 576904945 217139309 309123292 68245982 608921543 55070630 339028173 174079757 247607256 9954332 755363530 128656707 265339988 209109422 815422971 365215292 586540331 162724938 337213823 12382918 477190444 63551546 820569874 628297372 813197285 6547726 394509817 721543058 879496040 207342165 859153009 467670829 892491666 327716485 461053188 179726518 431059083 698312198 782273403 121236850 681593149 501007230 599937101 51720592 493763019 649321485 788107780 129869801 492736562 442807131 810971953 156488218 891327466 433653898 605325011 514221329 619741681 166199563 437915040 671205066 746144788 636478499 775210902